§2.1表上作業法

精品課程《運籌學》表上作業法表上作業法:建立在運輸費用矩陣的求解運輸問題的方法。表上作業法求解運輸問題的思想和單純形法完全類似：確定一個初始基本可行解——

根據最優性判別準則來檢查這個基本可行解是不是最優的？如果是，則計算結束；如果不是，則進行換基。

——

直至求出最優解為止。精品課程《運籌學》表上作業法

一、初始基本可行解的確定

根據上面的討論，要求得運輸問題的初始基本可行解，必須保證找到m+n–1個不構成閉回路的基變量。

一般的方法步驟如下：

精品課程《運籌學》表上作業法(1)在運輸問題求解作業數據表中任選一個單元格xij(Ai

行Bj

列交叉位置上的格),令

xij

=min{ai,bj

}

即從Ai

向Bj

運最大量(使行或列在允許的范圍內盡量飽和，即使一個約束方程得以滿足),填入xij

的相應位置；精品課程《運籌學》表上作業法(2)從ai

和bj

中分別減去xij

的值，修正為新的ai

和bj，即調整Ai

的擁有量及Bj

的需求量；(3)若ai=0，則劃去對應的行（已經把擁有的量全部運走），若bj=0

則劃去對應的列（已經把需要的量全部運來），且每次只劃去一行或一列（即每次要去掉且只去掉一個約束）；精品課程《運籌學》表上作業法(4)當最終的運輸量選定時，其所在行、列同時滿足，此時要同時劃去一行和一列。這樣，運輸平衡表中所有的行與列均被劃去，則得到了一個初始基本可行解。否則在剩下的運輸平衡表中選下一個變量，返回(1)。精品課程《運籌學》表上作業法上述計算過程可用流程圖描述如下取未劃去的單元格xij

,令xij

=min{ai,bj

}ai’=ai-xijbj’=bj-xijai’=0?劃去第i行劃去第j列是否

bj’=0否所有行列是否均被劃去是找到初始基本可行解求運輸問題的初始基本可行解過程注：為了方便，這里總記剩余的產量和銷量為ai,bj精品課程《運籌學》表上作業法

按照上述方法所產生的一組變量的取值將滿足下面條件：

(1)所得的變量均為非負，且變量總數恰好為m+n–1個；

(2)所有的約束條件均得到滿足；

(3)所得的變量不構成閉回路。精品課程《運籌學》表上作業法

因此，根據定理及其推論，所得的解一定是運輸問題的基本可行解。

在上面的方法中，xij

的選取方法并沒有給予限制，若采取不同的規則來選取xij

，則得到不同的方法，較常用的方法有西北角法和最小元素法。下面分別舉例予以說明。精品課程《運籌學》表上作業法1、初始基本可行解的確定（1）西北角法：從西北角（左上角）格開始，在格內的右下角標上允許取得的最大數。然后按行（列）標下一格的數。若某行（列）的產量（銷量）已滿足，則把該行（列）的其他格劃去。如此進行下去，直至得到一個基本可行解。精品課程《運籌學》表上作業法

（2）最小元素法：從運價最小的格開始，在格內的右下角標上允許取得的最大數。然后按運價從小到大順序填數。若某行（列）的產量（銷量）已滿足，則把該行（列）的其他格劃去。如此進行下去，直至得到一個基本可行解。精品課程《運籌學》表上作業法

注:應用西北角法和最小元素法，每次填完數，都只劃去一行或一列，只有最后一個元例外（同時劃去一行和一列）。當填上一個數后行、列同時飽和時，也應任意劃去一行（列），在保留的列（行）中沒被劃去的格內標一個0。精品課程《運籌學》表上作業法精品課程《運籌學》表上作業法精品課程《運籌學》表上作業法精品課程《運籌學》表上作業法

最優性檢驗就是檢查所得到的方案是不是最優方案。檢查的方法與單純形方法中的原理相同，即計算檢驗數。由于目標要求極小，因此，當所有的檢驗數都大于或等于零時該調運方案就是最優方案；否則就不是最優，需要進行調整。下面介紹兩種求檢驗數的方法。

二、基本可行解的最優性檢驗精品課程《運籌學》表上作業法1、閉回路法為了方便，我們以上表給出的初始基本可行解方案為例，考察初始方案的任意一個非基變量，比如x24。根據初始方案，產地A2的產品是不運往銷地B4的。如果現在改變初始方案，把A2的產品運送1個單位給B4

，那么為了保持產銷平衡，就必須使x14

或x34

減少1個單位；而如果x14

減少1個單位，第1行的運輸量就必須增加1個單位，例如x13

增加1個單位，那么為了保持產銷平衡，就必須使x23

減少1個單位。精品課程《運籌學》表上作業法

這個過程就是尋找一個以非基變量x24

為起始頂點的閉回路——{x24

，x14

，x13

，x23}，這個閉回路的其他頂點均為基變量(對應著填上數字的格)。容易計算出上述調整使總的運輸費用發生的變化為8–10+3–2＝-1，即總的運費減少1個單位，這就說明原始方案不是最優方案，可以進行調整以得到更好的方案。精品課程《運籌學》表上作業法

可以證明，如果對閉回路的方向不加區別（即只要起點及其他所有頂點完全相同，而不區別行進方向），那么以每一個非基量為起始頂點的閉回路就存在而且唯一。因此，對每一個非基變量可以找到而且只能找到唯一的一個閉回路。下表中用虛線畫出以非基變量x22

為起始頂點的閉回路。精品課程《運籌學》表上作業法銷地產地B1B2B3B4產量3[]11[]341037139[]218[]47[]4610[]539銷量365620(產銷平衡)A1A2A3精品課程《運籌學》表上作業法

可以計算出以非基變量x22

為起始頂點的閉回路調整使總的運輸費用發生的變化為

9–2+3–10+5–4＝1

即總的運費增加1個單位，這就說明這個調整不能改善目標值。從上面的討論可以看出，當某個非基變量增加一個單位時，有若干個基變量的取值受其影響。精品課程《運籌學》表上作業法

這樣，利用單位產品變化（運輸的單位費用）可計算出它們對目標函數的綜合影響，其作用與線性規劃單純形方法中的檢驗數完全相同。故也稱這個綜合影響為該非基變量對應的檢驗數。上面計算的兩個非基變量的檢驗數為

24=-1，

22=1。閉回路方法原理就是通過尋找閉回路來找到非基變量的檢驗數。精品課程《運籌學》表上作業法

如果規定作為起始頂點的非基變量為第1個頂點，閉回路的其他頂點依次為第2個頂點、第3個頂點……，那么就有

ij=(閉回路上的奇數次頂點單位運費之和)-(閉回路上的偶數次頂點單位運費之和)

其中ij為非基變量的下角指標。精品課程《運籌學》表上作業法

按上述作法，可計算出表中的所有非基變量的檢驗數，把它們填入相應位置的方括號內，如下圖所示。

銷地產地B1B2B3B4產量A13[1]11[2]341037A2139[1]218[-1]4A37[10]4610[12]539銷量365620(產銷平衡)初始基本可行解及檢驗數精品課程《運籌學》表上作業法

顯然，當所有非基變量的檢驗數均大于或等于零時，現行的調運方案就是最優方案，因為此時對現行方案作任何調整都將導致總的運輸費用增加。閉回路法的主要缺點是：當變量個數較多時，尋找閉回路以及計算兩方面都會產生困難。精品課程《運籌學》表上作業法

當非基變量的檢驗數出現負值時，則表明當前的基本可行解不是最優解。在這種情況下，應該對基本可行解進行調整，即找到一個新的基本可行解使目標函數值下降，這一過程通常稱為換基(或主元變換)過程。

三、求新的基本可行解精品課程《運籌學》表上作業法

（1）選負檢驗數中最小者

rk，那么xrk

為主元，作為進基變量（上圖中x24）;

（2）以xrk

為起點找一條閉回路，除xrk

外其余頂點必須為基變量格（上頁圖中的回路）;

在運輸問題的表上作業法中，換基的過程是如下進行：精品課程《運籌學》表上作業法

（3）為閉回路的每一個頂點標號，xrk

為1，沿一個方向（順時針或逆時針）依次給各頂點標號；（4）求

=min{xij

xij對應閉回路上的偶數標號格}=xpq那么確定xpq為出基變量，

為調整量；精品課程《運籌學》表上作業法

（5）對閉回路的各奇標號頂點調整為：xij+

，對各偶標號頂點調整為：xij-

，特別

xpq-

=0，xpq變為非基變量。重復(2)、(3)步，直到所有檢驗數均非負，得到最優解。精品課程《運籌學》表上作業法

ij

≥0，得到最優解x13=5,x14=2,x21=3,x24=1,

x32=6,x34=3,其余xij=0;

最優值：

f*=3×5+10×2+1×3+8×1+4×6+5×3=85精品課程《運籌學》表上作業法

四、產銷不平衡問題的處理在實際中遇到的運輸問題常常不是產銷平衡的，而是下列的一般運輸問題模型

m

nminf=

cijxij

（1）

i=1j=1

n

s.t.

xij

si

i=1,2,…,m

（2）

j=1

m

xij

(=,

)dj

j=1,2,…,n(3）

i=1xij0(i=1,2,…,m;j=1,2,…,n)（4）精品課程《運籌學》表上作業法

我們可以通過增加虛設產地或銷地（加、減松弛變量）把問題轉換成產銷平衡問題，下面分別來討論。

1.產量大于銷量的情況

m

n

考慮

si>dj的運輸問題，得到的數學模

i=1

j=1型為精品課程《運籌學》表上作業法

mn

minf=

cijxij

i=1j=1

n

s.t.

xij

si

i=1,2,…,m

j=1

m

xij

=dj

j=1,2,…,n

i=1

xij≥0(i=1,2,…,m;j=1,2,…,n)精品課程《運籌學》表上作業法

只要在模型中的產量限制約束（前m個不等式約束）中引入m個松弛變量xi,n+1i=1,2,…,m即可，變為：

n

xij+xin+1=si

i=1,2,…mj=1然后，需設一個銷地Bn+1,它的銷量為：

mn

bn+1=si-dj

i=1j=1

精品課程《運籌學》表上作業法

這里，松弛變量xin+1

可以視為從產地Ai

運往銷地Bn+1

的運輸量，由于實際并不運送，它們的運費為

cin+1=0i=1,2,…,m。于是，這個運輸問題就轉化成了一個產銷平衡的問題。精品課程《運籌學》表上作業法

例:某公司從兩個產地A1、A2將物品運往三個銷地B1、B2、B3，各產地的產量、各銷地的銷量和各產地運往各銷地每件物品的運費如下表所示，問：應如何調運可使總運輸費用最??？精品課程《運籌學》表上作業法

解：增加一個虛設的銷地運輸費用為0精品課程《運籌學》表上作業法2.銷量大于產量的情況

mn

考慮

si<dj的運輸問題，得到的數學模型為

i=1

j=1

mn

Minf=

cijxij

i=1j=1

n

s.t.

xij

=si

i=1,2,…,m

j=1

m

xij

dj

j=1,2,…,n

i=1