運(yùn)籌學(xué)試題講解

1、習(xí)題講解一、判斷題（共計10分，每小題1分，對的打，錯的打X）1. 無孤立點(diǎn)的圖一定是連通圖。2. 對于線性規(guī)劃的原題和其對偶問題，若其中一個有最優(yōu)解，另一個也一定有最優(yōu)解。 3. 如果一個線性規(guī)劃問題有可行解，那么它必有最優(yōu)解。4對偶問題的對偶問題一定是原問題。5用單純形求解標(biāo)準(zhǔn)形式（求最小值）的線性規(guī)劃問題時，與對應(yīng)的變量都可以被選作換入變量。6若線性規(guī)劃的原問題有無窮多個最優(yōu)解時，其對偶問題也有無窮多個最優(yōu)解。7. 度為0的點(diǎn)稱為懸掛點(diǎn)。8. 表上作業(yè)法實(shí)質(zhì)上就是求解運(yùn)輸問題的單純形法。 9. 一個圖G 是樹的充分必要條件是邊數(shù)最少的無孤立點(diǎn)的圖。10. 任何線性規(guī)劃問題都存在且有唯一的

2、對偶問題。 10XXXX一、判斷題（對的打，錯的打X. 共計10分，答在下面的表格中）1、單純形法計算中，選取最大正檢驗(yàn)數(shù)對應(yīng)的變量作為換入變量，可使目標(biāo)函數(shù)值得到最快的減少。2、單純形法計算中，如不按最小非負(fù)比值原則選出換出變量，則在下一個解中至少有一個基變量的值是負(fù)的。 3、對于一個動態(tài)規(guī)劃問題，應(yīng)用順推法和逆推法可能會得到不同的最優(yōu)解。4、應(yīng)用對偶單純形法計算時，若單純形表中某一基變量，且所在行的所有元素都大于或等于零，則其對偶問題具有無界解。5、用位勢法計算檢驗(yàn)數(shù)時，每一行（或列）的位勢的值是唯一的，所以每一個空格的檢驗(yàn)數(shù)是唯一的。 6、動態(tài)規(guī)劃的最短路問題也可以用圖論中求最短路問題的

3、方法求解。 7、圖論中的圖是為了研究問題中有哪些對象及對象之間的關(guān)系，它與圖的幾何形狀無關(guān)。 8、 動態(tài)規(guī)劃只是用來解決和時間有關(guān)的問題。 9、在畫網(wǎng)絡(luò)計劃圖時，允許有多個起點(diǎn)和多個終點(diǎn)。10、因?yàn)檫\(yùn)輸問題是一種特殊的線性規(guī)劃模型，因而求其解也可能出現(xiàn)下列四種情況：有唯一最優(yōu)解；有無窮多個最優(yōu)解；無界解；無可行解。10XXXXXXX一、 判斷題（每題1分，共15分）（ ）1、 若線性規(guī)劃問題存在兩個不同的最優(yōu)解，則必然有無窮多個最優(yōu)解。（ ）2、 圖解法同單純形法雖然求解形式不同，但從幾何上理解，兩者是一致的。（ ）3、 連通圖G的生成樹是取G的部分點(diǎn)和部分邊所組成的樹。（ ）4、 如線性規(guī)劃

4、問題存在最優(yōu)解，則最優(yōu)解一定對應(yīng)可行域邊界上的一個點(diǎn)。（ ）5、 按最小元素法（或Vogel法）給出的初始基可行解，從每一空格出發(fā)可以找到而且僅能找到惟一的閉回路。（ ）6、 已知yi*為線性規(guī)劃的對偶問題的最優(yōu)解，若yi*=0，說明在最優(yōu)生產(chǎn)計劃中第i種資源一定有剩余。（ ）7、 對偶問題的對偶問題未必是原問題。（ ）8、 當(dāng)目標(biāo)規(guī)劃模型中存在x1 + x2 + d- = 4的約束條件，則該約束為系統(tǒng)約束。（ ）9、目標(biāo)規(guī)劃中的正偏差變量大于等于零，負(fù)偏差變量小于等于零。（ ）10、整數(shù)規(guī)劃解的目標(biāo)函數(shù)值一般優(yōu)于其相應(yīng)的線性規(guī)劃問題的解的目標(biāo)函值。（ ）11、樹圖是邊數(shù)最多的無圈的連通圖。（

5、 ）12、求網(wǎng)絡(luò)最大流的問題可以歸結(jié)為求解一個線性規(guī)劃模型。（ ）13、圖論中的圖不論反映了研究對象之間的關(guān)系，而且是真實(shí)圖形的寫照，因而對圖中點(diǎn)與點(diǎn)的相對位置，點(diǎn)與點(diǎn)連線的長短曲直等都要嚴(yán)格注意。（ ）14、動態(tài)規(guī)劃的基本方程是將一個多階段的決策問題轉(zhuǎn)化為一系列具有遞推關(guān)系的單階段的決策問題。（ ）15、在動態(tài)規(guī)劃模型中，問題的階段數(shù)等于問題的子問題的數(shù)目。二、 單項(xiàng)選擇題（正確得2 分，選錯、多選或不選得0 分。共20 分）1原問題與對偶問題都有可行解，則（ ）。A原問題有最優(yōu)解，對偶問題沒有最優(yōu)解 B. 原問題與對偶問題可能都沒有最優(yōu)解C. 一個問題有最優(yōu)解，另一個問題有無界解 D. 原

6、問題與對偶問題都有最優(yōu)解2、當(dāng)線性規(guī)劃問題的可行解集合非空時一定（ ）。 A. 包含原點(diǎn)X=（0，0，） B. 有界 C. 無界 D. 是凸集3、 若原問題中xi 為自由變量，那么對偶問題中的第i個約束一定為（ ）。A. 等式約束 B. “”型約束 C. “”約束 D. 無法確定4在目標(biāo)規(guī)劃中，要求不低于第一目標(biāo)值，恰好完成第二目標(biāo)值，則其目標(biāo)函數(shù)為（ ）。A. min Z = P1d1- + P2（d2- + d2+） B. min Z = P1d1+ + P2（d2- + d2+）C. min Z = P1（d1- + d1+） + P2（d2- + d2+） D. min Z = P1（

7、d2- + d2+） + P2d2-5若樹 T 有 n 個點(diǎn)，那么它的邊數(shù)一定是（ ）。A. 2n B. n C. n+1 D. n-16完全決定確定型動態(tài)規(guī)劃問題第k+1階段的狀態(tài)Sk+1 的是（ ）。 A. 階段數(shù)k B. 決策Uk C. 狀態(tài)Sk D. 狀態(tài)Sk 與決策Uk7任何圖中，次為奇數(shù)的頂點(diǎn)的個數(shù)必為（ ）。A. 奇數(shù) B. 偶數(shù) C. 奇偶性無法判斷 D. 奇數(shù)偶數(shù)均可8圖G=(V,E)有生成樹的充要條件是（ ）。A. G是歐拉圖 B. G是完全圖 C. G是連通圖 D. G是有限圖9求m個產(chǎn)地，n個銷地的運(yùn)輸問題的表上作業(yè)法中，用最小元素法確定初始可行解時基變量（即填有數(shù)字格

8、）的個數(shù)為（ ） A. m+n-1 B. m+n C. m+n+1 D. mn10求解指派問題的匈牙利方法要求系數(shù)矩陣中每個元素都是（ ）。A. 非負(fù)的 B. 大于零 C. 無約束 D. 非零常數(shù)三、某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示。（15分）（1）寫出問題的數(shù)學(xué)模型 （2）求獲最大利潤的方案。甲乙設(shè)備能力設(shè)備A3265設(shè)備B2140設(shè)備C0375利潤（元/件）15002500三、 已知下表（表31）為求解某線性規(guī)劃問題的最終單純形表，表中為松弛變量，問題的約束為 £

9、 形式 表 315/201/211/25/211/201/61/300（） 寫出原線性規(guī)劃問題；（） 寫出原問題的對偶問題；直接由表寫出對偶問題的最優(yōu)解。三、現(xiàn)在有線性規(guī)劃問題（15分）max z=-5+5+13的最優(yōu)單純形表如下：Cj-551300b5X2-11310200X5160-2-4110r00-2-50-100（1）約束條件2的右端常數(shù)由90變?yōu)榱?0,對最優(yōu)基、最優(yōu)解有何影響？如果有影響請求出最優(yōu)解。（2）目標(biāo)函數(shù)中的系數(shù)由13變?yōu)?,對最優(yōu)基、最優(yōu)解有何影響？如果有影響請求出最優(yōu)解。三、靈敏度分析（10分）已知原問題的最終單純形表為：23000基23101/201/504002

10、14/53301001/500101/5試分析：1. 試計算原問題的檢驗(yàn)數(shù)，并判斷解的類型。2. 分析在什么范圍變動，最優(yōu)解不變？（可以直接在上表中添加）答：1. 原問題檢驗(yàn)數(shù)如上圖，所有非基變量檢驗(yàn)數(shù)小于零，有唯一的最優(yōu)解。（3分）2. 考慮目標(biāo)函數(shù)系數(shù)（產(chǎn)品價格）變化后的最終單純形表為：（3分）cj 23000CB基bx1x2x3x4x52x13101/201/50x4400214/53x2301001/5cjzj00(2)/20(1)/5最優(yōu)解條件為：，可得：（4分）六、有一運(yùn)輸問題平衡作業(yè)表如下：（10分，每小題5分）銷地產(chǎn)地B1B1B2B3產(chǎn)量A19 3 8 73A249 45 3A

11、35 7 6 25銷量12351） 為此運(yùn)輸問題確定初始調(diào)運(yùn)方案；2） 計算檢驗(yàn)數(shù)填于表中，并判斷初始調(diào)運(yùn)方案是否為最優(yōu)方案。五、運(yùn)輸問題（10分）某糖果經(jīng)銷公司的3個加工廠A1、A2、A3每天產(chǎn)量分別為7噸、4噸、9噸；這些產(chǎn)品要運(yùn)往4處經(jīng)銷點(diǎn)B1、B2、B3、B4，每天的銷量為3噸、6噸、5噸、6噸；產(chǎn)銷地點(diǎn)之間距離不同等因素形成的運(yùn)價如下表：產(chǎn)地 銷地B1B2B3B4A1311310A21928A3741051請列出該問題的產(chǎn)銷平衡表（問題2可在該表上分析）？2請采用表上作業(yè)法的最小元素法求出初始分配方案？ 3現(xiàn)已知僅有一處空格可以改進(jìn)，請采用閉回路法對空格A2B4進(jìn)行最優(yōu)性檢驗(yàn)，并求出最佳總費(fèi)用。六、 學(xué)校游泳隊有四名隊員，現(xiàn)在需組織參加全國大學(xué)生運(yùn)動會的游泳比賽，其中200米混合泳接力賽是一項(xiàng)反映綜合實(shí)力的項(xiàng)目，教