線性規劃
把平行線推到最遠的角落
數乙 · A-12乙-1
max (ax+by)在可行區域上,最佳解出現在 頂點
先觀察
工廠要決定兩種產品各做幾個。機器時間、人力都有上限,每種產品的利潤不同。
可行的做法有無限多種組合,怎麼不用一個一個試就找到利潤最大的那一種?
一步一步推導
- 每個限制式都是一個半平面。把它們疊在一起,共同的部分就是可行區域:所有符合條件的做法。⎩⎨⎧x≥0, y≥0x+2y≤83x+2y≤12
- 目標函數 ax+by 的等值線 ax+by=k 是一組平行線:同一條線上的做法利潤一樣。k 越大,線越往右上移。ax+by=k (一組平行線)
- 把等值線慢慢往利潤變大的方向推。最後還碰得到可行區域的位置,就是最大值;通常停在一個頂點上。maxk:離開區域前的最後接觸點
- 所以只要算出所有頂點,把它們一個個代進目標函數比大小就好。這是線性規劃的核心方法。(0,0),(4,0),(2,3),(0,4) → ax+by
- 兩種特殊情形:目標函數和某一條邊平行時,整條邊都是最佳解(有無限多組最佳做法);可行區域無界時,某個方向可能沒有最大值。平行於一邊 ⇒ 整條邊都最佳
課綱與應用
12 年級選修數學乙,是數乙特有的單元(數甲沒有)。前置是 10 年級的二元一次不等式(見「直線方程式」)。
練這間小屋的 5 題