Posted on 2012-05-01 22:39
lenohoo 閱讀(1713)
評論(0) 編輯 收藏 引用
單純形法，求解線性規(guī)劃問題的通用方法。單純形是美國數(shù)學(xué)家G.B.丹齊克于1947年首先提出來的。它的理論根據(jù)是：線性規(guī)劃問題的可行域是 n維向量空間Rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點(diǎn)處達(dá)到。頂點(diǎn)所對應(yīng)的可行解稱為基本可行解。單純形法的基本思想是：先找出一個基本可 行解，對它進(jìn)行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉(zhuǎn)換到另一改進(jìn)的基本可行解,再鑒別；若仍不是，則再轉(zhuǎn)換,按此重復(fù)進(jìn)行。因基本可行解的個 數(shù)有限，故經(jīng)有限次轉(zhuǎn)換必能得出問題的最優(yōu)解。如果問題無最優(yōu)解也可用此法判別。
概述
根據(jù)單純形法的原理，在線性規(guī)劃問題中，決策變量（控制變量）x1，x2，…x n的值稱為一個解,滿足所有的
約束條件的解稱為可行解。使目標(biāo)函數(shù)達(dá)到最大值（或最小值）的可行解稱為最優(yōu)解。這樣，一個最優(yōu)解能在整個由約束條件所確定的可行區(qū)域內(nèi)使目標(biāo)函數(shù)達(dá)到最大值（或最小值）。求解線性規(guī)劃問題的目的就是要找出最優(yōu)解。 最優(yōu)解可能出現(xiàn)下列情況之一：①存在著一個最優(yōu)解；②存在著無窮多個最優(yōu)解；③不存在最優(yōu)解，這只在兩種情況下發(fā)生，即沒有可行解或各項(xiàng)約束條件不阻止目標(biāo)函數(shù)的值無限增大（或向負(fù)的方向無限增大）。 單純形法的一般解題步驟可歸納如下：①把線性規(guī)劃問題的約束方程組表達(dá)成典范型方程組，找出基 本可行解作為初始基本可行解。②若基本可行解不存在，即約束條件有矛盾，則問題無解。③若基本可行解存在，從初始基本可行解作為起點(diǎn)，根據(jù)最優(yōu)性條件和可 行性條件，引入非基變量取代某一基變量，找出目標(biāo)函數(shù)值更優(yōu)的另一基本可行解。④按步驟3進(jìn)行迭代,直到對應(yīng)檢驗(yàn)數(shù)滿足最優(yōu)性條件（這時目標(biāo)函數(shù)值不能再 改善），即得到問題的最優(yōu)解。⑤若迭代過程中發(fā)現(xiàn)問題的目標(biāo)函數(shù)值無界，則終止迭代。 用單純形法求解線性規(guī)劃問題所需的迭代次數(shù)主要取決于約束條件的個數(shù)。現(xiàn)在一般的線性規(guī)劃問題都是應(yīng)用單純形法標(biāo)準(zhǔn)軟件在計(jì)算機(jī)上求解，對于具有106個決策變量和104個約束條件的線性規(guī)劃問題已能在計(jì)算機(jī)上解得。
附：1.決策變量：
又稱控制變量，設(shè)計(jì)變量，操作變量等。在描述過程系統(tǒng)的所有變量中，決策變量可以由設(shè)計(jì)人員按照最能符合系統(tǒng)的目標(biāo)選擇適當(dāng)?shù)臄?shù)值，用來描述系統(tǒng)的特性。決策變量的個數(shù)稱為自由度，自由度不能超過變量的總數(shù)和狀態(tài)方程數(shù)目之差，并且決策變量的選擇往往受到一定約束條件(熱力學(xué)，動力學(xué)或過程、設(shè)備條件)的限制。
內(nèi)生變量是管理者作決策時的可選項(xiàng)， 因此又被稱為模型的決策變量。、
2.約束條件：
運(yùn)用單純形法解某些線性規(guī)劃問題時，該問題已知的并須遵守的前提條件稱為約束條件。
約束條件：
a11x1+a12x2+…+a1nxn≤b1
a21x1+a22x2+…+a2nxn≤b2
…………………………
am1x1+am2x2+…+amnxn≤bm
x1，x2，…，xn≥0 式中x1，x2，…，xn為企業(yè)生產(chǎn)的各種產(chǎn)品；b1，b2，…，bm為可供使用的各種投入要素的數(shù)量；aij(i=1，2…m；j=1,2,… n)為第j種產(chǎn)品每生產(chǎn)1個單位所需要的第i種投入要素的數(shù)量；最后，非負(fù)值約束條件表示各種產(chǎn)品的產(chǎn)量必須是正值，負(fù)值是沒有意義的。
改進(jìn)單純形法
原單純形法不是很經(jīng)濟(jì)的算法。 1953年美國數(shù)學(xué)家G.B.丹齊克為了改進(jìn)單純形法每次迭代中積累起來的進(jìn)位誤差，提出改進(jìn)單純形法。其基本步驟和單純形法大致相同，主要區(qū)別是在逐次 迭代中不再以高斯消元法為基礎(chǔ)，而是由舊基陣的逆去直接計(jì)算新基陣的逆，再由此確定檢驗(yàn)數(shù)。這樣做可以減少迭代中的累積誤差，提高計(jì)算精度，同時也減少了 在計(jì)算機(jī)上的存儲量。
對偶單純形法
（Dual Simplex Method）1954年美國數(shù)學(xué)家C.萊姆基提出對偶單純形法。單純形法是從原始問題的一個可行解通過迭代轉(zhuǎn)到另一個可行解，直到檢驗(yàn)數(shù)滿足最優(yōu)性條件為止。對偶單純形法則是從滿足對偶可行性條件出發(fā)通過迭代逐步搜索原始問題的最優(yōu)解。在迭代過程中始終保持基解的對偶可行性，而使不可行性逐步消失。設(shè)原始問題為min{cx|Ax=b，x≥0}，則其對偶問題（Dual Problem）為 max{yb|yA≤c}。當(dāng)原始問題的一個基解滿足最優(yōu)性條件時,其檢驗(yàn)數(shù)cBB-1A-c≤0。即知y＝cBB-1（稱為單純形算子）為對偶問題的可 行解。所謂滿足對偶可行性，即指其檢驗(yàn)數(shù)滿足最優(yōu)性條件。因此在保持對偶可行性的前提下，一當(dāng)基解成為可行解時，便也就是最優(yōu)解。
其他信息
數(shù)學(xué)優(yōu)化中，由George Dantzig發(fā)明的單純形法是線性規(guī)劃問題的數(shù)值求解的流行技術(shù)。有一個算法與此無關(guān)，但名稱類似，它是Nelder-Mead法或稱下山單純形法，由Nelder和Mead發(fā)現(xiàn)（1965年），這是用于優(yōu)化多維無約束問題的一種數(shù)值方法，屬于更一般的搜索算法的類別。 這二者都使用了單純形的概念，它是N維中的N + 1個頂點(diǎn)的凸包，是一個多胞體：直線上的一個線段，平面上的一個三角形，
三維空間中的一個四面體，等等。