運(yùn)籌學(xué)復(fù)習(xí)題

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

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

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

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

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

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

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

8、80=0.192。為了促進(jìn)三種新產(chǎn)品的研制，決定增撥2萬元的研制費(fèi)，并要資金集中使用，以萬元為單位分配。其增撥研制費(fèi)與新產(chǎn)品不成功的概率如表5所示。試問如何分配費(fèi)用，使這三種新產(chǎn)品都研制不成功的概率為最小。表5新產(chǎn)品研制費(fèi)S不成功概率ABC0120.400.200.150.600.400.200.800.500.30五、分配甲、乙、丙、丁、戊五個(gè)人去完成A、B、C、D、E五項(xiàng)工作，每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間如下表所示。 (表中單位：小時(shí))任務(wù)人數(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已知甲不可能完成任務(wù)D，丁只可以完成任務(wù)B、C，試確定最優(yōu)分配方案，使完成任務(wù)的總時(shí)間為最少。 答案:1025，即第一年年初購(gòu)新車，第三年年初購(gòu)新車。2（1）T=31.5（2）37.07%3結(jié)論：按實(shí)際盈利額選存的擴(kuò)建方案；如按效用值選明年的擴(kuò)建方案。41-0-1, =0.065、答：解： 即：甲A；乙E；丙B；丁C；戊D Min Z=25+33+27+37+20=142小時(shí) 第三階段練習(xí)題一、填空題1在矩陣對(duì)策中，（是解的條件是 。2在標(biāo)準(zhǔn)的M/M/1排隊(duì)系統(tǒng)中，設(shè)顧客到達(dá)率為，服務(wù)率為，則隊(duì)長(zhǎng)_，它表示系統(tǒng)中的_，排隊(duì)長(zhǎng)_，它表示系統(tǒng)中的_，_。3若由一種情況轉(zhuǎn)換至另

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

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

12、)三、活動(dòng)活動(dòng)節(jié)點(diǎn)趕工期直接費(fèi)用增長(zhǎng)率活動(dòng)時(shí)間活動(dòng)費(fèi)用a*b*cd*e*f*0112132324340003110.0000.0000.0005000.0001666.6674250.0001474735000.0008000.00014000.00015000.0009666.66711750.000*：關(guān)鍵路徑活動(dòng)整個(gè)工程周期：12 直接費(fèi)用總額：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ù)量益損值（元）訂購(gòu)數(shù)量50100150200501001001001001000200200200150-100100300300200-2000200400（2）悲觀法：50，樂觀法：200，等可能法：100或150（3）后悔矩陣：銷售數(shù)量后悔值（元）訂購(gòu)數(shù)量50100150200Max500100200300300100100010020020015020010001002002003002001000300故按后悔值法決策為200。運(yùn)籌學(xué)

14、第四階段練習(xí)題一、填空題1除圖解法外，常用的求解線性規(guī)劃問題的方法是 。2在矩陣對(duì)策中，（是解的條件是 。 3設(shè)P為概率矩陣，則當(dāng)時(shí)，稱作P的_。二、某臺(tái)機(jī)器可連續(xù)工作4年，也可于每年末賣掉，換一臺(tái)新的。已知于各年初購(gòu)置一臺(tái)新機(jī)器的價(jià)格及不同役齡機(jī)器年末的處理價(jià)如下表所示，又新機(jī)器第一年運(yùn)行及維護(hù)費(fèi)用為0.3萬元，使用1-3年后機(jī)器每年的運(yùn)行及維修費(fèi)用為0.8、1.5、2.0萬元。試確定該機(jī)器的最優(yōu)更新策略，使4年內(nèi)用于更換、購(gòu)買及運(yùn)行維修的總費(fèi)用為最省。單位：萬元j第一年第二年第三年第四年年初購(gòu)置價(jià)2.52.62.83.1使用j年后的處理價(jià)2.01.61.31.1三、已知線性規(guī)劃問題： 求：（1）用圖解法求解； （2）寫出其對(duì)偶問題； （3）直接寫出對(duì)偶問題的最優(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