【文章內(nèi)容簡介】 +x4≤8 2x1+x2 ≤6 x2 + x3 +x4≤6 x1 + x2 +x3 ≤9 xj≥0（ j=1,2,3,4） 附 練習答案： y1=4/5, y2=3/5, y3=1, y4=0 已知原問題的最優(yōu)解為 :X*=(2,2,4,0)T，試根據(jù)互補松弛定理解出其對偶問題的最優(yōu)解。 線性規(guī)劃問題的對偶問題為： =8y1+6y2+6y3+9y4 . y1+2y2 +y4 ≥ 2 3y1+y2 + y3 +y4 ≥ 4 y3 +y4 ≥ 1 y1 +y3 ≥ 1 yj≥0（ j=1,2,3,4） 對偶線性規(guī)劃 30 ④ 為嚴格不等式，由互補松弛定知，必有 y4 = 0； Max Z=2x1+4x2+x3+x4 . x1+3x2 +x4≤8 2x1+x2 ≤6 x2 + x3 +x4≤6 x1 + x2 +x3 ≤9 xj≥0（ j=1,2,3,4） ① 8=8 ② 6=6 ③ 6=6 ④ 89 解之，有： y1=4/5, y2=3/5, y3=1， y4 = 0 答案：因為原問題的最優(yōu)解為 :X*=(2,2,4,0)T ： 又因 x1, x2 , x3＞ 0，故對偶問題的前三個約束必為緊約束 線性規(guī)劃問題的對偶問題為： MinS=8y1+6y2+6y3+9y4 . y1+2y2 +y4 ≥ 2 3y1+y2 + y3 +y4 ≥ 4 y3 +y4 ≥ 1 y1 +y3 ≥ 1 yj≥0（ j=1,2,3,4） y1+2y2 = 2 3y1+y2 + y3 = 4 y3 = 1 等號 對偶線性規(guī)劃 maxZ=16=minS 得對偶問題的最優(yōu)解 Y*=(4/5,3/5,1,0) minS=16 31 【 練習 】 已知線性規(guī)劃問題 ?????????????????????????4321214321432314321,2 6332 2 6863 m i nxxxxxxxxxxxxxxxxxxxz（ 1）寫出對偶問題； （ 2）已知原問題的最優(yōu)解為 X*=（ 2， 0， 1， 1） T，求對偶問題的最優(yōu)解。 對偶線性規(guī)劃 32 問題：可否用單純型法求解原問題的同時求對偶問題的解 結(jié)論：用單純形法求解線性規(guī)劃時 ， 迭代的每一步在得到原問題一個 基本可行解 的同時 ， 其： 線性規(guī)劃原問題及其對偶問題之間存在一對互補的基解 ，其中 原問題的松馳變量 對應(yīng) 對偶問題的原變量 ， 對偶問題的剩余變量 對應(yīng) 原問題的原變量 ；這些互相對應(yīng)的變量如果在一個問題的解中是 基變量 ， 則在另一問題的解中 是非基變量 ；將這兩個解代入各自的目標數(shù)中有 z=w。 注：證明過程參見教材 60頁性質(zhì) 6證明 檢驗數(shù)行的 (cjzj)值是其對偶問題的一個 基本解 yi ； 定理 7 對偶線性規(guī)劃 33 ?用單純形法同時求解 原問題 和 對偶問題 原問題是： maxZ=2x1 +x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0 原問題的標準型是： maxZ=2x1 +x2+0x3+0x4 +0x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi ≥0 對偶線性規(guī)劃 34 Cj 比 值 CB XB b 檢驗數(shù) ?j x1 x2 x3 x4 x5 2 1 0 0 0 15 0 5 1 0 0 24 6 2 0 1 0 5 1 1 0 0 1 x3 x4 x5 0 0 0 0 2 1 0 0 0 maxZ=2x1 +x2+0x3+0x4 +0x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi ≥0 24/6=4 5/1=5 原問題變量 原問題松馳變量 對偶問題剩余變量 y y5 對偶問題變量 y y2 、 y3 得原問題可行解 :X=(0,0,15,24,5)T 對偶問題解 :Y*=(0,0,0,2,1)T 檢驗數(shù)行的 － (cjzj)值是其對偶問題的一個 基本解 yi ； 對偶線性規(guī)劃 35 檢驗數(shù) ?j 15 0 5 1 0 0 4 1 1/3 0 1/6 0 1 0 2/3 0 1/6 1 x3 x1 x5 0 2 0 8 0 1/3 0 1/3 0 3 12 得原問題可行解 :X=(4,0,15,0,1)T，此時 Z=8 同時得對偶問題基礎(chǔ)解 :Y*=(0,1/3,0, 0,1/3)T， W=8 對偶問題剩余變量 y y5 對偶問題變量 y y2 、 y3 原問題變量 原問題松馳變量 檢驗數(shù)行的 (cjzj)值是其對偶問題的一個 基本解 yi ； 對偶線性規(guī)劃 36 變換單純形表 Cj 比 值 CB XB b 檢驗數(shù) ?j= cjzj x1 x2 x3 x4 x5 2 1 0 0 0 15/2 0 0 1 5/4 15/2 7/2 1 0 0 1/4 1/2 3/2 0 1 0 1/4 3/2 x3 x1 x2 0 2 1 17/2 0 0 0 1/4 1/2 此時得原問題最優(yōu)解 :X*=(7/2,3/2,15/2,0,0)T， Z*=17/2 原問題變量 原問題松馳變量 對偶問題剩余變量 y y5 對偶問題變量 y y2 、 y3 則對偶問題最優(yōu)解 :Y*=(0,1/4,1/2,0,0)T， S*=17/2 檢驗數(shù)行的 (cjzj)值是其對偶問題的一個 基本解 yi ； 對偶線性規(guī)劃 37 【 又例 】 用單純形法同時求解 原問題 和 對偶問題 maxZ= 100 x1 + 80 x2 2 x1+4 x2≤ 80 3 x1+ x2≤ 60 x1, x2 ≥0 將線性規(guī)劃問題標準化 maxZ= 100 x1 + 80 x2 + 0 x3 + 0 x4 2 x1+4 x2 + x3 = 80 3 x1+ x2 + x4 =60 x1, x2 x3 x4 ≥0 對偶線性規(guī)劃 38 0 0 0 80 100 Z 60 1 0 1 3 0 80 0 1 4 2 0 此時得原問題的最優(yōu)解： X0=(16,12,0,0)T , maxZ=2560 初等變換 2022 100/3 0 140/3 0 Z 20 1/3 0 1/3 1 0 40 2/3 1 10/3 0 0 2 x1+ 4 x2 + x3 = 80 3 x1+ x2 + x4 =60 Z+100 x1 + 80 x2 + 0 x3 + 0 x4=0 ～ ～ 2560 24 14 0 0 Z 16 2/5 1/10 0 1 0 12 1/5 3/10 1 0 0 Z x1 x2 x3 x4 b 同時得對偶問題的最優(yōu)解： y1=14,y2 =24,y3 =0,y4 =0,即 Y0=(14,24,0,0)T , minS=2560 對偶線性規(guī)劃 39 對偶單純形方法 原問題是： 原問題的標準型是： minZ=15y1+24y2+5y3 6y2+y3 ≥ 2 5y1 +2y2 +y3 ≥1 y1 , y2 , y3 ≥ 0 maxw’= 15y124y25y3 +0y4 +0y5 6y2+y3 y4 = 2 5y1 +2y2 +y3 y5 =1 y1 , y2 , y3 , y4 , y5 ≥ 0 利用單純形法： maxw’= 15y124y25y3 +0y4 +0y5My6My7 6y2+y3 y4 +y6 = 2 5y1 +2y2 +y3 y5 +y7 =1 y1 , y2 , y3 , y4 , y5 , y6 , y7≥ 0 對偶線性規(guī)劃 40 一、 用對偶單純形方法解線性規(guī)劃 對偶單純形方法 是使用對偶原理求解原問題解的一種方法，而不是求解對偶問題解的單純形方法。與對偶單純形方法相對應(yīng)，原已有的單純形方法稱 原始單純形方法 。 對偶線性規(guī)劃 41 【 例 】 用對偶單純形方法解下述線性規(guī)劃問題 原問題是： 原問題的標準型是： minZ=15y1+24y2+5y3 6y2+y3 ≥ 2 5y1 +2y2 +y3 ≥1 y1 , y2 , y3 ≥ 0 maxw’= 15y124y25y3 +0y4 +0y5 6y2+y3 y4 = 2 5y1 +2y2 +y3 y5 =1 y1 , y2 , y3 , y4 , y5 ≥ 0 maxw’= 15y124y25y3 +0y4 +0y5 6y2 y3 + y4 = 2 5y1 2y2 y3 + y5 = 1 y1 , y2 , y3 , y4 , y5 ≥ 0 對偶單純形方法 對偶線性規(guī)劃 42 Cj 比 值 CB XB b 檢驗數(shù) ?j y1 y2 y3 y4 y5 15 24 5 0 0 2 0 6 1 1 0 1 5 2 1 0 1 y4 y5 0 0 0 15 24 5 0 0 檢驗數(shù) ?j 1/3 0 1 1/6 1/6 0 1/3 5 0 2/3 1/3 1 y2 y5 24 0 8 15 0 1 4 0 maxw’= 15y124y25y3 +0y4 +0y5 6y2 y3 + y4 = 2 5y1 2y2 y3 + y5 = 1 y1 , y2 , y3 , y4 , y5 ≥ 0 檢驗