運(yùn)籌學(xué)復(fù)習(xí)考點(diǎn).ppt

1、運(yùn)籌學(xué)復(fù)習(xí)運(yùn)籌學(xué),第1章 線性規(guī)劃及單純形法,一、判斷題 （1）圖解法與單純形法雖然求解的形式不同，但從幾何上理解，兩者是一致的。 正確。 （2）線性規(guī)劃模型中增加一個約束條件，可行域的范圍一般將縮小，減少一個約束條件，可行域的范圍一般將擴(kuò)大。 正確。這里注意：增加約束，可行域不會變大；減少約束，可行域不會變小。 （3）線性規(guī)劃問題的每一個基解對應(yīng)可行域的一個頂點(diǎn)。 錯誤。線性規(guī)劃的基本定理之一為：線性規(guī)劃問題的基本可行解對應(yīng)于可行域的頂點(diǎn)。,（7）單純形法計算中，如不按最小比值原則選取換出變量，則在下一個解中至少有一個基變量的值為負(fù)。 正確。 （8）一旦一個人工變量在迭代中變?yōu)榉腔兞亢?，則

2、該變量及相應(yīng)列的數(shù)字可以從單純形表中刪除，而不影響計算結(jié)果。 正確。 人工變量一般是為取得對應(yīng)的初始基基向量而引入的，它一旦成為出基變量，其地位已被對應(yīng)的入基變量取代，刪除單純形表中該變量及相應(yīng)列的數(shù)字，不影響計算結(jié)果。,（11）線性規(guī)劃問題的可行解如為最優(yōu)解，則該可行解一定是基本可行解。 錯誤。 唯一最優(yōu)解時，最優(yōu)解是可行域頂點(diǎn)，對應(yīng)基本可行解；無窮多最優(yōu)解時，除了其中的可行域頂點(diǎn)對應(yīng)基本可行解外，其余最優(yōu)解不是可行域的頂點(diǎn)。 （12）若線性規(guī)劃問題具有可行解，且其可行域有界，則該線性規(guī)劃問題最多具有有限個數(shù)的最優(yōu)解。 錯誤。 如果在不止一個可行解上達(dá)到最優(yōu)，它們的凸組合仍然是最優(yōu)解，這樣就

3、有了無窮多的最優(yōu)解。,(13)若線性規(guī)劃問題的可行域可以伸展到無限，則該問題一定具有無界解。 錯誤。 （14）如果某線性規(guī)劃模型的一個最優(yōu)解不是基可行解，則可以斷定該問題有無窮多最優(yōu)解。 正確,二、選擇題,1.用單純形法求解線性規(guī)劃問題采用兩階段法計算時，第一階段計算的單純形表中人工變量系數(shù)取值（） A.必須為“-1”，其余變量系數(shù)為“0”； B.可取某一負(fù)的常數(shù)，其余變量系數(shù)為“0”； C.取值為零，其余變量系數(shù)為原目標(biāo)函數(shù)中系數(shù)Cj值； D.為某一正的常數(shù)值，其余變量取值為“0”。 答案：D,六、已知某線性規(guī)劃問題單純形法迭代時得到中間某兩步的單純形表如下表所示，試將表中空白處的數(shù)字填上。

4、,檢驗(yàn)數(shù)：(0,0,0,-45/41,-24/41,-11/41),第2章 線性規(guī)劃的對偶理論,一、判斷題 （1）任何線性規(guī)劃問題存在并具有唯一的對偶問題。 正確。 （2）對偶問題的對偶一定是原問題。 正確。 （3）根據(jù)對偶問題的性質(zhì)，當(dāng)原問題為無界解時，其對偶問題無可行解；反之，當(dāng)對偶問題無可行解時，其原問題具有無界解。 錯誤。,二、已知線性規(guī)劃問題： （a）寫出其對偶問題； （b）已知原問題用兩階段法求解時得到的最終單純形表如下,試寫出其對偶問題的最優(yōu)解。,三、,四、某廠生產(chǎn)、三種產(chǎn)品，分別經(jīng)過A、B、C三種設(shè)備加工，已知生產(chǎn)單位各種產(chǎn)品所需要的設(shè)備臺時，設(shè)備的現(xiàn)有加工能力以及每件產(chǎn)品的預(yù)

5、期的利潤如下表：,第3章 運(yùn)輸問題,（4）如果運(yùn)輸問題單位運(yùn)價表的某一行（或某一列）元素分別加上一個常數(shù)k，最優(yōu)調(diào)運(yùn)方案將不會發(fā)生變化。 正確。 （5）如果運(yùn)輸問題單位運(yùn)價表的某一行（或某一列）元素分別乘上一個常數(shù)k，最優(yōu)調(diào)運(yùn)方案將不會發(fā)生變化。 錯誤。 （6）如果運(yùn)輸問題單位運(yùn)價表的全部元素乘上一個常數(shù)k（k0），最優(yōu)調(diào)運(yùn)方案將不會發(fā)生變化。 正確。,（7）用位勢法求運(yùn)輸問題某一調(diào)運(yùn)方案的檢驗(yàn)數(shù)時，其結(jié)果可能同閉回路法求得的結(jié)果有異。 錯誤。 （8）運(yùn)輸問題初始方案的基本要求:（m+n-1）個數(shù)字格，不存在全部以數(shù)字格為頂點(diǎn)的閉回路。 正確。,二、已知運(yùn)輸問題的產(chǎn)銷平衡表，單位運(yùn)價表及某一調(diào)

6、運(yùn)方案如下：,產(chǎn)銷平衡表及調(diào)運(yùn)方案 單位運(yù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）指派問題效率矩陣的每個元素都乘上同一個常數(shù)k，將不影響最優(yōu)指派方案； 錯誤。 （5）指派問題數(shù)學(xué)模型的形式同運(yùn)輸問題十分相似，故也可以用表上作業(yè)法求解； 正確。 （6）用割平面法求

7、解整數(shù)規(guī)劃時，構(gòu)造的割平面有可能切去一些不屬于最優(yōu)解的整數(shù)。 錯誤。,（7）分枝定界法在需要分枝時必須滿足：一是分枝后的各子問題必須容易求解；二是各個子問題解的集合必須覆蓋原問題的解。 正確。 （8）一個整數(shù)規(guī)劃問題如果存在兩個以上的最優(yōu)解，則該問題一定有無窮多最優(yōu)解。 錯誤。,二、某科學(xué)實(shí)驗(yàn)衛(wèi)星擬從下列儀器裝置中選若干件裝上，有關(guān)數(shù)據(jù)資料如下表：,三、,四、,五、,第5章 目標(biāo)規(guī)劃,一、判斷題 （1）線性規(guī)劃問題是目標(biāo)規(guī)劃問題的一種特殊形式。 正確。 （2）正偏差變量取正值，負(fù)偏差變量應(yīng)取負(fù)值。 錯誤。 （3）目標(biāo)規(guī)劃模型中，可以不包含系統(tǒng)約束（絕對約束），但必須包含目標(biāo)約束。 正確。,選擇

8、題,1.對于目標(biāo)規(guī)劃模型，下述（ ）的表述是不正確的。 A.可以不含有系統(tǒng)約束； B.目標(biāo)約束方程必須同時含有正負(fù)偏差變量； C.單純形法求解時，若存在小于0的檢驗(yàn)數(shù)，則需繼續(xù)迭代需找最優(yōu)解； D.目標(biāo)函數(shù)不應(yīng)出現(xiàn)關(guān)于偏差變量最大化的結(jié)構(gòu)。 答案：C。,二、,五、,C點(diǎn),第6章 圖與網(wǎng)絡(luò)分析,（4）求圖的最小支撐樹以及求圖中一點(diǎn)至另一點(diǎn)的最短路問題，都可以歸結(jié)為求解整數(shù)規(guī)劃問題。 正確。 （5）任一圖中奇點(diǎn)的個數(shù)可能為奇數(shù)個，也可能為偶數(shù)個。 錯誤。 （6）任何n個節(jié)點(diǎn)，（n-1）條邊的圖一定是樹圖。 錯誤。,選擇題,1.已知某個連通圖共有6個偶點(diǎn)，則下述（ ）可能成為其含有奇點(diǎn)的個數(shù)。 A.

9、3 B.5 C.7 D.8 答案：D。,第7章 計劃評審方法和關(guān)鍵路線法,一、判斷題。 （1）網(wǎng)絡(luò)圖中只能有一個始點(diǎn)和一個終點(diǎn)； 正確。 （2）網(wǎng)絡(luò)圖中因虛作業(yè)的時間為零，因此在各項(xiàng)時間參數(shù)的計算中可將其忽略。 錯誤。 （3）網(wǎng)絡(luò)圖中關(guān)鍵路線的延續(xù)時間相當(dāng)于求圖中從起點(diǎn)到終點(diǎn)的最短路。 錯誤。,（4）網(wǎng)絡(luò)圖中求關(guān)鍵路線的問題可表達(dá)為求解一個線性規(guī)劃模型； 正確。 （5）網(wǎng)絡(luò)圖中從一個事件出發(fā)如果存在多項(xiàng)作業(yè)，則其中用時最長的一項(xiàng)作業(yè)必包含在該網(wǎng)絡(luò)圖的關(guān)鍵路線內(nèi)。 錯誤。 （6）一項(xiàng)非關(guān)鍵路線上的作業(yè)在其最早開始于最遲結(jié)束的時間段內(nèi)均可任意安排。 錯誤。 （7）若一項(xiàng)作業(yè)的總時差為10d，說明任

10、何情況下該項(xiàng)作業(yè)從開始到結(jié)束之間總有10d的機(jī)動時間。 錯誤。,（8）一個網(wǎng)絡(luò)只存在唯一的關(guān)鍵路線。 錯誤。 （9）為了在最短時間內(nèi)完成項(xiàng)目，其關(guān)鍵路線上作業(yè)的開始或結(jié)束時間不允許有任何延遲。 正確。 （10）網(wǎng)絡(luò)關(guān)鍵路線上的所有作業(yè)，其總時差和自由時差均為零。 正確。 （11）任何非關(guān)鍵路線上的作業(yè)，其總時差和自由時差均不為零。 錯誤。,（12）若一項(xiàng)作業(yè)的總時差為零，則其自由時差一定為零。 正確。 （13）若一項(xiàng)作業(yè)的自由時差為零，則其總時差比為零。 錯誤。 （14）當(dāng)作業(yè)時間用a,m,b三點(diǎn)估計時，m等于完成該項(xiàng)作業(yè)的期望時間。 錯誤。,第8章 動態(tài)規(guī)劃,一、判斷題。 （1）動態(tài)規(guī)劃的最優(yōu)性原理保證了從某一狀態(tài)開始的未來決策獨(dú)立于先前已作出的決策。 正確。 （2）對一個動態(tài)規(guī)劃問題，應(yīng)用順推或逆推解法可能會得出不同的最優(yōu)解。 錯誤。 （3）一個動態(tài)規(guī)劃問題若能用網(wǎng)絡(luò)表達(dá)時，節(jié)點(diǎn)代表各階段的狀態(tài)值，各條弧代表了可行的方案選擇。 正確。,