【正文】 ） 二 . 填空題 線性規(guī)劃問題 的數(shù)學(xué)模型中目標(biāo)函數(shù)和約束函數(shù)都是 __線性 _函數(shù)。 圖解法求解極小化線性規(guī)劃問題時，等成本線越往左下角 移動，成本越 _小 _。 圖解法求解極小化線性規(guī)劃問題時，等成本線越往 右上 角移動，成本越 __大 _。 下列的數(shù)學(xué)模型 (A)1 2 3121 2 31 2 3241. . 2 0, , 0Z x x xxxs t x x xx x x? ? ?? ? ??? ? ? ??? ??； (B)21121212m a x m in ,234. . 3 2 10,0xZxxxs t x xxx??????????? ???? ??中 (B)是線性規(guī)劃， 令3 1 3 21, 2x x x x??得312123 1 3 212m a x343 2 10.., ,0Zxxxxxstx x x xxx????? ???? ???? ?? 可轉(zhuǎn)化為線性規(guī)劃問題 5 下列的數(shù)學(xué)模型 (A)2121212max0..,0Z x xxxstxx????????； (B)12121212max21. . 2 3,0w x xxxst x xxx?????? ???? ??； (C),1m in. . 0 , 1, ,1, ,jjjij j ijZ c xa x bs t x j min??? ?????? ????； (D)；1 2 3121 2 31 2 3241. . 2 0, , 0Z x x xxxs t x x xx x x? ? ?? ? ??? ? ? ??? ?? (E)21121212m a x m in ,234. . 3 2 0,0xZxxxs t x xxx??????????? ???? ??中 (B)是線性規(guī)劃， (E)可轉(zhuǎn)化為線性規(guī)劃問題 、線性規(guī)劃模型有 3 種參數(shù)，其名稱分為價值參數(shù) （目標(biāo)函數(shù)系數(shù)） 、 資源常數(shù)（約束右端常數(shù) ）、 技術(shù)系數(shù)（約束系數(shù)） 。 對于 右 下面的 圖中 LP 問題的可行解為 OFIHC 所圍區(qū)域 ，基本解為 O,A,B,C,D,E,F,G,H,I 共十個點(diǎn) ，基本可行解為 O,F,H,I,C共 五 個點(diǎn) 。1212121212m ax 2 5422..20, 0Z x xxxxxstxxxx??????? ? ??? ???? ??? 對于平面中的某 LP的約束集合如右圖 其可行解為 OGEDH 所圍陰影區(qū) ， 基本解為 圖中 所有直線及坐標(biāo)軸之間 的交點(diǎn) ，基本可行解為 OGEDH 五 個點(diǎn) 。 原問題有可行解但無最優(yōu)解，則其對偶問題 無可行解 對偶問題中的決策變量稱為 影子價格 1 LP問題1212121212m ax 3 2243 2 14..30, 0Z x xxxxxstxxxx??? ? ??? ???? ???? ???的對偶問題 為1 2 31 2 31 2 31 2 3m in 4 14 333. . 2 2 20 , , 0w y y yy y ys t y y yy y y? ? ?? ? ? ??? ? ? ??? ???，對偶問題中的決 策變量稱為 影子價格 1線性規(guī)劃中的 影子價格 *1BY C B?? 就是對偶問題的 檢驗(yàn)數(shù) 。 1 影子價格 *Y 與對偶問題的關(guān)系是 *Y 是對偶問題的最優(yōu)解 。 x1x2目標(biāo)函數(shù)GFC IBHAODEx1x2FGDHBACOE6 1對偶定理有三個 互補(bǔ)松弛性 、 強(qiáng)對偶性 、 弱對偶性 。 1若對偶問題為無界解，其原問題為 無可行解 。 1 LP數(shù)學(xué)模型為 max.. 0Z CXAX bstX??????，則其 對偶數(shù)學(xué)模型為m in..TTTd b yA y Csty?? ??? 為 自 由 變 量 1 LP 數(shù)學(xué)模型為mj= 11m in, 1 , 2 , ,..jjnij j ijjd c ya y b i nsty = 1, 2, ,m??? ????? ????0,j， 其對偶數(shù)學(xué)模型的最優(yōu)解為? ?* * * *12, , , nX x x x? ， 則 原數(shù)學(xué)模型的最優(yōu)目標(biāo)函數(shù)值為 * * * *1 1 2 2 nnd b x b x b x? ? ? ? 1分枝定界法的基本思想計(jì)算法依據(jù)是 對最大化的整數(shù)規(guī)劃問題 A，先求與它相應(yīng)的線性規(guī)劃（不是整數(shù)）的問題 B，若其最優(yōu)解不符合整數(shù)條件，則將目標(biāo)函數(shù)最大值定為上界 Z 。然后將 B 的可行域分成子區(qū)域 （分析），逐步減少 Z 值，最終求出最優(yōu) *Z 。 1 如果把約束方程 1212342 5 5xxxx???? ???標(biāo)準(zhǔn)化為 1 2 31 2 4 5342 5 5x x xx x x x? ? ??? ? ? ? ??時， 1x 是 決策 變量 ， 2x 是 決策 變量， 3x 是 松弛 變量， 4x 是 剩余 變量， 5x 是 人工 變量。 LP的基本可行解與基本解的區(qū)別是 基本可行解的分量 0? 。 2 LP的基可行解與基解的區(qū)別是 基解的 可以有 分量 0? 。 2在單純性迭代中，任何出基的變量在緊接著的下一次迭代中， 不會 （選會或不會填空）立即再入基。 2若對偶問題為無界解，則其原問題為 無可行解 。 2求目標(biāo)最大的 LP中，有無窮最 優(yōu)解的條件是 j? 判別式中至少有一個零 。 2線性規(guī)劃中的影子價格 *1BY C B?? 就是對偶問題的 檢驗(yàn)數(shù) ； 2對經(jīng)濟(jì)類問題求極大化的過程中，用單純形法迭代簡化的表格表示 如下表（假定沒有人工變量）： 基 1x 2x 3x 4x 5x 6x 常數(shù) 3x 4 1? 1 0 2? 0 ? 7 4x 1 5 0 1 1 0 2 5x 3? 3 0 0 4 1 3 檢驗(yàn)數(shù)? 1? 2? 0 0 3 0 對六個未知數(shù)的約束條件選擇填空，使以下關(guān)于該表的說法為真。 （ 1）現(xiàn)行解有無窮多最優(yōu)解（ A） A. 10, 0????，或 210, 0???? B. 10, 0????，或 210, 0???? C. 10, 0????，或 210, 0???? （ 2） 現(xiàn)行解不可行 （ B） A. 0?? B. 0?? C.? 為任意數(shù) （ 3） 一個約束有矛盾 （ C） A. 120, 0, 0? ? ?? ? ? B. 120, 0, 0? ? ?? ? ? C. 120, 0, 0? ? ?? ? ? （ 4） 現(xiàn)行解是退化的基本可行解 （ C） A. 0?? B. 0?? C. 0?? （ 5） 現(xiàn)行解是惟一最優(yōu)解 （ A） A. 120, 0, 0? ? ?? ? ? B. 120, 0, 0? ? ?? ? ? C. 120, 0, 0? ? ?? ? ?. 2某一最大線性規(guī)劃問題在單純形計(jì)算時的下表： （書中例） 基 常數(shù) 1x 2x 3x 4x 5x 6x 3x f 2 b 1 0 e 0 4x 2 1 5 0 1 1 0 6x 3 a 3 0 0 4 1 檢驗(yàn)數(shù) jjcz? b d 0 0 3 0 對六個未知數(shù) 滿足什么 約束條件填空，原問題要求所有變量均非負(fù)。 （ 1） 0f? 時現(xiàn)行解是非可行基解； （ 2） 0, 0, 0f b d? ? ?時該 LP問題有惟一最優(yōu)解； （ 3） 0, 0, 0f b d? ? ?或 0 , 0 , 0 , 0f b d c? ? ? ?時該 LP問題 有無窮多最 優(yōu)解 ； （ 4） 0, 0, 0f b d? ? ?時現(xiàn)行解 是退化基可行解； 8 （ 5） 0, 0, 0f d c? ? ?時該 LP問題有 無界解 或稱目標(biāo)函數(shù)無界 ； （ 6） 30 , 0 , 0 , , 02ff b d aa? ? ? ? ?時現(xiàn)行解 是可行解但非最優(yōu)解，只有 1x 可以進(jìn)基且出基變量必為第三個基變量 6x 。 （ 7） 60, 0,b d x??為人工變量 時該 LP 問 題無可行基解。 2對經(jīng)濟(jì)類問題求極大化的過程中，用單純形法迭代簡化的表格表示如下表（假定沒有人工變量）： 基 常數(shù) 1x 2x 3x 4x 5x 6x 2x 2a 0 1 0 0 0 1a 3x 4 2 0 1 4a 0 2 5x 10 3a 0 0 4 1 3 檢驗(yàn)數(shù)定義為1B j jC B P C? ??? 5a 0 0 6a 0 6 表中 jx 均非人工變量， 對六個未知數(shù)的約束條件填 空 ，使以下關(guān)于該表的說法為真。 （ 1） 當(dāng) 2 5 60, 0, 0a a a? ? ?時現(xiàn)行解是惟一最優(yōu)解 （ 2） 當(dāng) 2 5 60, 0, 0a a a? ? ?或 2 6 5 40 , 0 , 0 , 0a a a a? ? ? ?時現(xiàn)行解為最優(yōu)，但有無窮多最優(yōu)解 ） （ 3） 當(dāng) 2 5 60, 0, 0a a a? ? ?時現(xiàn)行解是退化基本最優(yōu)解 （ 4） 當(dāng) 2 6 40, 0,