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

韓雅琦

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

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

一、引言

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

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

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

二、基本概念

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

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

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

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

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

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

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

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

1.模型建立的一般步驟

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

2.數(shù)學模型的基本形式

（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.具體實例

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

由數(shù)據(jù)列出下表：

表1 資源—產(chǎn)品表

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

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

于是，該生產(chǎn)計劃問題的數(shù)學模型為：

maxz=3x1+5x2目標函數(shù)

約束條件

2.模型求解

（1）圖解法

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

max（或min）z=c1x1+c2x2

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

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

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

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

（2）WPS表格求解

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

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

表2 WPS表格變量

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

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

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

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

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

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

四、結論

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

參考文獻：

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

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