【正文】 6 － 1/6 1 2x 8/3 0 1 － 2/3 1/3 j? 0 0 － 1/6 － 1/6 松弛問題的最優(yōu)解為 * ( 5 / 3 , 8 / 3 , 0 , 0) TX ? 。 （ 1） 0 1a ?? ， 0 3b? ， 51 0 0 06 ( ) 0 .5 3 8。 例 1. 考慮 下述 規(guī)劃問題 ： 1 1 2 2m in ( ) ( )z f x f x?? 其中， 1111 12 0 5 0() 0 0x if xfx if x???? ? ??， 2222 21 2 6 0() 0 0x if xfx if x???? ? ??。 甲 乙 丙 丁 產(chǎn)量 A 10 6 7 12 4 B 16 10 5 9 9 C 5 4 10 10 4 銷量 5 2 4 6 解：用 Vogel 法求出初始解，如下： 甲 乙 丙 丁 產(chǎn)量 A 1 2 1 4 B 3 6 9 C 4 4 銷量 5 2 4 6 用位勢法計(jì)算 u 和 v： 甲 乙 丙 丁 ui A (10) (6) (7) 0 B (5) (9) 2 C (5) 5 vj 10 6 7 11 非基變量檢驗(yàn)數(shù)為： 甲 乙 丙 丁 ui A 1(12) 0 B 8(16) 6(10) 2 C 3(4) 8(10) 4(10) 5 vj 10 6 7 11 所有非基變量檢驗(yàn)均為正數(shù)，故已得到最優(yōu)解，運(yùn)輸成本最小值為 118. 例 3. 用表上作業(yè)法求解下述運(yùn)輸問題。 （ 1）求出最優(yōu) 基 不變的 2b 變化范圍； （ 2）求出最優(yōu)解不變的 3c 變化范圍； （ 3） 在原問題中 增加 約束 條件 1 2 32 2 12x x x? ? ?，求最優(yōu)解。 b 1x 2x 3x 4x 5x 2 0 － 1 1 3 1 4 1 － 1 0 － 1 0 j? 0 － 3 0 － 3 － 1 （ 1）寫出該問題的最優(yōu)解； （ 2）當(dāng) 3c? 為何值時(shí)，其對偶問題無解？ 解：（ 1）最優(yōu)解為 * (4, 0, 2, 0, 0) TX ? 。 （ 6） 若引入一個(gè)約束③，單純形表 將增加一行。 例 有線性規(guī)劃如下： 1 2 31 2 31 2 31 2 3m a x 5 5 133 20 . . 12 4 10 90 , , 0z x x xx x xs t x x xx x x? ? ? ?? ? ? ??? ? ? ??? ??①② 先用單純形法求出最優(yōu)解，再分析以下各種條件下，最優(yōu)解分別有什么變化： （ 1）約束條件①的右端常數(shù)由 20 變?yōu)?30； （ 2）約束條件②的右端常數(shù)由 90 變?yōu)?85； （ 3）目標(biāo)函數(shù)中 3x 的系數(shù)由 13 變?yōu)?8； （ 4） 1x 的系數(shù)列向量由 [1, 12]T變?yōu)?[0, 5]T； （ 5） 1x 和 2x 的系數(shù)列向量由 [1, 12]T 、 [1, 4]T變?yōu)?[0, 5]T 、 [2, 1]T； （ 6）增加一個(gè)約束條件 ③ 1 2 32 3 5 50x x x? ? ?； （ 7）將約束條件②改變?yōu)?1 2 310 5 10 10 0x x x? ? ?。先將原問題化為標(biāo)準(zhǔn)型，可得： 1 2 31 2 3 41 3 52 3 6m a x 2 2622..200 , 1, 2 , , 6jz x x xx x x xx x xstx x xxj? ? ?? ? ? ???? ? ? ??? ? ? ??? ??? 引入人工變量，可得第一階段的問題為： 7 8 91 2 3 4 71 3 5 82 3 6 9m i n 622..200 , 1 , 2 , , 9jz x x xx x x x xx x x xstx x x xxj? ? ?? ? ? ? ??? ? ? ? ? ??? ? ? ? ??? ??? 構(gòu)造單純形表，計(jì)算如下： jc 0 0 0 0 0 0 1 1 1 i? Bc BX b 1x 2x 3x 4x 5x 6x 7x 8x 9x 1 7x 6 1 1 1 － 1 0 0 1 0 0 6 1 8x 2 － 2 0 1 0 － 1 0 0 1 0 － 1 9x 0 0 [2] － 1 0 0 － 1 0 0 1 0 j? 1 － 3 － 1 1 1 1 0 0 0 1 7x 6 1 0 3/2 － 1 0 1/2 1 0 － 1/2 4 1 8x 2 － 2 0 [1] 0 － 1 0 0 1 0 2 0 2x 0 0 1 － 1/2 0 0 － 1/2 0 0 1/2 － j? 1 0 － 5/2 1 1 － 1/2 0 0 3/2 1 7x 3 [4] 0 0 － 1 3/2 1/2 1 － 3/2 － 1/2 3/4 0 3x 2 － 2 0 1 0 － 1 0 0 1 0 － 0 2x 1 － 1 1 0 0 － 1/2 － 1/2 0 1/2 1/2 － j? － 4 0 0 1 － 3/2 － 1/2 0 5/2 3/2 0 1x 3/4 1 0 0 － 1/4 3/8 1/8 1/4 － 3/8 － 1/8 0 3x 7/2 0 0 1 － 1/2 － 1/4 1/4 1/2 1/4 － 1/4 0 2x 7/4 0 1 0 － 1/4 － 1/8 － 3/8 1/4 1/8 3/8 j? 0 0 0 0 0 0 1 1 1 故，第一階段的最優(yōu)解為 * 3 7 7( , , , 0 , 0 , 0 , 0 , 0 , 0 )442 TX ? 第二階段的單純形表如下： jc 2 － 1 2 0 0 0 i? Bc BX b 1x 2x 3x 4x 5x 6x 0 1x 3/4 1 0 0 － 1/4 3/8 1/8 0 3x 7/2 0 0 1 － 1/2 － 1/4 1/4 0 2x 7/4 0 1 0 － 1/4 － 1/8 － 3/8 j? 0 0 0 5/4 － 3/8 － 9/8 非基變量 4x 的檢驗(yàn)數(shù)為正，但其系數(shù)向量為負(fù)，故原問題為無界解。 121 2 31 2 41 2 3 4m in z 3 42 40. . 3 30, , , 0xxx x xs t x x xx x x x? ? ?? ? ??? ? ? ??? ?? 解：構(gòu)造單純形表計(jì) 算如下： jc － 3 － 4 0 0 i? Bc BX b 1x 2x 3x 4x 0 3x 40 2 1 1 0 40 0 4x 30 1 [3] 0 1 10 j? － 3 － 4 0 0 0 3x 30 [5/3] 0 1 － 1/3 18 － 4 2x 10 1/3 1 0 1/3 30 j? － 5/3 0 0 4/3 － 3 1x 18 1 0 3/5 － 1/5 － 4 2x 4 0 1 － 1/5 － 2/5 j? 0 0 1 1 故 ，最優(yōu)解為 * (18 , 4 , 0 , 0) TX ? ，目標(biāo)函數(shù)值為 * 3 * 18 4 * 4 70z ? ? ? ? ?。 用單純形法求解原問題時(shí)，單純形表如下： jc 2 3 0 0 0 i? Bc BX b 1x 2x 3x 4x 5x 0 3x 8 1 2 1 0 0 4 0 4x 16 4 0 0 1 0 － 0 5x 12 0 [4] 0 0 1 3 j? 2 3 0 0 0 0 3x 2 [1] 0 1 0 － 1/2 2 0 4x 16 4 0 0 1 0 4 3 2x 3 0 1 0 0 1/4 － j? 2 0 0 0 － 3/4 2 1x 2 1 0 1 0 － 1/2 － 0 4x 8 0 0 － 4 1 [2] 4 3 2x 3 0 1 0 0 1/4 12 j? 0 0 － 2 0 1/4 2 1x 4 1 0 0 1/4 0 0 5x 4 0 0 － 2 1/2 1 3 2x 2 0 1 1/2 － 1/8 0 j? 0 0 － 3/2 － 1/8 0 原問題的最優(yōu)解為 * (4, 2, 0, 0, 4) TX ? ，目標(biāo)函數(shù)最大值為 * 2 * 4 3 * 2 14z ? ? ?。 （ 3）令 1 2 4,x x x 為基變量、 35,xx為非基變量，可得解 (2, 3, 0,8, 0) TX ? ， 13z? 。求解下述 LP 問題 121 2 31425m a x 2 3284 16. . 4 120 , 1 , 2 , , 5jz x xx x xxxstxxxj??? ? ??? ???? ???? ??? 解：依據(jù)單純形理論，有 以下計(jì)算： （ 1）令 345,x x x 為基變量、 12,xx為非基變量，可得 123451 2 1 0 0 84 0 0 1 0 1 60 4 0 0 1 1 2xxxxx????? ? ? ???? ? ? ??? ?? ? ? ???? ? ? ?? ? ? ???????， 解得 3 1 241528216 412 4x x xxx? ? ??????????， 代入目標(biāo)函數(shù)，得 120 2 3z x x? ? ? 。 若令 1x 取正值且 5x 仍為 0，由 23141302016 4 0xxx????? ? ???? ? ??，可得 1124xx??? ??，這說明 1x 最大可以達(dá)到 2，此時(shí) 3x 將變?yōu)?0，成為非基本變量。 121 2 31425m a x 2 3284 16. . 4 120 , 1 , 2 , , 5jz x xx x xxxstxxxj??? ? ??? ???? ???? ??? 解：原問題可等價(jià)轉(zhuǎn)化為： 121212m ax 2 3284 16. . 4 120 , 1, 2jz x xxxxstxxj?????? ??? ??? ??? 圖解如下： 可知，目標(biāo)函數(shù)在 B(4, 2)處取得最大值，故原問題的最優(yōu)解為 * (4,2)TX ? ，目標(biāo)函數(shù)最大值為 * 2 * 4 3 * 2 14z ? ? ?。 例 3：用單純形法求解下述 LP 問題。 例 6： 求解下述 LP 問題 1 2 31 2 313231 2 3m a x 2 2622..20, , 0z x x xx x xxxstxxx x x? ? ?? ? ???? ? ??? ???? ?? 解：用兩階段法求解。 例 用對偶單純形法求解 1 2 31 2 31 2 31 2 3m in 2 3 423. . 2 3 4, , 0x x xx x xs t x x xx x x? ? ? ?? ? ??? ? ? ??? ?? 解：先將原問題改寫為： 1 2 31 2 3 41 2 3 5m a x 2 3 42 3. . 2 3 40 , 1 , 2 , , 5jz x x xx x x xs t x x x xxj? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ??? ??? 建立單純形表計(jì)算如下： jc － 2 － 3 － 4 0 0 BC BX b 1x 2x 3x 4x 5x 0 4x － 3 － 1 － 2 － 1 1 0 0 5x － 4 [－ 2] 1 － 3 0 1 j? － 2 － 3 － 4 0 0 0 4x － 1 0 [－ 5/2] 1/2 1 － 1/2 － 2 1x 2 1 － 1/2 3/2 0 － 1/2 j? 0 － 4 － 1 0 － 1 － 3 2x 2/5 0 1 － 1/5 － 2/5 1/5 － 2 1x 11/5 1 0 7/5