数学实验：实验八 线性函数极值求解

实验八线性函数极值求解

实验目的

本实验通过具体问题介绍线性规划的一些基本概念和性质；掌握线性规划问题的图解法、软件解法以及当线性规划问题规模较小，并且存在最优解时的理论解法。实验内容

本实验主要介绍线性函数的极值求解方法，即线性规划问题。它是运筹学的一个重要分支，在科学实践中有着广泛的应用，不仅许多实际课题属于线性规划问题，而且运筹学其它分支中的一些问题也可转化为线性规划问题来计算，因此，线性规划在最优化学科中占有重要地位。本实验通过具体问题介绍线性规划的一些基本概念和性质，给出求解线性规划问题的图解法和软件解法以及当线性规划问题规模较小，并且存在最优解时的理论解法。美国空军为了保证士兵的营养，规定每餐的食品中，要保证一定的营养成份，例如蛋白质、脂肪、维生素等等，都有定量的规定。当然这些营养成份可以由各种不同的食物来提供，例如牛奶提供蛋白质和维生素，黄油提供蛋白质和脂肪，胡萝卜提供维生素，等等。由於战争条件的限制，食品种类有限，又要尽量降低成本，於是在一盒套餐中，如何决定各种食品的数量，使得既能满足营养成份的需要，又可以降低成本？现代管理问题虽然千变万化，但大致上总是要利用有限的资源，去追求最大的利润或最小的成本，如何解决这些问题？

解决问题的方法：线性规划在波斯湾战争期间，美国军方利用线性规划，有效地解决了部队给养和武器调运问题，对促进战争的胜利，起了关键的作用。甚至有这样的说法：因为使用炸药，第一次世界大战可说是「化学的战争」；因为使用原子弹，第二次世界大战可说是「物理的战争」；因为使用线性规划，波斯湾战争可称为「数学的战争」。在历史上，没有哪种数学方法，可以像线性规划那样，直接为人类创造如此巨额的财富，并对历史的进程发生如此直接的影响。例1、生产计划问题：问：A,B各生产多少,可获最大利润?AB备用资源煤1230劳动日3260

仓库0224

利润4050一、引例某企业生产A，B两种产品，成本和利润指标如下：x1+2x2

30，

3x1

+2x2

60，

2x2

24，

x1，x2

0；maxZ=40x1

+50x2解:设产品A,B的产量分别为变量x1

，x2，则：s.t.

AB备用资源煤1230劳动日3260

仓库0224

利润4050例2：(资源配置问题)现有四种原料，其单位成本和所含维生素A，B，C成分如下：求：最低成本的原料混合方案。

ABＣ每单位成本

原料1

4102

原料2

6125

原料3

1716

原料4

2538每单位添加剂中维生素最低含量12148解：minZ=

2x1+

5x2+6x3+8x44x1+6x2+x3+2x4

12，x1+x2+7x3+5x4

14，

2x2+x3+3x4

8，

xi

0(i=1,…,4)；设每单位添加剂中原料i的用量为xi(i=1,2,3,4)，则：s.t.

ABＣ每单位成本原料14102

原料26125

原料31716

原料42538每单位添加剂中维生素最低含量12148

有一批长度为7.4m的钢筋若干根。现有5种下料方案，分别作成2.9m，2.1m，1.5m的钢筋架子各100根。每种下料方案及剩余料头如下表所示：例3、(资源配置问题)问：如何下料使得剩余料头最少？ⅠⅡⅢⅣⅤ2.9m120102.1m002211.5m31203合计7.47.37.27.16.6料头00.10.20.30.8解：设按第i种方案下料的原材料为xi根，则：minZ=0.1x2+0.2x3+0.3x4+0.8x5

x1+2x2+x4=100，

2x3+2x4+x5=100，3x1+x2+2x3+3x5=100，

xi

0(i=1,…,5)，且为整数；s.t.ⅠⅡⅢⅣⅤ2.9m120102.1m002211.5m31203合计7.47.37.27.16.6料头00.10.20.30.8例4、(运输问题)

123库存容量

1

21350

2

22430

3

34210

需求

401535仓库车间某棉纺厂的原棉需从仓库运送到各车间。各车间原棉需求量，单位产品从各仓库运往各车间的运输费以及各仓库的库存容量如下表所列：问：如何安排运输任务使得总运费最小？设xij为i

仓库运到j车间的原棉数量(i

＝1,2,3;

j＝1,2,3)。则minZ=2x11+x12+3x13+2x21+2x22+4x23

+3x31+4x32+2x33解：x11+x12+x13

50，x21+x22+x23

30，x31+x32+x33

10，x11+x21+x31=40，x12+x22+x32=15，x13+x23+x33=35，

xij

0，i

＝1,2,3;j＝1,2,3;s.t.123库存容量

121350222430334210需求401535仓库车间例5、连续投资10万元于4个项目。各项目投资时间和本利情况如下：项目A：从第1年到第4年每年初要投资，次年末回收本利1.15倍。项目B：第3年初投资，到第5年末回收本利1.25倍，最大投资4万元。项目C：第2年初投资，到第5年末回收本利1.40倍，最大投资3万元。项目D：每年初投资，每年末回收本利1.11倍。求：如何分配投资资金使得5年末总资本最大？以上问题的特点:2.某项任务确定后，如何安排人力、财力、物力，使之最省.1.在人力、财力、资源给定条件下，如何合理安排任务，使得效益最高.

即以上问题都是在一定条件下，求目标函数的最大值或最小值问题，而且目标函数和约束条件都是线性函数。这类问题称为线性规划LP(LinearProgramming，LP)问题。二线性规划问题的一般形式max(min)Z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn

(=,)b1,a21x1+a22x2+…+a2nxn

(=,)b2,………am1x1+am2x2+…+amnxn

(=,)bm,xj0(j=1,…,n);s.t.或三、线性规划问题的求解方法2二元线性规划问题的图解法3线性规划问题的理论解法1线性规划问题的MATLAB软件解法x=linprog(f,A,b):求解minz=f’

x,

Ax≤b1求解线性规划的MATLAB命令

若没有不等式约束,可用[]替代A和b,

若没有等式约束,可用[]替代Aeq和beq,若某个xi下无界或上无界,可设定-inf或inf；用[x,Fval]代替上述命令行中的x，可得最优解处的函数值Fval。x=linprog(f,A,b,Aeq,beq):求解：

minz=f’

x,Ax≤b,Aeqx=beq；x=linprog(f,A,b,Aeq,beq,lb,ub):

指定lb≤x≤ub;[x,fval,exitflag,output]=linprog(f,A,b,Aeq,beq,lb,ub)X为最优解向量；fval为最优值；exitflag描述linprog的终止条件：若为正值，表示目标函数收敛于解x，若为负值，表示目标函数不收敛，若为零值，表示已经达到函数评价或迭代的最大次数。output为返回优化算法信息的一个数据结构：output.iteration表示迭代次数，output.algorithm表示所采用的算法，output.funcCount表示函数评价次数。x1+2x2

30，

3x1

+2x2

60，

2x2

24，minZ=-40x1

-50x2s.t.例1、解：程序如下-------zhao81

c=[-40,-50];a=[1,2;3,2;0,2];b=[30;60;24];x=linprog

(c,a,b)

z=c*xx1+x2

5,-6

x1

10,

-1

x2

4;例2:minZ=4x1

+3x2s.t.解：%zhao82.m%c=[4,3];a=[1,1];b=[5];vlb=[-6;-1];

%lowerboundofvector

x%vub=[10;4];%upperboundofvectorx%x=linprog(c,a,b,[],[],vlb,vub)z=c*xx1+x2

+x37,-x1

+x2

-x3

-2,x1

,x2

,x3

0;例3:minZ=-x1+2x2

–3x3s.t.解：%zhao83.m%c=[-1,2,-3];a=[1,1,1;-1,1,-1];b=[7;-2];vlb=[0;0;0];

%lowerboundofvectorx%vub=[];%upperboundofvectorx%x=linprog(c,a,b,[],[],vlb,vub)z=c*xminZ=2x1+x2+3x3+2x4+2x5+4x6

+3x7+4x8+2x9x1

+x4

+x7

=40，

x2

+x5

+x8

=15，

x3

+x6

+x9

=35，x1+x2+x3

50，

x4+x5+x6

30，

x7+x8+x9

10，

xi

0，i

＝1,2,…,9;s.t.例4:%zhao84.m%c=[2,1,3,2,2,4,3,4,2];beq=[40;15;35];b=[50;30;10];a=[1,1,1,0,0,0,0,0,0;0,0,0,1,1,1,0,0,0;0,0,0,0,0,0,1,1,1];aeq=[1,0,0,1,0,0,1,0,0;0,1,0,0,1,0,0,1,0;0,0,1,0,0,1,0,0,1];vlb=zeros(9,1);%lowerboundofvectorx%vub=[];%upperboundofvectorx%x=linprog(c,a,b,aeq,beq,vlb,vub)z=c*x解：2线性规划问题的图解法Ax=b(1)x

0(2)maxZ=cx(3)定义1：满足约束(1)、(2)的x=(x1,

…,xn)T称为LP问题的可行解，全部可行解的集合称为可行域。定义2：满足(3)的可行解称为LP问题的最优解.图解法步骤（1）作出可行域的图形；（2）作出目标函数等值线；（3）将目标函数等值线自坐标原点开始向上（下）平移，与可行域的最后一个交点就是最优解；（4）求最优解坐标和最优值。x1+2x2

30，

3x1

+2x2

60，

2x2

24，

x1，x2

0；maxZ=40x1

+50x2例1:s.t.二元线性规划问题的图解法

AB备用资源煤1230劳动日3260

仓库0224

利润4050x2=0(纵)

(0,30),(20,0)

2x2

=24(1)、确定可行域解：x1

0;x1=0(横)x2

0;x1+2x2

30x1+2x2

=30

(0,15)(30,0)与坐标轴交点:3x1+2x2

=602x2

243x1+2x2

600x2102030DABC3x1+2x2

=

60x1+2x2

=302x2

=243010x120(2)、求最优解x*=(15,7.5)Z=40x1+50x20=40x1+50x2

x1+2x2

=303x1+2x2

=60C点:0102030x2DABC3x1+2x2

=

60x1+2x2

=302x2

=

24203010x1Z=975Z=0Zmax=975(0

1)maxZ=40x1+80x2

x1+2x230,3x1+2x260,2x224,

x1,x20;例2:

求解s.t.最优解：BC线段B点:x(1)=(6,12)'

C点:x(2)=(15,7.5)'BC线段:maxZ=1200

0102030x2DABC3x1+2x2

=

60x1+2x2

=302x2

=

24203010x1Z=1200Z=0例３、

maxZ=3x1+2x2

-x1-x21,x1,x20;即无可行解.x2x1-1-10s.t.可行域无解.-x1-x2=13线性规划问题的理论解法

（１）线性规划问题的标准形式特点：（1）所有约束条件是等式；（2）约束条件右端常数项为非负；（3）所有变量是非负。A称为约束矩阵.（２）化一般线性规划问题为标准形约束条件的转换：称为剩余变量或松弛变量

x1

+2x2

+x3

=30，

3x1

+2x2

+x4

=60，

2x2

+

+x5

=24，

x1

,

…,x5

0

；

maxZ=40x1+50x2+0·x3+0·x4+0·x5x1+2x2

30，

3x1

+2x2

60，

2x2

24，

x1，x2

0；maxZ=40x1

+50x2例1:s.t.其中x3

,

x4,x5

为松弛变量。s.t.minZ=

2x1+

5x2+6x3+8x44x1+6x2+x3+2x4

12，x1+x2+7x3+5x4

14，

2x2+x3+3x4

8，

xi

0(i=1,…,4)；例2：minZ=

2x1+

5x2+6x3+8x4

+0x5+0x6+0x74x1+6x2+x3+2x4

-x5

=12，x1+x2+7x3+5x4

-x6

=14，

2x2+x3+3x4

–x7=8，

xi

0(i=1,2,…,7)；其中x5

,

x6,x7

为剩余变量。s.t.s.t.变量的转换例3:令:

x1=x1'-x1

"3x1+2x28,x1

–4x2

14,x20,x1

为自由变量;(1)(1)3x1'–3

x1"+2x28,

x1'

–x1

"–4x2

14,x1',x1",x2

0;(2)令:

x1

'=x1

+6,

则

0

x1'

16x1+x2

5,-6

x1

10,x20;(3)-6+6x1+6

10+6易知:例4:(3)x1'

+x2

11,x1

'

16,x1',x2

0;(4)目标函数的转换ZZ

'令Z'=-ZxoZ将以下线性规划问题x1+x2

+x37,x1

-x2

+x3

2,x1

,x2

0，x3为自由变量;化为标准型。例5:minZ=-x1+2x2

–3x3s.t.①令x3

=x4

-

x5②加松弛变量x6③加剩余变量x7

④令Z'=-ZmaxZ'=x1–2x2+3x4

–3x5

解minZ=-x1+2x2

–3x3x1+x2

+x37,x1

-x2

+x3

2,x1

,x2

0；s.t.x1

+x2

+x4

-x5

+x6

=7,x1

-x2

+x4

-x5

-x7

=2,x1

,

x2

,

x4

,x5

,

x6,x7

0;s.t.（３）线性规划问题的理论解法:凸集：定义1：Ax=b(1)x

0(2)maxZ=cx(3)设D是n维欧氏空间的一个集合。任意点x(1),

x(2)∈D,若任一满足

x=

x(1)+(1-

)x(2)(0

1)的点x∈D。则D称为凸集。..x(2)x(1).x设线性规划的标准型B＝[P1

…

Pm]N=[Pm+1

…

Pn]a11…a1ma21…

a2m…………am1…

ammP1

…

Pma1m+1…a1na2m+1…

a2n……………amm+1…

amnPm+1

…

PnA＝，定义2：基(基阵)——若A中一个子矩阵方阵B可逆，则矩阵B称为LP问题的一个基(基阵)

。基向量:P1

…

Pm;非基向量:Pm+1

…

Pn;基变量:x1

xm…xB

=;非基变量:xN

=xm+1

xn…;设x=x1

xm…xm+1

xn…=xB

xN，xB=B-1b-B-1NxNA=[BN]x=xB

xNAx=b记:BxB+NxN=bBxB=b-NxN简称可行解，这时的基B称为可行基。称为Ax=b的一个基本可行解。B-1

b

0x=若B-1b0，x1+2x2+x3=30,3x1+2x2+x4=60,2x2+x5=24,x1…x50;例1、b=306024取B=[P3P4P5]=I

可逆,基阵。121003201002001P1P2P3P4P5A=,N=[P1P2]非基阵.非基向量xN=x1x2,xB=x3x4x5,基向量x=xN

xB解向量xB=B-1b-B-1NxNAx=b令=00xN=x1x2则基本解00306024x=xN

xB=因为x

0，是基本可行解。又由det(B1)=6≠0,知B1可逆,可以充当基矩阵.121320020=若取B1=(P1P2P3)相应的非基阵N1

=[P4P5]xB1=x1x2x3,基变量x4x5xN1=.非基变量得基本解令1212-600xB1

xN1x==(B1)

-1b0=.