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

点赞:8423 浏览:33454 近期更新时间:2024-01-08 作者:网友分享原创网站原创

摘 要:单纯形法是求解线性规划问题的一般方法,然而手工采用单纯形法求解线性规划问题时,计算量大、复杂、容易出错.借助计算机求解可以大大减轻计算者的工作量,并且快速准确地得到线性规划问题的解.研究了线性规划问题的计算机求解方法,分别给出了Matlab、Lingo、Excel求解线性规划问题的方法.

关 键 词:线性规划问题;计算机求解;Matlab;Lingo;Excel

中图分类号:TP301文献标识码:A文章编号:16727800(2012)009002502

0引言

线性规划问题是运筹学的一个重要的分支.对于有两个决策变量的线性规划问题,可采用图解法进行求解,较为简单.当决策变量为3个及以上,手工求解线性规划问题时,需要采用单纯形法.

下面给出某线性规划问题方程:

该线性规划问题若采用单纯形法手工求解,计算量大且容易出错.随着计算机技术快速发展及普遍使用,采用计算机来求解线性规划问题,可以大大减少计算量,快速准确地得到问题的解.本文以该线性规划问题为例,分别给出Matalab、Lingo、Excel求解线性规划问题的方法.

2线性规划问题的MATALAB求解

线性规划问题的数学描述为:

记号s.t.是英文subjectto的缩写,表示满足后面的关系.约束条件还可以进一步细化为等式约束Aeq等于Beq,线性不等式约束AX≤B,x变量的上界向量xmax和下界xmin,使得xmin≤x≤xmax.

在Matlab最优化工具箱中提供了求解线性规划问题的Linprog函数,该函数的调用格式为:

3用LINDO/LINGO求线性规划问题

Lindo和Lingo是美国Lindo系统公司开发的一套专门用于求解最优化问题的软件包.Lindo(LinearInteractiveandDiscreteOptimizer),即交互式的线性和离散优化求解器.主要用于解线性规划、二次规划.Lingo(LinearInteractiveandGeneralOptimizer)即“交互式的线性和通用优化求解器”,可以用于求解线性规划、整数规划(包括0-1整数规划).Lingo除了具有Lindo的全部功能外,还可以用于求解非线性规划,它不仅方便灵活,而且执行速度非常快.

一般使用Lingo求解运筹学问题可以按照以下两个步骤来完成:①根据实际问题建立数学模型;②根据该数学模型,利用Lingo来求解模型.根据Lingo软件,将数学模型转译为计算机语言,借助计算机来进行求解.

首先,应用Lingo来求解式(1)所示的线性规划模型,只需要在Lingo窗口中输入以下信息即可:

然后,按运行按钮,得到模型最优解,X等于(0,1,0,5)T,maxz等于17.

在利用Lingo求解线性规划时,如自变量都为非负的话,在Lingo中输入的信息和模型基本相同;如自变量为自由变量,可以使用函数@free来把系统默认的非负变量定义为自由变量.

4用EXCEL求线性规划问题

利用单纯形法手工计算线性规划问题是很麻烦的.可以利用Office软件中的Excel工作表来求解线性规划问题.用Excel工作表求解线性规划问题,首先需要设计一个工作表,然后将线性规划问题中的有关数据填入该表中.可按下列步骤来设计所需的工作:

(1)确定目标函数系数存放单元格,并将目标函数系数输入到这些单元格中.

(2)确定决策变量存放单元格,并任意输入一组数据(决策变量输入为4个1).

(3)确定约束条件中左端项系数(ZDX)存放单元格,并输入ZDX.

(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\-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)弹出“规划求解参数”对话框,在其中输入参数.置目标单元格文本框中输入目标单元格;“等于”框架中选中“最大值/最小值”单选按钮.

(3)设置可变单元格区域,按Ctrl键,用鼠标进行选取,或在每选一个连续区域后,在其后输入逗号“,”.

(4)单击“约束”框架中的“添加”按钮.

(5)在弹出的“添加约束”对话框中输入约束条件.

(6)单击“添加”按钮、完成一个约束条件的添加.重复步骤(5),直到添加完所有条件.

(7)单击“确定”按钮,返回到“规划求解参数”对话框,完成条件输入的“规划求解参数”对话框.

(8)点击“求解器参数”窗口右边的“选项”按钮.确信选择了“采用线性模型”旁边的选择框.如果变量全部非负,而“检测定变量非负”旁边的选择框没有被选择,那么请选择后点击“确定”.

(9)单击“求解”按钮,弹出“规划求解结果”对话柜,同时求解结果显示在工作表中.

(10)若结果符合要求,单击“确定”按钮,完成操作;若结果不符要求,单击“取消”按钮,在工作表中修改单元格初值后重新运行规划求解过程.

从计算结果可以看出,最优解为:X等于(0,1,0,5)T,maxz等于17.这与MATALAB和在LINGO中计算的值是一致的.

5结语

本文研究了线性规划问题的计算机求解方法,对同一个线性规划问题,用Matalab、Lingo以及在Excel分别对其进行求解.实验表明,3种方法求解的结果是一致的、正确的.通常简单的线性规划问题可以用Excel求解,复杂的问题用Matalab,Lingo求解.

针对线性规划问题,还有其它计算机求解方法,如可以编写C语言程序来实现计算,或采用提供线性规划问题求解功能的计算机软件求解,如WinQSB、SPSS、LstOpt等.

线性规划问题计算机求解方法参考属性评定
有关论文范文主题研究: 关于计算机的论文范文 大学生适用: 专升本毕业论文、高校毕业论文
相关参考文献下载数量: 97 写作解决问题: 如何写
毕业论文开题报告: 标准论文格式、论文目录 职称论文适用: 核心期刊、中级职称
所属大学生专业类别: 如何写 论文题目推荐度: 免费选题