[興倫智能課堂] 線性規劃

第二節頂點試算法

更多的例子

利用互動素材，求\(\;C=x+y\;\)在約束條件\(\; \left\{ \begin{array}{l} y + 10 \ge 0\\2x-y+5 \ge 0\\ 3x+y+2\le 0\\ -x+y+2\le 0 \end{array} \right.\;\)下的極大值和極小值。

利用互動素材畫出可行解區域，發現它是有界閉集。所以，我們只要把所有頂點坐標對應的序偶代入目標函數中，便可以找到\(\;C=x+y\;\)在約束條件下的極大值和極小值。

當\(\;\left(x,y\right)=\left(-\dfrac{15}{2},-10\right)\;\)，\(C=x+y=-\dfrac{35}{2}\)。
當\(\;\left(x,y\right)=\left(-7,-9\right)\;\)，\(C=x+y=-16\)。
當\(\;\left(x,y\right)=\left(0,-2\right)\;\)，\(C=x+y=-2\)。
當\(\;\left(x,y\right)=\left(\dfrac{8}{3},-10\right)\;\)，\(C=x+y=-\dfrac{22}{3}\)。

所以，\(C\;\)在約束條件下的極大值是\(\;-2\)，而極小值是\(\;-\dfrac{35}{2}\)。

利用互動素材，求\(\;C=x-y\;\)在約束條件\(\; \left\{ \begin{array}{l} 3x+3y - 10 \le 0\\x+7 \ge 0\\ y+6\ge 0\\ -x+y+2\ge 0 \end{array} \right.\;\)下的極大值和極小值。

利用互動素材畫出可行解區域，發現它是有界閉集。所以，我們只要把所有頂點坐標對應的序偶代入目標函數中，便可以找到\(\;C=x-y\;\)在約束條件下的極大值和極小值。

當\(\;\left(x,y\right)=\left(-7,-6 \right)\;\)，\(C=x-y=-1\)。
當\(\;\left(x,y\right)=\left(-4,-6\right)\;\)，\(C=x-y=2\)。
當\(\;\left(x,y\right)=\left(\dfrac{8}{3},\dfrac{2}{3}\right)\;\)，\(C=x-y=2\)。
當\(\;\left(x,y\right)=\left(-7,\frac{31}{3}\right)\;\)，\(C=x-y=-\dfrac{52}{3}\)。

所以，\(C\;\)在約束條件下的極大值是\(\;2\)，而極小值是\(\;-\dfrac{52}{3}\)。

利用互動素材，求\(\;C=x+5y\;\)在約束條件\(\; \left\{ \begin{array}{l} 2x-5y \ge 0\\x+y+7 \ge 0\\ y+6\ge 0\\ -x+y+3\ge 0 \end{array} \right.\;\)下的極大值和極小值。

利用互動素材畫出可行解區域，發現它是有界閉集。所以，我們只要把所有頂點坐標對應的序偶代入目標函數中，便可以找到\(\;C=x+5y\;\)在約束條件下的極大值和極小值。

所以，\(C\;\)在約束條件下的極大值是\(\;15\)，而極小值是\(\;-27\)。

一般的理論

在上一節，細心的同學可能已經觀察到，如果可行解區域為有界閉集(bounded and closed set)，則其中總會有某個頂點給出線性規劃的最優解。這是正確的觀察。當你發現線性約束條件下的可行解區域是有界的，你只要試試目標函數在各頂點的數值便可以最優解。這就是頂點試算法。

典型的問題

利用互動素材，求\(\;C=4x+5y\;\)在約束條件\(\; \left\{ \begin{array}{l} -x + 3y \le 10\\4x \ge -28 \\ 5y \ge -30 \\ y+2\ge x \end{array} \right.\;\)下的極大值和極小值。

首先，重寫約束條件為\(\; \left\{ \begin{array}{l} -x + 3y -10 \le 0\\x+7 \ge 0 \\ y+6 \ge 0 \\ -x+y+2\ge 0 \end{array} \right.\;\)。

利用互動素材畫出可行解區域，發現它是有界閉集。所以，我們只要把所有頂點坐標對應的序偶代入目標函數中，便可以找到\(\;C=4x+5y\;\)在約束條件下的極大值和極小值。

當\(\;\left(x,y\right)=\left(-7,-6\right)\;\)，\(C=4x+5y=-58\)。
當\(\;\left(x,y\right)=\left(-4,-6\right)\;\)，\(C=4x+5y=-46\)。
當\(\;\left(x,y\right)=\left(8,6\right)\;\)，\(C=4x+5y=62\)。
當\(\;\left(x,y\right)=\left(-7,1\right)\;\)，\(C=4x+5y=-23\)。
所以，\(C\;\)在約束條件下的極大值是\(\;62\)，而極小值是\(\;-58\)。