线性规划模型的计算机求解

罗 平

（兴义民族师范学院， 贵州 兴义 562400）

线性规划模型的计算机求解

罗 平

（兴义民族师范学院， 贵州 兴义 562400）

线性规划是运筹学的一个重要分支，在经济、管理等领域有着非常广泛的应用，通过对某一特定的线性规划问题，建立线性规划模型并分别用Lingdo、Mathematical、Matlab软件及office软件中的Excel进行求解，并对四种软件进行对比分析，发现Lingdo、Mathematical、Matlab软件是专业化的软件，需要具备一定的数学基础，Excel软件是大众化的软件，更便于一般人掌握。

线性规划；模型；计算机

线性规划是运筹学的重要分支，它是一门实用性很强的应用数学学科，这门学科产生于20世纪30年代。1939年，前苏联数学家康拓洛维奇在《生产组织与计划中的数学方法》一书中，最早提出和研究了线性规划问题。1947年美国数学家丹泽格提出了一般的线性规划模型和求解线性规划的通用方法—单纯形法，为这门学科奠定了基础[1]。50年代后人们对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于计算机科学与计算机技术的发展，使一些复杂的大型运筹学模型的求解成为可能，极大的推动了运筹学的发展。

运用单纯形法虽然可以给出一般线性规划的最优解，也可以给出某些参数的灵敏度分析，但是决策变量较多时，计算量会非常大。因此借助计算机软件，众多的约束条件和决策变量的线性规划问题的求解也能很快解出来。

本文我们将对某一类线性规划问题，分别用Lingdo、Mathematical、matlab 及 Excel软件来求解。

一、线性规划模型的建立

1.线性规划问题的提出

例[2]：某日化厂生产洗衣粉和洗涤剂。生产原料由市场供应：每千克5元，供应量无限制.该厂加工1kg原料可产出0.5kg普通洗衣粉和0.3kg普通洗涤剂.工厂还可以对普通洗衣粉级普通洗涤剂进行精加工.加工1kg普通洗衣粉可得到0.5kg浓缩洗衣粉,加工1kg普通洗涤剂可产出0.25kg高级洗涤剂,加工示意图见图一.市场售价为每千克普通洗衣粉为8元;每千克浓缩洗衣粉为24元;每千克普通洗涤剂为12元;每千克高级洗涤剂为55元.每加工1kg原料的加工成本为1元，每千克精加工产品的加工成本为3元，工厂设备每天最多可处理4t原料,而对精加工没有限制.若市场对产品也没有限制,问该厂如何安排生产能使每日利润最大？

设每日生产普通洗衣粉的产量为x1kg,生产浓缩洗衣粉的产量为x2kg,生产普通洗涤剂的产量为x3kg,生产高级洗涤剂的产量为x4kg,每日加工原料为x5kg.该问题的数学模型如为：

二、线性规划模型的求解

1.Lindo软件求解

Lindo是美国Lindo系统公司开发的一套专门用于求解最优化问题的软件包。由于Lindo执行速度很快、易于方便输入、求解和分析数学规划问题。因此在数学、科研和工业界得到广泛应用。常用于求解线性规划、整数规划、二次规划问题。按照Lindo格式要求输入：

点击solve求解得：x1=0,x2=1000,x3=0,x4=300,x5=4000,利润z=12600元.

2.Mathematical软件求解[3]

函数LinearProgramming[c,m]用来求解如下形式的线性规划问题.

从上面的形式可以看出,如果参数只写出[c,m,b]的形式，那么只能求解约束条件是的≥模型.对于一般模型，将函数中参数b改写成{bi,si}，即LinearProgramming[c,m,{bi,si}]的形式,就可以求解.LinearProgramming[c,m,{bi,si}]形式的意思是当si=1 时，表示 mx≥bi；当 si=0 时，表示 mx=bi；当 si=-1时，表示mx≤bi.

因此，对于建立的模型，在平台中输入函数后，按：组合键“shift+回车”得出结果如下：结果表示x1=0,x2=1000,x3=0,x4=300,x5=4000.

3.Matlab软件求解

在Matlab中函数linprog（）是求解线性规划问题的函数，Matlab中以求极小为标准。函数linprog的具体格式为：

其中X是解向量，c是目标函数的系数构成的向量，A是系数矩阵，b是右端向量。Aeq和Beq表示线性规划中等式的系数矩阵和右端向量。LB和UB是约束变量的下界和上界向量，X0是给定的变量的初始值，Opertions为控制规划的参数系列。

在matlab7.0中编程计算如下：

运行后结果为：x=（0，1000，0，300，4000）T.表明普通洗衣粉不生产,生产浓缩洗衣粉的1000kg,普通洗涤剂不生产,生产高级洗涤剂300kg,每日加工原料为4000kg.

4.EXCEL求解

Excel能对不同形式的线性规划问题求解。对本例而言，可以用表1表示成计算机能够识别的形式。

表1

输入公式：G3=SUMPRODUCT（B3:F3,B10:F10）

G4=SUMPRODUCT（B4:F4,B10:F10）

G5=SUMPRODUCT（B5:F5,B10:F10）

G6=SUMPRODUCT（B6:F6,B10:F10）

SUMPRODUCT表示对应的乘积之和。

选择工具菜单栏中的规划求解，在弹出的对话框中，完成以下设置：

（1）定一个目标单元格，它包含计算目标函数值的公式（本例中为G3）。

（2）对目标单元格选择求最大还是最小。

（3）确定变量所在的单元格。

（4）确定约束条件

参数设置完之后，点击求解按钮，求出最优解为

x1 x2 x3 x4 x5目标函数系数约束条件系数总计 限制8 21 12 52 -6 12600-1-2000.50＝0 00-1-40.30＝0 0 0 0 0 14000＜4000输出：解决方案x1 x2 x3 x4 x5 z 0 1000 0 300 4000

三、结论

通过以上四种软件求解，我们发现计算结果都是相同的，普通洗衣粉不生产,生产浓缩洗衣粉的1000kg,普通洗涤剂不生产,生产高级洗涤剂300kg,每日加工原料为4000kg.获得最大利润为12600元。对比四种软件，Lindo求解只需要按格式要求直接输入模型就可以求解出结果；Mathematical软件和Matlab软件共同点是调用函数命令求解，按照函数格式要求输入向量求解，但是对比计算发现Mathematical的线性规划函数格式要求比Matlab软件简单；Excel求解是在工作簿中来进行，把模型转化为计算机能识别的形式，点击工具菜单栏中的规划求解即可。Lindo、Mathematical、Exce不仅可以求最优解，还可以求目标函数值，Mathematical软件只能求最优解。Lindo、Mathematical、Matlab软件是专业的数学软件，必须具备一定的数学基础，Excel是常用的办公软件,操作也是很简单的，易于一般工作人员掌握。

总之，运用计算机求解运筹学线性规划模型，简单、高效、实用。伴随着社会和计算机技术的发展，运用计算机求解运筹学线性规划模型将逐步取代繁琐的手工计算，成为管理者实施现代化管理的重要手段。

[1]胡运权.运筹学基础及应用(第六版)[M].高等教育出版社,2014.

[2]何坚勇.运筹学基础[M].清华大学出版社,2008.

[3]郭志军.线性规划模型的建立及Mathematica求解[J].长沙大学学报，2010（5）.

The Computer Solving in Linear Programming Model

LUO Ping
（Xingyi Normal University for Nationalities,Xingyi,Guizhou,562400,China）

Linear programming which has a very wide range of applications in the economic and management, is an important branch of operational research. In accordance with a given linear programming problem, linear programming model is set up .We will solve the model respectively by Lindo, Mathematical, Matlab, software and office software of Excel. It reflects the diversity of computer solving method of linear programming computer

linear programming；model；computer

1009—0673（2015）01—0121—04

C931.1

A

2014—12—22

罗平（1983— ），女，云南昆明人，兴义民族师范学院数学科学学院讲师，硕士研究生，主要从事运筹学教学和研究。

责任编辑：彭光明