運(yùn)輸問(wèn)題剖析

1、運(yùn)輸問(wèn)題剖析 第三章第三章 運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題 運(yùn)輸問(wèn)題剖析 本章主要內(nèi)容本章主要內(nèi)容 第一節(jié)第一節(jié) 運(yùn)輸問(wèn)題的數(shù)學(xué)模型及其特征運(yùn)輸問(wèn)題的數(shù)學(xué)模型及其特征 第二節(jié)第二節(jié) 運(yùn)輸問(wèn)題的求解運(yùn)輸問(wèn)題的求解表上作業(yè)法表上作業(yè)法 第三節(jié)第三節(jié) 產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題及應(yīng)用產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題及應(yīng)用 運(yùn)輸問(wèn)題剖析 第一節(jié)第一節(jié) 運(yùn)輸問(wèn)題的數(shù)學(xué)模型及其特征運(yùn)輸問(wèn)題的數(shù)學(xué)模型及其特征 運(yùn)輸問(wèn)題的定義運(yùn)輸問(wèn)題的定義 運(yùn)輸問(wèn)題的數(shù)學(xué)模型運(yùn)輸問(wèn)題的數(shù)學(xué)模型 運(yùn)輸問(wèn)題的特征運(yùn)輸問(wèn)題的特征 運(yùn)輸問(wèn)題剖析 1. 1. 運(yùn)輸問(wèn)題的定義運(yùn)輸問(wèn)題的定義 例例1 1： 某集團(tuán)新購(gòu)進(jìn)一批鋼材，分別存儲(chǔ)在三個(gè)倉(cāng)庫(kù)，現(xiàn)在某集團(tuán)新購(gòu)進(jìn)一批鋼

2、材，分別存儲(chǔ)在三個(gè)倉(cāng)庫(kù)，現(xiàn)在 要將這批鋼材運(yùn)到分布在各地的四個(gè)工廠。各倉(cāng)庫(kù)的庫(kù)存量、要將這批鋼材運(yùn)到分布在各地的四個(gè)工廠。各倉(cāng)庫(kù)的庫(kù)存量、 各工廠的需求量以及從各倉(cāng)庫(kù)往各個(gè)工廠每運(yùn)送一噸鋼材所各工廠的需求量以及從各倉(cāng)庫(kù)往各個(gè)工廠每運(yùn)送一噸鋼材所 需的費(fèi)用見(jiàn)下表，問(wèn)如何調(diào)運(yùn)才能使總運(yùn)費(fèi)降到最低？需的費(fèi)用見(jiàn)下表，問(wèn)如何調(diào)運(yùn)才能使總運(yùn)費(fèi)降到最低？ 工廠工廠 B1 工廠工廠 B2 工廠工廠 B3 工廠工廠 B4 庫(kù)存量庫(kù)存量 倉(cāng)庫(kù)倉(cāng)庫(kù)A1291079 倉(cāng)庫(kù)倉(cāng)庫(kù)A213425 倉(cāng)庫(kù)倉(cāng)庫(kù)A384257 需求量需求量3846 運(yùn)輸問(wèn)題剖析 運(yùn)輸問(wèn)題：有運(yùn)輸問(wèn)題：有m個(gè)供應(yīng)點(diǎn)向個(gè)供應(yīng)點(diǎn)向n個(gè)需求點(diǎn)供應(yīng)某種物資

3、，這個(gè)需求點(diǎn)供應(yīng)某種物資，這m個(gè)個(gè) 供應(yīng)點(diǎn)供應(yīng)點(diǎn)A1、A2、.Am的供應(yīng)量分別為的供應(yīng)量分別為a1、a2、.am；n個(gè)個(gè) 需求點(diǎn)需求點(diǎn)B1、B2、.Bn的需求量分別為的需求量分別為b1、b2、.bn；已知已知 從任一供應(yīng)點(diǎn)從任一供應(yīng)點(diǎn)Ai向任一需求點(diǎn)向任一需求點(diǎn)Bj運(yùn)輸一個(gè)單位物資的費(fèi)用為運(yùn)輸一個(gè)單位物資的費(fèi)用為 cij。問(wèn)采取什么樣的物資調(diào)運(yùn)方案才能使總運(yùn)費(fèi)最省？問(wèn)采取什么樣的物資調(diào)運(yùn)方案才能使總運(yùn)費(fèi)最??？ B1B2Bn供應(yīng)量供應(yīng)量 A1c11c12c1na1 A2c21c22c2na2 Amcm1cm2cmnam 需求量需求量b1b2bn 運(yùn)輸問(wèn)題剖析 2. 2. 運(yùn)輸問(wèn)題的數(shù)學(xué)模型運(yùn)輸問(wèn)

4、題的數(shù)學(xué)模型 11 1 1 min (1,2,.) . .(1,2,. ) 0,1,2,.,1,2,. mn ijij ij n iji j m ijj i ij zc x xaim s txbjn xim jn 11 mn ij ij ab （其其中中） 運(yùn)輸問(wèn)題剖析 運(yùn)輸問(wèn)題的約束方程組系數(shù)矩陣及特征運(yùn)輸問(wèn)題的約束方程組系數(shù)矩陣及特征 111212122212 11.1 11.1 . 11.1 111 11. . .1 111 nnmmmn xxxxxxxxx A 矩陣矩陣A是一個(gè)是一個(gè)m+n行行mn列的矩陣，它的秩不超過(guò)列的矩陣，它的秩不超過(guò)m+n-1。 運(yùn)輸問(wèn)題一般有運(yùn)輸問(wèn)題一般有m+

5、n-1個(gè)基變量。個(gè)基變量。 系數(shù)矩陣非常稀疏。系數(shù)矩陣非常稀疏。 xij的系數(shù)列向量為：的系數(shù)列向量為： m行 n行 (0.1.0.1.0)T ijimj Pee 運(yùn)輸問(wèn)題剖析 3. 運(yùn)輸問(wèn)題的特征運(yùn)輸問(wèn)題的特征 特征特征1：運(yùn)輸問(wèn)題一定有可行解；運(yùn)輸問(wèn)題一定有可行解； 特征特征2：運(yùn)輸問(wèn)題一定有最優(yōu)解；運(yùn)輸問(wèn)題一定有最優(yōu)解； 特征特征3：運(yùn)輸問(wèn)題每一組基對(duì)應(yīng)運(yùn)輸問(wèn)題每一組基對(duì)應(yīng) m+n-1個(gè)基變量；個(gè)基變量； 特征特征4：運(yùn)輸問(wèn)題的運(yùn)輸問(wèn)題的 m+n-1個(gè)基變量構(gòu)成的變量組不含個(gè)基變量構(gòu)成的變量組不含 閉回路閉回路； 特征特征5：任意一個(gè)非基變量和任意一個(gè)非基變量和 m+n-1個(gè)基變量組成的

6、變個(gè)基變量組成的變 量組中必定存在一條并且只存在唯一一條閉回路；量組中必定存在一條并且只存在唯一一條閉回路； 特征特征6：如果運(yùn)輸問(wèn)題中的供應(yīng)量和需求量都是整數(shù)，如果運(yùn)輸問(wèn)題中的供應(yīng)量和需求量都是整數(shù)， 則任一基解中各變量的取值也都是整數(shù)。則任一基解中各變量的取值也都是整數(shù)。 運(yùn)輸問(wèn)題剖析 閉回路閉回路 定義：凡是能夠排列成下列序列的一組變量的集合就定義：凡是能夠排列成下列序列的一組變量的集合就 稱(chēng)為運(yùn)輸問(wèn)題的一個(gè)閉回路。稱(chēng)為運(yùn)輸問(wèn)題的一個(gè)閉回路。 1 12 12 23 21 , s ss i ji ji ji ji ji j xxxxxx 并稱(chēng)集合中每一個(gè)變量為此閉回路的一個(gè)頂點(diǎn)；稱(chēng)連并稱(chēng)集

7、合中每一個(gè)變量為此閉回路的一個(gè)頂點(diǎn)；稱(chēng)連 接相鄰兩個(gè)變量（頂點(diǎn)）以及連接最后一個(gè)頂點(diǎn)和第接相鄰兩個(gè)變量（頂點(diǎn)）以及連接最后一個(gè)頂點(diǎn)和第 一個(gè)頂點(diǎn)的線段為此閉回路的邊一個(gè)頂點(diǎn)的線段為此閉回路的邊。 或或 1 11 22 22 31 , s ss i ji ji ji ji ji j xxxxxx 運(yùn)輸問(wèn)題剖析 B1B2B3B4B5 A1 A2 A3 A4 X45 X41 X31X33 X13X15 運(yùn)輸問(wèn)題剖析 B1B2B3B4B5 A1 A2 A3 A4 X34 X32 X14X12 運(yùn)輸問(wèn)題剖析 B1B2B3B4B5 A1 A2 A3 A4 X35 X41 X31 X43 X13X15 運(yùn)輸

8、問(wèn)題剖析 B1B2B3B4B5 A1 A2 A3 A4 X11X12 X22X24 X44X42 X21 （1 1）每個(gè)頂點(diǎn)都是轉(zhuǎn)折點(diǎn)；）每個(gè)頂點(diǎn)都是轉(zhuǎn)折點(diǎn)； （2 2）閉回路是一條閉合的折線，每一條邊都是水）閉回路是一條閉合的折線，每一條邊都是水 平或垂直的；平或垂直的； （3 3）閉回路上同一行（列）的頂點(diǎn)有偶數(shù)個(gè)。）閉回路上同一行（列）的頂點(diǎn)有偶數(shù)個(gè)。 運(yùn)輸問(wèn)題剖析 閉回路上的點(diǎn)對(duì)應(yīng)的系數(shù)列向量線性相關(guān)。閉回路上的點(diǎn)對(duì)應(yīng)的系數(shù)列向量線性相關(guān)。 Pij Pik PlkPls Pus Puj ijimj Pee 0 ijiklklsusuj PPPPPP 由于由于 容易證明容易證明 運(yùn)輸問(wèn)題

9、剖析 第二節(jié)第二節(jié) 運(yùn)輸問(wèn)題的求解運(yùn)輸問(wèn)題的求解-表上作業(yè)法表上作業(yè)法 第四步：確定進(jìn)基變量和出基變量，調(diào)整非最優(yōu)的調(diào)運(yùn)第四步：確定進(jìn)基變量和出基變量，調(diào)整非最優(yōu)的調(diào)運(yùn) 方案，獲得更好的調(diào)運(yùn)方案；方案，獲得更好的調(diào)運(yùn)方案；轉(zhuǎn)第二步。轉(zhuǎn)第二步。 表上作業(yè)法的基本步驟：表上作業(yè)法的基本步驟： 第一步：編制初始調(diào)運(yùn)方案，即尋找第一個(gè)基可行解第一步：編制初始調(diào)運(yùn)方案，即尋找第一個(gè)基可行解； 第二步：計(jì)算各非基變量的檢驗(yàn)數(shù)；第二步：計(jì)算各非基變量的檢驗(yàn)數(shù)； 第三步：判斷當(dāng)前的調(diào)運(yùn)方案是否是最優(yōu)方案，如果已經(jīng)第三步：判斷當(dāng)前的調(diào)運(yùn)方案是否是最優(yōu)方案，如果已經(jīng) 是最優(yōu)，則算法結(jié)束，問(wèn)題已經(jīng)解決；否則，轉(zhuǎn)第四

10、步；是最優(yōu)，則算法結(jié)束，問(wèn)題已經(jīng)解決；否則，轉(zhuǎn)第四步； 運(yùn)輸問(wèn)題剖析 第一步：編制初始調(diào)運(yùn)方案第一步：編制初始調(diào)運(yùn)方案 要求得運(yùn)輸問(wèn)題的初始基可行解，必須保證找到要求得運(yùn)輸問(wèn)題的初始基可行解，必須保證找到 m+n1 個(gè)基變量個(gè)基變量. 運(yùn)輸問(wèn)題的任意運(yùn)輸問(wèn)題的任意m+n-1個(gè)變量構(gòu)成一組基變量的充要條個(gè)變量構(gòu)成一組基變量的充要條 件是變量組中不含閉回路件是變量組中不含閉回路. 關(guān)鍵關(guān)鍵:找出找出m+n-1個(gè)不含閉回路的變量。個(gè)不含閉回路的變量。 西北角法（左上角法）西北角法（左上角法） 最小元素法最小元素法 Vogel 法法 問(wèn)題：如何使得一個(gè)選定的變量不包含在閉回路中？問(wèn)題：如何使得一個(gè)選定

11、的變量不包含在閉回路中？ 運(yùn)輸問(wèn)題剖析 B1B2B3B4庫(kù)存量庫(kù)存量 A1291079 A213425 A384257 需求量需求量3846 6 2 3 1 6 3 對(duì)應(yīng)的總運(yùn)費(fèi)為對(duì)應(yīng)的總運(yùn)費(fèi)為 C 1= 23 + 93 + 96 + 36 + 32 + 42 + 43 + 23 + 21 + 51 + 56 = 1106 = 110 西北角法西北角法( (左上角法左上角法) ) -3 -3 -6 -6 -2 -2 -3 -3 -1 -1 -6 -6 運(yùn)輸問(wèn)題剖析 最小元素最小元素法法 B1B2B3B4庫(kù)存量庫(kù)存量 A1291079 A213425 A384257 需求量需求量3846 5 2

12、 34 4 3 對(duì)應(yīng)的總運(yùn)費(fèi)為對(duì)應(yīng)的總運(yùn)費(fèi)為 C 2= 95 + 75 + 74 + 14 + 13 + 23 + 22 + 42 + 43 + 23 + 24 = 1004 = 100 -3 -3 -4 -4 -2 -2-3 -3 -4 -4 -5 -5 運(yùn)輸問(wèn)題剖析 Vogel 法法 B1B2B3B4庫(kù)存量庫(kù)存量 A1291079 A213425 A384257 需求量需求量3846 1 5 4 5 3 3 對(duì)應(yīng)的總運(yùn)費(fèi)為對(duì)應(yīng)的總運(yùn)費(fèi)為 C 2= 23 + 93 + 95 + 75 + 71 + 21 + 25 + 45 + 43 + 23 + 24 =884 =88 -3 -3 -1 -

13、1 -5 -5 -3 -3 -5 -5 -4 -4 運(yùn)輸問(wèn)題剖析 B1B2B3B4供應(yīng)量供應(yīng)量 A178143 A226535 A314278 需求量需求量2176 1 0 5 2 6 2 退化情況的處理退化情況的處理 -2 -2 -1 -1 -5 -5 -2 -2 -6 -6 用西北角法求下列運(yùn)輸問(wèn)題的第一個(gè)基可行解用西北角法求下列運(yùn)輸問(wèn)題的第一個(gè)基可行解 運(yùn)輸問(wèn)題剖析 B1B2B3供應(yīng)量供應(yīng)量 A11842 A25251 A35737 需求量需求量217 1 7 2 -2 -2 -1 -1 -7 -7 注意：每次只能劃去一行或一列，不能同時(shí)劃去行和列。注意：每次只能劃去一行或一列，不能同時(shí)

14、劃去行和列。 當(dāng)只剩下一行（列）時(shí)，只能劃去列（行）。當(dāng)只剩下一行（列）時(shí)，只能劃去列（行）。 想一想：為什么？想一想：為什么？ 0 0 用最小元素法求下列運(yùn)輸問(wèn)題的第一個(gè)基可行解用最小元素法求下列運(yùn)輸問(wèn)題的第一個(gè)基可行解 運(yùn)輸問(wèn)題剖析 第二步：計(jì)算各非基變量的檢驗(yàn)數(shù)第二步：計(jì)算各非基變量的檢驗(yàn)數(shù) 1. 1. 閉回路法閉回路法； 2. 2. 位勢(shì)法位勢(shì)法。 檢驗(yàn)數(shù)的定義：非基變量的取值每增加檢驗(yàn)數(shù)的定義：非基變量的取值每增加1 1時(shí)，總運(yùn)費(fèi)的時(shí)，總運(yùn)費(fèi)的 增加量。增加量。 運(yùn)輸問(wèn)題的最優(yōu)性條件：檢驗(yàn)數(shù)非負(fù)運(yùn)輸問(wèn)題的最優(yōu)性條件：檢驗(yàn)數(shù)非負(fù) 運(yùn)輸問(wèn)題剖析 1. 1. 閉回路法閉回路法 基變量不含閉

15、回路，但任何一個(gè)非基變量都可以與基變基變量不含閉回路，但任何一個(gè)非基變量都可以與基變 量構(gòu)成唯一一條閉回路量構(gòu)成唯一一條閉回路 B1B2B3B4庫(kù)存量庫(kù)存量 A1291079 A213425 A384257 需求量需求量3846 6 2 3 1 6 3 14141222233334 7934256cccccc 含義：含義：x14 每增加一個(gè)單位，總運(yùn)費(fèi)增加每增加一個(gè)單位，總運(yùn)費(fèi)增加-6個(gè)單位個(gè)單位 +1 +1 +1 -1 -1 -1 運(yùn)輸問(wèn)題剖析 6 2 3 16 3 所有非基變量的檢驗(yàn)數(shù)見(jiàn)上表所有非基變量的檢驗(yàn)數(shù)見(jiàn)上表 B1B2B3B4庫(kù)存量庫(kù)存量 A1291079 0-6 A213425

16、5-5 A384257 143 需求需求 量量 3846 運(yùn)輸問(wèn)題剖析 2. 2. 位勢(shì)法位勢(shì)法 位勢(shì)：運(yùn)輸問(wèn)題的對(duì)偶變量稱(chēng)為位勢(shì)。位勢(shì)：運(yùn)輸問(wèn)題的對(duì)偶變量稱(chēng)為位勢(shì)。 因?yàn)橐驗(yàn)閙個(gè)供應(yīng)點(diǎn)個(gè)供應(yīng)點(diǎn)n個(gè)需求點(diǎn)的運(yùn)輸問(wèn)題有個(gè)需求點(diǎn)的運(yùn)輸問(wèn)題有m+n個(gè)約束，個(gè)約束， 因此運(yùn)輸問(wèn)題就有因此運(yùn)輸問(wèn)題就有m+n個(gè)位勢(shì)。個(gè)位勢(shì)。 行位勢(shì)行位勢(shì):關(guān)于供應(yīng)點(diǎn)關(guān)于供應(yīng)點(diǎn)Ai的約束對(duì)應(yīng)的對(duì)偶變量，記為的約束對(duì)應(yīng)的對(duì)偶變量，記為 ui, i=1,2,m。 列位勢(shì)列位勢(shì):關(guān)于需求點(diǎn)關(guān)于需求點(diǎn)Bj的約束對(duì)應(yīng)的對(duì)偶變量，記為的約束對(duì)應(yīng)的對(duì)偶變量，記為vj, j = 1,2,n。 運(yùn)輸問(wèn)題剖析 定理定理：運(yùn)輸問(wèn)題變量運(yùn)輸問(wèn)題變

17、量xij的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) ijijij cuv 1 11 0 1 (,.,.) 1 0 ijijBijijmnijij cC B Pcuuvvcuv 證明：證明： 運(yùn)輸問(wèn)題剖析 位勢(shì)及檢驗(yàn)數(shù)的求法位勢(shì)及檢驗(yàn)數(shù)的求法 由于基變量的檢驗(yàn)數(shù)為由于基變量的檢驗(yàn)數(shù)為0，所以可以利用，所以可以利用m+n-1 個(gè)基變個(gè)基變 量求出位勢(shì)量求出位勢(shì) B1B2B3B4庫(kù)存量庫(kù)存量 A1291079 A213425 A384257 需求量需求量3846 6 23 16 3 0 29 -6 10 -8 13 0 -6 5-5 143 運(yùn)輸問(wèn)題剖析 第四步：調(diào)整調(diào)運(yùn)方案第四步：調(diào)整調(diào)運(yùn)方案 1. 1. 確定入基變量：選

18、取最小負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量確定入基變量：選取最小負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)的非基變量 入基入基 2. 2. 確定出基變量和調(diào)整量確定出基變量和調(diào)整量 將進(jìn)基變量對(duì)應(yīng)的閉回路中的頂點(diǎn)分為奇頂點(diǎn)和偶頂點(diǎn)，將進(jìn)基變量對(duì)應(yīng)的閉回路中的頂點(diǎn)分為奇頂點(diǎn)和偶頂點(diǎn)， 令令= min 閉回路上所有偶頂點(diǎn)對(duì)應(yīng)的運(yùn)量閉回路上所有偶頂點(diǎn)對(duì)應(yīng)的運(yùn)量xij 則則即為調(diào)即為調(diào) 整量，選取一個(gè)運(yùn)量等于整量，選取一個(gè)運(yùn)量等于的偶頂點(diǎn)為出基變量。的偶頂點(diǎn)為出基變量。 3.調(diào)整：閉回路上奇頂點(diǎn)上的運(yùn)量增加調(diào)整：閉回路上奇頂點(diǎn)上的運(yùn)量增加，偶頂點(diǎn)上的運(yùn)偶頂點(diǎn)上的運(yùn) 量減少量減少。閉回路以外頂點(diǎn)的運(yùn)量不變。閉回路以外頂點(diǎn)的運(yùn)量不變。 運(yùn)輸問(wèn)題剖析

19、 上例中：若選上例中：若選x14進(jìn)基，進(jìn)基， 則則 =min6,3,6=3, 出基變量為出基變量為x23,調(diào)整后得：調(diào)整后得： B1B2B3B4庫(kù)存庫(kù)存 量量 A1291079 0-6 A213425 5-5 A384257 143 需求量需求量3846 6 23 16 3 運(yùn)輸問(wèn)題剖析 總運(yùn)費(fèi)：總運(yùn)費(fèi)： C = 23 + 93 + 73 + 35 + 24 + 53 = 92 110 x32進(jìn)基，則進(jìn)基，則 =min3,3=3, 出基變量選出基變量選x34,調(diào)整調(diào)整 后得：后得： B1B2B3B4庫(kù)存量庫(kù)存量 A1291079 A213425 A384257 需求需求 量量 3846 3 5

20、 43 33 0 -6 -2 2947 5 6 6 1 8-3 運(yùn)輸問(wèn)題剖析 檢驗(yàn)數(shù)全部非負(fù)，已經(jīng)是最優(yōu)調(diào)運(yùn)方案；檢驗(yàn)數(shù)全部非負(fù)，已經(jīng)是最優(yōu)調(diào)運(yùn)方案； 總費(fèi)用總費(fèi)用 C*= 23 + 90 + 76 + 35 + 43 + 24 = 83 B1B2B3B4庫(kù)存量庫(kù)存量 A1291079 A213425 A384257 需求量需求量3846 0 5 43 36 0 -6 -5 29 77 3 5 31 113 運(yùn)輸問(wèn)題剖析 表上作業(yè)法計(jì)算中應(yīng)注意的問(wèn)題表上作業(yè)法計(jì)算中應(yīng)注意的問(wèn)題 1.1.解的情況解的情況 唯一：非基變量檢驗(yàn)數(shù)全部大于唯一：非基變量檢驗(yàn)數(shù)全部大于0 0； 無(wú)窮多解：至少存在一個(gè)非

21、基變量檢驗(yàn)數(shù)等于無(wú)窮多解：至少存在一個(gè)非基變量檢驗(yàn)數(shù)等于0 0。 2.退化情況：退化情況： 在確定初始基可行解的時(shí)候，當(dāng)填在確定初始基可行解的時(shí)候，當(dāng)填(i,j)格子時(shí)，格子時(shí)， 若若ai=bj, 則則xij=ai=bj, 但此時(shí)只能劃去一行或一列，但此時(shí)只能劃去一行或一列， 在后面的填充過(guò)程中相應(yīng)格子要填在后面的填充過(guò)程中相應(yīng)格子要填0。 3.調(diào)整時(shí)，若閉回路上出現(xiàn)兩個(gè)或兩個(gè)以上偶頂點(diǎn)調(diào)整時(shí)，若閉回路上出現(xiàn)兩個(gè)或兩個(gè)以上偶頂點(diǎn) 取值同時(shí)達(dá)到最小，只能選一個(gè)變量出基。取值同時(shí)達(dá)到最小，只能選一個(gè)變量出基。 運(yùn)輸問(wèn)題剖析 課堂練習(xí)課堂練習(xí) 用表上作業(yè)法求解下列運(yùn)輸問(wèn)題用表上作業(yè)法求解下列運(yùn)輸問(wèn)題

22、. . B1B2B3B4供應(yīng)量供應(yīng)量 A13113107 A219284 A3741059 需求量需求量3656 運(yùn)輸問(wèn)題剖析 B1B2B3B4供應(yīng)量供應(yīng)量 A13113107 A219284 A3741059 需求量需求量 3656 4 31 36 3 運(yùn)輸問(wèn)題剖析 B1B2B3B4供應(yīng)量供應(yīng)量 A13113107 A219284 A3741059 需求量需求量 3656 4 31 36 3 0 310 -1 2 -5 9 12 1-1 10 12 調(diào)整量為調(diào)整量為 min3,1=1，出基變量為出基變量為x23. 運(yùn)輸問(wèn)題剖析 B1B2B3B4供應(yīng)量供應(yīng)量 A13113107 A219284

23、 A3741059 需求量需求量 3656 5 3 1 36 2 最優(yōu)解最優(yōu)解: : 131421243234 5,2,3,1,6,3,0 3 510 21 38 14 65 385 ij xxxxxxx f 其其余余 總總費(fèi)費(fèi)用用 0 310 -2 3 -5 9 02 21 912 由于由于x11的檢驗(yàn)數(shù)為的檢驗(yàn)數(shù)為0，所以最優(yōu)解不唯一。，所以最優(yōu)解不唯一。 運(yùn)輸問(wèn)題剖析 B1B2B3B4供應(yīng)量供應(yīng)量 A13113107 A219284 A3741059 需求量需求量 3656 5 1 3 36 2 0 310 -2 3 -5 9 2 21 912 0 最優(yōu)解最優(yōu)解: : 111321243

24、234 2,5,1,3,6,3,0 3 23 51 18 34 65 385 ij xxxxxxx f 其其余余 總總費(fèi)費(fèi)用用 運(yùn)輸問(wèn)題剖析 第三節(jié)第三節(jié) 產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題及應(yīng)用產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題及應(yīng)用 表上作業(yè)法是以產(chǎn)銷(xiāo)平衡為前提的：表上作業(yè)法是以產(chǎn)銷(xiāo)平衡為前提的： 11 mn ij ij ab 實(shí)際中，往往遇到產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題實(shí)際中，往往遇到產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題 1.1.產(chǎn)大于銷(xiāo)（供過(guò)于求）產(chǎn)大于銷(xiāo)（供過(guò)于求） 11 mn ij ij ab 2.2.銷(xiāo)大于產(chǎn)（供不應(yīng)求）銷(xiāo)大于產(chǎn)（供不應(yīng)求） 11 mn ij ij ab 運(yùn)輸問(wèn)題剖析 產(chǎn)銷(xiāo)不平衡運(yùn)輸問(wèn)題向產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的轉(zhuǎn)化產(chǎn)銷(xiāo)

25、不平衡運(yùn)輸問(wèn)題向產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的轉(zhuǎn)化 產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題：產(chǎn)大于銷(xiāo)的運(yùn)輸問(wèn)題： 11 mn ij ij ab 11 1 1 min (1,2,.) . .(1,2,. ) 0,1,2,.,1,2,. mn ijij ij n iji j m ijj i ij zc x xaim s txbjn xim jn 數(shù)學(xué)模型數(shù)學(xué)模型 運(yùn)輸問(wèn)題剖析 設(shè)設(shè)xi, n+1 是產(chǎn)地是產(chǎn)地Ai 的庫(kù)存量，化成標(biāo)準(zhǔn)形的庫(kù)存量，化成標(biāo)準(zhǔn)形 1 11 1 1 1 min (1,2,.) . .(1,2,. ,1) 0,1,2,.,1,2,.1 mn ijij ij n iji j m ijj i ij zc x x

26、aim s txbjn n xim jn 其中其中 ,1 1 11 0,1,. i n mn nij ij cim bab 引入一個(gè)虛擬的銷(xiāo)地引入一個(gè)虛擬的銷(xiāo)地B Bn+1 n+1（需求量等于 （需求量等于 ），）， 并令各個(gè)產(chǎn)地到該虛擬銷(xiāo)地的單位運(yùn)費(fèi)并令各個(gè)產(chǎn)地到該虛擬銷(xiāo)地的單位運(yùn)費(fèi)c ci,n+1 i,n+1=0 =0。 11 mn ij ij ab 運(yùn)輸問(wèn)題剖析 產(chǎn)小于銷(xiāo)的運(yùn)輸問(wèn)題：產(chǎn)小于銷(xiāo)的運(yùn)輸問(wèn)題： 11 mn ij ij ab 引入一個(gè)虛擬的產(chǎn)地（產(chǎn)量等于引入一個(gè)虛擬的產(chǎn)地（產(chǎn)量等于 ），）， 并令該虛擬產(chǎn)地到各銷(xiāo)地的單位運(yùn)費(fèi)為并令該虛擬產(chǎn)地到各銷(xiāo)地的單位運(yùn)費(fèi)為0 0。 11 nm

27、 ji ji ba 運(yùn)輸問(wèn)題剖析 總供應(yīng)量為總供應(yīng)量為1919千噸，而總需求量為千噸，而總需求量為1515千噸千噸 例例2： A1、A2、A3三個(gè)蔬菜生產(chǎn)地生產(chǎn)的蔬菜主要供應(yīng)三個(gè)蔬菜生產(chǎn)地生產(chǎn)的蔬菜主要供應(yīng)B1、 B2、B3、B4四個(gè)城市。已知三個(gè)產(chǎn)地今年的蔬菜產(chǎn)量預(yù)計(jì)分四個(gè)城市。已知三個(gè)產(chǎn)地今年的蔬菜產(chǎn)量預(yù)計(jì)分 別為別為7千噸、千噸、5千噸和千噸和7千噸；四個(gè)城市今年的蔬菜需求量分別千噸；四個(gè)城市今年的蔬菜需求量分別 為為2千噸、千噸、3千噸、千噸、4千噸和千噸和6千噸；從每個(gè)蔬菜產(chǎn)地平均運(yùn)輸千噸；從每個(gè)蔬菜產(chǎn)地平均運(yùn)輸1 千噸蔬菜到各個(gè)城市的單位費(fèi)用千噸蔬菜到各個(gè)城市的單位費(fèi)用(萬(wàn)元萬(wàn)元)

28、見(jiàn)下表，你能否替他見(jiàn)下表，你能否替他 們編制一個(gè)總運(yùn)費(fèi)最省的蔬菜調(diào)運(yùn)方案？們編制一個(gè)總運(yùn)費(fèi)最省的蔬菜調(diào)運(yùn)方案？ 單位運(yùn)費(fèi)單位運(yùn)費(fèi) B1B2B3B4 供應(yīng)量供應(yīng)量 A1211347 A2103595 A378127 需求量需求量 2346 運(yùn)輸問(wèn)題剖析 需求地需求地 生產(chǎn)地生產(chǎn)地 B1B2B3B4B5供應(yīng)量供應(yīng)量 A12113407 A21035905 A3781207 需求量需求量23464 0 0 -2 2043 0 8 25 7 2 3 3 4 3 2 2 2 3 8 7 最優(yōu)解中最優(yōu)解中x15=2, x25=2，表示兩個(gè)產(chǎn)地沒(méi)有運(yùn)出去的蔬菜量。表示兩個(gè)產(chǎn)地沒(méi)有運(yùn)出去的蔬菜量。 運(yùn)輸問(wèn)題剖析 另：假如例另：假如例2 2中各產(chǎn)地的蔬菜總產(chǎn)量不是中各產(chǎn)地的蔬菜總產(chǎn)量不是1919千噸，千噸， 而是而是1212千噸，就成了一個(gè)供不應(yīng)求的運(yùn)輸問(wèn)題。千噸，就成了一個(gè)供不應(yīng)求的運(yùn)輸問(wèn)題。 單位運(yùn)費(fèi)單位運(yùn)費(fèi) B1B2B3B4 供應(yīng)量供應(yīng)量 A1211343 A2103594 A378125 需求量需求量 2346 單位運(yùn)費(fèi)單位運(yùn)費(fèi) B