A-level 數學/OCR/D1/線性規劃

線性規劃是一種利用直線圖形和不等式尋找問題最佳解決方案（最佳化）的方法。

線性規劃問題的例子

一家工廠生產兩種型別的椅子，A 型和 B 型。工廠生產 A 型椅子每把利潤為 10 英鎊，生產 B 型椅子每把利潤為 10 英鎊。A 型椅子需要 20 個工時，B 型椅子需要 30 個工時。每把 A 型椅子需要 3 平方米木材；每把 B 型椅子需要 5 平方米木材。假設每週有 400 個工時和 50 平方米木材可用，那麼每週應該生產多少把每種型別的椅子才能使工廠的利潤最大化？

圖形法

解決這個問題的一種方法是在座標軸上繪製 a 和 b，然後繪製一條線來表示每個約束作為不等式。這將導致一個可行區域，該區域是滿足所有約束條件的區域。問題的最佳解決方案將位於該區域的頂點之一。

單純形法

首先，我們需要用線性方程來表示這個問題。我們將生產的 A 型椅子數量稱為 *a*，生產的 B 型椅子數量稱為 *b*。然後我們可以看到

${\begin{aligned}20a+30b\leq 400\Rightarrow &2a+3b\leq 40\\&3a+5b\leq 50\\&a\geq 0\\&b\geq 0\end{aligned}}$

這些被稱為線性規劃問題的約束。要最大化的函式（稱為目標函式）為

$P=10a+10b\,$

P 表示在給定的 a 和 b 值下的利潤。要使用單純形法，我們必須將約束條件和目標函式轉換為以下格式

${\begin{aligned}P-10a-10b=0\\2a+3b+s=40\\3a+5b+t=50\end{aligned}}$

變數 s 和 t 被稱為鬆弛變數。它們允許我們表示在達到該約束的最大值之前我們擁有的餘地。這也意味著我們不再需要使用不等式。我們將所有方程中變數的係數設定在一個初始“表格”中，最後一行是每個方程的右邊，如下所示

${\begin{matrix}P&a&b&s&t&=\\1&-10&-10&0&0&0\\0&2&3&1&0&40\\0&3&5&0&1&50\end{matrix}}$

設定好表格後，就按照單純形演算法進行操作

1. 考慮頂行有負數的任何一列，將最後一列的值除以同一行中正在考慮的列的正值。在我們當前的例子中，我們看到 a 列和 b 列在頂行有負值。我們任意決定考慮 a 列，因此我們將執行

${\frac {40}{2}}=20$

${\frac {50}{3}}=16{\frac {2}{3}}$

現在我們選擇 a 列中的值 3，因為它在我們將 50 除以它時給了我們最小的值。3 現在被稱為樞軸。

2. 將樞軸所在的整行除以樞軸。

3. 現在我們需要將其他兩行中 a 的值減至 0。我們必須透過新增或減去樞軸行的常數倍數來做到這一點。

4. 如果頂行中仍然存在任何負數，我們必須重複演算法。

參見

• 運籌學/單純形法