基于Matlab的线性规划问题求解

线性规划是运筹学中研究较早、发展较快、应用广泛、方法成熟的一个重要分支,它是辅助人们进行科学管理的一种重要的数学方法.文章首先介绍了线性规划的基本概念及标准形式,着重讨论了线性规划问题的三种常用解法:单纯形法、直接搜索法以及遗传算法,最后在Matlab R2009a环境下进行了仿真.通过结果可以看出,用Matlab求解线性规划问题,可以避免手工的烦琐计算,大大地提高工作效率和结果的准确性.     

求不相交QoS路由的一种整数线性规划方法

提出求解不相交QoS路由问题的一种整数线性规划方法.首先,利用一个0-1变量集合来表示不相交路由和路由的QoS需求;然后,通过拉格朗日乘子将集合中的复杂约束引入所导出的整数线性规划问题的目标函数中.因为约束系数矩阵是全幺模矩阵,所以这类整数线性规划问题能用单纯形法容易地求解,从而可在求解线性规划问题的迭代过程中求出不相交QoS路由.数值实验结果表明了所提出方法的有效性.     

具有最优时域指标的有界控制器设计

针对SISO线性离散系统,运用线性规划的方法,在控制器输出幅值受约束的条件 下,设计最优控制器,使闭环系统获得最优动态性能.为方便计算,将求取最优解的线性规划 问题转化为一个关于有界变量的BVLP(有界变量线性规划)问题.     

灰色二层多目标线性规划问题及其解法

针对二层多目标线性规划问题,结合灰色系统的特性,提出了一般灰色二层多目标线性规划问题,并给出了模型的相关定义和定理.针对漂移型灰色二层多目标线性规划问题,提出一种具有全局收敛性质的求解算法.首先通过线性加权模理想点法把多目标转化为单目标;然后当可行域为非空紧集时,利用库恩塔克条件把双层转化为单层,再利用粒子群算法搜索单目标单层线性规划即可得到原问题的解;最后通过算例表明了该算法的有效性.     

城市交通最优路径规划仿真研究

研究城市交通最优路径规划问题,由于城市交通网复杂,增加了规划的难度,传统的最优路径规划算法没有考虑城市道路网络中的交通限制问题,更忽略了车辆在道路交叉口转向延误的时间,不符合城市交通的实际情况.为了解决上述问题.首先建立了一个城市路网交通模璎.然后运用线性规划方法建立最优路径规划问题的线性规划模型.最后采用桶排序算法对狄杰斯特拉算法进行优化,得到一个新的最优路径规划算法,对线性规划模型进行求解.仿真结果证明,利用算法搜索得到的最优路径更加符合实际的路网情况,为设计提供了理论依据.     

分片线性规划及应用

提出通过分片线性逼近和分片线性规划,将非线性优化问题转化为一系列的线性规划进行求解的方法。讨论了分片线性规划的性质,证明了分片线性规划问题可以通过有限次线性规划得到求解,同时,给出了分片线性规划问题局部最优解的充要条件,并基于此构造了求解分片线性规划问题的下降算法。该算法与自适应链接超平面模型相结合,成功地对离心式冷水机组的工作点进行了优化。通过优化,机组的能耗比之当前工作点有了明显的下降,表明通过分片线性规划求解非线性优化问题的有效性。     

解大规模线性规划问题的某些技巧

发生于实际的线性规划问题往往是规模很大的.解决大规模线性规划问题有下面3个困难是必须设法克服的:解的精度问题、计算速度问题、存贮问题.自然,特殊类型的大规模线性规划采用一些特殊的解法也是人们经常讨论的.为了软件研制的需要,本文拟讨论这4个方面的问题和技巧.     

基于Matlab的分时电价下企业用电负荷优化调度

针对企业用电负荷优化调度算法计算量大、模型精度不高等问题,该文在建立分时电价下企业用电负荷优化调度模型的基础上,利用Matlab平台的模式搜索法、单纯形法和遗传算法进行了线性规划问题的求解,并对比了3种方法的优劣性.以天津市某企业的用电数据为例,验证了用电负荷优化调度模型的正确性和Matlab求解线性规划算法的优越性.从而将线性规划应用于辅助高耗能企业优化分配资源方面,降低了用电成本,具有较强的实用性.     

任务分配问题的建模与求解

建立了极大极小任务分配问题的混合整数线性规划模型,提出一种矩阵作业解答,并与穷举解及混合整数线性规划解的计算复杂度进行了比较.理论分析和数值试验表明矩阵作业法对两类任务分配问题,极大极小和总体极小任务分配问题,有效地提供最优解.     

加速度空间中基于线性规划的移动机器人路径规划方法

针对动态不确定环境下移动机器人的路径规划问题, 提出了加速度空间中一种基于线性规划 (Linear programming, LP) 的方法. 在机器人的加速度空间中利用相对信息, 把机器人路径规划这一非线性问题, 描述成满足一组线性约束同时使目标函数极小的线性规划问题, 嵌入基于线性规划方法的规划器, 得到一条满足性能要求的最优路径. 仿真试验验证了算法的实用性及有效性, 与势场引导进化计算的方法 (Artificial potential guided evolution algorithm, APEA) 相比更优化, 更实时.     

Multiobjective fuzzy linear programming for sustainable irrigation planning: an Indian case study

 Multiobjective fuzzy linear programming (MOFLP) irrigation planning model is formulated for the evaluation of management strategy for the case study of Jayakwadi irrigation project, Maharashtra, India. Three conflicting objectives net benefits, agricultural production and labour employment are considered in the irrigation planning scenario. All three criteria are to be maximised and the last two are sustainability related. All three objective functions are quantified by linear membership functions in a fuzzy multi objective framework. It is observed from MOFLP solution that net benefits, agricultural production and labour employment are 2.031×10⁹ Rupees, 2.1186×10⁶ tons, 3.5858×10⁷ man-days respectively with degree of truth (λ) 0.5715. Analysis of results indicated that net benefits, agricultural production, labour employment have decreased by 4.13, 5.39 and 3.4% as compared to ideal values in the crisp linear programming (LP) model. Present address: Department of Civil Engineering, Birla Institute of Technology and Science, Pilani, Rajasthan, India E-mail: ksraju@bits-pilani.ac.in     

计算甘油代谢目标函数的一种新算法

通量平衡分析是代谢工程研究中能够定量预测细胞内通量分布情况的有效工具,然而其预测准确性的前提是需要设计合理的代谢目标函数。研究了克雷伯氏杆菌歧化甘油生产1,3-丙二醇的代谢目标函数计算问题。该问题的数学形式是一个双层规划模型,首先应用线性规划的对偶理论将其转化为等价的单层非线性优化问题,然后采用非线性优化算法对其进行求解。与已有的研究结果相比,所提方法获得了克雷伯氏杆菌歧化甘油代谢的全局最优通量分布情况。     

求解炼钢连铸生产调度问题的改进算法

将炼钢连铸生产调度问题抽象为混和流水车间调度,建立了0-1型混合整数线性规划模型,并提出了一种遗传和线性规划相结合的求解方法。该模型通过优化钢水传搁时间来满足钢水的温度要求,通过最小化浇次开浇提前/拖期惩罚来协调连铸与热轧间的生产节奏。在算法设计中,给出了一种染色体编码来表示炉次设备指派与炉次在设备上的加工顺序方案,并探讨了相应的遗传操作。最后,仿真实验的结果表明了该算法的有效性。     

A stochastic production planning problem with nonlinear cost

Most production planning models are deterministic and often assume a linear relation between production volume and production cost. In this paper, we investigate a production planning problem in a steel production process considering the energy consumption cost which is a nonlinear function of the production quantity. Due to the uncertain environment, the production demands are stochastic. Taking a scenario-based approach to express the stochastic demands according to the knowledge of planners on the demand distributions, we formulate the stochastic production planning problem as a mixed integer nonlinear programming (MINLP) model.Approximated with the piecewise linear functions, the MINLP model is transformed into a mixed integer linear programming model. The approximation error can be improved by adjusting the linearization ranges repeatedly. Based on the piecewise linearization, a stepwise Lagrangian relaxation (SLR) heuristic for the problem is proposed where variable splitting is introduced during Lagrangian relaxation (LR). After decomposition, one subproblem is solved by linear programming and the other is solved by an effective polynomial time algorithm. The SLR heuristic is tested on a large set of problem instances and the results show that the algorithm generates solutions very close to optimums in an acceptable time. The impact of demand uncertainty on the solution is studied by a computational discussion on scenario generation.     

Earliness/tardiness production planning approaches with due-window for manufacturing systems

Although the earliness/tardiness production planning approaches for manufacturing systems with due-date have appeared in the literature, in practice, customers prefer a time duration rather than an exact due-date. This kind of due-date is called due-window. This paper focuses on the production planning problems to minimize the total earliness and tardiness penalties with a due-window subject to the manufacturing resource constraints. Two models, one for mass manufacture and another for one-of-a-kind product (OKP) manufacture, are discussed separately. By means of mathematical deduction, the model for mass manufacture is translated into a linear programming problem and solved by a simplex method. In the case of OKP manufacture, the problem is reduced to a linear 0–1 programming model, using the elaborate definition of variables. The computational results show that both algorithms achieve the optimal production planning and are applicable to practical manufacturing systems.     

Maximum expert consensus models with linear cost function and aggregation operators

In group decision making problems, consensus is a very important issue for the aggregation of individual opinions. Based on the concept of maximum expert consensus model (MECM), this paper incorporates aggregation operators into the MECM, and proposes a novel framework of MECM. When the aggregation operator is set to be the weighted averaging operator or the ordered weighed averaging (OWA) operator, this paper equivalently transforms the MECM into mixed 0–1 linear programming problems. Additionally, this paper also shows that the minimum cost consensus model under the OWA operator with any weights can be similarly transformed into a mixed 0–1 linear programming problem. Numerical examples and a comparison analysis are used to demonstrate the validity of the proposed model.     

A fuzzy linear programming model for production planning in coal mines

This article shows how fuzzy linear programming may be used to solve production scheduling problem in coal industry. First, a fuzzy linear programming model is presented. The proposed model is then tested on a hypothetical problem developed by using production cost estimates from independent coal mines in the states of Virginia, Illinois and Pennsylvania. The results of the model indicate that the model has potential for solving production scheduling problems in the coal industry.     

Dual Estimates of the Optimal Plan Model and Regional Market Costs: A Relationship

The relationship between linear programming dual estimates for the optimal production plan model and real regional market costs is studied. A two-stage linear programming model is necessary for exact approximation of cost allocation in analyzing with optimal plan estimates. A sign criterion is formulated for analyzing the reliability of the production planning model based on a comparison of the changes in the regional market costs and optimal plan estimates. An example is given to illustrate the analysis of reliability of the solution.     

最优递阶随机生产计划与控制

研究了敏捷制造车间(AMW)中的最优递阶随机生产计划与控制问题.首先根据实际 需要建立关联方程有延迟的车间生产的随机非线性规划模型,即一种求解动态优化问题的静态 优化模型.为求解方便将其转化成确定非线性规划模型并通过引进约束进一步转化成线性规划 模型.然后,提出分别用卡马卡算法和基于卡马卡算法的关联预测法进行求解,并编制了相应软 件.算例研究表明所提方法是非常有效的.     

求解SAT问题的线性半定规划算法

将线性半定规划应用到SAT问题的求解过程中。首先将SAT实例转化为整数规划问题,然后松弛为线性规划模型,最后再转化为一般的线性半定规划模型去求解。用SDPA-M软件求解线性半定规划问题后,规定了如何根据目标函数值去判定SAT实例和当CNF公式可满足时如何根据最优指派的概率X^＊i（i=1,…,n）去进行变元赋值,以期求得该公式的可满足指派。上述算法不仅可以判定SAT问题,而且对于符合算法规定可满足的CNF公式皆可给出一个可满足指派。求解SAT问题的线性半定规划算法在文章中被描述并被给予相应算例。