對偶單純形法:利用對偶理論得到的一個
求解線性規劃問題的方法
對偶單純形法是根據對偶問題求解的特點和對稱性設計出的一種解法。
在單純形法迭代時,在b 列中得到的是原問題的基可行解,而在檢驗數得到的是對偶問題的基解,透過逐步迭代,當在檢驗數行得到對偶問題的解也是基可行解時,已得到最優解,即原問題與對偶問題都是最優解。
根據對偶問題的對稱性:若保持對偶問題的解是基可行解,即cj-CBB-1Pj≤0,而原問題在非可行解的基礎上,透過逐步迭代達到基可行解,這樣也得到了最優解。
基本解
X(0)為基本可行解的條件?
B-1b≥0
X(0)為最優解的條件?
原
原問題最優解條件
令Y=CBB-1,代入原問題最優解條件,→YA≥C
對偶單純形法的基本思路:
保證對偶問題的可行性,逐步改進原問題的可行性,求解原問題。
2. 確定出基變數
按,對應的基變數xl為出基變數。
對偶單純形法步驟:
列出初始單純形表,檢查b 列的數字若都為非負,則已得到最優解,停止計算,若b列的數字中至少有一個負分量,轉第二步。
確定入基變數
在單純形表中檢查xl所在行的各系數alj(j=1,2, …,n),若所有alj ≥0,則無可行解,停止計算,若存在alj <0,計算
按規則所對應的列的非基變數xk為入基變數,保證得到的新基解所對應的對偶問題的解仍為可行解。
以 alk為主元素,進行迭代運算,得到新基解的單
純形表,重複1—4的步驟,直至b 列中所有元素均為非負數為止。
對偶單純形法:利用對偶理論得到的一個
求解線性規劃問題的方法
對偶單純形法是根據對偶問題求解的特點和對稱性設計出的一種解法。
在單純形法迭代時,在b 列中得到的是原問題的基可行解,而在檢驗數得到的是對偶問題的基解,透過逐步迭代,當在檢驗數行得到對偶問題的解也是基可行解時,已得到最優解,即原問題與對偶問題都是最優解。
根據對偶問題的對稱性:若保持對偶問題的解是基可行解,即cj-CBB-1Pj≤0,而原問題在非可行解的基礎上,透過逐步迭代達到基可行解,這樣也得到了最優解。
基本解
X(0)為基本可行解的條件?
B-1b≥0
X(0)為最優解的條件?
原
原問題最優解條件
令Y=CBB-1,代入原問題最優解條件,→YA≥C
對偶單純形法的基本思路:
保證對偶問題的可行性,逐步改進原問題的可行性,求解原問題。
對偶單純形法的基本思路:
2. 確定出基變數
按,對應的基變數xl為出基變數。
對偶單純形法步驟:
列出初始單純形表,檢查b 列的數字若都為非負,則已得到最優解,停止計算,若b列的數字中至少有一個負分量,轉第二步。
確定入基變數
在單純形表中檢查xl所在行的各系數alj(j=1,2, …,n),若所有alj ≥0,則無可行解,停止計算,若存在alj <0,計算
按規則所對應的列的非基變數xk為入基變數,保證得到的新基解所對應的對偶問題的解仍為可行解。
以 alk為主元素,進行迭代運算,得到新基解的單
純形表,重複1—4的步驟,直至b 列中所有元素均為非負數為止。