线性规划模型

第一章线性规划模型

一、线性规划模型的建立

例1某工厂A有生产甲，乙二种产品的能力，且生产一吨甲产品需要3个工日和0.35吨小

麦。生产一吨乙产品需要4个工日和0.25吨小麦。该厂仅有工人12人，一个月只能山300

个工日，小麦一个月只能进21吨，并且还知生产一吨甲产品可盈利80（百元），生产一吨

乙产品可盈利9。（百元）。那末，.LFA在一月中应如何安排这两种产品的生产，使之获得

最大的利润?

由以上条件可列表如下:

甲乙总和

资源

工日34300

小麦0.350.2521

盈利8090

问题•的数学模型：

设x,x分别表示一月中生产甲，乙二种产品的数量，称之为决策变量v所得利润为z,

12

问题一的目标是使得总利润函数z=80x+90x有最大值。

12

工日的约束为：3x+4x<300

12

原料小麦的约束为：0.35x+0.25x<21

12

于是问题FJ•归结为求F!标函数在约束条件下的最大值问题,显然H标函数和约束条件都

是决策变量的线性函数，即可建立以下线性规划模型

maxz=80x+90x

12

s.t.3x+4x<300

12（1.1）

0.35x+0.25x421

12

x,x>0

12

1

1.1线性规划模型的普通形式

max(min)z=2cx

ii

i.1

s.t.Xnax<(>,=)bi=1,2...,m(m个约束)(12)

ijji

j-1

x>0j=1,2...,n

J

矩阵形式

max(min)Z=CTX

s.t.AX《？，=)b(1.3)

X>0

其中X=(X,X,…X%为决策向量，c=(c,c,…c%为目标函数的系数向量，

12n12n

b三(b,b,…b>为常数向量，A=(a)为系数矩阵。

12mijm»n

1.2线性规划模型的标准形

minz=CTX

s.t.AX=b(1.4)

X20

对于例1可取：

CT(80,90),AJ34、J。。、

=

(0.350.25jV21J

1.3如何化普通形为标准形

1.3.1目标函数的转化

例2一个工厂的甲，乙，丙三个车间生产同一种产品，每件产品由4个零件A和3个

零件B组成。这两种零件耗用两种不同的原材料，而这两种原材料的现存数额分别是300

公斤和500公斤。每一个生产班的原材料的耗用量和零件产量如下表。问这三个车间应各开

多

少班数，才干使这种产品的配套数达到最大？

2

车间每班用料数每班产量(个)

原料1原料2零件A零件B

甲8675

乙5969

丙3884

解：设X,x,x是甲，乙，丙三个车间所开的生产班数，由原材料的限制条件，得

123

8x+5x+3x三300

6X1+9X2+8X3H500(1,5)

123

甲，乙，丙生产A零件总数是：7x+6x+8x，生产B零件总数是：5x+9x+4x。

123123

因为目标函数是要使产品的配套数最大，而每一个零件要4个A零件，3个B零件，所以产

品

lx+6.v+8.v5x+9x+4x

的最大量不超过—'----a-----^和1~~h--------^中较小的一个。设S是产品的配套数,

43

(7x+6x+8x5x+9x+4x)

即S=min(i23,i23卜

I43J

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

(7x+6x+8x5x+9x+4x)

y=min(—i---------2----------x,—i---------z-----------x卜(1.6)

I43J

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

7x+6x+8x.5x+9x+4x

123N123N

故可得如下线性规划模型：

maxS=y

s.t.7x+6x+8x-4y之0

123.

5x+9x+4x-3y之0

123

8x+5x+3x三300

123____

5x+9x+8x三5CO

123

x,xx,y之0

123

目标函数为求最大值，令S=-y即可将原问题转化为在相同约束条件下求最小值。

3

在以前讨论线性规划问题时，假定a,b,c都是常数。但实际上这些系数往往是估计值和预

ljii

测值。如市场条件一变，C值就会变化：a往往是因工艺条件的改变而改变；b是根据资

jUi

源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：当这些参数有一个或者

几个发生变化时，己求得的线性规划问题的最优解会有什么变化：或者这些参数在彳I么

范围内变化时，线性规划问题的最优解不变。

2.5可以转化为线性规划的问题

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

例3问题为

min|x|+|x|+...+|x|

1_2n(1.9)

s.t.Ax元b

其中X=[Xx]T,A和b为相应维数的矩阵和向量。

1n

要把上面的问题变换成线性规划问题，只要注意到事实：对任意的X,存在u,v>0

满足

U_V,|x|=U+V(1.10

事实上，我们只要取U='就可以满足上面的条件。

i

这样，记U=[UU]T,V=[V..v]T,从而我们可以把上面的问题变成

1n1n

n

minX(u+v)

ii

i=1

(A(u_v)7ub

s.t.('7i1.11)

'lu,v之0,

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

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

5

minz=CTX

A*X4b

stAeq*X=beq

lb<X<ub

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

限

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

X=1inprog(C,A,b,Aeq,beq；lb,ub)

注意，如果没有等式约束，可用□代替Aeq和beq；如果某个X下无界或者上无界，可设

定

i

lb(i)=-inf或者ub(i)=inf；用［x,Fval］代替上述各命令行着左边的x则可同时得到最

优值。当求解时有指定迭代初值xO时，求解命令如下：

X=1inprog(C.A,b,Aeq,beq,lb.ub.xO)

用［x,Fval］代替上述各命令行左边的X则可同时得到最优值。

例4某部门在今后5年内考虑给下列项目投资：

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

项目2,第三年初需要投资，到第五年末收回本利125%,但规定最大的投资额不超过4万元；

项目3,第二年初需要投资,到第五年末收回本利14(用,但规定最大的投资额不超过2万元；

项目4,五年内每年初可购买国债，于当年末还，并加利息6%。

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

额最大？

解设x(i=1,2,3,4,5;j=1,2,3,4)表示笫i年年初投资于项目j的金额。

ij

项第一年第二年第三年第四年第五年

目

1XX1.15XX1.15XX1.15XX1.15X

112111312141315141

2X1.25X

3333

3X1.40X

2323

4X1.06XX1.06XX1.06XX1.06XX1.06X

14142424343444445151

6

根据题意可得：

第一年：x+x=10:全部投入，不考虑全部投入可使用小于，由下面都要相应变化与

1114

可写篇文章

课本同)()

第二年：X4-X+X=(1+6%)x

21232414

第三年：x+x+x=1.15x+1.06x

3132341124

第四年：X+X=1.15X+1.06X

41442134

第五年：x=1.15x+1.06x

543144

对项目2,3的投资有限额的规定，有X44,X<3

3223

笫五年末该部门拥有的资金本利总额为：S=1.40x+1.25X+1.15x+1.06X

23324154

建立线性规划模型：

maxS=1.40x+1.25x+1.15x+1.06x

23324154

s.t.x+x=10

1114

x+x+x-1.06x=011.12)

21232414

x+x+x-1.15x-1.06x=0

321124

x4-x-1.15x-1.06x=0

41442134

x-1.15x-1.06x=0

543144

x<4

32

x<3

23

X>0,i=1,2...5；j=1,2...,4

对应的MATUB求解程序为：

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=[l,l,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,l,l,l,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

x=

6.55083.44920.65613.00000.00002.00664.00001.52682.3730

0.00002.3076

fval=

-14.3750

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

四、matlab命令详解

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

划问题的标准形式为：

minf'XXrRn

sub.to：A.xWb

Aeq.x=beq

lb<x<ub

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

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

函数linprog

格式x=linprog(f,A,b)%求minf'*xsub.toA.x<b线性规划的最优解。

x=linprog。,A,b,Aeq,beq)%等式约束Aeq.x=beq,若没有不等式约束

A.xKb,则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,xO)%设置初值xO

x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)%options为指定的优化参数

[x,fval]=linprogf--)%返回目标函数最优值,即fval=f'"x。

[x,lambda,exitfag]=linprog(…)%lambda为解x的Lagrange乘了。

[x,lambda,fval,exitflag]=linprog(-)%exitflag为终止迭代的错误条件。

[x,fval,lambda,exitflag,output]=linprog(…)%output为关于优化的一些信息

说明若exitflag>0表示函数收敛于解x,exitflag=0表示超过函数估值或者迭代的最大

数

字，exitflagvO表示函数不收敛于解x；若