單純形算法的一般原理

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

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

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

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

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