運籌學/圖形線性規劃解決方案

我們現在將嘗試找到上一節中介紹的線性規劃模型的最優解。我們將採用的方法被稱為圖形法，可以應用於任何具有兩個決策變數的問題。它基本上包括兩個步驟：找到可行域或可行空間（即平面上所有可行解所在的區域），然後在所有可行解中識別最優解。

為了開始這個過程，我們首先繪製直線

$6x_{1}+4x_{2}=24$,

$x_{1}+2x_{2}=6$,

$x_{2}-x_{1}=1$,

$x_{2}=2$,

在第一象限。請注意，出於我們的目的$x_{1}=x$ 和 $x_{2}=y$ 在圖上。

我們現在將對可行域進行陰影處理。為此，請逐個考慮約束條件。第一個是$6x_{1}+4x_{2}\leq 24$。為了確定它所代表的區域，請選擇任何不透過直線$6x_{1}+4x_{2}=24$ 的點，例如 (0,0)。將其代入約束條件$6x_{1}+4x_{2}\leq 24$ 以得到$0\leq 24$。由於這是正確的，我們得出結論 (0,0) 位於 $6x_{1}+4x_{2}\leq 24$ 所代表的區域中。我們得出結論，$6x_{1}+4x_{2}=24$ 這一側包含 (0,0) 的所有點實際上代表 $6x_{1}+4x_{2}\leq 24$。這一點由直線 $6x_{1}+4x_{2}=24$ 將平面分成兩個不同的半部分：一個點滿足不等式，另一個點不滿足不等式。

透過這種方式，可以對所有不等式進行陰影處理。在所有不等式下都進行陰影處理的區域是整個問題的可行域。(由於我們在第一象限內工作，因此非負性限制成立。)

現在我們準備找出最優解。為此，繪製直線$5x_{1}+4x_{2}=10$。由於$z=5x_{1}+4x_{2}$ 表示目標函式，因此 $5x_{1}+4x_{2}=10$ 表示目標函式值為 10 的點（即總利潤為 10）。現在繪製直線 $5x_{1}+4x_{2}=15$，它表示目標函式值為 15 的點。這讓我們瞭解了 z 增加的方向。最優解出現在點 X，該點是任何進一步增加都會導致 z 超出可行域邊界的點。X 的座標可以透過求解 $6x_{1}+4x_{2}=24$ 和 $x_{1}+2x_{2}=6$ 獲得，因此 $x_{1}=3$ 和 $x_{2}=1.5$。這是問題的最優解，表明鹽 X 和 Y 的數量應分別為 3 和 1.5。這將帶來 21 的最大利潤，即 *最優值*。

需要注意的是，LP 模型中的最優解總是出現在可行域的 *角點*。即使直線 z=c 與其中一個約束平行，這也成立。儘管這個事實的數學證明將涉及大量的線性代數，但我們可以透過注意到任何可行域中的目標函式都會在接觸一個角點後立即滑出該域來滿足自己。

最小化示例

讓我們來看一個最小化問題。當我們不是得到鹽 X 和 Y 的利潤，而是得到它們的生產成本時，它就會在實際應用中出現。我們所要做的就是現在將直線 z=c 朝其減少的方向移動，並且我們在這個點（在我們示例中為 (0,0)）處獲得了最優解，任何進一步的減少都會將 z 帶出可行域。解決問題的另一種方法是將最小化問題轉換為最大化問題。為此，只需考慮目標函式的負值。