單純形表上的換基疊代
在單純形表上的換基疊代過程是:
1.確定入基變數。若在 的檢驗數 中有檢驗數 ,且λ所在列的其他元素中有 ,則取 ,即T(B)中最左邊的一個正檢驗數λ(或取 ),讓其對應的變數x為入基變數。
2.求主元,確定出基變數。按最小比值原則
其中b為主元,記為 ,主元b所在行的基變數x就是要確定的出基變數。
3.以b為主元,進行初等行變換。將入基變數x所在的列變為單位向量,即 ,與此同時,原T(B)中的各元素按以下各式計算,變為相應的新元素:
於是得到新基 所對應的單純形表 :
c→ | c | ... | c | ... | c | c | ... | c | ... | c | ||
x | x | ... | x | ... | x | x | ... | x | ... | x | ||
x | 1 | ... | ... | 0 | ... | 0 | ... | |||||
... | ... | ... | ... | ... | ... | ... | ... | |||||
x | ... | ... | ... | ... | ... | ... | ||||||
x | 0 | ... | ... | 0 | ... | 1 | ... | |||||
x | ... | ... | ... | ... | ... | ... | ||||||
... | ... | ... | ... | ... | ... | ... | ... | |||||
x | 0 | ... | ... | 1 | ... | 0 | ... | |||||
-f | 0 | ... | ... | 0 | ... | 0 | ... |
表作業法的換基疊代
表作業法的換基疊代是一種求解運輸問題過程中的疊代技巧,指在調運表上對負檢驗數相應的空格所在的閉迴路上進行的疊代,先把第一個出現負檢驗數的空格所對應的非基變數作為入基變數,並使這些非基變數的值由零增到調整量,為了保持平衡,在這空格的閉迴路上取調整量θ=min{第奇數次拐角點的調運量},然後對閉迴路中的每個第奇數次拐角點的調運量各減去調整量θ,對每個第偶數次拐角點的調運量加上調整量θ,閉迴路外的調運量均不變.這樣,便得到一個新的調運方案。