Matlab在线性规划中的使用

1.优化问题(w6nti)及其数学模型

假设有一个问题，它有几个因素来决定，当这些因素处于某个状态时，可

以使问题得到我们最想要的结果。优化问题就是寻求(xOnqi①这个状态的过程。

例如:

某工厂(gongchmng)生产A,B两种产品，所用原料均为甲、乙、丙三种(s2

nzhong);生产一件产品所需原料和所获利润以及库存原料情况如下所示：

原料甲原料乙原料丙利润(元)

产品A8447000

产品B68610000

库存构熊在工々型程独库存原料「钟§80单位，眉能300单位)泵料丙220单

位的情况下如何(旧帕)安排A,B两种产品的生产数量可以获得最大的利润？

设生产A中产品件，生产B中产品件，z为所获得的利润，于是有关

系式：

我们称它为目标函数。生产的条件我们可以表示为：

我们把上面的不等式称为约束条件。

产品A的产量x和B的产量*是优化问题的变量。在满足约束条件的前提

12

下使目标函数得到最优的值成为最优解。根据以上定义，也可以说优化运算是

通过某种计算寻求最优解的过程。

以上这个用等式或者不等式来表达我们要解决的问题的过程就是优化问题

的建模过程。我们平时遇到的问题往往不是上面的这几个数学表达式就能表

达得

清清晰楚的，但是建立像上面类似的数学模型却是优化求解的第一步。优化问

题往往表现为在多约束条件下求某一函数的极值问题，例如上面的这个例子。

Matlab有一个优化工具箱，可以匡助我们方便的解决好这种问题。

2优化工具箱

Matlab的优化工具箱有一些对普通非线性函数求解最小化或者最大化(求

极值)的函数组成，此外还包括一些解决诸如线性规划等标准矩阵问题的函数

o所有的优化函数都是用Matlab语言编写的m文件，我们可以通过在命令窗

口里输入typefunction_name来查看这些函数。

优化工具箱的优化功能包括：

(1)求无约束非线性最小化；

(2)求有约束非线性最小化；

(3)二次和线性规划问题；

(4)非线性最小二乘法和曲线拟合问题；

(5)非线性等式的求解；

(6)约束线性最小二乘法；

(7)稀疏和结构化大尺度问题。

工具箱中求非线性函数极小值的命令函数如下表所示：

函数用法

线性规划问题x=linprog(f,A,k))

无限定标量问题x=fminuncf^jx),x为标量

无限定条件矩阵

x=fminunc^r,x),X为矩阵

问题

minf(x)，条件为

有限定条件x=fnd.ncon^f(f1x)

目标条件x=fgoa2attain(4^,x,goal,w),条件为

，汆ItN

最小最大极值x=fminmax^坷,x)

G(X)<0

非线性二次平

x=lsqnonneg(if

方极值

非线性方程x=fsolved

半无穷条件x=fsemimf^ft\n,x)，条件为任意给定v值

上面表中函数(MnshCi)可以对标量、向量和矩阵进行运算；我们普通用大写

字母表示矩阵，用小写字母表示向量和标量。在Matlab中用符号表示矩

阵的元素乘。固然，上述运算是在定义好了一个(yig?最小化函数的前提下进

行的，也就是说要先建立数学模型。

注：Matlab自身提供了一个(yig»优化演示示例，其命令为。ptdemo。

3.线性规划(xi6nxingguThu台)问题

前面6-1中所举的例子就是一个典型的线性规划问题。线性规划数学模型的

特点伯di*n)是：在线性不等式或者线性等式的约束条件下，求能满足目标函数

取得最大值或者最小值的一组变量的值，目标函数也要求是线性函数。

命令:linprog

格式:X=linprog(f,A,b)

[X,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,Beq,LB,UB,X0,optio

ns)

功能：计算使目标函数取得最小值的一组变量的值。

说明：这里f为由目标函数的系数组成的向量。A是一个矩阵，b是一个向

量，A和b构成为了线性规划的不等式约束条件0X是一个向量，为返

回的满足目标函数取得极小值的一组变量的值。Aeq是一个矩阵，Beq是一个

向量，Aeq和Beq构成为了线性规划的等式约束条件oLB和UB分

②在优化问题中，涉及到优化结果只能取整数值的情况时，如果我们对优

化结果随意的进行取整，可能导致最后结果不是最优，这一点需要注意。

例2中国石油天然气集团公司天然气的运送(yCinsdng)案例分析

中国(zhonggu6)石油天然气集团公司在东海有一个(yigV)油气田(节点

),该公司要将开采的天然气通过管道运送(pinsbng)到上海的一个配送中心

(节点),天然气在运送途中(tUZhong)要经过两次管道换接点(节点B和

C).换接先后管道长短不一，而且不同的管道对应不同的单位流量运费。如

图，天然气运送的管道网络图，弧线表示管道，弧旁的数字为(，)，其中

b表示管道上的单位流量费用，c表示管道上的容量。公司希翼选择一个经济

巧ij

实惠的管道路线运送天然气，既运送最多的天然气又使总的运输费用至少。

(4,2

这是一个最小费用最大流问题。为了建立该问题的数学模型，首先设每段

管道(gumnd台o)上的流量作为问题的决策变量，分别记为

,称分段(fendgn)流量。

从始点u处，可得流量(同冶ng)函数，

S

且有约束条件：(1);

(2)

(3)；

一方面要使流量(I血诒ng)最大，另一方面要是(yaoshi)费用最小。

所以分两部份计算，先求出最大流，再求最小费用最大流。

对应matlab程序如下：

f=­[1,1,0,0,0,0,0,0,0];

aeq=[l,0,-1,-1,1,0,0,0,0;

0,1,1,0,0,-1,0,0,0;

0,0,0,1,0,0,1,-1,0;

0,0,0,0,-1,1,-1,0,-1];

beq=zeros(4,1);

lb=zeros(9,1);

ub=[4;5;1;3;1;2;3;5;2];

Lx,fvalj=linprog(aeq,beq,lb,ub)

%求出最大流

fl=[1,3,1,3,2,4,1,2,4];

aeql=[1,1,0,0,0,0,0,0,0;

1,0,-1,-14,0,0,0,0;

0,1,1,0,0,-1,0,0,0;

0,0,0,1,0,0,1,-1,0;

0,0,0,0,-1,1,-1,0,-1]；

beql=[-fval;beq];

[z,fvall]=linprog(fl,[],[],aeql,beql,lb,ub)

程序执行后，结果为：

Z=

4.0000

1.0000

1.0000

3.0000

0.0000

2.0000

2.0000

5.0000

0.0000

fvall=

37.0000

练习(I诒nx。

某快餐店一周中每天需要不同数目的雇员(gCiy陷n),设周一至少人，周二

至少(zhisl•谄o)人，周三至少(zhish*o)人，周四至少(zhishmo)人，周五至

少人，周六至少人，周日至少人，又规定雇员需连续工作5天，每人每

天的工资为C元。问快餐店怎样聘用雇员才干满足需求，又能使总聘用费用最

少。

提示：由于每一个雇员需连续工作5天，故快餐店聘用的总人数不一定是每

天聘用人数之和。我们定义周一开始工作的雇员数为，周日开始工作的雇

员数

为，则一周的聘用总费用为：，由于

除了周二和周三开始工作的雇员之外，其余的雇员都会在周一工作，所以周一

至少应有a人的约束应表示为：

1

类似地可以得出其他的约束条件。

现给定元，人'a?=15人y16人宣19人y14

人，a=12人，a=18人，请给出问题的数学模型，并用matlab求解。

67

内容总