線性規(guī)劃
線性規(guī)劃是運籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個重要分支,它是輔助人們進行科學(xué)管理的一種數(shù)學(xué)方法.在經(jīng)濟管理、交通運輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟活動中,提高經(jīng)濟效果是人們不可缺少的要求,而提高經(jīng)濟效果一般通過兩種途徑：一是技術(shù)方面的改進,例如改善生產(chǎn)工藝,使用新設(shè)備和新型原材料.二是生產(chǎn)組織與計劃的改進,即合理安排人力物力資源.線性規(guī)劃所研究的是：在一定條件下,合理安排人力物力等資源,使經(jīng)濟效果達到最好.
單純形法
求解線性規(guī)劃問題的通用方法.單純形是美國數(shù)學(xué)家G.B.丹齊克于1947年首先提出來的.它的理論根據(jù)是：線性規(guī)劃問題的可行域是 n維向量空間Rn中的多面凸集,其最優(yōu)值如果存在必在該凸集的某頂點處達到.頂點所對應(yīng)的可行解稱為基本可行解.單純形法的基本思想是：先找出一個基本可行解,對它進行鑒別,看是否是最優(yōu)解；若不是,則按照一定法則轉(zhuǎn)換到另一改進的基本可行解,再鑒別；若仍不是,則再轉(zhuǎn)換,按此重復(fù)進行.因基本可行解的個數(shù)有限,故經(jīng)有限次轉(zhuǎn)換必能得出問題的最優(yōu)解.如果問題無最優(yōu)解也可用此法判別.單純形法的一般解題步驟可歸納如下：①把線性規(guī)劃問題的約束方程組表達成典范型方程組,找出基本可行解作為初始基本可行解.②若基本可行解不存在,即約束條件有矛盾,則問題無解.③若基本可行解存在,從初始基本可行解作為起點,根據(jù)最優(yōu)性條件和可行性條件,引入非基變量取代某一基變量,找出目標函數(shù)值更優(yōu)的另一基本可行解.④按步驟3進行迭代,直到對應(yīng)檢驗數(shù)滿足最優(yōu)性條件（這時目標函數(shù)值不能再改善）,即得到問題的最優(yōu)解.⑤若迭代過程中發(fā)現(xiàn)問題的目標函數(shù)值無界,則終止迭代.
用單純形法求解線性規(guī)劃問題所需的迭代次數(shù)主要取決于約束條件的個數(shù).現(xiàn)在一般的線性規(guī)劃問題都是應(yīng)用單純形法標準軟件在計算機上求解,對于具有106個決策變量和104個約束條件的線性規(guī)劃問題已能在計算機上解得.
改進單純形法 原單純形法不是很經(jīng)濟的算法.1953年美國數(shù)學(xué)家G.B.丹齊克為了改進單純形法每次迭代中積累起來的進位誤差,提出改進單純形法.其基本步驟和單純形法大致相同,主要區(qū)別是在逐次迭代中不再以高斯消去法為基礎(chǔ),而是由舊基陣的逆去直接計算新基陣的逆,再由此確定檢驗數(shù).這樣做可以減少迭代中的累積誤差,提高計算精度,同時也減少了在計算機上的存儲量.
對偶單純形法 1954年美國數(shù)學(xué)家C.萊姆基提出對偶單純形法.單純形法是從原始問題的一個可行解通過迭代轉(zhuǎn)到另一個可行解,直到檢驗數(shù)滿足最優(yōu)性條件為止.對偶單純形法則是從滿足對偶可行性條件出發(fā)通過迭代逐步搜索原始問題的最優(yōu)解.在迭代過程中始終保持基解的對偶可行性,而使不可行性逐步消失.設(shè)原始問題為min{cx|Ax=b,x≥0},則其對偶問題為 max{yb|yA≤c}.當原始問題的一個基解滿足最優(yōu)性條件時,其檢驗數(shù)cBB-1A-c≤0.即知y＝cBB-1（稱為單純形算子）為對偶問題的可行解.所謂滿足對偶可行性,即指其檢驗數(shù)滿足最優(yōu)性條件.因此在保持對偶可行性的前提下,一當基解成為可行解時,便也就是最優(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個頂點的凸包,是一個多胞體：直線上的一個線段,平面上的一個三角形,三維空間中的一個四面體,等等.