是數學規劃中理論成熟，方法有效，應用最廣泛的一個分支。它研究線性的目標函數的極值，而引數必須滿足一組線性等式與不等式組成的約束條件。
線性規劃最早的工作始於20世紀30年代。1939年蘇聯數學傢Л.Β.坎托羅維奇發表的名為《生產組織與計畫中的數學方法》的小冊子，是有關線性規劃的最早文獻。在這以後，美國也開始研究這個問題，早期最有影響的是F.L.希契科克研究的運輸問題及其解。但是，他們的工作都沒有受到註意。由於戰爭的需要要，軍事中有關規劃、計劃、偵察、後勤、生產等各方面的問題都陸續被提出來，系統的研究線性規劃的解法與應用便被提到日程上來瞭。1947年，G.B.丹齊克提出瞭一般的線性規劃模型和理論（線性規劃的名稱也是他首先提出的），以及著名的單純形方法，從而奠定瞭數學規劃作為一門學科的基石。直到現在，單純形方法仍然是這門學科中的有力工具。
從50年代起，線性規劃的應用逐漸從軍事擴大到其它領域。例如，1951年T.C.庫普曼斯結合W.列昂季耶夫投入產出模型將線性規劃應用於生產問題；J.馮·諾伊曼研究矩陣對策與線性規劃的關系，將它應用於經濟平衡問題。大型電子計算機的出現對線性規劃的理論以及應用的發展起著決定性的作用。在經濟領域中廣泛地應用線性規劃方法，並且利用電子計算機已能解決變量個數達數百萬之多的具有特殊結構的大型線性規劃問題。
線性規劃的基本概念 可以用一個簡單的例子來說明，一個工廠生產甲、乙兩種產品，假設產品甲受某種所需原料的限制，每周最多隻能生產8個單位，又假設甲、乙同時需要的另一種原料每周供應60公斤，而生產每單位產品甲需原料5公斤，乙需要2公斤。此外，生產甲、乙需要同一臺機器，且單位產品加工時間甲需2小時，乙需4小時，每周機械最多工作80小時。如果甲的單價為15元，乙為10元，若以生產總值最大為目標，且令甲、乙的產量分別為x1，x2，那麼，問題是要確定x1與x2的值，使滿足約束條件：x1≤8，5x1+2x2≤60，2x1+4x2≤80，x1≥0，x2≥0＝且使目標函數f(x)=15x1+10x2取最大值。下面借助附圖來說明這個簡單線性規劃問題的解的基本性質。
滿足約束條件的每一個點稱為可行解。可行解的全體組成的集合稱為可行解集。在所有可行解中求出一個使目標函數取最大值的可行解，這個可行解稱為最優解。
上述問題的可行解集形成圖中多邊形ABCDE圍成的區域，它有5個頂點A，B，C，D，E。如果賦於目標函數一個給定的值d，則稱f(x)=d為目標函數的等值線，如圖
中虛線所示。在不同的等值線上，目標函數取不同的值，虛線愈向右移動，相應的目標函數值愈大。顯然，在頂點
C=(5，17.5)處，目標函數
f(
x)達到可行解集上的最大值。因為虛線再向右移動便離開瞭可行解集。因此最優解是
x
1=5，
x
2=17.5，目標函數的最大值為
f(
x)=
15
x
1+10
x
2=250。
上例說明，線性規劃的最優解可以在可行解集的某一個頂點上達到。這對於未知變量多於兩個和可行解集不是有界的情形也是正確的，是線性規劃解的一個基本性質。根據這一性質，為瞭求最優解，隻須比較目標函數在有限個頂點上的值。然而，對於變量和約束條件很多的情形，頂點數目很大，必須采用有效方法和借助於電子計算機來求解，單純形方法就是基於此性質而建立的計算方法。
單純形方法 1947年由丹齊克建立的解決線性規劃問題的有效方法。它解決如下的標準型線性規劃問題：
(1)
滿足約束條件：
(2)
， (3)
式中
m≤
n;
α
ij，с
j，
b
j為常數；系數矩陣
A=(
α
ij)的秩為
m。不失一般性可設
b
j≥0，
i=1，2，…，
m；mi
n
f(
x)表示求
f(
x)的極小值。若問題中包含不等式約束
α
i1
x
1+…+
α
in
x
n≤
b
j，則可增加一個非負的松弛變量
x
n
+
j使之化為等式
α
i1
x
1+…+
α
in
x
n+
x
n
+
j=
b
j，
x
n
+
j≥0。若問題是求目標函數
f(
x)的最大值，則可等價地化為求-
f(
x)的最小值。若變量
x
j無非負要求，則可令
再代入各式。例如，通過引進松弛變量
x
3，
x
4，
x
5，前面的舉例可化為標準形式
這時，頂點
A，
B，
C，
D，
E分別對應於可行解：(8，0，0，20，64)，(8，10，0，0，24)，(5，17.5，3，0，0)，(0，20，8，20，0)，(0，0，8，60，80)。它們都隻有3個變量取正值，另2個變量取零值，稱為基礎可行解。一般，滿足約束條件(2)、(3)的可行解
x=(
x
1，
x
2，…，
x
n)，若其中
n-
m個變量取零值，且其他
m個變量在(2)中對應的系數矩陣（記作
B，稱為可行基）非異，則稱
x為一基礎各行解，它對應於可行解集的一個頂點。這
m個變量稱為基變量，其他
n-
m個稱為非基變量。由前面所敘的線性規劃解的基本性質，如果最優解存在，必可在一基礎可行解上達到。單純形方法的基本步驟就是從一個基礎可行解迭代到另一個使目標函數得到改進（或至少不退步）的基礎可行解，並且通過某種判斷準則可以判定它是否為最優解，或判定問題不存在最優解而停止計算。為簡化討論，采用矩陣符號，將問題(1)～(3)寫為：
設已知一可行基
B，將
A分塊為
A=(
B，
N)，相應地
C=
，其中
x
B的
m個分量為基變量，
x
N的
n-
m個分量
x
j(
j∈
J)為非基變量，
J為非基變量的下標集合。於是(5)可寫為
(7)
式中
α
j表示
A的第
j列。記
，
，則(7)式可寫為
， (8)
令
x
j=0(
j∈
J)，則
(因
B為可行基)，故
為基礎可行解，其相應目標函數值為
。考慮任一可行解
x，則由(8)，
， (9)
記
。分三種情形討論：① 若所有
σ
j≥0，
j∈
J，則對任意可行解
x，由(9)式有
f(
x)≥
f(
x
0)，所以
x
0為最優解；②若有某個
σ
k＜0，
k∈
J，且所有
y
ik≤0，
i=1，2，…，
m則當取
x
k＞0 而保留其他非基變量為零時，由(8)式有
， (10)
易見
x
k取任何正值都有
x
≥0，
i=1，…，
m，這時相應的目標函數值
隨
x
k增大而無限制減小，因此問題沒有有限最優值，計算停止：③若有某個
σ
k＜0但某些
y
ik＞0，則由(10)式可知，若令
，
其餘非基變量保持為零，則所有基變量非負，且基變量
x
Bl=0，以
x
k取代
x
Bl作為新的基變量，便得到一個新的基礎可行解，其相應的目標函數值減少（
x
k＞0時）或不變（當
x
k=0時）。為瞭繼續進行迭代，須要計算它所對應的
y
0與
y
j等。由於新的基與
B的不同僅在於用
α
k代替
B的第
l列，故不難由(8)式導出
，與
y
0，
y
j的關系：
，
式中當
j∈挓\
J時，定義
y
ij為當
i=
j，
y
ij=1；當
i≠
j，
y
ij=0。上述過程不斷重復，直到求得最優解或判斷問題無有限最優值為止。在用人工進行計算時，往往將(8)與(9)式的系數排列成單純形表格，在表上進行運算，十分方便有效。
線性規劃的對偶理論 每個線性規劃問題都有一個被稱為它的對偶問題的線性規劃問題與之對應。如線性規劃問題(4)～(6)的對偶問題為
式中
u=(
u
1，
u
2…
u
m)
T。在經濟上
u稱為影子價格。線性規劃的對偶形式及其重要性和著名的對偶定理，是馮·諾伊曼首先發現的。
對偶定理 若原問題與對偶問題之一有有限最優解，則另一問題亦有有限最優解，且兩者的目標函數值相等，即mincTx=maxbTu。若其中之一無有限最優值，則另一問題無可行解。
基於對偶理論，與單純形法有密切聯系的，有對偶單純形法，原始對偶單純形法等；由於計算數學、特別是數值代數的發展，單純形法的具體實現已經有瞭很大發展，並且形成瞭許多能夠有效解決大型線性規劃問題的計算機軟件包，但是從理論上講，單純形法不是多項式算法(見組合最優化)，蘇聯數學傢Л.Γ.哈奇揚於1979年提出瞭著名的線性規劃多項式算法，或稱橢球體算法，從理論上證明瞭線性規劃問題屬於p問題，解決瞭十多年來懸而未決的問題。但隻是理論結果，這一方法距離實際應用還很遠。1984年，印度數學傢N.卡馬卡提出一個新的多項式算法──投影算法，在理論上優於橢球體算法，在實際計算效果上，也顯示瞭高速度，引起瞭運籌學界的重視。
運輸問題 是一類特殊的線性規劃問題，它是由Л.Β.坎托羅維奇與F.L.希契科克分別提出的。其基本提法如下：
設某種產品的產地為A1，A2，…，Am；Ai的產量為αi，若欲將產品從產地運往銷地B1，B2，…，Bn；Bj的銷量為bj，且
。已知單位產品從
A
i運到
B
j的運價為
C
ij，1≤
i≤
m，1≤
j≤
n。問如何調運產品使總的運費最小？
設xij為從Ai運到Bj的產品數量，則上述問題的數學模型為
，
滿足約束條件：
對於解決運輸問題，較有效的解法是網絡流方法和表上作業法。如果將產地和銷地及其間的距離在圖上表示，且要求的是噸公裡數最小，則可以用圖上作業法求解。這個方法是50年代初中國糧食部門的同志的經驗總結，中國科學院的運籌學工作者從數學上嚴格論證瞭它的最優性。圖上作業法的要點是：①沒有對流，即在任何一段運輸路線上沒有相對往返的運輸；②沒有迂回，在一條封閉成圈的回路上，從一點到另一點的運輸要走小半圈，若走大半圈就是迂回。
上述方法簡單易懂，隻需在圖上進行計算和調整，便可得到噸公裡最小的方案。
參考書目
中國科學院數學研究所運籌室編：《運籌學》，科學出版社，北京，1973。
G.B.Dantzig，Lineαr Progrαmming，PrincetonUniv.Press，Princeton，1963.