運籌學(xué)考試練習(xí)題天津大學(xué)

1、07級工管運籌學(xué)期末習(xí)題課一、考慮線性規(guī)劃問題（P）（1） 若均為（P）的可行解，證明也是（P）的可行解；（2） 寫出（P）的對偶模型（仍用矩陣式表示）。二、有三個線性規(guī)劃：() Min z=CX () Min z¢=C¢X () Min =CX約束條件AX=b 約束條件AX=b 約束條件AX= X³0 X³0 X³0已知 X*是()的最優(yōu)解，X¢*是()的最優(yōu)解，是()的最優(yōu)解，Y*是()的對偶問題的最優(yōu)解，試證：（1）； (2) 。三、已知線性規(guī)劃問題 當(dāng)0時，用單純形法求得最終表如下： 5/201/211/20 5/21-1/2

2、0-1/61/30-40-4-2要求：1. 確定的值； 2. 當(dāng)0時，在什么范圍內(nèi)變化上述最優(yōu)解不變； 3. 當(dāng)0時，在什么范圍內(nèi)變化上述最優(yōu)基不變。四、某公司準(zhǔn)備以甲、乙、丙三種原料生產(chǎn)A、B、C、D四種型號的產(chǎn)品，每一單位產(chǎn)品對各原料的消耗系數(shù)、價格系數(shù)及原料成本等已知條件如下表：產(chǎn)品原料ABCD原料成本（百元/公斤）原料限量（公斤） 甲 1.5 2 4 3 4 5500 乙 4 1 2 1 5 3500 丙 2 3 1 2 2 2000單位產(chǎn)品價格（百元/公斤）453540301為解決“在現(xiàn)有原料量限制下，如何安排A、B、C、D四種產(chǎn)品的產(chǎn)量，使總利潤（這里利潤簡化為銷售收入與原料成本之

3、差）最大”這一問題，可建立一線性規(guī)劃模型，令x1、x2、x3、x4依次表示各型號產(chǎn)品的計劃產(chǎn)量，試列出這個模型，并記該模型為模型1；2利用一解線性規(guī)劃的程序解上述問題（模型1），得到的部分結(jié)果如下： OBJECTIVE FUNCTION VALUE 1) 19923.08 VARIABLE VALUE REDUCED COST X1 230.769226 0.000000 X2 100.000000 0.000000 X3 1238.461548 0.000000 X4 0.000000 4.384615 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000

4、 1.384615 3) 0.000000 1.230769 4) 0.000000 4.000000RANGES IN WHICH THE BASIS IS UNCHANGED RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 5500.000000 1499.999878 4025.000000 3 3500.000000 500.000000 749.999939 4 2000.000000 6192.307617 250.000000根據(jù)以上計算結(jié)果，分析并回答以下問題：（1）最優(yōu)

5、生產(chǎn)方案和最大總利潤是什么？按此方案生產(chǎn)，現(xiàn)有的原料是否還有剩余？哪一種有剩余？余多少？（2）如果市場上甲原料的價格為4.5（百元/公斤），那么從市場上購得1000公斤的甲原料擴大生產(chǎn)是否合算（即總利潤是否增加）？為什么？（3）若D產(chǎn)品的價格系數(shù)增大到34（百元/公斤），原最優(yōu)解會否發(fā)生變化？為什么？（4）在原考慮的A、B、C、D四種型號產(chǎn)品基礎(chǔ)上，如果又提出產(chǎn)品E，它對甲、乙、丙的消耗系數(shù)分別為5、6、2，價格系數(shù)為74（百元/公斤），那么原最優(yōu)方案是否要改變，為什么？（5）若在本題已有已知條件基礎(chǔ)上，還要考慮各產(chǎn)品的生產(chǎn)準(zhǔn)備費用（視為固定成本），其中A產(chǎn)品的生產(chǎn)準(zhǔn)備費為1000（百元），B

6、產(chǎn)品的生產(chǎn)準(zhǔn)備費為800（百元），C產(chǎn)品的生產(chǎn)準(zhǔn)備費為950（百元），D產(chǎn)品的生產(chǎn)準(zhǔn)備費為750（百元），而且由于某些原因，A、B、C三種產(chǎn)品至多生產(chǎn)其中的兩種。寫出考慮這些新增條件下（不考慮產(chǎn)品E），使生產(chǎn)利潤最大的生產(chǎn)計劃模型（不解）。五、某化學(xué)制藥廠有m種有害副產(chǎn)品，它們的數(shù)量為bi(i=1,m)。按照規(guī)定，必須經(jīng)過處理，制成n種無害物后才能廢棄。設(shè)aij為每制成一單位第j（j=1,n）種無害物可以處理掉第 i種有害物的數(shù)量，cj為制成一單位第j種無害物的費用。1 現(xiàn)欲求各無害物的產(chǎn)量xj以使總的處理費用為最小，請寫出此問題的線性規(guī)劃模型；2寫出此問題的對偶規(guī)劃模型，并解釋對偶規(guī)劃模型的

7、經(jīng)濟意義。六、一復(fù)合系統(tǒng)的結(jié)構(gòu)如下圖示意，它由4個部件串聯(lián)組成。第k個部件的功能由該部件專用的元件Ek完成，為提高系統(tǒng)的可靠性，第k個部件可由xk個相同的元件Ek并聯(lián)構(gòu)成，若每個元件的可靠度為pk，則第k個部件的可靠度為。已知4種元件的可靠度及價格見下表： 元件單價ck（元/個）可靠度pkE1350.95E2200.90E3250.85E4100.80要求設(shè)計中所用元件的總費用不超過150元，又因空間限制，第3、4個部件最多由3個元件并聯(lián)，應(yīng)如何設(shè)計使整個串聯(lián)系統(tǒng)的總可靠性最大？要求：1以xk (k=1,2,3,4)為變量，列出該問題的數(shù)學(xué)規(guī)劃模型。2若用動態(tài)規(guī)劃方法求解，選取狀態(tài)變量sk為安

8、排至第k個部件前的總可用費用，xk為決策變量，寫出以下表達式： （1）第1階段狀態(tài)集合； （2）第3階段狀態(tài)為s3時的允許決策集合；（3）狀態(tài)轉(zhuǎn)移方程；（4）階段指標(biāo)；（5）遞推方程（逆序遞推，含終端條件）。3按動態(tài)規(guī)劃方法計算第3階段狀態(tài)為75時的最優(yōu)指標(biāo)函數(shù)f3（75）和最優(yōu)決策x*3(75)。七、某投資者擬對A與B兩種基金進行投資，投資期限5年。該投資的收益有兩部分：一是長期的至第5年末的紅利收入，年利率分別為IA=0.06和IB=0.04，計復(fù)利且5年間利率不變（例如，第1年初投入A基金1元，5年后紅利收入(1+0.06)5元）；二是短期的每年利息收入，兩種基金在不同年份的利率iAk和

9、iBk見下表（例如，第1年初投入A基金1元，除5年后的紅利收入外，一年后還有0.02元的利息收入）。年份基金12345A0.0200.0230.0240.0260.030B0.0500.0500.0550.0450.055該投資者第1年初投入資金50000元，以后第2至5年初每年還再投入10000元（不包括已投資的利息收入），收益計算方法相同（如第2年初投入A基金1元，第5年末紅利收入(1+0.06)4元，同時第2至5年末還有年利息）。所有投入基金的資金（包括年利息）在第5年末之前不得支取?，F(xiàn)投資者需決定每年初的資金（當(dāng)年投入資金加已投資金的短期年利息）對基金A和B的分配額，以使第5年末總收入

10、最大。八、某汽車公司有兩家汽車配件制造廠A和B，負(fù)責(zé)向兩個服務(wù)配送中心C和D供應(yīng)汽車配件。運送的道路網(wǎng)絡(luò)及各路段的允許通過容量如下圖所示。設(shè)配件制造廠的供應(yīng)數(shù)量無限制，求向C、D的供應(yīng)量最大的運送方案和相應(yīng)的最大供應(yīng)量（求解的主要過程可在圖上標(biāo)出）。1235466020403040204030AB7CD40507050601070801235462326346311九、某工程所有關(guān)鍵工序組成的網(wǎng)絡(luò)圖如下圖所示，圖中?。搓P(guān)鍵工序）上的數(shù)字為各工序壓縮工時所需的費用（單位：百元/天）?，F(xiàn)該工程需將工期壓縮一天，試求出使總壓縮費用最小的壓縮方案（即應(yīng)在哪些工序上壓縮），以及該最小的壓縮費用。十、某

11、施工單位提交的一項目的網(wǎng)絡(luò)計劃如下圖所示，箭線下面的數(shù)字為該工作（工序）的正常工作時間（天），要求工期18天。1監(jiān)理工程師在審查該圖時發(fā)現(xiàn)工作D的緊前工作除B外還應(yīng)有A，請在圖中把這一關(guān)系正確表示出來，并指出該網(wǎng)絡(luò)計劃的關(guān)鍵線路（在圖上用雙線或色筆標(biāo)出）和（計算）工期；2當(dāng)上述網(wǎng)絡(luò)計劃尚未實施時，建設(shè)單位提出需增加工作M，它的緊前工作為A和B，緊后工作為E和G，M工作所需時間為9天。畫出增加M后的網(wǎng)絡(luò)計劃，并指出此時的關(guān)鍵線路（在圖上用雙線或色筆標(biāo)出）和（計算）工期；3增加工作M后，如工期仍要求18天，施工單位經(jīng)分析后，考慮有些工作可以適當(dāng)趕工，并估算出趕工1天所需增加的費用（直接費率），如下

12、表所示（表中未列出的工作不能趕工）：工作名稱正常時間最短時間直接費率（百元天）A426B323C542D641E642G873給出使工期仍為18天且增加趕工費最少的方案（要求寫出每步調(diào)整的工作，調(diào)整的天數(shù)及最后方案的網(wǎng)絡(luò)計劃，并在最后方案的網(wǎng)絡(luò)計劃中標(biāo)出關(guān)鍵線路）。十一、某航空公司在A市到B市的航線上用波音737客機執(zhí)行飛行任務(wù)。已知該機有效載客量為138人。按民用航空有關(guān)條例，旅客因有事或誤機，機票可免費改簽一次，也有在飛機起飛前退票的。為避免由此發(fā)生的空座損失，該航空公司決定每個航班超量售票（即每班售出票數(shù)為138+S張）。但由此會發(fā)生持票登機旅客多于座位數(shù)的情況，這種情況下，航空公司規(guī)定

13、，對超員旅客愿改乘本公司后續(xù)航班的，機票免費（即退回原機票款）；若換乘其他航空公司航班的，按機票價的150%退款。據(jù)統(tǒng)計前一類旅客（改乘本公司）占超員中的80%，后一類（換乘他公司）占20%。又據(jù)該公司長期統(tǒng)計，每個航班旅客退票和改簽發(fā)生的人數(shù)i的概率p（i）如表3所示。表3i012345678p(i)0.180.250.250.160.060.040.030.020.01試確定該航空公司從A市到B市的航班每班應(yīng)多售出的機票張數(shù)S，使預(yù)期的收益最大。十二、某牙科診所有1名牙醫(yī)。統(tǒng)計表明牙醫(yī)以平均每小時看3名病人的效率工作，平均每小時在診所內(nèi)的病人為14人。若可設(shè)病人到達的平均間隔和牙醫(yī)每看1名

14、病人的平均工作時間均服從負(fù)指數(shù)分布，（1）求病人的平均達到率；（2）如果某病人上午10：10到達，那么預(yù)計這名病人最可能何時能離開？ 十三、某公司近期向市場推出了一種新產(chǎn)品多功能復(fù)印-打印機。該產(chǎn)品的多功能很受顧客歡迎，但一旦需停下來維修則要同時耽誤多項工作，因此，顧客要求盡量縮短維修等待時間。為此，公司的技術(shù)服務(wù)部在每個銷售區(qū)域設(shè)置了一位技術(shù)服務(wù)代表專門負(fù)責(zé)該產(chǎn)品的維修服務(wù)工作。假設(shè)顧客要求維修的電話是完全隨機地到達，平均每天到達3個，而當(dāng)技術(shù)服務(wù)代表連續(xù)工作時，平均每天完成4項維修任務(wù)。（1）該服務(wù)系統(tǒng)能否看作一個M/M/1排隊系統(tǒng)？為什么？（2） 假設(shè)該系統(tǒng)可看作一個標(biāo)準(zhǔn)的M/M/1排隊

15、系統(tǒng)，求出系統(tǒng)的服務(wù)強度（技術(shù)服務(wù)代表的繁忙率）和顧客的平均等待（不包括維修）時間。（3）現(xiàn)公司希望將顧客的平均等待時間降為不超過天，為此需將每個技術(shù)服務(wù)代表的服務(wù)區(qū)域縮小為達到率不超過多少？這時每個技術(shù)服務(wù)代表的服務(wù)強度將降為多少？ 十四、 某服裝廠設(shè)計了一款新式女裝準(zhǔn)備推向全國，如直接大批生產(chǎn)與銷售，主觀估計成功與失敗概率各為0.5，其分別的獲利為1200萬元與-500萬元，如果取消生產(chǎn)銷售計劃，則損失設(shè)計與準(zhǔn)備費用40萬元。為穩(wěn)妥起見，可先小批試銷，試銷的投入需45萬元，根據(jù)歷史資料與專家估計，試銷成功與失敗的概率分別為0.6和0.4，又據(jù)過去情況大批生產(chǎn)銷售為成功的例子中，試銷成功的占

16、84%，大批生產(chǎn)銷售失敗的事例中試銷成果的占36%。試根據(jù)以上數(shù)據(jù)，先計算在試銷成功與失敗兩種情況下，進行大批量生產(chǎn)與銷售時成功與失敗的各自概率，再畫出決策樹按EMV準(zhǔn)則確定最優(yōu)決策。十五、甲乙二人玩一種游戲，甲有兩個球，乙有三個球，在互不知道的情況下將球分別投入A、B兩個箱中(每人都不允許有剩余球)。設(shè)甲投入兩箱中球數(shù)分別為和，乙投入兩個箱中球數(shù)分別為和；若甲贏,若甲贏；若甲輸，若甲輸；在其它情況下雙方無輸贏（即值為0），試將此問題表示成一個二人零和對策，即寫出甲、乙的可選策略和甲的損益矩陣（不必求解）。十六、離某國總統(tǒng)選舉日還剩兩天，民意測驗表明尚有大約10%的選民未確定態(tài)度，主要集中在S和T兩市。甲、乙兩候選人都認(rèn)為爭取這10%的選民對于選舉的成功是至關(guān)重要的，各自制定三個備選策略s1，s2和s3進行最后的競選活動。s1為兩天花在S市；s2為兩天花在T市；s3為S和T市各一天。競選班子估計在各局勢的結(jié)局下，候選人甲多得的選票數(shù)（以百萬計）如下表：乙甲1103121421為求解該矩陣對策問題，可先盡量將問題簡化。可將上