線性規劃簡介
數學模型
（1）列出約束條件及目标函數
（2）畫出約束條件所表示的可行域
（3）在可行域内求目标函數的最優解及最優值
标準型
描述線性規劃問題的常用和最直觀形式是标準型。标準型包括以下三個部分：
一個需要極大化的線性函數：
以下形式的問題約束：
和非負變量：
其它類型的問題，例如極小化問題，不同形式的約束問題，和有負變量的問題，都可以改寫成其等價問題的标準型。
模型建立
從實際問題中建立數學模型一般有以下三個步驟；
1.根據影響所要達到目的的因素找到決策變量；
2.由決策變量和所在達到目的之間的函數關系确定目标函數；
3.由決策變量所受的限制條件确定決策變量所要滿足的約束條件。
所建立的數學模型具有以下特點：
1、每個模型都有若幹個決策變量（x1，x2，x3……，xn），其中n為決策變量個數。決策變量的一組值表示一種方案，同時決策變量一般是非負的。
2、目标函數是決策變量的線性函數，根據具體問題可以是最大化（max）或最小化（min），二者統稱為最優化（opt）。
3、約束條件也是決策變量的線性函數。
當我們得到的數學模型的目标函數為線性函數，約束條件為線性等式或不等式時稱此數學模型為線性規劃模型。
例：
生産安排模型：某工廠要安排生産Ⅰ、Ⅱ兩種産品，已知生産單位産品所需的設備台時及A、B兩種原材料的消耗，如表所示，表中右邊一列是每日設備能力及原材料供應的限量，該工廠生産一單位産品Ⅰ可獲利2元，生産一單位産品Ⅱ可獲利3元，問應如何安排生産，使其獲利最多？
解：
1、确定決策變量：設x1、x2分别為産品Ⅰ、Ⅱ的生産數量；
2、明确目标函數：獲利最大，即求2x1+3x2最大值；
3、所滿足的約束條件：
設備限制：x1+2x2≤8
原材料A限制：4x1≤16
原材料B限制：4x2≤12
基本要求：x1，x2≥0
用max代替最大值，s.t.（subject to的簡寫）代替約束條件，則該模型可記為：
max z=2x1+3x2
s.t.x1+2x2≤8
4x1≤16
4x2≤12
x1，x2≥0
解法
求解線性規劃問題的基本方法是單純形法，已有單純形法的标準軟件，可在電子計算機上求解約束條件和決策變量數達10000個以上的線性規劃問題。為了提高解題速度，又有改進單純形法、對偶單純形法、原始對偶方法、分解算法和各種多項式時間算法。對于隻有兩個變量的簡單的線性規劃問題，也可采用圖解法求解。這種方法僅适用于隻有兩個變量的線性規劃問題。它的特點是直觀而易于理解，但實用價值不大。通過圖解法求解可以理解線性規劃的一些基本概念。
對于一般線性規劃問題：Min z=CX
S.T.
AX=b
X>=0
其中A為一個m*n矩陣。
若A行滿秩
則可以找到基矩陣B，并尋找初始基解。
用N表示對應于B的非基矩陣。則規劃問題1可化為：
規劃問題2：
Min z=CB XB+CNXN
S.T.B XB+N XN=b(1)
XB>=0，XN>=0(2)
(1)兩邊同乘B-1，得
XB+B-1 N XN=B-1 b
同時，由上式得XB=B-1 b-B-1 N XN，也代入目标函數，問題可以繼續化為：
規劃問題3：
Min z=CB B-1 b+(CN- CB B-1 N)XN
S.T.
XB+B-1N XN=B-1 b(1)
XB>=0，XN>=0(2)
令N:=B-1N，b:=B-1 b，ζ=CB B-1b，σ= CN - CB B-1 N，則上述問題化為規劃問題形式4：
Min z=ζ+σ XN
S.T.
XB+N XN=b(1)
XB>=0，XN>=0(2)
在上述變換中，若能找到規劃問題形式4，使得b>=0，稱該形式為初始基解形式。
上述的變換相當于對整個擴展矩陣（包含C及A）乘以增廣矩陣。所以重在選擇B，從而找出對應的CB。
若存在初始基解
若σ>=0
則z>=ζ。同時，令XN=0，XB=b，這是一個可行解，且此時z=ζ，即達到最優值。所以，此時可以得到最優解。
若σ>=0不成立
可以采用單純形表變換。
σ中存在分量<0。這些負分量對應的決策變量編号中，最小的為j。N中與j對應的列向量為Pj。
若Pj<=0不成立
則Pj至少存在一個分量ai，j為正。在規劃問題4的約束條件（1）的兩邊乘以矩陣T。
T=
則變換後，決策變量xj成為基變量，替換掉原來的那個基變量。為使得T b>=0，且T Pj=ei（其中，ei表示第i個單位向量），需要：
l ai，j>0。
l βq+βi*(-aq，j/ai，j)>=0，其中q!=i。即βq>=βi/ai，j*aq，j。
n若aq，j<=0，上式一定成立。
n若aq，j>0，則需要βq/aq，j>=βi/ai，j。因此，要選擇i使得βi/ai，j最小。
如果這種方法确定了多個下标，選擇下标最小的一個。
轉換後得到規劃問題4的形式，繼續對σ進行判斷。由于基解是有限個，因此，一定可以在有限步跳出該循環。
若對于每一個i，ai，j<=0
最優值無解。
若不能尋找到初始基解
無解。
若A不是行滿秩
化簡直到A行滿秩，轉到若A行滿秩。
發展
法國數學家J.-B.-J.傅裡葉和C.瓦萊－普森分别于1832和1911年獨立地提出線性規劃的想法，但未引起注意。
1939年蘇聯數學家Л.В.康托羅維奇在《生産組織與計劃中的數學方法》一書中提出線性規劃問題，也未引起重視。
1947年美國數學家G.B.Dantzing提出求解線性規劃的單純形法，為這門學科奠定了基礎。
1947年美國數學家J.von諾伊曼提出對偶理論，開創了線性規劃的許多新的研究領域，擴大了它的應用範圍和解題能力。
1951年美國經濟學家T.C.庫普曼斯把線性規劃應用到經濟領域，為此與康托羅維奇一起獲1975年諾貝爾經濟學獎。
50年代後對線性規劃進行大量的理論研究，并湧現出一大批新的算法。例如，1954年C.萊姆基提出對偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規劃的靈敏度分析和參數規劃問題，1956年A.塔克提出互補松弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解算法等。
線性規劃的研究成果還直接推動了其他數學規劃問題包括整數規劃、随機規劃和非線性規劃的算法研究。由于數字電子計算機的發展，出現了許多線性規劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變量的線性規劃問題。
1979年蘇聯數學家L.G.Khachian提出解線性規劃問題的橢球算法，并證明它是多項式時間算法。
1984年美國貝爾電話實驗室的印度數學家N.卡馬卡提出解線性規劃問題的新的多項式時間算法。用這種方法求解線性規劃問題在變量個數為5000時隻要單純形法所用時間的1/50。現已形成線性規劃多項式算法理論。50年代後線性規劃的應用範圍不斷擴大。建立線性規劃模型的方法。
應用
在企業的各項管理活動中，例如計劃、生産、運輸、技術等問題，線性規劃是指從各種限制條件的組合中，選擇出最為合理的計算方法，建立線性規劃模型從而求得最佳結果。
