運(yùn)籌學(xué)例題及答案.ppt

作業(yè)及答案,1。用單純形法解LP問(wèn)題,線性規(guī)劃,達(dá)到最優(yōu)解，且最優(yōu)解唯一,2。用大M或兩階段法解LP問(wèn)題,無(wú)界解,3，某廠在今后四個(gè)月內(nèi)需租用倉(cāng)庫(kù)堆放物資。已知各月份需租用倉(cāng)庫(kù)面積見(jiàn)表，倉(cāng)庫(kù)租借費(fèi)用隨合同期不同而不同，期限越長(zhǎng)折扣越大，具體數(shù)字見(jiàn)表。租借合同每個(gè)月月初都可辦理，合同規(guī)定具體的租借面積和月數(shù)，因此該廠可根據(jù)需要，在任何一個(gè)月月初辦理合同，每次辦理可簽一份或多份，總目標(biāo)是總的租借費(fèi)用最低，請(qǐng)建立數(shù)學(xué)模型并用軟件給出結(jié)果。,解:設(shè)一月初簽訂合同期限為一個(gè)月，兩個(gè)月，三個(gè)月，四個(gè)月的倉(cāng)庫(kù)面積分別為 ， ， ， ，二月初簽訂合同期限為一個(gè)月，兩個(gè)月，三個(gè)月的倉(cāng)庫(kù)面積分別為 ，三月初簽訂合同期限為一個(gè)月，兩個(gè)月的倉(cāng)庫(kù)面積分別為 ，四月初簽訂合同期限為一個(gè)月的倉(cāng)庫(kù)面積為 。 則,計(jì)算結(jié)果如下,4，某廠生產(chǎn)I,II,III三種產(chǎn)品，都分別經(jīng)過(guò)A,B兩道工序加工。設(shè)A工序可分別在設(shè)備A1或A2上完成，有B1，B2，B3三種設(shè)備可用于完成B工序。已知產(chǎn)品I可在A,B任何一種設(shè)備上加工；產(chǎn)品II可在任何規(guī)格的A設(shè)備上加工，但完成B工序時(shí)，只能在B1設(shè)備上加工；產(chǎn)品III只能在A2和B2設(shè)備上加工。加工單位產(chǎn)品所需的工序時(shí)間及其它各項(xiàng)數(shù)據(jù)見(jiàn)表，試安排最優(yōu)生成計(jì)劃，使該廠獲利最大。,解：設(shè)第種產(chǎn)品中，分別在 上加工的數(shù)量依次為 ，第種產(chǎn)品中分別在A1,B1和A2,B1 上加工的數(shù)量為 生產(chǎn)種產(chǎn)品數(shù)量為 。,對(duì)偶理論,1. 已知線性規(guī)劃問(wèn)題：,要求：a)寫出對(duì)偶問(wèn)題，b)已知原問(wèn)題最有解X*=(2,2,4,0),用互補(bǔ)松弛性求出對(duì)偶問(wèn)題的最優(yōu)解。,解：對(duì)偶問(wèn)題：,將原問(wèn)題的最優(yōu)解帶入約束，發(fā)現(xiàn)第4個(gè)約束為嚴(yán)格不等式，所以，得y4*=0,又因?yàn)?，原?wèn)題最優(yōu)解的前三個(gè)分量都大于0，所以，有如下三個(gè)等式成立。,解方程組得對(duì)偶問(wèn)題的最優(yōu)解為Y*=(4/5,3/5,1,0),2。已知線性規(guī)劃問(wèn)題,及最終單純形表,表1,解：a）,將其加到表（1）的最終單純形表的基變量b這一列數(shù)字上得表（2）,（表2）,表（2）中原問(wèn)題為非可行解，故用對(duì)偶單純形法繼續(xù)計(jì)算得表（3）,（表3）,即新解為,b) 將cj的改變反應(yīng)到最終單純形表上,得表（4）,繼續(xù)迭代,得表（5）,表5,即新解為,c）,將其加到最終單純形表上得表（6）,繼續(xù)迭代,得表（7）,表6,即新解為,表7,d）,將其加到最終單純形表上得表（8）,表8,因x2已變化為x/2，故用單純形法算法將x/2替換出基變量中的x2，并在下一個(gè)表中不再保留x2，得表（9）,表9,此時(shí)已經(jīng)達(dá)到最優(yōu)，新解為,e) 此時(shí)將原來(lái)的最優(yōu)解帶入約束，發(fā)現(xiàn)滿足，所以最優(yōu)解不變。,運(yùn)輸問(wèn)題,1，試求下表給出的產(chǎn)銷不平衡問(wèn)題的最優(yōu)解。,解：用最小元素法求得初始方案如下,用位勢(shì)法求檢驗(yàn)數(shù)知,找到閉回路，調(diào)整得,又用位勢(shì)法求檢驗(yàn)數(shù)知,找到閉回路，調(diào)整得,又用位勢(shì)法求檢驗(yàn)數(shù)知所有的檢驗(yàn)數(shù)都非負(fù)，達(dá)到最優(yōu)z=32。,2，某市有三個(gè)面粉廠，他們供給三個(gè)面食加工廠所需的面粉。各面粉廠的產(chǎn)量、面食加工廠加工面粉的能力、各面食加工廠和各面粉廠之間的單位運(yùn)價(jià)見(jiàn)下表。假定在第1，2，3面食加工廠制作單位面粉食品的利潤(rùn)分別為12元，16元，11元，試確定使總效益最大的面粉分配計(jì)劃（假定面粉廠和面食加工廠都屬于同一個(gè)主管單位）,食品廠,面粉廠,解：從題意很容易知道，總效益最大實(shí)際上是食品利潤(rùn)減去單位運(yùn)價(jià)之后再求的總效益。再因?yàn)槊娣鄣目偖a(chǎn)量為70，比食品廠的總需求量60多了10個(gè)單位，可以認(rèn)為，多的10個(gè)單位最后還是會(huì)分配給13個(gè)食品廠，所以就需要增加一個(gè)虛擬的食品廠4。 設(shè)xij第i個(gè)面粉廠運(yùn)到第j個(gè)食品廠的運(yùn)量，i=1,2,3;j=1,2,3,4 得下表：,為使用求解運(yùn)輸問(wèn)題的表上作業(yè)法，用上表中的最大數(shù)減去其他各數(shù)，得下表,使用表上作業(yè)法，得最優(yōu)解.,整數(shù)規(guī)劃,1，分配甲、乙、丙、丁四個(gè)人完成ABCDE五項(xiàng)任務(wù)，每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間如表所示：,由于任務(wù)多于人數(shù)，故考慮： （a）任務(wù)E必須完成，其他各項(xiàng)可任意選3項(xiàng)完成； （b）其中有一人完成2項(xiàng)，其他每人完成一項(xiàng)。 分別確定最優(yōu)方案，使完成任務(wù)總時(shí)間最少,解（a）增加一個(gè)虛擬的人，由題目要求，其對(duì)應(yīng)的效率如下,Z=105,解（b）增加一個(gè)虛擬的人，由題目要求，其對(duì)應(yīng)的效率如下,最優(yōu)方案：甲B，乙C，D，丙E，丁A，Z=131,2，用割平面法求解,單純形迭代得最終單純形表,寫出第一行的約束,將上式中所有常數(shù)寫成正數(shù)和一個(gè)正分?jǐn)?shù)之和,分?jǐn)?shù)項(xiàng)移到右邊，整數(shù)項(xiàng)移到左邊,由于左邊為整數(shù)，所以右邊也為整數(shù)，所以,所以,由于,加入松弛變量,放入單純形表,對(duì)偶單純形法繼續(xù)迭代，得,寫出第二行的約束,將上式中所有常數(shù)寫成正數(shù)和一個(gè)正分?jǐn)?shù)之和,分?jǐn)?shù)項(xiàng)移到右邊，整數(shù)項(xiàng)移到左邊,由于左邊為整數(shù)，所以右邊也為整數(shù)，所以,所以,由于,加入松弛變量,放入單純形表,達(dá)到最優(yōu)，,還可以得到另一個(gè)最優(yōu)解：。,目標(biāo)規(guī)劃,1，已知目標(biāo)規(guī)劃問(wèn)題,用圖解法求解最優(yōu)解。,2，某工廠生產(chǎn)A,S兩種型號(hào)的微型計(jì)算機(jī)，他們都需要經(jīng)過(guò)兩道工序，每臺(tái)計(jì)算機(jī)所需的加工時(shí)間、銷售利潤(rùn)及該廠每周最大的加工能力如下表：,工廠經(jīng)營(yíng)目標(biāo)的各優(yōu)先級(jí)如下：,P1：每周總利潤(rùn)不低于10000元； P2：合同要求A型機(jī)每周至少生產(chǎn)10臺(tái)，S型機(jī)至少15臺(tái)； P3：工序1每周生成時(shí)間最好恰為150h,工序2生成時(shí)間可適當(dāng)超過(guò)其能力； 試寫出目標(biāo)規(guī)劃的模型。,解：設(shè)生產(chǎn)A，S機(jī)器分別為x1,x2臺(tái)，則有,3，查找參考書，參閱較復(fù)雜問(wèn)題的模型,圖論,1，用避圈法或破圈法求下圖的最小樹,或選取 去掉,解答：,2，下圖中 是倉(cāng)庫(kù)， 是商店，求一條 到 的最短路,最優(yōu)方案可以有幾種：,3，用標(biāo)號(hào)算法求下圖的最大流,得增廣鏈如右圖中紅色部分，調(diào)整后得新圖如下：,再次標(biāo)號(hào)知：沒(méi)有增廣鏈存在，故達(dá)到最大流。最大流量為13,4，求下圖中流值為6的最小費(fèi)用流，其中弧旁邊的數(shù)字為 , 表示容量， 表示單位流量費(fèi)用。,解：以0作為初始流量，得長(zhǎng)度網(wǎng)絡(luò),最短路：,調(diào)整流量，得新的流量網(wǎng)絡(luò),對(duì)新的流量網(wǎng)絡(luò)，得到長(zhǎng)度網(wǎng)絡(luò),最短路：,調(diào)整流量，得新的流量網(wǎng)絡(luò),對(duì)新的流量網(wǎng)絡(luò)，得到長(zhǎng)度網(wǎng)絡(luò),最短路：,調(diào)整流量，得新的流量網(wǎng)絡(luò),PERT圖 與 關(guān)鍵路線法,1，下表給出一個(gè)汽車庫(kù)及引道的施工計(jì)劃：,請(qǐng)解答（1）該工程從施工開始道工程結(jié)束的最短周期；（2）如果引道混凝土施工工期拖延10天，對(duì)整個(gè)工程進(jìn)度有何影響？（3）若裝天花板的施工時(shí)間從12天縮短為8天，對(duì)整個(gè)工程進(jìn)度有何影響？（4）為保證工期不拖延，裝門這項(xiàng)作業(yè)最晚應(yīng)從哪一天開工？（5）如果要求該工程必須在75天內(nèi)完工，是否應(yīng)采取措施，應(yīng)采取什么措施？,解：作業(yè)編號(hào)分別對(duì)應(yīng)A,B,C,D,E,F,G,H,I,J,K,L,M,N，PERT 圖如下,（1）該工程從施工開始道工程結(jié)束的最短周期為80天,可計(jì)算出自由時(shí)差和總時(shí)差,若使用公式：,表示總時(shí)差,表示自由時(shí)差,如此可找到關(guān)鍵路線：A-C-E-F-G-J-K-N,（2）如果引道混凝土施工(L)工期拖延10天，由于此工序 有總時(shí)差28，所以它的工期拖延10天，對(duì)整個(gè)工程進(jìn)度 無(wú)影響。,（3）若裝天花板（J）的施工時(shí)間從12天縮短為8天，觀察它的平行工序H，I，發(fā)現(xiàn)關(guān)鍵路線不會(huì)改變，所以整個(gè)工程進(jìn)度也縮短4天。,（4）為保證工期不拖延，裝門（I）這項(xiàng)作業(yè)最晚應(yīng)從第56天開工,（5）如果要求該工程必須在75天內(nèi)完工，在合適的關(guān) 鍵工序上壓縮5天工期。,動(dòng)態(tài)規(guī)劃,1. 設(shè)有6萬(wàn)元資金用于四個(gè)工廠的擴(kuò)建。已知每個(gè)工廠的利潤(rùn)增長(zhǎng)額同投資數(shù)的大小有關(guān)，數(shù)據(jù)見(jiàn)表。如何確定對(duì)四個(gè)工廠的投資數(shù)，使得總利潤(rùn)增長(zhǎng)額最大。,利潤(rùn)增長(zhǎng)額,工廠,投資,1.解： 設(shè)sk表示第k個(gè)工廠到第4個(gè)工廠的投資數(shù)。Xk表示第k個(gè)工廠的投資數(shù),則第4個(gè)階段如下：,第3個(gè)階段：,第2個(gè)階段：,第1個(gè)階段：,最優(yōu)方案： 1，0，200，300，100 2，100，100，300，100 3，200，100，200，100 4，200，200，0，200,2. 用動(dòng)態(tài)規(guī)劃解以下靜態(tài)問(wèn)題：,解：令k=2, 狀態(tài)變量：k階段初各約束條件右端項(xiàng)的剩余值R1k,R2k 決策變量：x1,x2 ，狀態(tài)轉(zhuǎn)移方程為：,令k=1,由于,k=2時(shí),而由第2個(gè)約束知，,所以,此時(shí),x2=0.5,決策分析,1,某鐘表公司計(jì)劃通過(guò)它的銷售網(wǎng)銷售一種低價(jià)鐘表，計(jì)劃每塊售價(jià)10元。生產(chǎn)這種鐘表有3個(gè)設(shè)計(jì)方案：方案1需一次投資10萬(wàn)元，以后生產(chǎn)一個(gè)的費(fèi)用為5元，方案2需一次投資16萬(wàn)元，以后生產(chǎn)一個(gè)的費(fèi)用為4元；方案3需一次投資25萬(wàn)元，以后生產(chǎn)一個(gè)的費(fèi)用為3元。對(duì)該種鐘表的需求量為未知，但估計(jì)有三種可能： E130000；E2120000；E3200000 a)建立這個(gè)問(wèn)題的收益矩陣；b)分別用悲觀主義、樂(lè)觀主義和等可能性決策準(zhǔn)則決定該公司應(yīng)采用哪一個(gè)設(shè)計(jì)方案；c)建立機(jī)會(huì)損失矩陣，并用最小機(jī)會(huì)損失決策準(zhǔn)則決定采取哪一個(gè)設(shè)計(jì)方案。,收益矩陣（單位：萬(wàn)）：,樂(lè)觀準(zhǔn)則：,選A3,悲觀準(zhǔn)則：,選A1,機(jī)會(huì)損失矩陣（單位：萬(wàn)）：,選A3,2，某工程隊(duì)承擔(dān)一個(gè)橋梁的施工任務(wù)，由于該地區(qū)夏季多雨，有三個(gè)月時(shí)間不能施工。在不施工期內(nèi)，該工程隊(duì)可將施工機(jī)械搬走或留在原處。假如搬走，需華搬遷費(fèi)1800元，若留在原處，一種方案是花500元筑一護(hù)堤，防止河水上漲發(fā)生高水位侵襲；若不筑護(hù)堤，發(fā)生高水位侵襲時(shí)將損失10000元。又若下暴雨發(fā)生洪水，則不管是否修護(hù)堤，施工機(jī)械留在原處都將受到60000元的損失。如果預(yù)測(cè)在這三個(gè)月中，高水位的發(fā)生率為25%,洪水的發(fā)生率為2%,試依據(jù)決策樹的方法分析該施工隊(duì)要不要把施工機(jī)械搬走及要不要修筑護(hù)堤。,3，某公司經(jīng)理的決策效用函數(shù)如下：U(-10000)=-800, U(-200)=-2, U(-100)=-1, U(0)=0, U(10000)=250,他需要決定是否為該公司的財(cái)產(chǎn)報(bào)火險(xiǎn)。據(jù)大量統(tǒng)計(jì)資料，一年內(nèi)可能發(fā)生火災(zāi)的概率為0.0015，問(wèn)他是否愿意每年支付100元保10000元財(cái)產(chǎn)的潛在火災(zāi)損失。,排隊(duì)論,1.汽車按照平均90輛/h的Poisson流到達(dá)高速公路的一個(gè)收費(fèi)關(guān)卡，通過(guò)關(guān)卡的時(shí)間是38秒。由于駕駛?cè)藛T反應(yīng)等待時(shí)間太長(zhǎng)，主管部門打算采用新裝置，使汽車通過(guò)關(guān)卡的平均時(shí)間減少到30秒。但增加新裝置只有在原系統(tǒng)中等待的汽車平均數(shù)超過(guò)5輛和新系統(tǒng)中關(guān)卡的空閑時(shí)間不超過(guò)10%時(shí)才是合算的。根據(jù)這個(gè)要求，分析采用新裝置是否合算？,2.某小型家電維修部聲稱對(duì)家電一般維修做到一個(gè)小時(shí)內(nèi)完成，并保證若顧客停留超過(guò)一個(gè)小時(shí)，修理免費(fèi)。已知每項(xiàng)修理收費(fèi)10元，而修理成本為5.5元。若送達(dá)修理的家電服從泊松分布，平均6件/小時(shí)，修理每件的時(shí)間服從負(fù)指數(shù)分布，平均每件7.5分鐘。該維修部有一名修理工，問(wèn)：(1)該維修部能否做到盈利？（2）當(dāng)維修時(shí)間不變，則維修家電送達(dá)率為何值時(shí)，該維修部的收支到達(dá)盈虧平衡？,