運籌學課程設計

1、內蒙古科技大學課程設計問題一：（類型：某物資運輸企業(yè)貨物運輸方案的優(yōu)化研究）三個水泥廠供應四個地區(qū)的建筑用水泥。假定等量的水泥在這些地區(qū)的使用效果相同，已知各水泥廠年產(chǎn)量，各地區(qū)的年需求量及各水泥廠到各地區(qū)單位水泥的運價表如下表所示，試給出一個基本可行方案。 運價：萬元/萬噸 地區(qū)水泥廠 北京 山東 河北 江蘇 產(chǎn)量 保利 萬科 恒大3 11 3 101 9 2 87 4 10 5 50 40 50 需求量 30 70 30 10表1.10解：（1）編制運輸表，用最小元素法確定初始方案 地區(qū)水泥廠北京山東河北江蘇產(chǎn)量保利31131050萬科1303092840恒大7410550需求量30703

2、010表1.11 地區(qū)水泥廠北京山東河北江蘇產(chǎn)量保利31131050萬科19284030 10恒大7410550需求量30703010表1.12 地區(qū)水泥廠北京山東河北江蘇產(chǎn)量保利3113201050萬科1928403010恒大7410550需求量30703010表1.13 地區(qū)水泥廠北京山東河北江蘇產(chǎn)量保利3113201050萬科1928403010恒大7410550 50需求量30703010表1.14 地區(qū)水泥廠北京山東河北江蘇產(chǎn)量保利311320101050萬科1928403010恒大7410550 50需求量30703010表1.15 地區(qū)水泥廠北京山東河北江蘇產(chǎn)量保利3113105

3、0202010萬科1928403010恒大741055050需求量30703010表1.16初始方案為：x12=20, x13=20, x14=10x21=30, x23=10x32=50其余為 xij = 0相應的運輸費用為：z = 630（萬元）（2）最優(yōu)性檢驗：用位勢法算出上述方案中所有空格的檢驗數(shù) 地區(qū)水泥廠北京山東河北江蘇行保利3 (1)1131010u1=72020萬科130928 (-1)u2=6 (-1)10恒大7 (12)45010 (14)5 (2)u3=0列v1=-5v2=4v3=-4v4=3表1.17上表中存在檢驗數(shù)為負數(shù)，表明初始方案不是最優(yōu)方案，需要進一步調整。（3

4、）用閉回路法進行方案調整，從而得到新的調運方案。 地區(qū)水泥廠北京山東河北江蘇產(chǎn)量保利3 1110330101050萬科1309 10208 40恒大7 45010 5 50 需求量30 70 3010表1.18新方案為：x12=10, x13=30, x14=10x21=30, x22=10, x23=0 x32=50其余為 xij = 0相應的運輸費用為：z = 620（萬元）(4)重復用位勢法檢驗。 地區(qū)水泥廠北京山東河北江蘇行保利3 (0)11103301010u1=7萬科1309 10208 (0)u2=5恒大7 (11)45010 (13)5 (2)u3=0列v1=-4v2=4v3=

5、-3v4=3表1.19上表中不存在負檢驗數(shù)，表明新方案是最優(yōu)方案。所以，最優(yōu)方案為： x12=10, x13=30, x14=10x21=30, x22=10, x23=0 x32=50其余為 xij = 0相應的運輸費用為：z = 620（萬元）軟件運行結果：最優(yōu)解如下* 起 至 銷點 發(fā)點 1 2 3 4 - - - - - 1 0 10 30 10 2 30 10 0 0 3 0 50 0 0此運輸問題的成本或收益為: 620此問題的另外的解如下： 起 至 銷點 發(fā)點 1 2 3 4 - - - - - 1 0 20 30 0 2 30 0 0 10 3 0 50 0 0此運輸問題的成本

6、或收益為: 620此問題的另外的解如下： 起 至 銷點 發(fā)點 1 2 3 4 - - - - - 1 20 0 30 0 2 10 20 0 10 3 0 50 0 0此運輸問題的成本或收益為: 620問題二：（類型：某企業(yè)的生產(chǎn)計劃安排及優(yōu)化分析與研究）正華煤機廠生產(chǎn)焦炭、煤焦油兩種產(chǎn)品，需要煤、電、勞動力三種資源。計劃消耗定額、資源限額如下表。問焦炭、煤焦油兩種產(chǎn)品的產(chǎn)量計劃如何安排，才能使該廠獲得最大利潤？產(chǎn)品名稱消耗定額資源名稱 焦炭 煤焦油 資源限額 煤 電 勞動力 9 4 360噸 4 5 200千瓦 3 10 300工（日）單位產(chǎn)品利潤（萬元） 7 12 表2.10解：max z

7、 = 7x1+12x2s.t.（1） 確定可行域304090x1x2040501004x1+5x2=2003x1+10x2=3009x1+4x2=360圖2.11（2） 從可行域內尋找最優(yōu)解304090x1x2040501004x1+5x2=2003x1+10x2=3009x1+4x2=360y=-7/12xa圖2.12（3） 確定最優(yōu)點坐標a點坐標就是該問題的最優(yōu)解，它是直線4x1+5x2200與直線3x1+10x2300的交點，解方程組得x1=20,x2=24;將其帶入目標函數(shù)有z = 720+1224=428 這表明最優(yōu)生產(chǎn)計劃是焦炭、煤焦油的產(chǎn)量分別為20、24時，可獲得最大利潤為42

8、8萬元。軟件運行結果： *最優(yōu)解如下* 目標函數(shù)最優(yōu)值為 : 428 變量 最優(yōu)解 相差值 - - - x1 20 0 x2 24 0 約束 松弛/剩余變量 對偶價格 - - - 1 84 0 2 0 1.36 3 0 .52 目標函數(shù)系數(shù)范圍 : 變量 下限 當前值 上限 - - - - x1 3.6 7 9.6 x2 8.75 12 23.333 常數(shù)項數(shù)范圍 : 約束 下限 當前值 上限 - - - - 1 276 360 無上限 2 150 200 226.923 3 227.586 300 4001線性規(guī)劃1.1求解線性規(guī)劃問題： min z =x1-x2+x3 軟件運行結果： *最

9、優(yōu)解如下* 目標函數(shù)最優(yōu)值為 : -1.667 變量 最優(yōu)解 相差值 - - - x1 0 2.722 x2 5 0 x3 3.333 0 約束 松弛/剩余變量 對偶價格 - - - 1 18.333 0 2 0 -.167 3 0 .389 目標函數(shù)系數(shù)范圍 : 變量 下限 當前值 上限 - - - - x1 -1.722 1 無上限 x2 無下限 -1 3.083 x3 0 1 無上限 常數(shù)項數(shù)范圍 : 約束 下限 當前值 上限 - - - - 1 1.667 20 無上限 2 40 60 無上限 3 0 30 451.2求解線性規(guī)劃問題： max z = 2x1-4x2+5x3-6x4軟

10、件運行結果： *最優(yōu)解如下* 目標函數(shù)最優(yōu)值為 : 31 變量 最優(yōu)解 相差值 - - - x1 8 0 x2 0 66 x3 3 0 x4 0 130 約束 松弛/剩余變量 對偶價格 - - - 1 0 11 2 0 9 目標函數(shù)系數(shù)范圍 : 變量 下限 當前值 上限 - - - - x1 -1.667 2 無上限 x2 無下限 -4 62 x3 -4 5 無上限 x4 無下限 -6 124 常數(shù)項數(shù)范圍 : 約束 下限 當前值 上限 - - - - 1 -.667 2 無上限 2 -2 1 無上限1.3求解線性規(guī)劃問題： min z = x1-3x2-2x3軟件運行結果： *最優(yōu)解如下*

11、目標函數(shù)最優(yōu)值為 : 0 變量 最優(yōu)解 相差值 - - - x1 0 5 x2 0 2.25 x3 0 6 約束 松弛/剩余變量 對偶價格 - - - 1 7 0 2 12 0 3 0 1 目標函數(shù)系數(shù)范圍 : 變量 下限 當前值 上限 - - - - x1 -4 1 無上限 x2 無下限 -3 -.75 x3 -8 -2 無上限 常數(shù)項數(shù)范圍 : 約束 下限 當前值 上限 - - - - 1 0 7 無上限 2 無下限 -12 0 3 0 0 91.4某工廠生產(chǎn)a、b、c三種產(chǎn)品，每種產(chǎn)品的原料消耗量、機械臺時消耗量、資源限量及單位產(chǎn)品利潤如下表所示。根據(jù)用戶訂貨，三種產(chǎn)品的最低月需求量分別

12、為200、250和100件；又據(jù)銷售預測，三種產(chǎn)品的最大生產(chǎn)量應分別為250、280和120件。如何安排這三種產(chǎn)品的 產(chǎn)量可使該廠的利潤最大？列出該問題的線性規(guī)劃模型并求解。 a b c 資源量 材料 1.0 1.5 4.1 2000 機械 2.0 1.2 1.0 1000 利潤（元） 10 14 12 解：max z =10x1+14x2+12x3 軟件運行結果： *最優(yōu)解如下* 目標函數(shù)最優(yōu)值為 : 7860 變量 最優(yōu)解 相差值 - - - x1 250 0 x2 280 0 x3 120 0 約束 松弛/剩余變量 對偶價格 - - - 1 838 0 2 44 0 3 0 10 4 0

13、 14 5 0 12 目標函數(shù)系數(shù)范圍 : 變量 下限 當前值 上限 - - - - x1 0 10 無上限 x2 0 14 無上限 x3 0 12 無上限 常數(shù)項數(shù)范圍 : 約束 下限 當前值 上限 - - - - 1 1162 2000 無上限 2 956 1000 無上限 3 0 250 272 4 0 280 316.667 5 0 120 1642運輸問題2.1某一物資調運問題如下表所示，試求最優(yōu)調運方案。 銷地單價產(chǎn)地 b1 b2 b3 b4 產(chǎn)量 a1 a2 a3 3 11 6 10 1 9 9 7 7 5 8 8 7 8 9 需求量 7 8 6 7 表2.01軟件運行結果; 最

14、優(yōu)解如下* 起 至 銷點 發(fā)點 1 2 3 4 - - - - - 1 1 0 6 0 2 6 0 0 2 3 0 8 0 1此運輸問題的成本或收益為: 107注釋：總需求量多出總供應量 4 第4個銷地未被滿足，缺少 42.2求解運輸問題： 銷地單價產(chǎn)地 b1 b2 b3 b4 產(chǎn)量 a1 a2 a3 3 11 3 10 1 9 2 8 7 4 10 5 7 4 9 需求量 3 6 5 6 表2.02軟件運行結果：最優(yōu)解如下* 起 至 銷點 發(fā)點 1 2 3 4 - - - - - 1 0 0 5 2 2 3 0 0 1 3 0 6 0 3此運輸問題的成本或收益為: 85此問題的另外的解如下：

15、 起 至 銷點 發(fā)點 1 2 3 4 - - - - - 1 2 0 5 0 2 1 0 0 3 3 0 6 0 3此運輸問題的成本或收益為: 852.3某地區(qū)有三個化肥廠，估計每年可供應本地區(qū)的數(shù)字為：化肥廠a為7萬噸，b為8萬噸，c為3萬噸。有四個產(chǎn)糧區(qū)需要該化肥，需求量為：甲地區(qū)為6萬噸，乙地區(qū)為6萬噸，丙地區(qū)為3萬噸，丁地區(qū)為3萬噸。已知從各化肥廠到各產(chǎn)糧區(qū)的每噸化肥的運價如下表所示。 （單位：萬元/萬噸）產(chǎn)區(qū)單價化肥廠 甲 乙 丙 丁 產(chǎn)量 a b c 5 8 4 3 4 9 10 7 8 4 2 9 7 8 3 需求量 6 6 3 3 表2.03軟件運行結果： 最優(yōu)解如下* 起 至

16、 銷點 發(fā)點 1 2 3 4 - - - - - 1 0 1 3 3 2 6 2 0 0 3 0 3 0 0此運輸問題的成本或收益為: 833整數(shù)規(guī)劃3.1求解整數(shù)規(guī)劃問題： max z = 11x1+4x2s.t. 軟件運行結果：*最優(yōu)解如下* 目標函數(shù)最優(yōu)值為 : 34 變量 最優(yōu)解 - - x1 2 x2 3 約束 松弛/剩余 - - 1 3 2 0 3 3 4 2 5 3 3.2求解整數(shù)規(guī)劃問題： max z =9x1+6x2+5x3軟件運行結果：*最優(yōu)解如下* 目標函數(shù)最優(yōu)值為 : 45 變量 最優(yōu)解 - - x1 3 x2 3 x3 0 約束 松弛/剩余 - - 1 2.5 2 3

17、 3 3 4 3 5 0 3.3求解01規(guī)劃問題： min z =2x1+5x2+3x3+4x4s.t. 軟件運行結果：*最優(yōu)解如下* 目標函數(shù)最優(yōu)值為 : 4 變量 最優(yōu)解 - - x1 0 x2 0 x3 0 x4 1 約束 松弛/剩余 - - 1 1 2 0 3 0 3.4某公司計劃用集裝箱托運甲、乙兩種貨物，每箱的體積、凈載重、可獲取的利潤及托運所受限制如下表。 集裝箱體積和載重情況表 貨 物 體積（米3/箱） 凈載重（噸/箱） 利潤（元/箱） 甲 5 2 2000 乙 4 5 1000 托運限制 24（米3） 13（噸）表3.01問：該公司應當如何充分利用集裝箱的空間和承重來獲得最大

18、的利潤？設：x1,x2分別為甲、乙兩種貨物的托運箱數(shù)，建立模型如下：max z = 2000x1+1000x2且為整數(shù)軟件運行結果：*最優(yōu)解如下* 目標函數(shù)最優(yōu)值為 : 9000 變量 最優(yōu)解 - - x1 4 x2 1 約束 松弛/剩余 - - 1 0 2 0 3 4 4 1 4圖與網(wǎng)絡分析4.1求解下圖的最小支撐樹。 v1v2v5v6v3v44357864479圖4.01軟件運行結果： 此問題的最小生成樹如下：* 起點 終點 距離 - - - 1 4 3 1 2 4 2 3 5 3 5 4 5 6 4 此問題的解為:204.2求從起點v1到終點v5的最短路。 v1v2v3v4v562148212圖4.02軟件運行結果： 從節(jié)點 1到節(jié)點5的最短路* 起點 終點 距離 - - - 1 3 2