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

1、 運(yùn)籌學(xué) 習(xí)題課 2011年6月一、線性規(guī)劃1、線性規(guī)劃的模型與圖解法 教學(xué)要求： （1）要求會(huì)建立一個(gè)實(shí)際問(wèn)題的數(shù)學(xué)模型 （2）對(duì)于二維問(wèn)題會(huì)用圖解法求解某個(gè)中型百貨商場(chǎng)對(duì)售貨人員（周工資200元）的需求經(jīng)統(tǒng)計(jì)如下表；為了保證銷售人員充分休息，銷售人員每周連續(xù)工作5天，連續(xù)休息2天。問(wèn)應(yīng)如何安排銷售人員的工作時(shí)間，使得所配售貨人員的總費(fèi)用最??？星期一二三四五六七人數(shù)12151214161819習(xí)題 1且為整數(shù)解：設(shè)Xi為在第i天開(kāi)始休息的售貨人員數(shù)2、單純形法教學(xué)要求：（1）基本概念 ：標(biāo)準(zhǔn)型，矩陣表達(dá)，基本可行解，解的幾種形式。（2）單純形方法步驟 步驟：選定一個(gè)初始基本可行解 、檢驗(yàn)一個(gè)

2、基本可行解是否為最優(yōu)解 、尋找一個(gè)更好的基本可行解。（3）單純形表結(jié)構(gòu)表的結(jié)構(gòu)要求會(huì)計(jì)算表內(nèi)各項(xiàng)數(shù)值解釋表中內(nèi)容的含義單純形法求解方法找出初始基可行解，列出初始單純形表計(jì)算檢驗(yàn)數(shù)所有存在非基變量檢驗(yàn) 數(shù)為零基變量中是否含有非零人工變量？唯一最優(yōu)解對(duì)某一作為換入變量設(shè) 為主元素, 為換出變量迭代運(yùn)算1、用 替代2、列出新的單純形表（1）對(duì)主元行（2）其它行YNN無(wú)可行解無(wú)窮多最優(yōu)解無(wú)界解YYYN(2)單純形方法的步驟 （3）單純形表的信息每張表上對(duì)應(yīng)的單位向量列基變量列 每張表上B-1的位置對(duì)應(yīng)于初表中I 的位置x1x2x3x4x5X3 d4a1100X4 2-1-5010X5 3a2-3001

3、Cj-zjc1c20001、表中解為唯一最優(yōu)解？2、表中解為無(wú)窮多最優(yōu)解？3、下一步迭代以x1替代x54、該線性規(guī)劃問(wèn)題為無(wú)界解？5、該線性規(guī)劃問(wèn)題為無(wú)可行解習(xí)題2表中給出某求極大化問(wèn)題的單純形表，問(wèn)表中a1,a2,c1,c2,d 為何值以及表中變量屬哪一種類型時(shí)有：C10, C20，C1C2, 且d/43/a2C20 a1=0C10 , C2 0 ,x5為人工變量Answer習(xí)題3表中給出某求極大化問(wèn)題的初始單純形表和迭代計(jì)算中某一步的表，試求未知數(shù)al的值x1x2x3x4x5x6x5205-413b10 x68j-1kc01檢驗(yàn)數(shù)16-7a00 x3d-1/701-2/7f4/7x2el1

4、0-3/7-5/7g檢驗(yàn)數(shù)72/70011/7hi a=1 b=-2 c=-1 d=12/7 e=4/7 f=-1/7 g=13/7 h=23/7 i=-50/7 j=1 k=5 l=-12/7答案3、對(duì)偶模型以及靈敏度分析教學(xué)要求（1）會(huì)列對(duì)偶的模型（2）對(duì)偶的性質(zhì)（3）對(duì)偶問(wèn)題的求解會(huì)進(jìn)行解釋（4）靈敏度分析對(duì)b的分析對(duì)c的分析對(duì)X的分析 某廠使用A、B兩種原料生產(chǎn)甲、乙、丙三種產(chǎn)品，有關(guān)數(shù)據(jù)見(jiàn)下表。產(chǎn)品A B 生產(chǎn)成本銷售價(jià)格甲乙丙原料成本用量1 0.50.4 0.60.6 0.55 7350 460 8 5 18 30 20 35（1）請(qǐng)寫(xiě)出使總銷售利潤(rùn)最大的線性規(guī)劃模型習(xí)題4（1）設(shè)

5、生產(chǎn)甲產(chǎn)品、乙產(chǎn)品和丙產(chǎn)品各 件，則單純形表終表如下：CB XB B-bX1 X2 X3 X4 X5 X3 162.5 X2 631.25檢驗(yàn)數(shù)行 3.75 -2.5 -3.125 3.75-1.75 -11.875 -6.75 （2）填完終表，指出最優(yōu)生產(chǎn)計(jì)劃和最大利潤(rùn)（3）指出原料A的影子價(jià)格，求出使最優(yōu)基保持不變的原料A的可增量上限。（4）寫(xiě)出此問(wèn)題的對(duì)偶規(guī)劃模型，并指出對(duì)偶最優(yōu)解。（5）產(chǎn)品甲的價(jià)格上升至多少時(shí)才考慮生產(chǎn)它？（6）試分析：若原問(wèn)題模型第一個(gè)約束條件兩端同時(shí)乘以2，對(duì)偶問(wèn)題的最優(yōu)解有何變化？CB XB B-bX1 X2 X3 X4 X5 10.5 X3 162.5 8.8

6、 X2 631.25檢驗(yàn)數(shù)行 2.5 0 1 3.75 -2.5-1.25 1 0 -3.125 3.75-1.75 -11.875 -6.75 （2）（3）原料A的影子價(jià)格為11.875；A的可增量上限為202；（4）對(duì)偶模型：（5）甲產(chǎn)品價(jià)格上升至大于31.75時(shí)，可考慮生產(chǎn)（6）對(duì)偶問(wèn)題的最優(yōu)解4、運(yùn)輸問(wèn)題教學(xué)要求（1）會(huì)列出運(yùn)輸問(wèn)題的數(shù)學(xué)模型（2）確定初始調(diào)運(yùn)方案的方法（3）檢驗(yàn)當(dāng)前調(diào)運(yùn)方案是否最優(yōu)的方法（4）空格處檢驗(yàn)數(shù)的經(jīng)濟(jì)含義 已知一運(yùn)輸問(wèn)題如表A,欲求運(yùn)費(fèi)最小的調(diào)運(yùn)方案,現(xiàn)有一調(diào)運(yùn)方案如表BB1 B2 B3 B4限量A1A2A34 3 3 101 0 2 77 20 10 57

7、63需求3 2 5 6B1 B2 B3 B4限量A1A2A3 4 33 2 1 3763需求3 2 5 6計(jì)算空格x24處檢驗(yàn)數(shù),判斷此方案是否為最優(yōu)方案?為什么?從此空格處出發(fā),最大調(diào)整量應(yīng)該為多少?習(xí)題5、線性整數(shù)規(guī)劃教學(xué)要求（1）會(huì)列出線性整數(shù)規(guī)劃問(wèn)題的數(shù)學(xué)模型（2）了解線性整數(shù)規(guī)劃問(wèn)題的求解方法某工程公司擬從四個(gè)項(xiàng)目中選擇若干項(xiàng)目，若令 請(qǐng)用xi的線性表達(dá)式來(lái)表示下列要求： （）從，個(gè)項(xiàng)目中至少選擇一個(gè) （）只有項(xiàng)目被選中，項(xiàng)目才能被選中 （）若項(xiàng)目被選中，則項(xiàng)目不能被選中習(xí)題6 某?；@球隊(duì)準(zhǔn)備從六名預(yù)備隊(duì)員中選拔三名為正式隊(duì)員，并使平均身高盡可能高。這六名預(yù)備隊(duì)員情況如表所示，隊(duì)員的

8、挑選要滿足如下條件：（）至少補(bǔ)充一名后衛(wèi)對(duì)員；（）大李和小田之間只能入選一個(gè)（）最多補(bǔ)充一名中鋒（）只要大李或小趙入選，小周就不能入選預(yù)備隊(duì)員身高（厘米）位置大張大李小王小趙小田小周中鋒中鋒前鋒前鋒后衛(wèi)后衛(wèi)習(xí)題7P57二、圖與網(wǎng)絡(luò)技術(shù)教學(xué)要求1、掌握?qǐng)D的基本概念2、會(huì)利用避圈法和破圈法求最小支撐樹(shù)3、會(huì)利用標(biāo)號(hào)法求最短路4、會(huì)利用標(biāo)號(hào)法求最大流5、網(wǎng)絡(luò)計(jì)劃問(wèn)題能夠利用標(biāo)號(hào)法求工期、關(guān)鍵路徑和工程在預(yù)定時(shí)間內(nèi)完成的概率。已知有A、B、C、D、E、F六個(gè)城鎮(zhèn)間的道路網(wǎng)絡(luò) 如圖，現(xiàn)要在六個(gè)城鎮(zhèn)間架設(shè)通訊網(wǎng)絡(luò)（均沿道路架設(shè)），每段道路上的架設(shè)費(fèi)用如圖。求能保證各城鎮(zhèn)均能通話且總架設(shè)費(fèi)用最少的架設(shè)方案。

9、EACBFD51069353978284習(xí)題818在某一公園內(nèi)，為了保護(hù)園區(qū)的野生生態(tài)環(huán)境，現(xiàn)規(guī)定在每小時(shí)內(nèi)每條線路上各種觀光旅游車的數(shù)量是有限制的，如圖所示，弧上數(shù)字為通行車數(shù)量。習(xí)題9SACBDET574312454961SACBDET5(4)7(7)4(3)3(3)1(1)2(0)4(3)5(4)4(4)9(8)6(6)1(1)習(xí)題10某企業(yè)要進(jìn)行一項(xiàng)工程項(xiàng)目，工作的相互關(guān)系如表所示：工序abcdefg緊前工序/ a,b a,bbc d,e時(shí)間/天4234312請(qǐng)繪制工程網(wǎng)絡(luò)圖，并確定關(guān)鍵路線和總工期。125436A(4)B(2)C(3)d(4)e(3)g(2)f(1)答案三、決策分析教學(xué)要求1、掌握決策問(wèn)題的分類2、會(huì)利用悲觀法則、樂(lè)觀法則、等可能法則、樂(lè)觀系數(shù)法則、最小后悔值法則對(duì)不確定性決策問(wèn)題進(jìn)行分析；3、會(huì)利用決策矩陣和決策樹(shù)法對(duì)風(fēng)險(xiǎn)型決策問(wèn)題進(jìn)行分析；4、理解決策的效用理論習(xí)題11某企業(yè)有三種方案可供選擇：方案S1是對(duì)原廠進(jìn)行擴(kuò)建