運籌學/線性規劃

線性規劃（LP）是一種數學建模技術，用於將有限的資源（如材料、機器等）分配給多個競爭性活動（如專案、服務等）。典型的線性規劃問題包括一個線性目標函式，該函式需要在有限數量的線性約束條件下被最大化或最小化。（線性函式是指具有以下形式的函式 $a_{1}x_{1}+a_{2}x_{2}+\cdots a_{n}x_{n}$ 其中 $x_{1},x_{2}\cdots x_{n}$ 都是變數。)

線性規劃的創始人包括喬治·B·丹齊格，他在 1947 年發表了單純形法；約翰·馮·諾依曼，他在同年發展了對偶理論；以及列昂尼德·康託羅維奇，一位俄羅斯數學家，他在丹齊格之前就將類似的技術應用於經濟學，並在 1975 年獲得了諾貝爾經濟學獎。線性規劃問題最早被列昂尼德·哈奇揚在 1979 年證明可以在多項式時間內解決，但該領域更大的理論和實際突破出現在 1984 年，當時納倫德拉·卡馬卡爾提出了一種新的內點法來解決線性規劃問題。

二元線性規劃模型

實際情況下通常不存在二元線性規劃模型，但它們的學習可以為我們提供一個關於如何處理一般模型的示例。

我們將透過一個示例來解釋這個模型。

考慮一家生產兩種鹽類 X 和 Y 的化工廠。假設酸和鹼是該公司生產這兩種鹽類所需的僅有的兩種化學物質。此外，假設該公司所有者根據過去的經驗獲得了以下資料

生產 1 單位鹽 X 需要 6 單位酸和 1 單位鹼。生產 1 單位鹽 Y 需要 4 單位酸和 2 單位鹼。每天最多可以獲得 24 單位酸和 6 單位鹼。1 單位鹽 X 可以為他帶來 5 的利潤（以任何貨幣），1 單位鹽 Y 可以為他帶來 4 的利潤。此外，由於市場調查，他知道鹽 Y 的日需求量不能超過鹽 X 的需求量 1 個單位以上，並且鹽 Y 的最大日需求量為 2 個單位。

該公司所有者希望獲得最佳的“產品組合”。也就是說，他想了解他每天應該生產多少 X 和 Y，以獲得最高的利潤。

為了制定這個問題的線性規劃模型，我們首先需要確定“決策變數”。這些是代表我們需要實際做出決策的實體的變數。在我們這個問題中，很明顯，實體是鹽 X 和 Y，因此變數應該代表每種鹽類的生產量。因此，讓

$x_{1}$ = 每天生產的鹽 X 的單位數

$x_{2}$ = 每天生產的鹽 Y 的單位數

下一步是決定模型的目標函式是什麼。從名稱本身就可以清楚地看出，目標函式代表我們的目標，即最大化我們的總利潤。由於總利潤通常是 X 和 Y 的利潤之和，因此它應該等於 $5x_{1}+4x_{2}$ 。假設如果 1 單位 X（或 Y）帶來 5（或 4）的利潤，那麼 $x_{1}$ （或 $x_{2}$ ）單位將帶來 $5x_{1}$ （或 $4x_{2}$ ）的利潤。因此，如果 z 代表每日總利潤，目標是

最大化 z = $5x_{1}+4x_{2}$ .

現在我們考慮限制酸和鹽使用的約束條件。我們知道每天使用的總酸量不能超過 24。由於 $6x_{1}$ 和 $4x_{2}$ 分別是製造鹽 X 和 Y 所使用的酸量，我們可以得出結論，我們的約束條件是

$6x_{1}+4x_{2}\leq 24$

類似地，對於鹼，

$x_{1}+2x_{2}\leq 6$

現在市場要求 Y 的日產量超過 X 的產量 $x_{2}-x_{1}$ 不能超過 1，這意味著

$x_{2}-x_{1}\leq 1$

此外，鹽 Y 的最大日需求量為 2 單位，因此

$x_{2}\leq 2$

一個隱含的假設是變數 $x_{1}$ 和 $x_{2}$ 不能取負值（為什麼？）。非負性約束， $x_{1},x_{2}\geq 0$ 考慮了這個要求。

完整的模型現在可以表述為

最大化 z = $5x_{1}+4x_{2}$

受制於，

$6x_{1}+4x_{2}\leq 24$ ,

$x_{1}+2x_{2}\leq 6$ ,

$x_{2}-x_{1}\leq 1$ ,

$x_{2}\leq 2$ ,

$x_{1},x_{2}\geq 0$ .

任何滿足所有五個約束條件的 $x_{1}$ 和 $x_{2}$ 的值構成一個可行解。否則，該解是不可行的。例如，解 $x_{1}=3$ 和 $x_{2}=1$ 是可行的，因為在代入約束條件後，沒有一個不等式被違反。另一方面，解 $x_{1}=4$ 和 $x_{2}=1$ 是不可行的，因為它不滿足約束條件 (1)，即 6*4+4*1=28，大於等式右側 (=24)。

我們的目標是找到最優解，即在可行的情況下，最大化目標函式的解。如何實現這一點將在後面的章節中討論。

LP 模型的性質

LP 模型具有以下性質

**比例性**: 每個決策變數在目標函式和約束條件中的貢獻與其值成正比。例如，第一個約束條件中第一個決策變數的貢獻是 $6x_{1}$ 。這與 $x_{1}$ 成正比，比例常數為 6。簡單來說，就是遵循了三數法則。

**可加性**: 目標函式和約束條件中所有變數的貢獻等於每個變數單獨貢獻的總和。例如，總利潤為 $5x_{1}+4x_{2}$ ，它是單個利潤 $5x_{1}$ 和 $4x_{2}$ 的總和。

**確定性**: 所有目標函式和約束條件的係數都是確定的，也就是說關於利潤、可用資源和需求的所有資料都是固定的。