三維LP圖解法仿真設(shè)計(jì)與實(shí)現(xiàn)

李昂+++曹迎槐

摘 要：線性規(guī)劃（Linear Programming， LP）是運(yùn)籌學(xué)中研究較為充分的一個(gè)重要分支，應(yīng)用范圍十分廣泛，在經(jīng)濟(jì)金融、經(jīng)營管理、工業(yè)生產(chǎn)等方面均有應(yīng)用。它是研究在線性約束條件下線性目標(biāo)函數(shù)極值問題的數(shù)學(xué)理論。目前對線性規(guī)劃求解的方法比較成熟，常用的有單純形法、原始對偶方法和圖解法等。其中圖解法可以清晰直觀地展示求解過程，方便學(xué)習(xí)者掌握線性規(guī)劃的概念和細(xì)節(jié)，以及對對偶原理和靈敏度分析等性質(zhì)有更深地理解。雖然二維圖解法實(shí)現(xiàn)相對簡單，但三維的仿真實(shí)現(xiàn)目前在國內(nèi)外尚屬空白，論文的研究目的即為設(shè)計(jì)三維圖解法仿真模擬程序，使其更好地為教學(xué)工作服務(wù)，進(jìn)一步推動(dòng)線性規(guī)劃求解算法的發(fā)展。

關(guān)鍵詞：線性規(guī)劃 二維線性規(guī)劃 三維線性規(guī)劃 圖解法

線性規(guī)劃圖解法

1、線性規(guī)劃

線性規(guī)劃是對一組決策變量研究在

滿足約束條件的前提下，最大化或最小化目標(biāo)函數(shù)的問題，其中約束條件和目標(biāo)函數(shù)均為線性函數(shù)，如：

■

其中c為n維列向量，稱為價(jià)格向量或成本向量；■，稱為決策變量；b為m維向量，稱為右端向量；A為m*n階矩陣，稱為約束矩陣。稱■為可行域。線性規(guī)劃的可行域?yàn)橥辜?。通常我們將最大化目?biāo)函數(shù)的值作為線性規(guī)劃的標(biāo)準(zhǔn)形式（最小化問題可看作最大化其負(fù)函數(shù)，即■）。

在線性規(guī)劃問題中，決策變量的值稱為一個(gè)解，滿足所有的約束條件的解稱為可行解。使目標(biāo)函數(shù)達(dá)到最大值（或最小值）的可行解稱為最優(yōu)解。這樣，一個(gè)或多個(gè)最優(yōu)解能在整個(gè)由約束條件所確定的可行區(qū)域內(nèi)使目標(biāo)函數(shù)達(dá)到最大值（或最小值）。求解線性規(guī)劃問題的目的就是要找出最優(yōu)解。最優(yōu)解可能出現(xiàn)下列情況之一：①存在著一個(gè)最優(yōu)解；②存在著無窮多個(gè)最優(yōu)解；③不存在最優(yōu)解，這只在兩種情況下發(fā)生，即沒有可行解或各項(xiàng)約束條件不阻止目標(biāo)函數(shù)的值無限增大（或向負(fù)的方向無限增大）。

2、二維線性規(guī)劃圖解法

二維線性規(guī)劃圖解法的求解過程為：求出并繪制可行域（凸多邊形）；找出目標(biāo)函數(shù)下降（上升）方向，并以此為法方向繪制一條與可行域交集非空的初始等值線；沿目標(biāo)函數(shù)下降（上升）方向平移等值線，直至邊界。最終等值線與可行域邊界的交集作為最優(yōu)解集，等值線所代表的目標(biāo)函數(shù)值為最優(yōu)值。

下面我們用一個(gè)簡單的二維線性規(guī)劃問題說明圖解法的求解過程。

■

■

用圖解法求解：

第一步：畫出可行域。以x1與x2為坐標(biāo)軸作直角坐標(biāo)系，根據(jù)不等式的意義求出各半平面的公共部分稱為可行域。

第二步：畫出等值線。目標(biāo)函數(shù)S=2x1+5x2在坐標(biāo)平面表示以S為參數(shù)、以■為斜率的一簇平行直線，即■，它的位置隨著S的變化平行移動(dòng)。位于同一直線上的所有點(diǎn)，都使S具有相同的值，所以該直線稱為“等值線”。任取一個(gè)定點(diǎn)S0便可在坐標(biāo)平面上畫出一條等值線■，如圖1所示。

第三步：求最優(yōu)解。將直線■沿其法線方向向右上方平行移動(dòng)時(shí)，參變量S的值由S0逐步增大。當(dāng)?shù)戎稻€平行移動(dòng)到可行域的最后一個(gè)點(diǎn)B時(shí)，S達(dá)到最大值。此時(shí)由線性方程組可解得B的坐標(biāo)（2，3），故目標(biāo)函數(shù)的最大值S=19。

對于二維的線性規(guī)劃圖解法，我們很容易在直角坐標(biāo)系中實(shí)現(xiàn)，很容易在教學(xué)上演示，但當(dāng)線性規(guī)劃提升至三維乃至更高維空間以后，一些簡單直觀的操作就變得復(fù)雜起來，為了更好的研究和演示三維LP圖解算法，需要分析圖解算法的數(shù)學(xué)本質(zhì)，使用精確的數(shù)學(xué)語言而非自然語言來描述圖解算法。

3、三維線性規(guī)劃圖解法

三維LP圖解算法在步驟上與二維的相似，但在細(xì)節(jié)上較為復(fù)雜，它的具體步驟可以簡述為：

3.1求出并繪制可行域

根據(jù)線性規(guī)劃的基本理論，一個(gè)n維空間中線性不等式組的解集一定是個(gè)凸多面體（polyhedron）。特別的，如果線性不等式組的解集有界（即對任意的目標(biāo)系數(shù)向量■，有■），那么該不等式組的解集是一個(gè)多胞形（polytope）。由于圖解法的特殊性和局限性，在LP圖解法中，我們主要求解的是后者。

N維空間多胞形的定義：Q是n維空間Rn中的多胞形，當(dāng)且僅當(dāng)Q是Rn中有限點(diǎn)集的凸包，i.e. ■。

在二維平面上的圖解法中，繪制可行域其實(shí)就是繪制了這個(gè)多胞形（限制在二維空間中為多邊形）。而繪制多胞形所必需的信息即該多胞形的全部頂點(diǎn)。雖然，在理論上我們已經(jīng)知道有界不等式系統(tǒng)和多胞形的等價(jià)性，但是這個(gè)定理的證明本身并沒有提供計(jì)算多胞形全部頂點(diǎn)的算法。而Danzig所提出的單純形算法理論，提供了求解這些頂點(diǎn)坐標(biāo)的理論工具?；诙嗝骟w頂點(diǎn)的基本定義，可以簡單的得到結(jié)論：多胞形的頂點(diǎn)一一對應(yīng)于任一定義在這個(gè)多胞形上線性規(guī)劃的基本可行解。即：

求解給定線性不等式組對應(yīng)多胞形的頂點(diǎn)問題等價(jià)于求解該多面體上線性規(guī)劃基本可行解。

基于這個(gè)結(jié)論，可以得到如下多項(xiàng)式時(shí)間的多胞形頂點(diǎn)坐標(biāo)求解算法：

Step1：對于給定的線性不等式組Ax≤b，考慮其增廣矩陣，選取一組極大線性無關(guān)行向量組得到與原不等式組等價(jià)的不等式組■；

Step2：選取■全部的極大線性無關(guān)列向量組，對■的每一個(gè)極大線性無關(guān)列向量組■，其實(shí)是一個(gè)滿秩的方陣，■即可求得一個(gè)基本可行解，即一個(gè)頂點(diǎn)的坐標(biāo)。遍歷所有這樣的■，就可以求得全部頂點(diǎn)的坐標(biāo)。

3.2找出目標(biāo)函數(shù)下降（上升）方向，并以此為法方向繪制一條與可行域交集非空的初始等值線

目標(biāo)函數(shù)的下降（上升）方向甚至是梯度方向都是容易求解的，因?yàn)槟繕?biāo)函數(shù)的梯度正是目標(biāo)系數(shù)向量。但是尋找初始與可行域交集非空的等值線則是一件復(fù)雜的事情。事實(shí)上，初始等值線的選取問題等價(jià)于如下問題：

找到■，使得線性不等式組{Ax≤b，cx=c0}解集非空，即尋找一個(gè)原線性規(guī)劃的初始可行解。在運(yùn)籌學(xué)中，兩階段法是用來構(gòu)造求解初始可行解的常用手法。兩階段法簡要如下：endprint

Step1：將線性不等式組Ax≤b化成標(biāo)準(zhǔn)型中的等式組，每一個(gè)不等式添加非負(fù)的一個(gè)人工松弛變量變量；

Step2：構(gòu)造新的目標(biāo)函數(shù)，及最小化人工變量之和；

Step3：求解該線性規(guī)劃，如求得的最優(yōu)解的目標(biāo)函數(shù)值為0，則該最優(yōu)解為原問題的可行解；如目標(biāo)函數(shù)值大于0，則原問題無可行解。

在求得初始可行解x0以后，即可選取cx=cx0為初始等值面。

3.3沿目標(biāo)函數(shù)下降（上升）方向平移等值線（面），直至邊界

在該步驟中，主要的難點(diǎn)在于如何判定等值面是否到達(dá)邊界。一方面，由于移動(dòng)的是等值面，故在圖解算法過程中并不記錄當(dāng)前可行解的信息，所以單純形算法所使用的檢驗(yàn)系數(shù)判定方法難以奏效。另一方面，圖解算法的移動(dòng)行為非常近似于使用連續(xù)優(yōu)化技巧的線性規(guī)劃內(nèi)點(diǎn)算法，所以三維圖解法的邊界判定算法可以借鑒連續(xù)優(yōu)化的判定方法。

在連續(xù)優(yōu)化中，通常并不嚴(yán)格計(jì)算一個(gè)點(diǎn)是否落在可行域邊界上，而是通過完成判定是否落在可行域內(nèi)，然后通過線搜索算法逐漸逼近最值點(diǎn)或邊界點(diǎn)。對應(yīng)到線性規(guī)劃問題上，其實(shí)就是求解如下判定問題：

給定任意■，判斷線性不等式組{Ax≤b，cx≤c0}解集上是否為空。

線性不等式組的解存在問題可以借助Farks引理來轉(zhuǎn)換成線性等式組來處理。

Farks引理：令A(yù)是一個(gè)矩陣，b是一個(gè)向量。那么線性不等式組Ax≤b有解，當(dāng)且僅當(dāng)對于所有滿足yA=0的行向量y，有yb≥0。

事實(shí)上，這里就相當(dāng)于求解出yA=0的全部基本可行解，并逐一判斷是否滿足yb≥0。

到此為止，已經(jīng)把LP圖解法中每一個(gè)子問題推廣到n維空間中（自然包括三維），并對每一個(gè)子問題給出了求解算法，藉此擺脫了原LP圖解法的直觀經(jīng)驗(yàn)性描述而將其上升至了具有一般意義的數(shù)學(xué)算法。

三維LP圖解法的演示算法的改進(jìn)

這一章節(jié)主要研究三維LP圖解的演示動(dòng)畫實(shí)現(xiàn)算法。對于動(dòng)畫演示，重點(diǎn)是體現(xiàn)等值面從初始位置連續(xù)移動(dòng)至可行域邊界的過程。由于在演示動(dòng)畫中，并不會(huì)顯示具體的算法，所以為了提升算法的運(yùn)算速度，我們可以對上文中的圖解算法進(jìn)行簡化和改進(jìn)。

仔細(xì)分析上文中的圖解算法，發(fā)現(xiàn)初始等值面的選?。▋呻A段法的第一階段）以及邊界判定（不等式組解集是否為空）的計(jì)算量都至少等于一次同等規(guī)模的線性規(guī)劃算法的計(jì)算量，對于動(dòng)畫演示來說，其實(shí)有相當(dāng)一部分的運(yùn)算是無意義的，所以針對動(dòng)畫演算，采取如下簡化算法：

Step1：繪制可行域；

Step2：初始點(diǎn)選取。以-c為目標(biāo)系數(shù)，求解線性規(guī)劃，以求得的最優(yōu)值作為初始等值面；

Step3：計(jì)算移動(dòng)終止位置。以c為目標(biāo)系數(shù)，求解線性規(guī)劃，以求得的最優(yōu)值作為等值面終止位置。

Step4：從初始位置開始，直至終止位置連續(xù)繪制等值面移動(dòng)動(dòng)畫。

這樣在整個(gè)過程中，step2和step3的運(yùn)算量就壓縮到了兩次同規(guī)模線性規(guī)劃算法的運(yùn)算量，經(jīng)過實(shí)驗(yàn)對比，在不改變動(dòng)畫演示效果的同時(shí)，可以極大地加快程序的運(yùn)行速度。

基于MATLAB三維LP圖解法演示系統(tǒng)的仿真與實(shí)現(xiàn)

借助MATLAB GUI設(shè)計(jì)并實(shí)現(xiàn)交互式的三維LP圖解法演示系統(tǒng)。

首先，使用edit控件設(shè)計(jì)了參數(shù)讀入界面。在演示系統(tǒng)中，我們默認(rèn)的是考慮極大化問題，且可行域限制在第一卦限，即■。并且出于簡化考慮，僅考慮三個(gè)變量和三個(gè)線性不等式約束。

在讀入線性不等式以后，求出全部基本可行解，即求得可行域多胞形全部頂點(diǎn)坐標(biāo)，通過MATLAB圖形學(xué)工具箱自帶的convhull，通過頂點(diǎn)坐標(biāo)計(jì)算得到多胞形全部側(cè)面的數(shù)據(jù)，再使用mergeCoplanarFaces函數(shù)，將共面的全部小多邊形合并成大的側(cè)面，最終完成可行區(qū)域的繪制。

等值面移動(dòng)動(dòng)畫通過以下方法完成，對于處于最小值和最大值中間狀態(tài)的任意一個(gè)等值面cx=c0，將可行域分割成兩個(gè)部分{ax≤b，cx≥c0}以及{ax≤b，cx≤c0}兩個(gè)相鄰接的多面體，用不同的顏色繪制，以此標(biāo)注等值面。

最后通過drawnow和pause命令生成動(dòng)畫，并實(shí)時(shí)顯示當(dāng)前可行解及其對應(yīng)的目標(biāo)函數(shù)值，當(dāng)動(dòng)畫停止時(shí)所顯示的即為最優(yōu)解和最優(yōu)值。

在此基礎(chǔ)上，通過改變線性規(guī)劃約束中的系數(shù)我們可以實(shí)現(xiàn)三維線性規(guī)劃圖解法的動(dòng)態(tài)展示。

總結(jié)與展望

本文在掌握了二維線性規(guī)劃圖解法的基本原理、方法和步驟的基礎(chǔ)上，對多維線性規(guī)劃問題圖解法的實(shí)現(xiàn)進(jìn)行了理論分析，并且對三維線性規(guī)劃的圖解法利用MATLAB編程，編制了仿真模擬軟件。該程序可以實(shí)現(xiàn)對三維LP模型中各參數(shù)在一定范圍內(nèi)的靈活設(shè)置，將三維線性規(guī)劃問題優(yōu)化的整個(gè)過程通過動(dòng)態(tài)效果展示，界面編排合理，使用靈活方便，作為輔助教學(xué)軟件能夠使學(xué)生對線性規(guī)劃問題的性質(zhì)有更深的理解。同時(shí)基于對多維線性規(guī)劃問題實(shí)質(zhì)的分析，在三維圖解法程序的基礎(chǔ)上我們也很容易擴(kuò)展到三維以上線性規(guī)劃問題的圖解法仿真模擬，未來的研究工作可以考慮設(shè)計(jì)一個(gè)通用程序，通過自由設(shè)置問題優(yōu)化空間的維數(shù)實(shí)現(xiàn)各維數(shù)線性規(guī)劃問題圖解法的動(dòng)態(tài)效果展示。

參考文獻(xiàn)：

[1] Alexander Schrijver， Theory of Linear and Integer Programming， John Wiley and Sons. 1998.

[2] Frederick S. Hillier and Gerald J. Lieberman， Introduction to Operations Research， 8th edition. McGraw-Hill.

[3] 關(guān)玉昆 三維空間線性規(guī)劃問題的圖解法[J]，遼寧大學(xué)學(xué)報(bào)， 1999，18卷1期。

[4] 鄧先禮，最優(yōu)化技術(shù)，重慶大學(xué)出版社，1998.

[5] 申卯興，許進(jìn) 求解線性規(guī)劃的單純形法的直接方法，計(jì)算機(jī)工程與應(yīng)用，2007，30期，p94-96.

[6] 燕子宗，費(fèi)浦生，萬仲平. 線性規(guī)劃的單純形法及其發(fā)展，計(jì)算數(shù)學(xué)，2007，1期.

[7] JH. Mathews， KD. Fink. Numerical methods using MATLAB. 1999.

[8] 張志通. MATLAB教程，北京航空航天大學(xué)出版社，2006.

[9] 錢俊，吳金洪，程茗. 線性規(guī)劃問題的MATLAB求解. 科技創(chuàng)新導(dǎo)報(bào). 2011，25期，p158.

[10] 龍林川， 淺談二變量線性規(guī)劃問題的圖解法. 科技信息，2012，25期，p138-139.

（作者單位：浙江省寧波市公安海警學(xué)院）endprint