MATLAB在运筹学中的应用

张建勇 于恺 李友朋 张翠艳

摘    要： 本文根据运筹学的学科特点及在教学中存在的不足，提出了在教学实践中引入Matlab作为教学辅助手段，主要阐述MATLAB在线性规划、目标规划、二次规划中的应用，实例验证了Matlab在求解运筹学问题时的高效性和准确性。

关键词： MATLAB    运筹学    线性规划    目标规划    二次规划

一、引言

运筹学是利用现代数学研究各种广义资源的运用、筹划与相关决策等问题的一门新兴学科。该课程的主要特点是运用量化的分析方法，对有限的资源进行统筹安排，其研究成果为决策者提供科学依据。由于很多问题来源于实际的生产和管理活动，因此在建立数学模型时往往会涉及很多变量和约束条件，使得所建立的模型较复杂。如何求解这类模型成为解决问题的关键。

在运筹学的教学中，尽管目前的教学改革使得教学手段丰富多样，但这些教学手段只是将教材内容搬运到多媒体课件上。加之多媒体的教学节奏较快，使得原本生动的教学内容，只侧重于理论分析和公式推导，忽略计算过程和结果，导致课堂教学效果差。手工推演和计算运筹学中实例的可行性太低，成熟的商业软件能够为运筹学教学提供较好的辅助作用。

目前最好的方法是借助于计算机和商业软件进行求解，常见的软件主要有LINGO、LINDO和MATLAB等[1]。LINGO是美国LINDO系统公司研发的，常用于求解线性规划及一些简单的非线性规划问题。该软件在处理复杂的非线性规划问题时存在一定的局限性。1984年美国MathWorks公司开发的MATLAB软件，已经发展成国际上应用最广泛的科学与工程计算软件之一。其中包含与运筹学紧密相关的优化工具箱，该工具箱的基本功能有：求解线性规划、非线性规划、动态规划、目标规划及多目标规划等问题，在求解各类优化问题时都有着无可替代的优势[2]。

本文通过线性规划、二次规划和目标规划三个方面，结合具体实例，说明MATLAB在求解运筹学问题时的易操作性与直观性。

二、MATLAB在线性规划方面的应用

线性规划是最优化中的一个分支，是最优化理论的基础性内容。有关线性规划问题的建模、求解和应用性研究，构成了运筹学中线性规划[3]分支。在MATLAB的优化工具箱中，线性规划问题必须表示为如下[4]：

对于一般的线性规划问题，可以根据线性规划的标准化方法，将其转换为模型（1）的形式。求解模型（1）的MATLAB命令函数为linprog（），完整的调用格式形式为：

[x，fval，exitflag，output，lambda]=linprog（f，A，b，Aeq，beq，lb，ub，x0，options）

其中，f为目标函数中系数向量的转置，是一维行向量，A、b满足不等式Ax≤b，若没有不等式约束，则A=[]，b=[];Aeq、beq满足等式约束Aeq=beq，若没有，则取Aeq=[]，beq=[];lb、ub满足，若无界，可令lb=[]，ub=[];x0为初始值;options为包含算法控制参数的结构变量，可以通过optimset命令对这些具体的控制参数进行设置。

输出参数x为线性规划问题的最优解，fval为线性规划问题在最优解x处的函数值，exitflag返回的是优化函数计算终止时的状态指示，说明算法终止的原因，当其值为1时说明已经收敛到x，当x取其他值时，其物理意义如表1。

表1    Exitflag的反馈值与对应的物理意义

output输出优化信息，lambda为lagrange乘子，它体现某个约束的有效性。在使用linprog（）命令时，必须严格遵循它的调用格式（1）。比如下面的线性规划问题：

max z=x■+x■s.t.    x■-2x■≤4         x■+2x■≤8         x■，x■≥0

程序如下：

clc;clear;

f=[-1;-1]; %目标函数，为转化为极小，故取目标函数中设计变量的相反数

A=[1  -2;1  2];%线性不等式约束

b=[4;8];

lb=[0;0];

ub=[Inf;Inf];%边界约束，由于无上界，故设置ub=[Inf;Inf]

[x，fval]=linprog（f，A，b，[]，[]，lb，ub）%x为最优解，fval为最优值

运算结果如下：

Optimization terminated.

x=[6.0000，1.0000]

fval=-7.0000

由结果可知，当x=6，x=1时，目标函数取得最优解7。

三、MATLAB在二次规划中的应用

二次型规划问题是一种简单的有约束非线性规划问题，它已成为运筹学、经济数学及组合优化科学的基本方法。非线性规划问题在计算上是困难的，理论上也不像线性规划那样有简洁的结果和成熟的理论。通常情况下，采用迭代的思想计算非线性规划问题，即从一个满足约束条件的初始可行点出发，按照一定的搜索机制，找到下一个使目标函数更优的可行解，直到找到最优解其目标。在Matlab中，二次规划函数是x的二次型形式，约束条件仍为线性的。一般的二次规划问题的数学表示为[4]：

与线性规划相比，二次型规划多出一项XHX描述x和xx项。在MATLAB工具箱中，求解二次型规划的是命令函数是quadprog（）。函数调用形式如下所示：

[x，fval，exitflag，output，lambda]=quadprog（H，f，A，b，Aeq，beq，lb，ub，x0，options）

其输入参数H为对角矩阵，表示x和xx项前面的系数，其他参数的输入格式与linprog（）完全相同，见表1。

例如求解下列二次型规划问题

程序如下：

clc，clear;

H=diag（[10 8 6 4 2]）;

f=[-2，-1，-2，-5，-10];

A=[1，1，1，1，1;-5，4，-3，2，-1;1，1，0，0，-1;0，0，0，1，1;0，0，-1，0，0;0，0，0，-1，0];

b=[20;-5;8;10;-5;-3];

[x，fval，exitflag]=quadprog（H，f，A，b）

运算结果如下：

Optimization terminated.

x=[0.2000   0.1250   5.0000   3.0000   5.0000]

fval=42.7375

exitflag=1

所以当x=0.2，x=0.125，x=5，x=3，x=5时，目标函数取得最小值42.7375。exitflag=1说明函数取得最优解。

四、MATLAB在目标规划中的应用

目标规划在处理实际决策问题时，承认各项决策要求的存在有其合理性，即在最终决策时，不强调其绝对意义上的最优性，在一定程度上弥补了线性规划存在的某些缺陷。因此，在运筹学中所有的规划问题中，与实际联系最大的当属目标规划。MATLAB所定义的目标函数的标准形式为

γs.t.   f（x）-weight·γ≤goal        c（x）≤0        ceq（x）=0        Ax≤b        Aeqx=beq        lb≤x≤ub

其中x、weight、goal、b、beq、lb、ub为相应维数的向量，A、Aeq为矩阵，c（x）、ceq（x）、f（x）为返回向量的函数，它们可以是线性函数，也可以是非线性函数。

在MATLAB的库函数中，针对目标规划的命令函数名为fgoalattain（），调用形式为：

[x，fval，attainfactor，exitflag，output，lambda]=fgoalattain（fun，x0，goal，weight，A，b，Aeq，beq，lb，ub，nonlcon，options）

其中在输入参数中，fun为目标函数，x■是求解的初始值，goal是目标函数的期望值，weight是目标权重，nonlcon是非线性约束函数。输出参数中，attainfactor参数包含解处的γ值，γ取负值时表示结果溢出。

例如，某化工厂拟生产两种新产品A和B，其生产设备费用分别为：2万元/t和5万元/t。这两种产品均造成环境污染，假设由公害所造成的损失可折算为4万元/t和1万元/t。由于条件限制，该厂的两种产品的最大生产能力分别为每月5t和6t，而市场需要这两种产品的总量每月不少于7t。试问工厂如何安排生产计划，在满足市场需要的前提下，使设备投资和公害损失均达到最小？

该工厂决策认为，这两个目标中环境污染应优先考虑，设备投资的目标值20万元，公害损失的目标为12万元。

相应的MATLAB程序如下：

clc，clear;

A=[1，0;0，1;-1;-1];

b=[5;6;7];

x0=[0，0];

goal=[20，12];%设置期望目标值

weight=abs（goal）;%设置目标权重

[x，fval，attainfactor]=fgoalattain（@funa，x0，goal，weight，A，b）

function f=funa（x）

f（1）=2*x（1）+5*x（2）;

f（2）=4*x（1）+x（2）;

运算结果如下：

x=[2.9167    4.0833]

fval=26.2500   15.7500

attainfactor=0.3125

由结果可知，每月生产A产品3t，B产品4t时，设备投资费用和公害损失与目标最为接近，设备投资费用为26.25万元，公害损失为15.75万元。Attaintfactor>0说明γ值未溢出，结果可信。

五、结语

以上实例说明，利用MATLAB可以方便地求出线性规划等优化问题的解，不仅算法简单，避免了手工的繁琐计算，而且可以大大提高计算速度和计算的准确性。将MATLAB软件用于运筹学教学，可以更直观地理解运筹学中的基本概念理论，并可培养动手和科研实践能力。

同时，运筹学还包含其他内容，如动态规划、整数规划、非线性规划等内容，在Matlab中，也有与之对应的命令或工具箱，学习者可以结合网络资源或者Matlab中的help命令进行学习。

参考文献：

[1]王立欣，王爱维，赵美.运筹学常用软件综述[J].科技情报开发与经济，2009，26：95-96.

[2]张明，王文文.Matlab在经管类运筹学教学中的探索与实践[J].大学教育，2012，07：81-82.

[3]胡运权.运筹学教程（第三版）[M].北京：清华大学出版社，2007.

[4]杨云峰，胡金燕，宋国亮.数学建模与数学软件[M].哈尔滨：哈尔滨工程大学出版社，2012.

[5]马莉.MATLAB数学实验与建模[M].北京：清华大学出版社，2010.