基本介紹
- 中文名：閉迴路調整法
- 外文名：Closed loop adjustment method
- 別稱：閉合迴路法
- 學科：數學
- 概念：表上作業法的最後一個步驟
- 套用：運輸經濟部門管理等
背景,基本概念,基格和非基格,閉合迴路,簡介,示例,計算檢驗數,解的改進,
背景
運輸問題是一類常見而且極其典型的線性規劃問題。因此從理論上講，運輸問題也可用單純形法來求解。但是由於運輸問題數學模型具有特殊的結構，存在一種比單純形法更簡便的計算方法一表上作業法。表上作業法的實質仍是單純形法。
表上作業法的計算步驟如下：
（1）用西北角規則或最小元素法確定初始基本可行解；
（2）用位勢法求檢驗數；
（3）用閉迴路調整法調整基本可行解。
基本概念
基格和非基格
定義1：將變數
在調運表中所對應的空格記作(i，j)，稱為格點(i，j)或格(i，j)。而
的係數列向量
也稱做格點(i，j)所對應的係數列向量。若
為基變數，則(i，j)稱為基格，否則稱為非基格。
閉合迴路
所謂閉合迴路，就是指在調運方案表中，從一個空格出發，沿水平或垂直方向前進，遇到一個適當的有數字的格子時，轉90°繼續前進，直到回到起始空格為止，形成一條由水平線段和垂直線段所組成的封閉折線。
定義2：若一組格點經過適當的排序後，能寫成以下形式：
則稱這組格點構成了閉合迴路。
如下圖中(1，1)， (1，2)，(3，2)， (3，1)構成一個閉合迴路。
簡介
閉迴路調整法是藉助圖表作業方式，計算比較兩種（或兩種以上）變數值，以調整部分經濟指標實現最佳化經營提高管理效益的管理統計方法。
用表上作業法求解運輸問題時，可仿照一般的單純形法，檢驗這個解的各個非基變數（對應運輸表中是的空格）的檢驗數是否都是正數。若有某空格
的檢驗數為負，說明將
變為基變數將可使目標函式值減少，即使運輸費用減少，故當前這個解不是最優解。若所有空格的的檢驗全非負，則不管怎樣變換解均不能使運輸費用降低，即目標函式值已無法加以改進，這個解即是最優解。
為了計算出運輸表中空格（非基變數）的檢驗數，引入閉迴路的概念，使用閉迴路可以直觀地為滿足約束條件換入變數增值後，再從原來的某一基變數中減去相應數值，變成數值為零的換出變數，完成換入換出即運量的調整。
示例
下面舉例說明閉迴路調整法的計算步驟。下圖是一個產銷平衡的運輸問題的運輸表並且已使用最小元素法填入了基變數。
計算檢驗數
藍色方框中的是運價，橙色數字是基變數的值。如(A2,B1)表示從產地A2運送8個單位的貨物到銷地B1，其運價為2個單位。
首先考慮表中的空格(A1,B1)，構想由產地A1供應1個單位的物品給銷地B1，為使運入銷地B1的物品總數量不大於它的銷量，就應該將產地A2運到B1的物品數量減去一個單位，即將格子(A2,B1)中填入的數字8改為7；為了使由產地A2運出的物品正好等於它的產量，且保持新的到的解仍為基可行解，需將x23由原來的2增加1，改為3。然後將x13由10減去1，即變為9，以使運入銷地B3的物品數量正好等於它的銷量，同時使由A1運出的物品數量正好等於它的產量。顯然，由於x11的的調整將影響到x21、x23、x13這三個變數的取值，即(A1,B1)，(A2,B1)，(A2,B2)，(A1,B3)這四個格子中填入的數據。在運輸表中，每一個空格都可以和一些有數字的格子用水平線段和垂直線段交替連線在一閉合迴路上，而且這種閉合迴路是唯一的。而且，運輸問題的檢驗數的定義是產地到銷地供給1個單位物品所引起的總運費的變化。非基變數或者說空格(A1,B1)的檢驗數σ11即由此引起的總運費變化是：σ11=c11-c21+c23-c13=4-2+3-4=1。可以看出在計算檢驗數時，符號在起點時為正，任意時針往下到下個頂點，此時符號為負，由此正負交替直到所有頂點包括進去。
檢驗方案的數據指標，編排各個閉合迴路，這樣的工作熟練可以在。現再看空格(A2,B2)，它的閉迴路的頂點由以下各格組成：(A2,B2)，(A3,B2)，(A3,B4)，(A1,B4)，(A1,B3)，(A2,B3)，最後再回到(A2,B2)。
在實際操作中由於塗改不便，熟練則可以不用編制各個閉合迴路，在心中假想即可，其檢驗數為σ22=c22-c32+c34-c14+c13-c23=10-5+6-11+4-3=1。檢驗數為正數，表明修改這個基變數只會增加總運費，因此觀察其他空格的檢驗數。
按照同樣的方法，可得表中其他的非基變數的檢驗數如下：
σ12=c12-c32+c32-c14+c13=12-5+6-11=2
σ24=c24-c14+c13-c23=9-11-5+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，故知表中的解不是最優解。
用上述閉迴路法算出的初始調運方案中各個空格的檢驗數，表示在下圖的檢驗數表中。
解的改進
若最優性檢驗時某非基變數
（空格(Ai,Bj)）的檢驗數
為負， 說明將這個非基變數變為基變數時運費會更小，因而這個解不是最優解，還可以進一步。改進的方法是在運輸表中找到這個對應的閉迴路
，在滿足所有約束條件的前提下，使
儘量增大並相應調整閉迴路上其他頂點的運輸量，以得到另一個更好的基可行解。
解改進的具體步驟為：
（1）
為換入變數，找出它在運輸表中的閉迴路；
（2）以空格(Ai,Bj)為第一個奇數頂點，沿閉迴路的順（或逆）時針方向前進，對閉迴路上的頂點依次編號；
（3）在閉迴路上的所有偶數頂點集合L(e)中，找出運輸量最小
的頂點（格子），以該格中的變數為換出變數；
（4）以
為調整量，將該閉迴路上所有奇數頂點處的運輸量都增加這一數值，所有偶數頂點處的運輸量都減去這一數值，從而得出一新的運輸方案。該運輸方案的總運費比原運輸方案，該變數等於
。
然後，再對得到的新解進行最優性檢驗，如不是最優解，就重複以上步驟繼續進行調整，一直到得出最優解為止。
