第03章對(duì)偶問(wèn)題與靈敏度分析

1、1第第3 3章章 對(duì)偶問(wèn)題與靈敏度分析對(duì)偶問(wèn)題與靈敏度分析3-1 3-1 線性規(guī)劃的對(duì)偶問(wèn)題概念線性規(guī)劃的對(duì)偶問(wèn)題概念3-2 3-2 建立對(duì)偶問(wèn)題的規(guī)則建立對(duì)偶問(wèn)題的規(guī)則3-3 3-3 對(duì)偶基本理論或性質(zhì)對(duì)偶基本理論或性質(zhì)3-4 3-4 線性規(guī)劃解法之三：線性規(guī)劃解法之三： 對(duì)偶單純形法對(duì)偶單純形法3-5 3-5 線性規(guī)劃的靈敏度分析線性規(guī)劃的靈敏度分析23-1 3-1 線性規(guī)劃的對(duì)偶問(wèn)題概念線性規(guī)劃的對(duì)偶問(wèn)題概念一、營(yíng)養(yǎng)配置問(wèn)題舉例一、營(yíng)養(yǎng)配置問(wèn)題舉例例例1 某養(yǎng)雞場(chǎng)所用的飼料由某養(yǎng)雞場(chǎng)所用的飼料由A、B、C三種配料組成，三種配料組成，下表給出了各種配料所含的營(yíng)養(yǎng)成份、單位成本以下表給出了各

2、種配料所含的營(yíng)養(yǎng)成份、單位成本以及及l(fā)份混合詞料必須含有的各種營(yíng)養(yǎng)成份。份混合詞料必須含有的各種營(yíng)養(yǎng)成份。3(1)問(wèn)如何配制混合詞料使成本最小？問(wèn)如何配制混合詞料使成本最小？(2)若有一個(gè)飼料廠制造含有這三種營(yíng)養(yǎng)成分的營(yíng)若有一個(gè)飼料廠制造含有這三種營(yíng)養(yǎng)成分的營(yíng)養(yǎng)養(yǎng)飼飼料，在料，在1份混合飼料中三種營(yíng)養(yǎng)丸的價(jià)格如何份混合飼料中三種營(yíng)養(yǎng)丸的價(jià)格如何制定才使其售價(jià)最大？制定才使其售價(jià)最大？4解解:(1)設(shè)設(shè)xj表示一份混合飼料中第表示一份混合飼料中第j種配料的含量，種配料的含量， j=A，B，C。則。則 min Z=6XA十十3XB十十2XC s.t. XA十十XB十十XC 20 1/2XA十十1/

3、2XB十十1/4XC 6 2XA十十XB十十XC 10 XA，XB，XC 0求解結(jié)果為：求解結(jié)果為：5 cj632000cBXBBx1x2x3x4x5x62x316001-2400 x610-100-1013x241101-40 zj cj zj333020-11-4400表中所有檢驗(yàn)數(shù)均不小于表中所有檢驗(yàn)數(shù)均不小于0，已達(dá)到最優(yōu)已達(dá)到最優(yōu) 最優(yōu)解為最優(yōu)解為X=(0,4,16,0,0,10)T Zmin=216+34=446(2)若有一個(gè)飼料廠制造含有這三種營(yíng)養(yǎng)成分為若有一個(gè)飼料廠制造含有這三種營(yíng)養(yǎng)成分為1個(gè)單個(gè)單位的營(yíng)養(yǎng)丸，在位的營(yíng)養(yǎng)丸，在1份混合飼料中三種營(yíng)養(yǎng)丸的價(jià)格如份混合飼料中三種營(yíng)養(yǎng)

4、丸的價(jià)格如何制定才使其售價(jià)最大？何制定才使其售價(jià)最大？解：解：(2)設(shè)設(shè)qi表示一份混合飼料中第表示一份混合飼料中第I種營(yíng)養(yǎng)丸的價(jià)格，種營(yíng)養(yǎng)丸的價(jià)格，i=D,E,F,則則max Z=20q1十十6q2十十10q3 s.t. q1十十1/2q2十十2q3 6 q1十十1/2q2十十q3 3 q1十十1/4q2十十q3 2 q1 ， q2 ， q3 0求解結(jié)果為：求解結(jié)果為：7 cj20610000cBqBBq1q2q3q4q5q60q430011-106q2401004-420q111010-12 zj cj zj2006020-10004- 416-16表中所有檢驗(yàn)數(shù)均不大于表中所有檢驗(yàn)數(shù)均不

5、大于0，已達(dá)到最優(yōu)已達(dá)到最優(yōu) 最優(yōu)解為最優(yōu)解為q=(0,4,16,0,0,10)T Zmax=64+201=448LP1與與LP2的關(guān)系：的關(guān)系：min Z=6XA十十3XB十十2XC s.t. XA十十XB十十XC 20 1/2XA十十1/2XB十十1/4XC 6 2XA十十XB十十XC 10 XA，XB，XC 0 max w=20q1十十6q2十十10q3 s.t. q1十十1/2q2十十2q3 20 q1十十1/2q2十十q3 3 q1十十1/4q2十十q3 2 q1 ， q2 ， q3 09 cj632000cBXBBx1x2x3x4x5x62x316001-2400 x610-100

6、-1013x241101-40 zj cj zj333020-11-4400 cj20610000cBqBBq1q2q3q4q5q60q430011-106q2401004-420q111010-12 zj cj zj2006020-10004- 416-1610關(guān)系：關(guān)系：兩個(gè)兩個(gè)LP問(wèn)題的最優(yōu)解的目標(biāo)函數(shù)值相同問(wèn)題的最優(yōu)解的目標(biāo)函數(shù)值相同用單純形法求解一個(gè)用單純形法求解一個(gè)LP問(wèn)題就知道另一問(wèn)題就知道另一個(gè)問(wèn)題的解個(gè)問(wèn)題的解二、對(duì)偶問(wèn)題的概念及實(shí)質(zhì)二、對(duì)偶問(wèn)題的概念及實(shí)質(zhì)1.對(duì)每一個(gè)對(duì)每一個(gè)LP問(wèn)題所伴隨著的另一個(gè)問(wèn)題所伴隨著的另一個(gè)LP問(wèn)問(wèn)題，就稱為對(duì)偶問(wèn)題；原來(lái)的題，就稱為對(duì)偶問(wèn)題；原

7、來(lái)的LP問(wèn)題就稱問(wèn)題就稱為原問(wèn)題為原問(wèn)題2.實(shí)質(zhì)：實(shí)質(zhì)：對(duì)偶問(wèn)題實(shí)質(zhì)上也是一個(gè)對(duì)偶問(wèn)題實(shí)質(zhì)上也是一個(gè)LP問(wèn)題問(wèn)題11 3-2 3-2 建立對(duì)偶問(wèn)題的規(guī)則建立對(duì)偶問(wèn)題的規(guī)則一、建立對(duì)偶問(wèn)題的規(guī)則一、建立對(duì)偶問(wèn)題的規(guī)則 (LP) Max z = c x (DP) Min w = bTq s.t. Ax b s.t. AT q cT x 0 q 0 “Max - ” “Min- ”121.注意原問(wèn)題與對(duì)偶問(wèn)題的決策變量的表示方式：注意原問(wèn)題與對(duì)偶問(wèn)題的決策變量的表示方式：Xj,qi分別表示原問(wèn)題、對(duì)偶問(wèn)題的決策變量分別表示原問(wèn)題、對(duì)偶問(wèn)題的決策變量2.將問(wèn)題變換為統(tǒng)一形式，其中將問(wèn)題變換為統(tǒng)一形式，

8、其中b可以為負(fù)數(shù)可以為負(fù)數(shù)原問(wèn)題原問(wèn)題“max ”對(duì)偶問(wèn)題對(duì)偶問(wèn)題“min ”原問(wèn)題原問(wèn)題“min ” 對(duì)偶問(wèn)題對(duì)偶問(wèn)題“max ”對(duì)偶問(wèn)題建立的規(guī)則；請(qǐng)同學(xué)們抄寫下來(lái)對(duì)偶問(wèn)題建立的規(guī)則；請(qǐng)同學(xué)們抄寫下來(lái)1，原問(wèn)題目標(biāo)函數(shù)求最大，原問(wèn)題目標(biāo)函數(shù)求最大或者最小或者最小，則所有的約束條件符號(hào)，則所有的約束條件符號(hào)統(tǒng)一成小于或者等于統(tǒng)一成小于或者等于大于或者等于大于或者等于2，原問(wèn)題一個(gè)行約束對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)變量，如果行約束為，原問(wèn)題一個(gè)行約束對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)變量，如果行約束為不等式，這個(gè)變量就大于等于零不等式，這個(gè)變量就大于等于零否則就沒(méi)有限制否則就沒(méi)有限制為自由變量為自由變量3，原問(wèn)題每個(gè)變

9、量的列向量對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)行約束，如果，原問(wèn)題每個(gè)變量的列向量對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)行約束，如果原問(wèn)題的變量大于等于零，則行約束小于等于零如果原問(wèn)題的原問(wèn)題的變量大于等于零，則行約束小于等于零如果原問(wèn)題的變量沒(méi)有限制，則行約束為等號(hào)。變量沒(méi)有限制，則行約束為等號(hào)。4原問(wèn)題目標(biāo)函數(shù)與對(duì)偶問(wèn)題目標(biāo)函數(shù)相反。原問(wèn)題目標(biāo)函數(shù)與對(duì)偶問(wèn)題目標(biāo)函數(shù)相反。136.對(duì)偶問(wèn)題的約束條件方程的右端值是原問(wèn)題目標(biāo)對(duì)偶問(wèn)題的約束條件方程的右端值是原問(wèn)題目標(biāo)函數(shù)中決策變量的系數(shù)函數(shù)中決策變量的系數(shù)Cj；7.原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系 xjqix1X2xn原始約束原始約束Min wq1a11a12a1nb1

10、q2a21a22a2nb2qmam1am2amnbm對(duì)偶約束對(duì)偶約束max zC1C2Cn14二、原問(wèn)題不符合建立規(guī)則的處理二、原問(wèn)題不符合建立規(guī)則的處理1.原問(wèn)題為原問(wèn)題為“max ”形式形式原問(wèn)題為原問(wèn)題為“max ”形式形式約束條件方程約束條件方程兩端乘以兩端乘以-12.原問(wèn)題為原問(wèn)題為“min ”形式形式原問(wèn)題為原問(wèn)題為“min ”形式形式約束條件方程約束條件方程兩端乘以兩端乘以-13.原問(wèn)題的每一個(gè)約束條件方程對(duì)應(yīng)對(duì)偶問(wèn)題的一原問(wèn)題的每一個(gè)約束條件方程對(duì)應(yīng)對(duì)偶問(wèn)題的一個(gè)決策變量個(gè)決策變量qi若第若第i個(gè)約束條件為不等式個(gè)約束條件為不等式,則限定則限定qi0若約束條件方程是若約束條件方

11、程是“=”形式形式:將將“=”變?yōu)樽優(yōu)椤啊焙秃汀啊眱蓚€(gè)約束條件方程兩個(gè)約束條件方程,在按照在按照1、2條處理?xiàng)l處理15例例2：根據(jù)下表寫出原問(wèn)題：根據(jù)下表寫出原問(wèn)題(max)與對(duì)偶問(wèn)題與對(duì)偶問(wèn)題(min)的的表達(dá)式表達(dá)式 xjqix1X2bq1128q24016qm0412Cj2316(1) min Z=2X1十十4X2十十3X3 s.t. X1十十2X23X3 5 2X1 3X2 2X33 X1十十X2十十X3 =2 X1，X2，X3 0(2) max Z=X1十十2X2十十3X3十十4X4 s.t. X1十十X2X3 3X4 =5 6X1十十7X2十十3X35X4 812X1 9X2 9X

12、3十十9X420 X1，X2，X3 ，X40例例3：建立下列：建立下列LP 問(wèn)題的對(duì)偶問(wèn)題問(wèn)題的對(duì)偶問(wèn)題17(3)沒(méi)有非負(fù)限制321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxxZ183-3 3-3 對(duì)偶基本理論或性質(zhì)對(duì)偶基本理論或性質(zhì)一、對(duì)稱性一、對(duì)稱性對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題二、二、弱對(duì)偶性弱對(duì)偶性若若 x, q x, q 分別為（分別為（LP) LP) 和（和（DPDP）的可行）的可行解，那么解，那么cx bcx bT Tq q推論推論三、三、最優(yōu)性準(zhǔn)則定理最優(yōu)性準(zhǔn)則定理若若x x, ,q q分別

13、分別(LP),(DP)(LP),(DP)的可行解的可行解, ,且且cxcx= =b bT Tq q，那么那么x x, ,y y分別為分別為(LP)(LP)和和(DP)(DP)的最優(yōu)解的最優(yōu)解19四、對(duì)偶定理四、對(duì)偶定理若若(LP)(LP)和和(DP)(DP)均可行均可行 那么那么(LP)(LP)和和(DP)(DP)均有最優(yōu)解均有最優(yōu)解, ,且最優(yōu)值相等且最優(yōu)值相等五、從一個(gè)問(wèn)題的最優(yōu)解單純形表中可五、從一個(gè)問(wèn)題的最優(yōu)解單純形表中可以得到另一個(gè)問(wèn)題的最優(yōu)解以得到另一個(gè)問(wèn)題的最優(yōu)解從從(LP)(LP)的最優(yōu)解單純形表中找的最優(yōu)解單純形表中找(DP)(DP)的最優(yōu)解：的最優(yōu)解：q qi i=|Z=|

14、Zn+in+i| n| n為為(LP)(LP)的實(shí)際決策變量數(shù)的實(shí)際決策變量數(shù)從從(DP)(DP)的最優(yōu)解單純形表中找的最優(yōu)解單純形表中找 (LP)(LP)的最優(yōu)的最優(yōu)解：解：X Xj j=|Z=|Zm+im+i| m| m為為(LP)(LP)的約束條件方程個(gè)數(shù)的約束條件方程個(gè)數(shù)六、互補(bǔ)松弛性六、互補(bǔ)松弛性若若X,qX,q分別是分別是(LP)(LP)和和(DP)(DP)的可行解，那么的可行解，那么qXqXs s=0=0和和q qs sX=0X=0，當(dāng)且僅當(dāng)，當(dāng)且僅當(dāng)X,qX,q為最優(yōu)解為最優(yōu)解20例例4 4：已知：已知LPLP問(wèn)題問(wèn)題max Z=xmax Z=x1 1+x+x2 2s.t. x

15、s.t. x1 1+x+x2 2+x+x3 322-2x-2x1 1+x+x2 2-x-x3 31 1 x x1 1,x,x2 2,x,x3 300試用對(duì)偶理論證明試用對(duì)偶理論證明上述上述LPLP問(wèn)題無(wú)最優(yōu)問(wèn)題無(wú)最優(yōu)解解例例5 5：已知：已知LPLP問(wèn)題問(wèn)題min Z=2xmin Z=2x1 1+3x+3x2 2 +5x+5x3 3+2x+2x4 4 +3x+3x5 5s.t. xs.t. x1 1+x+x2 2+2x+2x3 3 +x+x4 4 +3x+3x5 5 44 2x 2x1 1-x-x2 2+3x+3x3 3 +x+x4 4 +x+x5 5 3 3 x x1 1,x,x2 2,x,

16、x3 3 ,x,x4 4 ,x,x5 500已知其對(duì)偶問(wèn)題的最優(yōu)解為已知其對(duì)偶問(wèn)題的最優(yōu)解為q q1 1=4/5;q=4/5;q2 2=3/5;z=5.=3/5;z=5.試用對(duì)偶試用對(duì)偶理論找出原問(wèn)題的最優(yōu)解理論找出原問(wèn)題的最優(yōu)解21解：先寫出其對(duì)偶問(wèn)題：解：先寫出其對(duì)偶問(wèn)題： max w=4q1+3q2 q1+2q22 (1) q1 -q23 (2)2q1+3q25 (3) q1 +q22 (4)3q1 +q23 (5)將將q1,q2的值代入約束條的值代入約束條件，得件，得(2),(3),(4)為嚴(yán)格不為嚴(yán)格不等式；由互補(bǔ)松弛性等式；由互補(bǔ)松弛性qsx=0得得x2=0,x3=0,x4=0。又

17、因?yàn)橛忠驗(yàn)閝1,q20，由互補(bǔ)松弛，由互補(bǔ)松弛性性qxs=0得得xs1=0 ,xs2=0,j即原問(wèn)即原問(wèn)題的兩個(gè)約束條件應(yīng)取等式，題的兩個(gè)約束條件應(yīng)取等式，故有故有 x x1 1 +3x+3x5 5 =4=4 2x 2x1 1 +x+x5 5 =3=3求解得求解得x x1 1=1.x=1.x2 2=1=1故原問(wèn)題的最優(yōu)解為故原問(wèn)題的最優(yōu)解為X=(1,0,0,0,1)X=(1,0,0,0,1)T TZ Zminmin=5=522例例6 6：已知某：已知某LPLP問(wèn)題的最優(yōu)單純形表如下，試問(wèn)題的最優(yōu)單純形表如下，試分別寫出其原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解分別寫出其原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解 cj63200

18、0cBXBBx1x2x3x4x5x62x316001-2400 x610-100-1013x241101-40 zj cj zj333020-11-4400對(duì)偶問(wèn)題的用途對(duì)偶問(wèn)題的用途減少計(jì)算工作量：如判斷減少計(jì)算工作量：如判斷LP問(wèn)題有無(wú)最優(yōu)解問(wèn)題有無(wú)最優(yōu)解對(duì)求對(duì)求“min ”時(shí)，可轉(zhuǎn)換為對(duì)偶問(wèn)題易求解時(shí)，可轉(zhuǎn)換為對(duì)偶問(wèn)題易求解233-4 3-4 線性規(guī)劃解法之三：線性規(guī)劃解法之三：對(duì)偶單純形法對(duì)偶單純形法一、對(duì)偶單純形法的基本思想一、對(duì)偶單純形法的基本思想從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行，從原規(guī)劃的一個(gè)基本解出發(fā)，此基本解不一定可行，但它對(duì)應(yīng)著一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正），所以

19、也但它對(duì)應(yīng)著一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正），所以也可以說(shuō)是從一個(gè)對(duì)偶可行解出發(fā)可以說(shuō)是從一個(gè)對(duì)偶可行解出發(fā)然后檢驗(yàn)原規(guī)劃的基本解是否可行，即是否有負(fù)的然后檢驗(yàn)原規(guī)劃的基本解是否可行，即是否有負(fù)的分量，如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)分量，如果有小于零的分量，則進(jìn)行迭代，求另一個(gè)基本解，此基本解對(duì)應(yīng)著另一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)基本解，此基本解對(duì)應(yīng)著另一個(gè)對(duì)偶可行解（檢驗(yàn)數(shù)非正）非正）如果得到的基本解的分量皆非負(fù)，則該基本解為最如果得到的基本解的分量皆非負(fù)，則該基本解為最優(yōu)解。也就是說(shuō)，優(yōu)解。也就是說(shuō)，對(duì)偶單純形法在迭代過(guò)程中始終保對(duì)偶單純形法在迭代過(guò)程中始終保持對(duì)偶解的可行性（即檢驗(yàn)數(shù)非正）

20、，使原規(guī)劃的基持對(duì)偶解的可行性（即檢驗(yàn)數(shù)非正），使原規(guī)劃的基本解由不可行逐步變?yōu)榭尚?，?dāng)同時(shí)得到對(duì)偶規(guī)劃與本解由不可行逐步變?yōu)榭尚?，?dāng)同時(shí)得到對(duì)偶規(guī)劃與原規(guī)劃的可行解時(shí)，便得到原規(guī)劃的最優(yōu)解原規(guī)劃的可行解時(shí)，便得到原規(guī)劃的最優(yōu)解24二、對(duì)偶單純形法求解線性規(guī)劃問(wèn)題過(guò)程二、對(duì)偶單純形法求解線性規(guī)劃問(wèn)題過(guò)程1.1.建立初始對(duì)偶單純形表建立初始對(duì)偶單純形表, ,對(duì)應(yīng)一個(gè)基本解對(duì)應(yīng)一個(gè)基本解, ,所有檢驗(yàn)數(shù)均非正所有檢驗(yàn)數(shù)均非正, ,轉(zhuǎn)轉(zhuǎn)2 2；2.2.若若b b0,0,則得到最優(yōu)解則得到最優(yōu)解, ,停止停止; ;否則否則, ,若有若有b bk k00則選則選minminb bk k| |b bk k

21、00的的k k行的基變量為換出變行的基變量為換出變量量, ,轉(zhuǎn)轉(zhuǎn)3 33.3.若所有若所有a akjkj0( 0( j j = 1,2, = 1,2,n n ) )，則原問(wèn)，則原問(wèn)題無(wú)可行解題無(wú)可行解, ,停止停止; ;否則否則, ,若有若有a akjkj0 0 則選則選minmin j j / / a akjkja akjkj00= r r/a akrkr那么選那么選x xr r為換入基變量為換入基變量, ,轉(zhuǎn)轉(zhuǎn)4 4；4.4.以以a akrkr進(jìn)行轉(zhuǎn)軸運(yùn)算進(jìn)行轉(zhuǎn)軸運(yùn)算, ,作矩陣行變換使其變作矩陣行變換使其變?yōu)闉?,1,該列其他元素變?yōu)樵摿衅渌刈優(yōu)?,0,轉(zhuǎn)轉(zhuǎn)2 225例例7 7：用對(duì)

22、偶單純形法求解下列：用對(duì)偶單純形法求解下列LPLP問(wèn)題問(wèn)題 min Z=6X1十十3X2十十2X3 s.t. X1十十X2十十X3 20 1/2X1十十1/2X2十十1/4X3 6 2X1十十X2十十X3 10 X1，X2，X3 026解法一解法一: :將將LPLP問(wèn)題化為問(wèn)題化為 max Z= 6X1 3X2 2X3 s.t. X1 X2 X3十十X4 = 20 1/2X1 1/2X2 1/4X3 十十X5 = 6 2X1 X2 X3 十十X6 = 10 X1，X2，X3 , X4 , X5 , X6 ,0 cj-6-3-2000cBXBbx1x2x3x4x5x60 x4-20-1-1-11

23、000 x5-6-1/2-1/2-1/40100 x6-10-2-1-1001 zj cj zj0-60-30-200000027 cj-6-3-2000cBXBbx1x2x3x4x5x60 x4(-20)-1-1-1*1000 x5-6-1/2-1/2-1/40100 x6-10-2-1-1001 zj cj zj0-60-30-2000000-2x320111-1000 x5(-1)-1/4-1/4*0-1/4100 x610-100-101 zj cj zj-2-4-2-1-202-20000-2x316001-240-3x241101-400 x610-100-101 zj cj zj

24、-3-3-30-201-14-40028表中所有檢驗(yàn)數(shù)均不大于表中所有檢驗(yàn)數(shù)均不大于0，且，且bi0已達(dá)到最優(yōu)已達(dá)到最優(yōu) 最優(yōu)解為最優(yōu)解為X=(0,4,16,0,0,10)T , Zmax=64+201=44Zmin= Zmax=44解法二解法二: :將將LPLP問(wèn)題化為問(wèn)題化為 min Z= 6X1十十3X2十十2X3 s.t. X1 X2 X3十十X4 = 20 1/2X1 1/2X2 1/4X3 十十X5 = 6 2X1 X2 X3 十十X6 = 10 X1，X2，X3 , X4 , X5 , X6 ,029 cj632000cBXBbx1x2x3x4x5x60 x4(-20)-1-1-

25、1*1000 x5-6-1/2-1/2-1/40100 x6-10-2-1-1001 zj zj cj0-60-30-2000000例例8:用對(duì)偶單純形法求解下列用對(duì)偶單純形法求解下列LP問(wèn)題問(wèn)題min Z=3X1十十2X2十十X3 s.t. X1十十X2十十X3 6 X1 X3 4 X2X3 3 X1，X2，X3 030解解:化為化為 min Z=3X1十十2X2十十X3 s.t. X1十十X2十十X3十十X4 =6 X1 十十X3 十十X5 =-4 X2 十十X3 十十X6 =-3 X1，X2，X3 , X4 , X5 , X6 0 cj321000cBXBbx1x2x3x4x5x60 x

26、461111000 x5(-4)-1*010100 x6-30-11001 zj zj cj0-30-20-100000031 cj321000cBXBbx1x2x3x4x5x60 x461111000 x5(-4)-1*010100 x6-30-11001 zj zj cj0-30-20-10000000 x420121103x1410-10-100 x6(-3)0-1*1001 zj zj cj300-2-3-400-3-3000 x4(-1)0011113x1410-10-100 x6301-100-1 zj zj cj3020-5-600-3-3-2-232表中所有檢驗(yàn)數(shù)均不大于表中所

27、有檢驗(yàn)數(shù)均不大于0,但但x4變量行的變量行的aij全為全為非負(fù)非負(fù),故該問(wèn)題無(wú)可行解故該問(wèn)題無(wú)可行解三、三、對(duì)偶單純形法的適用范圍對(duì)偶單純形法的適用范圍1.1.應(yīng)用前提：有一個(gè)基，其對(duì)應(yīng)的基滿足應(yīng)用前提：有一個(gè)基，其對(duì)應(yīng)的基滿足: :單純形表的檢驗(yàn)數(shù)行全部非正（對(duì)偶可行）單純形表的檢驗(yàn)數(shù)行全部非正（對(duì)偶可行）變量取值可有負(fù)數(shù)（非可行解）變量取值可有負(fù)數(shù)（非可行解）注：通過(guò)矩陣行變換運(yùn)算，使所有相應(yīng)變量注：通過(guò)矩陣行變換運(yùn)算，使所有相應(yīng)變量取值均為非負(fù)數(shù)即得到最優(yōu)單純性表取值均為非負(fù)數(shù)即得到最優(yōu)單純性表2.2.對(duì)偶單純形法適合于解如下形式的線性規(guī)對(duì)偶單純形法適合于解如下形式的線性規(guī)劃問(wèn)題劃問(wèn)題3

28、3njxmibxacxcZjnjijijnjjjj,2,1,0,2,10min11例例9 9：求解下列：求解下列LPLP問(wèn)題問(wèn)題max Z=X1十十X2s.t. 2X1十十X24 X1十十7X27 X1，X2034四、對(duì)偶單純形法與單純形法的比較四、對(duì)偶單純形法與單純形法的比較1.思路比較思路比較單純形法是單純形法是從一個(gè)基本可行解轉(zhuǎn)到另一個(gè)更從一個(gè)基本可行解轉(zhuǎn)到另一個(gè)更優(yōu)的基本可行解，優(yōu)的基本可行解，即跌代中始終保持原問(wèn)題的即跌代中始終保持原問(wèn)題的可行性：可行性：b0，檢驗(yàn)數(shù)中大于檢驗(yàn)數(shù)中大于0的逐步變?yōu)槿康闹鸩阶優(yōu)槿?為止為止對(duì)偶單純形法是對(duì)偶單純形法是保持滿足最優(yōu)檢驗(yàn)判斷，即保持滿足

29、最優(yōu)檢驗(yàn)判斷，即全部檢驗(yàn)數(shù)全部檢驗(yàn)數(shù)0，從一個(gè)基本解逐步跌代變?yōu)橐粡囊粋€(gè)基本解逐步跌代變?yōu)橐粋€(gè)基本可行解，即個(gè)基本可行解，即b0為止為止2.計(jì)算步驟的關(guān)系計(jì)算步驟的關(guān)系35是是是是否否否否所有所有得到最優(yōu)解計(jì)算計(jì)算典式對(duì)應(yīng)原規(guī)劃的基本解是可行的典式對(duì)應(yīng)原規(guī)劃的基本解的檢驗(yàn)數(shù)所有所有計(jì)算計(jì)算以中心元素進(jìn)行迭代以中心元素進(jìn)行迭代停沒(méi)有最優(yōu)解沒(méi)有最優(yōu)解單純形法對(duì)偶單純形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min36五、對(duì)偶單純法的應(yīng)用：增加約束條件五、對(duì)偶單純法的應(yīng)用：增加約束條件(一一)對(duì)偶單純形法的用途對(duì)偶單純形

30、法的用途1.對(duì)約束條件方程為對(duì)約束條件方程為“”型型,不必加人工變量用大不必加人工變量用大M法或兩階段法求解而采用對(duì)偶單純形法求解更容易法或兩階段法求解而采用對(duì)偶單純形法求解更容易2.增加一個(gè)約束條件方程后不必重新求解，只需在增加一個(gè)約束條件方程后不必重新求解，只需在最優(yōu)解表上增加用對(duì)偶單純形法求解即可最優(yōu)解表上增加用對(duì)偶單純形法求解即可(二二)LP問(wèn)題新增約束條件的求解步驟問(wèn)題新增約束條件的求解步驟1.檢驗(yàn)原來(lái)的最優(yōu)解是否滿足新增加的約束條件：檢驗(yàn)原來(lái)的最優(yōu)解是否滿足新增加的約束條件：若滿足，則原最優(yōu)解就是新問(wèn)題的最優(yōu)解若滿足，則原最優(yōu)解就是新問(wèn)題的最優(yōu)解若不滿足，則進(jìn)行下一步若不滿足，則進(jìn)

31、行下一步372.將新增約束條件加入松弛變量或多余變量后加到原將新增約束條件加入松弛變量或多余變量后加到原來(lái)最優(yōu)單純形表中，令來(lái)最優(yōu)單純形表中，令原基變量和新增的松弛變量或原基變量和新增的松弛變量或多余變量組成新基，并將基變量對(duì)應(yīng)的系數(shù)矩陣變?yōu)槎嘤嘧兞拷M成新基，并將基變量對(duì)應(yīng)的系數(shù)矩陣變?yōu)閱挝痪仃噯挝痪仃嚒啊毙图s束條件方程加松弛變量變?yōu)樾图s束條件方程加松弛變量變?yōu)椤啊毙图s束型約束條件方程條件方程“”型約束條件方程減多余變量變?yōu)樾图s束條件方程減多余變量變?yōu)椤啊毙图s束型約束條件方程，然后等式方程兩端乘以條件方程，然后等式方程兩端乘以(-1)“=”型約束條件方程轉(zhuǎn)化為型約束條件方程轉(zhuǎn)化為“”和和“”，

32、然后將不滿，然后將不滿足的條件加進(jìn)去足的條件加進(jìn)去3.利用對(duì)偶單純形法求最優(yōu)解利用對(duì)偶單純形法求最優(yōu)解38例例10：已知：已知LP問(wèn)題問(wèn)題 Max z =40 xMax z =40 x1 1+45x+45x2 2 +24x +24x3 3 s.t. 2x s.t. 2x1 1+3x+3x2 2+x+x3 3 100 100 3x 3x1 1+3x+3x2 2+2x+2x3 3 120 120 x x1 1 ,x,x2 2 ，x x3 300用單純形法求解得最優(yōu)單純形表如下：用單純形法求解得最優(yōu)單純形表如下： cj40452400cBXBBx1x2x3x4x545x22001-1/31-2/34

33、0 x120101-11 zj cj zj40045025-15-510-1039試求在增加一個(gè)約束條件試求在增加一個(gè)約束條件X115時(shí)新的最優(yōu)解時(shí)新的最優(yōu)解解解:(1)原最優(yōu)解為原最優(yōu)解為X1=20,X2=20,而新增約束而新增約束X115,所所以原最優(yōu)解不滿足新增約束條件以原最優(yōu)解不滿足新增約束條件(2) X115處理得處理得X1 X6=15， X60，從而得到新的，從而得到新的單純形表并進(jìn)行初等交換單純形表并進(jìn)行初等交換 cj404524000cBXBBx1x2x3x4x5x645x22001-1/31-2/3040 x120101-1100 x61510000140 cj4045240

34、00cBXBBx1x2x3x4x5x645x22001-1/31-2/3040 x120101-1100 x6-500-1*1-11 zj cj zj40045025-15-510-100045x265/30102/3-1/3-1/340 x11510000124x35001-11-1 zj cj zj4004502406-69-91-1表中所有檢驗(yàn)數(shù)均不大于表中所有檢驗(yàn)數(shù)均不大于0，且，且bi0已達(dá)到最優(yōu)已達(dá)到最優(yōu) 最優(yōu)解為最優(yōu)解為X=(15,65/3,5,0,0,0)T , Zmax=1695413-5 3-5 線性規(guī)劃的靈敏度分析線性規(guī)劃的靈敏度分析一、線性規(guī)劃與參數(shù)規(guī)劃一、線性規(guī)劃與參

35、數(shù)規(guī)劃1.1.線性規(guī)劃：目標(biāo)函數(shù)系數(shù)線性規(guī)劃：目標(biāo)函數(shù)系數(shù)C Cj j、約束條件方程、約束條件方程系數(shù)系數(shù)a aijij、約束條件方程右端值、約束條件方程右端值b bi i均固定均固定2.2.參數(shù)規(guī)劃：參數(shù)規(guī)劃：C Cj j、a aijij、b bi i不固定不固定使得最優(yōu)解或最優(yōu)基不變的使得最優(yōu)解或最優(yōu)基不變的C Cj j、a aijij、b bi i的變的變化范圍的分析化范圍的分析LPLP問(wèn)題的靈敏度分析問(wèn)題的靈敏度分析使得最優(yōu)解或最優(yōu)基變化的使得最優(yōu)解或最優(yōu)基變化的C Cj j、a aijij、b bi i的變的變化范圍的分析化范圍的分析參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃42二、靈敏度分析的概念與

36、界定范圍二、靈敏度分析的概念與界定范圍1.概念：概念：某一參數(shù)發(fā)生變化時(shí)，目標(biāo)函數(shù)發(fā)生怎樣變某一參數(shù)發(fā)生變化時(shí)，目標(biāo)函數(shù)發(fā)生怎樣變化的分析化的分析2.界定范圍：界定范圍：“Max ”三、三、LP問(wèn)題靈敏度分析的內(nèi)容問(wèn)題靈敏度分析的內(nèi)容1.對(duì)對(duì)C Cj j值的靈敏度分析值的靈敏度分析2.對(duì)對(duì)b bi i值的靈敏度分析值的靈敏度分析對(duì)對(duì)3. a3. aijij值的靈敏度分析值的靈敏度分析* *4.4.增加或刪去一個(gè)變量的分析增加或刪去一個(gè)變量的分析5.5.增加或去掉一個(gè)約束條件的分析增加或去掉一個(gè)約束條件的分析43四、理解最優(yōu)單純性表中各元素的含義四、理解最優(yōu)單純性表中各元素的含義考慮問(wèn)題考慮問(wèn)題

37、 Max Max z z = = c c1 1 x x1 1 + + c c2 2 x x2 2 + + + + c cn n x xn n s.t. s.t. a a1111x x1 1 + + a a1212x x2 2 + + + + a a1n1nx xn n b b1 1 a a2121x x1 1 + + a a2222x x2 2 + + + + a a2n2nx xn n b b2 2 . . . . . . a am1m1x x1 1 + + a am2m2x x2 2 + + + + a amnmnx xn n b bm m x x1 1 ，x x2 2 ， ，x xn n

38、 0 0 引入引入 m m 個(gè)松弛變量后，通過(guò)計(jì)算得到個(gè)松弛變量后，通過(guò)計(jì)算得到最優(yōu)單純形表。最優(yōu)單純形表。 應(yīng)能夠找到最優(yōu)基應(yīng)能夠找到最優(yōu)基 B B 的的逆矩陣逆矩陣 B B-1-1 和檢驗(yàn)數(shù)等和檢驗(yàn)數(shù)等44五、價(jià)值系數(shù)五、價(jià)值系數(shù)cj的靈敏度分析的靈敏度分析1.1.對(duì)對(duì)cj的靈敏度分析的前提的靈敏度分析的前提 維持最優(yōu)解維持最優(yōu)解 不變：基變量及其取值不變不變：基變量及其取值不變cj的變化仍使單純形表中的非基本量的檢驗(yàn)數(shù)的變化仍使單純形表中的非基本量的檢驗(yàn)數(shù) j = cj zj都保持不大于都保持不大于0 cj的變化僅影響的變化僅影響zj和檢驗(yàn)數(shù)和檢驗(yàn)數(shù) j = cj zj2.2.對(duì)對(duì)cj的

39、靈敏度分析的靈敏度分析(1) (1) xj是非基變量時(shí)是非基變量時(shí)若若x xj j是非基變量時(shí)，是非基變量時(shí)， cj的變化僅影響的變化僅影響x xj j對(duì)應(yīng)的檢驗(yàn)對(duì)應(yīng)的檢驗(yàn)數(shù)數(shù)cj zjcj減少的范圍：減少的范圍： xj已經(jīng)不在最優(yōu)解內(nèi)，已經(jīng)不在最優(yōu)解內(nèi)， cj減少時(shí)減少時(shí)xj更不會(huì)在最優(yōu)解范圍內(nèi)，所以更不會(huì)在最優(yōu)解范圍內(nèi)，所以cj的變動(dòng)下限為的變動(dòng)下限為 45cj增加的范圍：設(shè)在原最優(yōu)單純形表中，增加的范圍：設(shè)在原最優(yōu)單純形表中， cj變?yōu)樽優(yōu)閏j + cj ，則檢驗(yàn)數(shù)為，則檢驗(yàn)數(shù)為 j = cj + cj zjv若若cj + cj zj0成立，則目標(biāo)不變；成立，則目標(biāo)不變；v若若cj +

40、cj zj 0成立，則目標(biāo)不變，但有多重解成立，則目標(biāo)不變，但有多重解v若若cj + cj zj0成立，則目標(biāo)發(fā)生變化成立，則目標(biāo)發(fā)生變化cj + cj zj0 cj ( cj zj ),所以所以cj的變的變動(dòng)上限為動(dòng)上限為 ( cj zj ) 當(dāng)當(dāng)xj為非基變量時(shí)，為非基變量時(shí)， cj的變化范圍為的變化范圍為 cj ( cj zj )46例例11：已知下列：已知下列LP 問(wèn)題：?jiǎn)栴}： MaxMax z =x z =x1 1+5x+5x2 2 +3x+3x3 3 +4x+4x4 4 s.t. 2x s.t. 2x1 1+3x+3x2 2+x+x3 3+2x+2x4 4 800 800 5x 5

41、x1 1+4x+4x2 2+3x+3x3 3+4x+4x4 4 1200 1200 3x 3x1 1+4x+4x2 2+5x+5x3 3+3x+3x4 41000 1000 x x1 1 ,x,x2 2 ，x x3 3 ，x x4 400 其最優(yōu)單純形表如下，試分析其最優(yōu)單純形表如下，試分析c c1 1和和c c3 3的靈的靈敏度范圍敏度范圍47 cj1534000cBXBBx1x2x3x4x5x6x70 x51000.250-3.25010.25-14x420020-2101-15x2100-0.7512.7500-0.751 zj cj zj4.25-3.25505.75-2.754000

42、0.25-0.251-1解：由單純形表可知解：由單純形表可知(1) c1 ( c1 z1 )， c1 3.25 c1 4.25(2) c3 ( c3 z3 )， c3 2.75 c3 5.7548(2) (2) xj是基變量時(shí)是基變量時(shí)若若x xj j是基變量時(shí)，是基變量時(shí)， cj的變化影響的變化影響所有非基變量對(duì)應(yīng)所有非基變量對(duì)應(yīng)的的zj和檢驗(yàn)數(shù)和檢驗(yàn)數(shù)cj zjcj變化范圍：變化范圍：v設(shè)設(shè)xj為第為第r個(gè)約束條件方程對(duì)應(yīng)的基變量，當(dāng)個(gè)約束條件方程對(duì)應(yīng)的基變量，當(dāng)cj變?yōu)樽優(yōu)閏j + cj ，則，則cB變?yōu)樽優(yōu)閏B + cB其中其中 cB=(0,0,0, cj,0,0,0)v非基變量非基變

43、量xk檢驗(yàn)數(shù)應(yīng)滿足：檢驗(yàn)數(shù)應(yīng)滿足：ck (cB + cB)B-1Pk0ck cB B-1Pk cBB-1Pk0(ck zk ) cBB-1Pk0(ck zk )(0,0,0, cj,0,0,0) B-1Pk049(ck zk )(0,0,0, cj,0,0,0) B-1Pk0(ck zk )(0,0,0, cj,0,0,0) Pk0(ck zk ) cjark0 cjark ck zk 當(dāng)當(dāng)ark 0時(shí)，則時(shí)，則 cj（ck zk ）/ ark 當(dāng)當(dāng)ark 0時(shí)，則時(shí)，則 cj（ck zk ）/ ark 當(dāng)當(dāng)ark =0時(shí)，則時(shí)，則 cj的變化不影響的變化不影響zk結(jié)論：當(dāng)結(jié)論：當(dāng)xj為基變量

44、時(shí)為基變量時(shí), cj的變化范圍為的變化范圍為(xj為第為第r個(gè)方程個(gè)方程)Max（ck zk ）/ ark | ark 0 cj minck zk ）/ ark | ark 050例例12：已知：已知LP 問(wèn)題的問(wèn)題的最優(yōu)單純形表如下，試分最優(yōu)單純形表如下，試分析析c c2 2和和c c4 4的靈敏度范圍的靈敏度范圍 cj1534000cBXBBx1x2x3x4x5x6x70 x51000.250-3.25010.25-14x420020-2101-15x2100-0.7512.7500-0.751 zj cj zj4.25-3.25505.75-2.7540000.25-0.251-151六

45、、資源數(shù)量六、資源數(shù)量bi的靈敏度分析的靈敏度分析1.1.對(duì)對(duì)bi的靈敏度分析的前提的靈敏度分析的前提 維持最優(yōu)解基變量不變，但是其取值可變維持最優(yōu)解基變量不變，但是其取值可變bi的變化僅影響基變量的取值的變化僅影響基變量的取值2.2.對(duì)對(duì)bi的靈敏度分析的靈敏度分析原最優(yōu)解為原最優(yōu)解為X XB B=B=B-1-1b,b,設(shè)設(shè)b bk k的變化量為的變化量為b bk k，則其他系，則其他系數(shù)不變時(shí)新解中基變量的取值為數(shù)不變時(shí)新解中基變量的取值為XXB B=B=B-1-1（b+ b+ b b）00，其中，其中b=b=（0 0，0 0，b bk k ，0 0，0 0）T TXXB B=B=B-1-

46、1（b+ b+ b b）= X= XB B=B=B-1-1b+ Bb+ B-1-1 b b =(b =(b1 1+ + b bk kaa1,n+k1,n+k, b, b2 2+ + b bk kaa2,n+k 2,n+k ,， bbm m+ + b bk kaam,n+k m,n+k ) )T T由此可得由此可得, , bbi i+ + b bk kaai,n+ki,n+k 0,I=1,2,m 0,I=1,2,m b bk kaai,n+ki,n+k bbi i,I=1,2,m,I=1,2,m52(1)當(dāng)當(dāng)aai,n+ki,n+k 0 0時(shí)，則時(shí)，則b bk k bbi i/ a/ ai,n+

47、ki,n+k (2)(2)當(dāng)當(dāng)aai,n+ki,n+k 0 0時(shí)，則時(shí)，則b bk k bbi i/ a/ ai,n+ki,n+k 3.3.當(dāng)當(dāng)XXB B=B=B-1-1（b+ b+ b b）00時(shí)，最優(yōu)解基變時(shí)，最優(yōu)解基變量不變，但最優(yōu)解的取值發(fā)生變化，取值為量不變，但最優(yōu)解的取值發(fā)生變化，取值為XXB B=B=B-1-1（b+ b+ b b）=B=B-1-1b+ Bb+ B-1-1 b b = X = XB B+ +b bk kPPn+kn+k4.4.當(dāng)當(dāng)XXB B=B=B-1-1（b+ b+ b b）00時(shí)，原最優(yōu)解不時(shí)，原最優(yōu)解不可行，用可行，用對(duì)偶單純形法對(duì)偶單純形法求新的最優(yōu)解求新

48、的最優(yōu)解53例例13：已知：已知LP 問(wèn)題的問(wèn)題的最優(yōu)單純形表如下，試分最優(yōu)單純形表如下，試分析析b b2 2和和b b3 3的靈敏度范圍的靈敏度范圍 cj1534000cBXBBx1x2x3x4x5x6x70 x51000.250-3.25010.25-14x420020-2101-15x2100-0.7512.7500-0.751 zj cj zj4.25-3.25505.75-2.7540000.25-0.251-154七、七、增加或刪去一個(gè)變量的分析增加或刪去一個(gè)變量的分析1.1.增加一個(gè)變量增加一個(gè)變量 設(shè)增加的變量為設(shè)增加的變量為x xn+1n+1, ,其價(jià)值系數(shù)為其價(jià)值系數(shù)為c

49、cn+1n+1 , ,系數(shù)列向系數(shù)列向量量P Pn+1n+1, ,則檢驗(yàn)數(shù)為則檢驗(yàn)數(shù)為n+1n+1=c=cn+1n+1-c-cB BB B-1-1P Pn+1n+1(1)(1)若若n+1n+1 0, 0,則原最優(yōu)解不變則原最優(yōu)解不變(2)(2)若若n+1n+1 0,0,則將則將x xn+1n+1引入基變量引入基變量, ,進(jìn)行跌代進(jìn)行跌代2.2.刪去一個(gè)變量刪去一個(gè)變量(1)(1)若若x xr r為非基變量，去掉為非基變量，去掉x xr r不影響最優(yōu)解不影響最優(yōu)解55(2)(2)若若x xr r為基變量，對(duì)最優(yōu)解產(chǎn)生影響，其處理方法為：為基變量，對(duì)最優(yōu)解產(chǎn)生影響，其處理方法為：取取x xr r為

50、換出變量，用對(duì)偶單純形法求解為換出變量，用對(duì)偶單純形法求解取取x xr r的價(jià)值系數(shù)的價(jià)值系數(shù)c cr r為為M M，用大，用大M M法計(jì)算法計(jì)算八、八、增加或去掉一個(gè)約束條件的分析增加或去掉一個(gè)約束條件的分析1.刪去一個(gè)約束條件刪去一個(gè)約束條件(1)對(duì)最優(yōu)解沒(méi)有影響：松弛變量、多余變量的對(duì)最優(yōu)解沒(méi)有影響：松弛變量、多余變量的取值都是大于取值都是大于0的約束條件稱為松約束的約束條件稱為松約束(2)對(duì)最優(yōu)解有影響：松弛變量、多余變量的取對(duì)最優(yōu)解有影響：松弛變量、多余變量的取值都是等于值都是等于0的約束條件稱為緊約束的約束條件稱為緊約束562.增加一個(gè)約束條件增加一個(gè)約束條件(1)若原最優(yōu)解滿足約

51、束條件，最優(yōu)解不變?nèi)粼顑?yōu)解滿足約束條件，最優(yōu)解不變(2)若原最優(yōu)解不滿足約束條件，用對(duì)偶單純形法求解若原最優(yōu)解不滿足約束條件，用對(duì)偶單純形法求解例例14：已知下列：已知下列LP 問(wèn)題問(wèn)題 MaxMax z z = 2 = 2x x1 1 + 3 + 3x x2 2 s.t. s.t. x x1 1 + 2 + 2x x2 2 + + x x3 3 = 8= 8 4 4x x1 1 + + x x4 4 = 16 = 16 4 4x x2 2 + + x x5 5 = = 1212 x x1 1, ,x x2 2 , ,x x3 3, ,x x4 4, ,x x5 5 0 0其其最優(yōu)單純形表如

52、下最優(yōu)單純形表如下57 cj23000cBXBBx1x2x3x4x52x141001/400 x5400-21/213x22011/2-1/80 zj cj zj20303/2-3/21/8-1/800試分析：試分析：(1)分析分析C2的靈敏度范圍的靈敏度范圍(2) 當(dāng)?shù)谝粋€(gè)約束條件的當(dāng)?shù)谝粋€(gè)約束條件的b b1 1 增加增加4 4時(shí)，對(duì)原最優(yōu)解有影響嗎？時(shí)，對(duì)原最優(yōu)解有影響嗎？若有，求出新的最優(yōu)解若有，求出新的最優(yōu)解(3)(3)增加增加x x6 6時(shí)時(shí), , p p6 6=( 2, 6, 3 )=( 2, 6, 3 )T T, , c c6 6=5=5，對(duì)原最優(yōu)解的影響對(duì)原最優(yōu)解的影響 (4)(4)增加增加3 3x x1 1+ 2+ 2x x2 21515時(shí)對(duì)原最優(yōu)解的影響時(shí)對(duì)原最優(yōu)解的影響58解解: :(1)(1) -3 -3c c2 211(2)x = ( 4, 3, 2, 0, 0 )(2)x = ( 4, 3, 2, 0, 0 )T T Z Z* * = 17 =