實驗八線性函數極值求解

實驗目的

本實驗通過具體問題介紹線性規劃的一些基本概念和性質；掌握線性規劃問題的圖解法、軟件解法以及當線性規劃問題規模較小，并且存在最優解時的理論解法。實驗內容

本實驗主要介紹線性函數的極值求解方法，即線性規劃問題。它是運籌學的一個重要分支，在科學實踐中有著廣泛的應用，不僅許多實際課題屬于線性規劃問題，而且運籌學其它分支中的一些問題也可轉化為線性規劃問題來計算，因此，線性規劃在最優化學科中占有重要地位。本實驗通過具體問題介紹線性規劃的一些基本概念和性質，給出求解線性規劃問題的圖解法和軟件解法以及當線性規劃問題規模較小，并且存在最優解時的理論解法。美國空軍為了保證士兵的營養，規定每餐的食品中，要保證一定的營養成份，例如蛋白質、脂肪、維生素等等，都有定量的規定。當然這些營養成份可以由各種不同的食物來提供，例如牛奶提供蛋白質和維生素，黃油提供蛋白質和脂肪，胡蘿卜提供維生素，等等。由於戰爭條件的限制，食品種類有限，又要盡量降低成本，於是在一盒套餐中，如何決定各種食品的數量，使得既能滿足營養成份的需要，又可以降低成本？現代管理問題雖然千變萬化，但大致上總是要利用有限的資源，去追求最大的利潤或最小的成本，如何解決這些問題？

解決問題的方法：線性規劃在波斯灣戰爭期間，美國軍方利用線性規劃，有效地解決了部隊給養和武器調運問題，對促進戰爭的勝利，起了關鍵的作用。甚至有這樣的說法：因為使用炸藥，第一次世界大戰可說是「化學的戰爭」；因為使用原子彈，第二次世界大戰可說是「物理的戰爭」；因為使用線性規劃，波斯灣戰爭可稱為「數學的戰爭」。在歷史上，沒有哪種數學方法，可以像線性規劃那樣，直接為人類創造如此巨額的財富，并對歷史的進程發生如此直接的影響。例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=.