運(yùn)籌學(xué)課件解的最優(yōu)性檢驗(yàn)第一頁(yè)，共二十八頁(yè)，編輯于2023年，星期三1、閉回路法以確定了初始調(diào)運(yùn)方案的作業(yè)表為基礎(chǔ)，以一個(gè)非基變量作為起始頂點(diǎn)，尋求閉回路。該閉回路的特點(diǎn)是：除了起始頂點(diǎn)是非基變量外，其他頂點(diǎn)均為基變量（對(duì)應(yīng)著填上數(shù)值的格）?？梢宰C明，如果對(duì)閉回路的方向不加區(qū)別，對(duì)于每一個(gè)非基變量而言，以其為起點(diǎn)的閉回路存在且唯一。m+n-1個(gè)變量構(gòu)成基變量的充要條件是它們不構(gòu)成閉回路。第二頁(yè)，共二十八頁(yè)，編輯于2023年，星期三

X11

X13

X21

X24

X33

B1

B2

B3

B4

A1

X12

X14

A2

X22

X23

A3X31

X32

X34例設(shè)m=3，n=4，決策變量xij表示從產(chǎn)地Ai到銷地Bj的調(diào)運(yùn)量，列表如下，給出閉回路

在表中的表示法——用折線連接起來(lái)的頂點(diǎn)變量。第三頁(yè)，共二十八頁(yè)，編輯于2023年，星期三

請(qǐng)給出閉回路在表中的表示法。

X11

X13

X21

X24

X33

B1

B2

B3

B4

A1

X12

X14

A2

X22

X23

A3X31

X32

X34第四頁(yè)，共二十八頁(yè)，編輯于2023年，星期三下面的折線構(gòu)成的封閉曲線連接的頂點(diǎn)變量哪些不可能是閉回路？（a）（b）（c）（d）（e）表中的折線構(gòu)成一條封閉曲線，且所有的邊都是水平或垂直的；表中的每一行和每一列由折線相連的閉回路的頂點(diǎn)只有兩個(gè)；第五頁(yè)，共二十八頁(yè)，編輯于2023年，星期三

約定作為起始頂點(diǎn)的非基變量為偶數(shù)次頂點(diǎn)，其它頂點(diǎn)從1開(kāi)始順次排列，那么，該非基變量xij的檢驗(yàn)數(shù)：現(xiàn)在，在用最小元素法確定上例初始調(diào)運(yùn)方案的基礎(chǔ)上，計(jì)算非基變量X12的檢驗(yàn)數(shù)：=（閉回路上偶數(shù)次頂點(diǎn)運(yùn)價(jià)之和）-（閉回路上奇數(shù)次頂點(diǎn)運(yùn)價(jià)之和）第六頁(yè)，共二十八頁(yè)，編輯于2023年，星期三B1B2B3B4產(chǎn)量A1

16A210A322銷量814121448產(chǎn)地銷地412102851134119682101486x11x22x12x31x24x33第七頁(yè)，共二十八頁(yè)，編輯于2023年，星期三非基變量的檢驗(yàn)數(shù)：

=c12-c32+c34–c14=12-5+6-11=2

=c22-c32+c34–c14+c13–c23=10-5+6-11+4-3=1

=c11-c21+c23-c13=4-2+3-4=1第八頁(yè)，共二十八頁(yè)，編輯于2023年，星期三B1B2B3B4產(chǎn)量A11216A21-110A3101222銷量814121448檢驗(yàn)數(shù)表第九頁(yè)，共二十八頁(yè)，編輯于2023年，星期三2、位勢(shì)法

（對(duì)偶變量法）原問(wèn)題對(duì)偶問(wèn)題第十頁(yè)，共二十八頁(yè)，編輯于2023年，星期三對(duì)偶變量向量YUi,Vj對(duì)偶變量，也稱為位勢(shì)變量。第i個(gè)第m+j第十一頁(yè)，共二十八頁(yè)，編輯于2023年，星期三

以上例初始調(diào)運(yùn)方案為例，設(shè)置位勢(shì)變量和，在初始調(diào)運(yùn)方案表的基礎(chǔ)上增加一行和一列（見(jiàn)下頁(yè)表格）。然后構(gòu)造下面的方程組：第十二頁(yè)，共二十八頁(yè)，編輯于2023年，星期三方程組的特點(diǎn)：方程個(gè)數(shù)是m+n-1=3+4-1=6個(gè)，位勢(shì)變量共有m+n=3+4=7個(gè)，通常稱ui為第i行的位勢(shì)，稱vj為第j列的位勢(shì)；初始方案的每一個(gè)基變量xij對(duì)應(yīng)一個(gè)方程——-—所在行和列對(duì)應(yīng)的位勢(shì)變量之和等于該基變量對(duì)應(yīng)的運(yùn)價(jià)：ui+vj=cij；

第十三頁(yè)，共二十八頁(yè)，編輯于2023年，星期三

給定任一變量一個(gè)較少的整數(shù)或零，解方程組式，即可求得位勢(shì)變量的一組值。計(jì)算非基變量xij檢驗(yàn)數(shù)的公式σij=cij-（ui+vj）在式中，令u2=0，則可解得v1=2，v3=3，u1=1，u4=10,u3=-4,v2=9，計(jì)算檢驗(yàn)數(shù)σ11=c11-（u1+v1）=4-（1+2）=1σ12=c12-（u1+v2）=12-（1+9）=2σ22=c22-（u2+v2）=10-（0+9）=1σ24=c24-（u2+v4）=9-（0+10）=-1σ31=c31-（u3+v1）=8-（-4+2）=10σ33=c33-（u3+v3）=11-（-4+3）=12與前面用閉回路法求得的結(jié)果相同。

第十四頁(yè)，共二十八頁(yè)，編輯于2023年，星期三B1B2B3B4產(chǎn)量uiA1

16U1(1)A210U2(0)A322U3(-4)銷量814121448vjV1(2)V2(9)V3(3)V4(10)產(chǎn)地銷地412102851134119682101486第十五頁(yè)，共二十八頁(yè)，編輯于2023年，星期三B1B2B3B4產(chǎn)量A11216A21-110A3101222銷量814121448檢驗(yàn)數(shù)表第十六頁(yè)，共二十八頁(yè)，編輯于2023年，星期三位勢(shì)法計(jì)算非基變量xij檢驗(yàn)數(shù)的公式σij=cij-（ui+vj）=（閉回路上偶數(shù)次頂點(diǎn)運(yùn)價(jià)之和）-（閉回路上奇數(shù)次頂點(diǎn)運(yùn)價(jià)之和）閉回路法計(jì)算非基變量xij檢驗(yàn)數(shù)的公式：比較檢驗(yàn)數(shù)計(jì)算的兩種方法第十七頁(yè)，共二十八頁(yè)，編輯于2023年，星期三

三、解的改進(jìn)當(dāng)至少有一個(gè)非基變量的檢驗(yàn)數(shù)是負(fù)值時(shí)，說(shuō)明作業(yè)表上當(dāng)前的調(diào)運(yùn)方案不是最優(yōu)的，應(yīng)進(jìn)行調(diào)整。即檢驗(yàn)數(shù)σij小于零，則應(yīng)對(duì)解進(jìn)行改進(jìn)：1、首先在作業(yè)表上以xij為起始變量作出閉回路。2、以檢驗(yàn)數(shù)σij小于零所對(duì)應(yīng)的空格為第一個(gè)奇數(shù)點(diǎn)，沿閉回路順或逆時(shí)針依次對(duì)頂點(diǎn)進(jìn)行編號(hào)。3、在閉回路的所有偶數(shù)頂點(diǎn)，求出調(diào)整量ε：4、在閉回路的所有奇數(shù)頂點(diǎn)，增加調(diào)整量ε，所有偶數(shù)頂點(diǎn)，減去調(diào)整量ε，ijε=min{該閉回路中偶數(shù)次頂點(diǎn)調(diào)運(yùn)量xij}第十八頁(yè)，共二十八頁(yè)，編輯于2023年，星期三B1B2B3B4產(chǎn)量A1

16A210A322銷量814121448產(chǎn)地銷地412102851134119682101486σ24=c24-（u2+v4）=9-（0+10）=-1，x24換入變量,對(duì)應(yīng)的閉回路。x24+-+-第十九頁(yè)，共二十八頁(yè)，編輯于2023年，星期三

計(jì)算調(diào)整量，閉回路偶數(shù)頂點(diǎn)，找運(yùn)輸量最小的頂點(diǎn)：ε=Min（x14，x23）=Min（6，2）=2。按照下面的方法調(diào)整調(diào)運(yùn)量：閉回路上，奇數(shù)次頂點(diǎn)的調(diào)運(yùn)量增加ε，偶數(shù)次頂點(diǎn)（包括起始頂點(diǎn)）的調(diào)運(yùn)量減去ε；閉回路之外的變量調(diào)運(yùn)量不變。得到新的調(diào)運(yùn)方案：

第二十頁(yè)，共二十八頁(yè)，編輯于2023年，星期三B1B2B3B4產(chǎn)量A1

16A210A322銷量814121448產(chǎn)地銷地412102851134119682101486+2-2+2-2計(jì)算檢驗(yàn)數(shù)（位勢(shì)法或閉回路法）第二十一頁(yè)，共二十八頁(yè)，編輯于2023年，星期三B1B2B3B4產(chǎn)量A1

16A210A322銷量814121448產(chǎn)地銷地412102851134119681214842練習(xí):分別使用閉回路法和位勢(shì)法計(jì)算檢驗(yàn)數(shù)第二十二頁(yè)，共二十八頁(yè)，編輯于2023年，星期三B1B2B3B4產(chǎn)量A1

16A210A322銷量814121448產(chǎn)地銷地412102851134119681214842檢驗(yàn)數(shù)為非負(fù)，得到最優(yōu)解。σ11=0σ31=9σ12=2σ22=2σ23=1σ33=12第二十三頁(yè)，共二十八頁(yè)，編輯于2023年，星期三B1B2B3B4產(chǎn)量uiA1

16U1(2)A210U2(0)A322U3(-3)銷量814121448vjV1(2)V2(8)V3(2)V4(9)產(chǎn)地銷地412102851134119681214842σij=cij-（ui+vj）第二十四頁(yè)，共二十八頁(yè)，編輯于2023年，星期三B1B2B3B4產(chǎn)量uiA1

16U1(2)A210U2(0)A322U3(-3)銷量814121448vjV1(2)V2(8)V3(2)V4(9)產(chǎn)地銷地4121028511341196812148420922112檢驗(yàn)數(shù)為非負(fù)，得到最優(yōu)解。σij=cij-（ui+vj）第二十五頁(yè)，共二十八頁(yè)，編輯于2023年，星期三

結(jié)果

最優(yōu)調(diào)運(yùn)方案是：

x21=8，x32=14，x13=12，x14=4，x24=2，x34=8

相應(yīng)的最小總運(yùn)輸量為：

Zmin=8×2+14×5+12×4+4×11+2×9+8×6=244

第二十六頁(yè)，共二十八頁(yè)，編輯于2023年，星期三四、幾點(diǎn)說(shuō)明

1、如果運(yùn)輸問(wèn)題的某一個(gè)基可行解有多個(gè)非基變量的檢驗(yàn)數(shù)為