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

1、07級(jí)工管運(yùn)籌學(xué)期末習(xí)題課一、考慮線性規(guī)劃問(wèn)題（P）（1） 若均為（P）的可行解，證明也是（P）的可行解；（2） 寫出（P）的對(duì)偶模型（仍用矩陣式表示）。二、有三個(gè)線性規(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*是()的對(duì)偶問(wèn)題的最優(yōu)解，試證：（1）； (2) 。三、已知線性規(guī)劃問(wèn)題 當(dāng)0時(shí)，用單純形法求得最終表如下： 5/201/211/20 5/21-1/2

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

3、差）最大”這一問(wèn)題，可建立一線性規(guī)劃模型，令x1、x2、x3、x4依次表示各型號(hào)產(chǎn)品的計(jì)劃產(chǎn)量，試列出這個(gè)模型，并記該模型為模型1；2利用一解線性規(guī)劃的程序解上述問(wèn)題（模型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ù)以上計(jì)算結(jié)果，分析并回答以下問(wèn)題：（1）最優(yōu)

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

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

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

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

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

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

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

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

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

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

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

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