最優(yōu)化理論與方法單純形法最優(yōu)化理論與方法單純形法2.1標(biāo)準(zhǔn)形式一般線性規(guī)劃問題總可以寫成下列標(biāo)準(zhǔn)形式：

(2.1.1)用矩陣表示：

(2.1.2)其中，A是mXn矩陣，c是n維行向量，b是m維列向量。為了計算方便，一般假設(shè)，即b的每個分量都是非負(fù)數(shù)。2.1標(biāo)準(zhǔn)形式一般線性規(guī)劃問題總可以寫成下列標(biāo)準(zhǔn)形式：其中表示定理設(shè)為非空多面集，則有：極點(diǎn)集非空，且存在有限個極點(diǎn).極方向集為空集的充要條件是S有界。若S無界，則存在有限個極方向.x∈S的充要條件是：表示定理設(shè)定理與結(jié)論線性規(guī)劃的可行域是凸集。

設(shè)線性規(guī)劃(2.1.2)的可行域非空，則有下列結(jié)論：線性規(guī)劃(2.1.2)存在有限最優(yōu)解的充要條件是所有為非負(fù)數(shù)，其中是可行域的極方向。若線性規(guī)劃(2.1.2)存在有限最優(yōu)解，則目標(biāo)函數(shù)的最優(yōu)值可在某個極點(diǎn)上達(dá)到。（最優(yōu)極點(diǎn)）極點(diǎn)是個幾何概念，直觀性強(qiáng)，但不便于演算，因此需要研究極點(diǎn)的代數(shù)含義。定理與結(jié)論線性規(guī)劃的可行域是凸集。極點(diǎn)是個幾何概念，直觀性基本可行解

稱為方程組的一個基本解；B稱為基矩陣，簡稱基；xB的各分量稱為基變量；基變量的全體稱為一組基；xN的各分量稱為非基變量；若，則稱基本可行解是非退化的基本可行解；若且至少有一個分量是零，則稱此時的基本可行解是退化的基本可行解；同時，此基本可行解對應(yīng)的基被稱為退化的可行基。又若，則稱為約束條件

的基本可行解，稱B為可行基矩陣，為一組可行基；基本可行解若，則稱基本可行解是非退化的基基本可行解的個數(shù)若A是mXn矩陣，A的秩為m時，基本可行解的個數(shù)不會超過：基本可行解的個數(shù)若A是mXn矩陣，A的秩為m時，定理與推理線性規(guī)劃的可行域是凸集。

設(shè)線性規(guī)劃(2.1.2)的可行域非空，則有下列結(jié)論：線性規(guī)劃(2.1.2)存在有限最優(yōu)解的充要條件是所有為非負(fù)數(shù)，其中是可行域的極方向。若線性規(guī)劃(2.1.2)存在有限最優(yōu)解，則目標(biāo)函數(shù)的最優(yōu)值可在某個極點(diǎn)上達(dá)到。（最優(yōu)極點(diǎn)）線性規(guī)劃的可行域的極點(diǎn)集與基本可行解集等價；當(dāng)線性規(guī)劃(2.1.2)有可行解，則一定存在基本可行解。當(dāng)線性規(guī)劃(2.1.2)存在最優(yōu)解時，則一定存在一個基本可行解是目標(biāo)函數(shù)的最優(yōu)解。（最優(yōu)基本可行解）定理與推理線性規(guī)劃的可行域是凸集。第3章單純形方法3.1單純形方法原理3.2兩階段法3.3修正單純形法第3章單純形方法3.1單純形方法原理單純形方法的基本思想就是，從一個基本可行解出發(fā)，求一個使目標(biāo)函數(shù)值有所改變的基本可行解；通過不斷改進(jìn)基本可行解，力圖達(dá)到最優(yōu)基本可行解。怎樣實現(xiàn)基本可行解的轉(zhuǎn)換？單純形方法的基本思想就是，從一個基本可行解出發(fā)，求一個使目標(biāo)表格形式的單純形法顯然，在單純形表中包含了單純形方法所需的全部數(shù)據(jù)。fxBxN

右端xB0ImB-1NB-1bf10cBB-1N-cNcBB-1b表格形式的單純形法顯然，在單純形表中包含了單純形方法所需的全表格形式的單純形法顯然，在單純形表中包含了單純形方法所需的全部數(shù)據(jù)。主元進(jìn)基變量離基變量表格形式的單純形法顯然，在單純形表中包含了單純形方法所需的全表格形式的單純形法解的幾種情況在單純形表上的體現(xiàn)(min型)：唯一最優(yōu)解：終表非基變量判別數(shù)均小于零；多重最優(yōu)解：終表非基變量判別數(shù)中有等于零的；無界解：任意表有正判別數(shù)相應(yīng)的系數(shù)列均非正。max型單純形表與min型的區(qū)別僅在于：判別數(shù)反號，即，令負(fù)判別數(shù)中最小的對應(yīng)的變量進(jìn)基；當(dāng)判別數(shù)均大于等于零時為最優(yōu)。表格形式的單純形法解的幾種情況在單純形表上的體現(xiàn)(min型)兩階段法用單純形法消去人工變量（如果可能），即把人工變量變?yōu)榉腔兞?，求出原問題的一個基本可行解；首先引入人工變量。令，即消去人工變量的一種方法是解如下第一階段問題：用單純形法求解原問題。設(shè)得到的最優(yōu)基本可行解是，此時必有下列三種情況之一：（1）（無可行解）（2）且的分量都是非基變量（得基本可行解）（3）且的某些分量是基變量（用主元消去法）兩階段法用單純形法消去人工變量（如果可能），即把人工變量變?yōu)榇驧法其基本思想是：在約束中增加人工變量

xa，同時修改目標(biāo)函數(shù)，增加懲罰值MeTxa

，M是很大的正數(shù)，這樣，在極小化目標(biāo)函數(shù)的過程中，由于M的存在，將迫使人工變量離基。

大M法其基本思想是：在約束中增加人工變量xa，同時修改目標(biāo)修正單純形法在運(yùn)用單純形法解決線性規(guī)劃問題時，如果知道了可行基的逆，就能利用它和原始數(shù)據(jù)來計算基變量的取值及判別數(shù)，從而能夠確定一個基本可行解，并判斷它是否為最優(yōu)解。因此，只要保存原始數(shù)據(jù)和現(xiàn)行基的逆即可。修正單純形法的基本思想是：給定初始基本可行解以后，通過修改舊基的逆來獲得新基的逆，進(jìn)而完成單純形法的其它運(yùn)算。在整個過程中保存現(xiàn)行基的逆。修正單純形法在運(yùn)用單純形法解決線性規(guī)劃問題時，如果知道了可行修正單純形法的計算步驟給定初始可行基的逆，計算單純形乘子w和右端向量。構(gòu)成下表：對于每個非基變量，計算判別數(shù)，令。如果則停止計算，現(xiàn)行基本可行解是最優(yōu)解；否則，下一步。計算主列。若,則停止計算,無有限最優(yōu)解;否則下一步。把主列置于逆矩陣表的右邊，組成下表：