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

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

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

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

4、0-3/7-5/7g檢驗數(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、對偶模型以及靈敏度分析教學(xué)要求（1）會列對偶的模型（2）對偶的性質(zhì)（3）對偶問題的求解會進行解釋（4）靈敏度分析對b的分析對c的分析對X的分析 某廠使用A、B兩種原料生產(chǎn)甲、乙、丙三種產(chǎn)品，有關(guān)數(shù)據(jù)見下表。產(chǎn)品A B 生產(chǎn)成本銷售價格甲乙丙原料成本用量1 0.50.4 0.60.6 0.55 7350 460 8 5 18 30 20 35（1）請寫出使總銷售利潤最大的線性規(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檢驗數(shù)行 3.75 -2.5 -3.125 3.75-1.75 -11.875 -6.75 （2）填完終表，指出最優(yōu)生產(chǎn)計劃和最大利潤（3）指出原料A的影子價格，求出使最優(yōu)基保持不變的原料A的可增量上限。（4）寫出此問題的對偶規(guī)劃模型，并指出對偶最優(yōu)解。（5）產(chǎn)品甲的價格上升至多少時才考慮生產(chǎn)它？（6）試分析：若原問題模型第一個約束條件兩端同時乘以2，對偶問題的最優(yōu)解有何變化？CB XB B-bX1 X2 X3 X4 X5 10.5 X3 162.5 8.8

6、 X2 631.25檢驗數(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的影子價格為11.875；A的可增量上限為202；（4）對偶模型：（5）甲產(chǎn)品價格上升至大于31.75時，可考慮生產(chǎn)（6）對偶問題的最優(yōu)解4、運輸問題教學(xué)要求（1）會列出運輸問題的數(shù)學(xué)模型（2）確定初始調(diào)運方案的方法（3）檢驗當前調(diào)運方案是否最優(yōu)的方法（4）空格處檢驗數(shù)的經(jīng)濟含義 已知一運輸問題如表A,欲求運費最小的調(diào)運方案,現(xiàn)有一調(diào)運方案如表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計算空格x24處檢驗數(shù),判斷此方案是否為最優(yōu)方案?為什么?從此空格處出發(fā),最大調(diào)整量應(yīng)該為多少?習(xí)題5、線性整數(shù)規(guī)劃教學(xué)要求（1）會列出線性整數(shù)規(guī)劃問題的數(shù)學(xué)模型（2）了解線性整數(shù)規(guī)劃問題的求解方法某工程公司擬從四個項目中選擇若干項目，若令 請用xi的線性表達式來表示下列要求： （）從，個項目中至少選擇一個 （）只有項目被選中，項目才能被選中 （）若項目被選中，則項目不能被選中習(xí)題6 某?；@球隊準備從六名預(yù)備隊員中選拔三名為正式隊員，并使平均身高盡可能高。這六名預(yù)備隊員情況如表所示，隊員的

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

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