線性規劃

數學敘述

線性規劃由線性目標與線性限制構成，尋找可行域上的最小或最大值。有限候選網格可以完整核對列出的點，但除非已證候選完整涵蓋一般可行域，結論只能稱為所給候選中的最佳。

代表公式（精確 TeX）

L(x,y)

成立條件

• 題庫使用二變數整係數限制 ax+by≤c、整係數目標及完整明示有限候選點。
• 不以有限格點枚舉宣稱連續多面體或一般LP的全域最優解。

符號作用域

• L — 線性規劃資料
• x — 第一決策座標
• y — 第二決策座標

直觀、定義與常見誤解

先逐限制核對可行性，再只在可行候選間比較目標值。

線性目標可能在多個候選點平手，argmin或argmax應保留全部索引。

有限候選表的完整性是結論範圍的一部分；沒有多面體頂點完備性證明時不能外推。

把不可行但目標值較好的點當最優，或把有限格點最佳冒充一般LP最優。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• 最佳化問題 — LP是線性目標與線性限制的最佳化特例。
• 一元一次方程式 — 限制邊界使用線性式。
• 二元聯立一次方程組與退化邊界 — 限制邊界交點可由線性系統描述。
• 固定基底下的平面向量 — 目標與限制係數可視為向量內積。

驗證界線

只證所給有限候選中的最佳；一般LP可行域、對偶與最優證書未建立。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。

下一個義務

加入標準形、頂點、對偶與可重播最優性證書。

同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。