線性規劃求解器

線性規劃求解器

線性規劃求解器是一款在線計算機，用於在滿足一組線性不等式或等式系統的情況下，尋找線性目標函數的最大值或最小值。它採用 單體法（大 M 變體），因此可以自由混合 <=、>= 和 = 約束；對於雙變量問題，它會繪製互動式可行解區域圖，並突出顯示每個頂點和最佳點。

什麼是線性規劃？

線性規劃 (LP) 問題的要求如下：

滿足所有約束條件的點集稱為 可行解區域，它是一個凸多面體。線性規劃基本定理指出，如果線性規劃具有有限的最佳解，則該解一定在該多面體的頂點（極點）處達到。這就是為什麼單體法（從一個頂點移動到另一個頂點）如此有效的原因。

單體法是如何運作的

單體法從一個可行頂點開始，通過轉向具有更好值的相鄰頂點來不斷改進目標函數。其運作機制為：

1. 標準型： 將線性規劃轉換為在 Ax = b, x ≥ 0 約束下最大化 c^Tx。對於 <= 約束，添加 鬆弛（slack）變量；對於 >= 約束，減去 剩餘（surplus）變量並添加帶有巨大懲罰項 −M 的 人工 變量；對於等式，添加人工變量。
2. 初始單體表： 基底由鬆弛變量和人工變量組成，提供了一個明顯的起始頂點。
3. 進基變量： 選擇具有最大正縮減成本 \( c_j - z_j \) 的非基變量。如果不存在此類變量，則當前解即為最佳解。
4. 離基變量： 從進基列中進行 最小比值測試 — 將每一行的 RHS 除以其在進基列中的正項，並選擇比值最小的行。如果不存在正項，則該線性規劃為 無窮解。
5. 樞軸操作： 使用高斯消元法使進基列成為單位向量，在離基行中為 1。
6. 重複上述步驟，直到滿足停止標準。

如果終止時基底中仍留有值為正的人工變量，則原始線性規劃 無可行解。

圖解法（針對雙變量）

對於雙變量問題，可行解區域是一個 2D 凸多邊形。由於最佳解總是在頂點處，因此列舉每個頂點並在該處評估目標函數就足以解決問題。此計算機通過求每對約束邊界的交點來執行此枚舉，僅保留滿足所有其他約束的交點，並按逆時針順序對其進行排序以進行視覺化。

輸入語法

在第一行寫下 目標函數，然後 每行一個約束條件。變量名稱可以是任何標識符（x、y、x1、profit…）。運算符為 <=、>= 和 =。非負性限制可以簡寫為 x, y >= 0。

空行和以 # 開頭的注釋將被忽略。求解器最多接受 8 個決策變量和 20 個約束條件。

計算實例

假設一家家具工作室製作桌子和椅子。每張桌子產生 \\$3 利潤，需要 1 單位木材和 2 單位人工。每把椅子產生 \\$5 利潤，需要 1 單位木材、1 單位人工和 3 單位清漆。現有資源：10 單位木材、16 單位人工、18 單位清漆。令 x = 桌子數量，y = 椅子數量，則線性規劃為：

可行解區域是一個五邊形。在每個頂點評估 Z 值：

因此，工作室應製作 6 張桌子和 4 把椅子 以獲得 \\$38 的最大利潤。木材和人工約束是 有效約束（在最佳點處它們等於其 RHS 值）；清漆的鬆弛量為 0（在此案例中也為有效約束），這意味著所有三種資源都已耗盡。

常見陷阱與求解器檢測項

應用領域

• 產品組合與生產規劃 — 在資源限制下，決定每種產品的產量以獲得最大利潤。
• 飲食與混合問題 — 在滿足營養最低標準的同時，將飲食或飼料成本降至最低。
• 運輸與分配 — 在供需平衡的情況下，將運輸成本降至最低。
• 投資組合優化 — 在風險或曝險約束（線性化）下，使預期回報最大化。
• 網路流 — 最大流和最小費用流問題可以簡化為具有全單模係數矩陣的線性規劃。
• 排班 — 在輪班要求和總工時限制下進行員工排班。

如何使用此計算機

1. 在文字框中輸入您的線性規劃。第一行必須以 Maximize 或 Minimize 開頭。接下來的每一行代表一個約束條件。
2. 使用捷徑 x, y >= 0 一次性聲明所有列出變量的非負性。
3. 點擊「求解線性規劃問題」。求解器將報告最佳值 Z、每個決策變量的最佳值、有效約束列表，以及針對雙變量問題的互動式可行解區域圖。
4. 懸停在圖中的頂點 上以查看其坐標和 Z 值。最佳點會以星號突出顯示。
5. 查看單體表 以觀察每次樞軸操作並追蹤算法如何改進 Z。進基列以琥珀色標出，離基行以紅色標出。

常見問題解答

什麼是線性規劃問題？

線性規劃 (LP) 問題是要求一組滿足線性不等式或等式系統的決策變量，使線性目標函數達到最大值或最小值。可行解集合是一個凸多面體，且最佳點總是在其頂點之一達到 — 這是單體法利用的核心事實。

單體法是如何運作的？

單體法沿著可行多面體的頂點移動。每一步（「樞軸」）將基底中的一個變量換成另一個，移動到具有更好目標值的相鄰頂點。當沒有樞軸可以進一步改善 Z 時，算法停止 — 此時的頂點即為最佳解。此工具使用大 M 法，因此可以混合 <=、>= 和 = 約束。

什麼是可行解區域？

可行解區域是同時滿足所有約束條件的所有變量值的集合。對於 2 個變量，它是 2D 凸多邊形；對於 n 個變量，它是 n 維多面體。多面體為空意味著線性規劃 無可行解；在改進方向上無限延伸的多面體意味著線性規劃 無窮解。

在線性規劃中「無窮解」意味著什麼？

當可行解區域在目標函數不斷改進的方向上延伸至無窮大時，線性規劃就是無窮解的。例如，在僅受 x ≥ 0 約束的情況下 最大化 x 就沒有有限的最大值。現實中返回無窮解通常揭示了缺失的約束 — 通常是對資源或變量的上限。

「多重最佳解」意味著什麼？

多重最佳解發生在多個點達到相同最佳目標值時。從幾何上看，目標函數與多邊形的一個有效邊平行，因此該邊上的每個點 — 以及其端點的每個凸組合 — 都是最佳的。當終止時任何非基決策變量的縮減成本為零，求解器會標記出此情況。

求解器接受多少個變量和約束條件？

最多 8 個決策變量和 20 個約束條件。互動式可行解區域圖僅針對雙變量問題繪製；對於 3 個或更多變量，您仍將獲得完整的數值單體法解、分步單體表和約束條件活動報告。

延伸閱讀

• 線性規劃 — 維基百科
• 單體法 — 維基百科
• 大 M 法 — 維基百科 (英文)
• 優化中的對偶性 — 維基百科

進階數學計算:

• 鄰接矩陣計算機 新
• antilog計算機
• Beta函數計算機
• 二項式係數計算機
• 二項機率分布計算機
• 按位計算機
• 布林代數化簡器 新
• 中央極限定理計算機
• 中國剩餘定理計算機
• 組合計算機 熱門
• 互補誤差函數計算機
• 複數計算機 熱門
• 連分數計算機
• 錯排 子階乘計算機
• 戴克斯特拉最短路徑計算機
• 熵計算機
• 誤差函數計算機
• 歐拉函數計算機
• 指數衰減計算機（高精度）
• 指數增長計算機 高精度
• 指數積分計算機
• 指數計算機（高精度）
• 擴展歐幾里得演算法計算機
• 階乘計算機 熱門
• 伽瑪功能計算機
• 黃金比例計算機
• 圖著色計算機 新
• 圖度數序列驗證器
• 群論階數計算機 新
• 半衰期計算機
• 漢密爾頓路徑檢查器 新
• 容斥原理計算機 新
• 卡諾圖 (K-Map) 求解器 新
• 線性規劃求解器 新
• 馬可夫鏈穩態分布計算機
• 最小生成樹計算機
• 模冪運算計算機 新
• 模乘逆元計算機
• 負二項分布計算機 新
• 網路最大流計算機 新
• 百分比增長率計算機 熱門
• 排列計算機
• 重複排列計算機 新
• 鴿巢原理計算機
• 平面圖檢查器 新
• 泊松分佈計算機
• 多項式根計算機與詳細步驟
• 原根計算機
• 機率計算機
• 機率分布計算機
• 比例計算機 熱門
• 二次公式計算機 熱門
• 環與體計算機 新
• 四捨五入計算機 熱門
• 科學計算機
• 科學記數法計算機 熱門
• 集合論計算機
• 有效數字計算機 熱門
• 穩定婚姻問題求解器 新
• 斯特林數計算機
• 立方和計算機
• 連續數之和計算機
• 平方和計算機
• 拓撲排序計算機 新
• 旅行推銷員問題求解器 (TSP) 新
• 真值表產生器
• 韋恩圖產生器3集合