第七章運(yùn)輸問題之表上作業(yè)法

1、第七章第七章 運(yùn)輸問題運(yùn)輸問題之表上作業(yè)法之表上作業(yè)法一、運(yùn)輸問題模型及其求解一、運(yùn)輸問題模型及其求解思路思路二、確定初始基本可行解二、確定初始基本可行解三、最優(yōu)性檢驗(yàn)三、最優(yōu)性檢驗(yàn)四、方案調(diào)整四、方案調(diào)整五、幾種特殊情況五、幾種特殊情況一、運(yùn)輸問題模型及其求解思路一、運(yùn)輸問題模型及其求解思路v1、問題的提出：、問題的提出：v某公司從兩個(gè)產(chǎn)地某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三將物品運(yùn)往三個(gè)銷地個(gè)銷地B1、B2、B3。v各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示。運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示。v問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小

2、？問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？一、運(yùn)輸問題模型及其求解思路一、運(yùn)輸問題模型及其求解思路B1B2B3產(chǎn)量產(chǎn)量A1646200A2655300銷量銷量150150200一、運(yùn)輸問題模型及其求解思路一、運(yùn)輸問題模型及其求解思路v2、產(chǎn)銷平衡運(yùn)輸問題模型的特點(diǎn)、產(chǎn)銷平衡運(yùn)輸問題模型的特點(diǎn)v從模型的建立可知：從模型的建立可知：v列數(shù)為列數(shù)為2（產(chǎn)地?cái)?shù)）（產(chǎn)地?cái)?shù)）3（銷地?cái)?shù)）（銷地?cái)?shù)）6；v行數(shù)為行數(shù)為2（產(chǎn)地?cái)?shù)）（產(chǎn)地?cái)?shù)）+3（銷地?cái)?shù)）（銷地?cái)?shù)）5；v再觀察模型的系數(shù)矩陣：再觀察模型的系數(shù)矩陣：一、運(yùn)輸問題模型及其求解思路一、運(yùn)輸問題模型及其求解思路 1 1 1 0 0 0 200 0 0 0 1

3、 1 1 300 1 0 0 1 0 0 150 0 1 0 0 1 0 150 0 0 1 0 0 1 200前前2行之和后行之和后3行之和行之和一、運(yùn)輸問題模型及其求解思路一、運(yùn)輸問題模型及其求解思路v對(duì)于產(chǎn)銷平衡的運(yùn)輸問題，若產(chǎn)地為對(duì)于產(chǎn)銷平衡的運(yùn)輸問題，若產(chǎn)地為m個(gè)，銷地為個(gè)，銷地為n個(gè)，個(gè)，v則變量個(gè)數(shù)為則變量個(gè)數(shù)為mn個(gè)，線性無關(guān)的約束個(gè)，線性無關(guān)的約束條件個(gè)數(shù)為條件個(gè)數(shù)為m+n-1，v故基本解中的基變量個(gè)數(shù)為故基本解中的基變量個(gè)數(shù)為m+n-1。一、運(yùn)輸問題模型及其求解思路一、運(yùn)輸問題模型及其求解思路v3、運(yùn)輸問題求解思路、運(yùn)輸問題求解思路表上作業(yè)法表上作業(yè)法v由于運(yùn)輸規(guī)劃系數(shù)矩陣

4、的特殊性，如果由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計(jì)算，直接使用線性規(guī)劃單純形法求解計(jì)算，則無法利用這些有利條件。則無法利用這些有利條件。v人們在分析運(yùn)輸規(guī)劃系數(shù)矩陣特征的基人們在分析運(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對(duì)運(yùn)輸問題的礎(chǔ)上建立了針對(duì)運(yùn)輸問題的表上作業(yè)法表上作業(yè)法。一、運(yùn)輸問題模型及其求解思路一、運(yùn)輸問題模型及其求解思路B1B2B3產(chǎn)量產(chǎn)量A1 6 x11 4 x12 6 x13200A2 6 x21 5 x22 5 x23300銷量銷量150150200v我們關(guān)心的量均在運(yùn)價(jià)表和運(yùn)量表中，我們關(guān)心的量均在運(yùn)價(jià)表和運(yùn)量表中，故將兩表和為故將兩表和為作業(yè)表作

5、業(yè)表：一、運(yùn)輸問題模型及其求解思路一、運(yùn)輸問題模型及其求解思路v表上作業(yè)法的總體思路和單純形法類似：表上作業(yè)法的總體思路和單純形法類似：基本可行解基本可行解是否最優(yōu)解是否最優(yōu)解結(jié)束結(jié)束換基換基是是否否每個(gè)步驟每個(gè)步驟都充分利都充分利用運(yùn)輸表用運(yùn)輸表的特點(diǎn)的特點(diǎn)一、運(yùn)輸問題模型及其求解思路一、運(yùn)輸問題模型及其求解思路v例：某食品公司下屬的例：某食品公司下屬的A1、A2、A3 ，3個(gè)廠個(gè)廠生產(chǎn)方便食品，要運(yùn)輸?shù)缴a(chǎn)方便食品，要運(yùn)輸?shù)紹1、B2、B3、B4 ，4個(gè)銷售點(diǎn)，數(shù)據(jù)如下表，求最優(yōu)運(yùn)輸方案。個(gè)銷售點(diǎn)，數(shù)據(jù)如下表，求最優(yōu)運(yùn)輸方案。B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A374

6、1059銷量銷量365620二、確定初始基本可行解二、確定初始基本可行解v1、西北（左上）角法、西北（左上）角法v每次找最西北角的元素，讓其運(yùn)輸量盡每次找最西北角的元素，讓其運(yùn)輸量盡可能的滿足一個(gè)約束條件。可能的滿足一個(gè)約束條件。二、確定初始基本可行解二、確定初始基本可行解B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A3741059銷量銷量365620342236二、確定初始基本可行解二、確定初始基本可行解這樣得到的初始基本可行解為：這樣得到的初始基本可行解為：x11=3, x12=4, x22=2, x23=2, x33=3, x34=6，其，其余均為余均為0。對(duì)應(yīng)的總運(yùn)費(fèi)為：對(duì)

7、應(yīng)的總運(yùn)費(fèi)為：33+411+29+22+310+65135二、確定初始基本可行解二、確定初始基本可行解v2、最小元素法、最小元素法v每次找到剩下的最小運(yùn)價(jià)，讓其對(duì)應(yīng)的每次找到剩下的最小運(yùn)價(jià)，讓其對(duì)應(yīng)的運(yùn)輸量盡可能的滿足一個(gè)約束條件。運(yùn)輸量盡可能的滿足一個(gè)約束條件。二、確定初始基本可行解二、確定初始基本可行解B1B2B3B4產(chǎn)量產(chǎn)量A13113107A219284A3741059銷量銷量365620343163二、確定初始基本可行解二、確定初始基本可行解用最小元素法求出的初始基本可行解為：用最小元素法求出的初始基本可行解為： x21 =3, x22 =1, x13 =4, x32 =6, x34

8、=3, x14 =3,其余均為其余均為0。對(duì)應(yīng)的總運(yùn)費(fèi)為：對(duì)應(yīng)的總運(yùn)費(fèi)為：31+12+43+64+35+31086二、確定初始基本可行解二、確定初始基本可行解v為保證基變量的個(gè)數(shù)有為保證基變量的個(gè)數(shù)有m+n-1個(gè)，注意：個(gè)，注意：v1、每次填完數(shù)，只能劃去一行或一列，只有、每次填完數(shù)，只能劃去一行或一列，只有最后一個(gè)格子例外。最后一個(gè)格子例外。v2、用最小元素法時(shí)，可能會(huì)出現(xiàn)基變量個(gè)數(shù)、用最小元素法時(shí)，可能會(huì)出現(xiàn)基變量個(gè)數(shù)還差兩個(gè)以上但只剩下一行或一列的情況，還差兩個(gè)以上但只剩下一行或一列的情況，此時(shí)不能將剩下行或列按空格劃掉，應(yīng)在剩此時(shí)不能將剩下行或列按空格劃掉，應(yīng)在剩下的空格中標(biāo)上下的空格

9、中標(biāo)上0。（退化的基本可行解）。（退化的基本可行解）二、確定初始基本可行解二、確定初始基本可行解B1B2B3B4產(chǎn)量產(chǎn)量A13113108A219283A3741059銷量銷量365620353063二、確定初始基本可行解二、確定初始基本可行解B1B2B3B4產(chǎn)量產(chǎn)量A13113104A219284A3741059銷量銷量365317340163三、最優(yōu)性檢驗(yàn)三、最優(yōu)性檢驗(yàn)v檢驗(yàn)數(shù)的意義：非基變量增加一個(gè)單位，檢驗(yàn)數(shù)的意義：非基變量增加一個(gè)單位，使目標(biāo)函數(shù)值增加的數(shù)量。使目標(biāo)函數(shù)值增加的數(shù)量。v運(yùn)輸問題中目標(biāo)函數(shù)值要求最小化，因運(yùn)輸問題中目標(biāo)函數(shù)值要求最小化，因此，當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零

10、時(shí)此，當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)運(yùn)方案就是最優(yōu)方案；否則不是。該調(diào)運(yùn)方案就是最優(yōu)方案；否則不是。v下面介紹兩種計(jì)算檢驗(yàn)數(shù)的方法：下面介紹兩種計(jì)算檢驗(yàn)數(shù)的方法：三、最優(yōu)性檢驗(yàn)三、最優(yōu)性檢驗(yàn)v1、閉回路法、閉回路法v閉回路：在已給出基本解的運(yùn)輸表上，從一閉回路：在已給出基本解的運(yùn)輸表上，從一個(gè)非基變量出發(fā)，沿水平或豎直方向前進(jìn)，個(gè)非基變量出發(fā)，沿水平或豎直方向前進(jìn)，只有碰到基變量，才能向右或向左轉(zhuǎn)只有碰到基變量，才能向右或向左轉(zhuǎn)90o (當(dāng)當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)。然也可以不改變方向）繼續(xù)前進(jìn)。v這樣繼續(xù)下去，總能回到出發(fā)的那個(gè)非基變這樣繼續(xù)下去，總能回到出發(fā)的那個(gè)非基變量，由此路線

11、形成的封閉曲線，叫閉回路。量，由此路線形成的封閉曲線，叫閉回路。三、最優(yōu)性檢驗(yàn)三、最優(yōu)性檢驗(yàn)v每一個(gè)非基變量都有唯一的閉回路每一個(gè)非基變量都有唯一的閉回路B1B2B3B4產(chǎn)量產(chǎn)量A13113 410 37A21 392 184A374 6105 39銷量銷量365620三、最優(yōu)性檢驗(yàn)三、最優(yōu)性檢驗(yàn)v觀察觀察x24的閉回路：的閉回路：v若讓第一個(gè)頂點(diǎn)非基變量若讓第一個(gè)頂點(diǎn)非基變量x24的取值變?yōu)榈娜≈底優(yōu)?，為了保持產(chǎn)銷平衡，其閉回路上的頂點(diǎn)運(yùn)量為了保持產(chǎn)銷平衡，其閉回路上的頂點(diǎn)運(yùn)量都要調(diào)整，基數(shù)頂點(diǎn)都要調(diào)整，基數(shù)頂點(diǎn)+1，偶數(shù)頂點(diǎn)，偶數(shù)頂點(diǎn)-1。v上述調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為上述調(diào)整使總

12、的運(yùn)輸費(fèi)用發(fā)生的變化為 8 10 + 3 2 -1 ，這就說明原方案還不是最優(yōu)，這就說明原方案還不是最優(yōu)方案，需要進(jìn)行調(diào)整。方案，需要進(jìn)行調(diào)整。三、最優(yōu)性檢驗(yàn)三、最優(yōu)性檢驗(yàn)B1B2B3B4產(chǎn)量產(chǎn)量A13113 410 37A21 392 184A374 6105 39銷量銷量365620v若讓若讓x111，則總運(yùn)費(fèi)變化：，則總運(yùn)費(fèi)變化：33+211 。三、最優(yōu)性檢驗(yàn)三、最優(yōu)性檢驗(yàn)v如果規(guī)定作為起始頂點(diǎn)的非基變量如果規(guī)定作為起始頂點(diǎn)的非基變量xij為第為第 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)，那么就有該非基，那

13、么就有該非基變量的檢驗(yàn)數(shù)：變量的檢驗(yàn)數(shù)：v ij = (閉回路上的奇數(shù)頂點(diǎn)運(yùn)價(jià)之和閉回路上的奇數(shù)頂點(diǎn)運(yùn)價(jià)之和) - (閉回閉回路上的偶數(shù)頂點(diǎn)運(yùn)價(jià)之和路上的偶數(shù)頂點(diǎn)運(yùn)價(jià)之和)v最優(yōu)標(biāo)準(zhǔn)：所有檢驗(yàn)數(shù)最優(yōu)標(biāo)準(zhǔn)：所有檢驗(yàn)數(shù)0三、最優(yōu)性檢驗(yàn)三、最優(yōu)性檢驗(yàn)B1B2B3B4產(chǎn)量產(chǎn)量A13 113 410 37A21 39 2 18 4A37 4 610 5 39銷量銷量365620v檢驗(yàn)數(shù)計(jì)算如下表：檢驗(yàn)數(shù)計(jì)算如下表：（1）（2）（1）（-1）（10）（12）三、最優(yōu)性檢驗(yàn)三、最優(yōu)性檢驗(yàn)v2、位勢法、位勢法v閉回路法的缺點(diǎn)：當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路法的缺點(diǎn)：當(dāng)變量個(gè)數(shù)較多時(shí)，尋找閉回路以及計(jì)算兩方面都容

14、易出錯(cuò)。閉回路以及計(jì)算兩方面都容易出錯(cuò)。v位勢法：設(shè)產(chǎn)地位勢法：設(shè)產(chǎn)地Ai對(duì)應(yīng)的位勢量為對(duì)應(yīng)的位勢量為ui ，銷地，銷地Bj對(duì)應(yīng)的位勢量為對(duì)應(yīng)的位勢量為vj， 檢驗(yàn)數(shù)檢驗(yàn)數(shù) ij =cij ui-vj。三、最優(yōu)性檢驗(yàn)三、最優(yōu)性檢驗(yàn)B1B2B3B4產(chǎn)量產(chǎn)量uiA13 11 3 410 37u1A21 39 2 184u2A37 4 6105 39u3銷量銷量365620vjv1v2v3v4三、最優(yōu)性檢驗(yàn)三、最優(yōu)性檢驗(yàn)v根據(jù)基變量根據(jù)基變量xij 的檢驗(yàn)數(shù)的檢驗(yàn)數(shù) ij =0 ，對(duì)應(yīng)基變量，對(duì)應(yīng)基變量的運(yùn)價(jià)的運(yùn)價(jià)cij可以分解為可以分解為ui 和和vj，即，即cij =ui+vj 。v因?yàn)槲粍萘恳?/p>

15、為位勢量ui ,vj的總數(shù)為的總數(shù)為m + n 個(gè)，而限定個(gè)，而限定方程只有方程只有m+n-1個(gè)（基變量個(gè)數(shù)），所以位個(gè)（基變量個(gè)數(shù)），所以位勢量（勢量（ ui ,vj ）有無窮多組解，其中總有一個(gè)）有無窮多組解，其中總有一個(gè)自由變量。自由變量。v故可以任意取一個(gè)位勢量賦以定值，從而確故可以任意取一個(gè)位勢量賦以定值，從而確定其它位勢量的值，一般取定其它位勢量的值，一般取u1 0。三、最優(yōu)性檢驗(yàn)三、最優(yōu)性檢驗(yàn)10392vj206563銷量銷量bj-595 310 4 67 A3-148 2 19 1 3A20710 33 411 3 A1ui產(chǎn)量產(chǎn)量aiB4B3B2B1（1）（2）（1）（-1）

16、（10）（12）檢驗(yàn)數(shù)計(jì)算總結(jié)檢驗(yàn)數(shù)計(jì)算總結(jié)v1、閉回路法計(jì)算式：、閉回路法計(jì)算式：v ij = (閉回路上的奇數(shù)頂點(diǎn)運(yùn)價(jià)之和閉回路上的奇數(shù)頂點(diǎn)運(yùn)價(jià)之和) - (閉回閉回路上的偶數(shù)頂點(diǎn)運(yùn)價(jià)之和路上的偶數(shù)頂點(diǎn)運(yùn)價(jià)之和)v2、位勢法計(jì)算式：、位勢法計(jì)算式：v ij = cij - ui vj 四、方案調(diào)整四、方案調(diào)整B1B2B3B4產(chǎn)量產(chǎn)量A13 （1）11 （2）3 410 37A21 39 （1）2 18 （-1）4A37 （10）4 610 （12）5 39銷量銷量365620最小檢驗(yàn)數(shù)最小檢驗(yàn)數(shù)原則，確定原則，確定進(jìn)基變量進(jìn)基變量最小偶點(diǎn)原則，最小偶點(diǎn)原則，確定出基變量和確定出基變量和調(diào)整

17、量調(diào)整量+1-1+1-1四、方案調(diào)整四、方案調(diào)整B1B2B3B4產(chǎn)量產(chǎn)量aiA13 11 3 5 10 2 7A21 39 2 8 14A37 4 610 5 39銷量銷量bj365620v得到新的基變量：得到新的基變量：x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x34 = 3。重新計(jì)算檢驗(yàn)數(shù)。重新計(jì)算檢驗(yàn)數(shù)。（0）（2）（2）（1）（9）（12）四、方案調(diào)整四、方案調(diào)整v經(jīng)過一次基變換，所有經(jīng)過一次基變換，所有 ij 0，已得到最優(yōu)解：，已得到最優(yōu)解： x13 = 5, x14 = 2, x21 = 3, x24 = 1, x32 = 6, x

18、34 = 3，其它為其它為0。v最優(yōu)值：最優(yōu)值：vf* =35+102+13+81+46+53 = 85四、方案調(diào)整四、方案調(diào)整閉回路調(diào)整法步驟：閉回路調(diào)整法步驟：1、入基變量的確定：選負(fù)檢驗(yàn)數(shù)中最小者、入基變量的確定：選負(fù)檢驗(yàn)數(shù)中最小者 rk，那么，那么 xrk 作為進(jìn)基變量；（使總運(yùn)費(fèi)盡作為進(jìn)基變量；（使總運(yùn)費(fèi)盡快減少）快減少）2、出基變量的確定：在進(jìn)基變量、出基變量的確定：在進(jìn)基變量xrk 的閉回的閉回路上，選取偶數(shù)頂點(diǎn)上調(diào)運(yùn)量最小的值，將路上，選取偶數(shù)頂點(diǎn)上調(diào)運(yùn)量最小的值，將其對(duì)應(yīng)的運(yùn)量作為出基變量。（剛好有一個(gè)其對(duì)應(yīng)的運(yùn)量作為出基變量。（剛好有一個(gè)基變量出基，其它基變量都為正）基變量

19、出基，其它基變量都為正）四、方案調(diào)整四、方案調(diào)整即求即求 =Minxij 閉回路上的偶數(shù)頂點(diǎn)的閉回路上的偶數(shù)頂點(diǎn)的xij= xpq。那么確定那么確定xpq為出基變量，為出基變量， 為調(diào)整量；為調(diào)整量；3、換基調(diào)整：對(duì)閉回路的奇數(shù)頂點(diǎn)運(yùn)量調(diào)整、換基調(diào)整：對(duì)閉回路的奇數(shù)頂點(diǎn)運(yùn)量調(diào)整為：為：xij+ ，對(duì)各偶數(shù)頂點(diǎn)運(yùn)量調(diào)整為：，對(duì)各偶數(shù)頂點(diǎn)運(yùn)量調(diào)整為：xij- ，特別特別 xpq- =0，xpq變?yōu)榉腔兞?。變?yōu)榉腔兞?。重?fù)以上步驟，直到所有檢驗(yàn)數(shù)均非負(fù)，即重復(fù)以上步驟，直到所有檢驗(yàn)數(shù)均非負(fù)，即得到最優(yōu)解。得到最優(yōu)解。練習(xí)題練習(xí)題已知如下運(yùn)價(jià)表，用表上作業(yè)法求解：已知如下運(yùn)價(jià)表，用表上作業(yè)法求解：

20、產(chǎn)銷產(chǎn)銷地地B1B2B3B4產(chǎn)量產(chǎn)量A165344A244756A376583銷量銷量243413 初始解對(duì)應(yīng)目標(biāo)值為初始解對(duì)應(yīng)目標(biāo)值為33+41+42+44+8361產(chǎn)銷地產(chǎn)銷地B1B2B3B4產(chǎn)量產(chǎn)量uiA165344A244756A376583銷量銷量243413vj3421030341334(3)(2)(3)(0)(-1)(-2)產(chǎn)銷地產(chǎn)銷地B1B2B3B4產(chǎn)量產(chǎn)量uiA165344A244756A376583銷量銷量243413vj4030240341332(3)(2)(3)(2)(1)(2) 已達(dá)到最優(yōu)，最優(yōu)目標(biāo)值為已達(dá)到最優(yōu)，最優(yōu)目標(biāo)值為44+42+44+5355五、運(yùn)輸問題的幾種特殊情況五、運(yùn)輸問題的幾種特殊情況v1、多個(gè)最優(yōu)方案的情況：、多個(gè)最優(yōu)方案的情況：v若最優(yōu)表中有非基變量的檢驗(yàn)數(shù)為若最優(yōu)表中有非基變量的檢驗(yàn)數(shù)為0，則為多，則為多個(gè)最優(yōu)方案的情況。個(gè)最優(yōu)方案的情況。v這種情況下，可將檢驗(yàn)數(shù)為這種情況下，可將檢驗(yàn)數(shù)為0的非基變量作為的非基變量作