單純形法和對(duì)偶問(wèn)題

單純形法和對(duì)偶問(wèn)題第1頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月單純形表2第2頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析一、目標(biāo)函數(shù)中變量系數(shù)Ck靈敏度分析（在什么范圍內(nèi)變化，最優(yōu)解不變，與第二章，第三章聯(lián)系起來(lái)）在線性規(guī)劃的求解過(guò)程中，目標(biāo)函數(shù)系數(shù)的變動(dòng)將會(huì)影響檢驗(yàn)數(shù)的取值，但是，當(dāng)目標(biāo)函數(shù)的系數(shù)的變動(dòng)不破壞最優(yōu)判別準(zhǔn)則時(shí)，原最優(yōu)解不變，否則，原最優(yōu)解將發(fā)生變化，要設(shè)法求出新的最優(yōu)解。下面我們具體的分析

1.在最終的單純形表里，Xk是非基變量由于約束方程系數(shù)增廣矩陣在迭代中只是其本身的行的初等變換與Ck沒(méi)有任何關(guān)系，所以當(dāng)Ck變成Ck+Ck時(shí)，在最終單純形表中其系數(shù)的增廣矩陣不變，又因?yàn)閄k是非基變量，所以基變量的目標(biāo)函數(shù)的系數(shù)不變，即CB不變，可知Zk也不變，只是Ck變成了Ck+Ck。這時(shí)K=Ck-Zk就變成了Ck+Ck-Zk=K+Ck。要使原來(lái)的最優(yōu)解仍為最優(yōu)解，只要K+Ck≤0即可，也就是Ck的增量Ck≤-K。

3第3頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月2.在最終的單純形表中，Xk是基變量當(dāng)Ck變成Ck+Ck時(shí)，最終單純形表中約束方程的增廣矩陣不變，但是基變量的目標(biāo)函數(shù)的系數(shù)CB變了，則ZJ(J=1,2,…..,N)一般也變了，不妨設(shè)CB=(CB1,CB2。。。,Ck,…，CBm),當(dāng)CB變成=(CB1,CB2。。。,Ck+Ck,…,CBm),則：ZJ=(CB1,CB2。。。,Ck,…,,…，CBm)(a’1j,a’2j,…,a’Kj,…,a’mj)Z’J=(CB1,CB2。。。,Ck+Ck,…，CBm)(a’1j,a’2j,…,a’Kj,…,a’mj)=ZJ+Cka’Kj

4第4頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析根據(jù)上式可知檢驗(yàn)數(shù)J(J=1,2,…..,M)變成了’J,只要當(dāng)JK時(shí)，有

’

J=CJ-Z’J=J-CKa’Kj。要使最優(yōu)解不變，’J<=0

5第5頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析例：目標(biāo)函數(shù)：Maxz=50X1+100X2

約束條件：X1+X2≤3002X1+X2≤400X2≤250X1，X2≥0最優(yōu)單純形表如下迭代次數(shù)基變量CBX1X2S1S2S3b501000002X1501010-150

S2000-21150

X210001001250

ZJ501005005027500CJ-ZJ00-500-506第6頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析對(duì)非基變量目標(biāo)函數(shù)系數(shù)：C3

我們先對(duì)非基變量S1的目標(biāo)函數(shù)的系數(shù)C3進(jìn)行靈敏度分析。這里δ3=-50，所以當(dāng)c3的增量Δc3≤-（-50），最優(yōu)解不變。對(duì)基變量目標(biāo)函數(shù)系數(shù)：c1

再對(duì)基變量x1的目標(biāo)函數(shù)的系數(shù)c1進(jìn)行靈敏度分析。在a11’,a12’,a13’,a14’,a15’中，除了知道a11’和

a13’大于0，a15’小于0，可知，有同樣有。這樣可以知道當(dāng)-50≤Δc1≤50時(shí)，也就是x1的目標(biāo)函數(shù)c1’在0≤c1’≤100時(shí)最優(yōu)解不變。

7第7頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析迭代次數(shù)基變量CBX1X2S1S2S3bC’11000002X11010-150

S2000-21150

X210001001250

ZJC’1100C’10-C’1+100CJ-ZJ00-C’10C’1-1008

從δ3≤0，得到-c1’≤0,即c1’≥0，并且從δ5≤0，得到c1’≤100。那么如果c1’取值超出這個(gè)范圍，必然存在一個(gè)檢驗(yàn)數(shù)大于0，我們可以通過(guò)迭代來(lái)得到新的最優(yōu)解。另外一種求最優(yōu)解不變的C’1變化范圍方法在最終的單純形表中，用C’1代替原來(lái)的C1=50,計(jì)算得表第8頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月常數(shù)項(xiàng)靈敏度分析之前的一點(diǎn)補(bǔ)充知識(shí)：9第9頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月補(bǔ)充知識(shí)10第10頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月補(bǔ)充知識(shí)11第11頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月補(bǔ)充知識(shí)12第12頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月補(bǔ)充知識(shí)13第13頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月補(bǔ)充知識(shí)14第14頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析二、約束方程中常數(shù)項(xiàng)的靈敏度分析（使對(duì)偶價(jià)格不變的b的變化范圍）回想一下：第2章例一各個(gè)約束的對(duì)偶價(jià)格：

從上表我們可以發(fā)現(xiàn)各個(gè)松弛變量的Zj值，正好等于相應(yīng)變量的對(duì)偶價(jià)格。15迭代次數(shù)基變量CBX1X2S1S2S3b501000002X1501010-150

S2000-21150

X210001001250

ZJ501005005027500CJ-ZJ00-500-50第15頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析

單純形表中的Zj跟對(duì)偶價(jià)格的關(guān)系：對(duì)于含有小于等于號(hào)的約束條件，添加松弛變量轉(zhuǎn)化為標(biāo)準(zhǔn)型。這時(shí)這個(gè)約束條件的對(duì)偶價(jià)格就和松弛變量的Zj有關(guān)。對(duì)偶價(jià)格應(yīng)取松弛變量的Zj的值。對(duì)于含有大于等于號(hào)的約束條件，添加剩余變量化為標(biāo)準(zhǔn)型。這時(shí)這個(gè)約束條件的對(duì)偶價(jià)格就和這個(gè)剩余變量的有關(guān)了。這時(shí)約束條件的對(duì)偶價(jià)格應(yīng)取值的相反數(shù)-。對(duì)于含有等于號(hào)的約束條件，其約束條件的對(duì)偶價(jià)格就和該約束方程的人工變量有關(guān)了。其約束條件的對(duì)偶價(jià)格就等于此約束方程的人工變量的值。

16第16頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析17最終單純形表對(duì)于不同約束類型的對(duì)偶價(jià)格的取值。

常數(shù)項(xiàng)的靈敏度分析-》使對(duì)偶價(jià)格不變的bj靈敏度分析-》知道對(duì)偶價(jià)格Zj等于Cb*Pj的轉(zhuǎn)置。我們知道單純型法是增廣矩陣的行的初等變換，bj的變化并不影響系數(shù)矩陣的變化。所以Pj是不變的。所以要使對(duì)偶價(jià)格不變，只要使Cb不變就可以，就是最終單純形表中的最優(yōu)基不變，即最終單純型表中的基變量還是基變量，怎么保證基變量還是基變量？（即最優(yōu)基不變，所得到的基本解是可行解，也就是基變量的值仍然大于等于零）所以原問(wèn)題轉(zhuǎn)化為：使最優(yōu)解的所有基變量不變，且所得的最優(yōu)解仍然是可行的Bj的變化范圍。約束條件對(duì)偶價(jià)格的取值≤等于這個(gè)約束條件對(duì)應(yīng)的松弛變量的值,即為的相反數(shù)≥等于這個(gè)約束條件對(duì)應(yīng)的剩余變量的值的相反數(shù)=等于這個(gè)約束條件對(duì)應(yīng)的人工變量的值第17頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析

當(dāng)bj中的第k項(xiàng)bK

變成時(shí)，也就是原來(lái)的初始單純形表中的b向量變成了b’向量18第18頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析

這樣在最終單純形表中基變量XB的解就變成了如要使XB成為可行解，只要使上述等式的右邊>0，就可求出的取值范圍，也就是使得第K個(gè)約束條件的對(duì)偶價(jià)格不變的bk的變化范圍。，19第19頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析（k的取值固定的值，i的取值是1到m）下面我們?nèi)砸缘诙吕?在最終單純形表上對(duì)b1進(jìn)行靈敏度分析。最終單純形表如下所示：迭代次數(shù)基變量CBX1X2S1S2S3b501000002X1501010-150

S2000-21150

X210001001250

ZJ501005005027500CJ-ZJ00-500-5020第20頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析

我們對(duì)b1進(jìn)行靈敏度分析，因?yàn)樵诘谝粋€(gè)約束方程中含有松弛變量S1,

實(shí)際意義可以描述為：設(shè)備臺(tái)時(shí)數(shù)在250與325之間變化，則設(shè)備臺(tái)時(shí)數(shù)的對(duì)偶價(jià)格不變，都為每臺(tái)設(shè)備臺(tái)時(shí)50元。21第21頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析三、約束方程系數(shù)矩陣A靈敏度分析（約束條件改變，對(duì)最優(yōu)解的影響，比如有新產(chǎn)品要生產(chǎn)、生產(chǎn)工藝改進(jìn)等）下面分兩種情況討論

1.在最終單純形表上Xk是非基變量：在初始單純形表上的變量Xk的系數(shù)列Pk改變?yōu)镻’k經(jīng)過(guò)迭代后，在最終單純形表上Xk是非基變量。由于單純形表的迭代是約束方程的增廣矩陣的行變換，Pk變成Pk’僅僅影響最終單純形表上第k列數(shù)據(jù)，包括Xk的系數(shù)列、Zk以及k，這時(shí)最終單純形表上的Xk的系數(shù)列就變成了B-1Pj’,而Zk就變成CBB-1Pk’，新的檢驗(yàn)數(shù)k=Ck-CBB-1Pk’。若k≤0，則原最優(yōu)解仍然為最優(yōu)解。若k〉0，則繼續(xù)進(jìn)行迭代以求出最優(yōu)。例以第二章例1為基礎(chǔ)，設(shè)該廠除了生產(chǎn)Ι，Ⅱ種產(chǎn)品外，現(xiàn)在試制成一個(gè)新產(chǎn)品Ⅲ，已知生產(chǎn)產(chǎn)品Ⅲ,每件需要設(shè)備2臺(tái)時(shí)，并消耗A原料0.5公斤。B原料1.5公斤，獲利150元，問(wèn)該廠應(yīng)該生產(chǎn)該產(chǎn)品多少？解：這是一個(gè)增加新變量的問(wèn)題。我們可以把它認(rèn)為是一個(gè)改變變量X3在初始表上的系數(shù)列的問(wèn)題，22第22頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析迭代次數(shù)基變量CBX1X2S1S2S3X3b50100000150X1501010-10.550

S2000-211-250

X2100010011.5250

ZJ501005005017527500CJ-ZJ00-500-50-2523第23頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析例假設(shè)上例題中產(chǎn)品Ш的工藝結(jié)構(gòu)有了改進(jìn)，這時(shí)生產(chǎn)1件Ш產(chǎn)品需要使用1.5臺(tái)設(shè)備，消耗原料A為2千克，原料B為1千克，每件Ш產(chǎn)品的利潤(rùn)為160元，問(wèn)該廠的生產(chǎn)計(jì)劃是否要修改。解：首先求出X3在最終表上的系數(shù)列

24迭代次數(shù)基變量CBX1X2S1S2S3X3b501000001602X1501010-10.55050/0.5

S2000-211050

X2100010011250250/1

ZJ501005005012527500CJ-ZJ00-500-5035第24頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析接下來(lái)又可以有新的迭代S3進(jìn)基，迭代次數(shù)基變量CBX1X2S1S2S3X3b501000001503X31602020-21100---

S2000-21105050/1

X2100-201-2030150250/3

ZJ1201001200-2016031000CJ-ZJ-700-120020025第25頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析接上頁(yè)可知此規(guī)劃的最優(yōu)解X1=0,X2=0,S1=0,S2=0,S3=50,X3=200,此時(shí)，最大目標(biāo)函數(shù)為32000元。也就是說(shuō)，該廠的新的生產(chǎn)計(jì)劃為不生產(chǎn)Ι、П產(chǎn)品，生產(chǎn)Ш產(chǎn)品200件,可獲得最大利潤(rùn)32000元。迭代次數(shù)基變量CBX1X2S1S2S3X3b501000001504X31602020-21200---

S3000-21105050/1

X2100-214-3000250/3

ZJ1201008020016032000CJ-ZJ-700-80-200026第26頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析

2.最終表上XK是基變量：在初始表上的變量XK的系數(shù)PK改變?yōu)镻’K，經(jīng)過(guò)迭代后，在最終表上XK是基變量，（比如X1，X2，制作產(chǎn)品1，產(chǎn)品2的工藝有改善，在這種情況下原最優(yōu)解的可行性和最優(yōu)解都可能被破壞，問(wèn)題十分復(fù)雜）一般不去修改最終單純形表，而是重新用單純形法計(jì)算。27第27頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析四、增加一個(gè)約束條件的靈敏度分析（增加一個(gè)約束條件對(duì)最優(yōu)解的影響）在原線性規(guī)劃中增加一個(gè)約束條件時(shí),（1）先將原問(wèn)題的最優(yōu)解的變量值代入新增的約束條件，如滿足則說(shuō)明新增的條件沒(méi)有起到限制作用，故原最優(yōu)解不變，停止計(jì)算。（2）否則將新增的約束添入原最終單純形表上，進(jìn)一步求解。下面仍以第三章例1為例來(lái)加以說(shuō)明。例：假如該工廠除了在設(shè)備臺(tái)時(shí)，原材料A、B上對(duì)該廠的生產(chǎn)有限制外，還有電力供應(yīng)上的限制。最高供應(yīng)電量為5000度，而生產(chǎn)一個(gè)Ⅰ產(chǎn)品需要用電10度，而生產(chǎn)一個(gè)Ⅱ產(chǎn)品需要用電30度。試分析此時(shí)該廠獲得最大利潤(rùn)的生產(chǎn)計(jì)劃？28

第28頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析

29解：先將原問(wèn)題的最優(yōu)解=50，=250代入用電量的約束條件得：10×50+30×250=500+7500>5000,所以原題的最優(yōu)解不是本題的最優(yōu)解。在用電量的約束條件中加入松馳變量S4后得：把這個(gè)約束條件加入到原最終單純形表上，其中S4為基變量，得表如下：迭代次數(shù)基變量b比值501000000501010-1050000-2110501000100102500103000015000501005005002750000-500-500第29頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析

30在上表中的X1，X2不是單位向量，故進(jìn)行行的線性變換，得迭代次數(shù)基變量CBx1x2s1s2s3s4b比值501000000x1501010-1050s2000-211050x2100010010250s4000-100-201-3000zj501005005002750000-500-500把上表中的S4行的約束可以寫為：上式兩邊乘以（-1），再加上人工變量a1得：用上式替換上表中的S4行，得下表：第30頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析31迭代次數(shù)基變量x1x2s1s2s3s4a1b比值501000000-Mx1501010-10050s2000-21(1)0050x21000100100250s4-M00-100-20113000zj5010050-10M050-20M0-M0010M-50020M-5000

x15010-11000100

s3000-2110050

x2100012-1000200

s4-M0050-200-112000

zj50100150-50M20M-500M-M

050M-15050-20M0-M0

x1501003/50-1/501/50140

s300001/51-2/502/50130

x2100010-1/502/50-2/50120

s40001-2/50-1/501/5040

zj5010001003-3

00-100-3-M+3

第31頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§1單純形表的靈敏度分析

32由上表可知，最優(yōu)解為：

即該工廠在添加了用電限量以后的最優(yōu)生產(chǎn)計(jì)劃為Ⅰ產(chǎn)品生產(chǎn)140件，Ⅱ產(chǎn)品生產(chǎn)120件。第32頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月上節(jié)回顧單純形法的靈敏度分析1.目標(biāo)函數(shù)系數(shù)Cj的靈敏度2.常數(shù)項(xiàng)bj的靈敏度分析3.系數(shù)矩陣A的靈敏度分析

在初始表上的變量XK的系數(shù)PK改變?yōu)镻’K，經(jīng)過(guò)迭代后，在最終表上XK是基變量，（比如X1，X2，制作產(chǎn)品1，產(chǎn)品2的工藝有改善，在這種情況下原最優(yōu)解的可行性和最優(yōu)解都可能被破壞，問(wèn)題十分復(fù)雜）一般不去修改最終單純形表，而是重新用單純形法計(jì)算。4.增加一個(gè)約束條件的靈敏度分析（1）先將原問(wèn)題的最優(yōu)解的變量值代入新增的約束條件，如滿足則說(shuō)明新增的條件沒(méi)有起到限制作用，故原最優(yōu)解不變，停止計(jì)算。（2）否則將新增的約束添入原最終單純形表上，進(jìn)一步求解。33第33頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月對(duì)偶單純形法：對(duì)偶單純形法也是解決線性規(guī)劃問(wèn)題的一種方法。對(duì)偶單純形法是在保持原有問(wèn)題的所有檢驗(yàn)數(shù)都小于0的情況下，通過(guò)迭代使得所有的約束都大于等于0，最后求得最優(yōu)解。優(yōu)點(diǎn)：簡(jiǎn)化計(jì)算是對(duì)偶單純形法的優(yōu)點(diǎn)例子：缺點(diǎn)：但是它在使用上有很大的局限，這主要是大多數(shù)線性規(guī)劃問(wèn)題很難找到初始解使得其所有檢驗(yàn)數(shù)都小于0。適用目標(biāo)函數(shù)的特點(diǎn)：

A.maxf=-M1*X1-M2*X2….的形式

B.用在靈敏度分析中（增加約束條件的）。

34上節(jié)回顧第34頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§2線性規(guī)劃的對(duì)偶問(wèn)題1.對(duì)偶問(wèn)題的定義2.原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系3.如何根據(jù)原問(wèn)題的結(jié)果去找對(duì)偶問(wèn)題的答案4.如何將原問(wèn)題轉(zhuǎn)化成對(duì)偶問(wèn)題5.對(duì)偶規(guī)劃的基本性質(zhì)35第35頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月36任何一個(gè)求極大化的線性規(guī)劃問(wèn)題都有一個(gè)求極小化的線性規(guī)劃問(wèn)題與之對(duì)應(yīng)，反之亦然，如果我們把其中一個(gè)叫原問(wèn)題，則另一個(gè)就叫做它的對(duì)偶問(wèn)題，并稱這一對(duì)互相聯(lián)系的兩個(gè)問(wèn)題為一對(duì)對(duì)偶問(wèn)題。例題1

某工廠在計(jì)劃期內(nèi)安排Ⅰ、Ⅱ兩種產(chǎn)品，生產(chǎn)單位產(chǎn)品所需設(shè)備A、B、C臺(tái)時(shí)如表所示

該工廠每生產(chǎn)一單位產(chǎn)品可獲利50元，每生產(chǎn)一單位產(chǎn)品Ⅱ可獲利100元，問(wèn)工廠應(yīng)分別生產(chǎn)多少產(chǎn)品和Ⅱ產(chǎn)品，才能使工廠獲利最多？解：設(shè)為產(chǎn)品的計(jì)劃產(chǎn)量，為產(chǎn)品Ⅱ的計(jì)劃產(chǎn)量，則有目標(biāo)函數(shù)：Maxz=50X1+100x2約束條件：

，§2線性規(guī)劃的對(duì)偶問(wèn)題第36頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月37

現(xiàn)在我們從另一個(gè)角度來(lái)考慮這個(gè)問(wèn)題。假如有另外一個(gè)工廠要求租用該廠的設(shè)備A、B、C，那么該廠的廠長(zhǎng)應(yīng)該如何來(lái)確定合理的租金呢？設(shè)分別為設(shè)備A、B、C的每臺(tái)時(shí)的租金。租金定價(jià)的原則是：出租者：生產(chǎn)一個(gè)單位的產(chǎn)品需消耗1個(gè)單位的設(shè)備A、2個(gè)單位的設(shè)備B、0個(gè)單位的設(shè)備C，獲利50個(gè)單位；那么，將這些資源（設(shè)備臺(tái)時(shí)）全部轉(zhuǎn)讓時(shí)所獲得的利潤(rùn)應(yīng)不少于50個(gè)單位，否則就不出租還是用于生產(chǎn)產(chǎn)品以獲利50元；同樣把生產(chǎn)一個(gè)單位產(chǎn)品所需各設(shè)備的臺(tái)時(shí)的總租金也不應(yīng)當(dāng)?shù)陀谠麧?rùn)100元，即，否則這些設(shè)備臺(tái)時(shí)就不出租，還是用于生產(chǎn)產(chǎn)品以獲利100元?！?線性規(guī)劃的對(duì)偶問(wèn)題第37頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月對(duì)于租用者，他要求在滿足上述要求的前提下，也就是在出租者愿意出租的前提下盡量要求全部設(shè)備臺(tái)時(shí)的總租金越低越好，即min，這樣我們得到了該問(wèn)題的數(shù)學(xué)模型：

目標(biāo)函數(shù)：約束條件：這樣從兩個(gè)不同的角度來(lái)考慮同一個(gè)工廠的最大利潤(rùn)（最小租金）的問(wèn)題，所建立起來(lái)的兩個(gè)線性模型就是一對(duì)對(duì)偶問(wèn)題，其中一個(gè)叫做原問(wèn)題，而另外一個(gè)叫對(duì)偶問(wèn)題。38第38頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月39

如果我們把求目標(biāo)函數(shù)最大值的線性規(guī)劃問(wèn)題看成原問(wèn)題，則求目標(biāo)函數(shù)最小值的線性規(guī)劃問(wèn)題看成對(duì)偶問(wèn)題。下面來(lái)研究這兩個(gè)問(wèn)題在數(shù)學(xué)模型上的關(guān)系。

1求目標(biāo)函數(shù)最大值的線性規(guī)劃問(wèn)題中有n個(gè)變量m個(gè)約束條件，它的約束條件都是小于等于不等式。而其對(duì)偶則是求目標(biāo)函數(shù)為最小值的線性規(guī)劃問(wèn)題，有m個(gè)變量n個(gè)約束條件，其約束條件都為大于等于不等式。

2原問(wèn)題的目標(biāo)函數(shù)中的變量系數(shù)為對(duì)偶問(wèn)題中的約束條件的右邊常數(shù)項(xiàng)，并且原問(wèn)題的目標(biāo)函數(shù)中的第i個(gè)變量的系數(shù)就等于對(duì)偶問(wèn)題中的第i個(gè)約束條件的右邊常數(shù)項(xiàng)。

3原問(wèn)題的約束條件的右邊常數(shù)項(xiàng)為對(duì)偶問(wèn)題的目標(biāo)函數(shù)中的變量的系數(shù)。并且原問(wèn)題的第i個(gè)約束條件的右邊常數(shù)項(xiàng)就等于零對(duì)偶問(wèn)題的目標(biāo)函數(shù)中的第i個(gè)變量的系數(shù)。

§2線性規(guī)劃的對(duì)偶問(wèn)題第39頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月4對(duì)偶問(wèn)題的約束條件的系數(shù)矩陣A是原問(wèn)題約束矩陣的轉(zhuǎn)置。

設(shè)

A=則

40第40頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月41如果我們用矩陣形式來(lái)表示，則有原問(wèn)題：

其中A是矩陣m*n，該問(wèn)題有m個(gè)約束條件n個(gè)變量，x=,b=,c=

對(duì)偶問(wèn)題：

其中是A的轉(zhuǎn)置，是b的轉(zhuǎn)置,是c的轉(zhuǎn)置,y=現(xiàn)在我們用單純形法求對(duì)偶問(wèn)題的解?！?線性規(guī)劃的對(duì)偶問(wèn)題第41頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月42

加上剩余變量和人工變量，把此問(wèn)題化成標(biāo)準(zhǔn)型如下：把上述數(shù)據(jù)填入單純形表計(jì)算?！?線性規(guī)劃的對(duì)偶問(wèn)題第42頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月43迭代變量基變量b比值-300-400-25000-M

1-M1②0-1015050/2-2501110-10100100/1-M-250-2M-250-250M250-M-50M-25000M-2502M-1500-M-25002-4001/210-1/201/225-2501/2011/2-1-1/275-325-400-25075250-75-287502500-75-250-M+753-300120-10150-2500-111-1-150-300-350-25050250-50-275000-500-50-250-M+50§2線性規(guī)劃的對(duì)偶問(wèn)題第43頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月

由上表，最優(yōu)解：=50，

-f的最大值為-27500，即目標(biāo)函數(shù)f的最大值為f=27500元。從上面可知租金：A設(shè)備為50元，B設(shè)備為0元，C設(shè)備為50元。這樣把工廠的所有設(shè)備出租可共得租金27500元。對(duì)出租者來(lái)說(shuō)這租金是出租者愿意出租設(shè)備的最小費(fèi)用，因?yàn)檫@是目標(biāo)函數(shù)的最小值。通過(guò)比較，我們發(fā)現(xiàn)：對(duì)偶問(wèn)題的最優(yōu)解即最佳租金恰好等于原問(wèn)題各種設(shè)備的對(duì)偶價(jià)格。對(duì)于兩個(gè)有對(duì)偶關(guān)系的線性規(guī)劃的問(wèn)題，我們只要求得了其中一個(gè)最優(yōu)解，就可以從這個(gè)問(wèn)題的對(duì)偶價(jià)格而求得其對(duì)偶問(wèn)題的最優(yōu)解，知道其中一個(gè)最優(yōu)值也就找到了其對(duì)偶問(wèn)題的最優(yōu)值，因?yàn)檫@兩個(gè)最優(yōu)值相等。

44§2線性規(guī)劃的對(duì)偶問(wèn)題第44頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月45

下面來(lái)闡述如何寫出一個(gè)線性規(guī)劃問(wèn)題的對(duì)偶問(wèn)題。為了便于闡述，我們不妨以下面的線性規(guī)劃為例，寫出它的對(duì)偶問(wèn)題。

S.T.

§2線性規(guī)劃的對(duì)偶問(wèn)題第45頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月46

這是一個(gè)求最大值的線性規(guī)劃問(wèn)題，為了寫出它的對(duì)偶問(wèn)題，我們不妨把它的約束條件都變換成取小于號(hào)的不等式。顯然第一個(gè)約束條件已符合要求，不要做任何變動(dòng)，而第二個(gè)約束條件，我們只要兩邊都乘以（-1），使不等號(hào)方向改變即可，得

這樣第二個(gè)約束條件也就符合要求。對(duì)于第三個(gè)約束條件，我們可以用小于等于和大于等于兩個(gè)約束條件來(lái)替代它。即有

顯然，這兩個(gè)約束條件與原來(lái)第三個(gè)約束條件是等價(jià)的，我們?cè)侔哑渲械膬蛇叾汲艘裕?1），得

§2線性規(guī)劃的對(duì)偶問(wèn)題第46頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月47

通過(guò)上面的一些變換，我們得到了一個(gè)和原線性規(guī)劃等價(jià)的線性規(guī)劃問(wèn)題：

s.t.

§2線性規(guī)劃的對(duì)偶問(wèn)題第47頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月48

這個(gè)求最大值的線性規(guī)劃問(wèn)題的約束條件都取小于等于號(hào)，我們馬上可以寫出其對(duì)偶問(wèn)題：

s.t.§2線性規(guī)劃的對(duì)偶問(wèn)題第48頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月49

這里和一樣都是不同的決策變量，為了表示這兩個(gè)決策變量都來(lái)源于原問(wèn)題的第三個(gè)約束條件，記為。因?yàn)樵谠搶?duì)偶問(wèn)題中和的系數(shù)只相差一個(gè)符號(hào)，我們可以把上面的對(duì)偶問(wèn)題化為：

s.t.§2線性規(guī)劃的對(duì)偶問(wèn)題第49頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月50

進(jìn)一步，我們可以令，這時(shí)當(dāng)時(shí)，，當(dāng)時(shí)，。這也就是說(shuō)，盡管但的取值可以為正，可以為0，可以為負(fù)，即沒(méi)有非負(fù)限制。這樣我們把原規(guī)劃的對(duì)偶問(wèn)題化為

s.t.

沒(méi)有限制。對(duì)照原線性規(guī)劃問(wèn)題，我們可以知道：當(dāng)原線性規(guī)劃問(wèn)題的第i個(gè)約束條件取等號(hào)時(shí)，則其對(duì)偶問(wèn)題的i個(gè)決策變量沒(méi)有非負(fù)限制。如果當(dāng)原線性規(guī)劃問(wèn)題中的第i個(gè)決策變量沒(méi)有非負(fù)限制時(shí)，我們也可以用進(jìn)行替換，這里，，用類似的方法知道其對(duì)偶問(wèn)題中第i個(gè)約束條件取等號(hào)?！?線性規(guī)劃的對(duì)偶問(wèn)題第50頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月51

原線性規(guī)劃問(wèn)題為：

s.t.

無(wú)非負(fù)限制。§2線性規(guī)劃的對(duì)偶問(wèn)題第51頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月上節(jié)回顧1.對(duì)偶問(wèn)題的定義任何一個(gè)求極大化的線性規(guī)劃問(wèn)題都有一個(gè)求極小化的線性規(guī)劃問(wèn)題與之對(duì)應(yīng)，反之亦然，如果我們把其中一個(gè)叫原問(wèn)題，則另一個(gè)就叫做它的對(duì)偶問(wèn)題，并稱這一對(duì)互相聯(lián)系的兩個(gè)問(wèn)題為一對(duì)對(duì)偶問(wèn)題。2.原問(wèn)題與對(duì)偶問(wèn)題的關(guān)系a求目標(biāo)函數(shù)最大值的線性規(guī)劃問(wèn)題中有n個(gè)變量m個(gè)約束條件，它的約束條件都是小于等于不等式。而其對(duì)偶則是求目標(biāo)函數(shù)為最小值的線性規(guī)劃問(wèn)題，有m個(gè)變量n個(gè)約束條件，其約束條件都為大于等于不等式。b原問(wèn)題的目標(biāo)函數(shù)中的變量系數(shù)為對(duì)偶問(wèn)題中的約束條件的右邊常數(shù)項(xiàng)。c原問(wèn)題的約束條件的右邊常數(shù)項(xiàng)為對(duì)偶問(wèn)題的目標(biāo)函數(shù)中的變量的系數(shù)。d對(duì)偶問(wèn)題的約束條件的系數(shù)矩陣A是原問(wèn)題約束矩陣的轉(zhuǎn)置。52第52頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月3.如何根據(jù)原問(wèn)題的結(jié)果去找對(duì)偶問(wèn)題的答案對(duì)于兩個(gè)有對(duì)偶關(guān)系的線性規(guī)劃的問(wèn)題，我們只要求得了其中一個(gè)最優(yōu)解，就可以從這個(gè)問(wèn)題的對(duì)偶價(jià)格而求得其對(duì)偶問(wèn)題的最優(yōu)解，知道其中一個(gè)最優(yōu)值也就找到了其對(duì)偶問(wèn)題的最優(yōu)值4.如何將原問(wèn)題轉(zhuǎn)化成對(duì)偶問(wèn)題當(dāng)原線性規(guī)劃問(wèn)題的第i個(gè)約束條件取等號(hào)時(shí)，則其對(duì)偶問(wèn)題的i個(gè)決策變量沒(méi)有非負(fù)限制。如果當(dāng)原線性規(guī)劃問(wèn)題中的第i個(gè)決策變量沒(méi)有非負(fù)限制時(shí)，其對(duì)偶問(wèn)題中第i個(gè)約束條件取等號(hào)。5.對(duì)偶規(guī)劃的基本性質(zhì)53第53頁(yè)，課件共59頁(yè)，創(chuàng)作于2023年2月§3對(duì)偶規(guī)劃的基本性質(zhì)對(duì)偶規(guī)劃的基本性質(zhì)1．對(duì)稱性。即對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。2．弱對(duì)偶性。即對(duì)于原問(wèn)題（Ⅰ）和對(duì)偶問(wèn)題（Ⅱ）的可行解都有C≤bT

。由弱對(duì)偶性，可得出以下推論：（1）原問(wèn)題任一可行解的目標(biāo)函數(shù)值是其對(duì)偶問(wèn)題目標(biāo)函數(shù)值的下界；反之對(duì)偶問(wèn)題任一可行解的目標(biāo)函數(shù)值是其原問(wèn)題目標(biāo)函數(shù)值的上界。（2）如原問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界（或具有無(wú)界解），則其對(duì)偶問(wèn)題無(wú)可行解；反之對(duì)偶問(wèn)題有可行解且目標(biāo)函數(shù)值無(wú)界，則其原問(wèn)題無(wú)可行解（注意：本點(diǎn)性質(zhì)的逆不成立，當(dāng)對(duì)偶問(wèn)題無(wú)可行解時(shí)，其原問(wèn)題或具有無(wú)界解或無(wú)可行解，反之亦然）。（3）若原問(wèn)題有可行解而其對(duì)偶問(wèn)題無(wú)可行解，則原問(wèn)題目標(biāo)函數(shù)值無(wú)界；反之對(duì)偶問(wèn)題有可行解而其原問(wèn)題無(wú)可行解，則對(duì)偶問(wèn)題的目標(biāo)函數(shù)值無(wú)界。54第54