線性規劃求解的基本知識

線性規劃模型由3個基本部分組成：

• 決策變量（variable）
• 目標函數（objective）
• 約束條件（constraint）

示例：營養配方問題

（問題）某農場每天至少使用800磅特殊飼料。這種特殊飼料由玉米和大豆粉配制而成，含有以下成份：

?

特殊飼料的營養要求是至少30%的蛋白質和至多5%的纖維。該農場希望確定每天最小成本的飼料配制。
（解答過程）
因為飼料由玉米和大豆粉配制而成，所以模型的決策變量定義為：

x1=每天混合飼料中玉米的重量（磅）x2=每天混合飼料中大豆粉的重量（磅）

目標函數是使配制這種飼料的每天總成本最小，因此表示為：

min z=0.3×1+0.9×2

模型的約束條件是飼料的日需求量和對營養成份的需求量，具體表示為：

x1+x2≥8000.09×1+0.6×2≥0.3(x1+x2)0.02×1+0.06×2≤0.05(x1+x2)

將上述不等式化簡后，完整的模型為：

min z=0.3×1+0.9×2s.t. x1+x2≥8000.21×1-0.3×2≤00.03×1-0.01×2≥0x1,x2≥0

可以使用圖解法確定最優解。下面，我們介紹使用Excel的規劃求解加載項求解該模型。

?

使用Excel規劃求解解線性規劃問題?

1、?安裝Excel規劃求解加載項

單擊“Office按鈕——Excel選項——加載項——（Excel加載項）轉到”，出現“加載宏”對話框，如下圖所示。選擇“規劃求解加載項”，單擊“確定”。

此時，在“數據”選項卡中出現帶有“規劃求解”按鈕的“分析”組，如下圖所示。

?

2、?設計電子表格

使用Excel求解線性規劃問題時，電子表格是輸入和輸出的載體，因此設計良好的電子表格，更加易于閱讀。本例的電子表格設計如下圖所示：

?
其中，輸入數據的單元格使用了陰影格式，即B5:C8和F6:F8；變量和目標函數單元格為B12:D12，加上了粗線邊框；D5:D8中輸入了約束公式，公式如上圖中的右上角所示，其相應的代數表達式見上文。
技巧：也可以在單元格D5中輸入公式：

=SUMPRODUCT(B5:C5,$B$12:$C$12)

然后將其復制到下方相應的單元格中。

?

3、?應用規劃求解工具

單擊“數據——分析——規劃求解”，出現如下圖所示的“規劃求解參數”對話框，設計相應的參數。

?

并且單擊“添加”按鈕，添加相應的約束，如下圖所示。

?

?

注意，上圖所示的約束中，添加了非負限制，即$B$12:$C$12>=0。還可以在“規劃求解參數”對話框中，單擊“選項”按鈕，在出現的“規劃 求解選項”對話框中（如下圖所示）添加非負約束，即選擇“采用線性模型”和“假定非負”前的復選框，其余的默認值可以保持不變。當然，如果精度太高，可以 調低精度，也獲得滿意的結果。

?

4、?求解

設置好參數后，單擊“規劃求解參數”對話框中的“求解”按鈕，結果如下圖所示。

?

為了增強可讀性，還可以使用有描述性的Excel名稱來代替單元格字母。
如果問題沒有可行解，規劃求解將會顯示明確的信息“規劃求解找不到有用的解”。如果最優目標值是無界的，規劃求解將會顯示不太明確的信息“設置目標單元格的值未收斂”。這些情況都表明模型構造的公式有錯誤。
當然，規劃求解工具還可以得出更詳細的報告，這些功能我們在以后討論。