運籌學基礎對偶線性規(guī)劃第1頁，共37頁，2023年，2月20日，星期日一、對偶線性規(guī)劃問題

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

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

Ⅱ設備128臺時原材料A4016Kg原材料B0412Kg每單位產品利潤（萬元）23原問題的模型第3頁，共37頁，2023年，2月20日，星期日

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

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

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

……….mnmnmmbxaxaxa￡+++...22110,...,,213nxxx相應的對偶問題的一般模型可定義為：

mmybybybS+++=...min2211

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

………

nmmnnncyayaya3+++...22110,...,,213myyy第8頁，共37頁，2023年，2月20日，星期日

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

(P)maxZ=cx

s.t.Ax≤b

x≥0其中),..,,(21myyyy=上述的對偶模型都稱作為對稱型對偶模型。而在當原問題轉化為標準型以后所建立的對偶模型則是非對稱型的，如：

(P)maxZ=cx

s.t.Ax=b

x≥0s.t.yAy≥

c≥0(D)minS=ybs.t.yA≥cy為自由變量(D)minS=yb原問題與對偶問題的矩陣形式問題：如何由原模型寫出對偶模型？其規(guī)律是什么?第9頁，共37頁，2023年，2月20日，星期日三、原問題與對偶問題的對應關系當我們討論對偶問題時必定是指一對問題，因為沒有原問題也就不可能有對偶問題。原問題和對偶問題總是相依存在的。同時，原問題和對偶問題之間也并沒有嚴格的界線，它們互為對偶，誰都可以是原問題，誰也都可以是對偶問題。下列的表給出了原問題模型和模型的對應關系，這些也可以看作是一個線性規(guī)劃原問題轉化為對偶問題的一般規(guī)律。原問題線性規(guī)劃模型對偶線性規(guī)劃模型第10頁，共37頁，2023年，2月20日，星期日原問題為maxZ的線性規(guī)劃問題對偶關系表原問題（或對偶問題）

對偶問題（或原問題）

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

n個變量

m個約束

約束條件限定向量（右邊項）

目標函數(shù)價值向量（系數(shù)）

≥

0

變量

≤0≥

無限制

約束

≤

＝

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

n個約束

m個變量

目標函數(shù)價值向量（系數(shù)）

約束條件限定向量（右邊項）

≥

約束

≤

≤0

＝

變量

≥0

無限制

同號反號第11頁，共37頁，2023年，2月20日，星期日原問題 對偶問題目標函數(shù)max

目標函數(shù)min 原問題(maxZ)與對偶之關系：原問題(maxZ)口訣:約束決定變量是反號原問題(maxZ)口訣:變量決定約束是同號第12頁，共37頁，2023年，2月20日，星期日解：由原模型三個約束條件確定對偶模型有三個變量y1,y2,y3（還可依對偶問題寫出原問題）例1寫出下列問題的對偶問題：變量決定約束是同號,約束決定變量是反號

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第13頁，共37頁，2023年，2月20日，星期日原問題為minS的線性規(guī)劃問題對偶關系表原問題（或對偶問題）對偶問題（或原問題）目標函數(shù)最小化(minS)

n個變量

m個約束

約束條件限定向量（右邊項）目標函數(shù)價值向量

≥

0

變量≤0≥無限制

約束≤

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

n個約束

m個變量

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

≤

約束≥

≥0

＝

變量≤0無限制

同號反號第14頁，共37頁，2023年，2月20日，星期日原問題 對偶問題目標函數(shù)min

目標函數(shù)max 原問題(minS)與對偶之關系：原問題(minS)口訣:約束決定變量是同號原問題(minS)口訣:變量決定約束是反號第15頁，共37頁，2023年，2月20日，星期日解：由原模型三個約束條件確定對偶模型有三個變量y1,y2,y332134maxyyyZ+-=s.t.1232

1￡--yy2y-332

1￡

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

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

1￡+

x

xx1,x2,x3

30變量決定約束是反號,約束決定變量是同號01￡y，02￡y03￡y，第16頁，共37頁，2023年，2月20日，星期日練習：試求下列線性規(guī)劃問題的對偶問題321342maxxxxZ-+=

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

第17頁，共37頁，2023年，2月20日，星期日練習：試求下列線性規(guī)劃問題的對偶問題

答案：321342maxxxxZ-+=

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

3218510minyyyS+-=s.t.233213+-yyy424321￡++-yyy353321-=--yyy013y，03￡y第18頁，共37頁，2023年，2月20日，星期日練習：試求下列線性規(guī)劃問題的對偶問題

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

2y1+2y2

+y3≤

3-3y1+y3≤

-5

y1-y2+y3＝1

y1≥

0,y2,y3≤

0

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

定理5（強對偶定理）設X*是原問題的可行解，Y*是對偶問題的可行解，當CX*=Y*b時，X*與Y*是最優(yōu)解。若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解，且目標函數(shù)值相等綜合上述結論得原問題與對偶問題的解的關系一般是：cx≤yb第21頁，共37頁，2023年，2月20日，星期日

對偶問題有最優(yōu)解無界無可行解原有最優(yōu)解一定不可能不可能問無界不可能不可能一定題無可行解不可能可能可能原問題與對偶問題解的對應關系由原問題與對偶問題的解的關系可以判定線性規(guī)劃的解。第22頁，共37頁，2023年，2月20日，星期日例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應用如上關系求解線性規(guī)劃問題試用對偶理論證明上述規(guī)劃問題無最優(yōu)解。由第一約束條件可知對偶問題無可行解，則原問題的解無界或無可行解，由于原問題存在可行解，所以解無界。表2：原問題與對偶問題解的對應關系對偶問題有最優(yōu)解無界無可行解原有最優(yōu)解一定不可能不可能問無界不可能不可能一定題無可行解不可能可能可能[解]該問題存在可行解，如X=(0，0，0)；其對偶問題為：對偶問題無可行解第23頁，共37頁，2023年，2月20日，星期日定理6（互補松弛定理）在線性規(guī)劃問題的最優(yōu)解中，如果對應某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；反之如果約束條件取嚴格不等式，則其對應的對偶變量一定為零。注：證明過程參見教材59頁性質5證明第24頁，共37頁，2023年，2月20日，星期日討論:互補松弛定理也稱松緊定理，它描述了線性規(guī)劃達到最優(yōu)時，原問題（或對偶問題）的變量取值和對偶問題（或原問題）約束松緊之間的對應關系。當線性規(guī)劃問題達到最優(yōu)時，我們不僅同時得到了原問題和對偶問題的最優(yōu)解，而且也還得到了變量和約束之間的一種對應關系?；パa松弛定理即揭示了這一點。第25頁，共37頁，2023年，2月20日，星期日1.如果原問題的某一約束為緊約束（嚴格等式:松弛變量為零），該約束對應的對偶變量應大于或等于零；2.如果原問題的某一約束為松約束（嚴格不等式:松弛變量大于零），則對應的對偶變量必為零；3.如果原問題的某一變量大于零該變量對應的對偶約束必為緊約束(嚴格等式)；4.如果原問題的某一變量等于零，該變量對應的對偶約束可能是緊約束(嚴格等式)，也可能是松約束(嚴格不等式)。線性規(guī)劃達到最優(yōu)時的關系第26頁，共37頁，2023年，2月20日，星期日例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解：寫出對偶問題為：

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

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

3y1+y2≤3⑤

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

＞0，故原問題的兩個約束必為緊約束，即x1+3x5=42x1+x5=3解得：x1=x5=1。maxZ=5=minS=5得原問題的最優(yōu)解X*=(1,0,0,0,1)minS=5第27頁，共37頁，2023年，2月20日，星期日

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）附練習答案：y1=4/5,y2=3/5,y3=1,y4=0已知原問題的最優(yōu)解為:X*=(2,2,4,0)T，試根據互補松弛定理解出其對偶問題的最優(yōu)解。線性規(guī)劃問題的對偶問題為：

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）練習：已知線性規(guī)劃問題為：第28頁，共37頁，2023年，2月20日，星期日④為嚴格不等式，由互補松弛定知，必有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ōu)解為:X*=(2,2,4,0)T：又因x1,x2,x3＞0，故對偶問題的前三個約束必為緊約束線性規(guī)劃問題的對偶問題為：

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等號第29頁，共37頁，2023年，2月20日，星期日（1）寫出對偶問題；（2）已知原問題的最優(yōu)解為X*=（2，0，1，1）T，求對偶問題的最優(yōu)解。已知線性規(guī)劃問題第30頁，共37頁，2023年，2月20日，星期日定理7結論：用單純形法求解線性規(guī)劃時，迭代的每一步在得到原問題一個基本可行解的同時，其：

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

；第31頁，共37頁，2023年，2月20日，星期日用單純形法同時求解原問題和對偶問題

原問題是：

maxZ=2x1+x25x2≤15

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

x1,x2≥0原問題的標準型是：

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

+0x5

5x2

+x3=156x1+2x2

+x4=24x1+x2

+x5=5

xi≥0第32頁，共37頁，2023年，2月20日，星期日

Cj比值CBXBb檢驗數(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原問題變量原問題松馳變量對偶問題剩余變量y4、y5對偶問題變量y1、y2、y3得原問題可行解:X=(0,0,15,24,5)T對偶問題解:Y*=(0,0,0,-2,-1)T檢驗數(shù)行的－

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

；第33頁，共37頁，2023年，2月20日，星期日

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

；第34頁，共37頁，2023年，2月20日，星期日變換單純形表Cj比值CBXBb檢驗數(shù)