第七章運(yùn)輸問題之表上作業(yè)法一、運(yùn)輸問題模型及其求解思路二、確定初始基本可行解三、最優(yōu)性檢驗(yàn)四、方案調(diào)整五、幾種特殊情況1精品PPT|實(shí)用可編輯第一頁，共四十六頁。一、運(yùn)輸問題模型及其求解思路1、問題的提出：某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地B1、B2、B3。各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示。問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？2精品PPT|實(shí)用可編輯第二頁，共四十六頁。一、運(yùn)輸問題模型及其求解思路3精品PPT|實(shí)用可編輯第三頁，共四十六頁。一、運(yùn)輸問題模型及其求解思路2、產(chǎn)銷平衡運(yùn)輸問題模型的特點(diǎn)從模型的建立可知：列數(shù)為2（產(chǎn)地數(shù)）×3（銷地數(shù)）＝6；行數(shù)為2（產(chǎn)地數(shù)）+3（銷地數(shù)）＝5；再觀察模型的系數(shù)矩陣：4精品PPT|實(shí)用可編輯第四頁，共四十六頁。一、運(yùn)輸問題模型及其求解思路111000200

000111300100100150

010010150

001001200前2行之和＝后3行之和5精品PPT|實(shí)用可編輯第五頁，共四十六頁。一、運(yùn)輸問題模型及其求解思路對于產(chǎn)銷平衡的運(yùn)輸問題，若產(chǎn)地為m個，銷地為n個，則變量個數(shù)為m×n個，線性無關(guān)的約束條件個數(shù)為m+n-1，故基本解中的基變量個數(shù)為m+n-1。6精品PPT|實(shí)用可編輯第六頁，共四十六頁。一、運(yùn)輸問題模型及其求解思路3、運(yùn)輸問題求解思路——表上作業(yè)法由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計算，則無法利用這些有利條件。人們在分析運(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對運(yùn)輸問題的表上作業(yè)法。7精品PPT|實(shí)用可編輯第七頁，共四十六頁。一、運(yùn)輸問題模型及其求解思路我們關(guān)心的量均在運(yùn)價表和運(yùn)量表中，故將兩表和為作業(yè)表：8精品PPT|實(shí)用可編輯第八頁，共四十六頁。一、運(yùn)輸問題模型及其求解思路表上作業(yè)法的總體思路和單純形法類似：基本可行解是否最優(yōu)解結(jié)束換基是否每個步驟都充分利用運(yùn)輸表的特點(diǎn)9精品PPT|實(shí)用可編輯第九頁，共四十六頁。一、運(yùn)輸問題模型及其求解思路例：某食品公司下屬的A1、A2、A3

，3個廠生產(chǎn)方便食品，要運(yùn)輸?shù)紹1、B2、B3、B4

，4個銷售點(diǎn)，數(shù)據(jù)如下表，求最優(yōu)運(yùn)輸方案。10精品PPT|實(shí)用可編輯第十頁，共四十六頁。二、確定初始基本可行解1、西北（左上）角法每次找最西北角的元素，讓其運(yùn)輸量盡可能的滿足一個約束條件。11精品PPT|實(shí)用可編輯第十一頁，共四十六頁。二、確定初始基本可行解34223612精品PPT|實(shí)用可編輯第十二頁，共四十六頁。二、確定初始基本可行解這樣得到的初始基本可行解為：

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

對應(yīng)的總運(yùn)費(fèi)為：

3×3+4×11+2×9+2×2+3×10+6×5＝13513精品PPT|實(shí)用可編輯第十三頁，共四十六頁。二、確定初始基本可行解2、最小元素法每次找到剩下的最小運(yùn)價，讓其對應(yīng)的運(yùn)輸量盡可能的滿足一個約束條件。14精品PPT|實(shí)用可編輯第十四頁，共四十六頁。二、確定初始基本可行解34316315精品PPT|實(shí)用可編輯第十五頁，共四十六頁。二、確定初始基本可行解用最小元素法求出的初始基本可行解為：

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

對應(yīng)的總運(yùn)費(fèi)為：

3×1+1×2+4×3+6×4+3×5+3×10＝8616精品PPT|實(shí)用可編輯第十六頁，共四十六頁。二、確定初始基本可行解為保證基變量的個數(shù)有m+n-1個，注意：1、每次填完數(shù)，只能劃去一行或一列，只有最后一個格子例外。2、用最小元素法時，可能會出現(xiàn)基變量個數(shù)還差兩個以上但只剩下一行或一列的情況，此時不能將剩下行或列按空格劃掉，應(yīng)在剩下的空格中標(biāo)上0。（退化的基本可行解）17精品PPT|實(shí)用可編輯第十七頁，共四十六頁。二、確定初始基本可行解35306318精品PPT|實(shí)用可編輯第十八頁，共四十六頁。二、確定初始基本可行解34016319精品PPT|實(shí)用可編輯第十九頁，共四十六頁。三、最優(yōu)性檢驗(yàn)檢驗(yàn)數(shù)的意義：非基變量增加一個單位，使目標(biāo)函數(shù)值增加的數(shù)量。運(yùn)輸問題中目標(biāo)函數(shù)值要求最小化，因此，當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時該調(diào)運(yùn)方案就是最優(yōu)方案；否則不是。下面介紹兩種計算檢驗(yàn)數(shù)的方法：20精品PPT|實(shí)用可編輯第二十頁，共四十六頁。三、最優(yōu)性檢驗(yàn)1、閉回路法閉回路：在已給出基本解的運(yùn)輸表上，從一個非基變量出發(fā)，沿水平或豎直方向前進(jìn)，只有碰到基變量，才能向右或向左轉(zhuǎn)90o(當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)。這樣繼續(xù)下去，總能回到出發(fā)的那個非基變量，由此路線形成的封閉曲線，叫閉回路。21精品PPT|實(shí)用可編輯第二十一頁，共四十六頁。三、最優(yōu)性檢驗(yàn)每一個非基變量都有唯一的閉回路22精品PPT|實(shí)用可編輯第二十二頁，共四十六頁。三、最優(yōu)性檢驗(yàn)觀察x24的閉回路：若讓第一個頂點(diǎn)非基變量x24的取值變?yōu)?，為了保持產(chǎn)銷平衡，其閉回路上的頂點(diǎn)運(yùn)量都要調(diào)整，基數(shù)頂點(diǎn)+1，偶數(shù)頂點(diǎn)-1。上述調(diào)整使總的運(yùn)輸費(fèi)用發(fā)生的變化為8–10+3–2＝-1，這就說明原方案還不是最優(yōu)方案，需要進(jìn)行調(diào)整。23精品PPT|實(shí)用可編輯第二十三頁，共四十六頁。三、最優(yōu)性檢驗(yàn)若讓x11＝1，則總運(yùn)費(fèi)變化：3–3+2–1＝1。24精品PPT|實(shí)用可編輯第二十四頁，共四十六頁。三、最優(yōu)性檢驗(yàn)如果規(guī)定作為起始頂點(diǎn)的非基變量xij為第1個頂點(diǎn)，其閉回路上的其他頂點(diǎn)依次為第2個頂點(diǎn)、第3個頂點(diǎn)……，那么就有該非基變量的檢驗(yàn)數(shù)：

ij=(閉回路上的奇數(shù)頂點(diǎn)運(yùn)價之和)-(閉回路上的偶數(shù)頂點(diǎn)運(yùn)價之和)最優(yōu)標(biāo)準(zhǔn)：所有檢驗(yàn)數(shù)≥025精品PPT|實(shí)用可編輯第二十五頁，共四十六頁。三、最優(yōu)性檢驗(yàn)檢驗(yàn)數(shù)計算如下表：（1）（2）（1）（-1）（10）（12）26精品PPT|實(shí)用可編輯第二十六頁，共四十六頁。三、最優(yōu)性檢驗(yàn)2、位勢法閉回路法的缺點(diǎn)：當(dāng)變量個數(shù)較多時，尋找閉回路以及計算兩方面都容易出錯。位勢法：設(shè)產(chǎn)地Ai對應(yīng)的位勢量為ui

，銷地Bj對應(yīng)的位勢量為vj，檢驗(yàn)數(shù)

ij=cij–ui-vj。27精品PPT|實(shí)用可編輯第二十七頁，共四十六頁。三、最優(yōu)性檢驗(yàn)28精品PPT|實(shí)用可編輯第二十八頁，共四十六頁。三、最優(yōu)性檢驗(yàn)根據(jù)基變量xij

的檢驗(yàn)數(shù)

ij=0，對應(yīng)基變量的運(yùn)價cij可以分解為ui

和vj，即cij=ui+vj

。因?yàn)槲粍萘縰i,vj的總數(shù)為m+n個，而限定方程只有m+n-1個（基變量個數(shù)），所以位勢量（ui,vj

）有無窮多組解，其中總有一個自由變量。故可以任意取一個位勢量賦以定值，從而確定其它位勢量的值，一般取u1

＝0。29精品PPT|實(shí)用可編輯第二十九頁，共四十六頁。三、最優(yōu)性檢驗(yàn)10392vj206563銷量bj-595

310

4

67

A3-148

2

19

1

3A20710

33

411

3

A1ui產(chǎn)量aiB4B3B2B1（1）（2）（1）（-1）（10）（12）30精品PPT|實(shí)用可編輯第三十頁，共四十六頁。檢驗(yàn)數(shù)計算總結(jié)1、閉回路法計算式：

ij=(閉回路上的奇數(shù)頂點(diǎn)運(yùn)價之和)-(閉回路上的偶數(shù)頂點(diǎn)運(yùn)價之和)2、位勢法計算式：

ij=cij-ui–vj

31精品PPT|實(shí)用可編輯第三十一頁，共四十六頁。四、方案調(diào)整最小檢驗(yàn)數(shù)原則，確定進(jìn)基變量最小偶點(diǎn)原則，確定出基變量和調(diào)整量+1-1+1-132精品PPT|實(shí)用可編輯第三十二頁，共四十六頁。四、方案調(diào)整得到新的基變量：x13=5,x14=2,x21=3,x24=1,x32=6,x34=3。重新計算檢驗(yàn)數(shù)。（0）（2）（2）（1）（9）（12）33精品PPT|實(shí)用可編輯第三十三頁，共四十六頁。四、方案調(diào)整經(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=8534精品PPT|實(shí)用可編輯第三十四頁，共四十六頁。四、方案調(diào)整閉回路調(diào)整法步驟：1、入基變量的確定：選負(fù)檢驗(yàn)數(shù)中最小者

rk，那么xrk作為進(jìn)基變量；（使總運(yùn)費(fèi)盡快減少）2、出基變量的確定：在進(jìn)基變量xrk的閉回路上，選取偶數(shù)頂點(diǎn)上調(diào)運(yùn)量最小的值，將其對應(yīng)的運(yùn)量作為出基變量。（剛好有一個基變量出基，其它基變量都為正）35精品PPT|實(shí)用可編輯第三十五頁，共四十六頁。四、方案調(diào)整即求=Min{xij

閉回路上的偶數(shù)頂點(diǎn)的xij}=xpq。那么確定xpq為出基變量，

為調(diào)整量；3、換基調(diào)整：對閉回路的奇數(shù)頂點(diǎn)運(yùn)量調(diào)整為：xij+

，對各偶數(shù)頂點(diǎn)運(yùn)量調(diào)整為：xij-

，特別xpq-=0，xpq變?yōu)榉腔兞?。重?fù)以上步驟，直到所有檢驗(yàn)數(shù)均非負(fù)，即得到最優(yōu)解。36精品PPT|實(shí)用可編輯第三十六頁，共四十六頁。練習(xí)題

已知如下運(yùn)價表，用表上作業(yè)法求解：37精品PPT|實(shí)用可編輯第三十七頁，共四十六頁。

初始解對應(yīng)目標(biāo)值為3×3+4×1+4×2+4×4+8×3＝613421030341334(3)(2)(3)(0)(-1)(-2)38精品PPT|實(shí)用可編輯第三十八頁，共四十六頁。精品PPT·收集整理第三十九頁，共四十六頁。4030240341332(3)(2)(3)(2)(1)(2)

已達(dá)到最優(yōu)，最優(yōu)目標(biāo)值為4×4+4×2+4×4+5×3＝5540精品PPT|實(shí)用可編輯第四十頁，共四十六頁。五、運(yùn)輸問題的幾種特殊情況1、多個最優(yōu)方案的情況：若最優(yōu)表中有非基變量的檢驗(yàn)數(shù)為0，則為多個最優(yōu)方案的情況。這種情況下，可將檢驗(yàn)數(shù)為0的非基變量作為進(jìn)基變量，即可得到另一個最優(yōu)方案。41精品PPT|實(shí)用可編輯第四十一頁，共四十六頁。五、運(yùn)輸問題的幾種特殊情況如上例中的最優(yōu)方案就不唯一：（0）（2）（2）（1）（9）（12）檢驗(yàn)數(shù)為0者進(jìn)基最小偶點(diǎn)為出基變量和調(diào)整量+2-2-2+242精品PPT|實(shí)用可編輯第四十二頁，共四十六頁。PPT內(nèi)容概述第七章運(yùn)輸問題之表上作業(yè)法。列數(shù)為2（產(chǎn)地數(shù)）×3（銷地數(shù)）＝6。行數(shù)為2（產(chǎn)地數(shù)）+3（銷地數(shù)）＝5。前2行之和＝后3行之和。對于產(chǎn)銷平衡的運(yùn)輸問題，若產(chǎn)地為m個，銷地為n個，。則變量個數(shù)為m×n個，線性無關(guān)的約束條件個數(shù)為m+n-1，。由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計算，則無法利用這些有利條件。人們在分析運(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對運(yùn)輸問題的表上作業(yè)法。我們關(guān)心的量均在運(yùn)價表和運(yùn)