線性規劃

把平行線推到最遠的角落

數乙 · A-12乙-1

max⁡ (ax+by)在可行區域上,最佳解出現在 頂點\max\ (\co a x+\cb b y)\quad\text{在可行區域上,最佳解出現在}\ \cg{\text{頂點}}

先觀察

工廠要決定兩種產品各做幾個。機器時間、人力都有上限,每種產品的利潤不同。

可行的做法有無限多種組合,怎麼不用一個一個試就找到利潤最大的那一種?

一步一步推導

  1. 每個限制式都是一個半平面。把它們疊在一起,共同的部分就是可行區域:所有符合條件的做法。{x≥0, y≥0x+2y≤83x+2y≤12\begin{cases}x\ge0,\ y\ge0\\x+2y\le8\\3x+2y\le12\end{cases}
  2. 目標函數 ax+byax+by 的等值線 ax+by=kax+by=k 是一組平行線:同一條線上的做法利潤一樣。kk 越大,線越往右上移。ax+by=k (一組平行線)ax+by=k\ \text{(一組平行線)}
  3. 把等值線慢慢往利潤變大的方向推。最後還碰得到可行區域的位置,就是最大值;通常停在一個頂點上。max⁡k:離開區域前的最後接觸點\max k:\text{離開區域前的最後接觸點}
  4. 所以只要算出所有頂點,把它們一個個代進目標函數比大小就好。這是線性規劃的核心方法。(0,0),(4,0),(2,3),(0,4) → ax+by(0,0),(4,0),(2,3),(0,4)\ \to\ ax+by
  5. 兩種特殊情形:目標函數和某一條邊平行時,整條邊都是最佳解(有無限多組最佳做法);可行區域無界時,某個方向可能沒有最大值。平行於一邊 ⇒ 整條邊都最佳\text{平行於一邊}\ \Rightarrow\ \text{整條邊都最佳}

課綱與應用

12 年級選修數學乙,是數乙特有的單元(數甲沒有)。前置是 10 年級的二元一次不等式(見「直線方程式」)。

練這間小屋的 5 題

相關單元