運籌學(xué)課程設(shè)計

1、內(nèi)蒙古科技大學(xué)課程設(shè)計運籌學(xué)課程設(shè)計目錄第一章 自編題-1一、運輸規(guī)劃問題-1二、指派問題-4三、最小數(shù)問題-5第二章 上機(jī)題-8 一、線性規(guī)劃問題-8 1-82-93-104-115-126-147-15 二、運輸問題-168-159-1710-1711-18 三、最短路問題-1812-1813-1914-19 四、最大流問題-2015-2016-2117-2118-22 五、最小支撐樹問題-2319-2320-24參考文獻(xiàn)-24第一章自編題一、運輸規(guī)劃問題包頭市某冰箱工廠有三個分廠，生產(chǎn)同一種冰箱，供應(yīng)該廠在市內(nèi)的四個門市部銷售。已知三個分廠的日生產(chǎn)能力分別是50、60、50臺。四個門市部

2、的日銷售量分別是40、40、60、20臺。從各個分廠運往各門市部的運費如表1-11所示。試安排一個運費最低的運輸計劃。表1-11門市部工廠123 4供應(yīng)量總計19129650273776036591150需求量總計40406020解,（1）運用最小元素法求解，得初始基本可行解，如下表1-12表1-12銷地產(chǎn)地1234產(chǎn)量19 12 9 30 6 20502 7 3 40 7 20 7603 6 40 4 9 10 1150銷量40406020（2）用位勢法計算所有非基變量檢驗數(shù)，求得如下表1-13表1-13銷地產(chǎn)地1234產(chǎn)量19 （3） 12 （8） 9 30 6 20502 7 （3） 3

3、 40 7 20 7 （3）603 6 40 4 （-1） 9 10 11 （5）50銷量40406020（3）利用閉回路法進(jìn)一步求解：表1-14銷地產(chǎn)地1234產(chǎn)量19 （3） 12 （8） 9 30 6 20502- 7 （3） 3 40 7 + 20 7 （3）603 6 40 4 + （-1）- 9 10 11 （5）50銷量40406020（4）得出新方案，如表1-15表1-15銷地產(chǎn)地1234產(chǎn)量19 12 9 30 6 20502 7 3 30 7 30 7603 6 40 4 10 9 1150銷量40406020（5）經(jīng)檢驗所有空格的檢驗數(shù)均大于等于零，故此方案為最優(yōu)解。最優(yōu)

4、解為：x13=30，x14=20，x22=30，x23=30，x31=40，x32=10最優(yōu)方案運費z=309+206+303+307+406+104=970元（6）運用軟件進(jìn)行檢驗：最優(yōu)解如下* 起 至 銷點 發(fā)點 1 2 3 4 - - - - - 1 0 0 30 20 2 0 30 30 0 3 40 10 0 0此運輸問題的成本或收益為: 970二、指派問題現(xiàn)有四項不同的任務(wù)，分別由四個人去完成。因四個人的專長不同，所以每個人完成的任務(wù)所需的時間也不同(如 表1-21),試問如何安排他們的工作才能使總的工作時間最少？ 表1-21 （單位：小時）工作人1234甲10978乙5877丙5

5、465丁2345解：（1）變換效率系數(shù)矩陣，使其每行沒列都出現(xiàn)0元素 10 9 7 8 （-7） 3 2 0 1cij = 5 8 7 7 （-5） 0 3 2 2 5 4 6 5 （-4） 1 0 2 5 2 3 4 5 （-2） 0 1 2 3 （2）進(jìn)行試指派3 2 0 10 3 2 21 0 2 50 1 2 3（3）作最少的直線覆蓋所有的0元素，以確定該系數(shù)矩陣中能找到最多0元素3 2 0 10 3 2 2 1 0 2 50 1 2 3 （4）對矩陣進(jìn)行變換，以增加0元素3 2 0 1 4 2 0 00 3 2 2 0 2 1 01 0 2 5 2 0 2 00 1 2 3 0 0

6、1 1（5）重復(fù)第二步，找到最優(yōu)解4 2 0 0 4 2 0 00 2 1 0 或 0 2 1 02 0 2 0 2 0 2 00 0 1 1 0 0 0 1最優(yōu)方案1：乙1，丁2，甲3，丙4最少時間z=7+5+5+3=20小時最優(yōu)方案2：丁1，丙2，甲3，乙4 最少時間z=7+7+4+2=20小時因為軟件原因，無法進(jìn)行檢驗三、最小支撐樹問題 某網(wǎng)絡(luò)公司為沿著友誼大街8個居民點架設(shè)網(wǎng)線，連接8個居民點的道路如圖1-31所示，邊表示可架設(shè)網(wǎng)絡(luò)道路，邊權(quán)為道路的長度，設(shè)計一網(wǎng)線網(wǎng)絡(luò)連通這8個居民點，并使總的輸電線長度最短。54圖1-31223 1 2 634 725623 57 4 8解：（1）利

7、用破圈法求解：54圖1-32223 1 2 634 725623 57 4 854圖1-33223 1 2 634 725623 5 4 854圖1-34223 1 2 634 72523 5 4 84圖1-35223 1 2 634 72523 5 4 84圖1-36223 1 2 634 7223 5 4 8圖1-37223 1 2 634 7223 5 4 8至此，無圈，圖1-37為最小樹，各邊權(quán)之和為18,或如下1-38圖：各邊權(quán)之和也為184圖1-3823 1 2 623 7223 5 4 8（2）運用軟件進(jìn)行檢驗：此問題的最小生成樹如下：* 起點 終點 距離 - - - 1 3 2

8、 3 4 2 1 2 4 2 5 2 5 7 3 7 8 2 7 6 3此問題的解為:18第二章 上機(jī)題 一、線性規(guī)劃1. max z = s. t. 運算檢驗：目標(biāo)函數(shù)最優(yōu)值為 : 21 變量 最優(yōu)解 相差值 - - - 5 0 3 0 約束 松弛/剩余變量 對偶價格 - - - 1 0 .7 2 3 0 3 0 .8 4 5 0 目標(biāo)函數(shù)系數(shù)范圍 : 變量 下限 當(dāng)前值 上限 - - - - x1 1 3 無上限 x2 -1.5 2 6 常數(shù)項數(shù)范圍 : 約束 下限 當(dāng)前值 上限 - - - - 1 12 22 26.286 2 7 10 無上限 3 4.5 7 12 4 -4 1 無上限

9、2. max z= s.t. 運算檢驗：目標(biāo)函數(shù)最優(yōu)值為 : 31 變量 最優(yōu)解 相差值 - - - 13 0 5 0 約束 松弛/剩余變量 對偶價格 - - - 1 5 0 2 9 0 3 0 .5 4 0 .5 目標(biāo)函數(shù)系數(shù)范圍 : 變量 下限 當(dāng)前值 上限 - - - - 1 2 3 .667 1 2 常數(shù)項數(shù)范圍 : 約束 下限 當(dāng)前值 上限 - - - - 1 5 10 無上限 2 51 60 無上限 3 14.667 18 19.385 4 38 44 543. min z= s.t. 運算檢驗：目標(biāo)函數(shù)最優(yōu)值為 : 55 變量 最優(yōu)解 相差值 - - - 2 0 1 0 約束 松

10、弛/剩余變量 對偶價格 - - - 1 0 -5 2 7 0 3 0 -10 目標(biāo)函數(shù)系數(shù)范圍 : 變量 下限 當(dāng)前值 上限 - - - - 15 20 30 10 15 20 常數(shù)項數(shù)范圍 : 約束 下限 當(dāng)前值 上限 - - - - 1 3.6 5 6 2 -4 3 無上限 3 2.5 3 44 max z= s.t. 運算檢驗：目標(biāo)函數(shù)最優(yōu)值為 : 18 變量 最優(yōu)解 相差值 - - - 21 0 24 0 0 2 約束 松弛/剩余變量 對偶價格 - - - 1 0 1 2 0 1 3 7 0 目標(biāo)函數(shù)系數(shù)范圍 : 變量 下限 當(dāng)前值 上限 - - - - x1 1.5 2 無上限 x2

11、 -1.333 -1 無上限 x3 無下限 1 3 常數(shù)項數(shù)范圍 : 約束 下限 當(dāng)前值 上限 - - - - 1 -6 15 無上限 2 無下限 -3 4 3 -3 4 無上限5. min z= s.t. ,無約束，運算檢驗：目標(biāo)函數(shù)最優(yōu)值為 : 6 變量 最優(yōu)解 相差值 - - - 2 0 0 0 0 3.286 約束 松弛/剩余變量 對偶價格 - - - 1 8 0 2 0 -0.857 3 0 0.143 目標(biāo)函數(shù)系數(shù)范圍 : 變量 下限 當(dāng)前值 上限 - - - - -1.6 3 無上限 無下限 1 1 無下限 -2 1.286 常數(shù)項數(shù)范圍 : 約束 下限 當(dāng)前值 上限 - - -

12、 - 1 4 12 無上限 2 -6 8 8 3 6 6 無上限6.minz=-3x1+x2+x3-x4 s.t. 運算檢驗：目標(biāo)函數(shù)最優(yōu)值為 : 7 變量 最優(yōu)解 相差值 - - - 1 0 1 0 3 0 0 32.333 約束 松弛/剩余變量 對偶價格 - - - 1 0 .667 2 0 7 3 0 -11.667 目標(biāo)函數(shù)系數(shù)范圍 : 變量 下限 當(dāng)前值 上限 - - - - 無下限 -3 3.929 -6.462 1 無上限 -3.467 3 無上限 -33.333 -1 無上限 常數(shù)項數(shù)范圍 : 約束 下限 當(dāng)前值 上限 - - - - 1 -3 0 無上限 2 8 9 10 3

13、 5.4 6 6.757. min z= s.t. (j=1,4)運算檢驗：目標(biāo)函數(shù)最優(yōu)值為 : 5 變量 最優(yōu)解 相差值 - - - 0 9 0 0 1 0 1 0 約束 松弛/剩余變量 對偶價格 - - - 1 0 -2 2 0 3 目標(biāo)函數(shù)系數(shù)范圍 : 變量 下限 當(dāng)前值 上限 - - - - -4 5 無上限 -2 -2 無上限 3 3 無上限 無下限 2 2 常數(shù)項數(shù)范圍 : 約束 下限 當(dāng)前值 上限 - - - - 1 6 7 9 2 2.333 3 3.5 二、運輸問題8.下列表中的數(shù)據(jù)是某公司的甲、乙、丙三個分廠向公司所屬四個門市部運送單位產(chǎn)品的運費。請給出總運費最低的運費值。

14、表2-7銷地產(chǎn)地1234供應(yīng)量甲82975乙523820丙15181515需求5101015運算檢驗：最優(yōu)解如下* 起 至 銷點 發(fā)點 1 2 3 4 - - - - - 1 0 0 0 5 2 5 0 5 10 3 0 10 5 0此運輸問題的成本或收益為: 2059.運輸問題銷地產(chǎn)地b1b2b3b4供應(yīng)量a1211446a2103595a378128需求量5347運算檢驗：最優(yōu)解如下* 起 至 銷點 發(fā)點 1 2 3 4 - - - - - 1 5 0 0 1 2 0 3 2 0 3 0 0 2 6此運輸問題的成本或收益為: 4710.運輸問題銷地產(chǎn)地b1b2b3b4供應(yīng)量a1311310

15、7a219264a3741059需求量3656運算檢驗：最優(yōu)解如下* 起 至 銷點 發(fā)點 1 2 3 4 - - - - - 1 2 0 5 0 2 1 0 0 3 3 0 6 0 3此運輸問題的成本或收益為: 7911.運輸問題銷地產(chǎn)地b1b2b3b4供應(yīng)量a184127a2694725a3534326需求量10102015運算檢驗：最優(yōu)解如下* 起 至 銷點 發(fā)點 1 2 3 4 - - - - - 1 0 0 7 0 2 12 0 13 0 3 0 10 0 15此運輸問題的成本或收益為: 206三、最短路問題12.最短路問題7 a65164 d145 s b t82 e5 c 從節(jié)點s到節(jié)點t的最短路* 起點 終點 距離 - - - s a 4 a b 1 b d 5 d t 6此問題的解為:1613.最短路問題3475219 1 3510388 v1