運(yùn)籌學(xué) 運(yùn)輸問(wèn)題

1、1 第第4 4章章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 2 運(yùn)輸問(wèn)題與有關(guān)概念運(yùn)輸問(wèn)題與有關(guān)概念 運(yùn)輸問(wèn)題的求解運(yùn)輸問(wèn)題的求解表上作業(yè)法表上作業(yè)法 運(yùn)輸問(wèn)題應(yīng)用運(yùn)輸問(wèn)題應(yīng)用建模建模 本章內(nèi)容重點(diǎn)本章內(nèi)容重點(diǎn) 3 4.1 4.1 運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 4.1.1 4.1.1 問(wèn)題的提出問(wèn)題的提出 一般的運(yùn)輸問(wèn)題就是要解決把某一般的運(yùn)輸問(wèn)題就是要解決把某 種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè) 銷(xiāo)地，在每個(gè)產(chǎn)地的供應(yīng)量與每個(gè)銷(xiāo)地，在每個(gè)產(chǎn)地的供應(yīng)量與每個(gè) 銷(xiāo)地的需求量已知，并知道各地之銷(xiāo)地的需求量已知，并知道各地之 間的運(yùn)輸單價(jià)的前提下，如何確定間的運(yùn)輸單價(jià)的前提下，如

2、何確定 一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案。一個(gè)使得總的運(yùn)輸費(fèi)用最小的方案。 4 4.1 運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 例例4.1:某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地A1、A2將物將物 品運(yùn)往三個(gè)銷(xiāo)地品運(yùn)往三個(gè)銷(xiāo)地B1、B2、B3，各產(chǎn)地的，各產(chǎn)地的 產(chǎn)量、各銷(xiāo)地的銷(xiāo)量和各產(chǎn)地運(yùn)往各銷(xiāo)產(chǎn)量、各銷(xiāo)地的銷(xiāo)量和各產(chǎn)地運(yùn)往各銷(xiāo) 地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)地每件物品的運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng) 如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。咳绾握{(diào)運(yùn)可使總運(yùn)輸費(fèi)用最?。?B1 B2 B3 產(chǎn)量產(chǎn)量 A1 6 4 6 200 A2 6 5 5 300 銷(xiāo)量銷(xiāo)量 150 150 200 5 解：解： 產(chǎn)銷(xiāo)平衡問(wèn)題

3、：產(chǎn)銷(xiāo)平衡問(wèn)題： 總產(chǎn)量總產(chǎn)量 = = 總銷(xiāo)量總銷(xiāo)量 設(shè)設(shè) xij 為從產(chǎn)地為從產(chǎn)地Ai運(yùn)往銷(xiāo)地運(yùn)往銷(xiāo)地Bj的運(yùn)輸?shù)倪\(yùn)輸 量，得到下列運(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 4.1 運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 6 Min f = 6x11+4x12+6x13+6x21+5x22+5x23 s.t. x11+ x12 + x13 = 200 x21 + x22+ x23 = 300 x11 + x21 = 150 x12 + x22 = 150 x

4、13 + x23 = 200 xij0(i=1,2；j=1,2,3） 4.1 4.1 運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 7 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ù)矩陣系數(shù)矩陣 4.1 4.1 運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 8 模型系數(shù)矩陣特征模型系數(shù)矩陣特征 1.共有共有m + n 行，分別表示各產(chǎn)地和行，分別表示各產(chǎn)地和 銷(xiāo)地；銷(xiāo)地；m n 列，分別表示各決策變列，分別表示各決策變 量；量； 2.每列只有兩個(gè)每列只有兩個(gè) 1，其余為，其余為 0，分別，分別 表示只有一個(gè)產(chǎn)地和一個(gè)

5、銷(xiāo)地被使表示只有一個(gè)產(chǎn)地和一個(gè)銷(xiāo)地被使 用。用。 4.1 4.1 運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 9 一般運(yùn)輸問(wèn)題的提法：一般運(yùn)輸問(wèn)題的提法： 假設(shè)假設(shè) A1, A2,Am 表示某物資的表示某物資的m個(gè)個(gè) 產(chǎn)地；產(chǎn)地；B1,B2,Bn 表示某物資的表示某物資的n個(gè)銷(xiāo)地；個(gè)銷(xiāo)地； si表示產(chǎn)地表示產(chǎn)地 Ai 的產(chǎn)量；的產(chǎn)量；dj 表示銷(xiāo)地表示銷(xiāo)地 Bj 的的 銷(xiāo)量；銷(xiāo)量；cij 表示把物資從產(chǎn)地表示把物資從產(chǎn)地 Ai 運(yùn)往銷(xiāo)地運(yùn)往銷(xiāo)地 Bj 的單位運(yùn)價(jià)（表的單位運(yùn)價(jià)（表4-3）。如果）。如果 s1 + s2 + + sm = d1 + d2 + + dn 則稱(chēng)為產(chǎn)銷(xiāo)平衡問(wèn)題；否則，

6、稱(chēng)產(chǎn)銷(xiāo)不則稱(chēng)為產(chǎn)銷(xiāo)平衡問(wèn)題；否則，稱(chēng)產(chǎn)銷(xiāo)不 平衡。首先討論產(chǎn)銷(xiāo)平衡問(wèn)題。平衡。首先討論產(chǎn)銷(xiāo)平衡問(wèn)題。 4.1.2 一般運(yùn)輸問(wèn)題的線性規(guī)劃模型及求解思路一般運(yùn)輸問(wèn)題的線性規(guī)劃模型及求解思路 10 表表4-3 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題數(shù)據(jù)數(shù)據(jù)表表 4.1 運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 銷(xiāo)地銷(xiāo)地 產(chǎn)地產(chǎn)地 B1 B2 Bn產(chǎn)量產(chǎn)量 A1 A2 Am c11 c12 c1n c21 c22 c2n cm1 cm2 cmn s1 s2 sm 銷(xiāo)量銷(xiāo)量d1 d2 dn 設(shè)設(shè) xij 為從產(chǎn)地為從產(chǎn)地 Ai 運(yùn)往銷(xiāo)地運(yùn)往銷(xiāo)地 Bj 的運(yùn)輸量，的運(yùn)輸量， 根據(jù)這個(gè)運(yùn)輸問(wèn)題的要求，可以建立運(yùn)輸根據(jù)這個(gè)運(yùn)

7、輸問(wèn)題的要求，可以建立運(yùn)輸 變量表（表變量表（表 4-4）。）。 11 表表4-4 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題變量變量表表 4.1 運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 銷(xiāo)地銷(xiāo)地 產(chǎn)地產(chǎn)地 B1 B2 Bn產(chǎn)量產(chǎn)量 A1 A2 Am x11 x12 x1n x21 x22 x2n xm1 xm2 xmn s1 s2 sm 銷(xiāo)量銷(xiāo)量d1 d2 dn m n Min Min f = cij xij i=1 j=1 n s.ts.t. . xij = si i = 1,2,m (4-5) (4-5) j =1 m xij = dj j = 1,2,n (4-6) (4-6) i =1 xij 0 (

8、(i=1,2,m;j=1,2,n) ) 4.1 4.1 運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 對(duì)于產(chǎn)銷(xiāo)平衡問(wèn)題，可得到下列運(yùn)輸對(duì)于產(chǎn)銷(xiāo)平衡問(wèn)題，可得到下列運(yùn)輸 問(wèn)題的模型：?jiǎn)栴}的模型： 13 運(yùn)輸問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題，運(yùn)輸問(wèn)題是一種特殊的線性規(guī)劃問(wèn)題， 在求解時(shí)依然可以采用單純形法的思路，在求解時(shí)依然可以采用單純形法的思路， 如圖如圖4-14-1所示所示。 由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果 直接使用線性規(guī)劃單純形法求解計(jì)算，則直接使用線性規(guī)劃單純形法求解計(jì)算，則 無(wú)法利用這些有利條件。人們?cè)诜治鲞\(yùn)輸無(wú)法利用這些有利條件。人們?cè)诜治鲞\(yùn)輸 規(guī)劃系

9、數(shù)矩陣特征的基礎(chǔ)上建立了針對(duì)運(yùn)規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對(duì)運(yùn) 輸問(wèn)題的輸問(wèn)題的表上作業(yè)法表上作業(yè)法。 下面主要討論下面主要討論基本可行解、檢驗(yàn)數(shù)基本可行解、檢驗(yàn)數(shù)以及以及 基的轉(zhuǎn)換基的轉(zhuǎn)換等問(wèn)題。等問(wèn)題。 續(xù)下頁(yè)續(xù)下頁(yè) 產(chǎn)銷(xiāo)平衡運(yùn)輸模型求解產(chǎn)銷(xiāo)平衡運(yùn)輸模型求解 14 產(chǎn)銷(xiāo)平衡運(yùn)輸模型求解過(guò)程產(chǎn)銷(xiāo)平衡運(yùn)輸模型求解過(guò)程 基本 可行解 是否 最優(yōu)解 結(jié)束 換基 是 否 圖圖4-1 4-1 運(yùn)輸問(wèn)題的求解思路運(yùn)輸問(wèn)題的求解思路返回 15 產(chǎn)銷(xiāo)平衡運(yùn)輸模型數(shù)據(jù)表產(chǎn)銷(xiāo)平衡運(yùn)輸模型數(shù)據(jù)表 銷(xiāo)地銷(xiāo)地 產(chǎn)地產(chǎn)地 B1B2Bn產(chǎn)量產(chǎn)量 A1 c11 x11 c12 x12 c1n x1n a1 A2 c21

10、 x21 c22 x22 c2n x2n a2 Amcm1 xm1 cm2 xm2 cmn xmn am 銷(xiāo)量銷(xiāo)量b1b2bn 16 運(yùn)輸問(wèn)題的基變量共有運(yùn)輸問(wèn)題的基變量共有 m + n -1 個(gè)，系數(shù)矩陣個(gè)，系數(shù)矩陣A的秩為的秩為 m + n -1。 運(yùn)輸問(wèn)題的運(yùn)輸問(wèn)題的 m + n -1 個(gè)變量構(gòu)成個(gè)變量構(gòu)成 基變量的充分必要條件是不含閉基變量的充分必要條件是不含閉 回路?；芈?。 閉回路、閉回路的頂點(diǎn)閉回路、閉回路的頂點(diǎn) 運(yùn)輸運(yùn)輸模型模型的基變量的基變量 17 定義定義4.1 在表在表4-5的決策變量格中，凡是能的決策變量格中，凡是能 夠排列成下列形式的夠排列成下列形式的 xab ,xac

11、 ,xdc ,xde ,xst ,xsb (4-7) 或或 xab ,xcb ,xcd ,xed ,xst ,xat (4-8) 其中，其中，a,d,s 各不相同；各不相同；b,c,t 各不相同，各不相同， 我們稱(chēng)之為變量集合的一個(gè)我們稱(chēng)之為變量集合的一個(gè)閉回路閉回路，并將式，并將式 （4-7）、式（）、式（4-8）中的變量稱(chēng)為這個(gè)閉回路）中的變量稱(chēng)為這個(gè)閉回路 的頂點(diǎn)。的頂點(diǎn)。 為了說(shuō)明這個(gè)特征，我們不加證明的給為了說(shuō)明這個(gè)特征，我們不加證明的給 出一些概念和結(jié)論。下面的討論建立在表出一些概念和結(jié)論。下面的討論建立在表4-54-5 中決策變量格的基礎(chǔ)上。中決策變量格的基礎(chǔ)上。 4.1 4.1

12、 運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 18 例如，例如，x13, x16, x36, x34, x24, x23 ； x23, x53, x55, x45, x41, x21 ； x11, x14, x34, x31等都是閉回路。等都是閉回路。 若把閉回路的各變量格看作節(jié)點(diǎn)，在表若把閉回路的各變量格看作節(jié)點(diǎn)，在表 中可以畫(huà)出如下形式的閉回路：中可以畫(huà)出如下形式的閉回路： 4.1 4.1 運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 閉回路示意圖閉回路示意圖 19 根據(jù)定義可以看出閉回路的一些根據(jù)定義可以看出閉回路的一些 明顯特點(diǎn)：明顯特點(diǎn)： (1)(1)閉回路均為一封閉折線，它閉回路

13、均為一封閉折線，它 的每一條邊，或?yàn)樗降?，或?yàn)榇怪钡拿恳粭l邊，或?yàn)樗降模驗(yàn)榇怪?的；的； (2)(2)閉回路的每一條邊（水平的閉回路的每一條邊（水平的 或垂直的）均有且僅有兩個(gè)閉回路的或垂直的）均有且僅有兩個(gè)閉回路的 頂點(diǎn)（變量格）。頂點(diǎn)（變量格）。 4.1 4.1 運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 20 (1) 設(shè)設(shè) xab , xac , xdc , xde , xst , xsb 是一是一 個(gè)閉回路，那么該閉回路中變量所對(duì)應(yīng)個(gè)閉回路，那么該閉回路中變量所對(duì)應(yīng) 的系數(shù)列向量的系數(shù)列向量 pab , pac , pdc , pde , pst , psb 線性相關(guān)；線性相關(guān)

14、； (2) 若變量組若變量組 xab , xcd , xef , xst 中包含中包含 一個(gè)部分組構(gòu)成閉回路，那么該變量組一個(gè)部分組構(gòu)成閉回路，那么該變量組 所對(duì)應(yīng)的系數(shù)列向量所對(duì)應(yīng)的系數(shù)列向量 pab , pcd, pef , pst 線性相關(guān)。線性相關(guān)。 根據(jù)上述結(jié)論以及線性規(guī)劃基變量根據(jù)上述結(jié)論以及線性規(guī)劃基變量 的特點(diǎn)，可以得到下面重要定理及其推的特點(diǎn)，可以得到下面重要定理及其推 論。論。 關(guān)于閉回路有如下的一些重要結(jié)論關(guān)于閉回路有如下的一些重要結(jié)論 定理定理4.1 變量組變量組 xab , xcd , xef , xst 所所 對(duì)應(yīng)的系數(shù)列向量對(duì)應(yīng)的系數(shù)列向量 pab , pcd ,

15、 pef , pst 線性無(wú)關(guān)的充分必要條件是這個(gè)變量線性無(wú)關(guān)的充分必要條件是這個(gè)變量 組中組中不包含閉回路不包含閉回路。 推論推論 產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的 m + n -1 個(gè)變量個(gè)變量構(gòu)成基變量的充分必要條件是構(gòu)成基變量的充分必要條件是 它不含閉回路。它不含閉回路。 這個(gè)推論給出了運(yùn)輸問(wèn)題基本解這個(gè)推論給出了運(yùn)輸問(wèn)題基本解 的重要性質(zhì)，也為尋求基本可行解提的重要性質(zhì)，也為尋求基本可行解提 供了依據(jù)。供了依據(jù)。 4.1 4.1 運(yùn)輸問(wèn)題模型及有關(guān)概念運(yùn)輸問(wèn)題模型及有關(guān)概念 4.2 4.2 運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 表上作業(yè)法求解運(yùn)輸問(wèn)題的思想和表上作業(yè)法求解

16、運(yùn)輸問(wèn)題的思想和 單純形法完全類(lèi)似：?jiǎn)渭冃畏ㄍ耆?lèi)似： 確定一個(gè)初始基本可行解確定一個(gè)初始基本可行解 根根 據(jù)最優(yōu)性判別準(zhǔn)則來(lái)檢查這個(gè)基本可行據(jù)最優(yōu)性判別準(zhǔn)則來(lái)檢查這個(gè)基本可行 解是不是最優(yōu)的？解是不是最優(yōu)的？ 如果是，則計(jì)算結(jié)束；如果是，則計(jì)算結(jié)束； 如果不是，則進(jìn)行換基。如果不是，則進(jìn)行換基。 直至求出最優(yōu)解為止。直至求出最優(yōu)解為止。 23 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 一、初始基本可行解的確定一、初始基本可行解的確定 根據(jù)上面的討論，要求得運(yùn)輸問(wèn)根據(jù)上面的討論，要求得運(yùn)輸問(wèn) 題的初始基本可行解，必須保證找題的初始基本可行解，必須保證找 到到 m + n 1 個(gè)

17、不構(gòu)成閉回路的基變個(gè)不構(gòu)成閉回路的基變 量。量。 一般的方法步驟如下：一般的方法步驟如下： 24 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 (1)在運(yùn)輸問(wèn)題求解作業(yè)數(shù)據(jù)表中在運(yùn)輸問(wèn)題求解作業(yè)數(shù)據(jù)表中任選任選 一個(gè)單元格一個(gè)單元格 xij ( Ai 行行 Bj 列交叉位置上列交叉位置上 的格的格), 令令 xij = min ai , bj 即從即從 Ai 向向 Bj 運(yùn)最大量運(yùn)最大量(使行或列使行或列 在允許的范圍內(nèi)盡量飽和，即使一個(gè)在允許的范圍內(nèi)盡量飽和，即使一個(gè) 約束方程得以滿足約束方程得以滿足) , 填入填入 xij 的相應(yīng)的相應(yīng) 位置；位置； 25 運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題

18、求解表上作業(yè)法表上作業(yè)法 (2) 從從 ai 和和 bj 中分別減去中分別減去 xij 的值，修的值，修 正為新的正為新的ai 和和 bj 即調(diào)整即調(diào)整 Ai 的擁有量及的擁有量及 Bj 的需求量；的需求量； (3) 若若 ai = 0，則劃去對(duì)應(yīng)的行（已經(jīng)，則劃去對(duì)應(yīng)的行（已經(jīng) 把擁有的量全部運(yùn)走），若把擁有的量全部運(yùn)走），若 bj = 0 則劃則劃 去對(duì)應(yīng)的列（已經(jīng)把需要的量全部運(yùn)去對(duì)應(yīng)的列（已經(jīng)把需要的量全部運(yùn) 來(lái)），且每次只劃去一行或一列（即每來(lái)），且每次只劃去一行或一列（即每 次要去掉且只去掉一個(gè)約束）；次要去掉且只去掉一個(gè)約束）； 26 運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法

19、 (4) 當(dāng)最終的運(yùn)輸量選定時(shí)，其所在當(dāng)最終的運(yùn)輸量選定時(shí)，其所在 行、列同時(shí)滿足，此時(shí)要同時(shí)劃去行、列同時(shí)滿足，此時(shí)要同時(shí)劃去 一行和一列。這樣，運(yùn)輸平衡表中一行和一列。這樣，運(yùn)輸平衡表中 所有的行與列均被劃去，則得到了所有的行與列均被劃去，則得到了 一個(gè)初始基本可行解。一個(gè)初始基本可行解。 否則在剩下的運(yùn)輸平衡表中選下否則在剩下的運(yùn)輸平衡表中選下 一個(gè)變量，返回一個(gè)變量，返回(1)。 27 上述計(jì)算過(guò)程可用流程圖描述如下（圖上述計(jì)算過(guò)程可用流程圖描述如下（圖4-2） 取未劃去的單元格取未劃去的單元格xij ,令令 xij = min ai , bj ai = ai - xij bj = b

20、j - xij ai = 0?劃去第劃去第i行行 劃去第劃去第j列列 是是 否否 bj = 0 否否 所有行列是所有行列是 否均被劃去否均被劃去 是是 找到初始基找到初始基 本可行解本可行解 圖圖4-2 求運(yùn)輸問(wèn)題的初始基本可行解過(guò)程求運(yùn)輸問(wèn)題的初始基本可行解過(guò)程 注：為了方便，這注：為了方便，這 里總記剩余的產(chǎn)量里總記剩余的產(chǎn)量 和銷(xiāo)量為和銷(xiāo)量為ai, bj 28 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 按照上述方法所產(chǎn)生的一組變量的按照上述方法所產(chǎn)生的一組變量的 取值將滿足下面條件：取值將滿足下面條件： (1)所得的變量均為非負(fù)，且變量所得的變量均為非負(fù)，且變量 總數(shù)恰好

21、為總數(shù)恰好為 m + n 1 個(gè)；個(gè)； (2)所有的約束條件均得到滿足；所有的約束條件均得到滿足； (3)所得的變量不構(gòu)成閉回路。所得的變量不構(gòu)成閉回路。 29 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 在上面的方法中，在上面的方法中，xij 的選取方的選取方 法并沒(méi)有給予限制，若采取不同的規(guī)法并沒(méi)有給予限制，若采取不同的規(guī) 則來(lái)選取則來(lái)選取 xij ，則得到不同的方法，則得到不同的方法， 較常用的方法有西北角法和最小元素較常用的方法有西北角法和最小元素 法。下面分別舉例予以說(shuō)明法。下面分別舉例予以說(shuō)明。 30 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 1 1、

22、初始基本可行解的確定、初始基本可行解的確定 （1 1）西北角法）西北角法：從西北角（左上：從西北角（左上 角）格開(kāi)始，在格內(nèi)的右下角標(biāo)上允角）格開(kāi)始，在格內(nèi)的右下角標(biāo)上允 許取得的最大數(shù)。然后按行（列）標(biāo)許取得的最大數(shù)。然后按行（列）標(biāo) 下一格的數(shù)。若某行（列）的產(chǎn)量下一格的數(shù)。若某行（列）的產(chǎn)量 （銷(xiāo)量）已滿足，則把該行（列）的（銷(xiāo)量）已滿足，則把該行（列）的 其他格劃去。如此進(jìn)行下去，直至得其他格劃去。如此進(jìn)行下去，直至得 到一個(gè)基本可行解。到一個(gè)基本可行解。 31 （2）最小元素法最小元素法：從運(yùn)價(jià)最?。簭倪\(yùn)價(jià)最小 的格開(kāi)始，在格內(nèi)的右下角標(biāo)上允的格開(kāi)始，在格內(nèi)的右下角標(biāo)上允 許取得的最

23、大數(shù)。然后按運(yùn)價(jià)從小許取得的最大數(shù)。然后按運(yùn)價(jià)從小 到大順序填數(shù)。若某行（列）的產(chǎn)到大順序填數(shù)。若某行（列）的產(chǎn) 量（銷(xiāo)量）已滿足，則把該行（列）量（銷(xiāo)量）已滿足，則把該行（列） 的其他格劃去。如此進(jìn)行下去，直的其他格劃去。如此進(jìn)行下去，直 至得到一個(gè)基本可行解。至得到一個(gè)基本可行解。 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 32 注注: :應(yīng)用西北角法和最小元素應(yīng)用西北角法和最小元素 法，每次填完數(shù)，都只劃去一行或法，每次填完數(shù)，都只劃去一行或 一列，只有一列，只有最后一個(gè)元例外最后一個(gè)元例外（同時(shí)（同時(shí) 劃去一行和一列）。當(dāng)填上一個(gè)數(shù)劃去一行和一列）。當(dāng)填上一個(gè)數(shù) 后行、

24、列同時(shí)飽和時(shí)，也應(yīng)任意劃后行、列同時(shí)飽和時(shí)，也應(yīng)任意劃 去一行（列），在保留的列（行）去一行（列），在保留的列（行） 中沒(méi)被劃去的格內(nèi)任選一個(gè)格標(biāo)中沒(méi)被劃去的格內(nèi)任選一個(gè)格標(biāo)0 0。 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 4.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 4.2 運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 35 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 36 最優(yōu)性檢驗(yàn)就是檢查所得到的方案最優(yōu)性檢驗(yàn)就是檢查所得到的方案 是不是最優(yōu)方案。檢查的方法與單純形是不是最優(yōu)方案。檢查的方法與單純形 方法中的原理相同，即計(jì)算檢驗(yàn)數(shù)。由方法中的原理相同

25、，即計(jì)算檢驗(yàn)數(shù)。由 于目標(biāo)要求極小，因此，當(dāng)所有的檢驗(yàn)于目標(biāo)要求極小，因此，當(dāng)所有的檢驗(yàn) 數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最 優(yōu)方案；否則就不是最優(yōu)，需要進(jìn)行調(diào)優(yōu)方案；否則就不是最優(yōu)，需要進(jìn)行調(diào) 整。下面介紹兩種求檢驗(yàn)數(shù)的方法整。下面介紹兩種求檢驗(yàn)數(shù)的方法: : 閉閉 回路法回路法和和位勢(shì)法位勢(shì)法 二、基本可行解的最優(yōu)性檢驗(yàn)二、基本可行解的最優(yōu)性檢驗(yàn) 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 37 1、閉回路法、閉回路法 為了方便，我們以表為了方便，我們以表1給出的初始基本可給出的初始基本可 行解方案為例，考察初始方案的任意一個(gè)非行解方案為例，

26、考察初始方案的任意一個(gè)非 基變量，比如基變量，比如 x24。根據(jù)初始方案，產(chǎn)地。根據(jù)初始方案，產(chǎn)地 A2 的的 產(chǎn)品是不運(yùn)往銷(xiāo)地產(chǎn)品是不運(yùn)往銷(xiāo)地 B4 的。如果現(xiàn)在改變初始的。如果現(xiàn)在改變初始 方案，把方案，把 A2 的產(chǎn)品運(yùn)送的產(chǎn)品運(yùn)送1 個(gè)單位給個(gè)單位給 B4 ，那么，那么 為了保持產(chǎn)銷(xiāo)平衡，就必須使為了保持產(chǎn)銷(xiāo)平衡，就必須使 x14 或或 x34 減少減少 1 個(gè)單位；而如果個(gè)單位；而如果 x14 減少減少 1 個(gè)單位，第個(gè)單位，第 1 行行 的運(yùn)輸量就必須增加的運(yùn)輸量就必須增加 1 個(gè)單位，例如個(gè)單位，例如 x13 增加增加 1 個(gè)單位，那么為了保持產(chǎn)銷(xiāo)平衡，就必須使個(gè)單位，那么為了保

27、持產(chǎn)銷(xiāo)平衡，就必須使 x23 減少減少 1 個(gè)單位。個(gè)單位。 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 38 這個(gè)過(guò)程就是尋找一個(gè)以非基變量這個(gè)過(guò)程就是尋找一個(gè)以非基變量x24為為 起始頂點(diǎn)的閉回路起始頂點(diǎn)的閉回路x24，x14，x13，x23， 這個(gè)閉回路的其他頂點(diǎn)均為基變量這個(gè)閉回路的其他頂點(diǎn)均為基變量(對(duì)應(yīng)著對(duì)應(yīng)著 填上數(shù)字的格填上數(shù)字的格)。容易計(jì)算出上述調(diào)整使總。容易計(jì)算出上述調(diào)整使總 的運(yùn)輸費(fèi)用發(fā)生的變化為的運(yùn)輸費(fèi)用發(fā)生的變化為 8 10 + 3 2 - 1 ，即總的運(yùn)費(fèi)減少，即總的運(yùn)費(fèi)減少 1 個(gè)單位，這就說(shuō)明原個(gè)單位，這就說(shuō)明原 始方案不是最優(yōu)方案，可以進(jìn)行調(diào)整

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

29、出以非基變量 x22 為起為起 始頂點(diǎn)的閉回路。始頂點(diǎn)的閉回路。 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 40 表表4-10 以非基變量以非基變量 x22 為起始頂點(diǎn)的閉回路為起始頂點(diǎn)的閉回路 銷(xiāo)地銷(xiāo)地 產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量 3 11 3 4 10 37 1 3 9 2 1 8 4 7 4 6 10 5 39 銷(xiāo)量銷(xiāo)量3656 20(產(chǎn)銷(xiāo)平衡產(chǎn)銷(xiāo)平衡) A1 A2 A3 41 可以計(jì)算出以非基變量可以計(jì)算出以非基變量 x22 為起始為起始 頂點(diǎn)的閉回路調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生頂點(diǎn)的閉回路調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生 的變化為的變化為 9 2 + 3 10 + 5 4 1

30、 即總的運(yùn)費(fèi)增加即總的運(yùn)費(fèi)增加 1 個(gè)單位，這就說(shuō)明這個(gè)單位，這就說(shuō)明這 個(gè)調(diào)整不能改善目標(biāo)值。個(gè)調(diào)整不能改善目標(biāo)值。 從上面的討論可以看出，當(dāng)某個(gè)非基從上面的討論可以看出，當(dāng)某個(gè)非基 變量增加一個(gè)單位時(shí)，有若干個(gè)基變量變量增加一個(gè)單位時(shí)，有若干個(gè)基變量 的取值受其影響。的取值受其影響。 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 42 這樣，利用單位產(chǎn)品變化（運(yùn)輸這樣，利用單位產(chǎn)品變化（運(yùn)輸 的單位費(fèi)用）可計(jì)算出它們對(duì)目標(biāo)函數(shù)的單位費(fèi)用）可計(jì)算出它們對(duì)目標(biāo)函數(shù) 的綜合影響，其作用與線性規(guī)劃單純形的綜合影響，其作用與線性規(guī)劃單純形 方法中的檢驗(yàn)數(shù)完全相同。故也稱(chēng)這個(gè)方法中的檢驗(yàn)數(shù)

31、完全相同。故也稱(chēng)這個(gè) 綜合影響為該非基變量對(duì)應(yīng)的綜合影響為該非基變量對(duì)應(yīng)的檢驗(yàn)數(shù)檢驗(yàn)數(shù)。 上面計(jì)算的兩個(gè)非基變量的檢驗(yàn)數(shù)為上面計(jì)算的兩個(gè)非基變量的檢驗(yàn)數(shù)為 24 = -1， 22 = 1。閉回路方法原理就是閉回路方法原理就是 通過(guò)尋找閉回路來(lái)找到非基變量的檢驗(yàn)通過(guò)尋找閉回路來(lái)找到非基變量的檢驗(yàn) 數(shù)。數(shù)。 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 43 如果規(guī)定作為起始頂點(diǎn)的非基變量如果規(guī)定作為起始頂點(diǎn)的非基變量 為第為第 1 個(gè)頂點(diǎn)，閉回路的其他頂點(diǎn)依次為個(gè)頂點(diǎn)，閉回路的其他頂點(diǎn)依次為 第第 2 個(gè)頂點(diǎn)、第個(gè)頂點(diǎn)、第 3 個(gè)頂點(diǎn)個(gè)頂點(diǎn)那么就有那么就有 ij = (閉回路上的奇數(shù)

32、次頂點(diǎn)單位運(yùn)費(fèi)之閉回路上的奇數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之 和和) - (閉回路上的偶數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之閉回路上的偶數(shù)次頂點(diǎn)單位運(yùn)費(fèi)之 和和) 其中其中 ij 為非基變量的下角指標(biāo)。為非基變量的下角指標(biāo)。 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 44 按上述作法，可計(jì)算出表按上述作法，可計(jì)算出表1的所有非基的所有非基 變量的檢驗(yàn)數(shù)，把它們填入相應(yīng)位置的變量的檢驗(yàn)數(shù)，把它們填入相應(yīng)位置的 方括號(hào)內(nèi)，如圖方括號(hào)內(nèi)，如圖4-11所示。所示。 銷(xiāo)地銷(xiāo)地 產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量 A13 1 11 2 3 4 10 3 7 A21 3 9 1 2 1 8 -1 4 A37 10 4 6

33、10 12 5 3 9 銷(xiāo)量銷(xiāo)量3656 20(產(chǎn)銷(xiāo)平衡產(chǎn)銷(xiāo)平衡) 表表4-11 初始基本可行解及檢驗(yàn)數(shù)初始基本可行解及檢驗(yàn)數(shù) 45 顯然，當(dāng)所有非基變量的檢驗(yàn)顯然，當(dāng)所有非基變量的檢驗(yàn) 數(shù)均大于或等于零時(shí)，現(xiàn)行的調(diào)運(yùn)數(shù)均大于或等于零時(shí)，現(xiàn)行的調(diào)運(yùn) 方案就是最優(yōu)方案，因?yàn)榇藭r(shí)對(duì)現(xiàn)方案就是最優(yōu)方案，因?yàn)榇藭r(shí)對(duì)現(xiàn) 行方案作任何調(diào)整都將導(dǎo)致總的運(yùn)行方案作任何調(diào)整都將導(dǎo)致總的運(yùn) 輸費(fèi)用增加。輸費(fèi)用增加。 閉回路法的閉回路法的主要缺點(diǎn)主要缺點(diǎn)是：當(dāng)是：當(dāng) 變量個(gè)數(shù)較多時(shí)，尋找閉回路以及變量個(gè)數(shù)較多時(shí)，尋找閉回路以及 計(jì)算兩方面都會(huì)產(chǎn)生困難。計(jì)算兩方面都會(huì)產(chǎn)生困難。 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表

34、上作業(yè)法表上作業(yè)法 2.2.位勢(shì)法位勢(shì)法 位勢(shì)：設(shè)對(duì)應(yīng)位勢(shì)：設(shè)對(duì)應(yīng)基變量基變量xij 的的 m +n -1 個(gè)個(gè) ij ，存在，存在ui ,vj 滿足滿足 ui+vj=cij ，i=1,2 ,m ; j=1,2 ,n . 稱(chēng)這些稱(chēng)這些 ui , vj 為該基本可行解對(duì)應(yīng)的為該基本可行解對(duì)應(yīng)的 位勢(shì)。位勢(shì)。 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 47 由于有由于有m + n 個(gè)變量（個(gè)變量（ ui , vj ），）， m + n - 1 個(gè)方程（基變量個(gè)數(shù)），個(gè)方程（基變量個(gè)數(shù)）， 故有一個(gè)自由變量，位勢(shì)不唯一。故有一個(gè)自由變量，位勢(shì)不唯一。 利用位勢(shì)求檢驗(yàn)數(shù)：利用位勢(shì)求檢驗(yàn)

35、數(shù)： ij = cij - ui - vj i = 1, , m ; j = 1, , n 4.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 48 前例，位勢(shì)法求檢驗(yàn)數(shù)：前例，位勢(shì)法求檢驗(yàn)數(shù)： step 1 從任意基變量對(duì)應(yīng)的從任意基變量對(duì)應(yīng)的 cij 開(kāi)始開(kāi)始,任任 取取 ui 或或 vj ，然后利用，然后利用cij = ui + vj 公式公式 依次找出依次找出 m + n 個(gè)個(gè) ui 、vj , 我們我們 從從 c14 = 10 開(kāi)始開(kāi)始 step 2 計(jì)算非基變量的檢驗(yàn)數(shù)計(jì)算非基變量的檢驗(yàn)數(shù) ij = cij - ui - vj ；填入圓圈內(nèi)；填入圓圈內(nèi) 4.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求

36、解表上作業(yè)法表上作業(yè)法 49 4.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 50 當(dāng)非基變量的檢驗(yàn)數(shù)出現(xiàn)負(fù)當(dāng)非基變量的檢驗(yàn)數(shù)出現(xiàn)負(fù) 值時(shí)，則表明當(dāng)前的基本可行解不值時(shí)，則表明當(dāng)前的基本可行解不 是最優(yōu)解。在這種情況下，應(yīng)該對(duì)是最優(yōu)解。在這種情況下，應(yīng)該對(duì) 基本可行解進(jìn)行調(diào)整，即找到一個(gè)基本可行解進(jìn)行調(diào)整，即找到一個(gè) 新的基本可行解使目標(biāo)函數(shù)值下降，新的基本可行解使目標(biāo)函數(shù)值下降， 這一過(guò)程通常稱(chēng)為這一過(guò)程通常稱(chēng)為換基換基( (或主元變換或主元變換) ) 過(guò)程過(guò)程。 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 三、求新的基本可行解三、求新的基本可行解 51 （1）選負(fù)檢驗(yàn)數(shù)中

37、最小者選負(fù)檢驗(yàn)數(shù)中最小者 rk，那么，那么 xrk 為為 主元，作為進(jìn)基變量（上頁(yè)圖中主元，作為進(jìn)基變量（上頁(yè)圖中 x24 ）; （2）以以 xrk 為起點(diǎn)找一條閉回路，除為起點(diǎn)找一條閉回路，除 xrk 外外 其余頂點(diǎn)必須為基變量格（上頁(yè)圖中的回其余頂點(diǎn)必須為基變量格（上頁(yè)圖中的回 路）路）; 4.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 在運(yùn)輸問(wèn)題的表上作業(yè)法中，換基的過(guò)程在運(yùn)輸問(wèn)題的表上作業(yè)法中，換基的過(guò)程 是如下進(jìn)行：是如下進(jìn)行： 52 （3）為閉回路的每一個(gè)頂點(diǎn)標(biāo)號(hào)，為閉回路的每一個(gè)頂點(diǎn)標(biāo)號(hào)， xrk 為為 1，沿一個(gè)方向（順時(shí)針或逆時(shí)針），沿一個(gè)方向（順時(shí)針或逆時(shí)針） 依次給各

38、頂點(diǎn)標(biāo)號(hào)；依次給各頂點(diǎn)標(biāo)號(hào)； （4）求求 =Minxij xij對(duì)應(yīng)閉回路上的對(duì)應(yīng)閉回路上的 偶數(shù)標(biāo)號(hào)格偶數(shù)標(biāo)號(hào)格= xpq 那么確定那么確定 xpq為出基為出基 變量，變量， 為調(diào)整量；為調(diào)整量； 4.24.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 53 （5）對(duì)閉回路的各奇標(biāo)號(hào)頂點(diǎn)調(diào)對(duì)閉回路的各奇標(biāo)號(hào)頂點(diǎn)調(diào) 整為：整為：xij + ，對(duì)各偶標(biāo)號(hào)頂點(diǎn)，對(duì)各偶標(biāo)號(hào)頂點(diǎn) 調(diào)調(diào) 整為：整為：xij - ，特別，特別 xpq - = 0， xpq 變?yōu)榉腔兞?。變?yōu)榉腔兞俊?重復(fù)重復(fù)(2)、(3)步，直到所有檢驗(yàn)步，直到所有檢驗(yàn) 數(shù)均非負(fù)，得到最優(yōu)解。數(shù)均非負(fù)，得到最優(yōu)解。 4.24.2運(yùn)輸

39、問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 54 4.2運(yùn)輸問(wèn)題求解運(yùn)輸問(wèn)題求解表上作業(yè)法表上作業(yè)法 ij 0，得到，得到最優(yōu)解最優(yōu)解 x13 = 5,x14 = 2,x21 = 3,x24 = 1, x32 = 6, x34 = 3, 其余其余 xij = 0 ; 最優(yōu)值最優(yōu)值： f* = 35+102+13+81+46+53 = 85 55 例題求解過(guò)程總結(jié)：例題求解過(guò)程總結(jié)： 初始基本可行解初始基本可行解 位勢(shì)法求檢驗(yàn)數(shù)：位勢(shì)法求檢驗(yàn)數(shù)： 57 選擇負(fù)檢驗(yàn)數(shù)，找出閉回路，確定選擇負(fù)檢驗(yàn)數(shù)，找出閉回路，確定 調(diào)整運(yùn)輸量調(diào)整運(yùn)輸量 58 計(jì)算新的基本可行解，重新計(jì)算，檢驗(yàn)計(jì)算新的基本可行解，重

40、新計(jì)算，檢驗(yàn) 數(shù)均為非負(fù)，即得到最優(yōu)解：數(shù)均為非負(fù)，即得到最優(yōu)解： ；最優(yōu)值為；最優(yōu)值為85850 , 3, 6, 1, 3, 2, 4 343224211413 ij x xxxxxx 其它其它 注意事項(xiàng) 1.1.求初始基本可行解時(shí)：當(dāng)填上一個(gè)數(shù)后行、求初始基本可行解時(shí)：當(dāng)填上一個(gè)數(shù)后行、 列同時(shí)飽和時(shí)，也應(yīng)任意劃去一行（列），列同時(shí)飽和時(shí)，也應(yīng)任意劃去一行（列）， 在保留的列（行）中沒(méi)被劃去的格內(nèi)標(biāo)一在保留的列（行）中沒(méi)被劃去的格內(nèi)標(biāo)一 個(gè)個(gè)0 0。 2. 2. 求新的最優(yōu)解時(shí)，若閉回路有兩個(gè)偶頂點(diǎn)求新的最優(yōu)解時(shí)，若閉回路有兩個(gè)偶頂點(diǎn) 運(yùn)輸量減運(yùn)輸量減 后變成后變成 0 0，選擇其中一個(gè)為

41、出，選擇其中一個(gè)為出 基變量，另一個(gè)仍為基變量?；兞浚硪粋€(gè)仍為基變量。 3.3.閉回路的每一條邊（水平的或垂直的）均閉回路的每一條邊（水平的或垂直的）均 有且僅有兩個(gè)閉回路的頂點(diǎn)。有且僅有兩個(gè)閉回路的頂點(diǎn)。 60 產(chǎn)銷(xiāo)不平衡問(wèn)題的處理產(chǎn)銷(xiāo)不平衡問(wèn)題的處理 實(shí)踐中的運(yùn)輸問(wèn)題常常非產(chǎn)銷(xiāo)平衡，為下列實(shí)踐中的運(yùn)輸問(wèn)題常常非產(chǎn)銷(xiāo)平衡，為下列 的一般運(yùn)輸問(wèn)題模型的一般運(yùn)輸問(wèn)題模型 njmix njdx misxts xcf ij m i jij n j iij m i n j ijij ,.,2,1;,.,2,1,0 ,.,2,1,),( ,.,2,1,)(. min 1 1 11 61 1.產(chǎn)量大于

42、銷(xiāo)量的情況產(chǎn)量大于銷(xiāo)量的情況 考慮考慮 si dj 情況，得到的數(shù)學(xué)模型為情況，得到的數(shù)學(xué)模型為 njmix njdx misxts xcf ij m i jij n j iij m i n j ijij ,.,2,1;,.,2,1,0 ,.,2,1, ,.,2,1,. min 1 1 11 62 我們只須在模型中的產(chǎn)量限制約束我們只須在模型中的產(chǎn)量限制約束 (前前m個(gè)不等式約束個(gè)不等式約束) 中引入中引入m個(gè)松弛變量個(gè)松弛變量 xin+1 i= 1,2,m 即可，變?yōu)椋杭纯?，變?yōu)椋?xij + xin+1 = si i = 1, 2, , m 然后，然后，需設(shè)一個(gè)銷(xiāo)地需設(shè)一個(gè)銷(xiāo)地 Bn+1,

43、 它的銷(xiāo)量它的銷(xiāo)量 為：為：dn+1= si - dj 由于實(shí)際不運(yùn)送由于實(shí)際不運(yùn)送, 它們的運(yùn)費(fèi)為它們的運(yùn)費(fèi)為 cin+1 = 0 i = 1, 2, , m。 于是，這個(gè)運(yùn)輸問(wèn)題就轉(zhuǎn)化成了一于是，這個(gè)運(yùn)輸問(wèn)題就轉(zhuǎn)化成了一 個(gè)產(chǎn)銷(xiāo)平衡的問(wèn)題個(gè)產(chǎn)銷(xiāo)平衡的問(wèn)題 63 B1 B2 B3 產(chǎn)產(chǎn)量量 A1 6 4 6 300 A2 6 5 5 300 銷(xiāo)銷(xiāo)量量 150 150 200 例例4.3 某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)將物品運(yùn)往三個(gè) 銷(xiāo)地銷(xiāo)地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷(xiāo)地，各產(chǎn)地的產(chǎn)量、各銷(xiāo)地 的銷(xiāo)量和各產(chǎn)地運(yùn)往各銷(xiāo)地每件物品的運(yùn)的銷(xiāo)量和各產(chǎn)地運(yùn)往各銷(xiāo)地每件物

44、品的運(yùn) 費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)費(fèi)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn) 輸費(fèi)用最??？輸費(fèi)用最??？ 64 解：增加一個(gè)虛設(shè)的銷(xiāo)地運(yùn)輸費(fèi)用解：增加一個(gè)虛設(shè)的銷(xiāo)地運(yùn)輸費(fèi)用為為0 0 65 2.銷(xiāo)量大于產(chǎn)量的情況銷(xiāo)量大于產(chǎn)量的情況 考慮考慮 si dj 情況，得到的數(shù)學(xué)模型為情況，得到的數(shù)學(xué)模型為 njmix njdx misxts xcf ij m i jij n j iij m i n j ijij ,.,2,1;,.,2,1,0 ,.,2,1, ,.,2,1,. min 1 1 11 66 我們只須在模型中的銷(xiāo)量限制約束我們只須在模型中的銷(xiāo)量限制約束 (后后n個(gè)不等式約束個(gè)不等式約束)

45、 中引入中引入n個(gè)松弛變量個(gè)松弛變量 xm+1j j= 1,2,n 即可，變?yōu)椋杭纯?，變?yōu)椋?xij + xm+1j = dj j = 1, 2, , n 然后，需設(shè)一個(gè)銷(xiāo)地然后，需設(shè)一個(gè)銷(xiāo)地 Am+1, 它的它的c產(chǎn)量為：產(chǎn)量為： dm+1= dj - si 由于實(shí)際不運(yùn)送由于實(shí)際不運(yùn)送,它們它們 的運(yùn)費(fèi)為的運(yùn)費(fèi)為 cm+1j = 0 j = 1, 2, , n。 于是，這個(gè)運(yùn)輸問(wèn)題就轉(zhuǎn)化成了一于是，這個(gè)運(yùn)輸問(wèn)題就轉(zhuǎn)化成了一 個(gè)產(chǎn)銷(xiāo)平衡的問(wèn)題個(gè)產(chǎn)銷(xiāo)平衡的問(wèn)題 67 某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三將物品運(yùn)往三 個(gè)銷(xiāo)地個(gè)銷(xiāo)地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各，各產(chǎn)地的產(chǎn)量

46、、各 銷(xiāo)地的銷(xiāo)量和各產(chǎn)地運(yùn)往各銷(xiāo)地每件物銷(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)如下表所示，問(wèn)：應(yīng)如何調(diào)運(yùn) 可使總運(yùn)輸費(fèi)用最小？可使總運(yùn)輸費(fèi)用最??？ 例例4.4 68 解：增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為解：增加一個(gè)虛設(shè)的產(chǎn)地運(yùn)輸費(fèi)用為0 0 4.3 運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用 例例4.5: 某研究院有三個(gè)區(qū)。每年分別需要用某研究院有三個(gè)區(qū)。每年分別需要用 煤煤3000、1000、2000噸，由河北臨城、山西孟噸，由河北臨城、山西孟 縣兩處煤礦供應(yīng)，價(jià)格、質(zhì)量相同。供應(yīng)能力縣兩處煤礦供應(yīng)，價(jià)格、質(zhì)量相同。供應(yīng)能力 分別為分別為1500、4000噸，運(yùn)價(jià)如下表

47、。由于需求噸，運(yùn)價(jià)如下表。由于需求 大于供給，經(jīng)研究提出，大于供給，經(jīng)研究提出，1區(qū)供應(yīng)量可減少區(qū)供應(yīng)量可減少0 300噸，噸，2區(qū)必須滿足需求量，區(qū)必須滿足需求量，3區(qū)供應(yīng)量不少區(qū)供應(yīng)量不少 于于1700噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。 70 解解:根據(jù)題意，作出產(chǎn)銷(xiāo)平衡與運(yùn)價(jià)表：根據(jù)題意，作出產(chǎn)銷(xiāo)平衡與運(yùn)價(jià)表： 取取 M 代表一個(gè)很大的正數(shù)，其作用是強(qiáng)迫相代表一個(gè)很大的正數(shù)，其作用是強(qiáng)迫相 應(yīng)的應(yīng)的 x31、x33、x34取值為取值為0。 71 例例4.6: 設(shè)有設(shè)有A、B、C三個(gè)化肥廠供應(yīng)三個(gè)化肥廠供應(yīng)1、2、 3、4四個(gè)地區(qū)的農(nóng)用化肥。假設(shè)效四個(gè)地區(qū)的農(nóng)

48、用化肥。假設(shè)效 果相同，有關(guān)數(shù)據(jù)如下表。試求總果相同，有關(guān)數(shù)據(jù)如下表。試求總 費(fèi)用為費(fèi)用為最低最低的化肥調(diào)撥方案。的化肥調(diào)撥方案。 72 首先，作出產(chǎn)銷(xiāo)平衡運(yùn)價(jià)表首先，作出產(chǎn)銷(xiāo)平衡運(yùn)價(jià)表: 最低要求必須滿最低要求必須滿 足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為M；最；最 高要求與最低要求的差允許按需要安排，因高要求與最低要求的差允許按需要安排，因 此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為 0 。根據(jù)產(chǎn)銷(xiāo)。根據(jù)產(chǎn)銷(xiāo) 平衡要求確定平衡要求確定 D的產(chǎn)量為的產(chǎn)量為 50。 解：解： 作業(yè)： P106 4.3 生產(chǎn)與儲(chǔ)存問(wèn)題生產(chǎn)與儲(chǔ)存問(wèn)題 例例4.7: 某廠按合同規(guī)

49、定須于當(dāng)年每個(gè)季度末分某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分 別提供別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。臺(tái)同一規(guī)格的柴油機(jī)。 已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī) 的成本如右表。如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不的成本如右表。如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不 交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi) 用用0.15 萬(wàn)元。試求在完成合同的情況下，使該萬(wàn)元。試求在完成合同的情況下，使該 廠全年生產(chǎn)總費(fèi)用為最小的決策方案廠全年生產(chǎn)總費(fèi)用為最小的決策方案 交貨：交貨： 生產(chǎn)：生產(chǎn)： x11 = 10 x11+x12+x13+

50、x14 25 x12+x22 = 15 x22+x23+x24 35 x13+x23+x33 = 25 x33+x34 30 x14+x24+x34+x44 = 20 x44 10 解：解： 設(shè)設(shè) xij 為第為第 i 季度生產(chǎn)的第季度生產(chǎn)的第 j 季度交季度交 貨的柴油機(jī)數(shù)目，那么應(yīng)滿足貨的柴油機(jī)數(shù)目，那么應(yīng)滿足 把第把第 i 季度生產(chǎn)的柴油機(jī)數(shù)目看作第季度生產(chǎn)的柴油機(jī)數(shù)目看作第 i 個(gè)生產(chǎn)個(gè)生產(chǎn) 廠的產(chǎn)量；把第廠的產(chǎn)量；把第 j 季度交貨的柴油機(jī)數(shù)目看作季度交貨的柴油機(jī)數(shù)目看作 第第 j 個(gè)銷(xiāo)售點(diǎn)的銷(xiāo)量；成本加儲(chǔ)存、維護(hù)等費(fèi)個(gè)銷(xiāo)售點(diǎn)的銷(xiāo)量；成本加儲(chǔ)存、維護(hù)等費(fèi) 用看作運(yùn)費(fèi)。用看作運(yùn)費(fèi)。 可構(gòu)造下列產(chǎn)銷(xiāo)平衡問(wèn)題：可構(gòu)造下列產(chǎn)銷(xiāo)平衡問(wèn)題： 目標(biāo)函數(shù)：目標(biāo)函數(shù)：Min f = 10.8x11 +10.95x12 +11.1x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 77 轉(zhuǎn)運(yùn)問(wèn)題轉(zhuǎn)運(yùn)問(wèn)題: : 實(shí)踐中，還會(huì)有轉(zhuǎn)運(yùn)站，那么常出現(xiàn)的運(yùn)實(shí)踐中，還會(huì)有轉(zhuǎn)運(yùn)站，那么常出現(xiàn)的運(yùn) 輸方式就會(huì)有：輸方式就會(huì)有：產(chǎn)地產(chǎn)地轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)站轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)站 銷(xiāo)地、產(chǎn)地銷(xiāo)地、產(chǎn)地產(chǎn)地、產(chǎn)地產(chǎn)