單純形法:數學術語-中文百科頻道

正文

根據單純形法的原理，在線性規劃問題中，決策變量（控制變量）的值稱為一個解,滿足所有的約束條件的解稱為可行解。使目标函數達到最大值（或最小值）的可行解稱為最優解。這樣，一個最優解能在整個由約束條件所确定的可行區域内使目标函數達到最大值（或最小值）。求解線性規劃問題的目的就是要找出最優解。

可能出現下列情況之一：

①存在着一個最優解；

②存在着無窮多個最優解；

③不存在最優解，這隻在兩種情況下發生，即沒有可行解或各項約束條件不阻止目标函數的值無限增大（或向負的方向無限增大）。

要縮小對最優解的搜索範圍，就必須認識最優解的一般性質，最優解如果存在的話，則它必然處于可行區域的邊界上。

任何一項約束條件的邊界方程是用“＝”号來替換該約束條件中的“≤”或“≥”号而得到的。每一個邊界方程确定一個超平面。因此，可行區域的邊界是由那些滿足一個或同時滿足幾個邊界方程（即處在作為邊界的一個或幾個超平面上）的可行解所組成，而且最優解必在其中。最優解不僅是在可行區域的邊界上，而且也在這個區域的一個隅角上。

一個可行解，如果不處在由另兩個可行解連接起來的任何線段上，它就是一個角點可行解。如果連接兩個角點可行解的線段處在可行區域的邊界上，這兩個角點可行解就稱為相鄰的角點可行解。角點可行解具有下列三個重要性質：

①如果存在着一個最優解，那麼它必定是角點可行解。如果存在有多個最優解，那麼至少有兩個最優解必定是相鄰的角點可行解。

②隻存在有限個數的角點可行解。

③如果一個角點可行解按目标函數值來衡量時比其所有的相鄰角點可行解更好一些，那它就比所有其他角點可行解都更好，也就是最優解。

上述這些性質構成單純形法的原理基礎。最後一個性質的重要性在于它為一個角點可行解是否是最優解提供了一種簡便的檢驗标準，因而毋需列舉所有的可行解。單純形法正是利用了這個性質，隻要檢查少數的角點可行解，并且一旦這個最優性檢驗獲得通過就可立即停止運算。

單純形法的運算步驟可歸結為：①起始步驟──在一個角點可行解上開始。②叠代步驟──移動至一個更好一些的相鄰角點可行解（根據需要反複進行這一步驟）。③停止法則──在當前角點可行解比所有相鄰角點可行解都更好些時停止。當前角點可行解就是一個最優解。

單純形法的優點及其成功之處在于它隻需要較少的有限次數的叠代，即可找到最優解。

對偶

（Dual Simplex Method）1954年美國數學家C.萊姆基提出對偶單純形法。單純形法是從原始問題的一個可行解通過叠代轉到另一個可行解，直到檢驗數滿足最優性條件為止。對偶單純形法則是從滿足對偶可行性條件出發通過叠代逐步搜索原始問題的最優解。在叠代過程中始終保持基解的對偶可行性，而使不可行性逐步消失。

設原始問題為min{cx|Ax=b，x≥0}，則其對偶問題（Dual Problem）為max{yb|yA≤c}。當原始問題的一個基解滿足最優性條件時,其檢驗數cBB-1A-c≤0。即知y=cBB-1（稱為單純形算子）為對偶問題的可行解。所謂滿足對偶可行性，即指其檢驗數滿足最優性條件。因此在保持對偶可行性的前提下，一當基解成為可行解時，便也就是最優解。