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

第一節平移直線法

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

在互動素材加入上述兩條不等式，紅色部分劃出約束條件下的可行解區域。然後調整目標函數，再平移與其對應的綠色直線，有以下發現：

當序偶\(\;\left(x,y\right)=\left(0,3\right)\;\)時，\(x+4y\;\)在約束條件下達到極大值\(\;12\)。
\(x+4y\;\)在約束條件下不存在下界，所以並沒有極小值。

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

在互動素材加入上述三條不等式，紅色部分劃出約束條件下的可行解區域。然後調整目標函數，再平移與其對應的綠色直線，有以下發現：

當序偶\(\;\left(x,y\right)=\left(0,3\right)\;\)時，\(x+4y\;\)在約束條件下達到極大值\(\;12\)。
當序偶\(\;\left(x,y\right)=\left(-4,-1\right)\;\)時，\(x+4y\;\)在約束條件下達到極小值\(\;-8\)。

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

在互動素材加入上述三條不等式，紅色部分劃出約束條件下的可行解區域。然後調整目標函數，再平移與其對應的綠色直線，有以下發現：

當序偶\(\;\left(x,y\right)=\left(8,-1\right)\;\)時，\(x+4y\;\)在約束條件下達到極大值\(\;9\)。
當序偶\(\;\left(x,y\right)\;\)對應連起\(\;\left( 0,4\right)\;\)和\(\;\left( -4,-1\right)\;\)兩點的線段上的點時，\(x+4y\;\)在約束條件下都能達到極小值\(\;-3\)。換句話說，對於任何\(\;0 \le s \le 1\;\)，當序偶\(\;\left(x,y\right)=\left(-4s,-s+4\right)\;\)時，\(x+4y\;\)在約束條件下都能達到極小值\(\;-3\)。

線性規劃是一種最優化問題：在線性約束條件下尋找某個線性函數的極值。我們可以由以下例子開始學習。

典型的問題

約束條件\(\; \left\{ \begin{array}{l} 3x + 2y - 6 \le 0\\x \ge 0\\ y \ge 0 \end{array} \right.\;\)下，求目標函數\(\;C=2x+y\;\)的極大值和極小值。

透過前面的課件，我們知道滿足三條不等式的可行解區域對應\(\;xy-\)平面上三個半平面的交集。在互動素材中輸入不等式，便可看見可行解區域被塗成紅色。

調整好綠色線的斜率後，線上任何一點對應的序偶\(\;\left(x,y\right)\;\)給出一樣的目標函數值\(\;C\)。

平移綠色線便可以改邊目標函數值。觀察到：向右平移綠色線，則目標函數值上升；反之，則目標函數值下降。當綠色線達到紅色區域的邊界時，目標函數便達到約束條件下的極值：

當綠色線向右達到紅色區域的邊界時，序偶\(\;\left(x,y\right)=\left(2,0\right)\;\)，目標函數\(\;C=2x+y\;\)在約束條件下達到極大值\(\;4\)。
當綠色線向左達到紅色區域的邊界時，當序偶\(\;\left(x,y\right)=\left(0,0\right)\;\)，目標函數\(\;C=2x+y\;\)在約束條件下達到極小值\(\;0\)。

一般的理論

一般來說，有關兩個變量的線性規劃的問題是這樣的：

求目標函數\(\;C=Px+Qy\;\)在約束條件\(\; \left\{ \begin{array}{l} A_1 x + B_1 y + C_1 \ge 0\\A_2 x + B_2 y + C_2 \ge 0\\ \vdots \\A_n x + B_n y + C_n \ge 0 \end{array} \right.\;\)下的極大值(或極小值)。

而平移直線法是這樣的：

在\(\;xy-\)平面上繪畫與線性約束條件有關的直線。
判斷平面上滿足約束條件的可行解區域。
繪畫一條直線方程，使得該直線上的任何一點在目標函數下均取得等值，例如\(\;f(x,y)=0\;\)。
平移上述直線(或上、或下、或左、或右)，則任何時候該直線上的任何一點在目標函數下均取得等值。
觀察到目標函數值在上述直線向同一個方向平移時，其變化是一致的。
在直線移到可行解區域的某個邊界時，目標函數可達到極值。

約束條件的不等式可以是\(\; > \)、\( < \)、\(\ge\;\)或\(\;\le\)；當然，我們總可以改變\(\;A_i, B_i, C_i\;\)來保證不等式是以\(\; > \;\)或\(\;\ge\;\)來表達。
使目標函數在約束條件下達到極值的點可能多於一點。
有時候，目標函數在約束條件下有可能可以不斷上升或不斷下降而無法達到極值。