運(yùn)籌學(xué)基礎(chǔ)對(duì)偶線性規(guī)劃

運(yùn)籌學(xué)基礎(chǔ)對(duì)偶線性規(guī)劃第一頁(yè)，共三十七頁(yè)，編輯于2023年，星期三一、對(duì)偶線性規(guī)劃問題

某工廠計(jì)劃安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知每種單位產(chǎn)品的利潤(rùn)、生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及A、B兩種原材料的消耗、現(xiàn)有原材料和設(shè)備臺(tái)時(shí)的定額如下表所示：【例1】Ⅰ

Ⅱ設(shè)備128臺(tái)時(shí)原材料A4016Kg原材料B0412Kg每單位產(chǎn)品利潤(rùn)（萬元）23原問題的策略:問應(yīng)如何安排生產(chǎn)才能使工廠獲利最大？現(xiàn)在的策略:假設(shè)不生產(chǎn)Ⅰ、Ⅱ產(chǎn)品,而是計(jì)劃將現(xiàn)有資源出租或出售,從而獲得利潤(rùn),這時(shí)需要考慮如何定價(jià)才合理?第二頁(yè)，共三十七頁(yè)，編輯于2023年，星期三設(shè)x1、x2分別表示計(jì)劃生產(chǎn)產(chǎn)品Ⅰ、Ⅱ的單位數(shù)量，由題意原問題的模型為：工廠獲得最大利潤(rùn)符合資源限制Ⅰ

Ⅱ設(shè)備128臺(tái)時(shí)原材料A4016Kg原材料B0412Kg每單位產(chǎn)品利潤(rùn)（萬元）23原問題的模型第三頁(yè)，共三十七頁(yè)，編輯于2023年，星期三

改變策略后，需要考慮如何給資源定價(jià)的問題！設(shè)y1、y2、y3分別表示出租單位設(shè)備臺(tái)時(shí)的租金和出售單位原材料A、B的利潤(rùn).y1+4y2≥2，2y1+4y3≥3則：工廠出租設(shè)備、原材料的租金要大于生產(chǎn)的利潤(rùn)才合算。工廠把所有設(shè)備臺(tái)時(shí)和資源都出租和出讓，其收入為：要尋找使租用者支付的租金最少的策略。Ⅰ

Ⅱ設(shè)備128臺(tái)時(shí)原材料A4016Kg原材料B0412Kg每單位產(chǎn)品利潤(rùn)（萬元）23新問題的模型第四頁(yè)，共三十七頁(yè)，編輯于2023年，星期三工廠改變策略以后的數(shù)學(xué)模型為：工廠獲得相應(yīng)利潤(rùn)用戶所付租金最少第五頁(yè)，共三十七頁(yè)，編輯于2023年，星期三聯(lián)系在于，它們都是關(guān)于工廠生產(chǎn)經(jīng)營(yíng)的模型,并且使用相同的數(shù)據(jù)；原模型和對(duì)偶模型既有聯(lián)系又有區(qū)別區(qū)別在于,它們所反映的實(shí)質(zhì)內(nèi)容是完全不同的：前者是站在工廠經(jīng)營(yíng)者的立場(chǎng)上追求工廠的銷售收入最大，而后者則是站在談判對(duì)手的立場(chǎng)上尋求應(yīng)付工廠租金最少的策略。第六頁(yè)，共三十七頁(yè)，編輯于2023年，星期三所謂對(duì)偶規(guī)劃，就是與線性規(guī)劃原問題相對(duì)應(yīng)并使用同一組數(shù)據(jù)按照特定方法形成的另一種反映不同性質(zhì)問題的線性規(guī)劃模型。第七頁(yè)，共三十七頁(yè)，編輯于2023年，星期三

原模型與對(duì)偶模型有很多的內(nèi)在聯(lián)系和相似之處。如原問題如求目標(biāo)函數(shù)最大化，對(duì)偶問題即求目標(biāo)函數(shù)最小化；原問題目標(biāo)函數(shù)的系數(shù)變成為對(duì)偶問題的右邊項(xiàng)，而原問題的約束的右邊項(xiàng)則變成為對(duì)偶問題目標(biāo)函數(shù)的系數(shù)；對(duì)偶問題的系數(shù)矩陣是原問題系數(shù)矩陣的轉(zhuǎn)置。就象一個(gè)人對(duì)著鏡子會(huì)左右顛倒一樣，原問題與對(duì)偶問題之間存在著嚴(yán)格的對(duì)應(yīng)關(guān)系。原問題的一般模型可定義為：二、對(duì)偶規(guī)劃的一般數(shù)學(xué)模型nnxcxcxcZ+++=...max2211s.t.11212111...bxaxaxann￡+++22222121...bxaxaxann￡+++

……….mnmnmmbxaxaxa￡+++...22110,...,,213nxxx相應(yīng)的對(duì)偶問題的一般模型可定義為：

mmybybybS+++=...min2211

s.t.11221111...cyayayamm3+++22222112...cyayayamm3+++

………

nmmnnncyayaya3+++...22110,...,,213myyy第八頁(yè)，共三十七頁(yè)，編輯于2023年，星期三

上述的原問題P和對(duì)偶問題D還可以用矩陣形式寫為：

(P)maxZ=cx

s.t.Ax≤b

x≥0其中),..,,(21myyyy=上述的對(duì)偶模型都稱作為對(duì)稱型對(duì)偶模型。而在當(dāng)原問題轉(zhuǎn)化為標(biāo)準(zhǔn)型以后所建立的對(duì)偶模型則是非對(duì)稱型的，如：

(P)maxZ=cx

s.t.Ax=b

x≥0s.t.yAy≥

c≥0(D)minS=ybs.t.yA≥cy為自由變量(D)minS=yb原問題與對(duì)偶問題的矩陣形式問題：如何由原模型寫出對(duì)偶模型？其規(guī)律是什么?第九頁(yè)，共三十七頁(yè)，編輯于2023年，星期三三、原問題與對(duì)偶問題的對(duì)應(yīng)關(guān)系當(dāng)我們討論對(duì)偶問題時(shí)必定是指一對(duì)問題，因?yàn)闆]有原問題也就不可能有對(duì)偶問題。原問題和對(duì)偶問題總是相依存在的。同時(shí)，原問題和對(duì)偶問題之間也并沒有嚴(yán)格的界線，它們互為對(duì)偶，誰都可以是原問題，誰也都可以是對(duì)偶問題。下列的表給出了原問題模型和模型的對(duì)應(yīng)關(guān)系，這些也可以看作是一個(gè)線性規(guī)劃原問題轉(zhuǎn)化為對(duì)偶問題的一般規(guī)律。原問題線性規(guī)劃模型對(duì)偶線性規(guī)劃模型第十頁(yè)，共三十七頁(yè)，編輯于2023年，星期三原問題為maxZ的線性規(guī)劃問題對(duì)偶關(guān)系表原問題（或?qū)ε紗栴}）

對(duì)偶問題（或原問題）

目標(biāo)函數(shù)最大化(maxZ)

n個(gè)變量

m個(gè)約束

約束條件限定向量（右邊項(xiàng)）

目標(biāo)函數(shù)價(jià)值向量（系數(shù)）

≥

0

變量

≤0≥

無限制

約束

≤

＝

目標(biāo)函數(shù)最小化（minS）

n個(gè)約束

m個(gè)變量

目標(biāo)函數(shù)價(jià)值向量（系數(shù)）

約束條件限定向量（右邊項(xiàng)）

≥

約束

≤

≤0

＝

變量

≥0

無限制

同號(hào)反號(hào)第十一頁(yè)，共三十七頁(yè)，編輯于2023年，星期三原問題 對(duì)偶問題目標(biāo)函數(shù)max

目標(biāo)函數(shù)min 原問題(maxZ)與對(duì)偶之關(guān)系：原問題(maxZ)口訣:約束決定變量是反號(hào)原問題(maxZ)口訣:變量決定約束是同號(hào)第十二頁(yè)，共三十七頁(yè)，編輯于2023年，星期三解：由原模型三個(gè)約束條件確定對(duì)偶模型有三個(gè)變量y1,y2,y3（還可依對(duì)偶問題寫出原問題）例1寫出下列問題的對(duì)偶問題：變量決定約束是同號(hào),約束決定變量是反號(hào)

maxZ=2x1+x25x2≤

156x1+2x2≤

24x1+x2≤

5

x1,x2≥

0

minw=15y1+24y2+5y3

6y2+y3≥

2s.t.y1,y2,y3≥

0

5y1+2y2

+y3≥1第十三頁(yè)，共三十七頁(yè)，編輯于2023年，星期三原問題為minS的線性規(guī)劃問題對(duì)偶關(guān)系表原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）目標(biāo)函數(shù)最小化(minS)

n個(gè)變量

m個(gè)約束

約束條件限定向量（右邊項(xiàng)）目標(biāo)函數(shù)價(jià)值向量

≥

0

變量≤0≥無限制

約束≤

＝目標(biāo)函數(shù)最大化（maxZ）

n個(gè)約束

m個(gè)變量

目標(biāo)函數(shù)價(jià)值向量（系數(shù)）約束條件限定向量

≤

約束≥

≥0

＝

變量≤0無限制

同號(hào)反號(hào)第十四頁(yè)，共三十七頁(yè)，編輯于2023年，星期三原問題 對(duì)偶問題目標(biāo)函數(shù)min

目標(biāo)函數(shù)max 原問題(minS)與對(duì)偶之關(guān)系：原問題(minS)口訣:約束決定變量是同號(hào)原問題(minS)口訣:變量決定約束是反號(hào)第十五頁(yè)，共三十七頁(yè)，編輯于2023年，星期三解：由原模型三個(gè)約束條件確定對(duì)偶模型有三個(gè)變量y1,y2,y332134maxyyyZ+-=s.t.1232

1￡--yy2y-332

1￡

+-y4y42321￡++yyy（還可依對(duì)偶問題寫出原問題）例2寫出下列問題的對(duì)偶問題：32143MinxxxS+-=

s.t.1321￡+-4xx2x423321-￡++-xxx3-23

1￡+

x

xx1,x2,x3

30變量決定約束是反號(hào),約束決定變量是同號(hào)01￡y，02￡y03￡y，第十六頁(yè)，共三十七頁(yè)，編輯于2023年，星期三練習(xí)：試求下列線性規(guī)劃問題的對(duì)偶問題321342maxxxxZ-+=

s.t.10321￡+-xxx534321-=-+-xxx85233213-+xxx013x，02￡x

第十七頁(yè)，共三十七頁(yè)，編輯于2023年，星期三練習(xí)：試求下列線性規(guī)劃問題的對(duì)偶問題

答案：321342maxxxxZ-+=

s.t.10321￡+-xxx534321-=-+-xxx85233213-+xxx013x，02￡x

3218510minyyyS+-=s.t.233213+-yyy424321￡++-yyy353321-=--yyy013y，03￡y第十八頁(yè)，共三十七頁(yè)，編輯于2023年，星期三練習(xí)：試求下列線性規(guī)劃問題的對(duì)偶問題

maxZ=5y1+4y2+6y3y1+2y2≥

2y1+2y2

+y3≤

3-3y1+y3≤

-5

y1-y2+y3＝1

y1≥

0,y2,y3≤

0

答案：第十九頁(yè)，共三十七頁(yè)，編輯于2023年，星期三線性規(guī)劃的對(duì)偶理論包括以下幾個(gè)基本定理。定理1（對(duì)稱性定理）§2.2線性規(guī)劃的對(duì)偶理論定理2（弱對(duì)偶定理）即對(duì)偶問題的對(duì)偶是原問題。設(shè)x和y分別是原問題和對(duì)偶問題的可行解，則必有cx≤yb，即原問題的目標(biāo)值小于對(duì)偶問題的目標(biāo)值定理3（無界性）若原問題(對(duì)偶問題)為無界解，則其對(duì)偶問題(原問題)無可行解。若原（對(duì)偶）問題有可行解,對(duì)偶（原）問題無可行解，則原（對(duì)偶）問題一定無界；注:此定理可以判定解的情況第二十頁(yè)，共三十七頁(yè)，編輯于2023年，星期三定理4（可行解是最優(yōu)解的性質(zhì)）

定理5（強(qiáng)對(duì)偶定理）設(shè)X*是原問題的可行解，Y*是對(duì)偶問題的可行解，當(dāng)CX*=Y*b時(shí)，X*與Y*是最優(yōu)解。若原問題有最優(yōu)解，那么對(duì)偶問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等綜合上述結(jié)論得原問題與對(duì)偶問題的解的關(guān)系一般是：cx≤yb第二十一頁(yè)，共三十七頁(yè)，編輯于2023年，星期三

對(duì)偶問題有最優(yōu)解無界無可行解原有最優(yōu)解一定不可能不可能問無界不可能不可能一定題無可行解不可能可能可能原問題與對(duì)偶問題解的對(duì)應(yīng)關(guān)系由原問題與對(duì)偶問題的解的關(guān)系可以判定線性規(guī)劃的解。第二十二頁(yè)，共三十七頁(yè)，編輯于2023年，星期三例4已知線性規(guī)劃問題

Maxz=x1+x2S.t.–x1+x2+x3≤2

–

2x1+x2

–x3≤1xi≥0(i=1,2,3)

Minw=2y1+y2S.t.–y1

–2y2≥1①y1+y2≥1②

y1

–y2≥0③

y1,y2≥0應(yīng)用如上關(guān)系求解線性規(guī)劃問題試用對(duì)偶理論證明上述規(guī)劃問題無最優(yōu)解。由第一約束條件可知對(duì)偶問題無可行解，則原問題的解無界或無可行解，由于原問題存在可行解，所以解無界。表2：原問題與對(duì)偶問題解的對(duì)應(yīng)關(guān)系對(duì)偶問題有最優(yōu)解無界無可行解原有最優(yōu)解一定不可能不可能問無界不可能不可能一定題無可行解不可能可能可能[解]該問題存在可行解，如X=(0，0，0)；其對(duì)偶問題為：對(duì)偶問題無可行解第二十三頁(yè)，共三十七頁(yè)，編輯于2023年，星期三定理6（互補(bǔ)松弛定理）在線性規(guī)劃問題的最優(yōu)解中，如果對(duì)應(yīng)某一約束條件的對(duì)偶變量值為非零，則該約束條件取嚴(yán)格等式；反之如果約束條件取嚴(yán)格不等式，則其對(duì)應(yīng)的對(duì)偶變量一定為零。注：證明過程參見教材59頁(yè)性質(zhì)5證明第二十四頁(yè)，共三十七頁(yè)，編輯于2023年，星期三討論:互補(bǔ)松弛定理也稱松緊定理，它描述了線性規(guī)劃達(dá)到最優(yōu)時(shí)，原問題（或?qū)ε紗栴}）的變量取值和對(duì)偶問題（或原問題）約束松緊之間的對(duì)應(yīng)關(guān)系。當(dāng)線性規(guī)劃問題達(dá)到最優(yōu)時(shí)，我們不僅同時(shí)得到了原問題和對(duì)偶問題的最優(yōu)解，而且也還得到了變量和約束之間的一種對(duì)應(yīng)關(guān)系。互補(bǔ)松弛定理即揭示了這一點(diǎn)。第二十五頁(yè)，共三十七頁(yè)，編輯于2023年，星期三1.如果原問題的某一約束為緊約束（嚴(yán)格等式:松弛變量為零），該約束對(duì)應(yīng)的對(duì)偶變量應(yīng)大于或等于零；2.如果原問題的某一約束為松約束（嚴(yán)格不等式:松弛變量大于零），則對(duì)應(yīng)的對(duì)偶變量必為零；3.如果原問題的某一變量大于零該變量對(duì)應(yīng)的對(duì)偶約束必為緊約束(嚴(yán)格等式)；4.如果原問題的某一變量等于零，該變量對(duì)應(yīng)的對(duì)偶約束可能是緊約束(嚴(yán)格等式)，也可能是松約束(嚴(yán)格不等式)。線性規(guī)劃達(dá)到最優(yōu)時(shí)的關(guān)系第二十六頁(yè)，共三十七頁(yè)，編輯于2023年，星期三例5已知線性規(guī)劃問題

MinS=2x1+3x2+5x3+2x4+3x5

S.t.x1+x2+2x3+x4+3x5≥4

2x1–x2+3x3+x4+x5≥3xi≥0(i=1,2,3,4,5)2＝21/5＜317/5＜57/5＜23=3解：寫出對(duì)偶問題為：

MaxZ=4y1+3yS.t.y1+2y2≤2①y1–y2≤3②

2y1+3y2≤5③y1+y2≤2④

3y1+y2≤3⑤

y1,y2≥0又例:應(yīng)用如上關(guān)系求解線性規(guī)劃問題已知對(duì)偶問題的最優(yōu)解為y1=4/5,y2=3/5,試應(yīng)用對(duì)偶理論求解原問題。x2=0x3=0x4=0等號(hào)又因y1,y2

＞0，故原問題的兩個(gè)約束必為緊約束，即x1+3x5=42x1+x5=3解得：x1=x5=1。maxZ=5=minS=5得原問題的最優(yōu)解X*=(1,0,0,0,1)minS=5第二十七頁(yè)，共三十七頁(yè)，編輯于2023年，星期三

Max.Z=2x1+4x2+x3+x4

s.t.x1+3x2+x4≤82x1+x2≤6x2+

x3+x4≤6x1+

x2+x3≤9xj≥0（j=1,2,3,4）附練習(xí)答案：y1=4/5,y2=3/5,y3=1,y4=0已知原問題的最優(yōu)解為:X*=(2,2,4,0)T，試根據(jù)互補(bǔ)松弛定理解出其對(duì)偶問題的最優(yōu)解。線性規(guī)劃問題的對(duì)偶問題為：

Min.Z=8y1+6y2+6y3+9y4

s.t.y1+2y2+y4≥23y1+y2+

y3+y4≥4y3+y4≥1y1

+y3≥1yj≥0（j=1,2,3,4）練習(xí)：已知線性規(guī)劃問題為：第二十八頁(yè)，共三十七頁(yè)，編輯于2023年，星期三④為嚴(yán)格不等式，由互補(bǔ)松弛定知，必有y4=0；

Max.Z=2x1+4x2+x3+x4

s.t.x1+3x2+x4≤82x1+x2≤6x2+

x3+x4≤6x1+

x2+x3≤9xj≥0（j=1,2,3,4）①8=8②6=6③6=6④8<9解之，有：y1=4/5,y2=3/5,y3=1，y4=0答案：因?yàn)樵瓎栴}的最優(yōu)解為:X*=(2,2,4,0)T：又因x1,x2,x3＞0，故對(duì)偶問題的前三個(gè)約束必為緊約束線性規(guī)劃問題的對(duì)偶問題為：

Min.Z=8y1+6y2+6y3+9y4

s.t.y1+2y2+y4≥23y1+y2+

y3+y4≥4y3+y4≥1y1

+y3≥1yj≥0（j=1,2,3,4）

y1+2y2=23y1+y2+

y3=4y3=1等號(hào)第二十九頁(yè)，共三十七頁(yè)，編輯于2023年，星期三（1）寫出對(duì)偶問題；（2）已知原問題的最優(yōu)解為X*=（2，0，1，1）T，求對(duì)偶問題的最優(yōu)解。已知線性規(guī)劃問題第三十頁(yè)，共三十七頁(yè)，編輯于2023年，星期三定理7結(jié)論：用單純形法求解線性規(guī)劃時(shí)，迭代的每一步在得到原問題一個(gè)基本可行解的同時(shí)，其：

線性規(guī)劃原問題及其對(duì)偶問題之間存在一對(duì)互補(bǔ)的基解，其中原問題的松馳變量對(duì)應(yīng)對(duì)偶問題的變量，對(duì)偶問題的剩余變量對(duì)應(yīng)原問題的變量；這些互相對(duì)應(yīng)的變量如果在一個(gè)問題的解中是基變量，則在另一問題的解中是非基變量；將這兩個(gè)解代入各自的目標(biāo)數(shù)中有z=w。注：證明過程參見教材60頁(yè)性質(zhì)6證明檢驗(yàn)數(shù)行的-(cj-zj)值是其對(duì)偶問題的一個(gè)基本解yi

；第三十一頁(yè)，共三十七頁(yè)，編輯于2023年，星期三用單純形法同時(shí)求解原問題和對(duì)偶問題

原問題是：

maxZ=2x1+x25x2≤15

6x1+2x2≤24x1+x2≤5

x1,x2≥0原問題的標(biāo)準(zhǔn)型是：

maxZ=2x1+x2+0x3+0x4

+0x5

5x2

+x3=156x1+2x2

+x4=24x1+x2

+x5=5

xi≥0第三十二頁(yè)，共三十七頁(yè)，編輯于2023年，星期三

Cj比值CBXBb檢驗(yàn)數(shù)jx1x2x3x4x52100015051002462010511001x3x4x5000021000

maxZ=2x1+x2+0x3+0x4

+0x5

5x2

+x3

=15

6x1+2x2

+x4

=24x1+x2

+x5

=5

xi

≥0-24/6=45/1=5原問題變量原問題松馳變量對(duì)偶問題剩余變量y4、y5對(duì)偶問題變量y1、y2、y3得原問題可行解:X=(0,0,15,24,5)T對(duì)偶問題解:Y*=(0,0,0,-2,-1)T檢驗(yàn)數(shù)行的－

(cj-zj)值是其對(duì)偶問題的一個(gè)基本解yi

；第三十三頁(yè)，共三十七頁(yè)，編輯于2023年，星期三

檢驗(yàn)數(shù)j1505100411/301/60102/30-1/61x3x1x5020-801/30-1/303121.5得原問題可行解:X=(4,0,15,0,1)T，此時(shí)Z=8同時(shí)得對(duì)偶問題基礎(chǔ)解:Y*=(0,1/3,0,0,-1/3)T，W=8對(duì)偶問題剩余變量y4、y5對(duì)偶問題變量y1、y2、y3原問題變量原問題松馳變量檢驗(yàn)數(shù)行的-(cj-zj)值是其對(duì)偶問題的一個(gè)基本解yi

；第三十四頁(yè)，共三十七頁(yè)，編輯于2023年，星期三變換單純形表Cj比值CBXBb檢驗(yàn)數(shù)j