2022年《運籌學》知識點總結(jié)

1、1.用圖解法求解下列線性規(guī)劃問題，并指出問題具有惟一最優(yōu)解、無窮多最優(yōu)解、無界解還是 無可行解。maxzx 1x26x 110 x21205x 1103x282.將下述線性規(guī)劃問題化成標準形式。minz3x 14x22x35x44x 1x 22x 3x42（1）x 12x23x32x4x142x 1x34x 4 5x 4 x 2x ,1x,2x 30,x4 無約束解：令zz，x4xx44maxz 3x 14x22x 354x 1x22x 3xx 4 2144x 1x2x 32x 4 2x 4 x 52x 13x2x 3x 4 x 4 x 62x 1,x 2,x 3,x 4 ,x 4 ,x5,x

2、603.分別用圖解法和單純形法求解下述線性規(guī)劃問題，并對照指出單純形表中的各基可行解對應圖解法中的可行域的哪個頂點。maxz10 x 195 x23x 14x 25x 12x 28x 1,x 20解：圖解法：單純形法：將原問題標準化：maxz10 x 15x 2910 5 0 0 3 對應圖解法3 x 14x 2x35x 12x 2x 48x 1,x 2,x 3,x 40CjCBB b x 1x 2x 3x4中的點0 x 39 3 4 1 0 0 x 48 5 2 0 1 8/5 O 點0 j 0 10 5 0 0 3/2 C 點x 321/5 0 14/5 1 -3/5 10 x 18/5

3、1 2/5 0 1/5 4 5 j-16 0 1 0 -2 B 點x 23/2 0 1 5/14 -3/14 10 x 11 1 0 -1/7 2/7 j35/2 0 0 -5/14 -25/14 最優(yōu)解為（ 1,3/2,0,0），最優(yōu)值 Z=35/2。單純型法步驟：轉(zhuǎn)化為標準線性規(guī)劃問題；找到一個初始可行解，列出初始單純型表；最優(yōu)性檢驗，求 cj-zj，若所有的值都小于 0，則表中的解便是最優(yōu)解，否則，找出最大的值的那一列，求出 bi/aij，選取最小的相對應的 xij ，作為換入基進行初等行變換，重復此步驟。4.寫出下列線性規(guī)劃問題的對偶問題。m nmin z c ij x iji 1 j

4、 1nx ij a i i ,1 , mj 1（1）ms . t . x ij b j j ,1 , ni 1x ij 0 i 1 , , m ; j ,1 , nm nmax w a i y i b j y j mi 1 i 1y i y m j c ij i ,1 , m ; j ,1 , ns . t .x i , y j 無約束nmax z c j x jj 1n（2）s . t.j1aijxjb ij,1i,1m 1m 1m2 ,mnaijxjb iim 1,1j10n 1nxjxj無約束jn 1,1,nmminwi1b iyimi1aijyicjj,12 ,n1nms . t .i

5、aijyicj,1 2,jn 1,1m,n1yi0im 1m 1myi無約束i,1,5. 給出線性規(guī)劃問題X*2,2 ,40,T，試根據(jù)對偶理論，直maxz2x 14x 2x 3x 4x 13 x 2x 482 x 1x 26s . t.x2x3x46x 1x 2x 39xj0j,14要求：（1）寫出其對偶問題； （2）已知原問題最優(yōu)解為接求出對偶問題的最優(yōu)解。解：minw8y 16y 26y 39y4min w=28，y 12y2y42（1）s .3y 1y2y 3y 44y3y 41y 1y31yj0j,14（2）因為x 1,x2,x30，第四個約束取等號，根據(jù)互補松弛定理得：y 12y2

6、y 423y 1y2y 3y44y3y 41y 40求得對偶問題的最優(yōu)解為：Y*4,31, 0,，最優(yōu)值 min w=16 。55例 已知原問題 Max z =x1 + 2 x2 + 3 x3 + 4 x4x 1 + 2x 2 +2 x 3 +3 x 420 2x 1 + x 2 +3x 3 +2x 4 20 x 1、 x 2、 x 3 、 x 4 0和對偶問題Min w =20y 1 + 20 y2 y 1 + 2 y 21 2y 1 + y 22 2y 1 + 3 y 23 3y 1 + 2 y 24 y 1、 y 2 0已知對偶問題的最優(yōu)解 求原問題的最優(yōu)解及最優(yōu)值。y 1 = 1.2

7、、 y 2 =0.2 ，最優(yōu)值可用如下方法求解：引入將原問題和對偶問題化為標準形式。Max z =x1 +2x2 +3x3 +4x4和x1 + 2x2 + 2x3 + 3x4 + x5 = 20 2x1 + x2 + 3x3 + 2x4 + x6 =20 x1、x2、x3 、x4 、x5 、x6 0Min w =20y 1 + 20y2 y1 +2y2 y3 = 1 2y1 + y2 y4 = 2 2y1 + 3y2 y5 = 3 3y1 +2y2 y6 = 4 y1、y2 、y3 、 y4 、y5 、 y6 0（1） y1=1.20，而 y1與x5中至少有一個為零，故 x5 =0。（2）同理

8、， y2=0.20，所以 x6=0。（3）對偶問題的第一個約束條件在取最優(yōu)值時 y1+2y2=1.2+2 0.2=1.61這就表示該約束條件的松弛變量：y3=1.61=0.60 y3與x1中至少有一個為零，故 x1=0。（4）同理，對于第 2個約束條件在取得最優(yōu)值時 2y1+y2= 2 1.2+0.2=2.62y4=2.62=0.60y4與x2中至少有一個為零，故 x2=0。（5）同理，對于第 3個約束條件在取得最優(yōu)值時2y1+3y2= 2 1.2+ 3 0.2=3y5=3 3=0y5與x3中至少有一個為零，故 x30或者 x3=0 。（6）對于第 4個約束條件的分析也可得到x40 或者 x4

9、=0 。對于（ 5） 和（ 6）的分析，對于確定原問題的最優(yōu)解沒有 任何幫助。但從（ 1）到（ 4）的分析中得知，原問題取得 最優(yōu)解時：x5=0，x6=0，x1=0， x2=0 代入原問題的約束方程組得：2x3+3x4= 20 3x3+2x4= 20 解此方程組，可求得原問題的最優(yōu)解為：x1=0， x2=0 ，x3=4 ， x4=4 ，x5=0，x6=0弱對偶性的推論：(1) 原問題任一可行解的目標函數(shù)值是其對偶問題目標函數(shù)值的下界；題任一可行解的目標函數(shù)值是其原問題目標函數(shù)值的上界反之對偶問(2) 如原問題有可行解且目標函數(shù)值無界( 具有無界解 ) ，則其對偶問題無可行解；反之對偶問題有可行

10、解且目標函數(shù)值無界，則其原問題無可行解。注意：本點性質(zhì)的逆不成立，當對偶問題無可行解時，其原問題或具有無界解或無 可行解，反之亦然。(3) 若原問題有可行解而其對偶問題無可行解，則原問題目標函數(shù)值無界；反之對 偶問題有可行解而其原問題無可行解，則對偶問題的目標函數(shù)值無界。強對偶性 ( 或稱對偶定理 ) 若原問題及其對偶問題均具有可行解，則兩者均具有最優(yōu)解，且它們最優(yōu)解的 目標函數(shù)值相等?；パa松弛性 在線性規(guī)劃問題的最優(yōu)解中，如果對應某一約束條件的對偶變量值為非零，則 該約束條件取嚴格等式；反之如果約束條件取嚴格不等式，則其對應的對偶變量一 定為零。影子價格 資源的市場價格是其價值的客觀體現(xiàn)，相

11、對比較穩(wěn)定，而它的影子價格則有賴于資 源的利用情況，是未知數(shù)。因企業(yè)生產(chǎn)任務、產(chǎn)品結(jié)構(gòu)等情況發(fā)生變化，資源的影 子價格也隨之改變。影子價格是一種邊際價格。資源的影子價格實際上又是一種機會成本。隨著資源的買進賣出，其影子價格也將 隨之發(fā)生變化，一直到影子價格與市場價格保持同等水平時，才處于平衡狀態(tài)。生產(chǎn)過程中如果某種資源未得到充分利用時，該種資源的影子價格為零；又當資源的影子價格不為零時，表明該種資源在生產(chǎn)中已耗費完畢。影子價格反映單純形表中各個檢驗數(shù)的經(jīng)濟意義。一般說對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案，而對于對偶問題的求解則是確定對資源的恰當估價，這種估價直接涉及資源的最有效利用對偶

12、單純型法： 轉(zhuǎn)化成標準的線性規(guī)劃問題；確定換入基變量， bi 小于 0 中的最小的那一排，再求（ cj-zj）/aij，且 aij0,d+,d-0 目標規(guī)劃的圖解法： 先畫絕對約束的可行域， 然后按照優(yōu)先性優(yōu)先考慮某個目標約束，隨著 最合適的那條，直到最后10.用割平面法解下列整數(shù)規(guī)劃：（1）maxzx 1x22x 1x26s .4x 15 x220 x 1,x2,0且為整數(shù)min 系數(shù)中 d+或者 d- 的增大移動曲線，畫出解：引進松弛變量x3, x4，將問題化為標準形式，用單純形法解其松弛問題。0 3 cj1 1 0 CBX Bb x1x 2x 3x 40 x 36 【2】1 1 0 0

13、x 420 4 5 0 1 5 j1 1 0 0 6 1 x 13 1 1/2 1/2 0 0 x 48 0 【 3】-2 1 8/3 j0 1/2 -1/2 0 1 x 15/3 1 1 x 28/3 0 j0 找出非整數(shù)解變量中分數(shù)部分最大的一個基變量（0 5/6 -1/6 1 -2/3 1/3 0 -1/6 -1/6 x2），并寫下這一行的約束：x22x 31x 422333將上式中的所有常數(shù)分寫成整數(shù)與一個正的分數(shù)值之和得：x211x301x422333將上式中的分數(shù)項移到等式右端，整數(shù)項移到等式左端得：x2x3221x 321x40 0 333得到割平面約束為：x41x313332引

14、入松弛變量x ，得割平面方程為：1x 31x4x 5333cj1 1 0 CBX Bb x1x 2x 3x 4x51 x 15/3 1 0 5/6 -1/6 0 1 x 28/3 0 1 -2/3 1/3 0 0 x 5-2/3 0 0 【-1/3】-1/3 1 j0 0 -1/6 -1/6 0 j/arj0 1/2 1/2 5/2 1 x 10 1 0 -1 1 x 24 0 1 0 1 -2 0 x 32 0 0 1 1 -3 j0 0 0 0 -1/2 最優(yōu)解為X*0 ,4 ,200,T，最優(yōu)值為max z44=0，最優(yōu)解不唯一？11.用分支定界法解下列整數(shù)規(guī)劃max z 2 x 1 x

15、 2x 1 x 2 5（1）x 1 x 2 06 x 1 2 x 2 21x 1 , x 2 ,0 且為整數(shù)解：最優(yōu)解（ 3,1），最優(yōu)值 z=7。12.匈牙利解法：見課本145 頁v 到9v 的最短路。13.如圖，v 是一倉庫，v 是商店，求一條從解：v0v1v23vv4v56vv7v8v9P=T=0 T=T=T=T=T=T=T=T=T=P=T=2 T=T=11 T=T=7 T=T=4 T=T=T=13 T=11 T=T=7 T=P=T=4 T=T=T=13 T=11 T=P=T=7 T=11 T=13 T=T=13 P=T=11 T=T=11 T=13 T=T=13 T=16 P=T=11 T=13 T=P=T=13 T=16 T=13 T=20 T=16 P=T=13 T=19 P=T=16 T=19 P=19 最短路長為 19。最短路為： 0129，0329，0349，01249，0789。14.如圖，發(fā)點 1s ，s 分別可供應 10 和 15 個單位，收點 1t ，2t 可以接收 10 和 25 個單位，求最