運籌學復習題

1、運籌學復習題第一階段練習題一、填空題1某足球隊要從1、2、3、4號五名隊員中挑選若干名上場，令 ，請用xi的線性表達式表示下列要求：(1)若2號被選中，則4號不能被選中：_；(2)只有1名隊員被選中，3號才被選中：_。2線性規(guī)劃的對偶問題約束的個數(shù)與原問題_的個數(shù)相等。因此，當原問題增加一個變量時，對偶問題就增加一個_。這時，對偶問題的可行域?qū)⒆僟(大、小還是不變？)，從而對偶目標值將可能變_(好還是壞？)。3將非平衡運輸問題化為平衡運輸問題，在表上相當于增加一個虛設的 ，在模型中相當于增加若干個 變量。二、某廠生產(chǎn)，三種產(chǎn)品。產(chǎn)品依次經(jīng)A、B設備加工，產(chǎn)品經(jīng)A、C設備加工，產(chǎn)品經(jīng)C、B設備加

2、工。已知有關數(shù)據(jù)如下表所示，請為該廠制定一個最優(yōu)的生產(chǎn)計劃。產(chǎn)品機器生產(chǎn)率（件/小時）原料成本產(chǎn)品價格A B C10 2020 5 10 201525105010045機器成本（元/小時）200 100 200每周可用小時數(shù)50 45 60三、某廠準備生產(chǎn)A、B、C三種產(chǎn)品，它們都消耗勞動力和材料，有關數(shù)據(jù)見下表所示：產(chǎn)品消耗定額資源ABC擁有量（單位）勞動力材料6334554530單位產(chǎn)品利潤（元）314（1）確定獲利最大的產(chǎn)品生產(chǎn)計劃；（2）產(chǎn)品A的利潤在什么范圍內(nèi)變動時，上述最優(yōu)計劃不變；（3）如設計一種新產(chǎn)品D，單件勞動力消耗為8單位，材料消耗為2單位，每件可獲利3元，問該種產(chǎn)品是否值

3、得生產(chǎn)？（4）如勞動力數(shù)量不變，材料不足時可從市場購買，每單位0.4元，問該廠要不要購進原材料擴大生產(chǎn)，購多少為宜？四、已知某運輸問題的產(chǎn)銷平衡表和單價運價表如下表所示：銷地產(chǎn)地B1B2B3B4B5B6產(chǎn)量A1A2A3A424341252324234213442541250406031銷量305020403011求：（1）求最優(yōu)的運輸調(diào)撥方案；（2）單位運價表中的c12，c35，c41分別在什么范圍內(nèi)變化時，上面求出的最優(yōu)調(diào)撥方案不變。五、某彩色電視機組裝工廠，生產(chǎn)A、B、C三種規(guī)格電視機。裝配工作在同一生產(chǎn)線上完成，三種產(chǎn)品裝配時的工時消耗分別為6小時，8小時和10小時。生產(chǎn)線每月正常工作時

4、間為200小時；三種規(guī)格電視機銷售后，每臺可獲利分別為500元，650元和800元。每月銷量預計為12臺、10臺、6臺。該廠經(jīng)營目標如下：利潤指標定為每月元；：充分利用生產(chǎn)能力；：加班時間不超過24小時；：產(chǎn)量以預計銷量為標準；為確定生產(chǎn)計劃，試建立該問題的目標規(guī)劃模型。答案：一、填空題12變量個數(shù)，約束條件，小，壞3產(chǎn)地或銷地，松弛（或剩余）二、答：用表示第種產(chǎn)品的生產(chǎn)數(shù)量，使該廠獲利最大的線性規(guī)劃模型為：三、答：（1）建立線性規(guī)劃模型，模型中，分別代表A、B、C產(chǎn)品的產(chǎn)量，用單純形法求解得最優(yōu)計劃的單純形表如下： 5 310-1/31011/3-1/5-1/32/50-20-1/5-3/5

5、（2）產(chǎn)品A利潤在（）范圍內(nèi)變化時，最優(yōu)計劃不變。（3）安排生產(chǎn)新產(chǎn)品D是合算的（4）材料市場價格低于影子價格，故購進是合算的。用參數(shù)規(guī)劃計算確定購15單位為最適宜。四、答：（1）最優(yōu)的運輸調(diào)撥方案如下表所示：B1B2B3B4B5B6產(chǎn)量A1A2A3A42010302020391301150406031銷量305020403011（2）保持最優(yōu)調(diào)撥方案不變的cij變化范圍為：c121；c353；c412五、答：設生產(chǎn)電視機A型為臺，B型為臺，C型為臺，該問題的目標規(guī)劃模型為：第二階段練習題一、某汽車公司制定5年內(nèi)購買汽車的計劃，下面給出一輛新汽車的價格（如表1所示）以及一輛汽車的使用維修費用（

6、萬元，如表2所示）。使用網(wǎng)絡分析中最短路方法確定公司可采用的最優(yōu)策略。表1年號12345價格22.12.32.42.6表2汽車使用年齡0112233445維修費用0.71.11.522.5二、某項工程有關資料如表3所示，工序緊前工序平均工序時間(周)估計的工序時間方差A21.05B32.25CB2.54.34DB63.70EA、C204.95FD、E44.66GF24.05(1)畫出工程網(wǎng)絡圖，確定關鍵工序及完工期；(2)求工程在30周內(nèi)完成的概率。三、某工廠正在考慮是現(xiàn)在還是明年擴大生產(chǎn)的規(guī)模。由于可能出現(xiàn)的市場需求情況不一樣，預期利潤也不同。已知市場需求為高（）、中（）、低（）的概率及不同

7、方案的預期利潤（單位：萬元），如表4所示。對該廠來說，損失1萬元的效用值為0，獲利10萬元效用值為100，對以下事件效用值無差別：肯定得8萬元或0.9概率得10萬和0.1概率失去1萬；肯定得6萬或0.8概率得10萬和0.2概率失去1萬；肯定得1萬或0.25概率得10萬和0.75概率失去1萬。表4事件概率方案現(xiàn)在擴大明年擴大10886-11要求：（1）建立效用值表（2）分別根據(jù)實際盈利額和效用值按期望值法確定最優(yōu)決策。四、某工廠在一年進行了A、B、C三種新產(chǎn)品試制，由于資金不足，估計在年內(nèi)這三種新產(chǎn)品研制不成功的概率分別是0.40、0.60、0.80，因而都研制不成功的概率為0.400.600.

8、80=0.192。為了促進三種新產(chǎn)品的研制，決定增撥2萬元的研制費，并要資金集中使用，以萬元為單位分配。其增撥研制費與新產(chǎn)品不成功的概率如表5所示。試問如何分配費用，使這三種新產(chǎn)品都研制不成功的概率為最小。表5新產(chǎn)品研制費S不成功概率ABC0120.400.200.150.600.400.200.800.500.30五、分配甲、乙、丙、丁、戊五個人去完成A、B、C、D、E五項工作，每個人完成各項任務的時間如下表所示。 (表中單位：小時)任務人數(shù)A B C D E甲乙丙丁戊25 28 31 41 3840 38 26 26 33 35 27 28 40 32 24 42 37 23 45 30

9、29 26 20 32已知甲不可能完成任務D，丁只可以完成任務B、C，試確定最優(yōu)分配方案，使完成任務的總時間為最少。 答案:1025，即第一年年初購新車，第三年年初購新車。2（1）T=31.5（2）37.07%3結論：按實際盈利額選存的擴建方案；如按效用值選明年的擴建方案。41-0-1, =0.065、答：解： 即：甲A；乙E；丙B；丁C；戊D Min Z=25+33+27+37+20=142小時 第三階段練習題一、填空題1在矩陣對策中，（是解的條件是 。2在標準的M/M/1排隊系統(tǒng)中，設顧客到達率為，服務率為，則隊長_，它表示系統(tǒng)中的_，排隊長_，它表示系統(tǒng)中的_，_。3若由一種情況轉(zhuǎn)換至另

10、外一種情況的過程具有轉(zhuǎn)移概率，而且此種轉(zhuǎn)移概率又可以依據(jù)緊接的前項情況推算出來，則這種過程稱為_。二、（1）某基建項目的活動明細表如下，編繪該項目的箭線式網(wǎng)絡圖?；顒用骷毐砘顒用QABCDEF緊前活動無AABCC，D（2）求以下箭線式網(wǎng)絡圖的關鍵路線及工程完工期(時間單位：天)三、已知某工程有六項活動，有關數(shù)據(jù)如下表：活動正常時間極限時間正常直接費用極限直接費用a(01)b(12)c(13)d(23)e(24)f(34)1477841354525000800014000100008000750050001400020000150001300016000（1）畫出箭線式網(wǎng)絡圖；（2）如果要求趕工

11、期，在12周內(nèi)完成，請給出優(yōu)化方案。四、求下圖的網(wǎng)絡最大流，并寫出最小割集。 V1 4 V4 8 7 6 4 5Vs 9 V2 3 V5 3 Vt 15 5 2 8 7 V3 7 V6五、某書店希望訂購最新出版的好圖書出售。根據(jù)以往經(jīng)驗，新書的銷售量可能為50本，100本，150本或200本。假定每本書的訂購價為4元，銷售價為6元，剩余處理價為每本2元。試求：（1）建立損益矩陣；（2）分別用悲觀法、樂觀法及等可能發(fā)決定該書店應訂購的新書數(shù)量；（3）建立后悔矩陣，并用后悔值法決定書店應訂購的新書數(shù)。答案:一、填空題12，平均顧客數(shù)，排隊等待的平均顧客數(shù)，3馬爾科夫過程二、工程完工期：T=22(天

12、)三、活動活動節(jié)點趕工期直接費用增長率活動時間活動費用a*b*cd*e*f*0112132324340003110.0000.0000.0005000.0001666.6674250.0001474735000.0008000.00014000.00015000.0009666.66711750.000*：關鍵路徑活動整個工程周期：12 直接費用總額：63416.667四、解：找增廣鏈： (Vs,4) V1 (4,4) V4 (8,4) 7 6 4 (5,4)Vs ( 9,3) V2 (V1,4) (3,3) V5 (3,3) Vt (15,7) 5 2 8 (7,7) V3 (7,7) V6

13、 (Vs,8) 最小割集為：V*=（V3，V6），（V2，V5），（V1，V4） C*（V，V）=14 且V*（f）=14 五、答：（1）損益矩陣銷售數(shù)量益損值（元）訂購數(shù)量50100150200501001001001001000200200200150-100100300300200-2000200400（2）悲觀法：50，樂觀法：200，等可能法：100或150（3）后悔矩陣：銷售數(shù)量后悔值（元）訂購數(shù)量50100150200Max500100200300300100100010020020015020010001002002003002001000300故按后悔值法決策為200。運籌學

14、第四階段練習題一、填空題1除圖解法外，常用的求解線性規(guī)劃問題的方法是 。2在矩陣對策中，（是解的條件是 。 3設P為概率矩陣，則當時，稱作P的_。二、某臺機器可連續(xù)工作4年，也可于每年末賣掉，換一臺新的。已知于各年初購置一臺新機器的價格及不同役齡機器年末的處理價如下表所示，又新機器第一年運行及維護費用為0.3萬元，使用1-3年后機器每年的運行及維修費用為0.8、1.5、2.0萬元。試確定該機器的最優(yōu)更新策略，使4年內(nèi)用于更換、購買及運行維修的總費用為最省。單位：萬元j第一年第二年第三年第四年年初購置價2.52.62.83.1使用j年后的處理價2.01.61.31.1三、已知線性規(guī)劃問題： 求：（1）用圖解法求解； （2）寫出其對偶問題； （3）直接寫出對偶問題的最優(yōu)解。答案：一、填空題1單純形法23固定概率矩陣（平衡概率矩陣）二、解： 6.0 2.3 2.0 2.1 0.8 0.9 1.1 1.40 1 2 3 40 0.8 1