換基疊代

換基疊代

換基疊代(basis iteration)一般是指求解線性規劃問題過程中的疊代技巧,是從一個基可行解到另一個基可行解的疊代 ,表作業法的換基疊代是一種求解運輸問題過程中的疊代技巧。

基本信息

單純形表上的換基疊代

在單純形表上的換基疊代過程是:

換基疊代 換基疊代
換基疊代 換基疊代
換基疊代 換基疊代
換基疊代 換基疊代
換基疊代 換基疊代
換基疊代 換基疊代

1.確定入基變數。若在 的檢驗數 中有檢驗數 ,且λ所在列的其他元素中有 ,則取 ,即T(B)中最左邊的一個正檢驗數λ(或取 ),讓其對應的變數x為入基變數。

2.求主元,確定出基變數。按最小比值原則

換基疊代 換基疊代
換基疊代 換基疊代

其中b為主元,記為 ,主元b所在行的基變數x就是要確定的出基變數。

換基疊代 換基疊代

3.以b為主元,進行初等行變換。將入基變數x所在的列變為單位向量,即 ,與此同時,原T(B)中的各元素按以下各式計算,變為相應的新元素:

換基疊代 換基疊代
換基疊代 換基疊代
換基疊代 換基疊代
換基疊代 換基疊代
換基疊代 換基疊代
換基疊代 換基疊代

於是得到新基 所對應的單純形表 :

c→c...c...cc...c...c
x
換基疊代 換基疊代
x...x...xx...x...x
x
換基疊代 換基疊代
1...
換基疊代 換基疊代
...0
換基疊代 換基疊代
...0...
換基疊代 換基疊代
........................
x
換基疊代 換基疊代
..................
x
換基疊代 換基疊代
0...
換基疊代 換基疊代
...0
換基疊代 換基疊代
...1...
換基疊代 換基疊代
x
換基疊代 換基疊代
..................
........................
x
換基疊代 換基疊代
0...
換基疊代 換基疊代
...1
換基疊代 換基疊代
...0...
換基疊代 換基疊代
-f
換基疊代 換基疊代
0...
換基疊代 換基疊代
...0
換基疊代 換基疊代
...0...
換基疊代 換基疊代

表作業法的換基疊代

表作業法的換基疊代是一種求解運輸問題過程中的疊代技巧,指在調運表上對負檢驗數相應的空格所在的閉迴路上進行的疊代,先把第一個出現負檢驗數的空格所對應的非基變數作為入基變數,並使這些非基變數的值由零增到調整量,為了保持平衡,在這空格的閉迴路上取調整量θ=min{第奇數次拐角點的調運量},然後對閉迴路中的每個第奇數次拐角點的調運量各減去調整量θ,對每個第偶數次拐角點的調運量加上調整量θ,閉迴路外的調運量均不變.這樣,便得到一個新的調運方案。

相關詞條

熱門詞條

聯絡我們