表上作業(yè)法是一種求解運輸問題的特殊方法

1、 表上作業(yè)法是一種求解運輸問題的特殊方法，其表上作業(yè)法是一種求解運輸問題的特殊方法，其實質(zhì)是單純形法，其計算過程實質(zhì)是單純形法，其計算過程( (假設(shè)產(chǎn)銷平衡假設(shè)產(chǎn)銷平衡) )如下：如下：上周內(nèi)容回顧上周內(nèi)容回顧 方法一：最小元素法方法一：最小元素法（思想：就近供應(yīng)思想：就近供應(yīng)） 該方法的基本思想是采用該方法的基本思想是采用“優(yōu)先安排單位運價最小優(yōu)先安排單位運價最小的產(chǎn)地與銷地之間的運輸業(yè)務(wù)的產(chǎn)地與銷地之間的運輸業(yè)務(wù)”這個規(guī)則來確定初始這個規(guī)則來確定初始基可行解。基可行解。 方法二：差額法方法二：差額法(伏格爾伏格爾) 一個產(chǎn)地的產(chǎn)品，若不能按最小運費就近供應(yīng)，一個產(chǎn)地的產(chǎn)品，若不能按最小運費

2、就近供應(yīng)， 就考慮次小運費，這就有一個差額。差額越大，不就考慮次小運費，這就有一個差額。差額越大，不 能按最小運費調(diào)運時，運費增加越多。因而應(yīng)對差能按最小運費調(diào)運時，運費增加越多。因而應(yīng)對差 額最大處，優(yōu)先采用最小運費調(diào)運。額最大處，優(yōu)先采用最小運費調(diào)運。1.求初始的調(diào)運方案求初始的調(diào)運方案(初始基可行解初始基可行解)ijij = = c cijijYPYPijij = = c cijij（u u1 1，u um m，v v1 1，v vn n）P Pijij = = c cijij（u ui i+v+vj j）而所有基變量的檢驗數(shù)等于零，因此有而所有基變量的檢驗數(shù)等于零，因此有 c ciji

3、j（u ui i+v+vj j）= 0 = 0 即即 u ui i+v+vj j = = c cijij 由此，任選一個對偶變量為由此，任選一個對偶變量為0 0，可求出其余所有的，可求出其余所有的u ui i， v vj j(當(dāng)前基可行解的位勢當(dāng)前基可行解的位勢)。 再根據(jù)再根據(jù)ijij = = c cijij - ( - (u ui i+ + v vj j) )求出所有非基變量求出所有非基變量 的檢驗數(shù)。的檢驗數(shù)。方法一：位勢法方法一：位勢法2.最優(yōu)解的判定最優(yōu)解的判定(求各非基變量的檢驗數(shù)）求各非基變量的檢驗數(shù)） 閉回路法閉回路法: :就是對于代表非基變量的空格（其調(diào)就是對于代表非基變量的

4、空格（其調(diào)運量為零），把它的調(diào)運量調(diào)整為運量為零），把它的調(diào)運量調(diào)整為1 1，由于產(chǎn)銷平衡，由于產(chǎn)銷平衡的要求的要求, ,我們必須對這個空格的閉回路的頂點的調(diào)運我們必須對這個空格的閉回路的頂點的調(diào)運量加上或減少量加上或減少1 1。最后我們計算出由這些變化給整個。最后我們計算出由這些變化給整個運輸方案的總運輸費帶來的變化。如果所有代表非基運輸方案的總運輸費帶來的變化。如果所有代表非基變量的空格的檢驗數(shù)也即非基變量的檢驗數(shù)都大于等變量的空格的檢驗數(shù)也即非基變量的檢驗數(shù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。0111112122121242

5、41112241101,0ZZxxxxxxxZZ 令令則則運費的增量運費的增量即即 增加增加1個單位個單位, 的檢驗數(shù)的檢驗數(shù)=相應(yīng)的運費增量相應(yīng)的運費增量11x11x基本思想：基本思想：方法二：閉回路法方法二：閉回路法 當(dāng)非基變量的檢驗數(shù)出現(xiàn)負值時，則表明當(dāng)前的當(dāng)非基變量的檢驗數(shù)出現(xiàn)負值時，則表明當(dāng)前的基本可行解不是最優(yōu)解。此時，應(yīng)該對基本可行解進基本可行解不是最優(yōu)解。此時，應(yīng)該對基本可行解進行調(diào)整，即找到一個新的基本可行解使目標(biāo)函數(shù)值下行調(diào)整，即找到一個新的基本可行解使目標(biāo)函數(shù)值下降，這一過程通常稱為換基降，這一過程通常稱為換基( (或主元變換或主元變換) )過程。過程。（1）以某一個）以

6、某一個ij z但不符合整數(shù)條件則返回（但不符合整數(shù)條件則返回（2）繼續(xù)分）繼續(xù)分枝直到枝直到z=z*= z。【例例8-5】用分枝定界法求解下列整數(shù)規(guī)劃模型。用分枝定界法求解下列整數(shù)規(guī)劃模型。以上數(shù)模的最優(yōu)解可用圖解法求得。以上數(shù)模的最優(yōu)解可用圖解法求得。 12121212max40909756st. 72070,0Zxxxxxxxx ，且且為為整整數(shù)數(shù)（1）求解相應(yīng)的線性規(guī)劃模型，確定初始上、下界。）求解相應(yīng)的線性規(guī)劃模型，確定初始上、下界。x201 2 3 4 5 6 7 8 9 1087654321(1) 9x1+7x2=56(2) 7x1+20 x2=70(4.81,1.82)Tx1X(

7、0)=(x1,x2)T=(4.81,1.82)T Z(0)=356非整數(shù)非整數(shù)上界為上界為z=356；下界為下界為z=0（當(dāng)（當(dāng)x1=0,x2=0）12121212max40909756st. 72070,0Zxxxxxxxx （2）分枝并求解）分枝并求解 在最優(yōu)解的非整數(shù)變量中任選一個進行分枝，在最優(yōu)解的非整數(shù)變量中任選一個進行分枝，即可以將即可以將x x1 1分解成兩個可行解區(qū)域，顯然分解成兩個可行解區(qū)域，顯然x1x1 (4(4，5)5)是非可行解區(qū)域，所以是非可行解區(qū)域，所以將線性規(guī)劃將線性規(guī)劃LPLP分解為兩支分解為兩支，即把，即把x x1 14 4或或x x1 15 5中中這兩個條件

8、加到這兩個條件加到將線性規(guī)劃將線性規(guī)劃問題中去，就得到兩個子問題：問題中去，就得到兩個子問題：子問題子問題(1) 子問題子問題(2) 121212112max4090975672070st.4,0Zxxxxxxxxx 分分枝枝約約束束 121212112max4090975672070st.5,0Zxxxxxxxxx 分分枝枝約約束束x201 2 3 4 5 6 7 8 9 1087654321x1對對這兩個子問題數(shù)模可用這兩個子問題數(shù)?？捎脠D解法求得最優(yōu)解分別為：圖解法求得最優(yōu)解分別為： X(2)=(5,1.57)T, Z(2)=341 （3）定界）定界 修改整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)的上下界。

9、修改整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)的上下界。 上界上界z=356修改為修改為z =349，下界，下界z=0。子問題子問題1 x14子問題子問題2 x15X(1)=(4,2.1)T, Z(1)=349(1) (2)（4）比較和剪枝）比較和剪枝 最優(yōu)解為非整數(shù)，最優(yōu)解為非整數(shù)， z* z=0,返回（返回（2）繼續(xù)分枝）繼續(xù)分枝 子問題子問題(3) 子問題子問題(4)1212121212max4090975672070st.42,0Zxxxxxxxxxx 1212121212max4090975672070st.43,0Zxxxxxxxxxx 在子問題在子問題(1) 和子問題和子問題(2)中選擇一個上界最大

10、的線中選擇一個上界最大的線性規(guī)劃，即子問題性規(guī)劃，即子問題(1) ，進行分枝。即把，進行分枝。即把x22或或x23中這中這兩個條件加到子問題兩個條件加到子問題(1)中去，就得到兩個子問題：中去，就得到兩個子問題：x201 2 3 4 5 6 7 8 9 1087654321x1對對這兩個子問題數(shù)模用圖這兩個子問題數(shù)模用圖解法求得最優(yōu)解分別為：解法求得最優(yōu)解分別為： 定界：修改整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)的上下界。定界：修改整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)的上下界。 上界上界z=349，下界，下界z=0修改為修改為z=340 。X(3)=(4,2)T, Z(3)=340X(4)=(1.42,3)T, Z(4)=

11、327 子問題子問題4x23子問題子問題3 x22(4)(3)比較和剪枝：比較和剪枝： 子問題子問題(4)得到非整數(shù)最優(yōu)解，且目標(biāo)函數(shù)值得到非整數(shù)最優(yōu)解，且目標(biāo)函數(shù)值Z(4)=327 z=340,返返回（回（2）繼續(xù)分枝。）繼續(xù)分枝。 把把x21或或x22這兩個條件加到子問題這兩個條件加到子問題(2)中去，就得中去，就得到兩個子問題：到兩個子問題： 子問題子問題(5) 子問題子問題(6)1212121212max4090975672070st.51,0Zxxxxxxxxxx 1212121212max4090975672070st.52,0Zxxxxxxxxxx x201 2 3 4 5 6

12、7 8 9 1087654321x1對對這兩個子問題數(shù)模用圖這兩個子問題數(shù)模用圖解法求得最優(yōu)解分別為：解法求得最優(yōu)解分別為： 定界定界子問題子問題5得到非整數(shù)最優(yōu)解，且得到非整數(shù)最優(yōu)解，且z*=30810)n10)，這幾乎是不，這幾乎是不可能的。因此，常設(shè)計一些方法，只檢查變量取可能的。因此，常設(shè)計一些方法，只檢查變量取值組合的一部分，就能求得問題的最優(yōu)解。這樣值組合的一部分，就能求得問題的最優(yōu)解。這樣的方法稱為隱枚舉法，分枝定界法也是一種隱枚的方法稱為隱枚舉法，分枝定界法也是一種隱枚舉法。舉法?！纠纠?-6】用枚舉法和隱枚舉法求解下面用枚舉法和隱枚舉法求解下面0-1規(guī)劃模型規(guī)劃模型1231

13、231232312123max343241442. 26314,0,Zxxxxxxxxxstxxxxxxx 或或1 1（1）用枚舉法求解）用枚舉法求解變量的個數(shù)為變量的個數(shù)為3，所有可能取值為，所有可能取值為23=8。列出所有變量。列出所有變量的取值，再逐一檢驗是否為可行解，可以得到最優(yōu)解。的取值，再逐一檢驗是否為可行解，可以得到最優(yōu)解。枚舉法所有可能組合及最優(yōu)值列表枚舉法所有可能組合及最優(yōu)值列表組合解組合解是否滿足約束是否滿足約束是否可是否可行解行解Z值值x1x2x31234000是是0001是是4010是是-1011否否100是是3101是是7110否否111否否 最優(yōu)解為：最優(yōu)解為：x1

14、=1,x2=0,x3=1, 最優(yōu)值為最優(yōu)值為7。123max34Zxxx（2）用隱枚舉法求解）用隱枚舉法求解 通過試探的方法找一個行通過試探的方法找一個行解解 (1，0，0) ，目標(biāo)函數(shù)的，目標(biāo)函數(shù)的最優(yōu)值一定不小于這個可最優(yōu)值一定不小于這個可行解對應(yīng)的目標(biāo)函數(shù)值。行解對應(yīng)的目標(biāo)函數(shù)值。即即3x1-x2+4x34這個約束條這個約束條件就是過濾條件。件就是過濾條件。組合解組合解是否滿足約束是否滿足約束是否可是否可行解行解Z值值x1x2x31234001是是4101是是71231231231232312123max3434403241442.26314,0,Zxxxxxxxxxxxxstxxxxx

15、xx 或或1 1 在計算過程中，若遇到在計算過程中，若遇到z值巳超過了條件值巳超過了條件0右邊的值，右邊的值，應(yīng)改變條件應(yīng)改變條件0，使右邊的值是迄今為止的最大者。，使右邊的值是迄今為止的最大者。 實際不需要列出所有的可行組合。實際不需要列出所有的可行組合。 興趣興趣-使使目標(biāo)函數(shù)最優(yōu)目標(biāo)函數(shù)最優(yōu)的變量的可行的變量的可行組合組合。1. 按目標(biāo)函數(shù)值從優(yōu)到劣（本例，從大到小），順序按目標(biāo)函數(shù)值從優(yōu)到劣（本例，從大到?。?，順序列出變量的組合；列出變量的組合；過濾性條件過濾性條件2. 逐個檢驗變量組合的可行性，最先滿足所有約束條逐個檢驗變量組合的可行性，最先滿足所有約束條件的變量組合就是最優(yōu)解；件的

16、變量組合就是最優(yōu)解；4. 相當(dāng)于把枚舉法得出的所有非優(yōu)組合隱去不算了，相當(dāng)于把枚舉法得出的所有非優(yōu)組合隱去不算了，故稱為隱枚舉法。故稱為隱枚舉法。2. 隱枚舉法隱枚舉法3. 劣于最優(yōu)解的組合即使可行，也不用列出和檢驗；劣于最優(yōu)解的組合即使可行，也不用列出和檢驗； 123451234512345123max4.53.89.521.5(1)4612820(2)54123820(3)1(4)0,11,2,5jZxxxxxxxxxxxxxxxxxxxj 例題：求解下面例題：求解下面0-1規(guī)劃模型規(guī)劃模型 xj取值有取值有0和和1兩種狀態(tài)；有兩種狀態(tài)；有5個變量，這樣的個變量，這樣的0，1組組合就有合就

17、有25=32個。把每種組合列出，代入約束條件檢驗是個。把每種組合列出，代入約束條件檢驗是否可行，可行解代入目標(biāo)函數(shù)比較大小得出最優(yōu)解否可行，可行解代入目標(biāo)函數(shù)比較大小得出最優(yōu)解-枚枚舉法，繁瑣舉法，繁瑣!隱枚舉法解題步驟：隱枚舉法解題步驟：（1）變換目標(biāo)函數(shù)和約束條件）變換目標(biāo)函數(shù)和約束條件 價值系數(shù)價值系數(shù)cj前的符號統(tǒng)一前的符號統(tǒng)一 在目標(biāo)函數(shù)求在目標(biāo)函數(shù)求極大極大時，統(tǒng)一帶時，統(tǒng)一帶負號負號；求極小值時，；求極小值時，統(tǒng)一帶正號。在不滿足上述要求時，用統(tǒng)一帶正號。在不滿足上述要求時，用 代代入目標(biāo)函數(shù)。入目標(biāo)函數(shù)。 jjxx 1 本例求極大值，本例求極大值，x1,x2,x3前符號不滿足，

18、用前符號不滿足，用332211111xx,xx,xx代入目標(biāo)函數(shù)和約束條件；代入目標(biāo)函數(shù)和約束條件；按按 值從小到大排列決策變量項值從小到大排列決策變量項jc本例變換結(jié)果如下：本例變換結(jié)果如下：54321512598354x.xx.x.x.Zmax 10161254382124685954832518174312331245231245131245,x,xxxxxxxxxxxxxxx.x.x.xx.Zmaxjj（2）用目標(biāo)函數(shù)值探索法求最優(yōu)解）用目標(biāo)函數(shù)值探索法求最優(yōu)解 由公式由公式 ，當(dāng)，當(dāng) 時，時，Z=Z0=17.8為上限。為上限。如果如果 這個組合又滿足全部約束條件，則它這個組合又滿足全部約束條件，則它為最優(yōu)解為最優(yōu)解;否則，否則，按劣于按劣于Z0的組合解方向的組合解方向探索可行解。探索可行解。 10jjxx 或或0jjxx 或或最大值最大值 1 按按 由小到大逐項計算組合解的由小到大逐項計算組合解的 值及其相應(yīng)值及其相應(yīng)的的Z值，代入約束條件檢查可行性