【正文】 運(yùn)輸問(wèn)題的應(yīng)用 84 圖中 1— 廣州、 2— 大連、 3— 上海、 4— 天津 5— 南京、 6— 濟(jì)南、 7— 南昌、 8— 青島 運(yùn)輸問(wèn)題的應(yīng)用 450 85 解：設(shè) xij 為從 i 到 j 的運(yùn)輸量，可得到有下列特點(diǎn)的線(xiàn)性規(guī)劃模型： 目標(biāo)函數(shù)： Min f = 所有可能的運(yùn)輸費(fèi)用（運(yùn)輸單價(jià)與運(yùn)輸量乘積之和） 約束條件：對(duì)產(chǎn)地（發(fā)點(diǎn)） i ： 輸出量 輸入量 = 產(chǎn)量 對(duì)轉(zhuǎn)運(yùn)站（中轉(zhuǎn)點(diǎn)）： 輸入量 輸出量 = 0 對(duì)銷(xiāo)地（收點(diǎn)） j ： 輸入量 輸出量 = 銷(xiāo)量 運(yùn)輸問(wèn)題的應(yīng)用 86 約束條件： . x13+x14 ≤ 600 (廣州分廠(chǎng)供應(yīng)量限制） x23+x24+x28 ≤ 450 (大連分廠(chǎng)供應(yīng)量限制） x13x23+x35+x36+x37+x38 = 0 （上海銷(xiāo)售公司，轉(zhuǎn)運(yùn)站） 目標(biāo)函數(shù)： Min f = 2x13+3x14+3x23+x24+4x28+2x35 +6x36+3x37+6x38+4x45+4x46+6x47+ 5x48 運(yùn)輸問(wèn)題的應(yīng)用 87 x14 x24 + x45 + x46+ x47 + x48 = 0 （天津銷(xiāo)售公司，轉(zhuǎn)運(yùn)站） x35+ x45 = 200 （南京的銷(xiāo)量） x36+ x46 = 150 （濟(jì)南的銷(xiāo)量） x37+ x47 = 350 （南昌的銷(xiāo)量） x38+ x48 + x28 = 300 （南京的銷(xiāo)量） xij ≥ 0 , i,j = 1,2,3,4,5,6,7,8 可求得結(jié)果： x13 = 550,x14 = 0 x23 = 0,x24 = 150,x28 = 300 x35 = 200,x36 = 0,x37 = 350,x38 = 0 x45 = 0,x46 = 150,x47 = 0,x48 = 0 運(yùn)輸問(wèn)題的應(yīng)用 88 作業(yè)： 習(xí)題 —4， 5， 6 。問(wèn)應(yīng)該如何調(diào)運(yùn)儀器，可使總運(yùn)輸費(fèi)用最低？ 轉(zhuǎn)運(yùn)問(wèn)題 :原運(yùn)輸問(wèn)題上增加若干轉(zhuǎn)運(yùn)站。該公司在上海和天津有兩個(gè)銷(xiāo)售公司負(fù)責(zé)對(duì)南京、濟(jì)南、南昌、青島四個(gè)城市的儀器供應(yīng)。 生產(chǎn)能力 / 臺(tái) 單位成本 / 萬(wàn)元 一季度 25 1 0 . 8 二季度 35 1 1 . 1 三季度 30 1 1 . 0 四季度 10 1 1 . 3 運(yùn)輸問(wèn)題的應(yīng)用 交貨： 生產(chǎn)： x11 = 10 x11+x12+x13+x14 ≤ 25 x12+x22 = 15 x22+x23+x24 ≤ 35 x13+x23+x33 = 25 x33+x34 ≤ 30 x14+x24+x34+x44 = 20 x44≤ 10 解： 設(shè) xij 為第 i 季度生產(chǎn)的第 j 季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿(mǎn)足： 運(yùn)輸問(wèn)題的應(yīng)用 把第 i 季度生產(chǎn)的柴油機(jī)數(shù)目看作第 i 個(gè)生產(chǎn)廠(chǎng)的產(chǎn)量；把第 j 季度交貨的柴油機(jī)數(shù)目看作第 j 個(gè)銷(xiāo)售點(diǎn)的銷(xiāo)量；成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)。如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用 元。 1 ’ 1 ” 2 3 4 ’ 4 ” 產(chǎn)量 A 1 6 1 6 1 3 22 17 17 50 B 14 14 1 3 19 15 15 60 C 19 19 20 23 M M 50 D M 0 M 0 M 0 50 銷(xiāo)量 30 20 70 30 10 50 運(yùn)輸問(wèn)題的應(yīng)用 生產(chǎn)與儲(chǔ)存問(wèn)題 例 :某廠(chǎng)按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供 1 2 20臺(tái)同一規(guī)格的柴油機(jī)。 1 2 3 4 產(chǎn)量 A 1 6 1 3 22 17 50 B 14 1 3 19 15 60 C 19 20 23 50 最低需要量 30 70 0 10 最高需要量 50 70 30 不限 運(yùn)輸問(wèn)題的應(yīng)用 79 解：根據(jù)題意，作出產(chǎn)銷(xiāo)平衡與運(yùn)價(jià)表 :最低要求必須滿(mǎn)足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為 M ，而最高要求與最低要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為 0 。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表。 一區(qū) 二區(qū) 三區(qū) 產(chǎn)量 山西盂縣 1. 6 5 4000 河北臨城 1. 6 0 5 1500 需要量 3000 1000 2022 運(yùn)輸問(wèn)題的應(yīng)用 77 解 :根據(jù)題意，作出產(chǎn)銷(xiāo)平衡與運(yùn)價(jià)表： 取 M 代表一個(gè)很大的正數(shù)，其作用是強(qiáng)迫相應(yīng)的 x3 x3 x34取值為 0。供應(yīng)能力分別為 1500、 4000t，運(yùn)價(jià)如下表。 —表上作業(yè)法 74 例 :某公司從兩個(gè)產(chǎn)地 A A2將物品運(yùn)往三個(gè)銷(xiāo)地 B B B3，各產(chǎn)地的產(chǎn)量、各銷(xiāo)地的銷(xiāo)量和各產(chǎn)地運(yùn)往各銷(xiāo)地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？ B 1 B 2 B 3 產(chǎn)量 A 1 6 4 6 200 A 2 6 5 5 300 銷(xiāo)量 250 200 200 運(yùn)輸問(wèn)題的應(yīng)用 75 解：增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為 0 B 1 B 2 B 3 產(chǎn)量 A 1 6 4 6 2 00 A 2 6 5 5 300 A 3 0 0 0 150 銷(xiāo)量 250 200 200 運(yùn)輸問(wèn)題的應(yīng)用 例 :石家莊北方研究院有一、二、三，三個(gè)區(qū)。j=1,2,…, n) 72 只要在模型中的產(chǎn)量限制約束 （ 后 n個(gè)不等式約束 ） 中引入 n個(gè)松弛變量 xm+1j j = 1,2,… ,n即可 ， 變?yōu)椋? m ?xij+xm+1j=dj j=1,2,… ， m i=1 然后 ， 需設(shè)一個(gè)產(chǎn)地 A m+1,它的銷(xiāo)量為： n m am+1= ?dj ?si j=1 i=1 —表上作業(yè)法 73 這里 ， 松弛變量 x m+1j 可以視為從產(chǎn)地 A m+1 運(yùn)往銷(xiāo)地 B j 的運(yùn)輸量 ， 由于實(shí)際并不運(yùn)送 ， 它們的運(yùn)費(fèi)為 c m+1j = 0 j = 1,2,… ,n。 于是 ， 這個(gè)運(yùn)輸問(wèn)題就轉(zhuǎn)化成了一個(gè)產(chǎn)銷(xiāo)平衡的問(wèn)題 。 m n 考慮 ?si ?dj 的運(yùn)輸問(wèn)題，得到的數(shù)學(xué)模 i=1 j=1 型為 —表上作業(yè)法 66 —表上作業(yè)法 m n Min f = ? ? cij xij i=1 j=1 n . ? xij ≤ si i = 1,2,…, m j=1 m ?xij =dj j = 1,2,…, n i=1 xij≥0(i=1,2,…, m。 最優(yōu)值 ： f* = 3 5+10 2+1 3+8 1+4 6+5 3 = 85 例： vj 3 4 2 5 ui B1 B2 B3 B4 產(chǎn)量 ai 5 A1 3 1 11 2 3 4 10 3 7 4 A2