【正文】 量 8 14 9 ijijij ccccM ????? 10,10}m a x{ /22取86 銷地 產(chǎn)地 B1 B2 B3 產(chǎn)量 A1 2 5 8 9 A2 9 10 7 10 A3 6 5 4 12 銷量 8 14 9 得到新的最小化運(yùn)輸問題，用表上作業(yè)法求解即可。 87 2. 產(chǎn)銷不平衡的運(yùn)輸問題 3. 當(dāng)總產(chǎn)量與總銷量不相等時(shí) ,稱為不平衡運(yùn)輸問題 .這類運(yùn)輸問題在實(shí)際中常常碰到 ,它的求解方法是將不平衡問題化為平衡問題再按平衡問題求解。 當(dāng)產(chǎn)大于銷時(shí)，即： ? ?? ??minjji ba1 1數(shù)學(xué)模型為： ? ?? ??minjijij xcZ1 1m i n????????????????????njmixnjbxmiaxijmijijnjiij,2,1。,2,10,2,1,2,111????，88 ? 由于總產(chǎn)量大于總銷量，必有部分產(chǎn)地的產(chǎn)量不能全部運(yùn)送完，必須就地庫存，即每個(gè)產(chǎn)地設(shè)一個(gè)倉庫，假設(shè)該倉庫為一個(gè)虛擬銷地 Bn+1， bn+1作為一個(gè)虛設(shè)銷地 Bn+1的銷量 (即庫存量 )。各產(chǎn)地Ai到 Bn+1的運(yùn)價(jià)為零，即 Ci,n+1=0,（ i=1， … ， m）。則平衡問題的數(shù)學(xué)模型為： ? ?? ?? minjijij xcZ1 1m i n??????????????????????,2,1,2,1,01,2,1,2,1111jmixnjbxmiaxijmijijnjiij；???具體求解時(shí) ,只在運(yùn)價(jià)表右端增加一列 Bn+1，運(yùn)價(jià)為零 ,銷量為 bn+1即可 89 當(dāng)銷大于產(chǎn)時(shí)，即： ? ?? ??minjji ba1 1? ?? ??minjijij xCZ1 1m i n????????????????????,2,1。,2,1,0,2,1,2,111????jmixnjbxmiaxijmijijnjiij數(shù)學(xué)模型為： 由于總銷量大于總產(chǎn)量 ,故一定有些需求地不完全滿足 ,這時(shí)虛設(shè)一個(gè)產(chǎn)地 Am+1，產(chǎn)量為： ????? mi inj jab1190 銷大于產(chǎn)化為平衡問題的數(shù)學(xué)模型為 ： ? ?? ?? minjijij xcZ1 1m i n???????????????????????njmixnjbxmiaxijmijijnjiji,2,11,2,1,0,2,11,2,1111????；具體計(jì)算時(shí)，在運(yùn)價(jià)表的下方增加一行 Am+1，運(yùn)價(jià)為零。產(chǎn)量為 am+1即可。 91 ? 例 4 求下列表中極小化運(yùn)輸問題的最優(yōu)解。 B1 B2 B3 B4 ai A1 5 9 2 3 60 A2 4 7 8 40 A3 3 6 4 2 30 A4 4 8 10 11 50 bj 20 60 35 45 180 160 ? ?? ????4141160180i jji ba因?yàn)橛校? 92 ? 所以是一個(gè)產(chǎn)大于銷的運(yùn)輸問題。表中 A2不可達(dá)B1，用一個(gè)很大的正數(shù) M表示運(yùn)價(jià) C21。虛設(shè)一個(gè)銷量為 b5=180160=20， Ci5=0， i=1,2,3,4，表的右邊增添一列 ，得到新的運(yùn)價(jià)表。 B1 B2 B3 B4 B5 ai A1 5 9 2 3 0 60 A2 M 4 7 8 0 40 A3 3 6 4 2 0 30 A4 4 8 10 11 0 50 bj 20 60 35 45 20 180 93 ? 下表為計(jì)算結(jié)果?？煽闯觯寒a(chǎn)地 A4還有 20個(gè)單位沒有運(yùn)出。 B1 B2 B3 B4 B5 Ai A1 35 25 60 A2 40 40 A3 10 20 30 A4 20 10 20 50 Bj 20 60 35 45 20 180 94 ? 3. 生產(chǎn)與儲(chǔ)存問題 例 5 某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供 1 220臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用 。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。 季度 生產(chǎn)能力 /臺(tái) 單位成本 /萬元 Ⅰ 25 Ⅱ 35 Ⅲ 30 11 Ⅳ 10 95 ?解： 設(shè) xij為第 i 季度生產(chǎn)的第 j 季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足： ?交貨： x11 = 10 生產(chǎn)： 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 把第 i 季度生產(chǎn)的柴油機(jī)數(shù)目看作第 i 個(gè)生產(chǎn)廠的產(chǎn)量；把第 j 季度交貨的柴油機(jī)數(shù)目看作第 j 個(gè)銷售點(diǎn)的銷量；設(shè) cij是第 i季度生產(chǎn)的第 j季度交貨的每臺(tái)柴油機(jī)的實(shí)際成本，應(yīng)該等于該季度單位成本加上儲(chǔ)存、維護(hù)等費(fèi)用?？蓸?gòu)造下列產(chǎn)銷平衡問題： 96 j i Ⅰ Ⅱ Ⅲ Ⅳ 產(chǎn)量 Ⅰ 25 Ⅱ M 35 Ⅲ M M 30 Ⅳ M M M 10 銷量 10 15 25 20 100 70 由于產(chǎn)大于銷，加上一個(gè)虛擬的銷地 D，化為平衡問題，即可應(yīng)用表上作業(yè)法求解。 97 該問題的數(shù)學(xué)模型： Min f = x11 + x12 + x13 + x14 + x22 + x23 + x24 + x33 + x34 + x44 j i Ⅰ Ⅱ Ⅲ Ⅳ D 產(chǎn)量 Ⅰ 0 25 Ⅱ M 0 35 Ⅲ M M 0 30 Ⅳ M M M 0 10 銷量 10 15 25 20 30 100 100 98 j i Ⅰ Ⅱ Ⅲ Ⅳ D 產(chǎn)量 Ⅰ 10 15 0 25 Ⅱ 0 5 30 35 Ⅲ 25 5 30 Ⅳ 10 10 銷量 10 15 25 20 30 100 100 最優(yōu)生產(chǎn)決策如下表，最小費(fèi)用 z＝ 773萬元。 99 例 (運(yùn)輸問題 ) 兩個(gè)糧庫 A1,A2,向三個(gè)糧站 B1,B2,B3調(diào)運(yùn)大米，兩個(gè)糧庫現(xiàn)存大米分別為 4t， 8t，三個(gè)兩站至少需要大米分別為 2t,4t,5t，兩個(gè)糧庫到三個(gè)糧站的距離 (km)如下表，求使運(yùn)費(fèi)最低。 B1 B2 B3 庫存 A1 12 24 8 4 A2 30 12 24 8 需求 2 4 5 解： (1)問題分析：總需求量為 11t，小于總庫存量 12t，所以問題可行。 (2)從線性規(guī)劃的三個(gè)要素出發(fā)， 決策變量 ：問題是各個(gè)糧倉向糧站調(diào)運(yùn)了多少大米，此調(diào)運(yùn)量就是決策變量。 目標(biāo)函數(shù) ：運(yùn)費(fèi)和運(yùn)量和距離有關(guān)系，即 t*km最小，所以要將運(yùn)量與相應(yīng)的距離相乘然后使總和最小。 約束條件 ：兩個(gè)糧庫的庫存量限制和三個(gè)糧站需求量的限制。 100 (3)建立模型，設(shè) A1,A2分別向 B1,B2,B3運(yùn)送大米 x11,x12,x13,x21,x22,x23，則有： min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23 . x11+x12+x13=4 x21+x22+x23=8 x11+x21=2 x12+x22=4 x13+x23=5 x11,x12,x13,x21,x22,x23=0 101 102 通過選擇 Lingo|Generate|Display model將模型展開，方便查看求解報(bào)告的第三部分。 相應(yīng)的添加的剩余變量或者松弛變量。 103 程序改進(jìn)一、上面解法是一種傻瓜式的直接輸入法，適用于程序規(guī)模不大的問題，如果問題規(guī)模很大的話用這種方式很費(fèi)力，可以使用矩陣生成器來編寫程序 2 如下化為標(biāo)準(zhǔn)形式 min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23 . x11+x12+x13+y1=4 x21+x22+x23+y2=8 x11+x21y3=2 x12+x22y4=4 x13+x23y5=5 x11,x12,x13,x21,x22,x23,y1,y2,y3,y4,y5=0 轉(zhuǎn)換成 Lingo語言如下所示： 104 105 注： 寫程序要習(xí)慣給程序用 title命名 為了方便查看報(bào)告，用行號(hào)區(qū)分約束 此程序的格式可以固定為標(biāo)準(zhǔn)形式的求解模式。 程序改進(jìn)二：可以減少引入的變量個(gè)數(shù)，將模型修改為下面的形式 min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23 . x11+x12+x13=4 x21+x22+x23=8 x11x21= 2 x12x22= 4 x13x23= 5 x11,x12,x13,x21,x22,x23=0 寫成 lingo語言如下所示： 106 107 注： 改程序把不等式約束全部轉(zhuǎn)化為小于等于約束， 是為了將約束可以寫到一個(gè)循環(huán)語句中實(shí)現(xiàn) ，如果還有等是約束的話，則要在寫一個(gè)循環(huán)語句來控制約束。 當(dāng)程序比較大的時(shí)候，一般將 約束按性質(zhì) 進(jìn)行分類 108 程序改進(jìn)三：將約束進(jìn)行分類，代碼如下： 109 注： 在進(jìn)行調(diào)試程序時(shí)，可以用 !號(hào)某些語句屏蔽，縮小尋找出錯(cuò)的范圍。 可以編寫程序邊運(yùn)行，保證每行書寫都是正確的 常見的出錯(cuò)情況有： (1)定義了多個(gè)長度一樣的集合，而在使用中區(qū)分不明確； (2)定義了同名的屬性； (3)漏掉了括號(hào)； (4)分號(hào)不是英文半角； (5)使用的字母沒有定義； (6)循環(huán)語句中元素下標(biāo)顛倒或者不明； (7)約束錯(cuò)誤變成不可行或者無界； (8)關(guān)系運(yùn)算符誤用成邏輯運(yùn)算符； (9)函數(shù)調(diào)用錯(cuò)誤等等 … 110 作業(yè) LINGO求解 ? .某工廠在計(jì)劃內(nèi)擬生產(chǎn) I,II兩種產(chǎn)品 ,已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)及 A,B兩種原材料的消耗如下表 : ? I II 總量 ? 總量設(shè)備 (臺(tái)時(shí) ) 3 4 36 ? 原材料 A(kg) 0 2 12 ? 原材料 B(kg) 1 0 8 ? 該工廠生產(chǎn)一件產(chǎn)品 I可獲利 3百元 , 生產(chǎn)一件產(chǎn)品II可獲利 5百元 , ? 應(yīng)如何安排生產(chǎn) ? ? 若該工廠決定不生產(chǎn) ,而將上述資源出租 ,問總租金應(yīng)為多少 ? [影子價(jià)格問題 ] 111 ? 例 某公司從兩個(gè)產(chǎn)地 A A2將物品運(yùn)往三個(gè)銷地 B1, B2, B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？ [運(yùn)輸問題 ] 單位運(yùn)費(fèi) B1 B2 B3 產(chǎn)量 A1 6 4 6 200 A2 6 5 5 300 銷量 150 150 200 112 ? 3 .設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥 .假定等量的化肥在這些地區(qū)使用效果相同 .各化肥廠年產(chǎn)量 ,各地區(qū)年需要量及從各化肥廠到各地區(qū)運(yùn)送單位化肥的運(yùn)價(jià) (萬元 /萬噸 )如下表所示 .試求出總的運(yùn)費(fèi)最省的化肥調(diào)撥方案 . ? 需求地區(qū) I II III IV 產(chǎn)量 (萬噸 ) ? 化肥廠