運(yùn)籌學(xué)對(duì)偶問題

1、No Image 運(yùn)籌學(xué)對(duì)偶問題 第四章第四章 對(duì)偶問題對(duì)偶問題 l對(duì)偶問題的一般形式 l對(duì)偶問題的經(jīng)濟(jì)意義 l對(duì)偶性質(zhì) l對(duì)偶單純形法 l對(duì)偶單純形法的解題原理 No Image 運(yùn)籌學(xué)對(duì)偶問題 一、對(duì)偶問題的一般形式一、對(duì)偶問題的一般形式 l若設(shè)一線性規(guī)劃問題如下 ： （A） 0, 0, 0 . . max 21 2211 22222121 11212111 2211 n mnmnmm nn nn nn xxx bxaxaxa bxaxaxa bxaxaxa ts xcxcxcF No Image 運(yùn)籌學(xué)對(duì)偶問題 則以下線性規(guī)劃問題則以下線性規(guī)劃問題： （B） 稱為原問題（A）的對(duì)偶線性規(guī)

2、劃問題， 或稱A、B互為對(duì)偶問題。 0, 0, 0 . . min 21 2211 22222112 11221111 2211 m nmmnnn mm mm mm yyy cyayaya cyayaya cyayaya ts ybybybW No Image 運(yùn)籌學(xué)對(duì)偶問題 如果采用向量、矩陣來表示如果采用向量、矩陣來表示 0 . . max X BAX ts CXF 0 . . min Y CYA ts YBW T n cccC 21 m yyyY 21 m b b b B 2 1 n x x x X 2 1 mnmn n n aaa aaa aaa A 21 22221 11211 （A

3、） （B） 其中： No Image 運(yùn)籌學(xué)對(duì)偶問題 可以將以上關(guān)系列成以下對(duì)偶表：可以將以上關(guān)系列成以下對(duì)偶表： max min x1x2xnb y1a11a12a1nb1 y2a21a22b2 ymam1am2amnbm cc1c2cn No Image 運(yùn)籌學(xué)對(duì)偶問題 例例 l寫出下列線性規(guī)劃問題的對(duì)偶問題 0, 0, 0 6042 4824 . . 13146max 321 321 321 321 xxx xxx xxx ts xxxF No Image 運(yùn)籌學(xué)對(duì)偶問題 解：解： l可以將原問題的有關(guān)參數(shù)列成下表 max min x1x2x3b y114248 y212460 c614

4、13 No Image 運(yùn)籌學(xué)對(duì)偶問題 對(duì)偶規(guī)劃問題為對(duì)偶規(guī)劃問題為 0, 0 1342 1424 6 . . 6048min 21 21 21 21 21 yy yy yy yy ts yyW No Image 運(yùn)籌學(xué)對(duì)偶問題 比較比較 l以上我們介紹的對(duì)偶問題是嚴(yán)格定義的對(duì)偶問題，也 成為對(duì)稱對(duì)偶問題 。 l它滿足兩個(gè)條件： 0, 0, 0 6042 4824 . . 13146max 321 321 321 321 xxx xxx xxx ts xxxF 0, 0 1342 1424 6 . . 6048min 21 21 21 21 21 yy yy yy yy ts yyW No I

5、mage 運(yùn)籌學(xué)對(duì)偶問題 兩個(gè)條件：兩個(gè)條件： 1、所有變量非負(fù)：即X0，Y0 2、約束條件均為同向不等式。若原問題約束條件均 為“”，則它的對(duì)偶問題的約束條件都是“”。 l當(dāng)原問題的約束條件的符號(hào)不完全相同時(shí)，也存在 對(duì)偶問題，這種對(duì)偶問題稱為非對(duì)稱對(duì)偶問題。 No Image 運(yùn)籌學(xué)對(duì)偶問題 例例 l分析： l為求對(duì)偶問題，可先做過渡，將問題對(duì)稱化： 為自由變量 21 21 21 21 21 ,0 5 1034 2023 . 54max xx xx xx xx ts xxZ No Image 運(yùn)籌學(xué)對(duì)偶問題 對(duì)稱化對(duì)稱化 為自由變量 21 21 21 21 21 , 0 5 1034 20

6、23 . . 54max xx xx xx xx ts xxZ 0 x, 0 x,xxx 5 5 1034 43432 21 21 21 設(shè) xx xx xx 5 21 xx No Image 運(yùn)籌學(xué)對(duì)偶問題 則，原問題變?yōu)閯t，原問題變?yōu)?0, 0, 0 5 5 10334 20223 . . 554max 431 431 431 431 431 431 xxx xxx xxx xxx xxx ts xxxZ 為自由變量 21 21 21 21 21 , 0 5 1034 2023 . . 54max xx xx xx xx ts xxZ （A） （A） No Image 運(yùn)籌學(xué)對(duì)偶問題 則（

7、則（A）的對(duì)偶問題如下：）的對(duì)偶問題如下： 0,0,0,0 532 532 443 . 551020min 4321 4321 4321 4321 4321 yyyy yyyy yyyy yyyy ts yyyyW （B） 0, 0, 0 5 5 10334 20223 . . 554max 431 431 431 431 431 431 xxx xxx xxx xxx xxx ts xxxZ （A） No Image 運(yùn)籌學(xué)對(duì)偶問題 對(duì)比結(jié)果對(duì)比結(jié)果 l以上對(duì)偶問題（B）并非原問題（A）的對(duì)偶問題， 它是線性規(guī)劃問題（A）的對(duì)偶問題。 0, 0, 0, 0 532 532 443 . . 5

8、51020min 4321 4321 4321 4321 4321 yyyy yyyy yyyy yyyy ts yyyyW 為自由變量 21 21 21 21 21 , 0 5 1034 2023 . . 54max xx xx xx xx ts xxZ （A） （B） No Image 運(yùn)籌學(xué)對(duì)偶問題 調(diào)整調(diào)整 l對(duì)照問題B目標(biāo)函數(shù)系數(shù)的符號(hào)與原問題A中 約束條件右端常數(shù)項(xiàng)的符號(hào)，可做以下調(diào)整： l令y1=y1，y2=-y2，y3=y4-y3 No Image 運(yùn)籌學(xué)對(duì)偶問題 令令y1=y1，y2=-y2，y3=y4-y3 則得到以下對(duì)偶問題則得到以下對(duì)偶問題 為自由變量 321 321

9、321 321 321 , 0, 0 532 532 443 . . 51020min yyy yyy yyy yyy ts yyyW 0, 0, 0, 0 532 532 443 . . 551020min 4321 4321 4321 4321 4321 yyyy yyyy yyyy yyyy ts yyyyW （B）（B） No Image 運(yùn)籌學(xué)對(duì)偶問題 合并合并 為自由變量 321 321 321 321 321 , 0, 0 532 532 443 . . 51020min yyy yyy yyy yyy ts yyyW 為自由變量 321 321 321 321 , 0, 0 5

10、32 443 . . 51020min yyy yyy yyy ts yyyW （B） No Image 運(yùn)籌學(xué)對(duì)偶問題 比較比較 l對(duì)于任何一個(gè)線性規(guī)劃問題，我們都可以求出 它的對(duì)偶問題。 為自由變量 21 21 21 21 21 , 0 5 1034 2023 . . 54max xx xx xx xx ts xxZ （A） （B） 為自由變量 321 321 321 321 , 0, 0 532 443 . . 51020min yyy yyy yyy ts yyyW No Image 運(yùn)籌學(xué)對(duì)偶問題 原問題與對(duì)偶問題的相應(yīng)關(guān)系原問題與對(duì)偶問題的相應(yīng)關(guān)系 原問題原問題A A（對(duì)偶問題（對(duì)

11、偶問題B B）對(duì)偶問題對(duì)偶問題B B（原問題（原問題A A） 最大化 max最小化 min A系數(shù)矩陣AT B右端常數(shù)（列向量）目標(biāo)函數(shù)系數(shù)(行向量) C目標(biāo)函數(shù)系數(shù)右端常數(shù)（列向量） 第i個(gè)約束條件為等式“=”yi為自由變量 第i個(gè)約束條件為不等式“”yi0 第i個(gè)約束條件為不等式“”yi0 xj為自由變量第j個(gè)約束條件為等式“=” xj0第j個(gè)約束條件為不等式“” xj0第j個(gè)約束條件為不等式“” No Image 運(yùn)籌學(xué)對(duì)偶問題 例：寫出下列問題的對(duì)偶形式：例：寫出下列問題的對(duì)偶形式： 為自由變量 321 321 321 321 321 , 0, 0 4 163 2532 . . 34m

12、ax xxx xxx xxx xxx ts xxxZ No Image 運(yùn)籌學(xué)對(duì)偶問題 解：解： 為自由變量 321 321 321 321 321 , 0, 0 365 43 132 . . 42min yyy yyy yyy yyy ts yyyW 為自由變量 321 321 321 321 321 , 0, 0 4 163 2532 . . 34max xxx xxx xxx xxx ts xxxZ No Image 運(yùn)籌學(xué)對(duì)偶問題 例：寫出下列問題的對(duì)偶問題例：寫出下列問題的對(duì)偶問題 , 0, 0 24732 543 3432 . . 4323min 43, 21 4321 432 4

13、321 4321 xxxx xxxx xxx xxxx ts xxxxZ 為自由變量 No Image 運(yùn)籌學(xué)對(duì)偶問題 解：解： 為自由變量 321 321 321 321 31 321 , 0, 0 4444 3733 232 32 . . 253max yyy yyy yyy yyy yy ts yyyW , 0, 0 24732 543 3432 . . 4323min 43, 21 4321 432 4321 4321 xxxx xxxx xxx xxxx ts xxxxZ 為自由變量 No Image 運(yùn)籌學(xué)對(duì)偶問題 二、對(duì)偶問題的經(jīng)濟(jì)意義： l若原規(guī)劃問題是“在一定條件下，使工作或

14、成 果（產(chǎn)品產(chǎn)量、利潤(rùn)等）盡可能的大”， l那么它的對(duì)偶問題就是“在另外一些條件下， 使工作的消耗（浪費(fèi)、成本等）盡可能的小”。 l實(shí)際上是一個(gè)問題的兩個(gè)方面。 No Image 運(yùn)籌學(xué)對(duì)偶問題 例：某產(chǎn)品計(jì)劃問題的例：某產(chǎn)品計(jì)劃問題的 線性規(guī)劃數(shù)學(xué)模型為線性規(guī)劃數(shù)學(xué)模型為 0, 1025 1553 . . 2max 21 21 21 21 xx xx xx ts xxF （設(shè)備的約束） （原料的約束） l假設(shè)生產(chǎn)部門根據(jù)市場(chǎng)變化， 決定停止生產(chǎn)甲、乙產(chǎn)品， 而將原有的原料、設(shè)備專用 于接受外來訂貨以生產(chǎn)市場(chǎng) 急需的緊俏商品，則需要考 慮決策的問題就是“在什么 樣的價(jià)格條件下，才能接受 外來訂

15、貨？”。問題的實(shí)質(zhì) 就是如何確定原料、設(shè)備的 收費(fèi)標(biāo)準(zhǔn)？ No Image 運(yùn)籌學(xué)對(duì)偶問題 分析分析 l若設(shè)y1為單位原材料的價(jià)格，y2為設(shè)備單位臺(tái)時(shí)價(jià)格，由 于用了3個(gè)單位原料和5個(gè)單位設(shè)備臺(tái)時(shí)就可以生產(chǎn)一個(gè)單 位甲產(chǎn)品而獲利2個(gè)單位，現(xiàn)在不生產(chǎn)甲產(chǎn)品，轉(zhuǎn)而接受 外來訂貨加工，則收取的費(fèi)用不能低于2個(gè)單位，否則自 己生產(chǎn)甲產(chǎn)品更有利。因此，可以得到下面的條件： 253 21 yy No Image 運(yùn)籌學(xué)對(duì)偶問題 分析分析 l同理，將生產(chǎn)乙產(chǎn)品的原料和設(shè)備工時(shí)用于接 受外來加工訂貨，收取的費(fèi)用不能低于乙產(chǎn)品 的單位利潤(rùn)1個(gè)單位： 125 21 yy No Image 運(yùn)籌學(xué)對(duì)偶問題 分析分析

16、 l另外，為了爭(zhēng)取外來加工訂貨，在滿足上述要 求的基礎(chǔ)上，收費(fèi)標(biāo)準(zhǔn)應(yīng)盡可能低從而具有競(jìng) 爭(zhēng)力，因此總的收費(fèi) w=15y1+10y2 應(yīng)極小化。 這樣，就得到一個(gè)目標(biāo)函數(shù)： 21 1015minyyW No Image 運(yùn)籌學(xué)對(duì)偶問題 這樣，就得到另一個(gè)線性規(guī)劃模型：這樣，就得到另一個(gè)線性規(guī)劃模型： 0, 0 125 253 . . 1015min 21 21 21 21 yy yy yy ts yyW No Image 運(yùn)籌學(xué)對(duì)偶問題 比較比較 0, 0 125 253 . . 1015min 21 21 21 21 yy yy yy ts yyW 0, 1025 1553 . . 2max

17、21 21 21 21 xx xx xx ts xxF 生產(chǎn)問題 （要利用資源） 資源利用問題 （會(huì)影響生產(chǎn)） No Image 運(yùn)籌學(xué)對(duì)偶問題 第二節(jié) 對(duì)偶理論 No Image 運(yùn)籌學(xué)對(duì)偶問題 定理1（對(duì)稱性定理） l對(duì)偶問題（對(duì)偶問題（B）的對(duì)偶規(guī)劃為線性規(guī)劃（）的對(duì)偶規(guī)劃為線性規(guī)劃（A） l對(duì)稱性定理是很重要的。它表明原規(guī)劃問題（A）和對(duì)偶 規(guī)劃問題（B）是互為對(duì)偶的。也就是說，如果（B）是 （A）的對(duì)偶，那么（A）也是（B）的對(duì)偶。這就為以 后的討論帶來方便。不難理解，如果當(dāng)A具有某種性質(zhì)時(shí) 可以推出B的某些性質(zhì)，于是可以無需另加證明地得到： 當(dāng)B具有某種性質(zhì)時(shí)，問題A也具有那些性質(zhì)

18、。 No Image 運(yùn)籌學(xué)對(duì)偶問題 定理2（弱對(duì)偶定理） l當(dāng)原問題當(dāng)原問題A是求最大值是求最大值max，而對(duì)偶問題是求，而對(duì)偶問題是求 最小值時(shí)，如果最小值時(shí)，如果X0是原問題的任意可行解，是原問題的任意可行解，Y0 是對(duì)偶問題的任意可行解，則有以下關(guān)系式成是對(duì)偶問題的任意可行解，則有以下關(guān)系式成 立：立： BYCX 00 No Image 運(yùn)籌學(xué)對(duì)偶問題 定理3（最優(yōu)性定理） l設(shè)設(shè) 和和 分別是問題分別是問題A和和B的可行解，的可行解， 若相應(yīng)于若相應(yīng)于 和和 ，A和和B的目標(biāo)函數(shù)值的目標(biāo)函數(shù)值 相等，即相等，即 ，則，則 和和 分別是分別是A 和和B的最優(yōu)解。的最優(yōu)解。 x y x

19、ybyxc y x No Image 運(yùn)籌學(xué)對(duì)偶問題 定理4（無界性定理） l如果原問題如果原問題A的目標(biāo)函數(shù)值無界，則對(duì)偶問題的目標(biāo)函數(shù)值無界，則對(duì)偶問題 B無可行解；如果對(duì)偶問題無可行解；如果對(duì)偶問題B的目標(biāo)函數(shù)值無的目標(biāo)函數(shù)值無 界，則原問題界，則原問題A無可行解。無可行解。 No Image 運(yùn)籌學(xué)對(duì)偶問題 以上三個(gè)定理可以這樣記憶以上三個(gè)定理可以這樣記憶 l原問題A和對(duì)偶問題B如果有可行解，則它們的可行解區(qū)域只 可能相接，不可能相交。兩個(gè)區(qū)域的交界線即是它們的最優(yōu)解， 如果原問題A的目標(biāo)函數(shù)無界，意味著可行解區(qū)域無界，向外 擴(kuò)張，擠占了對(duì)偶問題B的可行解區(qū)域，則對(duì)偶問題無可行解， 反

20、之同理可說明。 對(duì)偶問題(B) minW 原問題(A) maxZ y0b cx0 byxc No Image 運(yùn)籌學(xué)對(duì)偶問題 定理5（強(qiáng)對(duì)偶定理） l若線性規(guī)劃若線性規(guī)劃A存在最優(yōu)解，則對(duì)偶規(guī)劃存在最優(yōu)解，則對(duì)偶規(guī)劃B也存也存 在最優(yōu)解，并且它們的最優(yōu)值相等；相反地，在最優(yōu)解，并且它們的最優(yōu)值相等；相反地， 若規(guī)劃若規(guī)劃B存在最優(yōu)解，則規(guī)劃存在最優(yōu)解，則規(guī)劃A也存在最優(yōu)解，也存在最優(yōu)解， 并且它們的最優(yōu)值相等。并且它們的最優(yōu)值相等。 No Image 運(yùn)籌學(xué)對(duì)偶問題 定理6（存在性定理） l若線性規(guī)劃若線性規(guī)劃A和和B都存在可行解，則都存在可行解，則A和和B都存都存 在最優(yōu)解。在最優(yōu)解。 No

21、 Image 運(yùn)籌學(xué)對(duì)偶問題 第三節(jié)第三節(jié) 對(duì)偶單純形法對(duì)偶單純形法 l條件： lb列中至少有一個(gè)bi0； l原問題A的檢驗(yàn)數(shù)滿足符號(hào)條件。 No Image 運(yùn)籌學(xué)對(duì)偶問題 例例 )4 , 3 , 2 , 1(0 242 32 . . 34min 4321 4321 421 jx xxxx xxxx ts xxxZ j No Image 運(yùn)籌學(xué)對(duì)偶問題 解：解： min max l解：引入松弛變量，化為標(biāo)準(zhǔn)形式： )6 , 2 , 1(0 242 32 . . 34max 64321 54321 421 jx xxxxx xxxxx ts xxxZ j No Image 運(yùn)籌學(xué)對(duì)偶問題 觀察

22、觀察A矩陣矩陣 101412 011121 A No Image 運(yùn)籌學(xué)對(duì)偶問題 解解 l以上標(biāo)準(zhǔn)形式中沒有完全單位向量組，我們將 約束條件進(jìn)行變換，兩邊同乘（-1）。 lA矩陣中存在完全單位向量組，但bi0時(shí)，得到最優(yōu)解。 l否則，進(jìn)行換基迭代 段段 CjCj 基基 0 0 b b -1-1 P P1 1 -4-4 P P2 2 0 0 P P3 3 -3-3 P P4 4 0 0 P P5 5 0 0 P P6 6 注注 1 1 0 0 x x5 5-3-3-1-1-2-21 1-1-11 10 0 0 0 x x6 6-2-22 21 1-4-4-1-10 01 1 Cj-ZjCj-Zj

23、- -1-1-4-40 0-3-30 00 0 j j No Image 運(yùn)籌學(xué)對(duì)偶問題 步驟步驟3：換基迭代：換基迭代 l（1）：找到b列中絕對(duì)值最大者所在行為 主元行，記為Pi*，主元行對(duì)應(yīng)的變量Xi*為調(diào)出變量。 段段 CjCj 基基 0 0 b b -1-1 P P1 1 -4-4 P P2 2 0 0 P P3 3 -3-3 P P4 4 0 0 P P5 5 0 0 P P6 6 注注 1 1 0 0 x x5 5-3-3-1-1-2-21 1-1-11 10 0 0 0 x x6 6-2-22 21 1-4-4-1-10 01 1 Cj-ZjCj-Zj- -1-1-4-40 0-

24、3-30 00 0 j j No Image 運(yùn)籌學(xué)對(duì)偶問題 （2） l找出主元行Pj*中所有負(fù)分量，計(jì)算 l注：若主元行中沒有負(fù)分量，則問題無解。 ji jj j p zc * 段段 CjCj 基基 0 0 b b -1-1 P P1 1 -4-4 P P2 2 0 0 P P3 3 -3-3 P P4 4 0 0 P P5 5 0 0 P P6 6 注注 1 1 0 0 x x5 5-3-3-1-1-2-21 1-1-11 10 0 0 0 x x6 6-2-22 21 1-4-4-1-10 01 1 Cj-ZjCj-Zj- -1-1-4-40 0-3-30 00 0 j j- -1 12

25、 2- -3 3- - - No Image 運(yùn)籌學(xué)對(duì)偶問題 （3） lj中絕對(duì)值最小者所在的列為主元列，記為Pj*， 主元列所對(duì)應(yīng)的變量xj*為調(diào)入變量。 段段 CjCj 基基 0 0 b b -1-1 P P1 1 -4-4 P P2 2 0 0 P P3 3 -3-3 P P4 4 0 0 P P5 5 0 0 P P6 6 注注 1 1 0 0 x x5 5-3-3-1-1-2-21 1-1-11 10 0 0 0 x x6 6-2-22 21 1-4-4-1-10 01 1 Cj-ZjCj-Zj- -1-1-4-40 0-3-30 00 0 j j- -1 12 2- -3 3- -

26、 - No Image 運(yùn)籌學(xué)對(duì)偶問題 （4） l主元行與主元列相交處的元素即主元素，記為Pi*j*。 段段 CjCj 基基 0 0 b b -1-1 P P1 1 -4-4 P P2 2 0 0 P P3 3 -3-3 P P4 4 0 0 P P5 5 0 0 P P6 6 注注 1 1 0 0 x x5 5-3-3(-1)(-1)-2-21 1-1-11 10 0 0 0 x x6 6-2-22 21 1-4-4-1-10 01 1 Cj-ZjCj-Zj- -1-1-4-40 0-3-30 00 0 j j- -1 12 2- -3 3- - - No Image 運(yùn)籌學(xué)對(duì)偶問題 （5）

27、迭代）迭代 l用高斯消去法，使原主元列中除了原主元素為1外， 其余元素均為0。 段段 CjCj 基基 0 0 b b -1-1 P P1 1 -4-4 P P2 2 0 0 P P3 3 -3-3 P P4 4 0 0 P P5 5 0 0 P P6 6 注注 1 1 0 0 x x5 5-3-3(-1)(-1)-2-21 1-1-11 10 0 0 0 x x6 6-2-22 21 1-4-4-1-10 01 1 Cj-ZjCj-Zj- -1-1-4-40 0-3-30 00 0 j j- -1 12 2- -3 3- - - 2 2 -1-1x x1 11 1 0 0 x x6 60 Cj

28、-ZjCj-Zj j j No Image 運(yùn)籌學(xué)對(duì)偶問題 計(jì)算結(jié)果計(jì)算結(jié)果 段段 CjCj 基基 0 0 b b -1-1 P P1 1 -4-4 P P2 2 0 0 P P3 3 -3-3 P P4 4 0 0 P P5 5 0 0 P P6 6 注注 1 1 0 0 x x5 5-3-3(-1)(-1)-2-21 1-1-11 10 0 0 0 x x6 6-2-22 21 1-4-4-1-10 01 1 Cj-ZjCj-Zj - -1-1-4-40 0-3-30 00 0 j j - -1 12 2- -3 3- - - 2 2 -1-1x x1 131 12-11-10 0 0 x

29、 x6 6-80 0-3-2-321 Cj-ZjCj-Zj j j No Image 運(yùn)籌學(xué)對(duì)偶問題 找主元行、確定調(diào)出變量、找主元行、確定調(diào)出變量、 計(jì)算計(jì)算zj-cj 段段 CjCj 基基 0 0 b b -1-1 P P1 1 -4-4 P P2 2 0 0 P P3 3 -3-3 P P4 4 0 0 P P5 5 0 0 P P6 6 注注 1 1 0 0 x x5 5-3-3(-1)(-1)-2-21 1-1-11 10 0 0 0 x x6 6-2-22 21 1-4-4-1-10 01 1 Cj-ZjCj-Zj - -1 14 40 03 30 00 0 j j - -1-1-

30、2-2- -3-3- - - 2 2 -1-1x x1 131 12-11-10 0 0 x x6 6-80 0-3-2-321 Cj-ZjCj-Zj -2-1-2- j j No Image 運(yùn)籌學(xué)對(duì)偶問題 計(jì)算計(jì)算j j、確定調(diào)入變量、確定調(diào)入變量 段段 CjCj 基基 0 0 b b -1-1 P P1 1 -4-4 P P2 2 0 0 P P3 3 -3-3 P P4 4 0 0 P P5 5 0 0 P P6 6 注注 1 1 0 0 x x5 5-3-3(-1)(-1)-2-21 1-1-11 10 0 0 0 x x6 6-2-22 21 1-4-4-1-10 01 1 Cj-

31、ZjCj-Zj - -1-1-4-40 0-3-30 00 0 j j - -1 12 2- -3 3- - - 2 2 -1-1x x1 131 12-11-10 0 0 x x6 6-80 0-3-2-321 Cj-ZjCj-Zj -0-2-1-210 j j -2/31/22/3- No Image 運(yùn)籌學(xué)對(duì)偶問題 繼續(xù)換基迭代：繼續(xù)換基迭代： 段段 CjCj 基基 0 0 b b -1-1 P P1 1 -4-4 P P2 2 0 0 P P3 3 -3-3 P P4 4 0 0 P P5 5 0 0 P P6 6 注注 1 1 0 0 x x5 5-3-3(-1)(-1)-2-21

32、1-1-11 10 0 0 0 x x6 6-2-22 21 1-4-4-1-10 01 1 Cj-ZjCj-Zj - -1-1-4-40 0-3-30 00 0 j j - -1 12 2- -3 3- - - 2 2 -1-1x x1 13 31 12 2-1-11 1-1-10 0 0 0 x x6 6-8-80 0-3-3(-2)(-2)-3-32 21 1 Cj-ZjCj-Zj - -0 0-2-2-1-1-2-2-1-10 0 j j - - -2/32/31/21/22/32/3- - - 3 3 -1-1x x1 10 0 0 0 x x3 31 1 Cj-ZjCj-Zj j

33、j No Image 運(yùn)籌學(xué)對(duì)偶問題 繼續(xù)換基迭代：繼續(xù)換基迭代： 段段 CjCj 基基 0 0 b b -1-1 P P1 1 -4-4 P P2 2 0 0 P P3 3 -3-3 P P4 4 0 0 P P5 5 0 0 P P6 6 注注 1 1 0 0 x x5 5-3-3(-1)(-1)-2-21 1-1-11 10 0 0 0 x x6 6-2-22 21 1-4-4-1-10 01 1 Cj-ZjCj-Zj - -1-1-4-40 0-3-30 00 0 j j - -1 12 2- -3 3- - - 2 2 -1-1x x1 13 31 12 2-1-11 1-1-10

34、0 0 0 x x6 6-8-80 0-3-3(-2)(-2)-3-32 21 1 Cj-ZjCj-Zj - -0 0-2-2-1-1-2-2-1-10 0 j j - - -2/32/31/21/22/32/3- - - 3 3 -1-1x x1 17 71 17/27/20 05/25/2-2-2-1/2-1/2 0 0 x x3 34 40 03/23/21 13/23/2-1-1-1/2-1/2 Cj-ZjCj-Zj j j No Image 運(yùn)籌學(xué)對(duì)偶問題 繼續(xù)換基迭代：繼續(xù)換基迭代： 段段 CjCj 基基 0 0 b b -1-1 P P1 1 -4-4 P P2 2 0 0 P P3 3 -3-3 P P4 4 0 0 P P5 5 0 0 P P6 6 注注 1 1 0 0 x x5 5-3-3(-1)(-1)-2-21 1-1-11 10 0 0 0 x x6 6-2-22 21 1-4-4-1-10 01 1 C