【導(dǎo)讀】?jī)H當(dāng)目標(biāo)函數(shù)趨勢(shì)線與x1=0是存在無窮個(gè)最。添加目標(biāo)函數(shù)的趨勢(shì)線如圖中虛線所示?？尚杏蛳嗲杏贏點(diǎn)時(shí)，目標(biāo)函數(shù)值最大，即達(dá)到最優(yōu)解。由圖可知，該線性規(guī)劃問題無可行域，即無可行解。當(dāng)，即x2,x4為基變量，x1,x3為非基變量。在上述基本解中為[5,0,10,0]T、[0,5,0,35]T、[0,0,5,10]T基本可行解，[-35/3,-20/3,0,0]T、[-5,0,0,20]T、[0,-2,7,0]T是不可行的。

　　

【正文】 ?2,1,0)()()(m a x)(0011kSfSfxVSf kkkkxkk k 于是用順推方法，從前向后依次有： 1?k ? ? ? ? 11430001143011 03m a x)()(m a x)(111111SxSfxVSf xsxxsx ????? ?????? 且且 2?k ? ?? ?? ?? ?22620222620126201122620223m a x25m a x5m a x)()(m a x)(222222222222xSxSxSxSfxVSfxsxxsxxsxxsx?????????????????????且且且且 因?yàn)?182?S 所以 18,6 22 ?? Sx 時(shí) )( 22 Sf 最大 解得： 18,6,6,2 2121 ???? SSxx （ 2） 逆序解法： 階段 1,2?k 狀態(tài)變量為 ks ，決策變量為 kx 。狀態(tài)轉(zhuǎn)移 02,3,18 2231121 ????? xSSxSSS 則有 20,30 2211 SxSx ???? 階段指標(biāo) 222111 5)(,3)( xxVxxV ?? 遞推方程 ? ?????????? ??1,2,0)()()(m a x)(3311kSfSfxVSf kkkkxkk k 于是用逆推方法，從后向前依次有： 2?k ? ? ? ? 2505m a x)()(m a x)( 22620332262022 222222SxSfxVSfxsxxsx??????????? 且且1?k ? ???????????????????????????????????????11430111430214302211430112925m a x)3(253m a x253m a x)()(m a x)(111111111111xSxSxSxSfxVSfxsxxsxxsxxsx且且且且 因?yàn)?122?S 即 123 11 ?? xS 所以11 43 xS ?? ? ?)18m a x)43(2925m a x)(14301143011111111???????? ?????????SSSSfxsxxsx且且 所以 18,2 11 ?? Sx 時(shí) )( 11Sf 最大 解得： 12,18,6,2 2121 ???? SSxx 2. 運(yùn)用動(dòng)態(tài)規(guī)劃方法求解下列問題 解： （ 1） 順序解法： 階段 321 、?k 狀態(tài)變量為 ks ，決策變量為 kx 。狀態(tài)轉(zhuǎn)移 6, 33222111 ?????? SxSSxSSx 則有 332211 0,0,0 SxSxSx ?????? 階段指標(biāo) 33332222111 )(,)(,)( xxVxxVxxV ??? 遞推方程 ? ?????????? ??3,2,1,1)()()(m a x)(0011kSfSfxVSf kkkkxkk k 于是用 順推方法，從前向后依次有： 1?k ? ? ? ? 212100011011 1m a x)()(m a x)( 1111 SxSfxVSf SxSx ????? ???? 2?k ? ?? ?? ?2222021201122022)(m a xm a x)()(m a x)(222222xSxSxSfxVSfSxSxSx????????????? 2222222 )(),( xSxxSh ??? 由 ? ?? ? 03 222222 ???? xSxSdxdh ，解得 3, 2222 SxSx ?? 或 又因?yàn)?222222 46 Sxdxhd ?? 當(dāng) 0246, 222222222 ????? SSSdx hdSx 為極小值點(diǎn) 當(dāng) 02436,2 222222222 ??????? SSSdx hdSx 為極大值點(diǎn) 所以 274)3(3m a x)(322222022 22SSSSSfSx ??????? ????? 3?k ? ??????? ???????????????????27)(4m a x274m a x)()(m a x)(333330323302233033333333xSxSxSfxVSfSxSxSx 27 )(4),( 33333333 xSxxSh ??? 由 ? ? ? ? 0294 332332322 ???? xSxSxdxdh ，解得 2,0 33333 SxSxx ??? 或 又因?yàn)?)55)((98 2333233332222 xxSSxSxdx hd ???? 當(dāng) 0,0 23323 ?? dxhdx 當(dāng) 0, 233233 ?? dxhdSx 當(dāng) 0181,2 43222233 ???? Sdx hdSx 為極大值點(diǎn) 所以 43 227)2(42m a x)(6333333033 33SSSSSfSx??????????? ??????????? 當(dāng) 63?S 時(shí) )( 33 Sf 最大 解得： 6,3,2,3,1,2 321321 ?????? SSSxxx （ 2） 逆序解法： 階段 321 、?k 狀態(tài)變量為 ks ，決策變量為 kx 。狀態(tài)轉(zhuǎn)移 3342231121 ,6 xSSxSSxSSS ??????? 則有 332211 0,0,0 SxSxSx ?????? 階段指標(biāo) 33332222111 )(,)(,)( xxVxxVxxV ??? 遞推方程 ? ?????????? ??1,2,3,1)()()(m a x)(4411kSfSfxVSf kkkkxkk k 于是用 逆推 方法，從 后往前 依次有： 3?k ? ? ? ? 333304433033 1m a x)()(m a x)( 3333 SxSfxVSf SxSx ????? ???? 2?k ? ?? ?? ?3222033203322022)(m a xm a x)()(m a x)(222222xSxSxSfxVSfSxSxSx????????????? 3222222 )(),( xSxxSh ??? 由 ? ? ? ? 04 2222222 ???? xSxSdxdh ，解得 4, 2222 SxSx ?? 或 又因?yàn)?)2)((6 22222222 xSxSdx hd ???? 當(dāng) 0, 222222 ?? dxhdSx 當(dāng) 049,4 22222222 ???? Sdx hdSx 為極大值點(diǎn) 所以 ? ? 423222022 25627)(m a x)(22SxSxSf Sx ???? ?? 1?k ? ??????? ???????????????????2 5 6)(27m a x2 5 627m a x)()(m a x)(411210422102211011111111xSxSxSfxVSfSxSxSx 256 )(27),( 41121111 xSxxSh ??? 由 ? ? ? ? 0312827 11311111 ???? xSxSxdxdh ，解得 3,0 11111 SxSxx ??? 或 又因?yàn)?)1510()(12827 2111212112112 xxSSxSdx hd ???? 當(dāng) 012827,0 4121121 ??? Sdx hdx 為極小值點(diǎn) 當(dāng) 0, 211211 ?? dxhdSx 當(dāng) 0161,3 41211211 ???? Sdx hdSx 為極大值點(diǎn) 所以 432256)3(273m a x)(6141121011 11SSSSSfSx??????????? ??????????? 當(dāng) 61?S 時(shí) )( 11Sf 最大 解得： 3,4,6,3,1,2 321321 ?????? SSSxxx 第九章 圖與網(wǎng)絡(luò)分析 1. 解： 由題可知 A,B,C,D,E,F 距離其他各村的最短距離如下表所示： A B C D E FA 0 2 6 8 9 12B 2 0 4 6 7 10C 6 4 0 4 3 6D 8 6 4 0 1 4E 9 7 3 1 0 3F 12 10 6 4 3 0 假設(shè)學(xué)校建在 A 村，則所有人行走路程總和 總路程 =50 0+40 2+60 6+20 8+70 9+90 12=2310 假設(shè)學(xué)校建在 B 村，則 所有人行走路程總和 總路程 =50 2+40 0+60 4+20 6+70 7+90 10=1850 假設(shè)學(xué)校建在 C 村，則所有人行走路程總和 總路程 =50 6+40 4+60 0+20 4+70 3+90 6=1290 假設(shè)學(xué)校建在 D 村，則所有人行走路程總和 總路程 =50 8+40 6+60 4+20 0+70 1+90 4=1310 假設(shè)學(xué)校建在 E 村，則所有人行走路程總和 總路程 =50 9+40 7+60 3+20 1+70 0+90 3=1310 假設(shè)學(xué)校建在 F 村，則所有人行走路程總和 總路程 =50 12+40 10+60 6+20 4+70 3+90 0=2280 當(dāng)學(xué)校建在 D 村或 E 村是總路程最小為 1310，所以可以選擇將學(xué)校建在 D 村或 E 村。 2. 解： 可將原文題轉(zhuǎn)換成為如下所示的最大流問題： 使用觀察發(fā)可得一可行流如下所示 （ 1） 給 S 標(biāo) ? ?S,? ,選與 S 關(guān)聯(lián)的流出未飽和弧或流入非零流弧，得流出未飽和弧? ?AS, ，給 A 標(biāo)號(hào) ? ?SA,? ，其中 ? ? ? ? 235,m in,m in ??????? SASAA fc? 則A 點(diǎn)獲得標(biāo)號(hào) ? ?S,2 （ 2） 把頂點(diǎn)集分為 ? ? ? ?TGFEDCBVASV ,, 11 ?? 考慮所有的這樣的弧? ?ji vv, 或 ? ?ij vv, 。其中， 11, VvVv ji ?? 得弧? ? ? ? ? ? ? ? ? ?AFDABACSBS ,,, 。在這些弧中， ? ?BA, 為流出的未飽和弧， 給 B 標(biāo)號(hào) ? ?AB,? ，其中 ? ? ? ? 101,2m in,2m in ????? ABABB fc? ， 即給 B 標(biāo)號(hào) ? ?A,1 。 （ 3） 把頂點(diǎn)集分為 ? ? ? ?TGFEDCVBASV ,, 11 ?? 考慮所有的這樣的弧? ?ji vv, 或 ? ?ij vv, 。其中， 11, VvVv ji ?? 得弧? ? ? ? ? ? ? ? ? ? ? ? ? ?FBEBDBCBAFDACS ,,,, 。 在 這 些 弧 中 ，? ? ? ? ? ?FBEBCB ,, 為 流 出 的 未 飽 和 弧 ， 給 C 標(biāo)號(hào) ? ?BC,? ，其中? ? ? ? 102,1m in,1m in ????? BCBCC fc? ， 即給 C 標(biāo)號(hào) ? ?B,1 ；給 E 標(biāo)號(hào)? ?BE,? ，其中 ? ? ? ? 135,1m in,1m in ????? BEBEE fc? ， 即給 E 標(biāo)號(hào) ? ?B,1 ；給 F 標(biāo)號(hào) ? ?BF,? ，其中 ? ? ? ? 101,1m in,1m in ????? BFBFF fc? ， 即給 F 標(biāo)