【導讀】一個基變量為負。形法求得的最優(yōu)解中有可能出現0jx??換入變量，將使目標函數值得到最快的增長。表示出來的問題可以考慮用線性規(guī)劃模型來處理。束條件，可行域的范圍一般將擴大。單純形表中刪除，而不影響計算結果。最優(yōu)調運方案將不會發(fā)生變化。狀況而言，余下的決策序列必構成最優(yōu)策略。

　　

【正文】 的兩個最優(yōu)解，則 ( D )也是該 LP 的最優(yōu)解。 A. ? ?4,4x? B. ? ?1,2x? C. ? ?2,3x? D. 無法判斷 1線性規(guī)劃問題的標準型最本質的特點是 ( B,D ) A. 目標要求是極小化 B. 變量和右端常數要求非負 C. 變量可以取任意值 D. 約束條件一定是等式形式 1目標函數取極小化（ minZ ）的線性規(guī)劃可以轉化為目標函數取極大化即 ( B )的線性規(guī)劃問題求解；兩 者的最優(yōu)解（ E ），最優(yōu)值（ D ） A. maxZ B. max( )Z? C. max( )Z?? D. 相差一個負號 E. 相同 F. 無確定關系 G. maxZ? 17 線性規(guī)劃問題12112212312m a x 3 542 12..3 2 180 , 0Z x xxyxs t yxxyxx?????? ????????? ???對 偶 變 量。已知最優(yōu)解為 12*2636xxz???，則其對偶問題的最優(yōu)解為 ( B ) A. （ 3， 2， 0） B. 20, ,13?????? C. 40,1,3?????? D. 23,1,3?????? BAO 1 21217 1 若 LP問題的約束條件是? ?1 2 31 2 41 2 3 4 52 253 304 7 2 850 1 , 2 , , 5ix x xx x xx x x x xxi? ? ??? ? ? ??? ? ? ? ? ??? ???，其可行域有一個頂點是（ D） A.? ?0, 0, 25, 30, 85 T?? B.? ?9,7,0,0,8 T C.? ?5,15,0, 20,0 T D.? ?9,7,10,0,0 T 1若 LP 問題 1 : m a x , , 0M Z CX A X b X? ? ?有最 優(yōu)解 *X ，則 LP 問題2 1: m a x , , 0M W C X A X b X?? ? ?（ ，其中 ? 為一正常數，有（ D） *X? ， 最優(yōu)值 *CX? *X ， 最優(yōu)值 *CX? *X? ， 最優(yōu)值 *CX *X ， 最優(yōu)值 *1CX? 判斷下列說法是否正確 （ C,D） 點 12,XX是某線性規(guī)劃問題的可行解，則 ? ?1 1 2 2 1 2 1X X X? ? ? ?? ? ? ?也必是該問題的可行解 C. 線性規(guī)劃問題若存在可行解，其可行域集合為凸集 D. 若 12,XX是某線性規(guī)劃問題的最優(yōu)解，則 ? ? ? ?1 1 1 2 11 0 1X X X? ? ?? ? ? ? ?也是該問題的最優(yōu)解 2 用線性規(guī)劃 求解標準型的線性規(guī)劃問題時 （ C,D） 0jjcz??時，即可判定表中解即為最優(yōu)解 ，必須選取與最大正檢驗數 ? ?kkcz? 對應的變量 kx 為換入基的變量 0j j jcz? ? ? ? ，且該列系數 0jP? ，則線性規(guī)劃問題最優(yōu)解不存在（無界解） 2線性規(guī)劃的可行域非空無界，則（ D） 偶問題不一定是無可行解 2線性規(guī)劃的原問題與其對偶問題之間存在如下關系 （ A,D） ，其對偶問題必存在可行解 ，其對偶問題必無可行解 18 ，其對偶問題也有無窮多最優(yōu)解 2 LP問 題? ?1111221( ) m a x0 1 , 2 , ,njjjnjjjnjjjja Z c xa x bya x bzx j n??????????? ???????? ??????對 偶 變 量，? ?1111221( ) m a x2211220 1 , 2 , ,njjjnjjjnjjjja Z c xa x bya x bzx j n???????????? ????????? ??????對 偶 變 量 則有 a（ ） (b) 兩對偶問題，各自最優(yōu)解與間關系 （ C） A. * * * *,y y z z???? B. * * * *12, 2y y z z???? C. * * * *1 ,22y y z z???? D. ABC以外的其它關系 2已知某個含有 10 個節(jié)點的樹圖，其中 9 個節(jié)點的次（線度）為 1,1,3,1,1,1,3,1,3，則另一節(jié)點的次為 ( C ) A. 1 B. 4 C. 3 D. 2 2用標號法尋找網絡最大流時，發(fā)生標號中斷。這時若用 V 表示已標號的節(jié)點集合，用 V 表示未標號的節(jié)點集合，則在網絡中所有 VV? 方向的弧上有 ( C )， VV?方向的弧上有 ( D )， A. 0f? B. fc? C. fc? D. 0f? （ f 為流量， c 為弧的容量 ） 2顧客到達有三個并聯(lián)服務站的排隊系統(tǒng)，一是在每個服務站前各排一行隊伍，顧客選隊長最短的行排在末尾，二是只排一行隊伍，近先到先服務規(guī)則依次服務。設顧客在系統(tǒng)中平均逗留時間第一種情況下為 1W ，第二種情況下為 2W ，則有 ( C ) A. 12WW? B. 12WW? C. 12WW? D. 不一定 2對系統(tǒng)中 顧客容量有限的排隊系統(tǒng) M/M/S，系統(tǒng)到達穩(wěn)定狀態(tài)的條件是 ( D ) A. 1S??? B. 1??? 1S???，但 1??? D. A,B,C,之外的其它條件 2滿足下面條件的簡單圖 ? ?,G V E? 是樹圖 （ A,C,D） n 個點恰有 1n? 條邊 D. G無圈，但只要加一條邊即得惟一的 圈 在目標規(guī)劃中 （ D） ，負偏差變量取負值 敏敏 min，也可以求 max 19 1 2 3, , ,P P P 之間表明數量上的重要性差別，如 1P 比 2P 級重要10倍或 20倍等 （剛性約束），也可以不包含 3 下列說法中，不正確的是 ( C ) A. 圖是反映對象之間關系的一種工具 B. 圖 的基本要素是點和 點之間的連 線 C. 無向圖是由點及弧所構成的 D. 圖中的點代表研究的對象 3 一個含有圈的 5個點的連通圖的線數（ B ） A．至少為 4 B．至少為 5 C．等于 5 D．至多為 5 3設 樹 M 是圖 N 的最小 支撐 樹，則 下列敘述錯誤的是 （ C ） A. M 中必不含圈 B. M 是連通的 C. N 不一定連通 D. M 可能并不唯一 3 一個圖有 5 個點， ８條邊。這個圖一定是 ( C ) A．連通圖 B．樹 C．含圈的圖 D．不連通圖 3下列敘述錯誤的是 ( C ) A. 樹的點數為線數加一 B. 樹的任意兩點之間只有一條路 C. 圖的點數大于線數 D. 任何不連通圖都不是樹 3 下列說法中不正確的是 （ D ） A. 對樹而言，多一邊必形成至少一個圈 B. 對樹而言，少任一邊，必不再連通 C. 任一圖中所有點的次之和是邊數的兩倍 D. 任一圖中偶點的個數為偶數 3 n 個點的不連通圖，其邊數（ A ） A．必然少于 n－ 1 B．必然等于 n－ 1 C．必然多于 n－ 1 D．可能多于 n－ 1 3 最短路線是 指 ( A ) A. 連接起點到終點總長度最短的路線 B. 連接所有點總長度最短的路線 C. 所有點之間長度最短的路線 D. 從起點出發(fā)經過各點到終點總長度最短的路線 20 補： 是否成立 “若原問題有唯一最優(yōu)解，則對偶問題也有唯一最優(yōu)解 ”。請證明。 答：不成立，見下面兩例。 121212max 320..0, 0z x xxxstxx?????????有惟一可行解也是最優(yōu)解 120, 0xx?? 其對偶單純形1111min 01. . 2 30wyyst yy????? ??? ??有無限多個可行解同時是最優(yōu)解。最優(yōu)值都為 0。 121212max 221..0, 0z x xxxstxx?????????有無限多個最優(yōu)解在 1221xx??上 其對偶單純形1111min1. . 2 20wyyst yy???? ??? ??只有唯一最優(yōu)解 1 1y? 。最優(yōu)值都為 1。 另： 當線性規(guī)劃的原問題存在可行解時，則其對偶問題不一定存在可行解。例如： 121 2 31 2 31 2 3m a x2. . 2 10 , 0 , 0z x xx x xs t x x xx x x??? ? ? ???? ? ? ??? ? ? ??存在可行解 ? ?0,0,0 TX ? ，但其對偶問題1212121212min 2211..00, 0w y yyyyystyyyy??? ? ??? ???? ???? ???由第一個條件知 不存在可行解。