單純形算法的一般原理

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

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

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

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

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