運(yùn)籌學(xué)第2章對(duì)偶理論習(xí)題自然科學(xué)

1/1運(yùn)籌學(xué)-第2章-對(duì)偶理論習(xí)題-自然科學(xué)

其次章線性規(guī)劃的對(duì)偶理論

2.1寫出下列線性規(guī)劃問題的對(duì)偶問題

maxz=2x1+2x2－4x3

x1+3x2+3x3≤304x1+2x2+4x3≤80x1、x2，x3≥0

解：其對(duì)偶問題為

minw=30y1+80y2y1+4y2≥23y1+2y2≥23y1+4y2≥－4y1、y2≥0

2.2寫出下列線性規(guī)劃問題的對(duì)偶問題

minz=2x1+8x2－4x3

x1+3x2－3x3≥30－x1+5x2+4x3=804x1+2x2－4x3≤50

x1≤0、x2≥0，x3無限制

解：其對(duì)偶問題為

maxw=30y1+80y2+50y3y1－y2+4y3≥23y1+5y2+2y3≤8－3y1+4y2－4y3=－4

y1≥0，y2無限制，y3≤0

2.3已知線性規(guī)劃問題

maxz=x1+2x2+3x3+4x4

x1+2x2+2x3+3x4≤202x1+x2+3x3+2x4≤20x1、x2，x3，x4≥0

其對(duì)偶問題的最優(yōu)解為y1*=6/5，y2*=1/5。試用互補(bǔ)松弛定理求該線性規(guī)劃問題的最優(yōu)解。

解：其對(duì)偶問題為

minw=20y1+20y2

y1+2y2≥1（1）2y1+y2≥2（2）2y1+3y2≥3（3）3y1+2y2≥4（4）y1、y2≥0

將y1*=6/5，y2*=1/5代入上述約束條件，得（1）、（2）為嚴(yán)格不等式；由互補(bǔ)松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原問題的兩個(gè)約束條件應(yīng)取等式，所以

2x3*+3x4*=203x3*+2x4*=20

解得x3*=x4*=4。故原問題的最優(yōu)解為X*=（0，0，4，4）T

2.4用對(duì)偶單純形法求解下列線性規(guī)劃

minz=4x1+2x2+6x3

2x1+4x2+8x3≥244x1+x2+4x3≥8x1、x2，x3≥0

解將問題改寫成如下形式

max（－z）=－4x1－2x2－6x3

－2x1－4x2－8x3+x4=－24－4x1－x2－4x3+x5=－8x1、x2，x3，x4，x5≥0

明顯，p4、p5可以構(gòu)成現(xiàn)成的單位基，此時(shí)，非基變量在目標(biāo)函數(shù)中的系數(shù)全為負(fù)數(shù)，因此p4、p5構(gòu)成的就是初始正側(cè)基。整個(gè)問題的計(jì)算過程列在表2—7中。

表2—7CjCB00θ-20θx2x5－zXBx4x5－z－4x1-2-4-4-4/-21/2-7/2-3-3/(-7/2)－2x2[-4]-1-2-2/-41000－6x3-8-4-6-6/-102[-2]-2-2/-20x41000-1/4-1/4-1/2(-1/2)/(-1/4)0x501000100b-24-806-2-120-2-6x2x3－z-37/4-1/2100010-1/21/8-1/41-1/2-144-32最終一個(gè)單純形表中，已得到一個(gè)可行的正側(cè)解，因而得到問題的最優(yōu)解為X*=（0，4，4）T最優(yōu)值為z*=32

2.5設(shè)某線性規(guī)劃問題的初始單純形表和最優(yōu)單純形表分別為表2—9（初始單純形表）CjCB00XBx4x5－z5x11254x21143x31430x41000x5010b60800

表2—10（最優(yōu)單純形表）CjCB45XBx2x1－z5x10104x21003x3-23-40x42-1-30x5-11-1b4020-260現(xiàn)在要問：

（1）c3在什么范圍內(nèi)變化，表中最優(yōu)解不變？（2）c3從3變?yōu)?，求新的最優(yōu)解

解（1）由于在最優(yōu)單純形表中，c3為非基變量的價(jià)格系數(shù)，因此其變化僅會(huì)影響到檢驗(yàn)數(shù)σ3=－4，因此當(dāng)Δc3≤－σ3=4時(shí)，表中最優(yōu)解不變。

（2）當(dāng)c3從3變?yōu)?時(shí)，則表中的檢驗(yàn)數(shù)σ3從—4變?yōu)?，即表中的最優(yōu)解將發(fā)生變化，用單純形法求解得到如表2—11中所示的新的最優(yōu)解。

表2—11CjCB4545XBx2x1－zx2x35x10102/31/34x2100108x3-2[3]1010x42-1-34/3-1/30x5-11-1-1/31/3b4020-260160/320/3－z00-4-3-1-740/3即新的最優(yōu)解為X*=（0，160/3，20/3）T。2.6某工廠在方案期內(nèi)要支配甲、乙兩種產(chǎn)品，已知生產(chǎn)一件產(chǎn)品所消耗的A、B、C三種原材料的數(shù)量以及單位產(chǎn)品的利潤(rùn)如下表所示：表2—12單位原材料消耗產(chǎn)品甲1215乙3114資源限量（kg）908045ABC單位產(chǎn)品利潤(rùn)（千元/件）若x1、x2分別表示工廠生產(chǎn)甲、乙產(chǎn)品的數(shù)量，則使工廠獲得最大利潤(rùn)的生產(chǎn)方案數(shù)學(xué)模型為：

maxz=5x1+4x2

x1+3x2≤902x1+x2≤80x1+x2≤45x1、x2，x3≥0

用單純形法求解該問題時(shí)，其初始單純形表和最優(yōu)單純形表分別如表2—13和3—14所示，試分析使最優(yōu)基不變的b3的變化范圍。

表2—13（初始單純形表）CjCB000XBx3x4x5－z5x112154x231140x310000x401000x50010b9080450

表2—14（最優(yōu)單純形表）CjCB054XBx3x1x2－z5x101004x200100x310000x421-1-10x5-5-12-3b253510-215解由表2—13和表2—14可知，當(dāng)B=（p3，p1，p2）時(shí)，有

?1B?1???0?0?21?1?5???1?2??

?25??1Bb??35?10??????當(dāng)下式成立時(shí)，最優(yōu)基不變。

?25??1?1Bb?B?b??35?10???1?????0??0??21?1?5??0???1??0?2????b3??25?5?b3?????35??b3??10??b3??????0??

即25－5Δb3≥0，35－Δb3≥0，10+Δb3≥0解不等式有

－5≤Δb3≤5此外，以B-1的第三列各元素去除最優(yōu)單純形表中右端常數(shù)項(xiàng)對(duì)應(yīng)各列，用公式可直接求出Δb3，即

25??10??35max??,????b?min???

?5??2???1同樣可得－5≤Δb3≤5

因此，不影響最優(yōu)基的b3的變化范圍是[40，50]。

2.7在例2.11的生產(chǎn)方案問題中：（1）若生產(chǎn)產(chǎn)品甲的工藝結(jié)構(gòu)發(fā)生了改進(jìn)，

‘

這時(shí)關(guān)于它的技術(shù)向量變?yōu)閜1=（1，2，1/2）T，試分析對(duì)原最優(yōu)方案有什么影響；（2）若該廠除了生產(chǎn)前兩種產(chǎn)品外，擬開發(fā)新產(chǎn)品丙，已知產(chǎn)品丙每件消耗A、B、C原材料各為2、4、1kg，每件可獲利潤(rùn)8千元。問該廠是否應(yīng)當(dāng)生產(chǎn)該產(chǎn)品和生產(chǎn)多少？

解（1）由于產(chǎn)品甲生產(chǎn)工藝的改進(jìn)，這樣原最優(yōu)單純形表中的第1列將會(huì)發(fā)生轉(zhuǎn)變，