運(yùn)籌學(xué)例題及答案（章節(jié)課程）

1、運(yùn) 籌 帷 幄 之 中決 勝 千 里 之 外作業(yè)及答案1。用單純形法解LP問(wèn)題線性規(guī)劃cj6-2300cBxBbx1x2x3x4x50 x422-12100 x5410401 cj - zj6-23006x111-1/211/200 x5301/23-1/21 cj - zj01-3-306x1410401-2x26016-12 cj - zj00-9-2-2cj6-2300cBxBbx1x2x3x4x5達(dá)到最優(yōu)解，且最優(yōu)解唯一2。用大M或兩階段法解LP問(wèn)題cj2-12000-M-M-McBxBbx1x2x3x4x5x6x7x8x9-Mx76111-100100-Mx82-2010-10010

2、-Mx9002-100-1001Cj-zj2-M3M-1M+2-M-M-M000-Mx76103/2-101/210-1/2-Mx82-2010-10010-1x2001-1/200-1/2001/2Cj-zj2-M05/2M+3/2-M-M1/2M-1/200-3/2M+1/2cj2-12000-M-M-McBxBbx1x2x3x4x5x6x7x8x9-Mx73400-13/21/21-3/2-1/22x32-201000010-1x21-1100-1/2-1/201/21Cj-zj5+4M00-M3/2M+3/21/2M-1/20-5/2M-3/2-3/2M+1/22x13/4100-1/

3、43/81/81/4-3/8-1/82x37/2001-1/2-1/41/41/21/4-1/4-1x27/4010-1/4-1/8-3/81/81/83/8Cj-zj0005/4-無(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é)果。月份1234所需倉(cāng)庫(kù)面積（100m2）15102012合同租借期限1個(gè)月2個(gè)月3個(gè)月4個(gè)月

4、租借費(fèi)用2800450060007300解:設(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è)備上加

5、工。加工單位產(chǎn)品所需的工序時(shí)間及其它各項(xiàng)數(shù)據(jù)見(jiàn)表，試安排最優(yōu)生成計(jì)劃，使該廠獲利最大。設(shè)備 產(chǎn)品I II III設(shè)備有效臺(tái)時(shí)設(shè)備加工費(fèi)（元/h）A15 10 60000.05A27 9 12100000.03B16 840000.06B24 1170000.11B3740000.05原料費(fèi)（元/件）售價(jià)（元/件）0.25 0.35 0.501.25 2.00 2.80解：設(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),用互

6、補(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)題及最終單純形表cj320000cBxBbx1x2x3x4x5x62x24/3012/3-1/3003x110/310-1/32/3000 x5300-11100 x62/300-2/31/301cjzj00-1/3-4/300表1分析下列各種條件單獨(dú)變化時(shí)，最優(yōu)解將如何變化。（a）第1，2個(gè)約束條件的后端項(xiàng)分別由6變7，8變4；（b）

7、目標(biāo)函數(shù)變?yōu)?; （c） 增加一個(gè)變量 ，系數(shù)為（d）問(wèn)題中變量 的系數(shù)變?yōu)椋╡）增加一個(gè)新的約束解：a）將其加到表（1）的最終單純形表的基變量b這一列數(shù)字上得表（2）（表2）表（2）中原問(wèn)題為非可行解，故用對(duì)偶單純形法繼續(xù)計(jì)算得表（3）cj320000cBxBbx1x2x3x4x5x62x210/3012/3-1/3003x11/310-1/32/3000 x5-200-11100 x6-4/300-2/31/301cjzj00-1/3-4/300（表3）cj320000cBxBbx1x2x3x4x5x62x220101/32/303x111001/3-1/300 x32001-1-100

8、x60000-1/3-2/31cjzj000-5/3-1/30即新解為b) 將cj的改變反應(yīng)到最終單純形表上,得表（4）cj250000cBxBbx1x2x3x4x5x65x24/3012/3-1/3002x110/310-1/32/3000 x5300-11100 x62/300-2/31/301cjzj00-8/31/300繼續(xù)迭代,得表（5）cj250000cBxBbx1x2x3x4x5x65x220100012x1210100-20 x5100101-30 x4200-2103cjzj00-200-1表5即新解為c）將其加到最終單純形表上得表（6）cj320000cBxBbx1x2x3

9、x4x5x62x24/3012/3-1/3003x110/310-1/32/3000 x5300-11100 x62/300-2/31/301cjzj00-1/3-4/3004x701421繼續(xù)迭代,得表（7）表6cj320000cBxBbx1x2x3x4x5x62x24/3012/3-1/3003x131001/20-1/20 x55/3001/31/21-24x71/300-1/31/601/2cjzj000-3/20-1/24x700010即新解為表7d）將其加到最終單純形表上得表（8）cj320000cBxBbx1x2x3x4x5x62x24/3012/3-1/3003x110/310

10、-1/32/3000 x5300-11100 x62/300-2/31/301cjzj00-1/3-4/3004X24/31/302/31/3表8因x2已變化為x/2，故用單純形法算法將x/2替換出基變量中的x2，并在下一個(gè)表中不再保留x2，得表（9）cj320000cBxBbx1X2x3x4x5x64X21011/2-1/4003x1310-1/23/4000 x5300-11100 x6000-11/201cjzj00-1/2-5/400表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)解。B1B2B3B4

11、產(chǎn)量A137645A224322A343856銷量3322解：用最小元素法求得初始方案如下B1B2B3B4B5A123A220A3132用位勢(shì)法求檢驗(yàn)數(shù)知找到閉回路，調(diào)整得B1B2B3B4B5A132A220A3321又用位勢(shì)法求檢驗(yàn)數(shù)知找到閉回路，調(diào)整得B1B2B3B4B5A1320A220A333又用位勢(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元，試確定使總效益最大

12、的面粉分配計(jì)劃（假定面粉廠和面食加工廠都屬于同一個(gè)主管單位）123面粉廠產(chǎn)量A310220C411830B811420食品廠需要量152520食品廠面粉廠解：從題意很容易知道，總效益最大實(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得下表：1234面粉廠產(chǎn)量A969920C853830B457720食品廠需要量15252010為使用求解運(yùn)輸問(wèn)題的表上作業(yè)法，用上表中的

13、最大數(shù)減去其他各數(shù)，得下表1234面粉廠產(chǎn)量A030020C146130B542220食品廠需要量15252010使用表上作業(yè)法，得最優(yōu)解.整數(shù)規(guī)劃1，分配甲、乙、丙、丁四個(gè)人完成ABCDE五項(xiàng)任務(wù)，每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間如表所示：ABCDE甲2529314237乙3938262 033丙3427284 032丁2442362345由于任務(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)

14、的效率如下最優(yōu)方案：甲B，乙C，D，丙E，丁A，Z=1312，用割平面法求解cj1100cBxBbx1x2x3x41x15/3105/6-1/31x28/301-2/31/3 cj - zj00-1/6-1/6單純形迭代得最終單純形表寫出第一行的約束將上式中所有常數(shù)寫成正數(shù)和一個(gè)正分?jǐn)?shù)之和分?jǐn)?shù)項(xiàng)移到右邊，整數(shù)項(xiàng)移到左邊由于左邊為整數(shù)，所以右邊也為整數(shù)，所以所以由于加入松弛變量放入單純形表cj1100cBxBbx1x2x3x41x15/3105/6-1/61x28/301-2/31/30 x5-2/300-5/61/6 cj - zj00-1/6-1/600 x5001對(duì)偶單純形法繼續(xù)迭代，得c

15、j1100cBxBbx1x2x3x41x1110001x216/50101/50 x34/5001-1/5 cj - zj000-1/5-1/50 x51-4/5-6/5寫出第二行的約束將上式中所有常數(shù)寫成正數(shù)和一個(gè)正分?jǐn)?shù)之和分?jǐn)?shù)項(xiàng)移到右邊，整數(shù)項(xiàng)移到左邊由于左邊為整數(shù)，所以右邊也為整數(shù)，所以所以由于加入松弛變量放入單純形表cj1100cBxBbx1x2x3x41x1110001x216/50101/50 x34/5001-1/5 cj - zj000-1/5-1/500 x51-4/5-6/50 x60000 x6-1/5000-1/5-1/51cj1100cBxBbx1x2x3x41x11

16、10001x2301000 x310010 cj - zj00000-10 x51-1-10 x601-10 x4100011-5達(dá)到最優(yōu)，還可以得到另一個(gè)最優(yōu)解：。目標(biāo)規(guī)劃1，已知目標(biāo)規(guī)劃問(wèn)題用圖解法求解最優(yōu)解。最優(yōu)解2，某工廠生產(chǎn)A,S兩種型號(hào)的微型計(jì)算機(jī)，他們都需要經(jīng)過(guò)兩道工序，每臺(tái)計(jì)算機(jī)所需的加工時(shí)間、銷售利潤(rùn)及該廠每周最大的加工能力如下表：AS周最大加工能力工序1（h/臺(tái)）46150h工序2（h/臺(tái)）3275h利潤(rùn)（元/臺(tái)）300450工廠經(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í)間最好

17、恰為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á)到最大流。最大流量為134，求下圖中流值為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)整流量，

18、得新的流量網(wǎng)絡(luò)對(duì)新的流量網(wǎng)絡(luò)，得到長(zhǎng)度網(wǎng)絡(luò)最短路：調(diào)整流量，得新的流量網(wǎng)絡(luò) PERT圖 與關(guān)鍵路線法1，下表給出一個(gè)汽車庫(kù)及引道的施工計(jì)劃：作業(yè)編號(hào)作業(yè)內(nèi)容作業(yè)時(shí)間（天）緊前作業(yè)1清理場(chǎng)地準(zhǔn)備施工10無(wú)2備料8無(wú)3車庫(kù)地面施工61，24墻及房頂 架預(yù)制1625車庫(kù)混凝土地面保養(yǎng)2436豎立墻架44，57豎立房頂 架468裝窗及邊墻1069裝門4610裝天花板12711油漆168，9，1012引道混凝土施工8313引道混凝土保養(yǎng)241214清理場(chǎng)地交工驗(yàn)收411，13請(qǐng)解答（1）該工程從施工開始道工程結(jié)束的最短周期；（2）如果引道混凝土施工工期拖延10天，對(duì)整個(gè)工程進(jìn)度有何影響？（3）若裝天花板

19、的施工時(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天，

20、觀察它的平行工序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)額最大。010020030040050060010204260758590202545576570733018396178909540284765748085利潤(rùn)增長(zhǎng)額工廠投資1.解： 設(shè)sk表示第k個(gè)工廠到第4個(gè)工廠的投資數(shù)。Xk表示第k個(gè)工廠

21、的投資數(shù),則第4個(gè)階段如下：fX*01002003004005006000000100282810020047472003006565300400747440050080805006008585600fX*0100200300400500600000010028182802004746394703006565676167200400748386897889300500809210410810690108300600859811312612511895126300第3個(gè)階段：fX*0100200300400500600000010028252802004753455310030067727357

22、73200400899292856592100，20050010811411210493701141006001261331341241129873134200第2個(gè)階段：fX*0100200300400500600600134134134133128113901340，100，200第1個(gè)階段：最優(yōu)方案：1，0，200，300，1002，100，100，300，1003，200，100，200，1004，200，200，0，2002. 用動(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í)

23、,而由第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；E3200000a)建立這個(gè)問(wèn)題的收益矩陣；b)分別用悲觀主義、樂(lè)觀主義和等可能性決策準(zhǔn)則決定該公司應(yīng)采用哪一個(gè)設(shè)計(jì)方案；c)建立機(jī)會(huì)損失矩陣，并用最小機(jī)會(huì)損失決策準(zhǔn)則決定采取哪一個(gè)設(shè)計(jì)方案。E1E2E3A155090A2256104A3-459115收益矩陣（單位：萬(wàn)）：E1E2E3A1550909A2256104104A3-459115115樂(lè)觀準(zhǔn)則：選A3E1E2E3A1550909A2256104104A3-459115115悲觀準(zhǔn)則：選A1E1E2E3A1092525A2