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

　　

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