對(duì)偶單純形法

對(duì)偶單純形法第一頁(yè)，共二十二頁(yè)，編輯于2023年，星期日

二、對(duì)偶單純形法的基本思想

1、對(duì)“單純形法”求解過(guò)程認(rèn)識(shí)的提升——

從更高的層次理解單純形法

初始可行基（對(duì)應(yīng)一個(gè)初始基本可行解）

→迭代→另一個(gè)可行基（對(duì)應(yīng)另一個(gè)基本可行解），直至所有檢驗(yàn)數(shù)≤0為止。第二頁(yè)，共二十二頁(yè)，編輯于2023年，星期日

所有檢驗(yàn)數(shù)≤0意味著

，說(shuō)明原始問(wèn)題的最優(yōu)基也是對(duì)偶問(wèn)題的可行基。換言之，當(dāng)原始問(wèn)題的基B既是原始可行基又是對(duì)偶可行基時(shí)，B成為最優(yōu)基。定理2-5

B是線性規(guī)劃的最優(yōu)基的充要條件是，B是可行基，同時(shí)也是對(duì)偶可行基。第三頁(yè)，共二十二頁(yè)，編輯于2023年，星期日LP原問(wèn)題:若B是A中的一個(gè)基可行基B對(duì)應(yīng)的解是基本可行解，則B是可行基對(duì)偶可行基若單純形乘子是對(duì)偶問(wèn)題的可行解，則B是對(duì)偶可行基

是對(duì)偶問(wèn)題的可行解檢驗(yàn)數(shù)等價(jià)

第四頁(yè)，共二十二頁(yè)，編輯于2023年，星期日

證明：第五頁(yè)，共二十二頁(yè)，編輯于2023年，星期日單純形法的求解過(guò)程就是：

在保持原始可行的前提下(b列保持≥0)，

通過(guò)逐步迭代實(shí)現(xiàn)對(duì)偶可行(檢驗(yàn)數(shù)行≤0)。

2、

對(duì)偶單純形法思想：

換個(gè)角度考慮LP求解過(guò)程：保持對(duì)偶可行的前提下（檢驗(yàn)數(shù)行保持≤0）

，通過(guò)逐步迭代實(shí)現(xiàn)原始可行（b列≥0，從非可行解變成可行解）。

第六頁(yè)，共二十二頁(yè)，編輯于2023年，星期日對(duì)偶單純形法的思想（圖示）原問(wèn)題初始基本可行解保持為基本可行解初始對(duì)偶可行解保持對(duì)偶可行性最優(yōu)解基本可行性對(duì)偶可行性始終滿足解的可行性始終滿足對(duì)偶可行性第七頁(yè)，共二十二頁(yè)，編輯于2023年，星期日

三、對(duì)偶單純形法的實(shí)施1、使用條件：

①檢驗(yàn)數(shù)全部≤0；

②解答列至少一個(gè)元素

<0；2、實(shí)施對(duì)偶單純形法的基本原則：在保持對(duì)偶可行的前提下進(jìn)行基變換——每一次迭代過(guò)程中取出基變量中的一個(gè)負(fù)分量作為換出變量去替換某個(gè)非基變量(作為換入變量),使原始問(wèn)題的非可行解向可行解靠近。

第八頁(yè)，共二十二頁(yè)，編輯于2023年，星期日3、計(jì)算步驟：

①建立初始單純形表，計(jì)算檢驗(yàn)數(shù)行。解答列≥0——已得最優(yōu)解；至少一個(gè)元素<0,轉(zhuǎn)下步;解答列≥0——原始單純形法；至少一個(gè)元素<0,另外處理；

檢驗(yàn)數(shù)全部≤0（非基變量檢驗(yàn)數(shù)<0）至少一個(gè)檢驗(yàn)數(shù)>0第九頁(yè)，共二十二頁(yè)，編輯于2023年，星期日

基變換：

先確定換出變量——解答列中的負(fù)元素（一般選最小的負(fù)元素）對(duì)應(yīng)的基變量出基；

即相應(yīng)的行為主元行。第十頁(yè)，共二十二頁(yè)，編輯于2023年，星期日然后確定換入變量——原則是：在保持對(duì)偶可行的前提下，減少原始問(wèn)題的不可行性。如果

(最小比值原則),則選

為換入變量

,相應(yīng)的列為主元列

,主元行和主元列交叉處的元素

為主元素。若,要計(jì)算最小比值嗎？為什么？第十一頁(yè)，共二十二頁(yè)，編輯于2023年，星期日

按主元素進(jìn)行換基迭代（旋轉(zhuǎn)運(yùn)算、樞運(yùn)算），將主元素變成1，主元列變成單位向量，得到新的單純形表。

循環(huán)以上步驟，直至求出最優(yōu)解。第十二頁(yè)，共二十二頁(yè)，編輯于2023年，星期日3、舉例——用對(duì)偶單純形法求解LP：

化為標(biāo)準(zhǔn)型

→

將兩個(gè)等式約束兩邊分別乘以-1，得第十三頁(yè)，共二十二頁(yè)，編輯于2023年，星期日以此形式進(jìn)行列表求解，滿足對(duì)偶單純形法的基本條件，具體如下：第十四頁(yè)，共二十二頁(yè)，編輯于2023年，星期日-2/-2----4/-3------

比

值-2-3-4000-Z-1-2-110-21-301-3-4

x4

x5

00

-2-3-400x1x2x3x4x5cjxjbXBCB第十五頁(yè)，共二十二頁(yè)，編輯于2023年，星期日----4/-5/2----1/-1/2

比

值0-4-10-10

cj-zj0-5/21/21-1/21-1/23/20-1/2-12

x4

x1

0-2

-2-3-400x1x2x3x4x5cjxjbXBCB第十六頁(yè)，共二十二頁(yè)，編輯于2023年，星期日00-3/5-8/5-1/50

cj-zj01-1/5-2/51/5107/5-1/5-2/52/511/5

x2

x1

-3-2

-2-3-400x1x2x3x4x5cjxjbXBCB最優(yōu)解:X*=（11/5，2/5,0,0,0）T，最優(yōu)值:minW=-maxZ*=-[11/5×(-2)+2/5×(-3)]=28/5第十七頁(yè)，共二十二頁(yè)，編輯于2023年，星期日4、舉例——用對(duì)偶單純形法求解LP：

化為標(biāo)準(zhǔn)型

→

將三個(gè)等式約束兩邊分別乘以-1，然后列表求解如下：第十八頁(yè)，共二十二頁(yè)，編輯于2023年，星期日-3/-1-9/-1---------

比

值-3-90000-Z-1-1100-1-4010-1-7001-2-3-3y3

y4

y5000-3-9000y1y2y3y4y5cjyjbXBCB第十九頁(yè)，共二十二頁(yè)，編輯于2023年，星期日

----6/-3-3/-1------

比

值0-6-3006-Z11-1000-3-1100-6-1012-1-1

y1

y4

y5

-300-3-9000y1y2y3y4y5cjyjbXBCB第二十頁(yè)，共二十二頁(yè)，編輯于2023年，星期日00-1-208-Z10-4/31/30011/3-1/30001-215/31/31

y1

y2

y5

-3-90-3-9000y1y2y3y4y5cjyj