西華大學運籌學例題及答案課件

1、作業(yè)及答案,1,PPT學習交流,1。用單純形法解LP問題,線性規(guī)劃,2,PPT學習交流,3,PPT學習交流,達到最優(yōu)解，且最優(yōu)解唯一,4,PPT學習交流,2。用大M或兩階段法解LP問題,5,PPT學習交流,6,PPT學習交流,無界解,7,PPT學習交流,3，某廠在今后四個月內需租用倉庫堆放物資。已知各月份需租用倉庫面積見表，倉庫租借費用隨合同期不同而不同，期限越長折扣越大，具體數(shù)字見表。租借合同每個月月初都可辦理，合同規(guī)定具體的租借面積和月數(shù)，因此該廠可根據(jù)需要，在任何一個月月初辦理合同，每次辦理可簽一份或多份，總目標是總的租借費用最低，請建立數(shù)學模型并用軟件給出結果。,8,PPT學習交流,解

2、:設一月初簽訂合同期限為一個月，兩個月，三個月，四個月的倉庫面積分別為 ， ， ， ，二月初簽訂合同期限為一個月，兩個月，三個月的倉庫面積分別為 ，三月初簽訂合同期限為一個月，兩個月的倉庫面積分別為 ，四月初簽訂合同期限為一個月的倉庫面積為 。 則,計算結果如下,9,PPT學習交流,10,PPT學習交流,4，某廠生產I,II,III三種產品，都分別經過A,B兩道工序加工。設A工序可分別在設備A1或A2上完成，有B1，B2，B3三種設備可用于完成B工序。已知產品I可在A,B任何一種設備上加工；產品II可在任何規(guī)格的A設備上加工，但完成B工序時，只能在B1設備上加工；產品III只能在A2和B2設備

3、上加工。加工單位產品所需的工序時間及其它各項數(shù)據(jù)見表，試安排最優(yōu)生成計劃，使該廠獲利最大。,11,PPT學習交流,12,PPT學習交流,解：設第種產品中，分別在 上加工的數(shù)量依次為 ，第種產品中分別在A1,B1和A2,B1 上加工的數(shù)量為 生產種產品數(shù)量為 。,13,PPT學習交流,14,PPT學習交流,對偶理論,15,PPT學習交流,1. 已知線性規(guī)劃問題：,要求：a)寫出對偶問題，b)已知原問題最有解X*=(2,2,4,0),用互補松弛性求出對偶問題的最優(yōu)解。,16,PPT學習交流,解：對偶問題：,將原問題的最優(yōu)解帶入約束，發(fā)現(xiàn)第4個約束為嚴格不等式，所以，得y4*=0,又因為，原問題最優(yōu)

4、解的前三個分量都大于0，所以，有如下三個等式成立。,17,PPT學習交流,解方程組得對偶問題的最優(yōu)解為Y*=(4/5,3/5,1,0),18,PPT學習交流,2。已知線性規(guī)劃問題,及最終單純形表,19,PPT學習交流,表1,20,PPT學習交流,21,PPT學習交流,解：a）,將其加到表（1）的最終單純形表的基變量b這一列數(shù)字上得表（2）,22,PPT學習交流,（表2）,表（2）中原問題為非可行解，故用對偶單純形法繼續(xù)計算得表（3）,23,PPT學習交流,（表3）,即新解為,24,PPT學習交流,b) 將cj的改變反應到最終單純形表上,得表（4）,繼續(xù)迭代,得表（5）,25,PPT學習交流,表

5、5,即新解為,26,PPT學習交流,c）,將其加到最終單純形表上得表（6）,27,PPT學習交流,繼續(xù)迭代,得表（7）,表6,28,PPT學習交流,即新解為,表7,29,PPT學習交流,d）,將其加到最終單純形表上得表（8）,30,PPT學習交流,表8,因x2已變化為x/2，故用單純形法算法將x/2替換出基變量中的x2，并在下一個表中不再保留x2，得表（9）,31,PPT學習交流,表9,此時已經達到最優(yōu)，新解為,32,PPT學習交流,e) 此時將原來的最優(yōu)解帶入約束，發(fā)現(xiàn)滿足，所以最優(yōu)解不變。,33,PPT學習交流,運輸問題,34,PPT學習交流,1，試求下表給出的產銷不平衡問題的最優(yōu)解。,3

6、5,PPT學習交流,解：用最小元素法求得初始方案如下,用位勢法求檢驗數(shù)知,找到閉回路，調整得,36,PPT學習交流,又用位勢法求檢驗數(shù)知,找到閉回路，調整得,37,PPT學習交流,又用位勢法求檢驗數(shù)知所有的檢驗數(shù)都非負，達到最優(yōu)z=32。,38,PPT學習交流,2，某市有三個面粉廠，他們供給三個面食加工廠所需的面粉。各面粉廠的產量、面食加工廠加工面粉的能力、各面食加工廠和各面粉廠之間的單位運價見下表。假定在第1，2，3面食加工廠制作單位面粉食品的利潤分別為12元，16元，11元，試確定使總效益最大的面粉分配計劃（假定面粉廠和面食加工廠都屬于同一個主管單位）,食品廠,面粉廠,39,PPT學習交流

7、,解：從題意很容易知道，總效益最大實際上是食品利潤減去單位運價之后再求的總效益。再因為面粉的總產量為70，比食品廠的總需求量60多了10個單位，可以認為，多的10個單位最后還是會分配給13個食品廠，所以就需要增加一個虛擬的食品廠4。 設xij第i個面粉廠運到第j個食品廠的運量，i=1,2,3;j=1,2,3,4 得下表：,40,PPT學習交流,為使用求解運輸問題的表上作業(yè)法，用上表中的最大數(shù)減去其他各數(shù)，得下表,使用表上作業(yè)法，得最優(yōu)解.,41,PPT學習交流,整數(shù)規(guī)劃,42,PPT學習交流,1，分配甲、乙、丙、丁四個人完成ABCDE五項任務，每個人完成各項任務的時間如表所示：,由于任務多于人

8、數(shù)，故考慮： （a）任務E必須完成，其他各項可任意選3項完成； （b）其中有一人完成2項，其他每人完成一項。 分別確定最優(yōu)方案，使完成任務總時間最少,43,PPT學習交流,解（a）增加一個虛擬的人，由題目要求，其對應的效率如下,Z=105,44,PPT學習交流,解（b）增加一個虛擬的人，由題目要求，其對應的效率如下,最優(yōu)方案：甲B，乙C，D，丙E，丁A，Z=131,45,PPT學習交流,2，用割平面法求解,46,PPT學習交流,單純形迭代得最終單純形表,47,PPT學習交流,寫出第一行的約束,將上式中所有常數(shù)寫成正數(shù)和一個正分數(shù)之和,分數(shù)項移到右邊，整數(shù)項移到左邊,48,PPT學習交流,由于左

9、邊為整數(shù)，所以右邊也為整數(shù)，所以,所以,由于,加入松弛變量,放入單純形表,49,PPT學習交流,對偶單純形法繼續(xù)迭代，得,50,PPT學習交流,51,PPT學習交流,寫出第二行的約束,將上式中所有常數(shù)寫成正數(shù)和一個正分數(shù)之和,分數(shù)項移到右邊，整數(shù)項移到左邊,52,PPT學習交流,由于左邊為整數(shù)，所以右邊也為整數(shù)，所以,所以,由于,加入松弛變量,放入單純形表,53,PPT學習交流,54,PPT學習交流,達到最優(yōu)，,還可以得到另一個最優(yōu)解：。,55,PPT學習交流,目標規(guī)劃,56,PPT學習交流,1，已知目標規(guī)劃問題,用圖解法求解最優(yōu)解。,57,PPT學習交流,58,PPT學習交流,2，某工廠生產

10、A,S兩種型號的微型計算機，他們都需要經過兩道工序，每臺計算機所需的加工時間、銷售利潤及該廠每周最大的加工能力如下表：,工廠經營目標的各優(yōu)先級如下：,59,PPT學習交流,P1：每周總利潤不低于10000元； P2：合同要求A型機每周至少生產10臺，S型機至少15臺； P3：工序1每周生成時間最好恰為150h,工序2生成時間可適當超過其能力； 試寫出目標規(guī)劃的模型。,60,PPT學習交流,解：設生產A，S機器分別為x1,x2臺，則有,61,PPT學習交流,3，查找參考書，參閱較復雜問題的模型,62,PPT學習交流,圖論,63,PPT學習交流,1，用避圈法或破圈法求下圖的最小樹,64,PPT學習

11、交流,或選取 去掉,解答：,65,PPT學習交流,2，下圖中 是倉庫， 是商店，求一條 到 的最短路,66,PPT學習交流,最優(yōu)方案可以有幾種：,67,PPT學習交流,3，用標號算法求下圖的最大流,68,PPT學習交流,得增廣鏈如右圖中紅色部分，調整后得新圖如下：,69,PPT學習交流,再次標號知：沒有增廣鏈存在，故達到最大流。最大流量為13,70,PPT學習交流,4，求下圖中流值為6的最小費用流，其中弧旁邊的數(shù)字為 , 表示容量， 表示單位流量費用。,71,PPT學習交流,解：以0作為初始流量，得長度網絡,最短路：,調整流量，得新的流量網絡,72,PPT學習交流,對新的流量網絡，得到長度網絡

12、,最短路：,調整流量，得新的流量網絡,73,PPT學習交流,對新的流量網絡，得到長度網絡,最短路：,調整流量，得新的流量網絡,74,PPT學習交流,PERT圖 與 關鍵路線法,75,PPT學習交流,1，下表給出一個汽車庫及引道的施工計劃：,76,PPT學習交流,請解答（1）該工程從施工開始道工程結束的最短周期；（2）如果引道混凝土施工工期拖延10天，對整個工程進度有何影響？（3）若裝天花板的施工時間從12天縮短為8天，對整個工程進度有何影響？（4）為保證工期不拖延，裝門這項作業(yè)最晚應從哪一天開工？（5）如果要求該工程必須在75天內完工，是否應采取措施，應采取什么措施？,77,PPT學習交流,解

13、：作業(yè)編號分別對應A,B,C,D,E,F,G,H,I,J,K,L,M,N，PERT 圖如下,78,PPT學習交流,（1）該工程從施工開始道工程結束的最短周期為80天,可計算出自由時差和總時差,若使用公式：,79,PPT學習交流,表示總時差,表示自由時差,80,PPT學習交流,如此可找到關鍵路線：A-C-E-F-G-J-K-N,（2）如果引道混凝土施工(L)工期拖延10天，由于此工序 有總時差28，所以它的工期拖延10天，對整個工程進度 無影響。,（3）若裝天花板（J）的施工時間從12天縮短為8天，觀察它的平行工序H，I，發(fā)現(xiàn)關鍵路線不會改變，所以整個工程進度也縮短4天。,（4）為保證工期不拖延

14、，裝門（I）這項作業(yè)最晚應從第56天開工,（5）如果要求該工程必須在75天內完工，在合適的關 鍵工序上壓縮5天工期。,81,PPT學習交流,動態(tài)規(guī)劃,82,PPT學習交流,1. 設有6萬元資金用于四個工廠的擴建。已知每個工廠的利潤增長額同投資數(shù)的大小有關，數(shù)據(jù)見表。如何確定對四個工廠的投資數(shù)，使得總利潤增長額最大。,利潤增長額,工廠,投資,83,PPT學習交流,1.解： 設sk表示第k個工廠到第4個工廠的投資數(shù)。Xk表示第k個工廠的投資數(shù),則第4個階段如下：,84,PPT學習交流,第3個階段：,85,PPT學習交流,第2個階段：,86,PPT學習交流,第1個階段：,最優(yōu)方案： 1，0，200，

15、300，100 2，100，100，300，100 3，200，100，200，100 4，200，200，0，200,87,PPT學習交流,2. 用動態(tài)規(guī)劃解以下靜態(tài)問題：,解：令k=2, 狀態(tài)變量：k階段初各約束條件右端項的剩余值R1k,R2k 決策變量：x1,x2 ，狀態(tài)轉移方程為：,88,PPT學習交流,令k=1,由于,k=2時,而由第2個約束知，,所以,89,PPT學習交流,此時,x2=0.5,90,PPT學習交流,決策分析,91,PPT學習交流,1,某鐘表公司計劃通過它的銷售網銷售一種低價鐘表，計劃每塊售價10元。生產這種鐘表有3個設計方案：方案1需一次投資10萬元，以后生產一個的

16、費用為5元，方案2需一次投資16萬元，以后生產一個的費用為4元；方案3需一次投資25萬元，以后生產一個的費用為3元。對該種鐘表的需求量為未知，但估計有三種可能： E130000；E2120000；E3200000 a)建立這個問題的收益矩陣；b)分別用悲觀主義、樂觀主義和等可能性決策準則決定該公司應采用哪一個設計方案；c)建立機會損失矩陣，并用最小機會損失決策準則決定采取哪一個設計方案。,92,PPT學習交流,收益矩陣（單位：萬）：,93,PPT學習交流,樂觀準則：,選A3,94,PPT學習交流,悲觀準則：,選A1,95,PPT學習交流,機會損失矩陣（單位：萬）：,選A3,96,PPT學習交流

17、,2，某工程隊承擔一個橋梁的施工任務，由于該地區(qū)夏季多雨，有三個月時間不能施工。在不施工期內，該工程隊可將施工機械搬走或留在原處。假如搬走，需華搬遷費1800元，若留在原處，一種方案是花500元筑一護堤，防止河水上漲發(fā)生高水位侵襲；若不筑護堤，發(fā)生高水位侵襲時將損失10000元。又若下暴雨發(fā)生洪水，則不管是否修護堤，施工機械留在原處都將受到60000元的損失。如果預測在這三個月中，高水位的發(fā)生率為25%,洪水的發(fā)生率為2%,試依據(jù)決策樹的方法分析該施工隊要不要把施工機械搬走及要不要修筑護堤。,97,PPT學習交流,3，某公司經理的決策效用函數(shù)如下：U(-10000)=-800, U(-200)=-2, U(-100)=-1, U(0)=0, U(10000)=250,他需要決定是否為該公司的財產報火險。據(jù)大量統(tǒng)計資料，一年內可能發(fā)生火災的概率為0.0015，問他是否愿意每年支付100元保10000元財產的潛在火災損失。,98,PPT學習交流,排隊論,99,PPT學習交流,1.汽車按照平均90輛/h的Poisson流到達高速公路的一個收費關卡，通過關卡的時間是38秒。由于駕駛人員反應等待時間太長，主管部門打算采用新裝置，使汽車通過關卡的平均時間減少到30秒。