1、單純形法原理及步驟單純形法，求解線性規劃問題的通用方法。單純形是美國數學家G.B.丹齊克于1947年首先提出來的。它的理論根據是：線性規劃問題的可行域是n維向量空間Rn中的多面凸集，其最優值如果存在必在該凸集的某頂點處達到。頂點所對應的可行解稱為基本可行解。單純形法的基本思想是：先找出一個基本可行解，對它進行鑒別，看是否是最優解；若不是，則按照一定法則轉換到另一改進的基本可行解，再鑒別；若仍不是，則再轉換，按此重復進行。因基本可行解的個數有限，故經有限次轉換必能得出問題的最優解。如果問題無最優解也可用此法判別。單純形法是從某一基可行解出發，連續地尋找相鄰的基可行解，直到達到最優的迭代過程，其實

2、質是解線性方程組。概述：根據單純形法的原理，在線性規劃問題中，決策變量（控制變量）x1,x2,xn的值稱為一個解，滿足所有的約束條件的解稱為可行解。使目標函數達到最大值（或最小值）的可行解稱為最優解。這樣，一個最優解能在整個由約束條件所確定的可行區域內使目標函數達到最大值（或最小值）。求解線性規劃問題的目的就是要找出最優解。最優解可能出現下列情況之一：存在著一個最優解；存在著無窮多個最優解；不存在最優解，這只在兩種情況下發生，即沒有可行解或各項約束條件不阻止目標函數的值無限增大（或向負的方向無限增大）。單純形法的一般解題步驟可歸納如下：把線性規劃問題的約束方程組表達成典范型方程組，找出基本可行

3、解作為初始基本可行解。若基本可行解不存在，即約束條件有矛盾，則問題無解。若基本可行解存在，從初始基本可行解作為起點，根據最優性條件和可行性條件，引入非基變量取代某一基變量，找出目標函數值更優的另一基本可行解。按步驟3進行迭代，直到對應檢驗數滿足最優性條件（這時目標函數值不能再改善），即得到問題的最優解。若迭代過程中發現問題的目標函數值無界，則終止迭代。用單純形法求解線性規劃問題所需的迭代次數主要取決于約束條件的個數。現在一般的線性規劃問題都是應用單純形法標準軟件在計算機上求解，對于具有106個決策變量和104個約束條件的線性規劃問題已能在計算機上解得。求解步驟：（1）確定初始基可行解從線性規劃

4、標準形的系數矩陣中能直接找出m個線性獨立的單位向量； 對約束條件全為“<=”連接的LP，化為標準形，左端添加松弛變量后即形成一個單位子矩陣； 約束條件中含有“<=”或“=”連接的方程，在插入剩余變量后找不到單位矩陣，則必須采用“人造基”法，也稱“人工變量”法。（2）最優性檢驗及解的判別準則最優性判定準則 多重最優解判定準則無界最優解判定準則（3）換基迭代確定換入變量 確定換出變量樞運算（旋轉運算）單純形法-正文：根據單純形法的原理，在線性規劃問題中，決策變量（控制變量）x1,x2,xn的值稱為一個解，滿足所有的約束條件的解稱為可行解。使目標函數達到最大值（或最小值）的可行解稱為最優

5、解。這樣，一個最優解能在整個由約束條件所確定的可行區域內使目標函數達到最大值（或最小值）。求解線性規劃問題的目的就是要找出最優解。可能出現下列情況之一：存在著一個最優解；存在著無窮多個最優解；不存在最優解，這只在兩種情況下發生，即沒有可行解或各項約束條件不阻止目標函數的值無限增大（或向負的方向無限增大）。要縮小對最優解的搜索范圍，就必須認識最優解的一般性質，最優解如果存在的話，則它必然處于可行區域的邊界上。任何一項約束條件的邊界方程是用=”號來替換該約束條件中的“域“肯而得到的。每一個邊界方程確定一個超平面。因此，可行區域的邊界是由那些滿足一個或同時滿足幾個邊界方程（即處在作為邊界的一個或幾個

6、超平面上）的可行解所組成，而且最優解必在其中。最優解不僅是在可行區域的邊界上，而且也在這個區域的一個隅角上。一個可行解，如果不處在由另兩個可行解連接起來的任何線段上，它就是一個角點可行解。如果連接兩個角點可行解的線段處在可行區域的邊界上，這兩個角點可行解就稱為相鄰的角點可行解。角點可行解具有下列三個重要性質：如果存在著一個最優解，那么它必定是角點可行解。如果存在有多個最優解，那么至少有兩個最優解必定是相鄰的角點可行解。只存在有限個數的角點可行解。如果一個角點可行解按目標函數值來衡量時比其所有的相鄰角點可行解更好一些，那它就比所有其他角點可行解都更好，也就是最優解。上述這些性質構成單純形法的原理

7、基礎。最后一個性質的重要性在于它為一個角點可行解是否是最優解提供了一種簡便的檢驗標準，因而毋需列舉所有的可行解。單純形法正是利用了這個性質，只要檢查少數的角點可行解，并且一旦這個最優性檢驗獲得通過就可立即停止運算。單純形法的運算步驟可歸結為：起始步驟一一個角點可行解上開始。迭代步驟一-動至一個更好一些的相鄰角點可行解（根據需要反復進行這一步驟）。停止法則一當前角點可行解比所有相鄰角點可行解都更好些時停止。當前角點可行解就是一個最優解。單純形法的優點及其成功之處在于它只需要較少的有限次數的迭代，即可找到最優解。改進單純形法：原單純形法不是很經濟的算法。1953年美國數學家G.B.丹齊克為了改進單

8、純形法每次迭代中積累起來的進位誤差，提出改進單純形法。其基本步驟和單純形法大致相同，主要區別是在逐次迭代中不再以高斯消去法為基礎，而是由舊基陣的逆去直接計算新基陣的逆，再由此確定檢驗數。這樣做可以減少迭代中的累積誤差，提高計算精度，同時也減少了在計算機上的存儲量。對偶單純形法：(DualSimplexMethod)1954年美國數學家C.萊姆基提出對偶單純形法。單純形法是從原始問題的一個可行解通過迭代轉到另一個可行解，直到檢驗數滿足最優性條件為止。對偶單純形法則是從滿足對偶可行性條件出發通過迭代逐步搜索原始問題的最優解。在迭代過程中始終保持基解的對偶可行性，而使不可行性逐步消失。設原始問題為mincx|Ax二b,x0,則其對偶問題(DualProblem)為maxyb|yAW。當原始問題的一個基解滿足最優性條件時，其檢驗數cB