換基疊代

換基疊代

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

基本介紹

  • 中文名：換基疊代
  • 外文名：basis iteration
  • 所屬學科：數學
  • 簡介：解線性規劃問題過程中的疊代技巧
單純形表上,表作業法,

單純形表上

在單純形表上的換基疊代過程是：
1.確定入基變數。若在
的檢驗數
中有檢驗數
，且λs所在列的其他元素中有
，則取
，即T(B)中最左邊的一個正檢驗數λs(或取
)，讓其對應的變數xs為入基變數。
2.求主元，確定出基變數。按最小比值原則
其中brs為主元，記為
，主元brs所在行的基變數xr就是要確定的出基變數。
3.以brs為主元，進行初等行變換。將入基變數xs所在的列變為單位向量，即
，與此同時，原T(B)中的各元素按以下各式計算，變為相應的新元素：
於是得到新基
所對應的單純形表
：
cj→
c1
...
cr
...
cm
cm+1
...
cs
...
cn
xB
x1
...
xr
...
xm
xm+1
...
xs
...
xn
x1
1
...
...
0
...
0
...
...
...
...

...

...
...

...

...
xr-1
...

...

...
...

...

...
xs
0
...
...
0
...
1
...
xr+1
...

...

...
...

...

...
...
...
...

...

...
...

...

...
xm
0
...
...
1
...
0
...
-f0
0
...
...
0
...
0
...

表作業法

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

相關詞條

熱門詞條

聯絡我們