運(yùn)籌學(xué)練習(xí)題.pdf

第一章第一章 線性規(guī)劃線性規(guī)劃 1 已知我系有三種不同體系的建筑應(yīng)予以修建 其耗用資源數(shù)量及可用的資源數(shù)量如下表 問不同體系的建 筑面積各為多少 才能使提供的建筑面積達(dá)到最大 造價(jià) 元 m2 鋼材 kg m2 水泥 kg m2 磚塊 塊 m2 人工 工 日 m2 磚混結(jié)構(gòu)105121102104 5 鋼混結(jié)構(gòu)137301903 0 框架結(jié)構(gòu)122251803 5 資源限量11000 萬元2000 萬 kg15000 萬 kg14700 萬塊400 萬工日 解 設(shè)三種不同體系建筑面積依次為 1 x 2 x 3 x萬 m2 則 123 maxZxxx 123 123 123 1 123 123 10513712211000 1230252000 11019018015000 210147000 4 53 03 5400 0 xxx xxx xxx x xxx x x x 其中 1 x 2 x 3 x為決策變量 2 把下列線性規(guī)劃問題化為標(biāo)準(zhǔn)型 123 min23Zxxx 123 123 123 123 29 324 3236 0 0 xxx xxx xxx xxx 無約束 解 令ZZ 11 xx 333 xxx 3 0 x 3 0 x 則問題轉(zhuǎn)化為 123345 max23300Zxxxxxx 12334 12335 1233 123345 29 3224 32336 0 xxxxx xxxxx xxxx xx xxx x 3 3 3 3 求下列求下列 LpLpLpLp 問題的所有基解 基可行解 最優(yōu)解問題的所有基解 基可行解 最優(yōu)解 12 max23Zxx 12 1 2 12 2212 416 515 0 0 xx x x xx 解 化為標(biāo)準(zhǔn)型 12345 max23000Zxxxxx 123 14 25 2212 416 515 0 1 2 5 j xxx xx xx xj 系數(shù)矩陣 22100 40010 05001 A 1 取 1123 221 400 050 Bp pp 則 145 01 10 01 Npp 1123 T B Xx x x 則 145 T N Xx x 當(dāng) 145 0 0 TT N Xx x 時(shí) 1 1 1 112 3 221124 400163 050152 B x XB bx x 1 43200 T X 2 取 2124 220 401 050 Bp pp 則 235 10 00 01 Npp 2124 T B Xx x x 則 235 T N Xx x 當(dāng) 235 0 0 TT N Xx x 時(shí) 1 1 1 222 4 220123 401163 050154 B x XBbx x 2 33040 T X 3 取 3125 220 400 051 Bp pp 則 334 10 01 00 Npp 3125 T B Xx x x 則 334 T N Xx x 當(dāng) 334 0 0 TT N Xx x 時(shí) 1 1 1 332 5 220124 400162 051155 B x XBbx x 3 42005 T X 4 取 4135 210 400 001 Bp pp 則 424 20 01 50 Npp 4135 T B Xx x x 則 424 T N Xx x 當(dāng) 424 0 0 TT N Xx x 時(shí) 1 1 1 443 5 210124 400164 0011515 B x XBbx x 3 404015 T X 5 取 5145 200 410 001 Bp pp 則 523 21 00 50 Npp 5145 T B Xx x x 則 523 T N Xx x 當(dāng) 523 0 0 TT N Xx x 時(shí) 1 1 1 554 5 200126 410168 0011515 B x XBbx x 5 6 0 0 8 15 T X 6 取 6234 210 001 500 Bppp 則 615 20 40 01 Np p 6234 T B Xx x x 則 615 T N Xx x 當(dāng) 615 0 0 TT N Xx x 時(shí) 1 2 1 663 4 210123 001166 5001516 B x XBbx x 6 036160 T X 7 取 7245 200 010 501 Bppp 則 713 21 40 00 Np p 7245 T B Xx x x 則 713 T N Xx x 當(dāng) 713 0 0 TT N Xx x 時(shí) 1 2 1 774 5 200126 0101616 5011515 B x XBbx x 7 0 6 0 16 15 T X 8 取 8345 100 010 001 Bppp 則 812 22 40 05 Np p 8345 T B Xx x x 則 812 T N Xx x 當(dāng) 812 0 0 TT N Xx x 時(shí) 3 1 884 5 12 16 15 B x XBbIbx x 8 00121615 T X 基 基解 是否可行解目標(biāo)函數(shù)值 1 x 2 x 3 x 4 x 5 x 1 p 2 p 3 p43 200否17 1 p 2 p 4 p33040是15 1 p 2 p 5 p42005是14 1 p 3 p 5 p404015是8 1 p 4 p 5 p600 815否12 2 p 3 p 4 p036160是9 2 p 4 p 5 p06016 15否18 3 p 4 p 5 p00121615是0 4 4 4 4 求下列求下列 LpLpLpLp 問題的所有基解 基可行解 最優(yōu)解問題的所有基解 基可行解 最優(yōu)解 1234 min5232Zxxxx 1234 1234 1234 2347 2223 0 xxxx xxxx x x x x 解 系數(shù)矩陣 1234 2212 A 1 取 112 12 22 Bp p 則 134 34 12 Npp 112 T B Xx x 則 134 T N Xx x 當(dāng) 134 0 0 TT N Xx x 時(shí) 1 11 11 2 4 127 11 223 2 B x XB b x 1 11 400 2 T X 2 取 213 13 21 Bp p 則 224 24 22 Npp 213 T B Xx x 則 224 T N Xx x 當(dāng) 224 0 0 TT N Xx x 時(shí) 1 11 22 3 1372 5 21311 5 B x XBb x 2 2 5011 50 T X 3 取 314 14 22 Bp p 則 323 23 22 Npp 314 T B Xx x 則 323 T N Xx x 當(dāng) 323 0 0 TT N Xx x 時(shí) 1 11 33 4 1471 3 22311 6 B x XBb x 3 1 30011 6 T X 4 取 423 23 21 Bpp 則 414 14 22 Np p 423 T B Xx x 則 414 T N Xx x 當(dāng) 414 0 0 TT N Xx x 時(shí) 1 21 44 3 2371 2 2132 B x XBb x 3 01 220 T X 5 取 524 24 22 Bpp 則 513 13 21 Np p 524 T B Xx x 則 513 T N Xx x 當(dāng) 513 0 0 TT N Xx x 時(shí) 1 21 55 4 2471 2 2032 B x XBb x 5 01 202 T X 6 取 634 34 12 Bpp 則 612 12 22 Np p 634 T B Xx x 則 612 T N Xx x 當(dāng) 612 0 0 TT N Xx x 時(shí) 1 31 66 4 3471 1231 B x XBb x 6 0010 T X 基 基解 是否可行解目標(biāo)函數(shù)值 1 x 2 x 3 x 4 x 1 p 2 p 411 200否 31 1 p 3 p2 5011 50是43 5 1 p 4 p 1 30011 6否2 2 p 3 p01 220是5 2 p 4 p0 1 202否5 3 p 4 p0011是5 此時(shí) Lp 問題的最優(yōu)值 Z 5 圖解法 圖解法 1 用圖解法求解下列線性規(guī)劃問題 12 max23Zxx 12 1 2 12 2212 416 515 0 0 xx x x xx 24 8 2 4 6 8 10 10 12 2212xx 1 416x 2 515x 21 2 33 Z xx 6 1 繪制可行區(qū)域圖形 2 將等值線 21 2 33 Z xx 沿法線方向向右上方平移到離原點(diǎn)最遠(yuǎn)且在可行域內(nèi)的點(diǎn) 12 2 2212 515 xx x 1 2 3 3 x x 最優(yōu)解 3 3 TX 最優(yōu)值 Z 15 2 用圖解法求解下列線性規(guī)劃問題 12 max23Zxx 12 12 12 466 424 0 0 xx xx xx 12 1 2 12 424xx P Q 所以 為無界解 2 若求 12 min23Zxx 則等值線 21 2 33 Z xx 與可行域交于一條線段 PQ 所以有無窮多最優(yōu)解 最優(yōu)值3Z 3 用圖解法求解下列線性規(guī)劃問題 12 maxZxx 12 12 12 24 2 0 0 xx xx xx 21 2 33 Z xx 12 466xx 24 8 2 4 6 8 10 10 12 2xx 6 存在無界解 4 用圖解法求解下列線性規(guī)劃問題 12 max32Zxx 12 12 12 22 3412 0 0 xx xx xx 解 12 1 3 12 3412xx 12 22xx 2 4 34 所以 無可行解 單純形法單純形法 1 用單純形法求解下列線性規(guī)劃問題 12345 max23000Zxxxxx 12 24xx 21 xxZ 21 3 22 Z xx 123 14 25 2212 416 515 0 1 2 5 j xxx xx xx xj 解 0345 100 010 001 BP P P 0 345 T B Xx x x 0 0 0 0 B C 令 0 12 0 0 TT N Xx x 則 0 B X 1 B b Ib 12 16 15 T 0 0Z 單純形表為 j c23000 B C B Xb 1 x 2 x 3 x 4 x 5 x 0 3 x122210012 2 0 0 4 x 5 x 16 15 4 0 0 5 0 0 1 0 0 1 15 5 j 23000 1 0Z 0 3 x6 2 010 2 56 2 0 3 4 x 2 x 16 3 4 0 0 1 0 0 1 0 0 1 5 16 4 j 2000 3 5 2 9Z 2 1 x3101 20 1 5 0 3 4 x 2 x 4 3 0 0 0 1 2 0 1 0 4 5 1 5 j 00 10 1 5 15Z 最優(yōu)解為 3 3 0 4 0 T X 最優(yōu)值 15Z 大大 MMMM 法 單純形法的擴(kuò)展法 單純形法的擴(kuò)展 2 單純形法求解線性規(guī)劃問題 13 max3Zxx 123 123 23 123 4 21 39 0 xxx xxx xx x xx 化為標(biāo)準(zhǔn)型 1345 max300Zxxxx 1234 1235 23 4 21 39 0 1 2 5 j xxxx xxxx xx xj 11110 21101 03100 A 加入人工變量得 134567 max300ZxxxxMxMx 1234 12356 237 4 21 39 0 1 2 7 j xxxx xxxxx xxx xj j c 30100M M B C B Xb 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 4 x411110004 M M 6 x 7 x 1 9 2 0 1 3 1 1 0 0 1 0 1 0 0 1 1 3 j 2M 34M10 M 00 0 10MZ 0 4 x3302 11 101 0 M 2 x 7 x 1 6 2 6 1 0 1 4 0 0 1 3 1 3 0 1 1 j 6M 304M 103M 4M0 1 6MZ 0 4 x0000 1 1 2 1 2 1 2 0 3 2 x 1 x 3 1 0 1 1 0 1 3 2 3 0 0 0 1 2 0 1 2 1 3 1 6 9 3 2 j 00303 2 M 3 2 M 1 2 2 3Z 0 4 x0000 1 1 2 1 2 1 2 0 2 x5 2 1 210 0 1 4 1 41 4 1 3 x3 23 201 03 4 3 41 4 j 3 2000 3 4 M 3 4 M 1 4 3 2Z 兩階段法 單純形法的擴(kuò)展兩階段法 單純形法的擴(kuò)展 3 單純形法求解線性規(guī)劃問題 13 max3Zxx 123 123 23 123 4 21 39 0 xxx xxx xx x xx 解 第一階段 67 maxxx 1234 12356 237 4 21 39 0 1 2 7 j xxxx xxxxx xxx xj j c00000 1 1 B C B Xb 1 x 2 x 3 x 4 x 5 x 6 x 7 x 0 4 x411110004 1 6 x1 2 1 10 1101 1 7 x903100013 j 2400 1 00 0 10 0 4 x3302 11 101 0 2 x1 21 10 110 1 7 x6 6 0403 311 j 60403 40 1 6 0 4 x00001 1 21 2 1 2 0 2 x3011 30001 39 0 1 x110 2 3 01 2 1 21 63 2 j 00000 1 1 2 0 最優(yōu)解為 1 3 0 0 0 0 0 T X 最優(yōu)值 0 注 若0 說明原式存在可行解 0 說明原式不存在可行解 第二階段 將第一階段的最終表中的人工變量 6 x 7 x除去 再從第一階段最終表出發(fā) 繼續(xù)用單純形法計(jì)算 此時(shí) 目標(biāo)函數(shù) 1345 max300Zxxxx j c 30100 B C B Xb 1 x 2 x 3 x 4 x 5 x 0 4 x0000 1 1 2 0 3 2 x 1 x 3 1 0 1 1 0 1 3 2 3 0 0 0 1 2 9 3 2 j 00303 2 1 0Z 0 4 x0000 1 1 2 0 2 x5 2 1 210 0 1 4 1 3 x3 23 201 03 4 j 3 2000 3 4 3 2Z 最優(yōu)解為 0 0 3 2 0 0 T X 最優(yōu)值 3 2Z 4 已知某求極大化線性規(guī)劃問題用單純形法求解時(shí)的初始單純形表及最終單純形表如下表所示 求表中各括 弧內(nèi)未知數(shù)的值 j c322000 B C B Xb 1 x 2 x 3 x 4 x 5 x 6 x 0 4 x b 111100 0 5 x15 a 12010 0 6 x202 c 1001 j 3 d 2000 0 4 x5 400 e h 1 4 1 4 3 1 x25 410 f 03 4 i 2 2 x5 201 g 0 j 1 2 j 0 k m 0 5 4 n 解 1h 2d 0k 1 2 j 11 41 410 03 41 01 21 220 ia 2a 1 4 i 11 41 410 03 41 410 01 21 21c 3c 11 41 45 4 03 41 41525 4 01 21 2205 2 b 10b 11 41 41 03 41 42 01 21 21 e f g 1 4 e 5 4 f 1 2 g 3 4 m 1 4 n 第二章第二章 對(duì)偶問題及靈敏度分析對(duì)偶問題及靈敏度分析 1 寫出下列問題的對(duì)偶問題 1 123 max743Zxxx 123 123 23 123 42624 36415 5330 0 0 xxx xxx xx xxx 無約束 其對(duì)偶問題 3 min241530 12 y y y 12 123 123 123 437 2654 6433 0 0 yy yyy yyy yyy 無約束 2 1234 min235Zxxxx 1234 124 234 1234 35 224 6 0 0 xxxx xxx xxx xxxx 無約束 其對(duì)偶問題 3 max546 12 Z y y y 12 123 13 123 123 22 23 35 1 0 0 yy yyy yy yyy yyy 無約束 互補(bǔ)松弛性 互補(bǔ)松弛性 1 已知 LP 問題 12345 min23523xxxxx 12345 12345 234 233 01 2 5 j xxxxx xxxxx xj 已知其對(duì)偶問題的最優(yōu)解為 1 4 5 y 2 3 5 y 5Z 試用對(duì)偶理論找出原問題的最優(yōu)解 解 原問題的對(duì)偶問題為 12 max43Zyy 12 12 12 12 12 12 221 32 2353 24 335 0 0 yy yy yy yy yy yy 將 1 y 2 y的值代入約束條件 得 2 3 4 為嚴(yán)格不等式 由互補(bǔ)松弛性得 234 0 xxx 又 1 4 0 5 y 2 3 0 5 y 由互補(bǔ)松弛性得 15 15 34 23 xx xx 解得 1 5 1 1 x x 故原問題的最優(yōu)解為 1 0 0 0 1 T X 最優(yōu)值 5Z 2 已知 LP 問題 1234 max24Zxxxx 124 12 234 123 38 1 26 2 6 3 9 4 01 2 3 4 j xxx xx xxx xxx xj 要求 1 寫出其對(duì)偶問題 2 已知其原問題的最優(yōu)解為 2 2 4 0 T X 試根據(jù)對(duì)偶理論直接 求出對(duì)偶問題的最優(yōu)解 解 原問題的對(duì)偶問題為 1234 min8669yyyy 124 1234 34 13 22 34 1 1 01 2 3 4 j yyy yyyy yy yy yj 將原問題的最優(yōu)解代入約束條件 得 4 為嚴(yán)格不等式 由互補(bǔ)松弛性得 4 0y 又 1 20 x 2 20 x 3 40 x 由互補(bǔ)松弛性得 12 123 3 22 34 1 yy yyy y 解得 1 2 3 4 5 3 5 1 y y y 故對(duì)偶問題的最優(yōu)解為 4 3 1 0 5 5 Y 最優(yōu)值 16 對(duì)偶單純形法對(duì)偶單純形法 1 用對(duì)偶單純形法求解下列線性規(guī)劃問題 123 min121615xxx 12 13 123 242 253 0 0 0 xx xx xxx 解 令 則 12345 max12161500 xxxxx 124 135 242 253 0 1 2 5 j xxx xxx xj 124 135 242 253 0 1 2 5 j xxx xxx xj 單純形表 j c 12 16 1500 B C B Xb 1 x 2 x 3 x 4 x 5 x 0 4 x 2 2 4010 0 5 x 3 20 5 01 j 12 16 1500 0 4 x 2 2 4010 15 3 x3 52 5010 1 5 j 6 1600 3 12 1 x1120 1 20 15 3 x1 50 4 511 5 1 5 j 0 40 3 3 2 已知線性規(guī)劃 12 min64Zxx 12 12 2 12 2 21 3 0 0 xx xx x xx 1 寫出對(duì)偶問題并求解 2 直接寫出原問題的最優(yōu)解 解 1 寫出對(duì)偶問題并求解 123 max23yyy 12345 max2300yyyyy 12 123 123 6 24 0 0 yy yyy yyy 0 124 1235 12345 6 24 0 yyy yyyy y yyyy j c2 1 300 B C B Yb 1 y 2 y 3 y 4 y 5 y 0 4 y6 1 10106 0 5 y4 12101 j 2 1 300 2 1 y611110 0 5 y1003111 j 0 3 5 20 最優(yōu)解為 6 0 0 0 10 Y 2 原問題的最優(yōu)解為 2 0 TX 靈敏度分析靈敏度分析 引例 引例 資源限量 設(shè)備 A h 2212h 設(shè)備 B h 4016h 設(shè)備 C h 0515h 該工廠每生產(chǎn)一件產(chǎn)品 可獲利 2 元 每生產(chǎn)一件產(chǎn)品 可獲利 3 元 問應(yīng)如何安排計(jì)劃使該工廠獲利最 多 解 設(shè) 1 x 2 x分別為 兩產(chǎn)品的數(shù)量 則 12 max23Zxx 12 1 2 12 2212 416 515 0 xx x x x x 化為標(biāo)準(zhǔn)型 1245 max2300Zxxxx 124 15 26 2212 416 515 0 1 2 6 j xxx xx xx xj j c23000 B C B Xb 1 x 2 x 3 x 4 x 5 x 0 3 x12221006 0 4 x1640010 0 5 x150 5 0013 j 23000 0 3 x6 2 010 2 53 0 4 x16400104 3 2 x301001 5 j 2000 3 5 2 1 x3101 20 1 5 0 4 x400 214 5 3 2 x301001 5 j 00 10 1 5 一 一 分析分析 j C變化變化 1 若產(chǎn)品 的利潤增至 3 元 件 產(chǎn)品 的利潤降至 2 元 件 此公司最優(yōu)生產(chǎn)計(jì)劃如何變化 j c32000 B C B Xb 1 x 2 x 3 x 4 x 5 x 3 1 x3101 20 1 5 0 4 x400 21 4 5 5 2 2 x301001 515 j 00 3 201 5 0 3 x41001 4016 0 5 x500 5 2 5 4 14 2 2 x2011 2 1 40 j 00 3 21 20 0 3 x3101 20 1 5 0 4 x400 214 5 2 2 x301001 5 j 0000 2 5 即 此時(shí)生產(chǎn) 0 件產(chǎn)品 生產(chǎn) 3 件產(chǎn)品 2 若產(chǎn)品 的利潤不變 則產(chǎn)品 的利潤在什么范圍內(nèi)變化時(shí) 該公司的最優(yōu)生產(chǎn)計(jì)劃將不發(fā)生變化 解 設(shè)產(chǎn)品 的利潤為 3 元 反映到最終單純形表中得 j c23 000 B C B Xb 1 x 2 x 3 x 4 x 5 x 2 1 x3101 20 1 5 0 4 x400 214 5 3 2 x301001 5 j 00 10 1 5 5 為使表中的解仍為最優(yōu)解 應(yīng)有 1 5 50 解得 1 即產(chǎn)品 的利潤的變化范圍應(yīng)滿足 3 2 二 二 分析分析 i b變化變化 原問題資源限量設(shè)備 A 12 設(shè)備 B 16 設(shè)備 C 15 1 若設(shè)備 B 和設(shè)備 C 的每天能力不變 而設(shè)備 A 每天的能力增加到 16 分析公司最優(yōu)生產(chǎn)計(jì)劃的變化 解 12 16 15 b 4 0 0 b 則在對(duì)應(yīng)最優(yōu)單純形表中 1 1 2024 4100 0050 bBb 1 201 54 214 50 001 50 2 8 0 得單純形表 j c23000 B C B Xb 1 x 2 x 3 x 4 x 5 x 2 1 x5101 20 1 5 0 4 x 400 2 14 5 3 2 x301001 5 j 00 10 1 5 2 1 x41001 40 0 3 x2001 1 2 2 5 3 2 x301001 5 j 000 1 2 3 5 所以最優(yōu)生產(chǎn)計(jì)劃變?yōu)?此時(shí)生產(chǎn) 4 件產(chǎn)品 生產(chǎn) 3 件產(chǎn)品 2 若設(shè)備 A 和設(shè)備 B 每天可用生產(chǎn)能力不變 則設(shè)備 C 的可用生產(chǎn)能力在什么范圍內(nèi)變化時(shí) 問題的最優(yōu) 基不變 解 設(shè)設(shè)備 C 每天可用生產(chǎn)能力為 15 因有 1 1 2020 4100 005 bBb 1 201 50 214 50 001 5 5 4 5 5 將其反映到最終單純形表中 其 b 列數(shù)字為 3 5 44 5 3 5 b 當(dāng)0b 時(shí) 問題最優(yōu)基不變 解得 515 由此 設(shè)備 C 的生產(chǎn)能力應(yīng)在 10 25 之間 三 三 增加一個(gè)變量增加一個(gè)變量 j x的分析的分析 例 該公司又推出一種新產(chǎn)品 生產(chǎn)一件產(chǎn)品 所需設(shè)備 A B C 分別為 2 4 5 該產(chǎn)品的預(yù)期盈利為 4 元 試分析該種產(chǎn)品是否值得投產(chǎn) 如果投產(chǎn) 最優(yōu)解將如何變化 解 設(shè)該公司生產(chǎn)產(chǎn)品 6 x件 則有 6 4c 6 2 4 5 p 1 66 1 201 520 214 544 001 551 pB p 6 0 42 0 3410 1 值得投產(chǎn) j c230004 B C B Xb 1 x 2 x 3 x 4 x 5 x 6 x 2 1 x3101 20 1 50 0 4 x400 214 5 4 1 3 2 x301001 513 j 00 10 1 5 1 2 1 x3101 20 1 50 4 6 x100 1 21 41 51 3 2 x2011 2 1 400 j 00 1 2 1 4 2 50 故新的解為 3 2 0 0 0 1 T X 即生產(chǎn)產(chǎn)品 3 件 產(chǎn)品 2 件 產(chǎn)品 1 件 可獲得的總利潤 16Z 四 四 增加一個(gè)約束條件的分析增加一個(gè)約束條件的分析 例 2 若生產(chǎn)產(chǎn)品 要求增加功能 需增設(shè)設(shè)備 D 且已知生產(chǎn)產(chǎn)品 需用設(shè)備 D3 生產(chǎn)產(chǎn)品 需用設(shè) 備 D2 設(shè)備的生產(chǎn)能力 資源限量 為 14 試分析最優(yōu)解的變化 解 12 3214xx 把 1 3x 2 3x 代入得3 3 2 2 15 不滿足約束條件 126 3214xxx j c230000 B C B Xb 1 x 2 x 3 x 4 x 5 x 6 x 2 1 x3101 20 1 50 0 4 x400 214 50 3 2 x301001 50 0 6 x14320001 j 00 10 1 50 通過線性變換 構(gòu)造單位矩陣 即 4 4 3 1 2 3 j c230000 B C B Xb 1 x 2 x 3 x 6 x 5 x 6 x 2 1 x3101 20 1 50 0 4 x400 214 50 3 2 x301001 50 0 6 x 100 3 201 51 j 00 10 1 50 2 1 x8 31000 2 151 3 0 4 x16 300018 15 4 3 3 2 x301001 50 0 3 x2 30010 2 15 2 3 j 0000 1 3 2 3 增設(shè)設(shè)備 D 后 問題的最優(yōu)解 8 3 3 2 3 16 3 0 0 T X 43 3Z 即生產(chǎn)產(chǎn)品 3 件 產(chǎn)品 3 件能使利潤最大 最大利潤為 15 第三章 運(yùn)輸問題 1 設(shè)有 1 A 2 A 3 A三個(gè)產(chǎn)地生產(chǎn)某種物質(zhì) 其產(chǎn)量分別為 7t 4t 9t 1 B 2 B 3 B 4 B四個(gè)銷地需要該 種物質(zhì) 銷量分別為 3t 6t 5t 6t 又知各產(chǎn)銷地之間的單位運(yùn)價(jià)見下表 試確定總運(yùn)費(fèi)最少的調(diào)運(yùn)方案 表表 3 13 13 13 1單位運(yùn)價(jià)表單位運(yùn)價(jià)表單位 元單位 元 t t t t 銷地 產(chǎn)地 1 B 2 B 3 B 4 B 1 A 311210 2 A 1938 3 A 74105 問題 用最小元素法求解上述運(yùn)輸問題 解 銷地 產(chǎn)地 1 B 2 B 3 B 4 B 產(chǎn)量 1 A437 3 2 A314 1 3 A639 3 銷量 365 4 6 3 所以初始解為 13 x 4 14 x 3 21 x 3 23 x 1 32 x 6 34 x 3 2 用伏格爾法求解上述運(yùn)輸問題 銷地 產(chǎn)地 1 B 2 B 3 B 4 B 產(chǎn)量 行罰數(shù) 1 A527 2 000 2 A314 1 1116 3 A639 3 12 銷量 3656 3 2 列 罰 數(shù) 2 13 21 12 12 7 19 4 33 2 10 10 8 5 11 311310 1928 74105 所以初始解為 13 x 5 14 x 2 21 x 3 24 x 1 32 x 6 34 x 3 則 11 5 32 103 1 1 86 43 585 mn ijij ij zc x 3 某公司有三個(gè)水泥產(chǎn)地 分別向四個(gè)建筑工地運(yùn)送水泥 已知各產(chǎn)地的產(chǎn)量分別為 1 16A 萬噸 2 10A 萬噸 3 22A 萬噸 四個(gè)建筑工地的銷量分別為 1 8B 萬噸 2 14B 萬噸 3 12B 萬噸 4 14B 萬噸 產(chǎn)銷平衡表如下表所示 用最小元素法求得的總運(yùn)費(fèi)最小的初始運(yùn)輸方案為 銷地 產(chǎn)地 1 B 2 B 3 B 4 B 產(chǎn)量 1 A106 16 2 A82 10 3 A148 22 銷量 8141214 48 即方案最優(yōu)解為 13 x 10 14 x 6 21 x 8 23 x 2 32 x 14 34 x 8 其余非 基變量取值為 0 求各決策變量對(duì)應(yīng)的檢驗(yàn)數(shù) 并判別此解是否為最優(yōu)解 若不是最優(yōu)解 進(jìn)行解的調(diào)整 調(diào)整一次 求此 運(yùn)輸問題的另一組基本可行解 答案 用對(duì)偶變量法求各非基變量的檢驗(yàn)數(shù) 并判別是否最優(yōu)解 若不是最優(yōu)解 進(jìn)解的調(diào)整 此運(yùn)輸問題初始基本可行解為 13 x 10 14 x 6 21 x 8 23 x 2 32 x 14 34 x 8 又 ijijiij cuv 對(duì)所有基變量 檢驗(yàn)數(shù) 0 13 14 21 23 32 34 4 11 2 3 5 6 uv uv uv uv uv uv 令 1 0u 得 3 4v 4 11v 2 1u 1 3v 3 5u 2 10v 非基變量檢驗(yàn)數(shù) 111111 cuv 4031 121212 cuv 120 102 222222 10 1 101cuv 242424 cuv 9 1 111 2 10 5 4 4 3 11 9 12 8611 313131 8 5 310cuv 333333 11 5 412cuv 或者 銷地 產(chǎn)地 1 B 2 B 3 B 4 B 產(chǎn)量 i u 1 A12 16 1 u 0 2 A1 1 10 2 u 1 3 A1012 22 3 u 5 銷量 8141214 48 j v 1 v 3 2 v 10 3 v 4 4 v 11 非基變量 24 x的檢驗(yàn)數(shù) 24 10 不是最優(yōu)解 或者用閉合回路法求解 酌情給分 2 求運(yùn)輸問題的另一組基本可行解 24 1 24 x為換入變量 對(duì)應(yīng)的閉回路如圖 對(duì)閉回路上各點(diǎn)按逆時(shí)針順序依次編號(hào) 其偶數(shù)點(diǎn)位于格 A1 B4 和 A2 B3 由于min 14 x 23 x min 6 2 2 故應(yīng)作如下調(diào)整 24 x 0 2 14 x 6 4 13 x 10 12 23 x 2 0 得到新的基可行解是 13 x 12 14 x 4 21 x 8 24 x 2 32 x 14 34 x 8 整數(shù)規(guī)劃整數(shù)規(guī)劃 1 某公司擬于東 西 南三區(qū)建立門市部 有 7 個(gè)位置 1 2 7 i A i 可供選擇 規(guī)定 1 在東區(qū) 由 1 A 2 A 3 A三點(diǎn)中至多選擇 2 個(gè) 2 在南區(qū) 由 4 A 5 A兩點(diǎn)中至少選擇 1 個(gè) 3 在西區(qū) 由 6 A 7 A兩點(diǎn)中至少選擇 1 個(gè) 如選用 i A點(diǎn) 設(shè)備投資估計(jì)為 i b元 每年可獲利估計(jì)為 i c元 但設(shè)備投資總額不能超過 B 元 問應(yīng)選擇 哪幾個(gè)點(diǎn)可使年利潤最大 試建立數(shù)學(xué)模型 解 引入 0 1 變量 i x 2 10 5 44 3 11 9 12 8611 1 1 2 7 0 i ij i A xi A 選 不選 則 7 1 max ii i zxc 7 1 123 45 67 2 1 1 01 1 2 7 ii i i x bB xxx xx xx xi 或 2 2 2 2 割平面法割平面法 對(duì)整數(shù)規(guī)劃問題 12 maxZxx 12 12 12 12 26 4520 0 0 xx xx xx x x 為整數(shù) 不考慮整數(shù)條件 加入松弛變量得 1234 max00Zxxxx 123 124 1234 26 4520 0 0 0 0 xxx xxx xxxx 求得的最終單純形表為 j c1100 B C B Xb 1 x 2 x 3 x 4 x 1 1 x5 3105 6 1 6 1 2 x8 301 2 31 3 j 00 1 6 1 6 用割平面法求解此整數(shù)規(guī)劃問題 解 由最終單純形表知 134 234 515 663 218 333 xxx xxx 即 1434 2334 255 1 366 211 2 333 xxxx xxxx 34 34 552 663 112 333 xx xx 345 345 554 2 xxx xxx 割平面方程為 34 2xx 所以引入松弛變量 得到新的約束條件 345 2xxx j c11000 B C B Xb 1 x 2 x 3 x 4 x 5 x 1 1 x5 3105 6 1 60 1 2 x8 301 2 31 30 0 5 x 200 1 11 j 00 1 6 1 6 0 1 1 x0100 1 5 6 1 2 x40101 2 3 0 3 x20011 1 j 0000 1 6 此時(shí)最優(yōu)解 1 x 0 2 x 4 3 x 2 4 x 0 5 x 0 指派問題 指派問題 3 公司在各地有 4 項(xiàng)工程 選定了 4 位項(xiàng)目經(jīng)理去分別處理 由于業(yè)務(wù)能力 經(jīng)驗(yàn)和其他情況的不同 4 位項(xiàng) 目經(jīng)理處理這 4 項(xiàng)業(yè)務(wù)的費(fèi)用各不相同 費(fèi)用估計(jì)如下表 應(yīng)當(dāng)怎樣分配這 4 位項(xiàng)目經(jīng)理 才能使 4 項(xiàng)工程都 得到處理 同時(shí)總的費(fèi)用最小 業(yè)務(wù) 費(fèi)用 項(xiàng)目經(jīng)理 1234 A215134 B141415 C9141613 D78119 解 min 2151342 1414151 91416139 781197 ij c 142min 013112 0313 14 0574 0142 01270 02912 0432 0000 ij b 1270 02912 432 0 1270 02912 432 0 21270 0710 021 20 0001 0100 1000 0010 所以 14 1x 22 1x 31 1x 43 1x 即 指派項(xiàng)目經(jīng)理 A 完成第 4 項(xiàng)任務(wù) 指派項(xiàng)目經(jīng)理 B 完成第 2 項(xiàng)任務(wù) 指派項(xiàng)目經(jīng)理 C 完成第 1 項(xiàng)任 務(wù) 指派項(xiàng)目經(jīng)理 D 完成第 3 項(xiàng)任務(wù) 或者 A 4 B 2 C 1 D 3 動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 1 給定一運(yùn)輸網(wǎng)絡(luò) 如圖 兩點(diǎn)之間直線上的數(shù)字表示兩點(diǎn)間距離 試求一條從 A 到 E 的運(yùn)軌路線 使總距 離為最短 解 1 當(dāng)4k 時(shí) 狀態(tài)變量 4 s可取兩種狀態(tài) 1 D 2 D 則 41 3fD 42 4fD 2 當(dāng)3k 時(shí) 狀態(tài)變量 3 s可取三種狀態(tài) 1 C 2 C 3 C 這是經(jīng)過中途點(diǎn)的二級(jí)決策問題 則 1141 31 1242 1 3 minmin4 44 d C DfD fC d C DfD 路徑為 11 CDE 決策為 311 xCD 2141 32 2242 63 minmin7 34 d C DfD fC d C DfD 路徑為 22 CDE 決策為 322 xCD 3141 33 3242 33 minmin6 34 d C DfD fC d C DfD 路徑為 31 CDE 決策為 331 xCD 3 當(dāng)2k 時(shí) 狀態(tài)變量 2 s可取三種狀態(tài) 1 B 2 B 3 B 這是經(jīng)過中途點(diǎn)的三級(jí)決策問題 則 2 A B3 B2 B1 C1 C2 C2 E D1 D2 5 3 7 6 3 3 3 3 3 4 5 5 1 1 4 4 1234 1131 21 1333 74 minmin11 66 d B CfC fB d B CfC 路徑為 111 BCDE 決策為 211 xBC 2131 222232 2333 34 min min 277 46 d B CfC fBd B CfC d B CfC 路徑為 211 BCDE 決策為 221 xBC 3131 233232 3333 54 min min 1 78 56 d B CfC fBd B CfC d B CfC 路徑為 322 BCDE 決策為 232 xBC 4 當(dāng)1k 時(shí) 狀態(tài)變量 1 s可取狀態(tài)A 這是經(jīng)過中途點(diǎn)的四級(jí)決策問題 則 121 1222 323 2 11 min min 5711 38 d A BfB fAd A BfB d A BfB 路徑為 322 ABCDE 決策為 13 xAB 2 某施工單位擬在 3 年內(nèi)開發(fā)三個(gè)項(xiàng)目 各年開發(fā)這些項(xiàng)目的盈利如下表 問如何安排開發(fā)計(jì)劃 使該施工 單位的總盈利最大 最大盈利是多少 盈利年份 技術(shù)數(shù) 第一年第二年第三年 0000 1364 27106 3101211 解 階段分為三個(gè)階段 設(shè)決策變量 k x表示第k年開發(fā)的項(xiàng)目數(shù) 狀態(tài)變量 k s表示第k年到第 3 年開發(fā)的項(xiàng)目總數(shù) kk px 第k年開發(fā) k x個(gè)項(xiàng)目的盈利 決策變量取值范圍 33 22 11 0 0 sx xs xs 則狀態(tài)轉(zhuǎn)移方程 1kkk ssx 3 2 1k 基本方程 11 0 44 max 0 kk kkkkkk xs fspxfs fs 1 當(dāng)3k 時(shí) 有 33 333344 max xs f sp xfs 33 3333 max xs p xp s 得 33 xs 2 當(dāng)2k 時(shí) 對(duì)應(yīng) 2 0 1 2 3s 有 22 222233 0 max xs fsp xf s 2 0s 時(shí) 22 223 0 0 max000 xs fpf 2 1s 時(shí) 2 22232 0 1 1 max 1 s fp xfx 23 23 0 1 04 maxmax5 1 0 50 pf pf 得 2 1x 2 2s 時(shí) 2 22232 0 1 2 2 max 2 s fpxfx 23 23 23 0 2 06 max 1 1 max 5410 100 2 0 pf pf pf 得 2 2x 2 3s 時(shí) 2 22232 0 1 2 3 3 max 3 s fp xfx 23 23 23 23 0 3 0 11 1 2 56 maxmax14 2 1 104 11 0 3 0 pf pf pf pf 得 2 2x 3 當(dāng)1k 時(shí) 對(duì)應(yīng) 1 3s 有 11 111122 0 max xs f sp xfs 1 11121 0 1 2 3 3 max 3 x fp xfx 12 12 12 12 0 3 0 14 1 2 3 10 maxmax14 2 1 75 90 3 0 pf pf pf pf 得 1 0 x 得最優(yōu)方案 1 0 x 2 2x 3 1x 即第二年開發(fā)項(xiàng)目 2 項(xiàng) 第三年開發(fā)項(xiàng)目 1 項(xiàng) 總盈利為 14 萬元 3 某一警衛(wèi)部門共有 9 支巡邏隊(duì) 負(fù)責(zé) 3 個(gè)要害部門 A B C 的警衛(wèi)巡邏 每個(gè)部位可分別派出 2 4 支巡邏 隊(duì) 并且由于派出的巡邏隊(duì)數(shù)不同 各部位預(yù)期在一段時(shí)間內(nèi)可造成的損失有差別 具體數(shù)字見表 問該警衛(wèi) 部門應(yīng)往各部位分別派多少支巡邏隊(duì) 使總的預(yù)期損失為最少 部位 ABC預(yù)期損失 巡邏隊(duì)數(shù) 2183824 3143522 4103121 解 3n 往 3 個(gè)部位派看作 3 個(gè)階段 設(shè)決策變量 k x表示派往A B C三個(gè)部位的巡邏隊(duì)數(shù) 狀態(tài)變量 k s表示從第k階段到第三階段末可派出的巡邏隊(duì)總數(shù) 1kkk ssx 1 2 3k kk px表示第k階段派出 k x支巡邏隊(duì)時(shí) 該部位的損失值 則狀態(tài)轉(zhuǎn)移方程 1kkk ssx 1 2 3k 基本方程 11 min kkk kkkkkk xDs fspxfs 1 0min kk kkkkk xs pxfsx 1 當(dāng)3k 時(shí) 3 2 3 4 5s 1當(dāng) 3 2s 時(shí) 3 x取 2 3 224f 3 2x 2當(dāng) 3 3s