閉回路

閉回路((loop)求解運(yùn)輸問題時(shí)產(chǎn)生的閉合回路。

在調(diào)運(yùn)方案表中，從一個(gè)空格出發(fā)，沿水平或垂直方向前進(jìn);遇到一個(gè)適當(dāng)?shù)挠袛?shù)字的格子，則轉(zhuǎn)90。前進(jìn);這樣必會(huì)又遇到一個(gè)適當(dāng)?shù)挠袛?shù)字的格子，同樣再轉(zhuǎn)90“向前進(jìn).經(jīng)若干次后，必然會(huì)回到出發(fā)的那個(gè)空格.這樣形成一條由水平線與垂直線 構(gòu)成的封閉折線，稱為一個(gè)閉回路.2100433B

下面舉例說明閉回路調(diào)整法的計(jì)算步驟。下圖2是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題的運(yùn)輸表并且已使用最小元素法填入了基變量。

閉回路調(diào)整法計(jì)算檢驗(yàn)數(shù)

藍(lán)色方框中的是運(yùn)價(jià)，橙色數(shù)字是基變量的值。如(A2,B1)表示從產(chǎn)地A2運(yùn)送8個(gè)單位的貨物到銷地B1，其運(yùn)價(jià)為2個(gè)單位。

首先考慮表中的空格(A1,B1)，設(shè)想由產(chǎn)地A1供應(yīng)1個(gè)單位的物品給銷地B1，為使運(yùn)入銷地B1的物品總數(shù)量不大于它的銷量，就應(yīng)該將產(chǎn)地A2運(yùn)到B1的物品數(shù)量減去一個(gè)單位，即將格子(A2,B1)中填入的數(shù)字8改為7；為了使由產(chǎn)地A2運(yùn)出的物品正好等于它的產(chǎn)量，且保持新的到的解仍為基可行解，需將x23由原來的2增加1，改為3。然后將x13由10減去1，即變?yōu)?，以使運(yùn)入銷地B3的物品數(shù)量正好等于它的銷量，同時(shí)使由A1運(yùn)出的物品數(shù)量正好等于它的產(chǎn)量。顯然，由于x11的的調(diào)整將影響到x21、x23、x13這三個(gè)變量的取值，即(A1,B1)，(A2,B1)，(A2,B2)，(A1,B3)這四個(gè)格子中填入的數(shù)據(jù)。在運(yùn)輸表中，每一個(gè)空格都可以和一些有數(shù)字的格子用水平線段和垂直線段交替連接在一閉合回路上，而且這種閉合回路是唯一的。而且，運(yùn)輸問題的檢驗(yàn)數(shù)的定義是產(chǎn)地到銷地供給1個(gè)單位物品所引起的總運(yùn)費(fèi)的變化。非基變量或者說空格(A1,B1)的檢驗(yàn)數(shù)σ11即由此引起的總運(yùn)費(fèi)變化是：σ11=c11-c21 c23-c13=4-2 3-4=1?？梢钥闯鲈谟?jì)算檢驗(yàn)數(shù)時(shí)，符號在起點(diǎn)時(shí)為正，任意時(shí)針往下到下個(gè)頂點(diǎn)，此時(shí)符號為負(fù)，由此正負(fù)交替直到所有頂點(diǎn)包括進(jìn)去。

檢驗(yàn)方案的數(shù)據(jù)指標(biāo)，編排各個(gè)閉合回路，這樣的工作熟練可以在?，F(xiàn)再看空格(A2,B2)，它的閉回路的頂點(diǎn)由以下各格組成：(A2,B2)，(A3,B2)，(A3,B4)，(A1,B4)，(A1,B3)，(A2,B3)，最后再回到(A2,B2)。

在實(shí)際操作中由于涂改不便，熟練則可以不用編制各個(gè)閉合回路，在心中假想即可，其檢驗(yàn)數(shù)為σ22=c22-c32 c34-c14 c13-c23=10-5 6-11 4-3=1。檢驗(yàn)數(shù)為正數(shù)，表明修改這個(gè)基變量只會(huì)增加總運(yùn)費(fèi)，因此觀察其他空格的檢驗(yàn)數(shù)。

按照同樣的方法，可得表中其他的非基變量的檢驗(yàn)數(shù)如下：

σ12=c12-c32 c34-c14 c13=12-5 6-11=2

σ24=c24-c14 c13-c23=9-11 4-3=-1

σ31=c31-c21 c23-c13 c14-c34=8-2 3-4 11-6=10

σ33=c33-c34 c14-c14 c13=11-6-11 4=12

由于σ24=-1<0，故知表中的解不是最優(yōu)解。

用上述閉回路法算出的初始調(diào)運(yùn)方案中各個(gè)空格的檢驗(yàn)數(shù)，表示在下圖3的檢驗(yàn)數(shù)表中。

閉回路調(diào)整法解的改進(jìn)

若最優(yōu)性檢驗(yàn)時(shí)某非基變量

解改進(jìn)的具體步驟為：

（1）

（2）以空格(Ai,Bj)為第一個(gè)奇數(shù)頂點(diǎn)，沿閉回路的順（或逆）時(shí)針方向前進(jìn)，對閉回路上的頂點(diǎn)依次編號；

（3）在閉回路上的所有偶數(shù)頂點(diǎn)集合L(e)中，找出運(yùn)輸量最小

（4）以

然后，再對得到的新解進(jìn)行最優(yōu)性檢驗(yàn)，如不是最優(yōu)解，就重復(fù)以上步驟繼續(xù)進(jìn)行調(diào)整，一直到得出最優(yōu)解為止 。2100433B

閉回路調(diào)整法基格和非基格

定義1：將變量

閉回路調(diào)整法閉合回路

所謂閉合回路，就是指在調(diào)運(yùn)方案表中，從一個(gè)空格出發(fā)，沿水平或垂直方向前進(jìn)，遇到一個(gè)適當(dāng)?shù)挠袛?shù)字的格子時(shí)，轉(zhuǎn)90°繼續(xù)前進(jìn)，直到回到起始空格為止，形成一條由水平線段和垂直線段所組成的封閉折線 。

定義2：若一組格點(diǎn)經(jīng)過適當(dāng)?shù)呐判蚝螅軐懗梢韵滦问剑?

則稱這組格點(diǎn)構(gòu)成了閉合回路。

如下圖1中(1，1)， (1，2)，(3，2)， (3，1)構(gòu)成一個(gè)閉合回路。

閉回路調(diào)整法是借助圖表作業(yè)方式，計(jì)算比較兩種（或兩種以上）變量值，以調(diào)整部分經(jīng)濟(jì)指標(biāo)實(shí)現(xiàn)優(yōu)化經(jīng)營提高管理效益的管理統(tǒng)計(jì)方法。

用表上作業(yè)法求解運(yùn)輸問題時(shí)，可仿照一般的單純形法，檢驗(yàn)這個(gè)解的各個(gè)非基變量（對應(yīng)運(yùn)輸表中是的空格）的檢驗(yàn)數(shù)是否都是正數(shù)。若有某空格

為了計(jì)算出運(yùn)輸表中空格（非基變量）的檢驗(yàn)數(shù)，引入閉回路的概念，使用閉回路可以直觀地為滿足約束條件換入變量增值后，再從原來的某一基變量中減去相應(yīng)數(shù)值，變成數(shù)值為零的換出變量，完成換入換出即運(yùn)量的調(diào)整。