【正文】 的運 輸問題。 5．調(diào)運方案的調(diào)整是要在檢驗數(shù)出現(xiàn) 負值 的點為頂點所對應的 閉回路 內(nèi)進行運量的調(diào)整。 五、給出線性規(guī)劃問題 用單純形表求解得單純形表如下，試分析下列各種條件 變化下最優(yōu)解 (基 )的變化： xl x2 x3 x4 x5 xB Z 8 0 0 3 5 1 xl x2 1 2 1 0 1 4 1 0 1 2 1 1 (1)分別確定目標函數(shù)中變量 X1和 X2的系數(shù) C1， c2在什么范圍內(nèi)變動時最優(yōu)解不變； (2)目標函數(shù)中變量 X3的系數(shù)變?yōu)?6； (3)增添新的約束 X1+2x2+x3≤4 解： (1)3/4≤ C1≤ 3 2≤ C2≤ 8 (2)X*=(2， 0， 1， 0， 0， 0)T Z*=10 (3)X*=(2， 1， 0， 0， 1， 0)T Z*=7 (4)X*=(0， 2， 0， 0， 0， 1/3)T Z*=25/3 第六章 物資調(diào)運規(guī)劃運輸問題 一、填空題 1． 物資調(diào)運問題中，有 m 個供應地， Al， A2? ， Am， Aj的供應量為 ai(i=1， 2? ， m)， n 個需求地 B1， B2， ?B n，B 的需求量為 bj(j=1， 2， ? ， n)，則 供需平衡條件為 ??mi ia1=??nj ib1 2．物資調(diào)運方案的最優(yōu)性判別準則是： 當全部檢驗數(shù) 非負 時，當前的方案一定是最優(yōu)方案。 (4)該廠預備引進一種新產(chǎn)品 Ⅲ ，已知生產(chǎn)每件產(chǎn)品 Ⅲ ，需消耗原材料 A、 B 分別為 6kg， 3kg使用設備 2 臺時，可獲利 5 百元，問該廠是否應生產(chǎn)該產(chǎn)品及生產(chǎn)多少 ? (1)使工廠獲利最多的產(chǎn)品混合生產(chǎn)方案 ：生產(chǎn) I 產(chǎn)品 4 件，生產(chǎn) II 產(chǎn)品 2 件，設備臺時與原材料 A 全部用完，原材料 B 剩余 4kg，此時，獲利 14 百元。 (2)如該廠從別處抽出 4 臺時的設備用于生產(chǎn) I、 Ⅱ ，求這時該廠生產(chǎn)產(chǎn)品 I、 Ⅱ 的最優(yōu)方案。已知生產(chǎn) 單位產(chǎn)品所需的設備臺時及 A、 B 兩種原料的消耗如表所示： I Ⅱ 設備 原材料 A 原材料 B 1 4 0 2 0 4 8臺時 16kg 12kg 該工廠每生產(chǎn)一件產(chǎn)品 I 可獲利 2 百元，每生產(chǎn)一件產(chǎn) 品Ⅱ可獲利 3 百元。 （ 1）預先確定保持現(xiàn)有生產(chǎn)規(guī)劃條件下，單位產(chǎn)品利潤的可變范圍；（ 2）當資源限制量發(fā)生變化時，確定新的生產(chǎn)方案；（ 3）確定某種新產(chǎn)品的投產(chǎn)在經(jīng)濟上是否有利；（ 4）考察建模時忽略的約束對問題的影響程度；（ 5）當產(chǎn)品的設計工藝改變時，原最優(yōu)方案是否需要調(diào)整。 A．非基變量的目標系數(shù)變化 B．基變量的目標系數(shù)變化 C．增加新的變量 D，增加新的約束條件 4．下列說法 錯誤 的是 ACD A．若最優(yōu)解的可行性滿足 B1 b≥0 ，則最優(yōu)解不發(fā)生變化 B．目標系數(shù) cj發(fā)生變化時，解的正則性將受到影響 C．某個變量 xj的目標系數(shù) cj發(fā)生變化，只會影響到該變量的檢驗數(shù)的變化 D．某個變量 xj的目標系數(shù) cj發(fā)生變化，會影響到所有變量的檢驗數(shù)發(fā)生變化。 A 基 B 松弛變量 C 原始 數(shù)據(jù) D 條件系數(shù) 三、多選題 1．如果線性規(guī)劃中的 cj、 bi同時發(fā)生變化，可能對原最優(yōu) 解產(chǎn)生的影響是 _ ABCD. A．正則性不滿足，可行性滿足 B．正則性滿足，可行性不滿足 C．正則性與可行 性都滿足 D．正則性與可行性都不滿足 E．可行性和正則性中只可能有一個受影響 2．在靈敏度分析中，我們可以直接從最優(yōu)單純形表中獲 得的有效信息有 ABCE。 C．當某個約束常數(shù) bk增加時，目標函數(shù)值一定增加。 A．目標系數(shù) B．約束常數(shù) C．技術系數(shù) D．增加新的變量 E．增加新的約束條件 5．對于標準型的線性規(guī)劃問題，下列說法 錯誤 的是 C A．在新增變量的靈敏度分析中，若新變量可以進入基底，則目標函數(shù)將會得到進一 步改善。 A．正則性 B．可行性 C．可行解 D．最優(yōu)解 3．在線性規(guī)劃的各項敏感性分析中，一定會引起最優(yōu)目 標函數(shù)值發(fā)生變化的是 B。 二、單選題 1．若線性規(guī)劃問題最優(yōu)基中某個基變量的目標系數(shù)發(fā)生 變化，則 C。 若某線性規(guī)劃問題增加一個新的約束條 件，在其最優(yōu)單純形表中將表現(xiàn)為增加 一行，一列 。 8．已知線性規(guī)劃問題，最優(yōu)基為 B，目標系數(shù)為 CB，若新增變 量 xt，目標系數(shù)為 ct，系數(shù)列向量為 Pt，則當 Ct≤ CBB－ 1Pt 時， xt不能 進入基底。 5．約束常數(shù) b；的變化，不會引起解的 正則性 的變化。 3．在靈敏度分析中，某個非基變量的目標系數(shù)的改變，將引起 該非基變量自身 的檢驗數(shù)的變化。 W* = 16 第五章 線性規(guī)劃的靈敏度分析 一、填空題 靈敏度分析研究的是線性規(guī)劃模型的 原始、最優(yōu)解 數(shù)據(jù)變化對產(chǎn)生的影響。 五、寫出下列線性規(guī)劃問題的對偶問題 1． minZ=2x1+2x2+4x3 六、已知線性規(guī)劃問題 應用對偶理論證明該問題最優(yōu)解的目標函數(shù)值不大于 25 七、已知線性規(guī)劃問題 maxZ=2x1+x2+5x3+6x4 其對偶問題的最優(yōu)解為 Yl﹡ =4， Y2﹡ =1，試應用對偶問題 的性質(zhì)求原問題的最優(yōu)解。 （ 1）指出企業(yè)內(nèi)部挖潛的方向；（ 2）為資源的購銷決策提供依據(jù)；（ 3）分析現(xiàn)有產(chǎn)品價格變動時資源緊缺情況的影響；（ 4）分析資源節(jié)約所帶來的收益；（ 5）決定某項新產(chǎn)品是否應投產(chǎn)。 影子價格：對偶變量 Yi表示與原問題的第 i 個約束條件相對應的資源的影子價格，在數(shù)量上表現(xiàn)為，當該約束條件的右端常數(shù)增加一個單位時（假設原問題的最優(yōu)解不變），原問題目標函數(shù)最優(yōu)值增加的數(shù)量。 .對稱的對偶問題：設原始線性規(guī)劃問題為 maxZ=CX AX≤ b X ≥ 0 稱線性規(guī)劃問題 minW=Yb YA≥ C Y≥ 0 為其對偶問題。 A． 對偶問題的解 B．市場上的稀缺情況 C．影子價格 D．資源的購銷決策 E．資源的市場價格 7．在下列線性規(guī)劃問題中， CE 采用求其對偶問題的 方法，單純形迭代的步驟一般會減少。 A．在迭代過程中應先選出基變量，再選進基變量 B．當?shù)械玫降慕鉂M足原始可行性條件時，即得到最優(yōu)解 C．初始單純形表中填列的是一個正則解 D．初始解不需要滿足可行性 E．初始解必須是可行的。 3．如線性規(guī)劃的原問題為求極大值型，則下列關于原問 題與對偶問題的關系中正確的是 BCDE。 C．若原問題為 maxZ=CX， AX≤b ， X≥0 ，則對偶問題為 minW=Yb， YA≥C ， Y≥ 0。 A．一個問題有可行解，另一個問題無可行解 B．兩 個問題都有可行解 C．兩個問題都無可行解 D．一個問題無界，另一個問題可行 2．下列說法 錯誤 的是 B 。是某標準型線性規(guī)劃問題的最優(yōu)目標函數(shù)值， 則其對偶問題的最優(yōu)目標函數(shù)值 w﹡ A。 3．對偶單純形法的迭代是從 _ A_開始的。 二、單選題 1．線性規(guī)劃原問題的目標函數(shù)為求極小值型，若其某個 變量小于等于 0，則其對偶問題約束條件為 A 形式。 13．線性規(guī)劃的原問題的約束條件系數(shù)矩陣為 A，則其對 偶問題的約束條件系數(shù)矩陣為 AT 。 11．設線性規(guī)劃的原問題為 maxZ=CX， Ax≤b ， X≥0 ，則 其對偶問題為 min=Yb YA≥ c Y≥ 0_。 9．若 X、 Y 分別是線性規(guī)劃的原問題和對偶問題的可行解，則 有 CX≤ Yb。 7．線性規(guī)劃問題的最優(yōu)基為 B，基變量的目標系數(shù)為 CB，則其對偶問題的最優(yōu)解 Y﹡ = CBB－ 1。在其他條件不變的情況下 (假設原問題的最佳基不變 )，當該種資源增加 3 個單位時。 5．若原問題可行，但目標函數(shù)無界，則對偶問題 不可行 。 3．如果原問題的某個變量無約束，則對偶問題中對應的約束條件應為 等式 _。已知該線 性規(guī)劃的目標函數(shù)為 maxZ=5x1+3x2，約束形式為“≤” ， X3， X4為松馳變量．表中解代入目標函數(shù) 后得 Z=10 Xl X2 X3 X4 — 10 b 1 f g X3 2 C O 1 1／ 5 Xl a d e 0 1 (1)求表中 a～ g 的值 (2)表中給出的解是否為最優(yōu)解 ? （ 1） a=2 b=0 c=0 d=1 e=4/5 f=0 g=－ 5 （ 2） 表中給出的解為最優(yōu)解 第四章 線性規(guī)劃的對偶理論 一、填空題 1．線性規(guī)劃問題具有對偶性，即對于任何一個求最大值的線性規(guī)劃問題，都有一個求 最小值 /極小值 的線性規(guī)劃問題與之對應，反之亦然。并指出問題的解屬于 哪一類。 五、分別用圖解法和單純形法求解下列線性規(guī)劃問題．并對照指出單純形迭代的每一步相當于圖解法可行域中的哪一個頂點。 A．一個基可行解 B．當前解是否為最優(yōu)解 C．線性規(guī)劃問題是否出現(xiàn)退化 D．線性規(guī)劃問題的最優(yōu)解 E．線性規(guī)劃問題是否無界 （ AB ） A 所有 δ j均小于等于 0 B 所有 δ j均小于等于 0 且有 aik≤ 0 C 所有 aik＞ 0 D 所有 bi≤ 0 （ ABCDE ） A 基可行解 B 迭代一次的改進解 C 迭代兩次的改進解 D 迭代三次的改進解 E 所有檢驗數(shù)均小于等于 0 且解中無人工變量 若某線性規(guī)劃問題有無窮多最優(yōu)解，應滿足的條件有（ BCE ） A Pk＜ Pk0 B 非基變量檢驗數(shù)為零 C 基變量中沒有人工變量 Dδ j＜ O E 所有 δj≤ 0 （ ABCDE ） A 基可行解 B 迭代一次的改進解 C 迭代兩次的改進解 D 迭代三次的改進解 E 所有檢驗數(shù)均小于等于 0 且解中無人工變量 四、名詞、簡答 人造初始可行基：當我們無法從一個標準的線性規(guī) 劃問題中找到一個 m 階單位矩陣時，通常在約束方程中引入人工變量，而在系數(shù)矩陣中湊成一個 m 階單位矩陣，進而形成的一個初始可行基稱為人造初始可行基。A．該問題的典式不超過 CNM個 B．基可行解中的基變量的個數(shù)為 m 個 C．該問題一定存在可行解 D．該問題的基至多有 CNM=1 個 E．該問題有 111 個基可行解 5．單純形法中，在進行換基運算時，應 ACDE。 A． c=6 a=1 b=10 B． c=6 a=1 b=12 C． c=4 a=3 b=12 D． c=4 a=3 b=12 E． c=6 a=3 b=12 3．設 X(1)， X(2)是用單純形法求得的某一線性規(guī)劃問題 的最優(yōu)解，則說明 ACDE。 A min B max C min + max D min ,max 任選 ，若全部非基變量的檢驗數(shù) ≤O ，且基變量中有人工變量時該 問題有 B A 無界解 B 無可行解 C 唯一最優(yōu)解 D 無窮多最優(yōu)解 三、多選題 1． 對取值無約束的變量 xj。 A．不 影響解的可行性 B．至少有一個基變量的值為負 C．找不到出基變量 D．找不到進基變量 4．用單純形法求解極大化線性規(guī)劃問題中，若某非基變 量檢驗數(shù)為零，而其他非基變量檢驗數(shù)全部 0，則說明本問 題 B 。 二、單選題 1．線性規(guī)劃問題 C 2．在單純形迭代中，出基變量在緊接著的下一次迭代中 B 立即進入基底。 11．在單純形迭代過程中，若有某個 δ k0 對應的非基變 量 xk的系數(shù)列向量 Pk_≤ 0_時，則此問題是無界的 。 9．線性規(guī)劃典式的特點是 基為單位矩陣，基變量的目標函數(shù)系數(shù)為 0。 7．當線性規(guī)劃問題的系數(shù)矩陣中不存在現(xiàn)成的可行基時，一般可以加入 人工變量 構(gòu)造可行基。 5．在單純形迭代中，可以根據(jù) 最終 _表中 人工變量 不為零 判斷線性規(guī)劃問題無解。 3．對于目標函數(shù)極大值型的線性規(guī)劃問題，用單純型法求解 時，當基變量檢驗數(shù) δ j_≤_0時，當前解為最優(yōu)解。 某建筑工地有一批長度為 10 米的相同型號的鋼筋，今 要截成長度為 3 米的鋼筋 90 根，長度為 4 米的鋼筋 60 根，問 怎樣下料，才能使所使用的原材料最省 ? 1． 某運輸公司在春運期間需要 24小時晝夜加班工作，需 要的人員數(shù)量如