單純形算法的一般原理

1、單純形算法的一般原理單純形算法的一般原理單純形法的基本思路是有選擇地取基本可行解，即是從可行域的一個極點出發(fā)，沿著可行域的邊界移到另一個相鄰的極點，要求新極點的目標函數值不比原目標函數值差?？紤]到如下線性規(guī)劃問題：其中Ａ一個mn矩陣，且秩為m，ｂ總可以被調整為一個m維非負列向量，Ｃ為n維行向量，Ｘ為n維列向量。根據線性規(guī)劃基本定理：如果可行域Ｄ=Ｘ∈ＲnＡＸ=ｂ，Ｘ≥0非空有界，則Ｄ上的最優(yōu)目標函數值Ｚ=ＣＸ一定可以在Ｄ的一個頂點上達到

2、。這個重要的定理啟發(fā)了Dantzig的單純形法，即將尋優(yōu)的目標集中在D的各個頂點上。Dantzig的單純形法把尋優(yōu)的目標集中在所有基本可行解（即可行域頂點）中。其基本思路是從一個初始的基本可行解出發(fā)，尋找一條達到最優(yōu)基本可行解的最佳途徑。單純形法的一般步驟如下：（1）尋找一個初始的基本可行解。（2）檢查現(xiàn)行的基本可行解是否最優(yōu)，如果為最優(yōu)，則停止迭代，已找到最優(yōu)解，否則轉一步。（3）移至目標函數值有所改善的另一個基本可行解，然后轉會到步

3、驟（2）。求解思想如下圖所示：maxZ=CXAX=bX0?????問題問題：?要判斷m個系數列向量是否恰好構成一個基并不是一件容易的事。基由系數矩陣Ａ中m個線性無關的系數列向量構成。但是要判斷m個系數列向量是否線性無關并非易事。?即使系數矩陣Ａ中找到了一個基B，也不能保證該基恰好是可行基。因為不能保證基變量ＸB=Ｂ1b≥0。?為了求得基本可行解，必須求基Ｂ的逆陣Ｂ1。但是求逆陣Ｂ1也是一件麻煩的事。?結論結論：在線性規(guī)劃標準化過程中設法

4、得到一個m階單位矩陣I作為初始可行基Ｂ，為了設法得到一個m階單位矩陣I作為初始可行基Ｂ，可在性規(guī)劃標準化過程標準化過程中作如下處理：?若在化標準形式前，m個約束方程都是“≤”的形式，那么在化標準形時只需在一個約束不等式左端都加上一個松弛變量xni(i=12…m)。?若在化標準形式前，約束方程中有“≥”不等式，那么在化標準形時除了在方程式左端減去剩余變量使不等式變成等式以外，還必須在左端再加上一個非負新變量，稱為人工變量?若在化標準形式前

5、，約束方程中有等式方程，那么可以直接在等式左端添加人工變量。加入已求的一個基本可行解，，將這一基本可行解代入目標函數，可求得相應的目標函數值其中，分別表示基變量和非基變量所對應的價值系數子向量。要判定是否已經達到最大值，只需將代入目標函數，使目標函數用非基變量表示，即：1BbX=0???????1BbX=0???????11BNBBbZ=CX=(CC)=CBb0???????B12mNm1m2nC=(ccc)C=(ccc)??1BZ=C