運(yùn)籌學(xué) 第二章 運(yùn)輸問題

1、運(yùn)籌學(xué) 第二章 運(yùn)輸問題運(yùn) 籌 學(xué)第二章 運(yùn)輸問題XX大學(xué)經(jīng)濟(jì)與管理學(xué)院 教授、博士生導(dǎo)師 管理科學(xué)與工程系主任 第二章 運(yùn)輸問題 前面討論了一般線性規(guī)劃問題的數(shù)學(xué)模型的建立和求解的方法, 但在實(shí)際工作中，往往碰到有些線性規(guī)劃問題, 它們的約束條件的系數(shù)矩陣具有特殊的結(jié)構(gòu)，這就使我們有可能找到比單純形法更為簡單的求解方法, 從而節(jié)約大量的計(jì)算時(shí)間和費(fèi)用。本章所討論的運(yùn)輸問題就是屬于這樣一類特殊的線性規(guī)劃問題，它在實(shí)踐中具有重要的作用，具有廣泛的應(yīng)用。 第一節(jié) 運(yùn)輸問題的數(shù)學(xué)模型 在經(jīng)濟(jì)建設(shè)中，經(jīng)常會遇到大宗物資調(diào)撥中的運(yùn)輸問題。如煤炭、鋼鐵、木材、糧食等物資,在全國有若干生產(chǎn)基地, 根據(jù)已有的

2、交通網(wǎng), 應(yīng)如何制定調(diào)運(yùn)方案，將這些物資運(yùn)到各消費(fèi)地點(diǎn)，而使總運(yùn)費(fèi)最小。這類問題可用以下數(shù)學(xué)語言來描述：運(yùn)輸問題 ：假設(shè)有 m 個(gè)生產(chǎn)地點(diǎn),可以供應(yīng)某種物資(以后稱為產(chǎn)地)，用 Ai 表示，i = 1,2,?,m；有 n 個(gè)銷售地，用 Bj 表示，j = 1,2, ?,n；產(chǎn)地的產(chǎn)量和銷售地的銷售量分別為 ai , i = 1,2,?,m 和 bj j = 1,2, ?,n，從 Ai 到 Bj 運(yùn)輸單位物資的運(yùn)價(jià)為 cij ，這些數(shù)據(jù)可匯總于如下表21。在假設(shè)產(chǎn)銷平衡的條件下，即 要求得總運(yùn)費(fèi)最小的調(diào)運(yùn)方案。 表21 產(chǎn)銷平衡表與單位運(yùn)價(jià)表 銷地產(chǎn)地 8B1 B2 ? Bn 產(chǎn)量 A1 c11

3、 c12 ? c1n a1 A2 c21 c22 ? c2n a2 ? ? ? ? ? ? Am cm1 cm2 ? cmn am 銷量 b1 b2 ? bn解: 假設(shè) xij 表示從 Ai 到 Bj 的運(yùn)量,則所求的數(shù)學(xué)模型為: 對于產(chǎn)銷不平衡的情況，我們將另行處理。 這就是運(yùn)輸問題的數(shù)學(xué)模型，它包含 mn 變量, m + n 個(gè)約束條件。如果用單純形法求解，先得在各約束條件上加入一個(gè)人工變量(以便求出初始基可行解)。因此，即使是 m = 3， n = 4 這樣的簡單問題, 變量數(shù)就有19個(gè)之多，計(jì)算起來非常復(fù)雜。因此，我們有必要針對運(yùn)輸問題的某些特點(diǎn)，來尋求更為簡單方便的求解方法。 第二節(jié)

4、 表上作業(yè)法 1. 表上作業(yè)法的基本概念與重要結(jié)論 針對運(yùn)輸問題的數(shù)學(xué)模型結(jié)構(gòu)的特殊性，它的約束方程組的系數(shù)矩陣具有如下形式( 具體見下一張幻燈片 )，該矩陣中，每列只有兩個(gè)元素為1，其余都是0。根據(jù)這個(gè)特點(diǎn)，在單純形法的基礎(chǔ)上，創(chuàng)造出一種專門用來求解運(yùn)輸問題的方法，這種方法我們稱為表上作業(yè)法。 運(yùn)輸問題也是一個(gè)線性規(guī)劃問題，當(dāng)用單純形法進(jìn)行求解時(shí)，我們首先應(yīng)當(dāng)知道它的基變量的個(gè)數(shù)；其次，要知道這樣一組基變量應(yīng)當(dāng)是由哪些變量來組成。由運(yùn)輸問題系數(shù)矩陣的形式并結(jié)合第一章單純形算法的討論可以知道: 運(yùn)輸問題的每一組基變量應(yīng)由 m+n-1個(gè)變量組成。(即基變量的個(gè)數(shù) = 產(chǎn)地個(gè)數(shù) + 銷售地個(gè)數(shù) 1

5、) 進(jìn)一步我們想知道, 怎樣的 m+n-1個(gè)變量會構(gòu)成一組基變量？ 為此我們需要引入一些基本概念，通過對這些基本概念 的分析和討論，結(jié)合單純形算法的基本結(jié)果，便可得出 我們所需要的結(jié)論。 定義1： 例1：設(shè) m = 3，n = 4，如表22所示。表22 銷地產(chǎn)地B1B2B3B4A1x11x12A2x21x24A3x32x34 x11、 x12、 x32、 x34、 x24、 x21 構(gòu)成一個(gè)閉回路. 這里有： i1 = 1， i2 = 3， i3 = 2；j1 = 1， j2 = 2， j3 = 4. 若把閉回路的頂點(diǎn)在表中畫出, 并且把相鄰兩個(gè)變量用一條直線相連（今后就稱這些直線為閉回路的邊

6、）。而表23，即頂 點(diǎn)為 x12、 x13、 x23、 x22 和表24，即頂點(diǎn)為 x11、 x12、 x22、 x24、 x34、 x31 也分別構(gòu)成兩個(gè)閉回路。 表23 銷地產(chǎn)地B1B2B3B4A1x12x13A2x22x23A3表2 4 銷地產(chǎn)地B1B2B3B4A1x11x12A2x22x24A3x31x34 從上面的幾個(gè)例子中不難看出，如果把一個(gè)閉回路的 所有頂點(diǎn)都在表中畫出，并且把相鄰的頂點(diǎn)都用一條直 線連接起來，就可以得到一條封閉的折線，折線的每一 條邊或者是水平的，或者是垂直的。定理： m+n-1個(gè)變量 構(gòu)成基變量的充分和必要條件是它不包含有任何閉回路。 以上的結(jié)果給出了運(yùn)輸問題

7、的基的一個(gè)特征，這個(gè)結(jié) 論是非常重要的，因?yàn)槔盟鼇砼袛?m+n-1個(gè)變量是否 構(gòu)成基變量比直接判斷這些變量所對應(yīng)的系數(shù)列向量組 是否線性無關(guān)要簡單和直觀。另外，在以后還將看到利 用基的這個(gè)特征可以導(dǎo)出求運(yùn)輸問題的第一個(gè)基本可行解 的一種 簡便的方法。 2. 表上作業(yè)法 表上作業(yè)法是單純形法在求解運(yùn)輸問題時(shí)的一種簡化方法，其實(shí)質(zhì)是單純形算法。只是具體計(jì)算和術(shù)語有所不同，可歸納為：（1）找出初始基可行解，即在 (m?n) 產(chǎn)銷平衡表上給出m+n-1個(gè)有數(shù)字的格，這些有數(shù)字的格不能構(gòu)成閉回路，且行和等于產(chǎn)量，列和等于銷售量；（2）求各非基變量的檢驗(yàn)數(shù)，即在表上求空格的檢驗(yàn)數(shù)，判別是否達(dá)到最優(yōu)解。如

8、果達(dá)到最優(yōu)解，則停止計(jì)算，否則轉(zhuǎn)入下一步；（3）確定換入變量和換出變量，找出新的基可行解，在表上用閉回路法進(jìn)行調(diào)整。（4）重復(fù)（2）、（3）步，直到求得最優(yōu)解為止。 以下我們就具體給出求解運(yùn)輸問題表上作業(yè)法的 計(jì)算步驟。2.1 確定初始基可行解 確定初始基可行解即首先給出初始的調(diào)運(yùn)方案，方法很多，我們只介紹其中的兩種方法： 1. 方法一、最小元素法： 最小元素法的基本思想就是就近供應(yīng)。即從單位運(yùn)價(jià)表中最小的運(yùn)價(jià)開始確定產(chǎn)銷關(guān)系,依次類 推,直到給出初始方案為止。舉例如下： 例2：某公司經(jīng)銷甲產(chǎn)品，它下設(shè)三個(gè)加工廠，每日的產(chǎn)量分別為：A17噸、 A24噸、 A39噸。該公司把這些產(chǎn)品分別運(yùn)往四個(gè)

9、銷售點(diǎn). 各銷售點(diǎn)每日銷售量為：B13噸、 B26噸、 B35噸、B46噸。已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)如表25所示。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，在滿足各銷售點(diǎn)的需要量的前提下,使總的運(yùn)費(fèi)為最小。 表2551047A38291A2103113A1B4B3B2B1 銷地產(chǎn)地3656749產(chǎn)量銷量 表26 單位：噸 銷地產(chǎn)地B1B2B3B4產(chǎn)量A17A24A39銷量3656解：先畫出這個(gè)問題的產(chǎn)銷平衡表26。 第一步：從單位運(yùn)價(jià)表中找出最小運(yùn)價(jià)為1，這表示先將 A2 的產(chǎn)品供應(yīng) B1 。由于A2 每天生產(chǎn)4噸，B1 每天只需要 3噸，即 A2 除每日能滿足B1 的需要外還余1噸。因此在產(chǎn) 銷

10、平衡表 (A2 , B1) 交叉處填上3，表示 A2 調(diào)運(yùn)3噸給B1 ， 再在單位運(yùn)價(jià)表中將B1 這一列運(yùn)價(jià)劃去，表示 B1 的需求 已滿足，不需要繼續(xù)調(diào)運(yùn) (即x21 =3=min(a2,b1)=min(4 , 3). 第二步: 從上述未劃去的單位運(yùn)價(jià)表的元素中找出最小的 運(yùn)價(jià)2 ，即A2 把剩余的產(chǎn)品供應(yīng)給B3 ；B3 每天需要5 噸 ，A2 只剩余 1 噸，因此在上述產(chǎn)銷平衡表的 (A2 , B3) 交 叉處填上 1，劃去上述運(yùn)價(jià)表中A2 這一行運(yùn)價(jià)，表示 A2的產(chǎn)品已分配完畢。 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1437A2314A3639銷量365651047A38291A2103113

11、A1B4B3B2B1 表27第三步: 從上述第二步所得的單位運(yùn)價(jià)表未劃去的元素中 找出最小元素為 3。這表示將 A1 的產(chǎn)品供應(yīng) B3 ， A1 每 天生產(chǎn)7 噸，B3 尚缺 4 噸，因此在產(chǎn)銷平衡表的(A1 , B3) 交叉處填上 4，由于B3 的需求已滿足，將第二步的單位 運(yùn)價(jià)表中的 B3 這一列運(yùn)價(jià)劃去。 如此，一步步進(jìn)行下去，直到單位運(yùn)價(jià)表中所有元素都劃去為止，最終在產(chǎn)銷平衡表上就可以得到一個(gè)初始調(diào)運(yùn)方案。這個(gè)方案的總運(yùn)費(fèi)為 86 元，如表27所示。 應(yīng)當(dāng)注意的是，在用最小元素法確定初始基可行解 的時(shí)候，有可能出現(xiàn)以下的兩種特殊情況： 當(dāng)在中間步驟的未劃去的單位運(yùn)價(jià)表中尋找最小元 素時(shí)

12、，發(fā)現(xiàn)該元素所在行的剩余產(chǎn)量等于該元素所在列 的剩余銷售量。這時(shí)在產(chǎn)銷平衡表相應(yīng)的位置填上一個(gè) 數(shù)，而在單位運(yùn)價(jià)表中就要同時(shí)劃去一行和一列。為了 使調(diào)運(yùn)方案中有數(shù)字的格仍為（m + n 1）個(gè)，需要在同 時(shí)劃去的行或列的任一空格位置添上一個(gè)“0”，這個(gè)“0” 表示該變量是基變量，只不過它取值為0，即此時(shí)的調(diào)運(yùn) 方案是一個(gè)退化的基可行解。見如下例 4： 銷地產(chǎn)地B1B2B3B4產(chǎn)量A15049A2314A377銷量3584751020A36961A241035A1B4B3B2B1 在這個(gè)例子中，當(dāng)在填入第三數(shù)字的格 ( A1, B4 ) 時(shí), 在填入 4 之后，恰好產(chǎn)銷平衡，就必須在單位運(yùn)價(jià)表中

13、 同時(shí)劃去第一行和第四列。為了使有數(shù)字的格不減少， ( 有數(shù)字的格的總數(shù)應(yīng)為m + n 1個(gè) )可以在空格( A1, B1 ) 、 ( A1, B3 ) 、 ( A2, B4 ) 、( A3, B4 )中任選一個(gè)格添加一個(gè) “0”；同樣，這個(gè)添加的“0”格當(dāng) 作基變量，取值為0。我 們這里是在 ( A1, B3 ) 處填0（即初始調(diào)運(yùn)方案是一個(gè)退化 的基可行解）。 2. 方法二、伏格爾法： 最小元素法的缺點(diǎn)是，為了節(jié)省一處的費(fèi)用，有時(shí)造成在其它地方要花多幾倍的運(yùn)費(fèi)。伏格爾法考慮到，一 產(chǎn)地的產(chǎn)品，假如不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次 小運(yùn)費(fèi)。這就有一個(gè)差額，差額越大，說明不能按最小 運(yùn)費(fèi)調(diào)運(yùn)時(shí)

14、，運(yùn)費(fèi)增加就越多。因此，對于差額最大處 ，就優(yōu)先采用最小運(yùn)費(fèi)調(diào)運(yùn)。我們還是用例 1 來說明伏 格爾法的具體實(shí)施過程，步驟如下： 第一步：在單位運(yùn)價(jià)表中增加一行和一列，列的格位置 相應(yīng)填入該行的次小運(yùn)費(fèi)與最小運(yùn)費(fèi)之差，我們稱之為 行差額。行的格位置相應(yīng)填入該列的次小運(yùn)費(fèi)與最小運(yùn) 費(fèi)之差，我們稱之為列差額。如此可得表28： 銷地產(chǎn)地B1B2B3B4行差額A13113100A219281A3741051列差額2513 表28 第二步：從行差額和列差額中選出最大者，選擇它所在 的行或列中的最小元素。比較該元素所在的行和列的產(chǎn) 量，取它們最小者填入產(chǎn)銷平衡表相應(yīng)的位置。同時(shí)在 單位運(yùn)價(jià)表中劃去一行或一列

15、。由于B2 的列差額最大。B2 列中最小元素為 4（即 A3 行），可確定 A3 產(chǎn)品優(yōu)先供應(yīng) B2 。比較它們的產(chǎn)量和銷量，可知在單位 運(yùn)價(jià)表中劃去 B2 列。在產(chǎn)銷平衡表的( A3 , B2 ) 空格處填 入 6。 第三步：對上述未劃去的元素再比較出各行、各列 的差額。重復(fù)第一、二步的工作，直到給出初始解為止。 本問題利用伏格爾方法給出的初始調(diào)運(yùn)方案如下表29 所示。 由以上可見：伏格爾方法同最小元素法除在確定供求 關(guān)系的原則上不同外，其余步驟相同，因而給出的初始調(diào)運(yùn)方案也是基可行解。且一般來說，比用最小元素法 所求出的初始解更接近于最優(yōu)解。本例用伏格爾方法給 出的初始解，這個(gè)方案的總運(yùn)費(fèi)

16、為 85元。表29 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1527A2314A3639銷量3656 2 .2 最優(yōu)解的判別 判別的方法是計(jì)算非基變量即空格的檢驗(yàn)數(shù)。因運(yùn)輸 問題的目標(biāo)函數(shù)是要求實(shí)現(xiàn)最小化，所以當(dāng)所有的非基 變量檢驗(yàn)數(shù)全都 ? 0 時(shí)為最優(yōu)解。下面介紹兩種求空格 檢驗(yàn)數(shù)的方法。 1. 閉回路法 在給出調(diào)運(yùn)方案的計(jì)算表上，如表29，從每一空格 出發(fā)，找一條閉回路。它是以空格為起點(diǎn)，用水平線或 垂直線向前劃，每碰到一數(shù)字格就轉(zhuǎn) 90 度后繼續(xù)前進(jìn)。 直到回到起始空格處為止。(A1 , B1) 空格與(A1 , B4) 、 (A2 , B4) 和 (A2 , B1) 三個(gè)有數(shù)字的格構(gòu)成一閉回路

17、，如此 等等。 閉回路計(jì)算檢驗(yàn)數(shù)的經(jīng)濟(jì)解釋為：在已給出初始解的表27中，可以從任一空格出發(fā)，如從 (A1 , B1) 出發(fā)，若 讓 A1 的產(chǎn)品調(diào) 1 噸給B1 ，為了保持產(chǎn)銷平衡，就要依次 作調(diào)整：在 (A1 , B3) 處減少 1 噸， (A2 , B3) 處增加 1 噸， (A2 , B1) 處減少 1 噸，即構(gòu)成了以(A1 , B1) 空格為起點(diǎn)， 其它為有數(shù)字的格的閉回路。如表210中的直線所示， 在這表閉回路中，各頂點(diǎn)所在格的右上角的數(shù)字是單位運(yùn)價(jià)。 可見這一調(diào)整方案使運(yùn)費(fèi)增加了： (+1)?3 + (-1) ?3 + (+1)?2 + (-1) ?1 = 1 (元) 這表明若這樣

18、調(diào)整運(yùn)輸方式將增加運(yùn)費(fèi)。將“1”這個(gè)數(shù)填 入(A1 , B1) 格，這就是檢驗(yàn)數(shù)。 表210 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1 3（+1）4 3（-1）37A2 3 1（-1）1 2（+1）4A3639銷量3656按以上所述，就可以找出 所有空格的檢驗(yàn)數(shù)，見如下表211。 這時(shí)檢驗(yàn)數(shù)還存在負(fù)數(shù)，因?yàn)?A2 , B4) 空格的檢驗(yàn)數(shù) 為 1，這說明原方案還不是最優(yōu)解，還需要進(jìn)一步改進(jìn)， 改進(jìn)方法見后面的2. 3小節(jié)。 表211空 格閉 回 路檢驗(yàn)數(shù)(A1 , B1)(1,1)? (1,3)? (2,3)? (2,1)?(1,1)1(A1 , B2)(1,2)? (1,4)? (3,4)? (3,

19、2)?(1,2)2(A2 , B2)(2,2)? (2,3)? (1,3)? (1,4)? (3,4)? (3,2)? (2,2)1(A2 , B4)(2,4)? (2,3)? (3,3)? (1,4)?(2,4)-1(A3 , B1)(3,1)? (3,4)? (1,4)? (1,3)? (2,3)? (2,1)? (3,1)10(A3 , B3)(3,3)? (3,4)? (1,4)? (1,3)? (3,3)12 2. 方法二：位勢法 用閉回路法求檢驗(yàn)數(shù)時(shí)，需要給每一空格找一條閉 回路。當(dāng)產(chǎn)銷點(diǎn)很多時(shí)，這種計(jì)算很費(fèi)時(shí)。下面介紹一 種較為簡便的方法位勢法。 是一組基可行解， 現(xiàn)在引進(jìn) m+

20、n 個(gè)未知量 u1 , , um , v1 , , vn ，由上述基 本可行解可構(gòu)造如下一個(gè)方程組（2.1)： 其中cij 為單位運(yùn)價(jià)。方程組（2.1）共有m+n 未知數(shù)和 m+n-1個(gè)方程。(2.1)的解存在且恰有一個(gè)自由變量。稱 u1 , , um 為行位勢， v1 , , vn 為列位勢。 定理：設(shè)已給了一組基本可行解，則對每一個(gè)非基變量xij 來說，它所對應(yīng)的檢驗(yàn)數(shù)為： ?ij = cij ( ui + vj ) (2.2) 下面,我們就以例子來說明這種方法的具體實(shí)施過程 仍以例2所給出的初始基可行解表27為例： 第一步：由表27作表212，在對應(yīng)表27的數(shù)字格 處填入單位運(yùn)價(jià)如表21

21、2所示： 第二步：在表212上增加一行和一列，列中填入行 位勢 ui ，行中填入列位勢 vj 的表213。 先令u1= 0 （行和列中基變量多的令為0），然后按 ui + vj = cij ( i , j )?基變量指標(biāo)集 ，相繼確定 ui 、 vj 。由表213可見，u1= 0 時(shí)，由 u1 + v3 = c13 = 3 可得v3 = 3 ，由u1 + v4 = c14 = 10 可得 v4 = 10；在v4 = 10時(shí)，由u3 + v4 = c34 = 5 可得 u3 = -5 。 以此類推可確定所有的 ui 、vj 的值。 表212 B1B2B3B4A1310A212A345 表213

22、銷地產(chǎn)地B1B2B3B4行位勢 uiA13100A212-1A345-5列位勢 vj 29310 第三步：按?ij = cij (ui + vj ) ,( i , j )?非基變量指標(biāo)集，計(jì) 算所有的空格檢驗(yàn)數(shù)。如： ?11 = c11 (u1 + v1 ) =3 ( 0 + 2 ) = 1 ?12 = c12 (u1 + v2 ) = 11 - ( 0 + 9 ) = 2 這些計(jì)算可直接在表213上進(jìn)行。為了方便，特設(shè)計(jì)計(jì) 算表，如表214。右上角框內(nèi)的數(shù)為單位運(yùn)價(jià)。 在表214中還有負(fù)的檢驗(yàn)數(shù)，說明還未得到最優(yōu)解， 還得進(jìn)一步進(jìn)行改進(jìn)。 表214 銷地產(chǎn)地B1B2B3B4行位勢 uiA1

23、31 112 30 1000A2 10 91 20 8-1-1A3 710 40 1012 50-5列位勢 vj 29310 2. 3 解改進(jìn)的方法閉回路調(diào)整法 當(dāng)計(jì)算所有的空格檢驗(yàn)數(shù)時(shí)，出現(xiàn)了負(fù)檢驗(yàn)數(shù)，這表 明還未得到最優(yōu)解。若有兩個(gè)或兩個(gè)以上的檢驗(yàn)數(shù)為負(fù) 時(shí)，一般選擇其中最小的負(fù)檢驗(yàn)數(shù)，以它對應(yīng)的空格為 調(diào)入格。即以它對應(yīng)的非基變量為換入變量。由表214 可知 (A2 , B4)為調(diào)入格（即以它對應(yīng)的變量 x24 為換入變 量）。以此格為出發(fā)點(diǎn)，作一閉回路，如表215所示。 (A2 , B4) 格的調(diào)入量 ? 是選擇閉回路上具有（-1）的 數(shù)字格中的最小者。即 ? = min1 , 3=1

24、 (其原理與單純 形法中按? 規(guī)則來確定的換出變量是相同)，然后按閉回 路上的正、負(fù)號，加入和減去此值，得到調(diào)整方案如表2 16所示。對表216給出的解，再用閉回路法或位勢法 求各空格的檢驗(yàn)數(shù)，見表217，這時(shí)表中的所有檢驗(yàn)數(shù) 全都 ? 0 ，所以表216所給出的解為最優(yōu)解。這時(shí)得到 的總運(yùn)費(fèi)的最小值是 85 元。 銷地產(chǎn)地B1B2B3B4產(chǎn)量A14(+1)3(-1)7A231(-1)1(+1)4A3639銷量3656 表215 表216 解的調(diào)整表 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1527A2314A3639銷量3656 表217 檢驗(yàn)數(shù)表 B1B2B3B4A102A221A3912 應(yīng)當(dāng)指出

25、的是，產(chǎn)銷平衡的運(yùn)輸問題必定存在最優(yōu) 解。那么有唯一最優(yōu)解還是無窮多個(gè)最優(yōu)解？依據(jù)仍然 是要檢驗(yàn)是否有存在非基變量（即空格處）的檢驗(yàn)數(shù)為 0。若有，則存在無窮多個(gè)最優(yōu)解；否則，只有唯一最優(yōu) 解。由于表217可知，空格 (A1 , B1)處的檢驗(yàn)數(shù)為0，表 明例2有無窮多個(gè)最優(yōu)解?？稍诒?16中以(A1 , B1)為調(diào) 入格, 作閉回路 (A1 , B1)+?(A1 , B4)-?(A2 , B4)+?(A2 , B1)- ?(A1 , B1)+ 。確定? = min2 , 3=2，經(jīng)調(diào)整后得到另一 個(gè)最優(yōu)解，見表218。當(dāng)然，我們的調(diào)入量可以是： 0 < ? < 2 中的任一實(shí)數(shù)，

26、這時(shí)的解仍為最優(yōu)解，但不是 基可行解（因?yàn)榫€性規(guī)劃問題可以在頂點(diǎn)取到最優(yōu)解， 也可以是在非頂點(diǎn)即是邊界點(diǎn)上取到最優(yōu)解，本題如表 219所示。 表218 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1257A2134A3639銷量3656 表219 銷地產(chǎn)地B1B2B3B4產(chǎn)量A1?52- ? 7A23- ? 1+ ? 4A3639銷量3656 第三節(jié) 產(chǎn)銷不平衡的運(yùn)輸問題及其求解方法 前面講的表上作業(yè)法，都是以產(chǎn)銷平衡為前提的。 但實(shí)際問題往往是不平衡的。這就需要把產(chǎn)銷不平衡的 問題轉(zhuǎn)化為產(chǎn)銷平衡的問題。 當(dāng)產(chǎn)大于銷，即 時(shí)，運(yùn)輸問題的 的數(shù)學(xué)模型可以寫成： 由于總的產(chǎn)量大于銷售量，就要考慮多余的物資在那

27、一個(gè)產(chǎn)地貯存的問題。設(shè) xin+1 是產(chǎn)地 Ai 貯存量，故有： 將其分別代入，得到： 這是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題。 類似地，當(dāng)銷大于產(chǎn)時(shí)，可以在產(chǎn)銷平衡表中增加一 個(gè)假想的產(chǎn)地 i = m + 1 ，該產(chǎn)地的產(chǎn)量為 在單位運(yùn)價(jià)表中令從該產(chǎn)地到各個(gè)銷售地的單位運(yùn)價(jià)為： cm+1 j = 0，同樣可以轉(zhuǎn)化為產(chǎn)銷平衡的運(yùn)輸問題。 第四節(jié) 應(yīng)用舉例 例3 設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥。假定等 量的化肥在這些地區(qū)使用的效果相同。各化肥廠年產(chǎn)量、 各地區(qū)年需要量及從各化肥廠到各地區(qū)運(yùn)送單位化肥的 運(yùn)價(jià)表如表220所示。試求出總的運(yùn)費(fèi)最省的化肥調(diào)撥 方案。 解：這是一個(gè)產(chǎn)銷不平衡的運(yùn)輸問題，總產(chǎn)量

28、為160萬噸 ，四個(gè)地區(qū)的最低需求為110萬噸，最高需求為無限。根 據(jù)現(xiàn)有產(chǎn)量，第?個(gè)地區(qū)每年最多能分配得到60萬噸， 這樣最高需求就為210萬噸，大于產(chǎn)量。為了求得平衡，在產(chǎn)銷平衡表中增加一個(gè)假想的化肥廠 D ，其年產(chǎn)量為 50 萬噸。由于各地區(qū)的需求量包含兩部分，如地區(qū)1，其 中 30 萬噸是最低需求，故不能由假想化肥廠 D 供給，令 相應(yīng)的單位運(yùn)價(jià)為 M （任意大的正數(shù)）；而另一部分 20 萬噸滿足或不滿足均可以，因此可以由假想化肥廠 D 供 給，按前述，可令相應(yīng)的單位運(yùn)價(jià)為0。對凡是需求分兩 種情況的地區(qū)，實(shí)際上可按照兩個(gè)地區(qū)看待。這樣可以 寫出這個(gè)問題的產(chǎn)銷平衡表（表221）和單位運(yùn)

29、價(jià)表（ 表222）。并根據(jù)表上作業(yè)法，可以求得這個(gè)問題的最 優(yōu)解如表223所示。 表220 單位運(yùn)價(jià)：萬元/萬噸 需求產(chǎn)地?產(chǎn)量(萬噸)A1613221750B1413191560C19202350最低需求3070010最高需求507030不限 表221 產(chǎn)銷平衡表 產(chǎn)地銷地?產(chǎn) 量A50B60C50D50銷 量 302070301050 表222 單位運(yùn)價(jià)表 產(chǎn)地銷地?A161613221717B141413191515C19192023MMDM0M0M0 表223 最優(yōu)調(diào)運(yùn)方案 產(chǎn)地銷地?產(chǎn) 量A5050B20103060C3020050D302050銷 量 302070301050 由于在變量個(gè)數(shù)相等的情況下，表上作業(yè)法的計(jì)算 遠(yuǎn)比單純形法的計(jì)算簡單得多，所以在解決實(shí)際問題時(shí)， 人們常常盡可能把某些線性規(guī)劃問題化為運(yùn)輸問題的數(shù) 學(xué)模型。下面介紹例4作為一個(gè)典型的實(shí)例。 例4 某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、 15、25、20臺同一規(guī)格的柴油機(jī)。已知該廠各季度的生 產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如表224所示。又如果 生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺每季度需存儲費(fèi)、 維護(hù)費(fèi)等共0.15萬元。要求在完成合同的情況下，做出 使該廠全年生產(chǎn)（包括儲存、維護(hù)等）費(fèi)用最小的決策。 表224季 度