浅谈MATLAB在线性规划教学中的应用

贺明凤 张艳玲

【摘要】线性规划是运筹学中研究较早、发展较快、应用较广泛、方法较成熟的一个重要分支，它已成为现代管理科学研究的重要工具之一，其应用范围涉及经营规划制定、生产任务安排、投资决策、生产计划和库存控制等多方面。本文讨论了在企业的各项管理活动各种限制条件的组合选择出最合理的一般计算方法，重点探讨线性规划问题的MATLAB程序设计和实现过程，充分体现MATLAB在管理运筹学教学辅助中的优越性。

【关键词】线性规划 管理活动 MATLAB实现

【中图分类号】O221.1 【文献标识码】A 【文章编号】2095-3089（2018）11-0010-02

线性规划主要用于解决生产、生活中的人力资源规划、投资计划、生产配料、库存控制、资源利用等问题，它是辅助人们进行科学管理的一种重要的数学模型，研究线性约束条件下线性目标函数的极值问题的数学方法。在教学中，简单的线性规划指的是二维变量的线性规划模型，主要讲解用“图解法”或者“枚举法”求最优解；当自变量个数n和约束条件个数m较大时，教学侧重讲解用单纯形法求最优解。

方法一、线性规划的图解法：

Step 1：确定可行解空间。

Step 2：从可行解空间所有的可行点中确定最优解。

【例1】哈哈农商使用大豆和玉米部分提取物配制两种特殊饲料A和B，其中，配制每公斤特殊饲料A需使用6公斤大豆和1公斤玉米，配制每公斤特殊饲料B需使用4公斤大豆和2公斤玉米，而大豆和玉米的日最大可用量分别为2400和600公斤。一项市场调查表明，特殊饲料B的日需求量不超过A的日需求量。假设A、B两种饲料的利润分别为50和40元/公斤，哈哈农商打算确定最优的饲料A、B的产品混合，如何能使得日总利润达到最大？

本问题的MATLAB程序为：c=[-50， -40]； A=[6， 4； 1， 2； 1， -1]； b=[2400； 600； 0]；

lb=zeros（2， 1）； [x， fval， exitflag]=linprog（c， A， b， [ ]， [ ]， lb）

方法二、线性规划的单纯形法

【例2】若上述哈哈农商的特殊饲料生产中，使用大豆、玉米和麦麸三种原料部分提取物配制三种特殊饲料A、B和C，其中，配制每公斤特殊饲料A需使用大豆、玉米和麦麸分别为3.5、2、1.5公斤，配制每公斤饲料B需使用大豆、玉米和麦麸分别为1.5、1.2、1.5公斤，配制每公斤新饲料C需使用大豆、玉米和麦麸分别为4.5、1、1公斤，而大豆、玉米和麦麸的日最大可用量分别为1500、750和750公斤。饲料B的日需求量不超过A的日需求量。假设此时A、B、C三种饲料的利润分别为50、40和80元/公斤，哈哈农商如何确定最优的饲料产品混合，使得日总利润达到最大？

用单纯形法求解例线性规划问题的MATLAB实现步骤：

Step 1：自定义实现单纯形表的MATLAB函数：Simplex_

Tableau。

Step 2：将线性规划模型标准化，构造初始单纯形表。

Step 3：调用自定义函数Simplex_Tableau，求解优化问题[3]。

（1）定义函数Simplex_Tableau

function Simplex_Tableau（mat，numFreeVar）

format short

maxRow=length（mat（：，1））； maxCol=length（mat（1，：））； objEntryExcludingMaxPayOff=mat（maxRow，1：maxCol？鄄2）；

[objEnt bestColToPivot]=min（objEntryExcludingMaxPay

Off）；

while（objEnt<0）

lastColExcludingObjEntry=mat（1：（max

Row？鄄1），maxCol）；ithColExcludingObjEntry=mat（1：（maxRow？鄄1），bestColToPivot）；

for i=1：maxRow？鄄1

if （lastColExcludingObjEntry（i，1）==0&ithColExcludingObj;

Entry（i，1）<=0）

lastColExcludingObjEntry（i，1）=1；

end

end

a=lastColExcludingObjEntry./ithColExcludingObjEntry； [ val bestRowToPivot]=min（a）；

if（val<0）

[s indices]=sort（a）；

if（max（a）>0）

count=1；

while（s（ount）<0）

count=count+1；

end

bestRowToPivot=indices（count）；

end

end

sprintf（'本次迭代的單纯形表的枢轴列为第%d列，枢轴行为第%d行'，bestColToPivot，bestRowToPivot）

disp（'本次迭代的单纯形表为'）；

[mat，[a；0]] disp（'请按键盘上任意一个键继续操作'）；

pause；

if（length（a）==0）

length（a）

return

end

mat=pivot（mat，bestRowToPivot，bestColToPivot）；

objEntryExcludingMaxPayOff=mat（maxRow，1：maxCol？鄄2）；

[objEnt bestColToPivot]=min（objEntryExcludingMaxPay

Off）；

end

sprintf（'本次迭代的单纯形表的枢轴列为第%d列，枢轴行为第%d行'，bestColToPivot，bestRowToPivot）

disp（'本次迭代的单纯形表为'）；

[mat，[a；0]]

disp（'请按键盘上任意一个键继续操作'）；

function newMat=interChange（mat，row1，row2）

temp=mat（row1，：）； mat（row1，：）=mat（row2，：）；

mat（row2，：）=temp； newMat=mat；

function newMat=multiFromRowToRow（mat，fromRow，toRow，multiplier）

rG=mat（fromRow，：）？鄢multiplier； mat（toRow，：）=rG+mat（toRow，：）； newMat=mat；

function newMat=multMat（mat，row，mult）

mat（row，：）=mat（row，：）？鄢mult； newMat=mat；

function newMat=pivot（mat，row，col）

mat（row，：）=mat（row，：）./mat（row，col）；

for r=1：length（mat（：，1））

if（r～=row）

mat=multiFromRowToRow（mat，row，r，？鄄mat（r，col））；

end

end

newMat=mat；

（2）将【例2】的线性规划模型标准化，构造初始单纯形表

mat=[3.5，1.5，4.5，1，0，0，1500；2，1.2，1，0，1，0，750；1，1.5，1，0，0，1，

750；-50，-40，-80，0，0，0，0]

（3）调用自定义函数Simplex_Tableau，求解【例2】的优化问题，此时在MATLAB的命令窗口command window或编辑器editor中输入：

mat=[3.5，1.5，4.5，1，0，0，1500；2，1.2，1，0，1，0，750；1，1.5，1，0，0，1，

750；-50，-40，-80，0，0，0，0]；numFreeVar=3； Simplex_Tableau（mat， numFreeVar）

其最终的运行结果为：

从运行结果可以看出，例2的线性规划问题的最优解为x3=214，x5=107，x2=357，其他变量为0，此时哈哈农商的利润最大值z=31429元。

事实上，线性规划的图解法和单纯形法的手算步骤较为繁琐，而且手算速度慢，容易出错。能用于求解线性规划优化问题的MATLAB内置函数除linprog外，还有LINDO、LINGO和GLPK软件等。由上述例2的算法实现过程可以看出，线性规划单纯形法的手工计算过程可以在MATLAB编程中得以实现，简化了手工计算的繁琐，提高了计算效率，且自定义的Simplex_Tableau函数可以用于求解所有可以用单纯形法求解的线性规划模型，为学习者进一步应用线性规划模型提供了方便。

参考文献：

[1]Hamdy A.Taha著.刘德纲，朱建明等译.运筹学导论.中国人民大学出版社，2014.

[2]耿修林著.數据、模型与决策，中国人民大学出版社，2013.

[3]吴祁宗，郑志勇、邓伟等编著.运筹学与最优化MATLAB编程.机械工业出版社，2009.

[4]薛长虹，于凯著.MATLAB数学实验.西南交通大学出版社，2014.

[5]雍龙泉. 求解线性规划的几种方法. 江西科学，第25卷第2期，2007年4月：203-205.