管理運籌學第七章運輸問題之表上作業(yè)法教材課件

一、運輸問題模型及其求解思路1、問題的提出：某公司從兩個產地A1、A2將物品運往三個銷地B1、B2、B3。各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示。問：應如何調運可使總運輸費用最??？一、運輸問題模型及其求解思路1、問題的提出：1一、運輸問題模型及其求解思路B1B2B3產量A1646200A2655300銷量150150200一、運輸問題模型及其求解思路B1B2B3產量A16462002一、運輸問題模型及其求解思路2、產銷平衡運輸問題模型的特點從模型的建立可知：列數(shù)為2（產地數(shù)）×3（銷地數(shù)）＝6；行數(shù)為2（產地數(shù)）+3（銷地數(shù)）＝5；再觀察模型的系數(shù)矩陣：一、運輸問題模型及其求解思路2、產銷平衡運輸問題模型的特點3一、運輸問題模型及其求解思路111000200

000111300100100150

010010150

001001200前2行之和＝后3行之和一、運輸問題模型及其求解思路114一、運輸問題模型及其求解思路對于產銷平衡的運輸問題，若產地為m個，銷地為n個，則變量個數(shù)為m×n個，線性無關的約束條件個數(shù)為m+n-1，故基本解中的基變量個數(shù)為m+n-1。一、運輸問題模型及其求解思路對于產銷平衡的運輸問題，若產地為5一、運輸問題模型及其求解思路3、運輸問題求解思路——表上作業(yè)法由于運輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計算，則無法利用這些有利條件。人們在分析運輸規(guī)劃系數(shù)矩陣特征的基礎上建立了針對運輸問題的表上作業(yè)法。一、運輸問題模型及其求解思路3、運輸問題求解思路——表上作業(yè)6一、運輸問題模型及其求解思路B1B2B3產量A16x114x126x13200A26x215x225x23300銷量150150200我們關心的量均在運價表和運量表中，故將兩表和為作業(yè)表：一、運輸問題模型及其求解思路B1B2B3產量A16467由于運輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計算，則無法利用這些有利條件。下面介紹兩種計算檢驗數(shù)的方法：2、產銷平衡運輸問題模型的特點613如上例中的最優(yōu)方案就不唯一：二、確定初始基本可行解二、確定初始基本可行解五、運輸問題的幾種特殊情況3在最優(yōu)解中，若相應xij的取值為0，則此最優(yōu)解為原問題的最優(yōu)解；已達到最優(yōu)，最優(yōu)目標值為4×4+4×2+4×4+5×3＝55五、運輸問題的幾種特殊情況010010150即求=Min{xij閉回路上的偶數(shù)頂點的xij}=xpq。ij=cij-ui–vj則變量個數(shù)為m×n個，線性無關的約束條件個數(shù)為m+n-1，33、運輸問題求解思路——表上作業(yè)法一、運輸問題模型及其求解思路表上作業(yè)法的總體思路和單純形法類似：基本可行解是否最優(yōu)解結束換基是否每個步驟都充分利用運輸表的特點由于運輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求8一、運輸問題模型及其求解思路例：某食品公司下屬的A1、A2、A3，3個廠生產方便食品，要運輸?shù)紹1、B2、B3、B4，4個銷售點，數(shù)據(jù)如下表，求最優(yōu)運輸方案。B1B2B3B4產量A13113107A219284A3741059銷量365620一、運輸問題模型及其求解思路例：某食品公司下屬的A1、A2、9二、確定初始基本可行解1、西北（左上）角法每次找最西北角的元素，讓其運輸量盡可能的滿足一個約束條件。二、確定初始基本可行解1、西北（左上）角法10二、確定初始基本可行解B1B2B3B4產量A13113107A219284A3741059銷量365620342236二、確定初始基本可行解B1B2B3B4產量A1311310711二、確定初始基本可行解這樣得到的初始基本可行解為：

x11=3,x12=4,x22=2,x23=2,x33=3,x34=6，其余均為0。

對應的總運費為：

3×3+4×11+2×9+2×2+3×10+6×5＝135二、確定初始基本可行解這樣得到的初始基本可行解為：

x11=12二、確定初始基本可行解2、最小元素法每次找到剩下的最小運價，讓其對應的運輸量盡可能的滿足一個約束條件。二、確定初始基本可行解2、最小元素法13二、確定初始基本可行解B1B2B3B4產量A13113107A219284A3741059銷量365620343163二、確定初始基本可行解B1B2B3B4產量A1311310714二、確定初始基本可行解用最小元素法求出的初始基本可行解為：

x21=3,x22=1,x13=4,x32=6,x34=3,x14=3,其余均為0。

對應的總運費為：

3×1+1×2+4×3+6×4+3×5+3×10＝86二、確定初始基本可行解用最小元素法求出的初始基本可行解為：

15二、確定初始基本可行解為保證基變量的個數(shù)有m+n-1個，注意：1、每次填完數(shù)，只能劃去一行或一列，只有最后一個格子例外。2、用最小元素法時，可能會出現(xiàn)基變量個數(shù)還差兩個以上但只剩下一行或一列的情況，此時不能將剩下行或列按空格劃掉，應在剩下的空格中標上0。（退化的基本可行解）二、確定初始基本可行解為保證基變量的個數(shù)有m+n-1個，注意16二、確定初始基本可行解B1B2B3B4產量A13113108A219283A3741059銷量365620353063二、確定初始基本可行解B1B2B3B4產量A1311310817二、確定初始基本可行解B1B2B3B4產量A13113104A219284A3741059銷量365317340163二、確定初始基本可行解B1B2B3B4產量A1311310418三、最優(yōu)性檢驗檢驗數(shù)的意義：非基變量增加一個單位，使目標函數(shù)值增加的數(shù)量。運輸問題中目標函數(shù)值要求最小化，因此，當所有的檢驗數(shù)都大于或等于零時該調運方案就是最優(yōu)方案；否則不是。下面介紹兩種計算檢驗數(shù)的方法：三、最優(yōu)性檢驗檢驗數(shù)的意義：非基變量增加一個單位，使目標函數(shù)19三、最優(yōu)性檢驗1、閉回路法閉回路：在已給出基本解的運輸表上，從一個非基變量出發(fā)，沿水平或豎直方向前進，只有碰到基變量，才能向右或向左轉90o(當然也可以不改變方向）繼續(xù)前進。這樣繼續(xù)下去，總能回到出發(fā)的那個非基變量，由此路線形成的封閉曲線，叫閉回路。三、最優(yōu)性檢驗1、閉回路法20三、最優(yōu)性檢驗每一個非基變量都有唯一的閉回路B1B2B3B4產量A13113

410

37A21

392

184A374

6105

39銷量365620三、最優(yōu)性檢驗每一個非基變量都有唯一的閉回路B1B2B3B421則變量個數(shù)為m×n個，線性無關的約束條件個數(shù)為m+n-1，333二、確定初始基本可行解對于產銷平衡的運輸問題，若產地為m個，銷地為n個，位勢法：設產地Ai對應的位勢量為ui，銷地Bj對應的位勢量為vj，檢驗數(shù)ij=cij–ui-vj。則變量個數(shù)為m×n個，線性無關的約束條件個數(shù)為m+n-1，因為位勢量ui,vj的總數(shù)為m+n個，而限定方程只有m+n-1個（基變量個數(shù)），所以位勢量（ui,vj）有無窮多組解，其中總有一個自由變量。2、產銷平衡運輸問題模型的特點1根據(jù)基變量xij的檢驗數(shù)ij=0，對應基變量的運價cij可以分解為ui和vj，即cij=ui+vj。3二、確定初始基本可行解1對于產銷平衡的運輸問題，若產地為m個，銷地為n個，那么確定xpq為出基變量，為調整量；五、運輸問題的幾種特殊情況若讓x11＝1，則總運費變化：3–3+2–1＝1。3行數(shù)為2（產地數(shù)）+3（銷地數(shù)）＝5；三、最優(yōu)性檢驗觀察x24的閉回路：若讓第一個頂點非基變量x24的取值變?yōu)?，為了保持產銷平衡，其閉回路上的頂點運量都要調整，基數(shù)頂點+1，偶數(shù)頂點-1。上述調整使總的運輸費用發(fā)生的變化為8–10+3–2＝-1，這就說明原方案還不是最優(yōu)方案，需要進行調整。則變量個數(shù)為m×n個，線性無關的約束條件個數(shù)為m+n-1，三22三、最優(yōu)性檢驗B1B2B3B4產量A13113

410

37A21

392

184A374

6105

39銷量365620若讓x11＝1，則總運費變化：3–3+2–1＝1。三、最優(yōu)性檢驗B1B2B3B4產量A13113107A21923三、最優(yōu)性檢驗如果規(guī)定作為起始頂點的非基變量xij為第1個頂點，其閉回路上的其他頂點依次為第2個頂點、第3個頂點……，那么就有該非基變量的檢驗數(shù)：ij=(閉回路上的奇數(shù)頂點運價之和)-(閉回路上的偶數(shù)頂點運價之和)最優(yōu)標準：所有檢驗數(shù)≥0三、最優(yōu)性檢驗如果規(guī)定作為起始頂點的非基變量xij為第124三、最優(yōu)性檢驗B1B2B3B4產量A13

113

410

37A21

39

2

18

4A37

4

610

5

39銷量365620檢驗數(shù)計算如下表：（1）（2）（1）（-1）（10）（12）三、最優(yōu)性檢驗B1B2B3B4產量A13113107A21925三、最優(yōu)性檢驗2、位勢法閉回路法的缺點：當變量個數(shù)較多時，尋找閉回路以及計算兩方面都容易出錯。位勢法：設產地Ai對應的位勢量為ui，銷地Bj對應的位勢量為vj，檢驗數(shù)ij=cij–ui-vj。三、最優(yōu)性檢驗2、位勢法26三、最優(yōu)性檢驗B1B2B3B4產量uiA13

11

3

410

37u1A21

39

2184u2A37

4

6105

39u3銷量365620vjv1v2v3v4三、最優(yōu)性檢驗B1B2B3B4產量uiA13113107u27三、最優(yōu)性檢驗根據(jù)基變量xij的檢驗數(shù)ij=0，對應基變量的運價cij可以分解為ui和vj，即cij=ui+vj。因為位勢量ui,vj的總數(shù)為m+n個，而限定方程只有m+n-1個（基變量個數(shù)），所以位勢量（ui,vj）有無窮多組解，其中總有一個自由變量。故可以任意取一個位勢量賦以定值，從而確定其它位勢量的值，一般取u1＝0。三、最優(yōu)性檢驗根據(jù)基變量xij的檢驗數(shù)ij=0，對應281二、確定初始基本可行解x11f*=3×5+10×2+1×3+8×1+4×6+5×3=852、用最小元素法時，可能會出現(xiàn)基變量個數(shù)還差兩個以上但只剩下一行或一列的情況，此時不能將剩下行或列按空格劃掉，應在剩下的空格中標上0。一個或多個基變量等于0。336二、確定初始基本可行解3、運輸問題求解思路——表上作業(yè)法再觀察模型的系數(shù)矩陣：二、確定初始基本可行解對于產銷平衡的運輸問題，若產地為m個，銷地為n個，100100150如上例中的最優(yōu)方案就不唯一：得到新的基變量：x13=5,x14=2,x21=3,x24=1,x32=6,x34=3。故基本解中的基變量個數(shù)為m+n-1。2、產銷平衡運輸問題模型的特點二、確定初始基本可行解三、最優(yōu)性檢驗10392vj206563銷量bj-595

310

4

67

A3-148

2

19

1

3A20710

33

411

3

A1ui產量aiB4B3B2B1（1）（2）（1）（-1）（10）（12）1三、最優(yōu)性檢驗10392vj206563銷量bj-595129檢驗數(shù)計算總結1、閉回路法計算式：ij=(閉回路上的奇數(shù)頂點運價之和)-(閉回路上的偶數(shù)頂點運價之和)2、位勢法計算式：ij=cij-ui–vj

檢驗數(shù)計算總結1、閉回路法計算式：30四、方案調整B1B2B3B4產量A13（1）11（2）3

410

37A21

39（1）2

18（-1）4A37（10）4

610（12）5

39銷量365620最小檢驗數(shù)原則，確定進基變量最小偶點原則，確定出基變量和調整量+1-1+1-1四、方案調整B1B2B3B4產量A13113107A219231四、方案調整B1B2B3B4產量aiA13

11

3

510

27A21

39

2

8

14A37

4

610

5

39銷量bj365620得到新的基變量：x13=5,x14=2,x21=3,x24=1,x32=6,x34=3。重新計算檢驗數(shù)。（0）（2）（2）（1）（9）（12）四、方案調整B1B2B3B4產量aiA13113107A2132四、方案調整經(jīng)過一次基變換，所有ij≥0，已得到最優(yōu)解：x13=5,x14=2,x21=3,x24=1,x32=6,x34=3，其它為0。最優(yōu)值：f*=3×5+10×2+1×3+8×1+4×6+5×3=85四、方案調整33四、方案調整閉回路調整法步驟：1、入基變量的確定：選負檢驗數(shù)中最小者rk，那么xrk作為進基變量；（使總運費盡快減少）2、出基變量的確定：在進基變量xrk的閉回路上，選取偶數(shù)頂點上調運量最小的值，將其對應的運量作為出基變量。（剛好有一個基變量出基，其它基變量都為正）四、方案調整閉回路調整法步驟：34每一個非基變量都有唯一的閉回路每次找到剩下的最小運價，讓其對應的運輸量盡可能的滿足一個約束條件。3二、確定初始基本可行解6一、運輸問題模型及其求解思路2、產銷平衡運輸問題模型的特點2、產銷平衡運輸問題模型的特點2、產銷平衡運輸問題模型的特點最小檢驗數(shù)原則，確定進基變量這樣得到的初始基本可行解為：

x11=3,x12=4,x22=2,x23=2,x33=3,x34=6，其余均為0。二、確定初始基本可行解故基本解中的基變量個數(shù)為m+n-1。每次找最西北角的元素，讓其運輸量盡可能的滿足一個約束條件。3位勢法：設產地Ai對應的位勢量為ui，銷地Bj對應的位勢量為vj，檢驗數(shù)ij=cij–ui-vj。1若讓x11＝1，則總運費變化：3–3+2–1＝1。故基本解中的基變量個數(shù)為m+n-1。3四、方案調整即求=Min{xij閉回路上的偶數(shù)頂點的xij}=xpq。那么確定xpq為出基變量，為調整量；3、換基調整：對閉回路的奇數(shù)頂點運量調整為：xij+，對各偶數(shù)頂點運量調整為：xij-，特別xpq-=0，xpq變?yōu)榉腔兞俊Ｖ貜鸵陨喜襟E，直到所有檢驗數(shù)均非負，即得到最優(yōu)解。每一個非基變量都有唯一的閉回路四、方案調整即求=Min{x35練習題

已知如下運價表，用表上作業(yè)法求解：產銷地B1B2B3B4產量A165344A244756A376583銷量243413練習題

已知如下運價表，用表上作業(yè)法求解：產銷地B1B2B336初始解對應目標值為3×3+4×1+4×2+4×4+8×3＝61產銷地B1B2B3B4產量uiA165344A244756A376583銷量243413vj3421030341334(3)(2)(3)(0)(-1)(-2)初始解對應目標值為3×3+4×1+4×2+4×4+837產銷地B1B2B3B4產量uiA165344A244756A376583銷量243413vj4030240341332(3)(2)(3)(2)(1)(2)已達到最優(yōu)，最優(yōu)目標值為4×4+4×2+4×4+5×3＝55產銷地B1B2B3B4產量uiA165344A244756A38五、運輸問題的幾種特殊情況1、多個最優(yōu)方案的情況：若最優(yōu)表中有非基變量的檢驗數(shù)為0，則為多個最優(yōu)方案的情況。這種情況下，可將檢驗數(shù)為0的非基變量作為進基變量，即可得到另一個最優(yōu)方案。五、運輸問題的幾種特殊情況1、多個最優(yōu)方案的情況：39五、運輸問題的幾種特殊情況B1B2B3B4產量aiA13

11

3

510

27A21

39

2

8

14A37

4

610

5

39銷量bj365620如上例中的最優(yōu)方案就不唯一：（0）（2）（2）（1）（9）（12）檢驗數(shù)為0者進基最小偶點為出基變量和調整量+2-2-2+2五、運輸問題的幾種特殊情況B1B2B3B4產量aiA131140五、運輸問題的幾種特殊情況得到另一個最優(yōu)方案：x11=2,x13=5,x21=1,x24=3,x32=6,x34=3,其余xij=0；最優(yōu)值仍然為f*=85五、運輸問題的幾種特殊情況41五、運輸問題的幾種特殊情況2、無解情況：當某個產地Ai不能向某個銷地Bj供應產品時，設相應的運費為M（類似于大M法），然后求最優(yōu)解。在最優(yōu)解中，若相應xij的取值為0，則此最優(yōu)解為原問題的最優(yōu)解；若xij的取值不為0，則原問題無解。五、運輸問題的幾種特殊情況2、無解情況：424運輸問題中目標函數(shù)值要求最小化，因此，當所有的檢驗數(shù)都大于或等于零時該調運方案就是最優(yōu)方案；二、確定初始基本可行解五、運輸問題的幾種特殊情況二、確定初始基本可行解二、確定初始基本可行解二、確定初始基本可行解000111300最小檢驗數(shù)原則，確定進基變量一、運輸問題模型及其求解思路對于產銷平衡的運輸問題，若產地為m個，銷地為n個，3根據(jù)基變量xij的檢驗數(shù)ij=0，對應基變量的運價cij可以分解為ui和vj，即cij=ui+vj。二、確定初始基本可行解五、運輸問題的幾種特殊情況2、產銷平衡運輸問題模型的特點已達到最優(yōu)，最優(yōu)目標值為4×4+4×2+4×4+5×3＝55位勢法：設產地Ai對應的位勢量為ui，銷地Bj對應的位勢量為vj，檢驗數(shù)ij=cij–ui-vj。1110002003則變量個數(shù)為m×n個，線性無關的約束條件個數(shù)為m+n-1，二、確定初始基本可行解5那么確定xpq為出基變量，為調整量；一個或多個基變量等于0。五、運輸問題的幾種特殊情況若讓x11＝1，則總運費變化：3–3+2–1＝1。3則變量個數(shù)為m×n個，線性無關的約束條件個數(shù)為m+n-1，ij=cij-ui–vj五、運輸問題的幾種特殊情況f*=3×5+10×2+1×3+8×1+4×6+5×3=85111000200ij=(閉回路上的奇數(shù)頂點運價之和)-(閉回路上的偶數(shù)頂點運價之和)五、運輸問題的幾種特殊情況若讓x11＝1，則總運費變化：3–3+2–1＝1。故可以任意取一個位勢量賦以定值，從而確定其它位勢量的值，一般取u1＝0。位勢法：設產地Ai對應的位勢量為ui，銷地Bj對應的位勢量為vj，檢驗數(shù)ij=cij–ui-vj。行數(shù)為2（產地數(shù)）+3（銷地數(shù)）＝5；行數(shù)為2（產地數(shù)）+3（銷地數(shù)）＝5；那么確定xpq為出基變量，為調整量；五、運輸問題的幾種特殊情況3、退化情況一個或多個基變量等于0。思考：運輸問題是否存在無界解情況？4二、確定初始基本可行解五、運輸問題的幾種特殊情況3、退化情43一、運輸問題模型及其求解思路1、問題的提出：某公司從兩個產地A1、A2將物品運往三個銷地B1、B2、B3。各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示。問：應如何調運可使總運輸費用最??？一、運輸問題模型及其求解思路1、問題的提出：44一、運輸問題模型及其求解思路B1B2B3產量A1646200A2655300銷量150150200一、運輸問題模型及其求解思路B1B2B3產量A164620045一、運輸問題模型及其求解思路2、產銷平衡運輸問題模型的特點從模型的建立可知：列數(shù)為2（產地數(shù)）×3（銷地數(shù)）＝6；行數(shù)為2（產地數(shù)）+3（銷地數(shù)）＝5；再觀察模型的系數(shù)矩陣：一、運輸問題模型及其求解思路2、產銷平衡運輸問題模型的特點46一、運輸問題模型及其求解思路111000200

000111300100100150

010010150

001001200前2行之和＝后3行之和一、運輸問題模型及其求解思路1147一、運輸問題模型及其求解思路對于產銷平衡的運輸問題，若產地為m個，銷地為n個，則變量個數(shù)為m×n個，線性無關的約束條件個數(shù)為m+n-1，故基本解中的基變量個數(shù)為m+n-1。一、運輸問題模型及其求解思路對于產銷平衡的運輸問題，若產地為48一、運輸問題模型及其求解思路3、運輸問題求解思路——表上作業(yè)法由于運輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計算，則無法利用這些有利條件。人們在分析運輸規(guī)劃系數(shù)矩陣特征的基礎上建立了針對運輸問題的表上作業(yè)法。一、運輸問題模型及其求解思路3、運輸問題求解思路——表上作業(yè)49一、運輸問題模型及其求解思路B1B2B3產量A16x114x126x13200A26x215x225x23300銷量150150200我們關心的量均在運價表和運量表中，故將兩表和為作業(yè)表：一、運輸問題模型及其求解思路B1B2B3產量A164650由于運輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計算，則無法利用這些有利條件。下面介紹兩種計算檢驗數(shù)的方法：2、產銷平衡運輸問題模型的特點613如上例中的最優(yōu)方案就不唯一：二、確定初始基本可行解二、確定初始基本可行解五、運輸問題的幾種特殊情況3在最優(yōu)解中，若相應xij的取值為0，則此最優(yōu)解為原問題的最優(yōu)解；已達到最優(yōu)，最優(yōu)目標值為4×4+4×2+4×4+5×3＝55五、運輸問題的幾種特殊情況010010150即求=Min{xij閉回路上的偶數(shù)頂點的xij}=xpq。ij=cij-ui–vj則變量個數(shù)為m×n個，線性無關的約束條件個數(shù)為m+n-1，33、運輸問題求解思路——表上作業(yè)法一、運輸問題模型及其求解思路表上作業(yè)法的總體思路和單純形法類似：基本可行解是否最優(yōu)解結束換基是否每個步驟都充分利用運輸表的特點由于運輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求51一、運輸問題模型及其求解思路例：某食品公司下屬的A1、A2、A3，3個廠生產方便食品，要運輸?shù)紹1、B2、B3、B4，4個銷售點，數(shù)據(jù)如下表，求最優(yōu)運輸方案。B1B2B3B4產量A13113107A219284A3741059銷量365620一、運輸問題模型及其求解思路例：某食品公司下屬的A1、A2、52二、確定初始基本可行解1、西北（左上）角法每次找最西北角的元素，讓其運輸量盡可能的滿足一個約束條件。二、確定初始基本可行解1、西北（左上）角法53二、確定初始基本可行解B1B2B3B4產量A13113107A219284A3741059銷量365620342236二、確定初始基本可行解B1B2B3B4產量A1311310754二、確定初始基本可行解這樣得到的初始基本可行解為：

x11=3,x12=4,x22=2,x23=2,x33=3,x34=6，其余均為0。

對應的總運費為：

3×3+4×11+2×9+2×2+3×10+6×5＝135二、確定初始基本可行解這樣得到的初始基本可行解為：

x11=55二、確定初始基本可行解2、最小元素法每次找到剩下的最小運價，讓其對應的運輸量盡可能的滿足一個約束條件。二、確定初始基本可行解2、最小元素法56二、確定初始基本可行解B1B2B3B4產量A13113107A219284A3741059銷量365620343163二、確定初始基本可行解B1B2B3B4產量A1311310757二、確定初始基本可行解用最小元素法求出的初始基本可行解為：

x21=3,x22=1,x13=4,x32=6,x34=3,x14=3,其余均為0。

對應的總運費為：

3×1+1×2+4×3+6×4+3×5+3×10＝86二、確定初始基本可行解用最小元素法求出的初始基本可行解為：

58二、確定初始基本可行解為保證基變量的個數(shù)有m+n-1個，注意：1、每次填完數(shù)，只能劃去一行或一列，只有最后一個格子例外。2、用最小元素法時，可能會出現(xiàn)基變量個數(shù)還差兩個以上但只剩下一行或一列的情況，此時不能將剩下行或列按空格劃掉，應在剩下的空格中標上0。（退化的基本可行解）二、確定初始基本可行解為保證基變量的個數(shù)有m+n-1個，注意59二、確定初始基本可行解B1B2B3B4產量A13113108A219283A3741059銷量365620353063二、確定初始基本可行解B1B2B3B4產量A1311310860二、確定初始基本可行解B1B2B3B4產量A13113104A219284A3741059銷量365317340163二、確定初始基本可行解B1B2B3B4產量A1311310461三、最優(yōu)性檢驗檢驗數(shù)的意義：非基變量增加一個單位，使目標函數(shù)值增加的數(shù)量。運輸問題中目標函數(shù)值要求最小化，因此，當所有的檢驗數(shù)都大于或等于零時該調運方案就是最優(yōu)方案；否則不是。下面介紹兩種計算檢驗數(shù)的方法：三、最優(yōu)性檢驗檢驗數(shù)的意義：非基變量增加一個單位，使目標函數(shù)62三、最優(yōu)性檢驗1、閉回路法閉回路：在已給出基本解的運輸表上，從一個非基變量出發(fā)，沿水平或豎直方向前進，只有碰到基變量，才能向右或向左轉90o(當然也可以不改變方向）繼續(xù)前進。這樣繼續(xù)下去，總能回到出發(fā)的那個非基變量，由此路線形成的封閉曲線，叫閉回路。三、最優(yōu)性檢驗1、閉回路法63三、最優(yōu)性檢驗每一個非基變量都有唯一的閉回路B1B2B3B4產量A13113

410

37A21

392

184A374

6105

39銷量365620三、最優(yōu)性檢驗每一個非基變量都有唯一的閉回路B1B2B3B464則變量個數(shù)為m×n個，線性無關的約束條件個數(shù)為m+n-1，333二、確定初始基本可行解對于產銷平衡的運輸問題，若產地為m個，銷地為n個，位勢法：設產地Ai對應的位勢量為ui，銷地Bj對應的位勢量為vj，檢驗數(shù)ij=cij–ui-vj。則變量個數(shù)為m×n個，線性無關的約束條件個數(shù)為m+n-1，因為位勢量ui,vj的總數(shù)為m+n個，而限定方程只有m+n-1個（基變量個數(shù)），所以位勢量（ui,vj）有無窮多組解，其中總有一個自由變量。2、產銷平衡運輸問題模型的特點1根據(jù)基變量xij的檢驗數(shù)ij=0，對應基變量的運價cij可以分解為ui和vj，即cij=ui+vj。3二、確定初始基本可行解1對于產銷平衡的運輸問題，若產地為m個，銷地為n個，那么確定xpq為出基變量，為調整量；五、運輸問題的幾種特殊情況若讓x11＝1，則總運費變化：3–3+2–1＝1。3行數(shù)為2（產地數(shù)）+3（銷地數(shù)）＝5；三、最優(yōu)性檢驗觀察x24的閉回路：若讓第一個頂點非基變量x24的取值變?yōu)?，為了保持產銷平衡，其閉回路上的頂點運量都要調整，基數(shù)頂點+1，偶數(shù)頂點-1。上述調整使總的運輸費用發(fā)生的變化為8–10+3–2＝-1，這就說明原方案還不是最優(yōu)方案，需要進行調整。則變量個數(shù)為m×n個，線性無關的約束條件個數(shù)為m+n-1，三65三、最優(yōu)性檢驗B1B2B3B4產量A13113

410

37A21

392

184A374

6105

39銷量365620若讓x11＝1，則總運費變化：3–3+2–1＝1。三、最優(yōu)性檢驗B1B2B3B4產量A13113107A21966三、最優(yōu)性檢驗如果規(guī)定作為起始頂點的非基變量xij為第1個頂點，其閉回路上的其他頂點依次為第2個頂點、第3個頂點……，那么就有該非基變量的檢驗數(shù)：ij=(閉回路上的奇數(shù)頂點運價之和)-(閉回路上的偶數(shù)頂點運價之和)最優(yōu)標準：所有檢驗數(shù)≥0三、最優(yōu)性檢驗如果規(guī)定作為起始頂點的非基變量xij為第167三、最優(yōu)性檢驗B1B2B3B4產量A13

113

410

37A21

39

2

18

4A37

4

610

5

39銷量365620檢驗數(shù)計算如下表：（1）（2）（1）（-1）（10）（12）三、最優(yōu)性檢驗B1B2B3B4產量A13113107A21968三、最優(yōu)性檢驗2、位勢法閉回路法的缺點：當變量個數(shù)較多時，尋找閉回路以及計算兩方面都容易出錯。位勢法：設產地Ai對應的位勢量為ui，銷地Bj對應的位勢量為vj，檢驗數(shù)ij=cij–ui-vj。三、最優(yōu)性檢驗2、位勢法69三、最優(yōu)性檢驗B1B2B3B4產量uiA13

11

3

410

37u1A21

39

2184u2A37

4

6105

39u3銷量365620vjv1v2v3v4三、最優(yōu)性檢驗B1B2B3B4產量uiA13113107u70三、最優(yōu)性檢驗根據(jù)基變量xij的檢驗數(shù)ij=0，對應基變量的運價cij可以分解為ui和vj，即cij=ui+vj。因為位勢量ui,vj的總數(shù)為m+n個，而限定方程只有m+n-1個（基變量個數(shù)），所以位勢量（ui,vj）有無窮多組解，其中總有一個自由變量。故可以任意取一個位勢量賦以定值，從而確定其它位勢量的值，一般取u1＝0。三、最優(yōu)性檢驗根據(jù)基變量xij的檢驗數(shù)ij=0，對應711二、確定初始基本可行解x11f*=3×5+10×2+1×3+8×1+4×6+5×3=852、用最小元素法時，可能會出現(xiàn)基變量個數(shù)還差兩個以上但只剩下一行或一列的情況，此時不能將剩下行或列按空格劃掉，應在剩下的空格中標上0。一個或多個基變量等于0。336二、確定初始基本可行解3、運輸問題求解思路——表上作業(yè)法再觀察模型的系數(shù)矩陣：二、確定初始基本可行解對于產銷平衡的運輸問題，若產地為m個，銷地為n個，100100150如上例中的最優(yōu)方案就不唯一：得到新的基變量：x13=5,x14=2,x21=3,x24=1,x32=6,x34=3。故基本解中的基變量個數(shù)為m+n-1。2、產銷平衡運輸問題模型的特點二、確定初始基本可行解三、最優(yōu)性檢驗10392vj206563銷量bj-595

310

4

67

A3-148

2

19

1

3A20710

33

411

3

A1ui產量aiB4B3B2B1（1）（2）（1）（-1）（10）（12）1三、最優(yōu)性檢驗10392vj206563銷量bj-595172檢驗數(shù)計算總結1、閉回路法計算式：ij=(閉回路上的奇數(shù)頂點運價之和)-(閉回路上的偶數(shù)頂點運價之和)2、位勢法計算式：ij=cij-ui–vj

檢驗數(shù)計算總結1、閉回路法計算式：73四、方案調整B1B2B3B4產量A13（1）11（2）3

410

37A21

39（1）2

18（-1）4A37（10）4

610（12）5

39銷量365620最小檢驗數(shù)原則，確定進基變量最小偶點原則，確定出基變量和調整量+1-1+1-1四、方案調整B1B2B3B4產量A13113107A219274四、方案調整B1B2B3B4產量aiA13

11

3

510

27A21

39

2

8

14A37

4

610

5

39銷量bj365620得到新的基變量：x13=5,x14=2,x21=3,x24=1,x32=6,x34=3。重新計算檢驗數(shù)。（0）（2）（2）（1）（9）（12）四、方案調整B1B2B3B4產量aiA13113107A2175四、方案調整經(jīng)過一次基變換，所有ij≥0，已得到最優(yōu)解：x13=5,x14=2,x21=3,x24=1,x32=6,x34=3，其它為0。最優(yōu)值：f*=3×5+10×2+1×3+8×1+4×6+5×3=85四、方案調整76四、方案調整閉回路調整法步驟：1、入基變量的確定：選負檢驗數(shù)中最小者rk，那么xrk作為進基變量；（使總運費盡快減少）2、出基變量的確定：在進基變量xrk的閉回路上，選取偶數(shù)頂點上調運量最小的值，將其對應的運量作為出基變量。（剛好有一個基變量出基，其它基變量都為正）四、方案調整閉回路調整法步驟：77每一個非基變量都有唯一的閉回路每次找到剩下的最小運價，讓其對應的運輸量盡可能的滿足一個約束條件。3二、確定初始基本可行解6一、運輸問題模型及其求解思路2、產銷平衡運輸問題模型的特點2、產銷平衡運輸問題模型的特點2、產銷平衡運輸問題模型的特點最小檢驗數(shù)原則，確定進基變量這樣得到的初始基本可行解為：

x11=3,x12=4,x22=2,x23=2,x33=3,x34=6，其余均為0。二、確定初始基本可行解故基本解中的基變量個數(shù)為m+n-1。每次找最西北角的元素，讓其運輸量盡可能的滿足一個約束條件。3位勢法：設產地Ai對應的位勢量為ui，銷地Bj對應的位勢量為vj，檢驗數(shù)ij=cij–ui-vj。1若讓x11＝1，則總運費變化：3–3+2–1＝1。故基本解中的基變量個數(shù)為m+n-1。3四、方案調整即求=Min{xij閉回路上的偶數(shù)頂點的xij}=xpq。那么確定xpq為出基變量，為調整量；3、換基調整：對閉回路的奇數(shù)頂點運量調整為：xij+，對各偶數(shù)頂點運量調整為：xij-，特別xpq-=0，xpq變?yōu)榉腔兞?。重復以上步驟，直到所有檢驗數(shù)均非負，即得到最優(yōu)解。每一個非基變量都有唯一的閉回路四、方案調整即求=Min{x78練習題

已知如下運價表，用表上作業(yè)法求解：產銷地B1B2B3B4產量A165344A244756A376583銷量243413練習題

已知如下運價表，用表上作業(yè)法求解：產銷地B1B2B379初始解對應目標值為3×3+4×1+4×2+4×4+8×3＝61產銷地B1B2B3B4產量uiA165344A244756A376583銷量243413vj3421030341334(3)(2)(3)(0)(-1)(-2)