線性規(guī)劃問題的應用及求解方法

韓雅琦

摘 要：線性規(guī)劃是一類特殊的“最優(yōu)化”問題，它是針對如何利用有限的資源取得最大收益這類問題而提出的。本文對教材中的線性規(guī)劃問題進行了深入研究，從簡單線性規(guī)劃問題求解的常規(guī)圖解法入手，提出了了兩個決策變量的線性規(guī)劃問題的求解方法。本文揭示了線性規(guī)劃問題思想的本質，闡明了“最優(yōu)解”之所以最優(yōu)的原因，詮釋了數學來源于生活又服務于生活的含義。

關鍵詞：線性規(guī)劃；數學模型；最優(yōu)解

一、引言

在生產和經營等經濟活動中，經常需要進行計劃或規(guī)劃，如在生產條件不變的情況下，如何經過統(tǒng)籌安排，改進生產組織或計劃，合理安排人力、物力、資金等資源，組織生產過程，使總的經濟效益最大化。通過學習人教B版普通高中課程標準實驗教科書數學必修5的第三章“不等式”，筆者發(fā)現線性規(guī)劃問題在數學領域和實際生活中的應用相當廣泛。雖然各類經濟活動計劃和規(guī)劃的內容千差萬別，但其共同特點均可歸結為：在現有各項資源條件的限制下，如何確定方案，使預期目標達到最優(yōu)化；或為了達到預期目標，使資源消耗最少。

然而，教材只介紹了簡單的數學規(guī)劃問題。首先，以生產安排的實例作為問題引入新課，借助不等式建立線性規(guī)劃模型，通過將不等式組表示成平面上的區(qū)域，確定可行域，利用圖解法求得使利潤達到最大的最優(yōu)解，即最佳生產安排方案。由于該問題要確定的是產品的生產工時，得到的是整數解，并且由圖易知最優(yōu)解是唯一的。接著，舉了一個營養(yǎng)調配的例子，采取與引例相同的求解方法，得到了滿足消費金額最低的食物購買方案。此問題的目的是給出食物的購買量，其結果是整數解，從求解過程可以看出，該問題的最優(yōu)解也是唯一解。然后，例2提出的運輸安排問題，以裝運貨物的多少（不一定都是整袋）為目標函數，對所得到的不等式組進行求解，所以其結果可以是整數解，也可以是分數解，這也是線性規(guī)劃問題。我們發(fā)現，通過圖解法得到的最優(yōu)解為整數解。最后，教材上的例3是人員安排問題，與上面的幾個例題基本類似，如何進行合理的人員安排，使受服務的老人最多，顯然，得到的最優(yōu)解為唯一的整數解。

一方面，通過對教材所應用的圖解法思路的解讀，筆者發(fā)現，書中的線性規(guī)劃問題所存在的最優(yōu)解具有唯一性和多樣性，但是會不會出現最優(yōu)解不存在的情況呢？另一方面，通過對不等式組所表示的平面陰影區(qū)域（即可行域）進行觀察，筆者結合幾何直觀得到一些概念性的判斷，發(fā)現教材中的4個例題均存在可行域，那么是否存在無可行解或者有無界解（有可行解但無最優(yōu)解）的情況呢？此外，教材中所提出的線性規(guī)劃問題，均是通過建立平面直角坐標系，用圖解法作出可行域，然后平移目標函數尋求最優(yōu)解。然而，在工程實際中，若用圖解法來處理，則費時費力。因此，我們需要探尋更加方便、有效的線性規(guī)劃問題的求解方法。隨著計算機技術的發(fā)展，辦公軟件中的WPS表格可以快速地對線性規(guī)劃問題進行求解和分析，利用WPS表格求解線性規(guī)劃問題不僅可以提高求解的速度，還能有效簡化計算過程。

二、基本概念

1.線性規(guī)劃問題的定義

在一組線性等式或不等式的約束之下，求一個線性函數的最大值或最小值的問題，稱為線性規(guī)劃問題。

2.線性規(guī)劃的數學模型三要素

一是變量，或稱決策變量。它是問題中要確定的未知量，用以表明規(guī)劃中的用數量表示的方案、措施，可由決策者決定和控制。

二是目標函數。它是決策變量的函數，按優(yōu)化目標分別在這個函數前加上max或min。

三是約束條件。指決策變量取值時受到各種資源條件的限制，通常表達為變量的等式或不等式。

如果規(guī)劃問題的數學模型中，決策變量的取值可以是連續(xù)的，目標函數是變量的線性函數，約束條件是變量的線性等式或不等式，則該類規(guī)劃問題的數學模型稱為線性規(guī)劃問題的數學模型。

三、線性規(guī)劃問題的數學模型

1.模型建立的一般步驟

從生活中的實際問題到數學模型的建立，一般有以下三個步驟：根據影響所要達到目的的因素找到決策變量；由決策變量和所在達到目的之間的函數關系確定目標函數；由決策變量所受的限制條件確定決策變量所要滿足的約束條件。

2.數學模型的基本形式

（1）一般形式

max（或min）z=c1x1+c2x2+L=cnxn

其中，aij（i=1，2，Lm；j=1，2，Ln），

bi（i=1，2，Lm）都是常量，xj（j=1，2，Ln）是非負變量。

（2）簡約形式

max（或min）z=

四、兩個變量的線性規(guī)劃模型的應用及求解

1.具體實例

（生產計劃問題）某企業(yè)要生產甲、乙兩種產品，該企業(yè)現有的資源量是：設備18臺時，原材料A4噸，原材料B12噸；已知生產每噸產品所需消耗原材料及每噸產品的獲利如下表。問應如何確定生產計劃，使企業(yè)獲利最多。

由數據列出下表：

表1 資源—產品表

模型建立。設甲、乙產品的產量分別是x1，x2，企業(yè)獲利總額為z。該問題轉化為求x1，x2的值，使其滿足：

并使函數z=3x1+5x2取最大值。

于是，該生產計劃問題的數學模型為：

maxz=3x1+5x2目標函數

約束條件

2.模型求解

（1）圖解法

圖解法適用于求解如下只有兩個變量的線性規(guī)劃問題。

max（或min）z=c1x1+c2x2

滿足約束條件的x1、x2稱為線性規(guī)劃問題的可行解，所有可行解的集合稱為可行域，使目標函數達到最大值（或最小值）的可行解稱為最優(yōu)解。

圖解法的步驟可概括為：在平面上建立直角坐標系；圖示約束條件，找出可行域；圖示目標函數和尋找最優(yōu)解。

下面，用圖解法求解上述線性規(guī)劃問題（見圖1）。

從圖上容易得出本問題有唯一最優(yōu)解：Q2（2，6）。

（2）WPS表格求解

Excel辦公軟件具有強大的表格處理能力，同時也具有強大的線性規(guī)劃問題的求解功能。它對線性和整數規(guī)劃問題的求解，利用的是有界變量單純形法和分支界定法原理。本文所用的Excel環(huán)境為Office2016版的WPS表格，其功能與OfficeExcel相媲美，也可進行規(guī)劃求解運算。其操作步驟比較簡單，可以概括為：

①新建一個WPS表格文件，根據題設條件輸入關于甲、乙產品的相關信息，設置可變單元格（即決策變量）。本題中有兩個決策變量，所以設置兩個。

表2 WPS表格變量

②在WPS表格最上面的菜單欄中找到數據，點擊數據標簽，在中間位置找到模擬分析，再在下拉菜單中找到規(guī)劃求解，點擊后會彈出如圖3的對話框。目標單元格是總利潤計算公式所在的單元格，可變單元格是決策變量，即要求的甲、乙產品的數量，約束為當前資源小于等于資源限制單元格。

圖3 規(guī)劃求解對話框

③勾選“使無約束變量為非負數”（本題是實際問題，要求約束變量是正數），點擊求解按鈕即可直接求出該線性規(guī)劃問題的解。這時計算結果已經顯示出來，見圖4。點擊“保留規(guī)劃求解的解”，可以將解留在表格上，再點擊“確定”即可。

圖4 規(guī)劃求解結果

從表格中可知，上述的線性規(guī)劃問題有唯一最優(yōu)解，最優(yōu)解為生產甲產品2件，生產乙產品6件。若點擊圖4右側的報告，則會分別得到運算結果報告和極限值報告（見圖5），該報告充分說明了運用WPS表格求解線性規(guī)劃問題的可行性和有效性。

針對例題所代表的兩個變量的具體實例，本文給出了圖解法和WPS表格求解法兩種不同的求解方法。但是，一般來說，在實際生活中遇到的線性規(guī)劃問題，需要花大量精力去建立模型。很多情況下，為了盡可能地符合實際情況，需要建立多變量的模型，此時，快速高效地得到模型的最優(yōu)解成為解決問題的關鍵一步。

四、結論

線性規(guī)劃是幫助人們進行數學建模的一種數學方法與手段。線性規(guī)劃問題不僅可以求解經濟、管理、交通運輸，以及軍事等各個方面的優(yōu)化問題，而且在工農業(yè)生產、經濟管理和交通運輸等方面也有極其廣泛的應用。但在其建立數學模型的基礎上，手動計算的繁瑣復雜給線性規(guī)劃的推廣與應用帶來了諸多不便，傳統(tǒng)的解法將會失去作用。然而利用計算機軟件工具會使計算過程大大簡化，這有效推廣了線性規(guī)劃在各行各業(yè)中的應用，有助于應用數學知識解決實際生活問題。

參考文獻：

[1]胡運權.運籌學基礎及應用[M].北京：清華大學出版社，2012.

[2]韓佳伶.利用計算機工具求解運籌學中線性規(guī)劃問題[J].現代交際，2010（10）：43.