線性規劃簡介

定義

研究線性約束條件下線性目標函數極值問題的方法總稱，是運籌學的一個分支，在多方面均有應用。線性規劃的某些特殊情況，如網絡流、多商品流量等問題都有可能在 OI 題目中出現

線性規劃問題的描述

一個問題要能轉化為線性規劃問題，首先要有若干個線性約束條件，並且所求的目標函數也應該是線性的。那麼，最容易也最常用的描述方法就是標準型。

我們以《算法導論》中線性規劃一節提出的問題為例：

假如你是一位政治家，試圖贏得一場選舉，你的選區有三種：市區，郊區和鄉村，這些選區分別有 100000、200000 和 50000 個選民，儘管並不是所有人都有足夠的社會責任感去投票，你還是希望每個選區至少有半數選民投票以確保你可以當選

顯而易見的，你是一個正直、可敬的人，然而你意識到，在某些選區，某些議題可以更有效的贏取選票。你的首要議題是修築更多的道路、槍支管制、農場補貼以及調整汽油税。你的競選班子可以為你估測每花費 $1000 做廣告，在每個選區可以贏取或者失去的選票的數量（千人），如下表所示：

政策	市區	郊區	鄉村
修路	-2	5	3
槍支管制	8	2	-5
農場補貼	0	0	10
汽油税	10	0	-2

你的目標是計算出要在市區，郊區和鄉村分別獲得至少 50000，100000 和 25000 張選票所花費的最少錢數。

我們可以使用數學語言來描述它：

$x_1$ 為花費在修路廣告上的錢（千美元）

設 $x_2$ 為花費在槍支管制廣告上的錢（千美元）

設 $x_3$ 為花費在農場補貼廣告上的錢（千美元）

設 $x_4$ 為花費在汽油税廣告上的錢（千美元）

那麼我們可以將「在市區獲得至少 50000 張市區選票」表述為

$-2x_1+8x_2+0x_3+10x_4 \geq 50$

同樣的，「在郊區獲得至少 100000 張選票和在鄉村獲得至少 25000 張選票」可以表示為

$5x_1+2x_2+0x_3+0x_4 \geq 100$

$3x_1-5x_2+10x_3-2x_4 \geq 25$

顯而易見的，廣告服務提供商不會倒貼錢給你然後做反向廣告，由此可得

$x_1,x_2,x_3,x_4 \geq 0$

又因為我們的目標是使總費用最小，綜上所述，原問題可以表述為：

最小化 $x_1+x_2+x_3+x_4$,

滿足

$-2x_1+8x_2+0x_3+10x_4\geq50$

$5x_1+2x_2+0x_3+0x_4\geq100$

$3x_1-5x_2+10x_3-2x_4\geq25$

$x_1,x_2,x_3,x_4\geq0$

這個線性規劃的解就是這個問題的最優策略

用更具有普遍性的語言説：

已知一組實數 $[a_1..a_n]$ 和一組變量 $[x_1..x_n]$, 在定義上有函數 $f(x_1..x_n)=\sum_{i=1}^na_ix_i$

這個函數是線性的。如果 b 是一個實數而滿足 $f(x_1..x_n)=b$, 則這個等式被稱為線性等式，同樣的，滿足 $f(x_1..x_n)\leq b$ 或者 $f(x_1..x_n)\geq b$ 則稱之為線性不等式

在線性規劃問題中，線性等式和線性不等式統稱為線性約束。

一個線性規劃問題是一個線性函數的極值問題，而這個線性函數應該服從於一個或者多個線性約束。

圖解法

當線性規劃問題的變量較少時，我們可以使用圖解法來直觀地解決問題。對於一般的情況，通常使用單純形法。

上一節問題的變量較多，不便於使用圖解法，所以用下面的問題來介紹圖解法：

最小化 $x+y$

滿足

$3x+y\geq9$

$x\leq4$

$y\geq3$

$x,y\in N$

知道這些約束條件以後，我們需要將它們在平面直角座標系中畫出來

$x\leq4$（紅色區域）

$y\geq3$（黑色區域）

$3x+y\geq9$（藍色直線右側區域）

黃色區域為三塊區域的交集，這就是這個線性規劃的所有可行解。因為題目中説明，需要最小化 $x + y$，觀察圖像可知，在點 $(2,3)$,$x$ 和 $y$ 同時取到最小值，此時 $x + y$ 當然最小。因此，$\min(x + y) = (2 + 3) = 5$。

把求解線性規劃的圖解法總結起來，就是先在座標系中作出所有的約束條件，然後作出需要求極值的線性函數（目標函數）的圖像。目標函數中所有點的集合與滿足約束條件的所有點的集合的交集就是這個線性規劃的解集，而所需求的極值由觀察可以輕易得出。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Ir1d, YZircon, huhaoo, QAQAutoMaton, Enter-tainer, Marcythm, sshwy, partychicken, Konano, H-J-Granger, baker221, isdanni, ksyx
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用