運(yùn)籌學(xué)教學(xué)課件第三章運(yùn)輸問(wèn)題

1、1第三章 運(yùn)輸問(wèn)題 運(yùn)輸問(wèn)題與有關(guān)概念 運(yùn)輸問(wèn)題的求解表上作業(yè)法 運(yùn)輸問(wèn)題應(yīng)用建模本章內(nèi)容重點(diǎn)21.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 問(wèn)題的提出 一般的運(yùn)輸問(wèn)題就是要解決把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷(xiāo)地，在每個(gè)產(chǎn)地的供應(yīng)量與每個(gè)銷(xiāo)地的需求量已知，并知道各地之間的運(yùn)輸單價(jià)的前提下，如何確定一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案。31.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 例4.1:某公司從兩個(gè)產(chǎn)地a1、a2將物品運(yùn)往三個(gè)銷(xiāo)地b1、b2、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)用最小？ b1 b2 b3 產(chǎn)量產(chǎn)

2、量 a1 6 4 6 200 a2 6 5 5 300 銷(xiāo)量銷(xiāo)量 150 150 200 4 解： 產(chǎn)銷(xiāo)平衡問(wèn)題： 總產(chǎn)量 = 總銷(xiāo)量 設(shè) xij 為從產(chǎn)地ai運(yùn)往銷(xiāo)地bj的運(yùn)輸量，得到下列運(yùn)輸量表： b1 b2 b3 產(chǎn)量產(chǎn)量 a1 x11 x12 x13 200 a2 x21 x22 x23 300 銷(xiāo)量銷(xiāo)量 150 150 200 1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念5 min z = 6x11+4x12+6x13+6x21+5x22+5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x

3、12 + x22 = 150 x13 + x23 = 200 xij0(i=1,2；j=1,2,3）1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念6 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 系數(shù)矩陣1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念7 模型系數(shù)矩陣特征 1.共有m+n行，分別表示各產(chǎn)地和銷(xiāo)地；mn列，分別表示各決策變量； 2.每列只有兩個(gè) 1，其余為 0，分別表示只有一個(gè)產(chǎn)地和一個(gè)銷(xiāo)地被使用。1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念8 一般運(yùn)輸問(wèn)題的線性規(guī)劃模型及求解思路 一般運(yùn)

4、輸問(wèn)題的提法： 假設(shè) a1, a2,am 表示某物資的m個(gè)產(chǎn)地；b1,b2,bn 表示某物資的n個(gè)銷(xiāo)地；ai表示產(chǎn)地 ai 的產(chǎn)量；bj 表示銷(xiāo)地 bj 的銷(xiāo)量；cij 表示把物資從產(chǎn)地 ai 運(yùn)往銷(xiāo)地 bj 的單位運(yùn)價(jià)（表4-3）。如果 a1 + a2 + + am = b1 + b2 + + bn則稱該運(yùn)輸問(wèn)題為產(chǎn)銷(xiāo)平衡問(wèn)題；否則，稱產(chǎn)銷(xiāo)不平衡。首先討論產(chǎn)銷(xiāo)平衡問(wèn)題。1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念9表4-3 運(yùn)輸問(wèn)題數(shù)據(jù)表1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 銷(xiāo)地產(chǎn)地b1 b2 bn產(chǎn)量a1 a2 amc11 c12 c1nc21 c22 c2n cm

5、1 cm2 cmna1 a2 am銷(xiāo)量b1 b2 bn 設(shè) xij 為從產(chǎn)地 ai 運(yùn)往銷(xiāo)地 bj 的運(yùn)輸量，根據(jù)這個(gè)運(yùn)輸問(wèn)題的要求，可以建立運(yùn)輸變量表（表 4-4）。10表4-4 運(yùn)輸問(wèn)題變量表1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 銷(xiāo)地產(chǎn)地b1 b2 bn產(chǎn)量a1 a2 amx11 x12 x1nx21 x22 x2n xm1 xm2 xmna1 a2 am銷(xiāo)量b1 b2 bn11 m nmin z = cij xij （4-1） i=1 j=1 n s.t. xij ai i = 1,2,m （4-2） j=1 m xij (=,)bj j = 1,2,n （4-3） i=

6、1 xij 0 (i=1,2,m;j=1,2,n)（4-4） 1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 于是得到下列一般運(yùn)輸問(wèn)題的模型： 在模型（4-1）（4-4）中，式（4-2）為 m 個(gè)產(chǎn)地的產(chǎn)量約束；式（4-3）為 n 個(gè)銷(xiāo)地的銷(xiāo)量約束。 12 m n min z = cij xij i=1 j=1 n s.t. xij = ai i = 1,2,m (4-5) j=1 m xij = bj j = 1,2,n (4-6) i=1 xij0(i=1,2,m;j=1,2,n) 1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 對(duì)于產(chǎn)銷(xiāo)平衡問(wèn)題，可得到下列運(yùn)輸問(wèn)題的模型：13

7、 在產(chǎn)銷(xiāo)平衡問(wèn)題中，仔細(xì)觀察式（4-2）、 （4-3）分別變?yōu)椋?-5）、（4-6），約束條件成 為等式。 在實(shí)際問(wèn)題建模時(shí)，還會(huì)出現(xiàn)如下一 些變化： （1）有時(shí)目標(biāo)函數(shù)求最大，如求利潤(rùn)最 大或營(yíng)業(yè)額最大等； （2）當(dāng)某些運(yùn)輸線路上的能力有限制時(shí)， 模型中可直接加入（等式或不等式）約束； 1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念14 (3)產(chǎn)銷(xiāo)不平衡的情況。當(dāng)銷(xiāo)量大于產(chǎn)量時(shí)可加入一個(gè)虛設(shè)的產(chǎn)地去生產(chǎn)不足的物資，這相當(dāng)于在式（4-2）每一式中加上 1 個(gè)松弛變量，共 m 個(gè)；當(dāng)產(chǎn)量大于銷(xiāo)量時(shí)可加入一個(gè)虛設(shè)的銷(xiāo)地去消化多余的物資，這相當(dāng)于在式（4-3）每一式中加上 1 個(gè)松弛變量，共

8、n 個(gè)。1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念15 運(yùn)輸問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題，在求解時(shí)依然可以采用單純形法的思路，如圖4-1所示。由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計(jì)算，則無(wú)法利用這些有利條件。人們?cè)诜治鲞\(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對(duì)運(yùn)輸問(wèn)題的表上作業(yè)法。在這里需要討論基本可行解、檢驗(yàn)數(shù)以及基的轉(zhuǎn)換等問(wèn)題。1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念161.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念基本可行解是否最優(yōu)解結(jié)束換基是否圖4-1 運(yùn)輸問(wèn)題的求解思路17 運(yùn)輸問(wèn)題求解的有關(guān)概念 考慮產(chǎn)銷(xiāo)平衡問(wèn)題，由于我們關(guān)心的量均

9、在表4-3與表4-4中，因此考慮把表4-3與表4-4合成一個(gè)表, 如下表4-5表4-5 運(yùn)輸問(wèn)題求解作業(yè)數(shù)據(jù)表(下頁(yè)）1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念181.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 銷(xiāo)地產(chǎn)地b1b2bn產(chǎn)量a1 c11 x11c12 x12c1n x1na1 a2 c21 x21c22 x22c2n x2na2 amcm1 xm1cm2 xm2cmn xmnam銷(xiāo)量b1b2bn19111111111111111111212222111211mnmmnnxxxxxxxxxa中任意m+n階子式等于零，取第一行到m+n1行與對(duì)應(yīng)的列（共m+n-1列）組成

10、的m+n1階子式1, 1121121,nmnnnxxxxxx，200111111111故r(a)=m+n1所以運(yùn)輸問(wèn)題有m+n1個(gè)基變量。21 運(yùn)輸問(wèn)題的基變量共有 m + n -1 個(gè)，a的秩為 m + n -1。 運(yùn)輸問(wèn)題的 m + n -1 個(gè)變量構(gòu)成基變量的充分必要條件是不含閉回路。 重要概念: 閉回路、閉回路的頂點(diǎn)特點(diǎn) 運(yùn)輸問(wèn)題基變量的1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念22 定義4.1 在表4-5的決策變量格中，凡是能夠排列成下列形式的 xab ,xac ,xdc ,xde ,xst ,xsb (4-7)或 xab ,xcb ,xcd ,xed ,xst ,xat

11、(4-8) 其中，a,d,s 各不相同；b,c,t 各不相同，我們稱之為變量集合的一個(gè)閉回路閉回路，并將式（4-7）、式（4-8）中的變量稱為這個(gè)閉回路的頂點(diǎn)閉回路的頂點(diǎn)。 為了說(shuō)明這個(gè)特征，我們不加證明的給出一些概念和結(jié)論。下面的討論建立在表4-5中決策變量格的基礎(chǔ)上。1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念23例如，x13, x16, x36, x34, x24, x23 ； x23, x53, x55, x45, x41, x21 ； x11, x14, x34, x31等都是閉回路。 若把閉回路的各變量格看作節(jié)點(diǎn)，在表中可以畫(huà)出如下形式的閉回路：1.1.運(yùn)輸問(wèn)題模型及有關(guān)概

12、念運(yùn)輸問(wèn)題模型及有關(guān)概念 閉回路示意圖24 根據(jù)定義可以看出閉回路的一些明顯特點(diǎn)： (1)閉回路均為一封閉折線，它的每一條邊，或?yàn)樗降模驗(yàn)榇怪钡模?(2)閉回路的每一條邊（水平的或垂直的）均有且僅有兩個(gè)閉回路的頂點(diǎn)（變量格）。 1.1.運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念25 x23 b1b2b3b4b5a1 a2 a3 x35a4 x43 x11x12 x25x31 x42表33表33中閉回路的變量集合是x11,x12,x42, x 43, x 23, x 25, x 35, x 31共有8個(gè)頂點(diǎn)， 這8個(gè)頂點(diǎn)間用水平或垂直線段連接起來(lái)，組成一條封閉的回路。 26x11x12x3

13、2x33x41 b1b2b3a1 a2 a3 a4 x43表34 一條回路中的頂點(diǎn)數(shù)一定是偶數(shù)，回路遇到頂點(diǎn)必須轉(zhuǎn)90度與另一頂點(diǎn)連接，表33中的變量x 32及x33不是回閉路的頂點(diǎn)，只是連線的交點(diǎn)。 表34中閉回路是123233434111,xxxxxx;,121131352521xxxxxxa ;,2111123233xxxxxb 例如變量組a不能組成一條閉回路，但a中包含有閉回路 ;,31352521xxxxb的變量數(shù)是奇數(shù)，顯然不是閉回路，也不含有閉回路； 27333211122321,xxxxxxc c是一條閉回路，若把c重新寫(xiě)成 就不難看出c仍是一條閉回路。 11123233232

14、1,xxxxxxc 【定理定理1】 若變量組b 包含有閉回路 ，則b中的變量對(duì)應(yīng)的例向量線性相關(guān)。12111,jijijisxxxc【證】由線性代數(shù)知，向量組中部分向量組線性相關(guān)則該向量組線性相關(guān)，顯然，將c中列向量分別乘以正負(fù)號(hào)線性組合后等于零，即01222111jijijijispppp因而c中的列向量線性相關(guān)，所以b中列向量線性相關(guān)。【定理定理2】若變量組中包含一個(gè)部分組構(gòu)成閉回路，那么該變量組所對(duì)應(yīng)的系數(shù)列向量線性相關(guān)。1122,rri jiji jxxx1122,rrijijijppp28 定理3 變量組 xab , xcd , xef , xst 所對(duì)應(yīng)的系數(shù)列向量pab , pc

15、d , pef , pst 線性無(wú)關(guān)的充分必要條件是這個(gè)變量組中不包含閉回路。 推論 產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的 m + n -1 個(gè)變量構(gòu)成基變量的充分必要條件是它不含閉回路。 這個(gè)推論給出了運(yùn)輸問(wèn)題基本解的重要性質(zhì)，也為尋求基本可行解提供了依據(jù)。這個(gè)推論告訴了一個(gè)求基變量的簡(jiǎn)單方法，同時(shí)也可以判斷一組變量是否可以作為某個(gè)運(yùn)輸問(wèn)題的基變量。這種方法是直接在運(yùn)價(jià)表中進(jìn)行的，不需要在系數(shù)矩陣a中去尋找，從而給運(yùn)輸問(wèn)題求初始基可行解帶來(lái)極大的方便。29例如，m=3,n=4，在運(yùn)價(jià)表cij的格子的右上方填上相應(yīng)的xij，如表3-5所示。表35 bjaib1b2b3b4aia1 x11 x12 x13 x14

16、 a1c11c12c13c14a2 x21 x22 x23 x24a2c21c22c23c24a3 x31 x32 x2 x34a3c31c32c33c34bjb1b2b3b4 30這個(gè)運(yùn)輸問(wèn)題的基變量數(shù)目是3+41=6。變量組中有7個(gè)變量，顯然不能構(gòu)成一組基變量，又如中有6個(gè)變量，但包含有一條閉回路故不能構(gòu)成一組基變量。變量組有6個(gè)變量且不含有任何閉回路，故可以構(gòu)成此問(wèn)題的一組基變量。22121324323111,xxxxxxx,342413322221xxxxxx24343222,xxxx343332222111,xxxxxx312.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 上一

17、節(jié)已經(jīng)分析了，對(duì)于產(chǎn)銷(xiāo)平衡問(wèn)題，我們關(guān)心的量均可以表示在表4-5中。因此可以建立基于表4-5的求解運(yùn)輸問(wèn)題的方法表上作業(yè)法。這里求解運(yùn)輸問(wèn)題的思想和單純形法完全類(lèi)似，即首先確定一個(gè)初始基本可行解，然后根據(jù)最優(yōu)性判別準(zhǔn)則來(lái)檢查這個(gè)基本可行解是不是最優(yōu)的。如果是則計(jì)算結(jié)束；如果不是，則進(jìn)行換基，直至求出最優(yōu)解為止。322.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 一、初始基本可行解的確定 根據(jù)上面的討論，要求得運(yùn)輸問(wèn)題的初始基本可行解，必須保證找到 m + n 1 個(gè)不構(gòu)成閉回路的基變量。一般的方法步驟如下： (1)在運(yùn)輸問(wèn)題求解作業(yè)數(shù)據(jù)表中任選一個(gè)單元格 xij ( ai 行 bj 列

18、交叉位置上的格),令 xij = min ai , bj 即從ai向bj運(yùn)最大量(使行或列在允許的范圍內(nèi)盡量飽和，即使一個(gè)約束方程得以滿足),填入xij的相應(yīng)位置；332.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 (2)從 ai 或 bj 中分別減去 xij 的值，即調(diào)整 ai 的擁有量及 bj 的需求量；(3)若ai=0，則劃去對(duì)應(yīng)的行（把擁有的量全部運(yùn)走），若bj=0則劃去對(duì)應(yīng)的列（把需要的量全部運(yùn)來(lái)），且每次只劃去一行或一列（即每次要去掉且只去掉一個(gè)約束）；(4)若運(yùn)輸平衡表中所有的行與列均被劃去，則得到了一個(gè)初始基本可行解。否則在剩下的運(yùn)輸平衡表中選下一個(gè)變量，轉(zhuǎn)(4)。34

19、上述計(jì)算過(guò)程可用流程圖描述如下（圖4-2）取未劃去的單元格xij ,令xij = min ai , bj ai = ai - xijbj = bj - xijai = 0?劃去第i行劃去第j列是否 bj = 0否所有行列是否均被劃去是找到初始基本可行解圖4-2 求運(yùn)輸問(wèn)題的初始基本可行解過(guò)程352.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 按照上述方法所產(chǎn)生的一組變量的取值將滿足下面條件：(1)所得的變量均為非負(fù)，且變量總數(shù)恰好為 m + n 1 個(gè)；(2)所有的約束條件均得到滿足；(3)所得的變量不構(gòu)成閉回路。因此，根據(jù)定理4.1及其推論，所得的解一定是運(yùn)輸問(wèn)題的基本可行解。在上面

20、的方法中，xij的選取方法并沒(méi)有給予限制，若采取不同的規(guī)則來(lái)選取xij，則得到不同的方法，較常用的方法有西北角法和最小元素法。下面分別舉例予以說(shuō)明。362.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 1、初始基本可行解的確定 （1）西北角法：從西北角（左上角）格開(kāi)始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按行（列）標(biāo)下一格的數(shù)。若某行（列）的產(chǎn)量（銷(xiāo)量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。37例1：設(shè)有運(yùn)輸問(wèn)題如下表所示，求其最優(yōu)解。2b3b1a2a 銷(xiāo)地 產(chǎn)地可供量(t)907095200806575230需求量(t)1001501801b38

21、 銷(xiāo)地 產(chǎn)地可供量(t)90（100）70 （100）95200 （100）8065（50） 75（180） 230 （180）需求量(t)100（0）150 （50）180（0）1b2b3b1a2a第一次第二次第三次第四次392.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 （2）最小元素法：從運(yùn)價(jià)最小的格開(kāi)始，在格內(nèi)的右下角標(biāo)上允許取得的最大數(shù)。然后按運(yùn)價(jià)從小到大順序填數(shù)。若某行（列）的產(chǎn)量（銷(xiāo)量）已滿足，則把該行（列）的其他格劃去。如此進(jìn)行下去，直至得到一個(gè)基本可行解。最小元素法的思想是就近優(yōu)先運(yùn)送，即最小運(yùn)價(jià)cij對(duì)應(yīng)的變量xij優(yōu)先賦值然后再在剩下的運(yùn)價(jià)中取最小運(yùn)價(jià)對(duì)應(yīng)的變量賦

22、值并滿足約束，依次下去，直到最后一個(gè)初始基可行解。jiijbax,min40【例例2】求表】求表36所示的運(yùn)輸問(wèn)題的初始基可行解。表36 銷(xiāo) 地產(chǎn)地b1b2b3產(chǎn)量a186730a243545a374825銷(xiāo) 量60301010041b1b2b3可發(fā)量a186730a243545a374825未滿足量6030101000 00【解】301510252015452020000產(chǎn)地銷(xiāo)地42 注:應(yīng)用西北角法和最小元素法，每次填完數(shù)，都只劃去一行或一列，只有最后一個(gè)元例外（同時(shí)劃去一行和一列）。當(dāng)填上一個(gè)數(shù)后行、列同時(shí)飽和時(shí)，也應(yīng)任意劃去一行（列），在保留的列（行）中沒(méi)被劃去的格內(nèi)標(biāo)一個(gè)0。2.2.

23、運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 432.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 表1441、確 定 初 始 基 本 可 行 解： （1）西 北 角 法 b1 b2 b3 b4 產(chǎn)量 ai a1 3 3 11 4 3 10 7 a2 1 9 2 2 2 8 4 a3 7 4 10 3 5 6 9 銷(xiāo)量 bj 3 6 5 6 20 2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 45（2）最小元素法 b1 b2 b3 b4 產(chǎn)量 ai a1 3 11 3 4 10 3 7 a2 1 3 9 2 1 8 4 a3 7 4 6 10 5 3 9 銷(xiāo)量 bj 3 6

24、5 6 20 2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 46 最優(yōu)性檢驗(yàn)就是檢查所得到的方案是不是最優(yōu)方案。檢查的方法與單純形方法中的原理相同，即計(jì)算檢驗(yàn)數(shù)。由于目標(biāo)要求極小，因此，當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案；否則就不是最優(yōu)，需要進(jìn)行調(diào)整。下面介紹兩種求檢驗(yàn)數(shù)的方法。 二、基本可行解的最優(yōu)性檢驗(yàn) 2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 47 1、閉回路法 為了方便，我們以表1給出的初始基本可行解方案為例，考察初始方案的任意一個(gè)非基變量，比如 x24。根據(jù)初始方案，產(chǎn)地 a2 的產(chǎn)品是不運(yùn)往銷(xiāo)地 b4 的。如果現(xiàn)在改變初始方案，把 a2 的

25、產(chǎn)品運(yùn)送1 個(gè)單位給 b4 ，那么為了保持產(chǎn)銷(xiāo)平衡，就必須使 x14 或 x34 減少 1 個(gè)單位；而如果 x14 減少 1 個(gè)單位，第 1 行的運(yùn)輸量就必須增加 1 個(gè)單位，例如 x13 增加 1 個(gè)單位，那么為了保持產(chǎn)銷(xiāo)平衡，就必須使 x23 減少 1 個(gè)單位。2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 48 這個(gè)過(guò)程就是尋找一個(gè)以非基變量 x24 為起始頂點(diǎn)的閉回路 x24 ，x14 ，x13 ，x23 ，這個(gè)閉回路的其他頂點(diǎn)均為基變量(對(duì)應(yīng)著填上數(shù)字的格)。容易計(jì)算出上述調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為 8 10 + 3 2 -1 ，即總的運(yùn)費(fèi)減少 1 個(gè)單位，這就說(shuō)明原始方

26、案不是最優(yōu)方案，可以進(jìn)行調(diào)整以得到更好的方案。2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 49 可以證明，如果對(duì)閉回路的方向不加區(qū)別（即只要起點(diǎn)及其他所有頂點(diǎn)完全相同，而不區(qū)別行進(jìn)方向），那么以每一個(gè)非基量為起始頂點(diǎn)的閉回路就存在而且唯一。因此，對(duì)每一個(gè)非基變量可以找到而且只能找到唯一的一個(gè)閉回路。 表4-10中用虛線畫(huà)出以非基變量 x22 為起始頂點(diǎn)的閉回路。2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 50表4-10 以非基變量 x22 為起始頂點(diǎn)的閉回路銷(xiāo)地產(chǎn)地b1b2b3b4產(chǎn)量3 11 3 410 371 39 2 18 47 4 610 5 39銷(xiāo)量36562

27、0(產(chǎn)銷(xiāo)平衡)a1a2a351 可以計(jì)算出以非基變量 x22 為起始頂點(diǎn)的閉回路調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為 9 2 + 3 10 + 5 4 1 即總的運(yùn)費(fèi)增加 1 個(gè)單位，這就說(shuō)明這個(gè)調(diào)整不能改善目標(biāo)值。 從上面的討論可以看出，當(dāng)某個(gè)非基變量增加一個(gè)單位時(shí)，有若干個(gè)基變量的取值受其影響。2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 52 這樣，利用單位產(chǎn)品變化（運(yùn)輸?shù)膯挝毁M(fèi)用）可計(jì)算出它們對(duì)目標(biāo)函數(shù)的綜合影響，其作用與線性規(guī)劃單純形方法中的檢驗(yàn)數(shù)完全相同。故也稱這個(gè)綜合影響為該非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)。上面計(jì)算的兩個(gè)非基變量的檢驗(yàn)數(shù)為 24 = -1，22 = 1。閉回路方法原理就

28、是通過(guò)尋找閉回路來(lái)找到非基變量的檢驗(yàn)數(shù)。 2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 53 如果規(guī)定作為起始頂點(diǎn)的非基變量為第 1 個(gè)頂點(diǎn)，閉回路的其他頂點(diǎn)依次為第 2 個(gè)頂點(diǎn)、第 3 個(gè)頂點(diǎn)，那么就有 ij = (閉回路上的奇數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和) - (閉回路上的偶數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之和) 其中 ij 為非基變量的下角指標(biāo)。2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 54 按上述作法，可計(jì)算出表1的所有非基變量的檢驗(yàn)數(shù)，把它們填入相應(yīng)位置的方括號(hào)內(nèi)，如圖4-11所示。 銷(xiāo)地產(chǎn)地b1b2b3b4產(chǎn)量a13 111 23 410 37a21 39 12 18-14a37

29、104 610125 39銷(xiāo)量365620(產(chǎn)銷(xiāo)平衡)表4-11 初始基本可行解及檢驗(yàn)數(shù)55 顯然，當(dāng)所有非基變量的檢驗(yàn)數(shù)均大于或等于零時(shí)，現(xiàn)行的調(diào)運(yùn)方案就是最優(yōu)方案，因?yàn)榇藭r(shí)對(duì)現(xiàn)行方案作任何調(diào)整都將導(dǎo)致總的運(yùn)輸費(fèi)用增加。 閉回路法的主要缺點(diǎn)是：當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路以及計(jì)算兩方面都會(huì)產(chǎn)生困難。2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 56【解】用最小元素法得到下列一組基本可行解【例例4】求下列運(yùn)輸問(wèn)題的一個(gè)初始基本可行解及其檢驗(yàn)數(shù)。矩陣中的元素為運(yùn)價(jià)cij ，矩陣右邊的元素為產(chǎn)量ai ，下方的元素為銷(xiāo)量bj 。3040601020507029102156748391010

30、30201060x20507010 60 40 3057矩陣中打“”的位置是非基變量，其余是基變量，這里只求非基變量的檢驗(yàn)數(shù)。求11，先找出x11的閉回路 ，對(duì)應(yīng)的運(yùn)價(jià)為再用正負(fù)號(hào)分別交替乘以運(yùn)價(jià)有直接求代數(shù)和得31331311,xxxx31331311,cccc31331311,cccc829893133131111cccc58同理可求出其它非基變量的檢驗(yàn)數(shù)：3951269831063856929570851433232434343313123232121323222231332321211323244114cccccccccccccccccccc這里34 dj 的運(yùn)輸問(wèn)題，得到的數(shù)學(xué)模 i

31、=1 j=1型為2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 812.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 m n min f = cij xij i=1 j=1 n s.t. xij si i = 1,2,m j=1 m xij =dj j = 1,2,n i=1 xij0(i=1,2,m;j=1,2,n) 82 只要在模型中的產(chǎn)量限制約束（前m個(gè)不等式約束）中引入m個(gè)松弛變量xin+1 i= 1,2,m 即可，變?yōu)椋?n xij+xin+1=si i=1,2,mj=1然后，需設(shè)一個(gè)銷(xiāo)地b n+1,它的銷(xiāo)量為： m n bn+1= si- d dj j i=1 j=1

32、2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 83 這里，松弛變量 x i n+1 可以視為從產(chǎn)地 a i 運(yùn)往銷(xiāo)地 b n+1 的運(yùn)輸量，由于實(shí)際并不運(yùn)送，它們的運(yùn)費(fèi)為 c i n+1 = 0 i = 1,2,m。于是，這個(gè)運(yùn)輸問(wèn)題就轉(zhuǎn)化成了一個(gè)產(chǎn)銷(xiāo)平衡的問(wèn)題。2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 84 例4.2:某公司從兩個(gè)產(chǎn)地a1、a2將物品運(yùn)往三個(gè)銷(xiāo)地b1、b2、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)用最小？ b1 b2 b3 產(chǎn)產(chǎn)量量 a1 6 4 6 300 a2 6 5 5 300 銷(xiāo)銷(xiāo)量

33、量 150 150 200 2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 85 解：增加一個(gè)虛設(shè)的銷(xiāo)地運(yùn)輸費(fèi)用為0 b1 b2 b3 b4 產(chǎn)量 a1 6 4 6 0 300 a2 6 5 5 0 300 銷(xiāo)量 150 150 200 100 2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 86 2.銷(xiāo)量大于產(chǎn)量的情況 m n 考慮sidj的運(yùn)輸問(wèn)題，得到的數(shù)學(xué)模型為 i=1 j=12.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 m n min f = cij xij i=1 j=1 n s.t. xij =si i = 1,2,m j=1 m xij dj j =

34、1,2,n i=1 xij0(i=1,2,m;j=1,2,n) 87 只要在模型中的產(chǎn)量限制約束（后n個(gè)不等式約束）中引入n個(gè)松弛變量xm+1j j = 1,2,n即可，變?yōu)椋?m xij+xm+1j=dj j=1,2,mi=1然后，需設(shè)一個(gè)產(chǎn)地a m+1,它的銷(xiāo)量為： n m am+1= dj - si j=1 i=12.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 88 這里，松弛變量 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)題。2.2.

35、運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 89 例4.3:某公司從兩個(gè)產(chǎn)地a1、a2將物品運(yùn)往三個(gè)銷(xiāo)地b1、b2、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)用最??？ b1 b2 b3 產(chǎn)量 a1 6 4 6 200 a2 6 5 5 300 銷(xiāo)量 250 200 200 2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解 表上作業(yè)法表上作業(yè)法 90 解：增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為0 b1 b2 b3 產(chǎn)量 a1 6 4 6 200 a2 6 5 5 300 a3 0 0 0 150 銷(xiāo)量 250 200 200 2.2.運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解

36、 表上作業(yè)法表上作業(yè)法 91 例4.4:石家莊北方研究院有一、二、三，三個(gè)區(qū)。每年分別需要用煤3000、1000、2000t，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價(jià)格、質(zhì)量相同。供應(yīng)能力分別為1500、4000t，運(yùn)價(jià)如下表。由于需大于供，經(jīng)院研究決定一區(qū)供應(yīng)量可減少0300t，二區(qū)必須滿足需求量，三區(qū)供應(yīng)量不少于1700t，試求總費(fèi)用為最低的調(diào)運(yùn)方案。 一區(qū) 二區(qū) 三區(qū) 產(chǎn)量 山西盂縣 1.65 1.70 1.75 4000 河北臨城 1.60 1.65 1.70 1500 需要量 3000 1000 2000 3.3.運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用92 解:根據(jù)題意，作出產(chǎn)銷(xiāo)平衡與運(yùn)價(jià)表：

37、 取 m 代表一個(gè)很大的正數(shù)，其作用是強(qiáng)迫相應(yīng)的 x31、x33、x34取值為0。 一區(qū) 一區(qū) 二區(qū) 三區(qū) 三區(qū) 產(chǎn)量 山西盂縣 1.65 1.65 1.70 1.75 1.75 4000 河北臨城 1.60 1.60 1.65 1.70 1.70 1500 假想生產(chǎn)點(diǎn) m 0 m m 0 500 需要量 2700 300 1000 1700 300 3.3.運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用93 例4.5:設(shè)有a、b、c三個(gè)化肥廠供應(yīng)1、2、3、4四個(gè)地區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表。試求總費(fèi)用為最低的化肥調(diào)撥方案。 1 2 3 4 產(chǎn)量 a 16 13 22 17 50 b 14 1

38、3 19 15 60 c 19 20 23 - 50 最低需要量 30 70 0 10 最高需要量 50 70 30 不限 3.3.運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用94 解：解：根據(jù)題意，作出產(chǎn)銷(xiāo)平衡與運(yùn)價(jià)表:最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為 m ，而最高要求與最低要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為 0 。對(duì)應(yīng) 4”的銷(xiāo)量 50 是考慮問(wèn)題本身適當(dāng)取的數(shù)據(jù)，根據(jù)產(chǎn)銷(xiāo)平衡要求確定 d的產(chǎn)量為 50。 1 1” 2 3 4 4” 產(chǎn)量 a 16 16 13 22 17 17 50 b 14 14 13 19 15 15 60 c 19 19 20 23 m m 50 d

39、 m 0 m 0 m 0 50 銷(xiāo)量 30 20 70 30 10 50 3.3.運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用95 生產(chǎn)與儲(chǔ)存問(wèn)題生產(chǎn)與儲(chǔ)存問(wèn)題 例例4.6:4.6:某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如右表。如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用0.15萬(wàn)元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。生產(chǎn)能力（臺(tái)） 單位成本（萬(wàn)元）一季度2510.8二季度3511.1三季度3011.0四季度1011.33.3.運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用96 交貨：

40、生產(chǎn)：x11 = 10 x11 + x12 + x13 + x14 25x12 + x22 = 15 x22 + x23 + x24 35x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10 解：解： 設(shè)設(shè) x xijij為第為第 i i 季度生產(chǎn)的第季度生產(chǎn)的第 j j 季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足：季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足：3.3.運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用97把第 i 季度生產(chǎn)的柴油機(jī)數(shù)目看作第 i 個(gè)生產(chǎn)廠的產(chǎn)量；把第 j 季度交貨的柴油機(jī)數(shù)目看作第 j 個(gè)銷(xiāo)售點(diǎn)的銷(xiāo)量；成本加儲(chǔ)存、維護(hù)等費(fèi)

41、用看作運(yùn)費(fèi)。可構(gòu)造下列產(chǎn)銷(xiāo)平衡問(wèn)題：目標(biāo)函數(shù)：min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 第 一 季 度 第 二 季 度 第 三 季 度 第 四 季 度 d 產(chǎn) 量 第 一 季 度 10.80 10.95 11.10 11.2 0 25 第 二 季 度 m 11.10 11.25 11.40 0 35 第 三 季 度 m m 11.00 11.15 0 30 第 四 季 度 m m m 11.30 0 10 銷(xiāo) 量 1

42、0 15 25 20 30 3.3.運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用98 生產(chǎn)與儲(chǔ)存問(wèn)題 例4.7:光明儀器廠生產(chǎn)電腦繡花機(jī)是以產(chǎn)定銷(xiāo)的。已知1至6月份各月的生產(chǎn)能力、合同銷(xiāo)量和單臺(tái)電腦繡花機(jī)平均生產(chǎn)費(fèi)用見(jiàn)下表： 正常生產(chǎn)能力（臺(tái)） 加班生產(chǎn)能力（臺(tái)） 銷(xiāo)量（臺(tái)） 單臺(tái)費(fèi)用（萬(wàn)元）1月份6010104152月份501075143月份902011513.54月份10040160135月份10040103136月份80407013.53.3.運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用99 已知上年末庫(kù)存103臺(tái)繡花機(jī)，如果當(dāng)月生產(chǎn)出來(lái)的機(jī)器當(dāng)月不交貨，則需要運(yùn)到分廠庫(kù)房，每臺(tái)增加運(yùn)輸成本0.1萬(wàn)元,每臺(tái)機(jī)器每月的平

43、均倉(cāng)儲(chǔ)費(fèi)、維護(hù)費(fèi)為0.2萬(wàn)元。在7-8月份銷(xiāo)售淡季，全廠停產(chǎn)1個(gè)月，因此在6月份完成銷(xiāo)售合同后還要留出庫(kù)存80臺(tái)。加班生產(chǎn)機(jī)器每臺(tái)增加成本1萬(wàn)元。問(wèn)應(yīng)如何安排1-6月份的生產(chǎn)，可使總的生產(chǎn)費(fèi)用（包括運(yùn)輸、倉(cāng)儲(chǔ)、維護(hù)）最少？運(yùn)輸問(wèn)題（運(yùn)輸問(wèn)題（7 7）3 3 運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用100 解： 這個(gè)生產(chǎn)存儲(chǔ)問(wèn)題可化為運(yùn)輸問(wèn)題來(lái)做。考慮：各月生產(chǎn)與交貨分別視為產(chǎn)地和銷(xiāo)地。 1）1-6月份合計(jì)生產(chǎn)能力（包括上年末儲(chǔ)存量）為743臺(tái)，銷(xiāo)量為707臺(tái)。設(shè)一假想銷(xiāo)地銷(xiāo)量為36； 2）上年末庫(kù)存103臺(tái)，只有倉(cāng)儲(chǔ)費(fèi)和運(yùn)輸費(fèi)，把它列為的0行； 3）6月份的需求除70臺(tái)銷(xiāo)量外，還要80臺(tái)庫(kù)存，其需求應(yīng)為7

44、0+80=150臺(tái)； 4）1-6表示1-6月份正常生產(chǎn)情況， 1-6表示1-6月份加班生產(chǎn)情況。3.3.運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用101產(chǎn)銷(xiāo)平衡與運(yùn)價(jià)表： 1 月 2 月 3 月 4 月 5 月 6 月 虛銷(xiāo)地 正常產(chǎn)量 加班產(chǎn)量 0 0.3 0.5 0.7 0.9 1.1 1.3 0 103 1 15 15.3 15.5 15.7 15.9 16.1 0 60 1 16 16.3 16.5 16.7 6.9 17.1 0 10 2 m 14 14.3 14.5 14.7 14.9 0 50 2 m 15 15.3 15.5 15.7 15.9 0 10 3 m m 13.5 13.8 14

45、.0 14.2 0 90 3 m m 14.5 14.8 15.0 15.2 0 20 4 m m m 13.0 13.3 13.5 0 100 4 m m m 14.0 14.3 14.5 0 40 5 m m m m 13.0 13.3 0 100 5 m m m m 14.0 14.3 0 40 6 m m m m m 13.5 0 80 6 m m m m m 14.5 0 40 銷(xiāo)量 104 75 115 160 103 150 36 - 3.3.運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用102 例4.8:騰飛電子儀器公司在大連和廣州有兩個(gè)分廠生產(chǎn)同一種儀器，大連分廠每月生產(chǎn)450臺(tái),廣州分廠每月

46、生產(chǎn)600臺(tái)。該公司在上海和天津有兩個(gè)銷(xiāo)售公司負(fù)責(zé)對(duì)南京、濟(jì)南、南昌、青島四個(gè)城市的儀器供應(yīng)。另外因?yàn)榇筮B距離青島較近，公司同意大連分廠向青島直接供貨，運(yùn)輸費(fèi)用如下圖，單位是百元。問(wèn)應(yīng)該如何調(diào)運(yùn)儀器，可使總運(yùn)輸費(fèi)用最低？ 三、轉(zhuǎn)運(yùn)問(wèn)題三、轉(zhuǎn)運(yùn)問(wèn)題: :原運(yùn)輸問(wèn)題上增加若干轉(zhuǎn)運(yùn)站。運(yùn)輸方式有：產(chǎn)地 轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)站 銷(xiāo)地、產(chǎn)地 產(chǎn)地、產(chǎn)地 銷(xiāo)地、銷(xiāo)地 轉(zhuǎn)運(yùn)站、銷(xiāo)地 產(chǎn)地等。3.3.運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用103圖中 1廣州、2大連、3上海、4天津 5南京、6濟(jì)南、7南昌、8青島3.3.運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用450104 解：解：設(shè) xij 為從 i 到 j 的運(yùn)輸量，可得到有下列特點(diǎn)的線

47、性規(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)量3.3.運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用105約束條件： s.t. x13+x14 600 (廣州分廠供應(yīng)量限制） x23+x24+x28 450 (大連分廠供應(yīng)量限制） -x13-x23+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 3.3.運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用106-x14- x