線性規(guī)劃精品課件

1、關(guān)于線性規(guī)劃第一張，PPT共一百零一頁，創(chuàng)作于2022年6月2決策變量：x1, ., xn表示要尋求的方案，每一組值就是一個方案；約束條件：線性等式或不等式目標函數(shù)：Z=(x1 xn) 線性式，求Z極大或極小線性規(guī)劃模型特點第二張，PPT共一百零一頁，創(chuàng)作于2022年6月3 一般式min z=c1x1+ c2x2+cnxnai1x1+ ai2x2+ ainxn =bi ,i=1,pai1x1+ ai2x2+ ainxn bi , i=p+1,mxj 0 , j=1,qxj 符號無限制， j=q+1,ns.t.目標函數(shù)（LP）第三張，PPT共一百零一頁，創(chuàng)作于2022年6月4比例性：決策變量變化

2、引起目標的改變量與決策變量改變量成正比可加性：每個決策變量對目標和約束的影響?yīng)毩⒂谄渌兞窟B續(xù)性：每個決策變量取連續(xù)值確定性：線性規(guī)劃中的參數(shù)aij , bi , ci為確定值 隱含的假設(shè)第四張，PPT共一百零一頁，創(chuàng)作于2022年6月5 矩陣形式說明： A1 A2 An a11 a12 a1n A= a21 a22 a2n am1 am2 amn x1 x= x2 xn b1 b= b2 bm c1 c= c2 cn約束矩陣決策向量右端向量價值向量第五張，PPT共一百零一頁，創(chuàng)作于2022年6月6 LP問題的規(guī)范型： LP問題的標準型：LP問題的三種形式是等價的：min z=cTxAx bx

3、 0 s.t.min z=cTxAx=bx 0 s.t.LP問題的規(guī)范型LP問題的標準型LP問題的一般型第六張，PPT共一百零一頁，創(chuàng)作于2022年6月7LP問題的規(guī)范型LP問題的一般型第七張，PPT共一百零一頁，創(chuàng)作于2022年6月8LP問題的標準型LP問題的一般型第八張，PPT共一百零一頁，創(chuàng)作于2022年6月9 例：將線性規(guī)劃問題化成標準型：第九張，PPT共一百零一頁，創(chuàng)作于2022年6月10解的概念：滿足所有約束條件的一組x1, x2， xn的值稱作線性規(guī)劃的可行解，所有可行解構(gòu)成的集合稱作可行域。使目標函數(shù)取得最大或最小值的可行解稱為線性規(guī)劃問題的最優(yōu)解；對應(yīng)的目標函數(shù)的取值稱為最優(yōu)

4、值。求解線性規(guī)劃問題就是求其最優(yōu)解和相應(yīng)的最優(yōu)值。圖解法？對于只有兩個變量的線性規(guī)劃問題，可以用在平面上作圖的方法求解，這種方法稱為圖解法。 特點：圖解法簡單、直觀，便于初學(xué)者了解線性規(guī)劃基本原理和幾何意義。2.2可行區(qū)域與基本可行解第十張，PPT共一百零一頁，創(chuàng)作于2022年6月11step1.畫直角坐標系； 線性規(guī)劃問題圖解法的步驟 對每個約束（包括非負約束）條件，先取等式得到一條直線（平面）并在坐標圖中畫出該直線，然后取一已知點來判斷該點的坐標是否滿足該約束條件，若滿足，則可行域與已知點在所畫直線的同側(cè)，否則可行域在直線的另一側(cè)。若所有的約束均已畫出，則可在坐標系中畫出可行域。step2

5、.依次做每條約束線，找出可行域;若不存在可行域,則該問題無界；step3.做目標函數(shù)線，根據(jù)目標類型平移,直到該線即將離開可行域時與該線接觸的最后一點即為一最優(yōu)解; 若該線可無限制地在可行域內(nèi)移動,則該問題無界。第十一張，PPT共一百零一頁，創(chuàng)作于2022年6月12例1、maxZ=-X1+ X2 2 X1-X2 -2X1-2X2 2X1+X2 5 X1 , X2 0 1.圖解法第十二張，PPT共一百零一頁，創(chuàng)作于2022年6月13解：(1)、確定可行域 X1 0 X1 =0 (縱) X2 0 X2=0 (橫) 2 X1-X2 =-2 () (0,2) (-1,0)0123X2BCX1-2X2

6、=2 ()(0,-1) (2,0) 42 X1-X2 =-2X1-2X2 =2X1+X2 =5 ()(0,5) (5,0) X1+X2 =5(1,4)- X1+X2 =3- X1+X2 =0在該點取到最大值3A1A2A3A4OZ=-X1+ X2, Z=0 2 3 1解：(1)、確定可行域 X1 0 X1 =0 (縱) X2 0 X2=0 (橫) 0123X2第十三張，PPT共一百零一頁，創(chuàng)作于2022年6月14 2 3 10123X2A1BC42 X1-X2 =-2X1-2X2 =2X1+X2 =5(1,4)若目標函數(shù)改為min Z=4X1-2X2 2 X1-X2 -2X1-2X2 2X1+X

7、2 5 X1 , X2 0A2A3A4O第十四張，PPT共一百零一頁，創(chuàng)作于2022年6月15最優(yōu)解：A1A2線段上所有的點，最優(yōu)值為-4X(1)=(0, 2)T , X(2)=(1,4)TX= X(1)+(1-) X(2) (0 1)X1 =1- X2=2+4 (1- )=4-2 (0 1)min Z=4X1-2X2 =-4 第十五張，PPT共一百零一頁，創(chuàng)作于2022年6月16 2 3 10123X2A1BC42 X1-X2 =-2X1-2X2 =2X1+X2 =5(1,4)A2A3A4O可行域：由約束平面圍起來的凸多邊形區(qū)域，可行域內(nèi)的每一個點代表一 個可行解。最優(yōu)解：總是在可行域的邊界

8、上，一般由可行域的頂點表示。有效與無效(緊與松)約束：與最優(yōu)解相關(guān)的約束為有效(緊)約束。圖解法的觀察【1】第十六張，PPT共一百零一頁，創(chuàng)作于2022年6月17無界無有限最優(yōu)解例2、 maxZ=2X1+ 4X2 2X1+X2 8-2X1+X2 2X1 , X2 0Z=02X1+ X2=8-2X1+ X2=28246X240X1第十七張，PPT共一百零一頁，創(chuàng)作于2022年6月18例3、 maxZ=3X1+2X2 -X1 -X2 1X1 , X2 0無解無可行解-1X2-1X10-X1-X2 =1第十八張，PPT共一百零一頁，創(chuàng)作于2022年6月19如果可行域為空集，線性規(guī)劃問題無可行解；如果

9、目標函數(shù)線可以無限制地在可行域內(nèi)向改善的方向移動，線性規(guī)劃問題無界；線性規(guī)劃問題可能存在無窮多個最優(yōu)解。圖解法的觀察（2） 唯一最優(yōu)解 無窮多最優(yōu)解 無有限最優(yōu)解 無可行解有最優(yōu)解無最優(yōu)解總結(jié)第十九張，PPT共一百零一頁，創(chuàng)作于2022年6月20兩個變量的LP問題的解：(1)、可行域為凸多邊形。(2)、若有最優(yōu)解，定可在可行域的頂點得到。X(1)X(2)凸多邊形凹多邊形X(1)X(2)第二十張，PPT共一百零一頁，創(chuàng)作于2022年6月212.可行區(qū)域的幾何結(jié)構(gòu)min Z=CTX AX =b X0A mn 滿秩 X = (x1 xn)T D=XRn| AX =b, X0第二十一張，PPT共一百零

10、一頁，創(chuàng)作于2022年6月22凸集沒有凹陷部分，該集合內(nèi)任取兩點連線上的任何點都應(yīng)該在集合內(nèi)。 定義1：xSy凸集：S是n維歐氏空間的一個集合,如果對任意 x, yS, 0 1, 有x + (1 - ) y S。第二十二張，PPT共一百零一頁，創(chuàng)作于2022年6月23定理1 D=XRn| AX =b, X0是凸集。第二十三張，PPT共一百零一頁，創(chuàng)作于2022年6月24定義2： 給定bR1,及非零向量aTRn稱集合H =XRn| aTX =b是Rn中的一個超平面.H+ =XRn| aTX bH- =XRn| aTX bH+，H-和超平面H都是凸集.H+和H-是由超平面H產(chǎn)生的兩個閉的半空間.結(jié)

11、論：線性規(guī)劃的可行域是凸集。第二十四張，PPT共一百零一頁，創(chuàng)作于2022年6月25定義3：凸集凸集S的頂點X：S是一個凸集，XS，對任意X(1), X(2)S，X(1) X(2) ,和任意的 ，01,都有 X X(1)+(1-) X(2) .定義4：第二十五張，PPT共一百零一頁，創(chuàng)作于2022年6月26a11 a1m a1m+1 a1na21 a2m a2m+1 a2n am1 amm amm+1 amnBN(m n) r(A)=m , 至少有一個m階子式不為03、基本可行解及線性規(guī)劃的基本原理第二十六張，PPT共一百零一頁，創(chuàng)作于2022年6月27定義5：基(基陣) 秩為m的約束矩陣 A

12、mn的一個m階子矩陣B是可逆矩陣，則方陣B稱為對應(yīng)LP問題的一個基。A= (A1 Am Am+1 An )=(BN) 基向量 非基向量X= (X1 Xm Xm+1 Xn )T=(XBT ，XNT)T 基變量 非基變量 XBT XNT第二十七張，PPT共一百零一頁，創(chuàng)作于2022年6月28AX=b的求解A=(B N)X=(XBT ，XNT)T XB XN(B N) = bBXB +NXN=bBXB =b-NXNXB = B-1 b - B-1N XN第二十八張，PPT共一百零一頁，創(chuàng)作于2022年6月29定義5：基本解對應(yīng)于基B，X=為AX=b的一個解。B-1 b 0 基本可行解基B，基本解X=

13、若B-1 b0，稱基B為可行基。 B-1 b 0 基本解中最多有m個非零分量。 基本解的數(shù)目不超過Cnm = 個。n!m!(n-m)!（續(xù)）第二十九張，PPT共一百零一頁，創(chuàng)作于2022年6月30 X1+2X2 +X3 =30 3X1+2X2 +X4 =60 2X2 +X5=24 X1 X5 01 2 1 0 03 2 0 1 00 2 0 0 1A1 A2 A3 A4 A5A=例：Max Z=40X1 +50X2 第三十張，PPT共一百零一頁，創(chuàng)作于2022年6月31X1X2X3X4X5X=b=306024基 B=(A3 A4 A5)=I 可逆 非基 N=(A1 A2)X3=30-( X1+

14、2 X2)X4=60-(3X1+2 X2)X5 =24 -2 X21 2 1 0 03 2 0 1 00 2 0 0 1A1 A2 A3 A4 A5A=Z=40X1 +50X2 第三十一張，PPT共一百零一頁，創(chuàng)作于2022年6月32令X1 = X2 =0, X3=30, X4=60, X5=24X= = = XN 0 XB B-1 b 00306024 1 2 1又：1 =(A1 A2 A3 )= 3 2 0 0 2 0|B1|=60, 可逆第三十二張，PPT共一百零一頁，創(chuàng)作于2022年6月33X1=12-(1/3 X4 -1/3 X5)X2=12-(1/2 X5 )X3 =-6-(- 1

15、/3 X4 -2/3 X5 )令X4=X5=0 X=(12, 12, -6, 0, 0)T不是可行解1 =(A1 A2 A3 )不是可行基?？梢灾苯域炞CB-1 b 是否大于等于零。 第三十三張，PPT共一百零一頁，創(chuàng)作于2022年6月34定理3：LP問題的可行解X是基本可行解X的非0分量對應(yīng)的系數(shù)列向量線性無關(guān)證明：( )顯然。 不妨設(shè)前k個分量非零。若A1 , , Ak 線性無關(guān)，則必有km。 若k=m,構(gòu)成基，則X就是基本可行解；若km,可以在其余n-k列向量中再找出m-k個，構(gòu)成m個線形無關(guān)的列向量構(gòu)成基， X就是該基對應(yīng)的基本可行解。第三十四張，PPT共一百零一頁，創(chuàng)作于2022年6月

16、35可行域D中點X是頂點X是基本可行解定理4：第三十五張，PPT共一百零一頁，創(chuàng)作于2022年6月36標準形式的LP問題有可行解該LP問題一定有基本可行解定理5：第三十六張，PPT共一百零一頁，創(chuàng)作于2022年6月37標準形式的LP問題有有限的最優(yōu)值該LP問題一定有基本可行解是最優(yōu)解定理6:第三十七張，PPT共一百零一頁，創(chuàng)作于2022年6月38若(LP)問題有可行解，則可行解集(可行域)是凸集(可能有界，也可能無界)，有有限個頂點。LP問題解的性質(zhì) (LP)問題的基本可行解 可行域的頂點。 若(LP)問題有最優(yōu)解，必可以在基本可行解(頂點)達到。第三十八張，PPT共一百零一頁，創(chuàng)作于2022

17、年6月39可行解基本解基本可行解個數(shù)有限，當約束條件為m個，n個變量時，基本可行解個數(shù)不超過:Cnm = n!m!(n-m)!(m 40 選X2從0，X1 =0X3 =30-2X2 0， X2 30/2 X4 =60-2X2 0， X2 60/2 X5 =24-2X2 0 ，X2 24/2 X2=min(30/2 , 60/2 , 24/2 ) =12X2進基變量， X5出基變量。min W=-40X1 -50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0第四十二張，PPT共一百零一頁，創(chuàng)作于2022年6月43B2=(A3 A4

18、A2)min W=-40X1 -50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0min W=-600-40X1 +25X5 X1 +X3 -X5 =6 3X1 +X4 - X5 =36 X2 +1/2X5 =12 X1 X5 0 1/2 ，代入式， ，令X1 =X5 =0 X(2) =(0, 12, 6, 36, 0)T W(2) =-600第四十三張，PPT共一百零一頁，創(chuàng)作于2022年6月44(2) 判斷： min W=-600-40X1 +25X5 400， X(2)不是最優(yōu)解。(3) 選X1從0， X5 =0 X3= 6

19、- X1 0 X4= 36-3X1 0 X2=12 0 X1=min( 6/1 , 36/3 ) =6X1進基， X3出基。min W=-600-40X1 +25X5 X1 +X3 -X5 =6 3X1 +X4 - X5 =36 X2 +1/2X5 =12 X1 X5 0第四十四張，PPT共一百零一頁，創(chuàng)作于2022年6月45B3 =(A1 A4 A2 )minW=-840+40X3-15X5X1 +X3 -X5 =6 -3X3 + X4 +2X5 =18 X2 +1/2X5 =12令X3 =X5 =0 ,X(3) =(6, 12, 0, 18, 0)TW(3) =-840min W=-600

20、-40X1 +25X5 X1 +X3 -X5 =6 3X1 +X4 - X5 =36 X2 +1/2X5 =12 X1 X5 0代入式， -3*第四十五張，PPT共一百零一頁，創(chuàng)作于2022年6月46(2) 判斷：minW=-840+40X3-15X5 150 X(3)不是最優(yōu)解(3) 選X5從0， X3 =0 X1=6 +X5 0 X4= 18 -2X5 0 X2=12-1/2 X5 0 X5=min( 18/2 , 12/1/2 ) =9X5進基， X4出基。minW=-840+40X3-15X5X1 +X3 -X5 =6 -3X3 + X4 +2X5 =18 X2 +1/2 X5 =12

21、第四十六張，PPT共一百零一頁，創(chuàng)作于2022年6月47B4=(A1 A5 A2 )minW=-975+35/2X3 + 15/2X4X1 -1/2X3 + 1/2X4 = 15 -3/2X3 +1/2X4 + X5= 9 X2+3/4X3 - 1/4X4 = 15/2 令X3 =X4 =0 ,X(4) =(15, 15/2 , 0, 0 ,9 )T W(4)=-975minW=-840+40X3-15X5 X1 +X3 -X5 =6 -3X3 + X4 +2X5 =18 X2 +1/2 X5 =12 1/2 ， 代入式， +(1/2) ， -(1/4) 判斷：minW=-975+35/2X3

22、 + 15/2X4 ，maxZ=975達到最優(yōu)。第四十七張，PPT共一百零一頁，創(chuàng)作于2022年6月48例1 x1 x2 x3 x4 x5-z0 40 50 0 0 0 x3x4x5306024 1 2 1 0 0 3 2 0 1 0 0 2 0 0 1maxZ=40X1 +50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0(-z)+40X1 +50X2 =0 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0X2 30/2 X2 60/2 X2 24/2回顧第四十八張，PPT

23、共一百零一頁，創(chuàng)作于2022年6月49例1 x1 x2 x3 x4 x5-z-600 40 0 0 0 -25 x3x4x263612 1 0 1 0 -1 3 0 0 1 -1 0 1 0 0 1/2(-z)+40X1 -25X5 =-600 X1 +X3 -X5 =6 3X1 +X4 -X5 =36 X2 +(1/2) X5 =12 X1 X5 0X1 6/1 X1 36/3第四十九張，PPT共一百零一頁，創(chuàng)作于2022年6月50例1 x1 x2 x3 x4 x5-z-840 0 0 -40 0 15x1x4x261812 1 0 1 0 -1 0 0 -3 1 2 0 1 0 0 1/2

24、(-z) -40X3 +15X5 =-840 X1 +X3 -X5 =6 -3X3 +X4 +2X5 =18 X2 +1/2 X5 =12 X1 X5 0X5 18/2 X5 12/1/2第五十張，PPT共一百零一頁，創(chuàng)作于2022年6月51例1(-z)-35/2X3 -15/2X4 =-975 X1 -1/2X3 +1/2X4 =15 -3/2X3 +1/2X4 +X5 =9 X2 +3/4X3 -1/4X4 =15/2 X1 X5 0 x1 x2 x3 x4 x5-z-975 0 0 -35/2 -15/2 0 x1x5x215915/2 1 0 -1/2 1/2 0 0 0 -3/2 1

25、/2 1 0 1 3/4 -1/4 0 X(4) =(15, 15/2 , 0, 0 ,9 )T maxZ=975第五十一張，PPT共一百零一頁，創(chuàng)作于2022年6月520(0,0)X2X1A DCB(0,12)(6,12)(15,7.5)X(1) =(0, 0, 30, 60, 24 )T ；Z(1) =0X(2) =(0, 12, 6, 36, 0)T ； Z(2) =600X(3) =(6, 12, 0, 18, 0 )T ；Z(3) =840 X(4) =(15, 7.5, 0, 0, 9 )T ；Z(4) =975思考：線性規(guī)劃問題的求解方法第五十二張，PPT共一百零一頁，創(chuàng)作于20

26、22年6月單純形法的理論基礎(chǔ)（略）第五十三張，PPT共一百零一頁，創(chuàng)作于2022年6月54為了敘述方便，我們不妨假設(shè)（LP）問題為如下形式：或典則方程組（典式）非基變量檢驗數(shù)第五十四張，PPT共一百零一頁，創(chuàng)作于2022年6月55單純形表 X1 X2 Xm Xm+1 Xm+k XnXB Z0 0 0 0 m+1 m+k nX1 b1 1 0 0 a1m+1 a1m+k a1nX2 b2 0 1 0 a2m+1 a2m+k a2nXr br 0 0 0 arm+1 arm+k arnXm bm 0 0 1 amm+1 amm+k ann P1 P2 Pm Pm+1 Pm+k Pn第五十五張，PP

27、T共一百零一頁，創(chuàng)作于2022年6月56此時，B=(P1 P2 Pm )I對應(yīng)的基本可行解為定理1：對解X(1) ，若檢驗數(shù)j ( j=1,n)全部 0,則X(1)為最優(yōu)解。第五十六張，PPT共一百零一頁，創(chuàng)作于2022年6月57定理2：對X(1)，若有某個非基變量Xkk0且相應(yīng)的Pk =(a1k , ,amk )T 0，則原問題無有限最優(yōu)解。第五十七張，PPT共一百零一頁，創(chuàng)作于2022年6月58換基迭代公式：(1)、決定進基變量：maxj =k 0,則Xk 為進基變量(2)、決定離基變量：bi -aikXk 0 ( i=1 ,2 , m)，Xk biaik(aik0= min aik 0

28、=biaikbrark則第r個基變量（XBr）為換出變量。第五十八張，PPT共一百零一頁，創(chuàng)作于2022年6月59定理3：在非退化情況下，經(jīng)單純形法得到的X(2) =(b1 - a1k , ,bm - amk ,0, , , ,0)T是基本可行解，且Z(2)0 =biaikbrark注：第五十九張，PPT共一百零一頁，創(chuàng)作于2022年6月60單純形法基本步驟(1)、定初始基，初始基本可行解，典式， 檢驗數(shù)(3)、若有k 0，Pk全 0，停， 沒有有限最優(yōu)解； 否則轉(zhuǎn)(4)(2)、對應(yīng)于非基變量檢驗數(shù)j全 0。 若是，停，得到最優(yōu)解； 若否，轉(zhuǎn)(3)。第六十張，PPT共一百零一頁，創(chuàng)作于2022

29、年6月61= min aik 0 =biaikbrark定第r個基變量（XBr）為離基變量，ark為主元。由最小比值法求：kmaxj|j=1,n0 ,kXk Xk為進基變量j0(4)、第六十一張，PPT共一百零一頁，創(chuàng)作于2022年6月62轉(zhuǎn)(2) k 0 a1k 0ark 1amk 0初等行變換Pk =(5)、以ark為中心，換基迭代第六十二張，PPT共一百零一頁，創(chuàng)作于2022年6月63在單純形表上解決下述問題 maxZ=40X1 +50X2 X1 +2X2 +X3 =30 3X1 +2X2 +X4 =60 2X2 +X5 =24 X1 X5 0Min Z=-40X1-50X2第六十三張，

30、PPT共一百零一頁，創(chuàng)作于2022年6月64 X1 X2 X3 X4 X5Z 0 40 50 0 0 0 X3 30 1 2 1 0 0 15X4 60 3 2 0 1 0 30X5 24 0 (2) 0 0 1 12 -600 40 0 0 0 -25X3 6 (1) 0 1 0 -1 6X4 36 3 0 0 1 -1 12X2 12 0 1 0 0 1/2 -840 0 0 -40 0 15X1 6 1 0 1 0 -1X4 18 0 0 -3 1 (2) 9X2 12 0 1 0 0 1/2 24第六十四張，PPT共一百零一頁，創(chuàng)作于2022年6月65 z -975 0 0 -35/2

31、 -15/2 0 X1 15 1 0 -1/2 1/2 0 X5 9 0 0 -3/2 1/2 1 X2 15/2 0 1 3/4 -1/4 0本問題的最優(yōu)解 X=(15, 15/2, 0, 0, 9)T Z=975第六十五張，PPT共一百零一頁，創(chuàng)作于2022年6月66幾點說明：(1)、例 minZ=-X1 -2X2X1 4X2 3X1+2X2 8 X1 , X2 0 X1 +X3 = 4 X2 +X4 = 3X1+2X2 +X5= 8 X1 ， ，X5 0第六十六張，PPT共一百零一頁，創(chuàng)作于2022年6月67 X1 X2 X3 X4 X5Z 0 1 2 0 0 0X3 4 1 0 1 0

32、 0X4 3 0 (1) 0 1 0X5 8 1 2 0 0 1Z -6 1 0 0 -2 0X3 4 1 0 1 0 0 X2 3 0 1 0 1 0 X5 2 (1) 0 0 -2 1 (接下表)第六十七張，PPT共一百零一頁，創(chuàng)作于2022年6月68 X1 X2 X3 X4 X5 Z -8 0 0 0 0 -1X3 2 0 0 1 (2) -1X2 3 0 1 0 1 0X1 2 1 0 0 -2 1Z -8 0 0 0 0 -1X4 1 0 0 1/2 1 -1/2 X2 2 0 1 -1/2 0 1/2 X1 4 1 0 1 0 0 非基變量檢驗數(shù)為0第六十八張，PPT共一百零一頁，

33、創(chuàng)作于2022年6月69X(1)= (2,3) Z(1)=-8 X(2)= (4,2) Z(2)=-8無窮多解全部解：X= + (1-) (0 1)2 4 3 2第六十九張，PPT共一百零一頁，創(chuàng)作于2022年6月70(2)、3X1+4X2 64X1+ X2 23X1 +2X2 3X1 , X2 0Min Z=-10X1-12X2 X1 X2 X3 X4 X5Z 0 10 12 0 0 0X3 6 3 (4) 1 0 0X4 2 4 1 0 1 0X5 3 3 2 0 0 1第七十張，PPT共一百零一頁，創(chuàng)作于2022年6月71 X1 X2 X3 X4 X5 z 0 10 12 0 0 0 i

34、 X3 6 3 (4) 1 0 0 3/2 X4 2 4 1 0 1 0 2/1 X5 3 3 2 0 0 1 3/2 z -18 1 0 -3 0 0 i X2 3/2 3/4 1 1/4 0 0 2 X4 1/2 13/4 0 -1/4 1 0 2/13 X5 0 (3/2) 0 -1/2 0 1 0 z -18 0 0 -8/3 0 -2/3 X2 3/2 0 1 1/2 0 -1/2 X4 1/2 0 0 5/6 1 -13/6 X1 0 1 0 -1/3 0 2/3第七十一張，PPT共一百零一頁，創(chuàng)作于2022年6月72退化解X *=(0, 3/2, 0, 1/2, 0)TZmin=

35、-18第七十二張，PPT共一百零一頁，創(chuàng)作于2022年6月73 X1 X2 X3 X4 X5Z 0 4 1 0 0 0X3 2 -1 1 1 0 0X4 4 (1) -4 0 1 0X5 8 1 -2 0 0 1(3)例：minZ= -4X1 -X2 -X1+ X2 2 X1 -4X2 4 X1 -2X2 8X1 , X2 0第七十三張，PPT共一百零一頁，創(chuàng)作于2022年6月74Z -16 0 17 0 -4 0X3 6 0 -3 1 1 0X1 4 1 -4 0 1 0X5 4 0 (2) 0 -1 1z - 50 0 0 0 9/2 -17/2X3 12 0 0 1 -1/2 3/2X1

36、 12 1 0 0 -1 2X2 2 0 1 0 -1/2 1/2 第七十四張，PPT共一百零一頁，創(chuàng)作于2022年6月75本問題無界。X1X2OZ=0Z= -4X1 -X2 X1 -2X2 8-X1+ X2 2 X1 -4X2 4 第七十五張，PPT共一百零一頁，創(chuàng)作于2022年6月76一、兩階段法：原問題 minZ= Cj xj j=1nxj 0j=1naij xj =bi 0 ( i=1,2, ,m)作輔助問題minW= yi i=1mxj ， yi 0j=1naij xj + yi =bi ( i=1,2, ,m)2.4 初始解第七十六張，PPT共一百零一頁，創(chuàng)作于2022年6月77第

37、1階段 最優(yōu)基B* min = *(1)、 *0 (2)、 * =0 yi 0( i=1,2, ,m) B* 基變量無人工變量 B* 基變量含人工變量yr 單純形表中， yr+ark yk +arj xj =0 () k Jj JJ：非基變量下標集合, 判定原問題無可行解。第七十七張，PPT共一百零一頁，創(chuàng)作于2022年6月781) arj 全 =0 () 式多余方程2) arj 有0 元，設(shè)為ars 0 以ars為主元，換基迭代，最后得到第七十八張，PPT共一百零一頁，創(chuàng)作于2022年6月79maxZ= -X1 +2X2 X1 +X2 2-X1 +X2 1 X2 3X1 X2 0例1：min

38、Z= X1 - 2X2 minW=X6 +X7 X1 +X2 -X3 +X6 =2-X1 +X2 -X4 +X7 =1 X2 +X5 =3X1 X7 0 X1 +X2 -X3 =2-X1 +X2 -X4 =1 X2 +X5 =3X1 X5 0第一階段：求第七十九張，PPT共一百零一頁，創(chuàng)作于2022年6月80 0 0 0 0 0 -1 -1 X1 X2 X3 X4 X5 X6 X7 W 3 0 2 -1 -1 0 0 0 X6 2 1 1 -1 0 0 1 0 X7 1 -1 (1) 0 -1 0 0 1 X5 3 0 1 0 0 1 0 0 W 1 +2 0 -1 1 0 0 -2 X6 1

39、 (2) 0 -1 1 0 1 -1 X2 1 -1 1 0 -1 0 0 1 X5 2 1 0 0 1 1 0 -1 W 0 0 0 0 0 0 -1 -1 X1 1/2 1 0 -1/2 1/2 0 1/2 -1/2 X2 3/2 0 1 -1/2 -1/2 0 1/2 1/2 X5 3/2 0 0 1/2 1/2 1 -1/2 -1/2 第八十張，PPT共一百零一頁，創(chuàng)作于2022年6月81 -1 2 0 0 0 X1 X2 X3 X4 X5 z -5/2 0 0 1/2 3/2 0 X1 1/2 1 0 -1/2 (1/2) 0 X2 3/2 0 1 -1/2 -1/2 0 X5 3/

40、2 0 0 1/2 1/2 1 z -4 -3 0 2 0 0 X4 1 2 0 -1 1 0 X2 2 1 1 -1 0 0 X5 1 -1 0 (1) 0 1 z - 6 -1 0 0 0 -2 X4 2 1 0 0 1 1 X2 3 0 1 0 0 1 X3 1 -1 0 1 0 1第二階段第八十一張，PPT共一百零一頁，創(chuàng)作于2022年6月82例2：maxZ= 2X1 +X2 5X1 +10X2 82X1 +2X2 1X1 ，X2 0minZ= -2X1 -X2 第(1)階段：minW= X55X1 +10X2 -X3 +X5 =82X1 +2X2 +X4 =1X1 X5 0第八十二張

41、，PPT共一百零一頁，創(chuàng)作于2022年6月83 0 0 0 0 -1 X1 X2 X3 X4 X5 W 8 5 10 -1 0 0X5 8 5 10 -1 0 1X4 1 2 (2) 0 1 0W 3 -5 0 -1 -5 0X5 3 -5 0 -1 -5 1X2 1/2 1 1 0 1/2 0第八十三張，PPT共一百零一頁，創(chuàng)作于2022年6月84X2X1O5X1 +10X2 82X1 +2X2 1X1 ，X2 05X1 +10X2 810X1 +10X2 5X1 ，X2 0第八十四張，PPT共一百零一頁，創(chuàng)作于2022年6月85例3、求minZ= +4X1 +3X3 1/2X1 +X2+1

42、/2X3-2/3X4 = 23/2X1 +3/4X3 =33X1 -6X2 +4X4 = 0X1 , X2 , X3 , X4 0滿足第八十五張，PPT共一百零一頁，創(chuàng)作于2022年6月86 0 0 0 0 -1 -1 -1 X1 X2 X3 X4 y1 y2 y3 W 5 5 -5 5/4 10/3 0 0 0 y1 2 1/2 1 1/2 -2/3 1 0 0 y2 3 3/2 0 3/4 0 0 1 0 y3 0 3 -6 0 4 0 0 1 W 5 0 5 5/4 -10/3 0 0 -5/3 y1 2 0 2 1/2 -4/3 1 0 -1/6 y2 3 0 3 3/4 -2 0 1

43、 -1/2 X1 0 1 -2 0 4/3 0 0 1/3第 一 階 段 一二第八十六張，PPT共一百零一頁，創(chuàng)作于2022年6月87 W 0 0 0 0 0 -5/2 0 -5/4 X2 1 0 1 1/4 -2/3 1/2 0 -1/2 y2 0 0 0 0 0 -3/2 1 -1/4 X1 2 1 0 1/2 0 1 0 1/6第一階段三 -4 0 -3 0 X1 X2 X3 X4 Z 8 0 0 -1 0 X2 1 0 1 1/4 -2/3 X1 2 1 0 1/2 0第二階段第八十七張，PPT共一百零一頁，創(chuàng)作于2022年6月88例4、求minZ=4X1 +3X31/2X1 +X2

44、+1/2X3 -2/3X4 =23/2X1 -1/2X3 =33X1 -6X2 +4X4 =0X1 , X2 , X3 , X4 0滿足第八十八張，PPT共一百零一頁，創(chuàng)作于2022年6月89 0 0 0 0 -1 -1 -1 X1 X2 X3 X4 y1 y2 y3 W 5 5 - 5 0 10/3 0 0 0 y1 2 1/2 1 1/2 -2/3 1 0 0 y2 3 3/2 0 -1/2 0 0 1 0 y3 0 3 -6 0 4 0 0 1 W 5 0 5 0 -10/3 0 0 -5/3 y1 2 0 2 1/2 -4/3 1 0 -1/6 y2 3 0 3 -1/2 -2 0 1 -1/2 X1 0 1 -2 0 4/3 0 0 1/3第 一 階 段 一二第八十九張，PPT共一百零一頁，創(chuàng)作于2022年6月90第 一 階 段 W 0 0 0 -5/4 0 -5/2 0 -5/4 X2 1 0 1 1/4 -2/3 1/2 0 -1/12 y2 0 0 0 -5/4 0 -3/2 1 -1/4 X1 2 1 0 1/2 0 1 0 1