线性规划模型

一、 线性规划模型的建立

例1某工厂A有生产甲，乙二种产品的能力，且生产一吨甲产品需要3个工日和0.35吨小麦。生产一吨乙产品需要4个工日和0.25吨小麦。该厂仅有工人12人，一个月只能出300个工日，小麦一个月只能进21吨，并且还知生产一吨甲产品可盈利80（百元），生产一吨乙产品可盈利90（百元）。那么，工厂A在一月中应如何安排这两种产品的生产，使之获得最大的利润？

由以上条件可列表如下：

产品 资源 工日 小麦 盈利

问题一的数学模型:

设x1,x2分别表示一月中生产甲，乙二种产品的数量，称之为决策变量。所得利润为z，问题一的目标是使得总利润函数z80x190x2有最大值。 工日的约束为：3x14x2300

原料小麦的约束为：0.35x10.25x221

于是问题一可归结为求目标函数在约束条件下的最大值问题，显然目标函数和约束条件都是决策变量的线性函数，即可建立以下线性规划模型

3 0.35 80 4 0.25 90 300 21 甲 乙 总和 maxz80x190x2s.t.3x14x23000.35x10.25x221x1,x20 (1.1)

1

1.1 线性规划模型的一般形式

maxminzcixii1ns.t.aj1nijxj,bii1,2,m （m个约束） (1.2)

xj0矩阵形式

j1,2,nmaxminzcTXs.t.AX,b (1.3)

X0其中Xx1,x2,xn为决策向量，cc1,c2,cn为目标函数的系数向量，

TTTbb1,b2,bm为常数向量，Aaijmn为系数矩阵。

1.2 线性规划模型的标准形

minzcTXs.t.AXb (1.4)

X0对于例1可取：

43300c80,90，A0.350.25，b21。

T1.3 如何化一般形为标准形 1.3.1 目标函数的转化

例2 一个工厂的甲，乙，丙三个车间生产同一种产品，每件产品由4个零件A和3个零件B组成。这两种零件耗用两种不同的原材料，而这两种原材料的现有数额分别是300公斤和500公斤。每个生产班的原材料的耗用量和零件产量如下表。问这三个车间应各开多少班数，才能使这种产品的配套数达到最大？

2

车间 每班用料数 原料1 原料2 6 9 8 每班产量(个) 零件A 7 6 8 零件B 5 9 4 甲 乙 丙

8 5 3 解: 设x1,x2,x3是甲，乙，丙三个车间所开的生产班数，由原材料的条件，得

8x15x23x33006x19x28x3500 (1.5)

甲，乙，丙生产A零件总数是: 7x16x28x3,生产B 零件总数是: 5x19x24x3。因为目标函数是要使产品的配套数最大，而每个零件要4个A零件，3个B零件，所以产品的最大量不超过

7x16x28x35x19x24x3和中较小的一个。设S是产品的配套数，

43即Smin7x16x28x35x19x24x3,

43 这个目标函数不是线性函数，但可以通过适当的变换把它化为线性的，设

7x6x28x35x19x24x3ymin1, (1.6)

43则上式可以等价于下面两个不等式

7x16x28x35x9x24x3y,1y (1.7)

43故可得如下线性规划模型:

maxSys.t.7x16x28x34y05x19x24x33y0 (1.8) 8x15x23x33005x19x28x3500x1,x2,x3,y0目标函数为求最大值，令Sy即可将原问题转化为在相同约束条件下求最小值。

3

1.3.2 约束条件的转化

若约束条件中有和号，则可在（）号的左端加上（或减去）一个非负变量（称为松弛变量）使其变成=号约束。如4x15x26变为4x15x2x36。

a1x1a2x2b若约束条件带有绝对值号，如a1x1a2x2b，则可等价转化为：。

axaxb2211若决策变量没有非负，称为自由变量。例如x1,为自由变量，则可引入

y10,y20，令x1y1y2代入模型即可。

二、 线性规划的求解方法

2.1 线性规划解的概念

T定义1.1 满足约束条件的解x(x1,x2,,xn)，称为线性规划问题的可行解，而使目标函

数达到最小值的可行解叫最优解。所有可行解构成的集合称为可行域，记为R。 2.2 线性规划解的基本理论

定理1.1 如果线性规划问题存在可行域，则其可行域是凸集。

定理1.2 如果线性规划问题的可行域有界，则问题的最优解一定在可行域的顶点上达到。 2.3 单纯形法

单纯形法是求解线性规划问题的最常用、最有效的算法之一。单纯形法是首先由 George Dantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由定理2可知，如果线性规划问题的最优解存在，则一定可以在其可行区域的顶点中找到。基于此，单纯形法的基本思路是：先找出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。这里我们不再详细介绍单纯形法，有兴趣的读者可以参看其它线

性规划书籍。 2.4 灵敏度分析

灵敏度分析是指对系统或周围事物因周围条件变化显示出来的敏感程度的分析。

4

在以前讨论线性规划问题时，假定aij,bi,cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；aij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：当这些参数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；或者这些参数在什么范围内变化时，线性规划问题的最优解不变。 2.5 可以转化为线性规划的问题

很多看起来不是线性规划的问题也可以通过变换变成线性规划问题来解决。如： 例3 问题为

min|x1||x2||xn|s. t. Axb其中x[x1 (1.9)

xn]T，A和b为相应维数的矩阵和向量。

要把上面的问题变换成线性规划问题，只要注意到事实：对任意的xi，存在ui,vi0满足

xiuivi，|xi|uivi (1.10)

事实上，我们只要取ui这样，记u[u1xi|xi||x|xi，vii就可以满足上面的条件。 22un]T，v[v1vn]T，从而我们可以把上面的问题变成

min(ui1nivi)

A(uv)b s. t.  (1.11)

u,v0

三、 利用MATLAB求解线性规划问题

假设线性规划问题的数学模型为：

5

minzcTXs.t.AXbAeqXbeqlbXub

其中Aeq表示等号约束，beq表示相应的常数项。lb,ub分别表示决策变量X的上，下限

MATLAB中求解上述模型的命令如下：

X=linprog（C，A，b,Aeq，beq，lb，ub）

注意，如果没有等式约束，可用[]代替Aeq和beq；如果某个xi下无界或上无界，可设定lb(i)= –inf或ub(i)=inf；用[x，Fval]代替上述各命令行着左边的x则可同时得到最优值。当求解时有指定迭代初值x0时，求解命令如下：

X=linprog（C，A，b,Aeq，beq，lb，ub，x0）

用[x，Fval]代替上述各命令行左边的X则可同时得到最优值。 例4 某部门在今后5年内考虑给下列项目投资：

项目1,从第一年到第四年每年年初需要投资,并于次年末收回本利115%；

项目2,第三年初需要投资,到第五年末收回本利125%,但规定最大的投资额不超过4万元； 项目3,第二年初需要投资,到第五年末收回本利140%,但规定最大的投资额不超过2万元； 项目4,五年内每年初可购买国债,于当年末还,并加利息6%。

设该部门现有资金10万元,问应如何确定这些项目的投资额,使第五年末拥有的资金本利总额最大?

解 设xiji1,2,3,4,5;j1,2,3,4表示第i年年初投资于项目j的金额。 项目 1 2 3 4

第一年 第二年 第三年 第四年 第五年 x11 x21 1.15x11 x31 1.15x21 x41 1.15x31 x51 1.15x41 x33 1.25x33 1.40x23 x23 x14 1.06x14 x24 1.06x24 x34 1.06x34 x44 1.06x44 x51 1.06x51 6

根据题意可得：

第一年：x11x1410 (全部投入,不考虑全部投入可使用小于，由下面都要相应变化与

课本同) (

可写篇文章)

第二年：x21x23x2416%x14 第三年：x31x32x341.15x111.06x24 第四年：x41x441.15x211.06x34 第五年：x541.15x311.06x44

对项目2，3的投资有限额的规定，有x324，x233

第五年末该部门拥有的资金本利总额为：S1.40x231.25x321.15x411.06x54 建立线性规划模型：

maxS1.40x231.25x321.15x411.06x54s.t.x11x1410x21x23x241.06x140x31x32x341.15x111.06x240x41x441.15x211.06x340x541.15x311.06x440x324x233xij0,i1,25;j1,2,4对应的MATLAB求解程序为：

c=[0,0,0,-1.4,0,0,-1.25,0,-1.15,0,-1.06]';

A=[0,0,0,0,0,0,1,0,0,0,0;0,0,0,1,0,0,0,0,0,0,0]; b=[4,3]';

Aeq=[1,1,0,0,0,0,0,0,0,0,0;0,-1.06,1,1,1,0,0,0,0,0,0;-1.15,0,0,0,-1.06,1,1,1,0,0,0;0,0,-1.15,0,0,0,0,-1.06,1,1,0;0,0,0,0,0,-1.15,0,0,0,-1.06,1]; beq=[10,0,0,0,0]; lb=zeros(11,1);

[x,fval]=linprog(c,A,b,Aeq,beq,lb) 输出结果为：

7

(1.12)

x=

6.5508 3.4492 0.6561 3.0000 0.0000 2.0066 4.0000 1.5268 2.3730 0.0000 2.3076 fval=

-14.3750 即第五年末该部门拥有的资金总额为14.375万元，盈利43.75%。

四、matlab命令详解

线性规划问题是目标函数和约束条件均为线性函数的问题，MATLAB6.0解决的线性规划问题的标准形式为：

xRn min fxsub.to：Axb

Aeqxbeq lbxub

其中f、x、b、beq、lb、ub为向量，A、Aeq为矩阵。

其它形式的线性规划问题都可经过适当变换化为此标准形式。 函数 linprog

格式 x = linprog(f,A,b) %求min f ' *x sub.to Axb线性规划的最优解。

x = linprog(f,A,b,Aeq,beq) %等式约束Aeqxbeq，若没有不等式约束

Axb，则A=[ ]，b=[ ]。

x = linprog(f,A,b,Aeq,beq,lb,ub) %指定x的范围lbxub，若没有等式约束

Aeqxbeq ，则Aeq=[ ]，beq=[ ]

x = linprog(f,A,b,Aeq,beq,lb,ub,x0) %设置初值x0

x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options) % options为指定的优化参数 [x,fval] = linprog(…) % 返回目标函数最优值，即fval= f ' *x。

[x,lambda,exitflag] = linprog(…) % lambda为解x的Lagrange乘子。 [x, lambda,fval,exitflag] = linprog(…) % exitflag为终止迭代的错误条件。 [x,fval, lambda,exitflag,output] = linprog(…) % output为关于优化的一些信息 说明 若exitflag>0表示函数收敛于解x，exitflag=0表示超过函数估值或迭代的最大数字，exitflag<0表示函数不收敛于解x；若lambda=lower 表示下界lb，lambda=upper表示上界ub，lambda=ineqlin表示不等式约束，lambda=eqlin表示等式约束，lambda中的非0元素表示对应的约束是有效约束；output=iterations表示迭代次数，output=algorithm表示使用的运算规则，output=cgiterations表示PCG迭代次数。

例5-1 求下面的优化问题

min 5x14x26x3

sub.to x1x2x320 3x12x24x342 3x12x230

0x1,0x2,0x3

解：

>>f = [-5; -4; -6];

>>A = [1 -1 1;3 2 4;3 2 0]; >>b = [20; 42; 30]; >>lb = zeros(3,1);

8

>>[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb)

结果为：

x = %最优解 0.0000 15.0000 3.0000

fval = %最优值 -78.0000

exitflag = %收敛 1 output =

iterations: 6 %迭代次数 cgiterations: 0

algorithm: 'lipsol' %所使用规则 lambda =

ineqlin: [3x1 double] eqlin: [0x1 double] upper: [3x1 double] lower: [3x1 double] >> lambda.ineqlin ans =

0.0000 1.5000 0.5000

>> lambda.lower ans =

1.0000 0.0000 0.0000

表明：不等约束条件2和3以及第1个下界是有效的

9