线性规划问题计算机求解方法研究.doc

线性规划问题计算机求解方法研究.doc线性规划问题计算机求解方法研究
摘要：单纯形法是求解线性规划问题的一般方法，然而手工采用单 纯形法求解线性规划问题时，计算量大、复杂、容易出错。借助计算机求 解可以大大减轻计算者的工作量，并且快速准确地得到线性规划问题的 解。研究了线性规划问题的计算机求解方法，分别给出了 Matlab、Lingo、 Excel求解线性规划问题的方法。
关键词：线性规划问题；计算机求解；Mat lab； Lingo； Excel
中图分类号：TP301文献标识码：A文章编号：16727800 (2012) 009002502
0引言
线性规划问题是运筹学的一个重要的分支。对于有两个决策变量的线 性规划问题，可采用图解法进行求解，较为简单。当决策变量为3个及以 上，手工求解线性规划问题时，需要采用单纯形法。
下面给出某线性规划问题方程：
该线性规划问题若采用单纯形法手工求解，计算量大且容易出错。随 着计算机技术快速发展及普遍使用，采用计算机来求解线性规划问题，可 以大大减少计算量，快速准确地得到问题的解。本文以该线性规划问题为 例，分别给出Matalab、Lingo、Excel求解线性规划问题的方法。
2线性规划问题的MATALAB求解
线性规划问题的数学描述为:
记号s. to的缩写，表示满足后面的关系。约束条 件还可以进一步细化为等式约束Aeq=Beq,线性不等式约束AXWB, x变量 的上界向量xmax和下界xmin,使得xminWxWxmax。
在Mat lab最优化工具箱中提供了求解线性规划问题的L inprog函数, 该函数的调用格式为：
3用LIND0/LING0求线性规划问题
Lindo和Lingo是美国Lindo系统公司开发的一套专门用于求解最优 化问题的软件包。Lindo (Linear Interactive and Discrete Optimizer), 即交互式的线性和离散优化求解器。主要用于解线性规划、二次规划。 Lingo (Linear Interactive and General Optimizer)即"交互式的线 性和通用优化求解器”，可以用于求解线性规划、整数规划(包括0T整 数规划)。Lingo除了具有Lindo的全部功能外，还可以用于求解非线性规 划，它不仅方便灵活，而且执行速度非常快。
一般使用Lingo求解运筹学问题可以按照以下两个步骤来完成：①根 据实际问题建立数学模型；②根据该数学模型，利用Lingo来求解模型。 根据Lingo软件，将数学模型转译为计算机语言，借助计算机来进行求解。
首先，应用Lingo来求解式(1)所示的线性规划模型，只需要在Lingo 窗口中输入以下信息即可：
然后，按运行按钮，得到模型最优解，X= (0, 1, 0, 5) T, maxz=17o
在利用Lingo求解线性规划时，如自变量都为非负的话，在Lingo中 输入的信息和模型基本相同；如自变量为自由变量，可以使用函数©free
来把系统默认的非负变量定义为自由变量。
4用EXCEL求线性规划问题
利用单纯形法手工计算线性规划问题是很麻烦的。可以利用Office 软件中的Excel工作表来求解线性规划问题。用Excel工作表求解线性规 划问题，首先需要设计一个工作