线性规划问题计算机求解方法探究

《线性规划问题计算机求解方法探究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、线性规划问题计算机求解方法探究　　摘要：单纯形法是求解线性规划问题的一般方法，然而手工采用单纯形法求解线性规划问题时，计算量大、复杂、容易出错。借助计算机求解可以大大减轻计算者的工作量，并且快速准确地得到线性规划问题的解。研究了线性规划问题的计算机求解方法，分别给出了Matlab、Lingo、Excel求解线性规划问题的方法。关键词：线性规划问题；计算机求解；Matlab；Lingo；Excel中图分类号：TP301文献标识码：A文章编号：16727800（2012）0090025020引言线性规划问题是运筹学的一个重要的分支。对于有两个决策变量的线性规划

2、问题，可采用图解法进行求解，较为简单。当决策变量为3个及以上，手工求解线性规划问题时，需要采用单纯形法。下面给出某线性规划问题方程：6该线性规划问题若采用单纯形法手工求解，计算量大且容易出错。随着计算机技术快速发展及普遍使用，采用计算机来求解线性规划问题，可以大大减少计算量，快速准确地得到问题的解。本文以该线性规划问题为例，分别给出Matalab、Lingo、Excel求解线性规划问题的方法。2线性规划问题的MATALAB求解线性规划问题的数学描述为：记号s.t.是英文subjectto的缩写，表示满足后面的关系。约束条件还可以进一步细化为等式约束Aeq=

3、Beq，线性不等式约束AX≤B，x变量的上界向量xmax和下界xmin，使得xmin≤x≤xmax。在Matlab最优化工具箱中提供了求解线性规划问题的Linprog函数，该函数的调用格式为：3用LINDO/LINGO求线性规划问题Lindo和Lingo是美国Lindo系统公司开发的一套专门用于求解最优化问题的软件包。Lindo（LinearInteractiveandDiscreteOptimizer），即交互式的线性和离散优化求解器。主要用于解线性规划、二次规划。Lingo（LinearInteractiveandGeneralOptimizer）即“

4、交互式的线性和通用优化求解器”，可以用于求解线性规划、整数规划（包括0-1整数规划）。Lingo除了具有Lindo的全部功能外，还可以用于求解非线性规划，它不仅方便灵活，而且执行速度非常快。6一般使用Lingo求解运筹学问题可以按照以下两个步骤来完成：①根据实际问题建立数学模型；②根据该数学模型，利用Lingo来求解模型。根据Lingo软件，将数学模型转译为计算机语言，借助计算机来进行求解。首先，应用Lingo来求解式（1）所示的线性规划模型，只需要在Lingo窗口中输入以下信息即可：然后，按运行按钮，得到模型最优解，X=（0，1，0，5）T，maxz=1

5、7。在利用Lingo求解线性规划时，如自变量都为非负的话，在Lingo中输入的信息和模型基本相同；如自变量为自由变量，可以使用函数@free来把系统默认的非负变量定义为自由变量。4用EXCEL求线性规划问题利用单纯形法手工计算线性规划问题是很麻烦的。可以利用Office软件中的Excel工作表来求解线性规划问题。用Excel工作表求解线性规划问题，首先需要设计一个工作表，然后将线性规划问题中的有关数据填入该表中。可按下列步骤来设计所需的工作：（1）确定目标函数系数存放单元格，并将目标函数系数输入到这些单元格中。（2）确定决策变量存放单元格，并任意输入一组数

6、据（决策变量输入为4个1）。（3）确定约束条件中左端项系数（ZDX）存放单元格，并输入ZDX。6（4）在约束条件左端项系数（ZDX）存放单元格右边的单元格中输入约束条件左端项的计算公式，计算出约束条件左端项对应于目前决策变量的函数值。（5）在步骤（4）的数据右边输入约束条件中右端项（即常数项，用B表示）。（6）确定目标函数值存放单元格，在该单元格中输入目标函数值的计算公式。如式（1）所示的线性规划问题，按照上述步骤建立线性规划问题的Excel表。Excel表中：F＼-4=B＼-4*B＼-2+C＼-4*C＼-2+D＼-4*D＼-2+E＼-4*E＼-2；F＼-

7、5=B＼-5*B＼-2+C＼-5*C＼-2+D＼-5*D＼-2+E＼-5*E＼-2；F＼-6=B＼-6*B＼-2+C＼-6*C＼-2+D＼-6*D＼-2+E＼-6*E＼-2；C＼-7=B＼-2*B＼-1+C＼-2*C＼-1+D＼-2*D＼-1+E＼-2*E＼-1。建立了Excel工作表后，就可以利用其中的规划求解功能求解相应的线性规划问题了。求解步骤如下：（1）单击“工具”菜单中的“规划求解”命令。如果没有“规划求解”命令，可通过“加载宏”来添加规划求解功能。（2）弹出“规划求解参数”对话框，在其中输入参数。置目标单元格文本框中输入目标单元格；“等于”框架

8、中选中“最大值/最小值”单选按钮。6（3）设置可变单元格区域，按C