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