管理運(yùn)籌學(xué)(第3版)章后習(xí)題解析(上)課后習(xí)題答案.pdf

677 管理運(yùn)籌學(xué) 第 3 版 章后習(xí)題解析 第 2 章 線性規(guī)劃的圖解法 1 解 1 可行域?yàn)?OABC 2 等值線為圖中虛線部分 3 由圖 2 1 可知 最優(yōu)解為 B 點(diǎn) 最優(yōu)解 1 x 12 7 2 15 7 x 最優(yōu)目標(biāo)函數(shù)值 69 7 圖 2 1 2 解 1 如圖2 2所示 由圖解法可知有唯一解 1 2 0 2 0 6 x x 函數(shù)值為3 6 圖 2 2 678 2 無可行解 3 無界解 4 無可行解 5 無窮多解 6 有唯一解 1 2 20 3 8 3 x x 函數(shù)值為 92 3 3 解 1 標(biāo)準(zhǔn)形式 12123 max32000fxxsss 121 122 123 12123 9230 3213 229 0 xxs xxs xxs x x s s s 2 標(biāo)準(zhǔn)形式 1212 min4600fxxss 121 122 12 1212 36 210 764 0 xxs xxs xx x x s s 3 標(biāo)準(zhǔn)形式 12212 min2200fxxxss 1221 122 1222 12212 35570 25550 32230 0 xxxs xxx xxxs x xxs s 4 解 標(biāo)準(zhǔn)形式 1212 max10500zxxss 121 122 1212 349 528 0 xxs xxs x x s s 松弛變量 0 0 最優(yōu)解為 1 x 1 x2 3 2 5 解 679 標(biāo)準(zhǔn)形式 12123 min118000fxxsss 121 122 123 12123 10220 3318 4936 0 xxs xxs xxs x x s s s 剩余變量 0 0 13 最優(yōu)解為 x1 1 x2 5 6 解 1 最優(yōu)解為 x1 3 x2 7 2 1 13c 3 2 26c 理由見百 分之一百法則 3 解 1 18 000 3 000 102 000 153 000 682 2 總投資額的松弛變量為0 表示投資額正好為1 200 000 基金B(yǎng)的投資額的剩余變量 為0 表示投資B基金的投資額正好為300 000 3 總投資額每增加1個(gè)單位 回報(bào)額增加0 1 基金B(yǎng)的投資額每增加1個(gè)單位 回報(bào)額下降0 06 4 1 c不變時(shí) 2 c在負(fù)無窮到10的范圍內(nèi)變化 其最優(yōu)解不變 2 c不變時(shí) 1 c在2到正無窮的范圍內(nèi)變化 其最優(yōu)解不變 5 約束條件1的右邊值在300 000到正無窮的范圍內(nèi)變化 對偶價(jià)格仍為0 1 約束條件2的右邊值在0到1 200 000的范圍內(nèi)變化 對偶價(jià)格仍為 0 06 6 600000300000 900000900000 100 故對偶價(jià)格不變 4 解 1 1 8 5x 2 1 5x 3 0 x 4 0 x 最優(yōu)目標(biāo)函數(shù)18 5 2 約束條件2和3 對偶價(jià)格為2和3 5 約束條件2和3的常數(shù)項(xiàng)增加一個(gè)單位目標(biāo)函 數(shù)分別提高2和3 5 3 第3個(gè) 此時(shí)最優(yōu)目標(biāo)函數(shù)值為22 4 在負(fù)無窮到5 5的范圍內(nèi)變化 其最優(yōu)解不變 但此時(shí)最優(yōu)目標(biāo)函數(shù)值變化 5 在0到正無窮的范圍內(nèi)變化 其最優(yōu)解不變 但此時(shí)最優(yōu)目標(biāo)函數(shù)值變化 5 解 1 約束條件2的右邊值增加1個(gè)單位 目標(biāo)函數(shù)值將增加3 622 2 2 x目標(biāo)函數(shù)系數(shù)提高到0 703 最優(yōu)解中 2 x的取值可以大于零 3 根據(jù)百分之一百法則判定 因?yàn)樵试S減少的百分比與允許增加的百分比之和 12 100 14 583 所以最優(yōu)解不變 4 因?yàn)?1565 100 309 189111 25 15 根據(jù)百分之一百法則 我們不能判定其對偶價(jià)格 是否有變化 683 第 4 章 線性規(guī)劃在工商管理中的應(yīng)用 1 解 為了用最少的原材料得到10臺(tái)鍋爐 需要混合使用14種下料方案 設(shè)按14種方案下料的原材料的根數(shù)分別為x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 模型如表4 1所示 表 4 1 各種下料方式 1 2 3 4 5 6 7 8 9 1011 12 13 14 2 640 mm 2 1 1 1 0 0 0 0 0 0 0 0 0 0 1 770 mm 0 1 0 0 3 2 2 1 1 1 0 0 0 0 1 650 mm 0 0 1 0 0 1 0 2 1 0 3 2 1 0 1 440 mm 0 0 0 1 0 0 1 0 1 2 0 1 2 3 min f x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 s t 2x1 x2 x3 x4 80 x2 3x5 2x6 2x7 x8 x9 x10 350 x3 x6 2x8 x9 3x11 2x12 x13 420 x4 x7 x9 2x10 x12 2x13 3x14 10 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14 0 用管理運(yùn)籌學(xué)軟件我們可以求得此問題的解為 x1 40 x2 0 x3 0 x4 0 x5 116 667 x6 0 x7 0 x8 0 x9 0 x10 0 x11 140 x12 0 x13 0 x14 3 333 最優(yōu)值為300 2 解 從上午11時(shí)到下午10時(shí)分成11個(gè)班次 設(shè)xi表示第i班次安排的臨時(shí)工的人數(shù) 模型如下 min f 16 x1 x 2 x3 x4 x5 x6 x7 x8 x9 x10 x11 s t x1 1 9 x1 x2 1 9 x1 x2 x3 2 9 x1 x2 x3 x4 2 3 x2 x3 x4 x5 1 3 x3 x4 x5 x6 2 3 x4 x5 x6 x7 1 6 x5 x6 x7 x8 2 12 x6 x7 x8 x9 2 12 x7 x8 x9 x10 1 7 x8 x9 x10 x11 1 7 684 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 0 用管理運(yùn)籌學(xué)軟件我們可以求得此問題的解如下 x1 8 x2 0 x3 1 x4 1 x5 0 x6 4 x7 0 x8 6 x9 0 x10 0 x11 0 最優(yōu)值為320 1 在滿足對職工需求的條件下 在11時(shí)安排8個(gè)臨時(shí)工 13時(shí)新安排1個(gè)臨時(shí)工 14 時(shí)新安排1個(gè)臨時(shí)工 16時(shí)新安排4個(gè)臨時(shí)工 18時(shí)新安排6個(gè)臨時(shí)工可使臨時(shí)工的總成本 最小 2 這時(shí)付給臨時(shí)工的工資總額為80元 一共需要安排20個(gè)臨時(shí)工的班次 約束 松弛 剩余變量 對偶價(jià)格 1 0 4 2 0 0 3 2 0 4 9 0 5 0 4 6 5 0 7 0 0 8 0 0 9 0 4 10 0 0 11 0 0 根據(jù)剩余變量的數(shù)字分析可知 可以讓11時(shí)安排的8個(gè)人工做3小時(shí) 13時(shí)安排的1個(gè) 人工作3小時(shí) 可使得總成本更小 3 設(shè)xi表示第i班上班4小時(shí)臨時(shí)工人數(shù) yj表示第j班上班3小時(shí)臨時(shí)工人數(shù) min f 16 x1 x 2 x3 x4 x5 x6 x7 x8 12 y1 y2 y3 y4 y5 y6 y7 y8 y9 s t x1 y1 1 9 x1 x2 y1 y2 1 9 x1 x2 x3 y1 y2 y3 2 9 x1 x2 x3 x4 y2 y3 y4 2 3 x2 x3 x4 x5 y3 y4 y5 1 3 x3 x4 x5 x6 y4 y5 y6 2 3 x4 x5 x6 x7 y5 y6 y7 1 6 x5 x6 x7 x8 y6 y7 y8 2 12 x6 x7 x8 y7 y8 y9 2 12 x7 x8 y8 y9 1 7 x8 y9 1 7 x1 x2 x3 x4 x5 x6 x7 x8 y1 y2 y3 y4 y5 y6 y7 y8 y9 0 用管理運(yùn)籌學(xué)軟件我們可以求得此問題的解如下 685 x1 0 x2 0 x3 0 x4 0 x5 0 x6 0 x7 0 x8 6 y1 8 y2 0 y3 1 y4 0 y5 1 y6 0 y7 4 y8 0 y9 0 最優(yōu)值為264 具體安排如下 在11 00 12 00安排8個(gè)3小時(shí)的班 在13 00 14 00安排1個(gè)3小時(shí)的班 在 15 00 16 00安排1個(gè)3小時(shí)的班 在17 00 18 00安排4個(gè)3小時(shí)的班 在18 00 19 00安排6個(gè)4小時(shí)的班 總成本最小為264元 能比第一問節(jié)省320 264 56元 3 解 設(shè)生產(chǎn)A B C三種產(chǎn)品的數(shù)量分別為x1 x2 x3 則可建立下面的數(shù)學(xué)模型 max z 10 x1 12x2 14x3 s t x1 1 5x2 4x3 2 000 2x1 1 2x2 x3 1 000 x1 200 x2 250 x3 100 x1 x2 x3 0 用管理運(yùn)籌學(xué)軟件我們可以求得此問題的解如下 x1 200 x2 250 x3 100 最優(yōu)值為6 400 1 在資源數(shù)量及市場容量允許的條件下 生產(chǎn)A 200件 B 250件 C 100件 可使生產(chǎn) 獲利最多 2 A B C的市場容量的對偶價(jià)格分別為10元 12元 14元 材料 臺(tái)時(shí)的對偶價(jià)格 均為0 說明A的市場容量增加一件就可使總利潤增加10元 B的市場容量增加一件就可使總 利潤增加12元 C的市場容量增加一件就可使總利潤增加14元 但增加一千克的材料或增加 一個(gè)臺(tái)時(shí)數(shù)都不能使總利潤增加 如果要開拓市場應(yīng)當(dāng)首先開拓C產(chǎn)品的市場 如果要增加資 源 則應(yīng)在0價(jià)位上增加材料數(shù)量和機(jī)器臺(tái)時(shí)數(shù) 4 解 設(shè)白天調(diào)查的有孩子的家庭的戶數(shù)為x11 白天調(diào)查的無孩子的家庭的戶數(shù)為x12 晚上調(diào)查的 有孩子的家庭的戶數(shù)為x21 晚上調(diào)查的無孩子的家庭的戶數(shù)為x22 則可建立下面的數(shù)學(xué)模型 min f 25x11 20 x12 30 x21 24x22 s t x11 x12 x21 x22 2 000 x11 x12 x21 x22 x11 x21 700 x12 x22 450 x11 x12 x21 x22 0 用管理運(yùn)籌學(xué)軟件我們可以求得此問題的解如下 x11 700 x12 300 x21 0 x22 1 000 最優(yōu)值為47 500 686 1 白天調(diào)查的有孩子的家庭的戶數(shù)為700戶 白天調(diào)查的無孩子的家庭的戶數(shù)為300戶 晚上調(diào)查的有孩子的家庭的戶數(shù)為0 晚上調(diào)查的無孩子的家庭的戶數(shù)為1 000戶 可使總調(diào)查 費(fèi)用最小 2 白天調(diào)查的有孩子的家庭的費(fèi)用在20 26元之間 總調(diào)查方案不會(huì)變化 白天調(diào)查的 無孩子的家庭的費(fèi)用在19 25元之間 總調(diào)查方案不會(huì)變化 晚上調(diào)查的有孩子的家庭的費(fèi)用 在29到正無窮之間 總調(diào)查方案不會(huì)變化 晚上調(diào)查的無孩子的家庭的費(fèi)用在 20 25元之間 總調(diào)查方案不會(huì)變化 3 發(fā)調(diào)查的總戶數(shù)在1 400到正無窮之間 對偶價(jià)格不會(huì)變化 有孩子家庭的最少調(diào)查 數(shù)在0到1 000之間 對偶價(jià)格不會(huì)變化 無孩子家庭的最少調(diào)查數(shù)在負(fù)無窮到1 300之間 對 偶價(jià)格不會(huì)變化 5 解 設(shè)第i個(gè)月簽訂的合同打算租用j個(gè)月的面積為xij 則需要建立下面的數(shù)學(xué)模型 min f 2 800 x11 4 500 x12 6 000 x13 7 300 x14 2 800 x21 4 500 x22 6 000 x23 2 800 x31 4 500 x32 2 800 x41 s t x11 15 x12 x21 10 x13 x22 x31 20 x14 x23 x32 x41 12 xij 0 i j 1 2 3 4 用管理運(yùn)籌學(xué)軟件我們可以求得此問題的解如下 x11 15 x12 0 x13 0 x14 0 x21 10 x22 0 x23 0 x31 20 x32 0 x41 12 最優(yōu)值為159 600 即在一月份租用1 500平方米一個(gè)月 在二月份租用1 000平方米一個(gè)月 在三月份租用2 000平方米一個(gè)月 四月份租用1 200平方米一個(gè)月 可使所付的租借費(fèi)最小 6 解 設(shè)xij表示第i種類型的雞需要第j種飼料的量 可建立下面的數(shù)學(xué)模型 max z 9 x11 x12 x13 7 x21 x22 x23 8 x31 x32 x33 5 5 x11 x21 x31 4 x12 x22 x32 5 x13 x23 x33 s t x11 0 5 x11 x12 x13 x12 0 2 x11 x12 x13 x21 0 3 x21 x22 x23 x23 0 3 x21 x22 x23 x33 0 5 x31 x32 x33 x11 x21 x31 30 x12 x22 x32 30 x13 x23 x33 30 xij 0 i j 1 2 3 用管理運(yùn)籌學(xué)軟件我們可以求得此問題的解如下 x11 30 x12 10 x13 10 x21 0 x22 0 x23 0 x31 0 x32 20 x33 20 最優(yōu)值為335 即 687 生產(chǎn)雛雞飼料50噸 不生產(chǎn)蛋雞飼料 生產(chǎn)肉雞飼料40噸 7 解 設(shè)Xi為第i個(gè)月生產(chǎn)的產(chǎn)品 數(shù)量 Yi為第i個(gè)月生產(chǎn)的產(chǎn)品 數(shù)量 Zi Wi分別為第i 個(gè)月末產(chǎn)品 庫存數(shù) S i1 S i2 分別為用于第 i 1 個(gè)月庫存的自有及租借的倉庫容積 立 方米 則可以建立如下模型 min z 51212 12 161 58 4 57 iiiiii iii xyxySS s t X1 10 000 Z1 X2 Z1 10 000 Z2 X3 Z2 10 000 Z3 X4 Z3 10 000 Z4 X5 Z4 30 000 Z5 X6 Z5 30 000 Z6 X7 Z6 30 000 Z7 X8 Z7 30 000 Z8 X9 Z8 30 000 Z9 X10 Z9 100 000 Z10 X11 Z10 100 000 Z11 X12 Z11 100 000 Z12 Y1 50 000 W1 Y2 W1 50 000 W2 Y3 W2 15 000 W3 Y4 W3 15 000 W4 Y5 W4 15 000 W5 Y6 W5 15 000 W6 Y7 W6 15 000 W7 Y8 W7 15 000 W8 Y9 W8 15 000 W9 Y10 W9 50 000 W10 Y11 W10 50 000 W11 Y12 W11 50 000 W12 S1i 15 000 1 i 12 Xi Yi 120 000 1 i 12 0 2Zi 0 4Wi 12ii SS 31 i 12 Xi 0 0 i Y Zi 12 0 0 0 0 iii WSS 用管理運(yùn)籌學(xué)軟件我們可以求得此問題的解如下 688 最優(yōu)值為4 910 500 X1 10 000 X2 10 000 X3 10 000 X4 10 000 X5 30 000 X6 30 000 X7 30 000 X8 45 000 X9 105 000 X10 70 000 X11 70 000 X12 70 000 Y1 50 000 Y2 50 000 Y3 15 000 Y4 15 000 Y5 15 000 Y6 15 000 Y7 15 000 Y8 15 000 Y9 15 000 Y10 50 000 Y11 50 000 Y12 50 000 Z8 15 000 Z9 90 000 Z10 60 000 Z11 30 000 S18 3 000 S19 15 000 S110 12 000 S111 6 000 S29 3 000 其余變量都等于0 8 解 設(shè)第i個(gè)車間生產(chǎn)第j種型號(hào)產(chǎn)品的數(shù)量為xij 可以建立下面的數(shù)學(xué)模型 1121 max25 xx 3141511232425213234353 20 17 xxxxxxxxxxx 11 142444 xxx s t 1121314151 1400 xxxxx 12324252 300 xxxx 12324252 800 xxxx 13234353 8000 xxxx 142444 700 xxx 11121314 576518000 xxxx 212324 63315000 xxx 4 3132 314000 xx 41424344 324212000 xxxx 515253 24510000 xxx x0 1 2 3 4 5 ij i j 1 2 3 4 用管理運(yùn)籌學(xué)軟件我們可以求得此問題的解如下 最優(yōu)解如下 目標(biāo)函數(shù)最優(yōu)值為 279 400 變量 最優(yōu)解 相差值 x11 0 11 x21 0 26 4 x31 1 400 0 x41 0 16 5 x51 0 5 28 x12 0 15 4 x32 800 0 x42 0 11 x52 0 10 56 x13 1 000 0 689 x23 5 000 0 x43 0 8 8 x53 2 000 0 x14 2 400 0 x24 0 2 2 x44 6 000 0 約束 松弛 剩余變量 對偶價(jià)格 1 0 25 2 500 0 3 0 20 4 0 3 8 5 7 700 0 6 0 2 2 7 0 4 4 8 6 000 0 9 0 5 5 10 0 2 64 目標(biāo)函數(shù)系數(shù)范圍 變量 下限 當(dāng)前值 上限 x11 無下限 25 36 x21 無下限 25 51 4 x31 19 72 25 無上限 x41 無下限 25 41 5 x51 無下限 25 30 28 x12 無下限 20 35 4 x32 9 44 20 無上限 x42 無下限 20 31 x52 無下限 20 30 56 x13 13 2 17 19 2 x23 14 8 17 無上限 x43 無下限 17 25 8 x53 3 8 17 無上限 x14 9 167 11 14 167 x24 無下限 11 13 2 x44 6 6 11 無上限 常數(shù)項(xiàng)數(shù)范圍 690 約束 下限 當(dāng)前值 上限 1 0 1 400 2 900 2 無下限 300 800 3 300 800 2 800 4 7 000 8 000 10 000 5 無下限 700 8 400 6 6 000 18 000 無上限 7 9 000 15 000 18 000 8 8 000 14 000 無上限 9 0 12 000 無上限 10 0 10 000 15 000 11121314212324 31324142434451 5253 0 0 1000 2 400 0 5000 0 1400 800 0 0 0 6 000 0 0 2 000 xxxxxxx xxxxxxx xx 即 最優(yōu)值為279 400 對5個(gè)車間的可用生產(chǎn)時(shí)間做靈敏度分析可以按照以上管理運(yùn)籌學(xué)軟件的計(jì)算結(jié)果自行 進(jìn)行 9 解 設(shè)第一個(gè)月正常生產(chǎn)x1 加班生產(chǎn)x2 庫存x3 第二個(gè)月正常生產(chǎn)x4 加班生產(chǎn)x5 庫存 x6 第三個(gè)月正常生產(chǎn)x7 加班生產(chǎn)x8 庫存x9 第四個(gè)月正常生產(chǎn)x10 加班生產(chǎn)x11 可以 建立下面的數(shù)學(xué)模型 min f 200 x1 x4 x7 x10 300 x2 x5 x8 x11 60 x3 x6 x9 s t x1 4 000 x4 4 000 x7 4 000 x10 4 000 x3 4 000 x6 6 1000 x91000 x21000 x51000 x81000 x111000 123 4500 xxx 3456 3000 xxxx 6789 5500 xxxx 91011 4 500 xxx 691 1234567891011 0 x xxxxxxxxxx 用管理運(yùn)籌學(xué)軟件我們可以求得此問題的解如下 最優(yōu)值為f 3 710 000元 x1 4 000噸 x2 500噸 x3 0噸 x4 4 000噸 x5 0噸 x6 1 000噸 x7 4 000噸 x8 500噸 x9 0噸 x10 4 000噸 x11 500噸 692 第 5 章 單 純 形 法 1 解 表中a c e f是可行解 a b f是基本解 a f是基本可行解 2 解 1 該線性規(guī)劃的標(biāo)準(zhǔn)型如下 max 5x1 9x2 0s1 0s2 0s3 s t 0 5x1 x2 s1 8 x1 x2 s2 10 0 25x1 0 5x2 s3 6 x1 x2 s1 s2 s3 0 2 有兩個(gè)變量的值取零 因?yàn)橛腥齻€(gè)基變量 兩個(gè)非基變量 非基變量取零 3 4 6 0 0 2 T 4 0 10 2 0 1 T 5 不是 因?yàn)榛究尚薪庖蠡兞康闹等糠秦?fù) 6 略 3 解 1 表 5 1 1 x 2 x 3 x 1 s 2 s 3 s 迭代次數(shù) 基變量 B C 6 30 25 0 0 0 b s1 0 3 1 0 1 0 0 40 s2 0 0 2 1 0 1 0 50 s3 0 2 1 1 0 0 1 20 zj 0 0 0 0 0 0 0 0 jj cz 6 30 25 0 0 0 2 線性規(guī)劃模型如下 max 6x1 30 x2 25x3 s t 3x1 x2 s1 40 2x2 x3 s2 50 2x1 x 2 x3 s3 20 x1 x2 x3 s1 s2 s3 0 3 初始解的基為 s1 s2 s3 T 初始解為 0 0 0 40 50 20 T 對應(yīng)的目標(biāo)函數(shù) 693 值為0 4 第一次迭代時(shí) 入基變量時(shí)x2 出基變量為s3 4 解 最優(yōu)解為 2 25 0 T 最優(yōu)值為 9 圖 5 1 單純形法如表5 2所示 表 5 2 1 x 2 x 1 s 2 s 迭代次數(shù) 基變量 B C 4 1 0 0 b 1 s 0 1 3 1 0 7 2 s 0 4 2 0 1 9 j z 0 0 0 0 0 jj cz 4 1 0 0 1 s 0 0 2 5 1 0 25 4 75 1 x 4 1 0 5 0 0 25 2 25 j z 4 2 0 1 1 jj cz 0 1 0 1 5 解 1 最優(yōu)解為 2 5 4 T 最優(yōu)值為 84 2 最優(yōu)解為 0 0 4 T 最優(yōu)值為 4 6 解 有無界解 694 7 解 1 無可行解 2 最優(yōu)解為 4 4 T 最優(yōu)值為 28 3 有無界解 4 最優(yōu)解為 4 0 0 T 最優(yōu)值為 8 695 第 6 章 單純形法的靈敏度分析與對偶 1 解 1 c1 24 2 c2 6 3 cs2 8 2 解 1 c1 0 5 2 2 c3 0 3 cs2 0 5 3 解 1 b1 250 2 0 b2 50 3 0 b3 150 4 解 1 b1 4 2 0 b2 10 3 b3 4 5 解 1 利潤變動(dòng)范圍c1 3 故當(dāng)c1 2時(shí)最優(yōu)解不變 2 根據(jù)材料的對偶價(jià)格為1判斷 此做法不利 3 0 b2 45 4 最優(yōu)解不變 故不需要修改生產(chǎn)計(jì)劃 5 此時(shí)生產(chǎn)計(jì)劃不需要修改 因?yàn)樾碌漠a(chǎn)品計(jì)算的檢驗(yàn)數(shù)為 3小于零 對原生產(chǎn)計(jì)劃沒 有影響 6 解 均為唯一最優(yōu)解 根據(jù)從計(jì)算機(jī)輸出的結(jié)果看出 如果松弛或剩余變量為零且對應(yīng)的對偶 價(jià)格也為零 或者存在取值為零的決策變量并且其相差值也為零時(shí) 可知此線性規(guī)劃有無窮多 組解 7 解 1 min f 10y1 20y2 s t y1 y2 2 y1 5y2 1 y1 y2 1 y1 y2 0 2 max z 100y1 200y2 s t 1 2y1 4y2 4 696 2y1 6y2 4 2y1 3y2 2 y1 y2 0 8 解 1 min f 10y1 50y2 20y3 s t 2y1 3y2 y3 1 3y1 y2 2 y1 y2 y3 5 y1 y2 0 y3沒有非負(fù)限制 2 max z 6y1 3y2 2y3 s t y1 y2 y3 1 2y1 y2 y3 3 3y1 2y2 y3 2 y1 y2 0 y3沒有非負(fù)限制 9 解 123 1234 1235 236 max23 4 28 2 0 1 6 j zxxx xxxx xxxx xxx xj 用對偶單純形法解如表6 1所示 表 6 1 1 x 2 x 3 x 1 s 2 s 3 s 迭代次數(shù) 基變量 B C 1 2 3 0 0 0 b 1 s 0 1 1 1 1 0 0 4 2 s 0 1 1 2 0 1 0 8 3 s 0 0 1 1 0 0 1 2 j z 0 0 0 0 0 0 0 jj cz 1 2 3 0 0 0 1 x 1 1 1 1 1 0 0 4 2 s 0 0 2 1 1 1 0 4 3 s 0 0 1 1 0 0 1 2 j z 1 1 1 1 0 0 1 jj cz 0 3 2 1 0 0 697 續(xù)表 1 x 2 x 3 x 1 s 2 s 3 s 迭代次數(shù) 基變量 B C 1 2 3 0 0 0 b 1 x 1 1 0 0 1 0 1 6 2 s 0 0 0 3 1 1 2 0 2 x 2 0 1 1 0 0 1 2 j z 1 2 2 1 0 3 2 jj cz 0 0 5 1 0 3 最優(yōu)解為x1 6 x2 2 x3 0 目標(biāo)函數(shù)最優(yōu)值為10 698 第 7 章 運(yùn) 輸 問 題 1 解 1 此問題為產(chǎn)銷平衡問題 表 7 1 甲 乙 丙 丁 產(chǎn)量 1 分廠 21 17 23 25 300 2 分廠 10 15 30 19 400 3 分廠 23 21 20 22 500 銷量 400 250 350 200 1 200 最優(yōu)解如下 起 至 銷點(diǎn) 發(fā)點(diǎn) 1 2 3 4 1 0 250 0 50 2 400 0 0 0 3 0 0 350 150 此運(yùn)輸問題的成本或收益為 19 800 此問題的另外的解如下 起 至 銷點(diǎn) 發(fā)點(diǎn) 1 2 3 4 1 0 250 50 0 2 400 0 0 0 3 0 0 300 200 此運(yùn)輸問題的成本或收益為 19 800 2 如果2分廠產(chǎn)量提高到600 則為產(chǎn)銷不平衡問題 最優(yōu)解如下 起 至 銷點(diǎn) 發(fā)點(diǎn) 1 2 3 4 1 0 250 0 0 2 400 0 0 200 3 0 0 350 0 699 此運(yùn)輸問題的成本或收益為 19 050 注釋 總供應(yīng)量多出總需求量 200 第1產(chǎn)地的剩余50 第3個(gè)產(chǎn)地剩余150 3 銷地甲的需求提高后 也變?yōu)楫a(chǎn)銷不平衡問題 最優(yōu)解如下 起 至 銷點(diǎn) 發(fā)點(diǎn) 1 2 3 4 1 50 250 0 0 2 400 0 0 0 3 0 0 350 150 此運(yùn)輸問題的成本或收益為 19 600 注釋 總需求量多出總供應(yīng)量 150 第1個(gè)銷地未被滿足 缺少 100 第4個(gè)銷地未被滿足 缺少 50 2 解 首先 計(jì)算本題的利潤模型 如表7 2所示 表 7 2 甲 0 3 0 3 0 4 0 4 0 3 0 4 0 1 0 9 乙 0 3 0 3 0 1 0 1 0 4 0 2 0 2 0 6 丙 0 05 0 05 0 05 0 05 0 15 0 05 0 05 0 55 丁 0 2 0 2 0 3 0 3 0 1 0 1 0 1 0 1 由于目標(biāo)函數(shù)是 max 將目標(biāo)函數(shù)變?yōu)?min 則以上利潤模型變?yōu)橐韵履Ｐ?表 7 3 甲 0 3 0 3 0 4 0 4 0 3 0 4 0 1 0 9 乙 0 3 0 3 0 1 0 1 0 4 0 2 0 2 0 6 丙 0 05 0 05 0 05 0 05 0 15 0 05 0 05 0 55 丁 0 2 0 2 0 3 0 3 0 1 0 1 0 1 0 1 700 由于管理運(yùn)籌學(xué)軟件中要求所輸入的數(shù)值必須為非負(fù) 則將上表中的所有數(shù)值均加上1 因此表7 3就變?yōu)橐韵履Ｐ?表 7 4 甲 0 7 0 7 0 6 0 6 0 7 0 6 0 9 0 1 乙 0 7 0 7 0 9 0 9 1 4 0 8 1 2 0 4 丙 0 95 0 95 0 95 0 95 0 85 0 95 1 05 0 45 丁 1 2 1 2 0 7 0 7 0 9 1 1 1 1 0 9 加入產(chǎn)銷量變?yōu)檫\(yùn)輸模型如下 表 7 5 產(chǎn)量 甲 0 7 0 7 0 6 0 6 0 7 0 6 0 9 0 1 300 乙 0 7 0 7 0 9 0 9 1 4 0 8 1 2 0 4 500 丙 0 95 0 95 0 95 0 95 0 85 0 95 1 05 0 45 400 丁 1 2 1 2 0 7 0 7 0 9 1 1 1 1 0 9 100 銷量 150 150 150 100 350 200 250 150 由于以上模型銷量大于產(chǎn)量所以加入一個(gè)虛擬產(chǎn)地戊 產(chǎn)量為200 模型如表7 6所示 表 7 6 產(chǎn)量 甲 0 7 0 7 0 6 0 6 0 7 0 6 0 9 0 1 300 乙 0 7 0 7 0 9 0 9 1 4 0 8 1 2 0 4 500 丙 0 95 0 95 0 95 0 95 0 85 0 95 1 05 0 45 400 丁 1 2 1 2 0 7 0 7 0 9 1 1 1 1 0 9 100 戊 M 0 M 0 0 0 M 0 200 銷量 150 150 150 100 350 200 250 150 1 500 用管理運(yùn)籌學(xué)軟件計(jì)算得出結(jié)果如圖7 1所示 701 圖 7 1 由于計(jì)算過程中將表中的所有數(shù)值均加上 1 因此應(yīng)將這部分加上的值去掉 所以 935 1300 1365 又因?yàn)樽畛鯇⒛繕?biāo)函數(shù)變?yōu)榱?min 因此此利潤問題的結(jié)果為365 3 解 建立的運(yùn)輸模型如表7 7 表 7 7 1 2 3 0 60 120 180 2 1 600 600 60 600 60 2 3 1 600 600 10 600 600 10 60 600 600 10 60 2 3 2 M 700 700 60 4 2 M 700 700 10 700 700 10 60 2 3 M M 650 2 3 M M 650 650 10 3 5 5 6 最優(yōu)解如下 起 至 銷點(diǎn) 發(fā)點(diǎn) 1 2 3 1 1 0 1 2 3 0 0 3 1 1 0 702 4 0 4 0 5 0 0 0 6 0 0 2 7 0 0 3 此運(yùn)輸問題的成本或收益為 9 665 注釋 總供應(yīng)量多出總需求量 3 第3個(gè)產(chǎn)地剩余 1 第5個(gè)產(chǎn)地剩余 2 此問題的另外的解如下 起 至 銷點(diǎn) 發(fā)點(diǎn) 1 2 3 1 2 0 0 2 3 0 0 3 0 2 0 4 0 3 1 5 0 0 0 6 0 0 2 7 0 0 3 此運(yùn)輸問題的成本或收益為 9 665 注釋 總供應(yīng)量多出總需求量 3 第3個(gè)產(chǎn)地剩余 1 第5個(gè)產(chǎn)地剩余 2 此問題的另外的解如下 起 至 銷點(diǎn) 發(fā)點(diǎn) 1 2 3 1 2 0 0 2 3 0 0 3 0 1 1 4 0 4 0 5 0 0 0 703 6 0 0 2 7 0 0 3 此運(yùn)輸問題的成本或收益為 9 665 注釋 總供應(yīng)量多出總需求量 3 第3個(gè)產(chǎn)地剩余 1 第5個(gè)產(chǎn)地剩余 2 4 解 表 7 8 甲 乙 A B C D 甲 0 100 150 200 180 240 1 600 乙 80 0 80 210 60 170 1 700 A 150 80 0 60 110 80 1 100 B 200 210 70 0 140 50 1 100 C 180 60 110 130 0 90 1 100 D 240 170 90 50 85 0 1 100 1 100 1 100 1 400 1 300 1 600 1 200 最優(yōu)解如下 起 至 銷點(diǎn) 發(fā)點(diǎn) 1 2 3 4 5 6 1 1 100 0 300 200 0 0 2 0 1 100 0 0 600 0 3 0 0 1 100 0 0 0 4 0 0 0 1 100 0 0 5 0 0 0 0 1 000 100 6 0 0 0 0 0 1 100 此運(yùn)輸問題的成本或收益為130 000 5 解 建立的運(yùn)輸模型如下 min f 54x11 49x12 52x13 64x14 57x21 73x22 69x23 65x24 s t x11 x12 x13 x14 1 100 x21 x22 x23 x24 1 000 x11 x12 x13 x14 x21 x22 x23 x24 0 704 1 2 3 4 A 54 49 52 64 1 100 B 57 73 69 61 1 000 500 300 550 650 最優(yōu)解如下 起 至 銷點(diǎn) 發(fā)點(diǎn) 1 2 3 4 1 250 300 550 0 2 250 0 0 650 此運(yùn)輸問題的成本或收益為 110 700 注釋 總供應(yīng)量多出總需求量 100 第2個(gè)產(chǎn)地剩余 100 6 解 1 最小元素法的初始解如表7 9所示 表 7 9 1 2 3 產(chǎn)量 8 7 4 甲 15 0 3 5 9 乙 25 15 5 0 0 0 0 丙 10 0 銷量 20 10 0 10 0 20 5 0 2 最優(yōu)解如下 起 至 銷點(diǎn) 發(fā)點(diǎn) 1 2 3 1 0 0 15 2 20 5 0 15 10105 10 705 此運(yùn)輸問題的成本或收益為 145 注釋 總需求量多出總供應(yīng)量 10 第2個(gè)銷地未被滿足 缺少 5 第3個(gè)銷地未被滿足 缺少 5 3 該運(yùn)輸問題只有一個(gè)最優(yōu)解 因?yàn)槠錂z驗(yàn)數(shù)均不為零 4 最優(yōu)解如下 起 至 銷點(diǎn) 發(fā)點(diǎn) 1 2 3 1 0 0 15 2 25 0 0 此運(yùn)輸問題的成本或收益為 135 注釋 總需求量多出總供應(yīng)量 20 第1個(gè)銷地未被滿足 缺少 5 第2個(gè)銷地未被滿足 缺少 10 第3個(gè)銷地未被滿足 缺少 5 706 第 8 章 整 數(shù) 規(guī) 劃 1 解 max z 5x1 8x2 s t x1 x2 6 5x1 9x2 45 x1 x2 0 且為整數(shù) 目標(biāo)函數(shù)最優(yōu)解為 12 0 5 40 xxz max z 3x1 2x2 s t 2x1 3x2 14 2x1 x2 9 x1 x2 0 且x1為整數(shù) 目標(biāo)函數(shù)最優(yōu)解為 12 3 2 666 7 14 3334xxz max z 7x1 9x2 3x3 s t x1 3x2 x3 7 7x1 x2 3x3 38 x1 x2 x3 0 且x1為整數(shù) x3為0 1變量 目標(biāo)函數(shù)最優(yōu)解為 123 5 3 0 62xxxz 2 解 設(shè)xi為裝到船上的第i種貨物的件數(shù) i 1 2 3 4 5 則該船裝載的貨物取得最大價(jià)值目標(biāo) 函數(shù)的數(shù)學(xué)模型可寫為 max z 5x1 10 x2 15x3 18x4 25x5 s t 20 x1 5x2 10 x3 12x4 25x5 400 000 x1 2x2 3x3 4x4 5x5 50 000 x1 4x4 10 000 0 1x1 0 2x2 0 4x3 0 1x4 0 2x5 750 xi 0 且為整數(shù) i 1 2 3 4 5 目標(biāo)函數(shù)最優(yōu)解為 12345 0 0 0 2500 2500 107 500 xxxxxz 3 解 設(shè)xi為第i項(xiàng)工程 i 1 2 3 4 5 且xi為0 1變量 并規(guī)定 707 1 0 i x 根據(jù)給定條件 使三年后總收入最大的目標(biāo)函數(shù)的數(shù)學(xué)模型為 max z 20 x1 40 x2 20 x3 15x4 30 x5 s t 5x1 4x2 3x3 7x4 8x5 25 x1 7x2 9x3 4x4 6x5 25 8x1 10 x2 2x3 x4 10 x5 25 xi為0 1變量 i 1 2 3 4 5 目標(biāo)函數(shù)最優(yōu)解為 12345 1 1 1 1 0 95xxxxxz 4 解 這是一個(gè)混合整數(shù)規(guī)劃問題 設(shè)x1 x2 x3分別為利用A B C設(shè)備生產(chǎn)的產(chǎn)品的件數(shù) 生產(chǎn)準(zhǔn)備費(fèi)只有在利用該設(shè)備 時(shí)才投入 為了說明固定費(fèi)用的性質(zhì) 設(shè) 1 0 i y 故其目標(biāo)函數(shù)為 min z 100y1 300y2 200y3 7x1 2x2 5x3 為了避免沒有投入生產(chǎn)準(zhǔn)備費(fèi)就使用該設(shè)備生產(chǎn) 必須加以下的約束條件 M為充分大的數(shù) x1 y1M x2 y2M x3 y3M 設(shè)M 1 000 000 該目標(biāo)函數(shù)的數(shù)學(xué)模型為 min z 100y1 300y2 200y3 7x1 2x2 5x3 s t x1 x2 x3 2 000 0 5x1 1 8x2 1 0 x3 2 000 x1 800 x2 1 200 x3 1 400 x1 y1M x2 y2M x3 y3M x1 x2 x3 0 且為整數(shù) y1 y2 y3為0 1變量 當(dāng)?shù)趇項(xiàng)工程被選定時(shí) 當(dāng)?shù)趇項(xiàng)工程沒被選定時(shí) 708 目標(biāo)函數(shù)最優(yōu)解為 1 x 370 2 x 231 3 x 1 399 y1 1 y2 1 y3 1 z 10 647 該目標(biāo)函數(shù)的數(shù)學(xué)模型為 min z 100y1 300y2 200y3 7x1 2x2 5x3 s t x1 x2 x3 2 000 0 5x1 1 8x2 1 0 x3 2 500 x1 800 x2 1 200 x3 1 400 x1 y1M x2 y2M x3 y3M x1 x2 x3 0 且為整數(shù) y1 y2 y3為0 1變量 目標(biāo)函數(shù)最優(yōu)解為 1 x 0 2 x 625 3 x 1 375 y1 0 y2 1 y3 1 z 8 625 該目標(biāo)函數(shù)的數(shù)學(xué)模型為 min z 100y1 300y2 200y3 7x1 2x2 5x3 s t x1 x2 x3 2 000 0 5x1 1 8x2 1 0 x3 2 800 x1 800 x2 1 200 x3 1 400 x1 y1M x2 y2M x3 y3M x1 x2 x3 0 且為整數(shù) y1 y2 y3為0 1變量 目標(biāo)函數(shù)最優(yōu)解為 1 x 0 2 x 1 000 3 x 1 000 y1 0 y2 1 y3 1 z 7 500 該目標(biāo)函數(shù)的數(shù)學(xué)模型為 min z 100y1 300y2 200y3 7x1 2x2 5x3 s t x1 x2 x3 2 000 x1 800 x2 1 200 x3 1 400 x1 y1M x2 y2M x3 y3M 709 x1 x2 x3 0 且為整數(shù) y1 y2 y3為0 1變量 目標(biāo)函數(shù)最優(yōu)解為 1 x 0 2 x 1 200 3 x 800 y1 0 y2 1 y3 1 z 6 900 5 解 設(shè)xij為從Di地運(yùn)往Ri地的運(yùn)輸量 i 1 2 3 4 j 1 2 3分別代表從北京 上海 廣州 武漢運(yùn)往華北 華中 華南的貨物件數(shù) 并規(guī)定 1 0 i y 該目標(biāo)函數(shù)的數(shù)學(xué)模型為 min z 45 000y1 50 000y2 70 000y3 40 000y4 200 x11 400 x12 500 x13 300 x21 250 x22 400 x23 600 x31 350 x32 300 x33 350 x41 150 x42 350 x43 s t x11 x21 x31 x41 500 x12 x22 x32 x42 800 x13 x23 x33 x43 700 x11 x12 x13 1 000y1 x21 x22 x23 1 000y2 x31 x32 x33 1 000y3 x41 x42 x43 1 000y4 y2 y4 y1 y2 y3 y4 2 y3 y4 1 xij 0 且為整數(shù) yi為0 1變量 i 1 2 3 4 目標(biāo)函數(shù)最優(yōu)解為 111213212223313233 4142431234 500 0 500 0 0 0 0 0 0 0 800 200 1 0 0 1 625 000 xxxxxxxxx xxxyyyyz 也就是說在北京和武漢建庫房 北京向華北和華南各發(fā)貨500件 武漢向華中發(fā)貨800件 向華南發(fā)貨200件就能滿足要求 即這就是最優(yōu)解 6 解 引入0 1變量xij 并令xij 1 當(dāng)指派第i人去完成第j項(xiàng)工作時(shí) 0 當(dāng)不指派第i人去完成第j項(xiàng)工作時(shí) 為使總消耗時(shí)間最少的目標(biāo)函數(shù)的數(shù)學(xué)模型為 min z 20 x11 19x12 20 x13 28x14 18x21 24x22 27x23 20 x24 26x31 16x32 15x33 18x34 17x41 20 x42 24x43 19x44 s t x11 x12 x13 x14 1 當(dāng)i地被選設(shè)庫房 當(dāng)i地沒被選設(shè)庫房 710 x21 x22 x23 x24 1 x31 x32 x33 x34 1 x41 x42 x43 x44 1 x11 x21 x31 x41 1 x12 x22 x32 x42 1 x13 x23 x33 x43 1 x14 x24 x34 x44 1 xij為0 1變量 i 1 2 3 4 j 1 2 3 4 目標(biāo)函數(shù)最優(yōu)解為 1112131421222324313233344142 0 1 0 0 1 0 0 0 0 0 1 0 0 0 xxxxxxxxxxxxxx 4344 0 1 71xxz 或 1112131421222324313233344142 0 1 0 0 0 0 0 1 0 0 1 0 1 0 xxxxxxxxxxxxxx 4344 0 0 71xxz 即安排甲做B項(xiàng)工作 乙做A項(xiàng)工作 丙做C項(xiàng)工作 丁做D項(xiàng)工作 或者是安排甲做 B項(xiàng)工作 乙做D項(xiàng)工作 丙做C項(xiàng)工作 丁做A項(xiàng)工作 最少時(shí)間為71分鐘 也可用管理 運(yùn)籌學(xué)軟件的整數(shù)規(guī)劃中的指派問題子程序直接求得 為使總收益最大的目標(biāo)函數(shù)的數(shù)學(xué)模型是 將 中的目標(biāo)函數(shù)改為求最大值即可 目標(biāo)函數(shù)最優(yōu)解為 1112131421222324313233344142 0 0 0 1 0 1 0 0 1 0 0 0 0 0 xxxxxxxxxxxxxx 4344 1 0 102xxz 即安排甲做D項(xiàng)工作 乙做C項(xiàng)工作 丙做A項(xiàng)工作 丁做B項(xiàng)工作 最大收益為102 由于工作多人少 我們假設(shè)有一個(gè)工人戊 他做各項(xiàng)工作所需的時(shí)間均為0 該問題就 變?yōu)榘才?個(gè)人去做5項(xiàng)不同的工作的問題了 其目標(biāo)函數(shù)的數(shù)學(xué)模型為 min z 20 x11 19x12 20 x13 28x14 17x15 18x21 24x22 27x23 20 x24 20 x25 26x31 16x32 15x33 18x34 15x35 17x41 20 x42 24x43 19x44 16x45 s t x11 x12 x13 x14 x15 1 x21 x22 x23 x24 x25 1 x31 x32 x33 x34 x35 1 x41 x42 x43 x44 x45 1 x51 x52 x53 x54 x55 1 x11 x21 x31 x41 x51 1 x12 x22 x32 x42 x52 1 x13 x23 x33 x43 x53 1 x14 x24 x34 x44 x54 1 711 x15 x25 x35 x45 x55 1 xij為0 1變量 i 1 2 3 4 5 j 1 2 3 4 5 目標(biāo)函數(shù)最優(yōu)解為 1112131415212223242531323334 0 1 0 0 0 1 0 0 0 0 0 0 1 0 xxxxxxxxxxxxxx 354142434445 0 0 0 0 0 1 68xxxxxxz 即安排甲做B項(xiàng)工作 乙做A項(xiàng)工作 丙做C項(xiàng)工作 丁做E項(xiàng)工作 最少時(shí)間為68分鐘 該問題為人多任務(wù)少的問題 其目標(biāo)函數(shù)的數(shù)學(xué)模型為 min z 20 x11 19x12 20 x13 28x14 18x21 24x22 27x2