運籌學(xué)復(fù)習(xí)題課件

1、運籌學(xué)復(fù)習(xí)運籌學(xué)F_02,第1章 線性規(guī)劃及單純形法,一、判斷題 （1）圖解法與單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的。 正確。 （2）線性規(guī)劃模型中增加一個約束條件，可行域的范圍一般將縮小，減少一個約束條件，可行域的范圍一般將擴大。 正確。這里注意：增加約束，可行域不會變大；減少約束，可行域不會變小。 （3）線性規(guī)劃問題的每一個基解對應(yīng)可行域的一個頂點。 錯誤。線性規(guī)劃的基本定理之一為：線性規(guī)劃問題的基本可行解對應(yīng)于可行域的頂點。,（4）如線性規(guī)劃問題存在可行域，則可行域一定包含坐標(biāo)的原點。 錯誤。 如果約束條件中有一個約束所對應(yīng)的區(qū)域不包含坐標(biāo)的原點，則即使有可行域，也不

2、包含坐標(biāo)的原點。 （5）取值無約束的變量 ，通常令 = ，其中 0, 0，在用單純形法求得的最優(yōu)解中，有可能同時出現(xiàn) 0, 0。 錯誤。 （6）用單純形法求解標(biāo)準(zhǔn)型式的線性規(guī)劃問題時，與 0對應(yīng)的變量都可以被選作入基變量。 正確。,（7）單純形法計算中，如不按最小比值原則選取換出變量，則在下一個解中至少有一個基變量的值為負(fù)。 正確。 （8）一旦一個人工變量在迭代中變?yōu)榉腔兞亢?，則該變量及相應(yīng)列的數(shù)字可以從單純形表中刪除，而不影響計算結(jié)果。 正確。 人工變量一般是為取得對應(yīng)的初始基基向量而引入的，它一旦成為出基變量，其地位已被對應(yīng)的入基變量取代，刪除單純形表中該變量及相應(yīng)列的數(shù)字，不影響計算結(jié)

3、果。 （9）線性規(guī)劃問題的任一可行解都可以用全部基可行解的線性組合表示。 錯誤。 如果 =1 =1 ，則命題正確，否則，不正確。,（10）對一個有n個變量，m個約束的標(biāo)準(zhǔn)型的線性規(guī)劃問題，其可行域頂點恰好是 個。 錯誤。 （11）線性規(guī)劃問題的可行解如為最優(yōu)解，則該可行解一定是基本可行解。 錯誤。 唯一最優(yōu)解時，最優(yōu)解是可行域頂點，對應(yīng)基本可行解；無窮多最優(yōu)解時，除了其中的可行域頂點對應(yīng)基本可行解外，其余最優(yōu)解不是可行域的頂點。 （12）若線性規(guī)劃問題具有可行解，且其可行域有界，則該線性規(guī)劃問題最多具有有限個數(shù)的最優(yōu)解。 錯誤。 如果在不止一個可行解上達(dá)到最優(yōu)，它們的凸組合仍然是最優(yōu)解，這樣就

4、有了無窮多的最優(yōu)解。,(13)若線性規(guī)劃問題的可行域可以伸展到無限，則該問題一定具有無界解。 錯誤。 二、用單純形法求解標(biāo)準(zhǔn)型式的線性規(guī)劃問題時，如何判別該問題具有唯一最優(yōu)解、無窮多最優(yōu)解、無界解或者無可行解？ 當(dāng)所有 0，且非基變量的檢驗數(shù)0，有 0，有無界解 對于所有 0，而基變量中含非0人工變量，有無可行解。,三、下表中給出某一求極大化問題的單純形表，問表中 1 ， 2 ， 1 ， 2 ，為何值時以及表中變量屬哪一種類型時有： （a）表中解為唯一最優(yōu)解； （b）表中解為無窮多最優(yōu)解之一； （c）表中解為退化的可行解； （d）下一步迭代將以 1 替換 5 ； （e）該線性規(guī)劃問題具有無界解

5、； （f）該線性規(guī)劃問題無可行解。,答案： （a）d0， 1 0， 1 0，且 4 = 3 2 ； （d） 1 0， 1 2 ， 4 3 2 ； （e） 2 0， 1 0； （f） 5 為人工變量，且 1 0， 2 0。,四、已知某線性規(guī)劃問題單純形法迭代時得到中間某兩步的單純形表如下表所示，試將表中空白處的數(shù)字填上。,檢驗數(shù)：(0,0,0,-45/41,-24/41,-11/41),第2章 線性規(guī)劃的對偶理論,一、判斷題 （1）任何線性規(guī)劃問題存在并具有唯一的對偶問題。 正確。 （2）對偶問題的對偶一定是原問題。 正確。 （3）根據(jù)對偶問題的性質(zhì)，當(dāng)原問題為無界解時，其對偶問題無可行解；反之

6、，當(dāng)對偶問題無可行解時，其原問題具有無界解。 錯誤。 （4）設(shè) 和 分別是標(biāo)準(zhǔn)形式（P,max）和（D,min）的可行解， 和 分別為其最優(yōu)解，則恒有 = b b。 正確。,（5）若原問題有可行解，則其對偶問題有可行解。 錯誤。 （6）若原問題無可行解，則其對偶問題也一定無可行解。 錯誤。 （7）若原問題有最優(yōu)解，則其對偶問題也一定有最優(yōu)解。 正確。 （8）若原問題和對偶問題均存在可行解，則兩者均存在最優(yōu)解。 正確。 （9）如果原問題的約束方程Ax b，變成Ax b，則其對偶問題的唯一改變就是非負(fù)的y0變成非正的 y0。 正確。,（10）已知 為線性規(guī)劃的對偶問題的最優(yōu)解的第i個分量，若 0，

7、說明在最優(yōu)生產(chǎn)計劃中第i種資源已經(jīng)耗盡。 正確。 （11）已知 為線性規(guī)劃的對偶問題的最優(yōu)解第i個分量，若 =0說明在最優(yōu)生產(chǎn)計劃中第i種資源已經(jīng)耗盡且一定有剩余。 錯誤。 （12）用對偶單純形法求解線性規(guī)劃的每一步，在單純形表檢驗數(shù)行與基變量列對應(yīng)的對偶問題與原問題的解代入各自的目標(biāo)函數(shù)得到的值始終相等。 正確。,（13）如果某種資源的影子價格為k，在其它條件不變的前提下，當(dāng)該種資源增加5個單位時，相應(yīng)的目標(biāo)函數(shù)值將增加5k。 錯誤。 （14）應(yīng)用對偶單純形法計算時，若單純形表中某一基變量 0，又 所在行的元素全部大于或等于零，則可以判斷其對偶問題具有無界解。 錯誤。 （15）若線性規(guī)劃問題

8、中的 、 值同時發(fā)生變化，反應(yīng)到最終單純形表中，不會出現(xiàn)原問題和對偶問題均為非可行解的情況。 錯誤。,（r）在線性規(guī)劃問題的最優(yōu)解中，如果某一變量 為非基變量，則在原來問題中，無論改變它在目標(biāo)函數(shù)中的系數(shù) 或在各約束中的相應(yīng)系數(shù) ，反應(yīng)到最終單純形表中，除該列數(shù)字有變化外，將不會引起其它列數(shù)字的變化。 正確。,二、已知線性規(guī)劃問題： （a） 寫出其對偶問題； （b）已知原問題用兩階段法求解時得到的最終單純形表如下,試寫出其對偶問題的最優(yōu)解。,答案 (a)對偶問題 (b) y 1 =0， y 2 =1， y 3 =3 4 的檢驗數(shù)=0 y 1 =0 1 =14 2 y 2 + y 3 =5 3

9、=-4 3 y 2 + y 3 =6,三、,四、某廠生產(chǎn)、三種產(chǎn)品，分別經(jīng)過A、B、C三種設(shè)備加工，已知生產(chǎn)單位各種產(chǎn)品所需要的設(shè)備臺時，設(shè)備的現(xiàn)有加工能力以及每件產(chǎn)品的預(yù)期的利潤如下表： （a）求獲利最大的產(chǎn)品計劃？ Maxz=10 1 +6 2 +4 3 1 + 2 + 3 100 10 1 + 4 2 +5 3 600 2 1 + 2 2 +6 3 100 0，=1,2,3,最優(yōu)單純形表 因此，獲利最大的產(chǎn)品生產(chǎn)計劃為 100 3, 200 3 ,0,0,0,100 = 2200 3,（b）產(chǎn)品每件的利潤增加到多大時才值得安排生產(chǎn)？如果產(chǎn)品的每件利潤增加到50/6元，求最優(yōu)計劃的變化？

10、200 3 (見下頁PPT) （c）產(chǎn)品的利潤在多大范圍變化時，原最優(yōu)計劃保持不變？ 6,15 （d）設(shè)備A的能力如為 100+10，確定保持最優(yōu)基不變的的變化范圍？ -4,5 （e）如有一種新產(chǎn)品，加工一件設(shè)備A、B、C的臺時為1、4、3小時，預(yù)期每件的利潤為8元，是否值得安排生產(chǎn)？ 檢驗數(shù)為正，值得生產(chǎn) （f）如合同規(guī)定該廠至少生產(chǎn)10件產(chǎn)品，試確定最優(yōu)的變化？ 去掉生產(chǎn)10件產(chǎn)品的資源，重新計算，結(jié)論為95/3,175/3,10,第3章 運輸問題,一、判斷題 （1）在運輸問題中，只要任意地給出一組含m+n-1個非零的 ，且滿足 =1 = ， =1 = ，就可以作為一個初始基本可行解。 錯

11、誤。 （2）表上作業(yè)法實質(zhì)上就是求解運輸問題的單純形法。 正確。 （3）按最小元素法（或Vogel法）給出的初始基可行解，從每一空格出發(fā)可以找出而且僅能找出唯一的閉回路。 正確。,（4）如果運輸問題單位運價表的某一行（或某一列）元素分別加上一個常數(shù)k，最優(yōu)調(diào)運方案將不會發(fā)生變化。 正確。 （5）如果運輸問題單位運價表的某一行（或某一列）元素分別乘上一個常數(shù)k，最優(yōu)調(diào)運方案將不會發(fā)生變化。 錯誤。 （6）如果運輸問題單位運價表的全部元素乘上一個常數(shù)k（k0），最優(yōu)調(diào)運方案將不會發(fā)生變化。 正確。,（7）用位勢法求運輸問題某一調(diào)運方案的檢驗數(shù)時，其結(jié)果可能同閉回路法求得的結(jié)果有異。 錯誤。 （8）

12、運輸問題初始方案的基本要求:（m+n-1）個數(shù)字格，不存在全部以數(shù)字格為頂點的閉回路。 正確。,二、,不是最優(yōu)，因為不是基可行解。,3.5 某造船廠根據(jù)合同要在當(dāng)年算起的連續(xù)三年年末各提供三條規(guī)格相同的大型貨輪。已知該廠今后三年的生產(chǎn)能力及生產(chǎn)成本如表。 已知加班生產(chǎn)情況下每條貨輪成本比正常生產(chǎn)時高出70萬元，又知造出的貨輪如當(dāng)年不交貨，每條貨輪每積壓一年將增加維護(hù)保養(yǎng)等損失為40萬元。在簽訂合同時該廠已有兩條積壓未交互的貨輪，該廠希望在第三年末在交完合同任務(wù)后能儲存一條備用。 問該廠應(yīng)如何安排計劃，使在滿足上述要求的條件下，使總的費用支出為最小。,設(shè),為期初庫存用于第 j 年交貨的數(shù)量,為第

13、 i 年正常生產(chǎn)用于第 j 年交貨的數(shù)量,為第 i 年加班生產(chǎn)用于第 j 年交貨的數(shù)量,約束條件：,生產(chǎn)能力限制,需求限制,目標(biāo)函數(shù)：,其中費用系數(shù)見下表：,產(chǎn)地：每年正常生產(chǎn)、加班生產(chǎn)及其庫存 銷地：每一年的需求,第4章 整數(shù)規(guī)劃與分配問題,一、判斷題 （1）整數(shù)規(guī)劃解的目標(biāo)函數(shù)值一般優(yōu)于其相應(yīng)的線性規(guī)劃問題的解的目標(biāo)函數(shù)值； 錯誤。 （2）用分枝定界法求解一個極大化的整數(shù)規(guī)劃問題時，任何一個可行解的目標(biāo)函數(shù)值是該問題目標(biāo)函數(shù)值的下界； 正確。 （3）用分枝定界法求解一個極大化的整數(shù)規(guī)劃問題時，當(dāng)?shù)玫蕉嘤谝粋€可行解時，通?？扇稳∑渲幸粋€作為下界值，再進(jìn)行比較剪枝。 錯誤。,（4）指派問題效率

14、矩陣的每個元素都乘上同一個常數(shù)k，將不影響最優(yōu)指派方案； 錯誤。 （5）指派問題數(shù)學(xué)模型的形式同運輸問題十分相似，故也可以用表上作業(yè)法求解； 正確。 （6）用割平面法求解整數(shù)規(guī)劃時，構(gòu)造的割平面有可能切去一些不屬于最優(yōu)解的整數(shù)。 錯誤。,（7）分枝定界法在需要分枝時必須滿足：一是分枝后的各子問題必須容易求解；二是各個子問題解的集合必須覆蓋原問題的解。 正確。 （8）一個整數(shù)規(guī)劃問題如果存在兩個以上的最優(yōu)解，則該問題一定有無窮多最優(yōu)解。 錯誤。,二、某科學(xué)實驗衛(wèi)星擬從下列儀器裝置中選若干件裝上，有關(guān)數(shù)據(jù)資料如下表：,三、,四、,五、,第5章 目標(biāo)規(guī)劃,一、判斷題 （1）線性規(guī)劃問題是目標(biāo)規(guī)劃問題

15、的一種特殊形式。 正確。 （2）正偏差變量取正值，負(fù)偏差變量應(yīng)取負(fù)值。 錯誤。 （3）目標(biāo)規(guī)劃模型中，可以不包含系統(tǒng)約束（絕對約束），但必須包含目標(biāo)約束。 正確。,（4）同一個目標(biāo)約束中的一對偏差變量 、 + 至少有一個取值為零。 正確。 （5）目標(biāo)規(guī)劃的目標(biāo)函數(shù)中，既包含決策變量，又包含偏差變量。 錯誤。 （6）只含目標(biāo)約束的目標(biāo)規(guī)劃模型一定存在滿意解。 正確。,（7）目標(biāo)規(guī)劃模型中的目標(biāo)函數(shù)按問題性質(zhì)要求分別表示為求min或求max。 錯誤。 （8）目標(biāo)規(guī)劃模型中的優(yōu)先級 1 、 2 ，其中 較之 +1 目標(biāo)的重要性一般為數(shù)倍至數(shù)十倍之間。 錯誤。 （9）下列表達(dá)式均不能用來表達(dá)目標(biāo)規(guī)劃模

16、型的目標(biāo)函數(shù)：maxz= 1 1 + 2 2 ； minz= 1 1 2 2 ； minz= 1 1 + 2 （ 2 2 + ）。 正確。,二、,五、,C點,第6章 圖與網(wǎng)絡(luò)分析,一、判斷題。 （1）圖論中的圖不僅反映了研究對象之間的關(guān)系，而且是真實圖形的寫照，因而對圖中 點與點的相對位置、邊的長短曲直等都要嚴(yán)格注意。 錯誤。 （2）在任一圖G中，當(dāng)點集V確定后，樹圖是G中邊數(shù)最少的連通圖。 正確。 （3）如圖中某點 有若干個相鄰點，與其距離最遠(yuǎn)的相鄰點為 ，則邊i,j必不包含在最小支撐樹內(nèi)。 錯誤。,（4）求圖的最小支撐樹以及求圖中一點至另一點的最短路問題，都可以歸結(jié)為求解整數(shù)規(guī)劃問題。 正

17、確。 （5）任一圖中奇點的個數(shù)可能為奇數(shù)個，也可能為偶數(shù)個。 錯誤。 （6）任何n個節(jié)點，（n-1）條邊的圖一定是樹圖。 錯誤。,（7）一個具有多個發(fā)點和多個收點的求網(wǎng)絡(luò)最大流的問題一定可以轉(zhuǎn)化為求具有單個發(fā)點和單個收點的求網(wǎng)絡(luò)最大流問題。 正確。 （8）作為增廣鏈上的弧，如屬正向弧一定有 。 錯誤。,第7章 計劃評審方法和關(guān)鍵路線法,一、判斷題。 （1）網(wǎng)絡(luò)圖中只能有一個始點和一個終點； 正確。 （2）網(wǎng)絡(luò)圖中因虛作業(yè)的時間為零，因此在各項時間參數(shù)的計算中可將其忽略。 錯誤。 （3）網(wǎng)絡(luò)圖中關(guān)鍵路線的延續(xù)時間相當(dāng)于求圖中從起點到終點的最短路。 錯誤。,（4）網(wǎng)絡(luò)圖中求關(guān)鍵路線的問題可表達(dá)為求

18、解一個線性規(guī)劃模型； 正確。 （5）網(wǎng)絡(luò)圖中從一個事件出發(fā)如果存在多項作業(yè)，則其中用時最長的一項作業(yè)必包含在該網(wǎng)絡(luò)圖的關(guān)鍵路線內(nèi)。 錯誤。 （6）一項非關(guān)鍵路線上的作業(yè)在其最早開始于最遲結(jié)束的時間段內(nèi)均可任意安排。 錯誤。 （7）若一項作業(yè)的總時差為10d，說明任何情況下該項作業(yè)從開始到結(jié)束之間總有10d的機動時間。 錯誤。,（8）一個網(wǎng)絡(luò)只存在唯一的關(guān)鍵路線。 錯誤。 （9）為了在最短時間內(nèi)完成項目，其關(guān)鍵路線上作業(yè)的開始或結(jié)束時間不允許有任何延遲。 正確。 （10）網(wǎng)絡(luò)關(guān)鍵路線上的所有作業(yè)，其總時差和自由時差均為零。 正確。 （11）任何非關(guān)鍵路線上的作業(yè)，其總時差和自由時差均不為零。 錯誤。,（12）若一項作業(yè)的總時差為零，則其自由時差一定為零。 正確。 （13）若一項作業(yè)的自由時差為零，則其總時差比為零。 錯誤。 （14）當(dāng)作業(yè)時間用a,m,b三點估計時，m等于完成該項作業(yè)的期望時間。 錯誤。,第8章 動態(tài)規(guī)劃,一、判斷題。 （1）動態(tài)規(guī)劃的