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

李昂+++曹迎槐

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

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

線(xiàn)性規(guī)劃圖解法

1、線(xiàn)性規(guī)劃

線(xiàn)性規(guī)劃是對(duì)一組決策變量研究在

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

■

其中c為n維列向量，稱(chēng)為價(jià)格向量或成本向量；■，稱(chēng)為決策變量；b為m維向量，稱(chēng)為右端向量；A為m*n階矩陣，稱(chēng)為約束矩陣。稱(chēng)■為可行域。線(xiàn)性規(guī)劃的可行域?yàn)橥辜ＭǔＮ覀儗⒆畲蠡繕?biāo)函數(shù)的值作為線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)形式（最小化問(wèn)題可看作最大化其負(fù)函數(shù)，即■）。

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

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

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

下面我們用一個(gè)簡(jiǎn)單的二維線(xiàn)性規(guī)劃問(wèn)題說(shuō)明圖解法的求解過(guò)程。

■

■

用圖解法求解：

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

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

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

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

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

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

3.1求出并繪制可行域

根據(jù)線(xiàn)性規(guī)劃的基本理論，一個(gè)n維空間中線(xiàn)性不等式組的解集一定是個(gè)凸多面體（polyhedron）。特別的，如果線(xiàn)性不等式組的解集有界（即對(duì)任意的目標(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è)定理的證明本身并沒(méi)有提供計(jì)算多胞形全部頂點(diǎn)的算法。而Danzig所提出的單純形算法理論，提供了求解這些頂點(diǎn)坐標(biāo)的理論工具。基于多面體頂點(diǎn)的基本定義，可以簡(jiǎn)單的得到結(jié)論：多胞形的頂點(diǎn)一一對(duì)應(yīng)于任一定義在這個(gè)多胞形上線(xiàn)性規(guī)劃的基本可行解。即：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step1：繪制可行域；

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

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

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

這樣在整個(gè)過(guò)程中，step2和step3的運(yùn)算量就壓縮到了兩次同規(guī)模線(xiàn)性規(guī)劃算法的運(yùn)算量，經(jīng)過(guò)實(shí)驗(yàn)對(duì)比，在不改變動(dòng)畫(huà)演示效果的同時(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)的是考慮極大化問(wèn)題，且可行域限制在第一卦限，即■。并且出于簡(jiǎn)化考慮，僅考慮三個(gè)變量和三個(gè)線(xiàn)性不等式約束。

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

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

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

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

總結(jié)與展望

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

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

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

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

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

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

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

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

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