三維LP圖解法仿真設計與實現

李昂+++曹迎槐

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

關鍵詞：線性規劃 二維線性規劃 三維線性規劃 圖解法

線性規劃圖解法

1、線性規劃

線性規劃是對一組決策變量研究在

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

■

其中c為n維列向量，稱為價格向量或成本向量；■，稱為決策變量；b為m維向量，稱為右端向量；A為m*n階矩陣，稱為約束矩陣。稱■為可行域。線性規劃的可行域為凸集。通常我們將最大化目標函數的值作為線性規劃的標準形式（最小化問題可看作最大化其負函數，即■）。

在線性規劃問題中，決策變量的值稱為一個解，滿足所有的約束條件的解稱為可行解。使目標函數達到最大值（或最小值）的可行解稱為最優解。這樣，一個或多個最優解能在整個由約束條件所確定的可行區域內使目標函數達到最大值（或最小值）。求解線性規劃問題的目的就是要找出最優解。最優解可能出現下列情況之一：①存在著一個最優解；②存在著無窮多個最優解；③不存在最優解，這只在兩種情況下發生，即沒有可行解或各項約束條件不阻止目標函數的值無限增大（或向負的方向無限增大）。

2、二維線性規劃圖解法

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

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

■

■

用圖解法求解：

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

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

第三步：求最優解。將直線■沿其法線方向向右上方平行移動時，參變量S的值由S0逐步增大。當等值線平行移動到可行域的最后一個點B時，S達到最大值。此時由線性方程組可解得B的坐標（2，3），故目標函數的最大值S=19。

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

3、三維線性規劃圖解法

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

3.1求出并繪制可行域

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

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

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

求解給定線性不等式組對應多胞形的頂點問題等價于求解該多面體上線性規劃基本可行解。

基于這個結論，可以得到如下多項式時間的多胞形頂點坐標求解算法：

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

Step2：選取■全部的極大線性無關列向量組，對■的每一個極大線性無關列向量組■，其實是一個滿秩的方陣，■即可求得一個基本可行解，即一個頂點的坐標。遍歷所有這樣的■，就可以求得全部頂點的坐標。

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

目標函數的下降（上升）方向甚至是梯度方向都是容易求解的，因為目標函數的梯度正是目標系數向量。但是尋找初始與可行域交集非空的等值線則是一件復雜的事情。事實上，初始等值線的選取問題等價于如下問題：

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

Step1：將線性不等式組Ax≤b化成標準型中的等式組，每一個不等式添加非負的一個人工松弛變量變量；

Step2：構造新的目標函數，及最小化人工變量之和；

Step3：求解該線性規劃，如求得的最優解的目標函數值為0，則該最優解為原問題的可行解；如目標函數值大于0，則原問題無可行解。

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

3.3沿目標函數下降（上升）方向平移等值線（面），直至邊界

在該步驟中，主要的難點在于如何判定等值面是否到達邊界。一方面，由于移動的是等值面，故在圖解算法過程中并不記錄當前可行解的信息，所以單純形算法所使用的檢驗系數判定方法難以奏效。另一方面，圖解算法的移動行為非常近似于使用連續優化技巧的線性規劃內點算法，所以三維圖解法的邊界判定算法可以借鑒連續優化的判定方法。

在連續優化中，通常并不嚴格計算一個點是否落在可行域邊界上，而是通過完成判定是否落在可行域內，然后通過線搜索算法逐漸逼近最值點或邊界點。對應到線性規劃問題上，其實就是求解如下判定問題：

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

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

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

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

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

三維LP圖解法的演示算法的改進

這一章節主要研究三維LP圖解的演示動畫實現算法。對于動畫演示，重點是體現等值面從初始位置連續移動至可行域邊界的過程。由于在演示動畫中，并不會顯示具體的算法，所以為了提升算法的運算速度，我們可以對上文中的圖解算法進行簡化和改進。

仔細分析上文中的圖解算法，發現初始等值面的選取（兩階段法的第一階段）以及邊界判定（不等式組解集是否為空）的計算量都至少等于一次同等規模的線性規劃算法的計算量，對于動畫演示來說，其實有相當一部分的運算是無意義的，所以針對動畫演算，采取如下簡化算法：

Step1：繪制可行域；

Step2：初始點選取。以-c為目標系數，求解線性規劃，以求得的最優值作為初始等值面；

Step3：計算移動終止位置。以c為目標系數，求解線性規劃，以求得的最優值作為等值面終止位置。

Step4：從初始位置開始，直至終止位置連續繪制等值面移動動畫。

這樣在整個過程中，step2和step3的運算量就壓縮到了兩次同規模線性規劃算法的運算量，經過實驗對比，在不改變動畫演示效果的同時，可以極大地加快程序的運行速度。

基于MATLAB三維LP圖解法演示系統的仿真與實現

借助MATLAB GUI設計并實現交互式的三維LP圖解法演示系統。

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

在讀入線性不等式以后，求出全部基本可行解，即求得可行域多胞形全部頂點坐標，通過MATLAB圖形學工具箱自帶的convhull，通過頂點坐標計算得到多胞形全部側面的數據，再使用mergeCoplanarFaces函數，將共面的全部小多邊形合并成大的側面，最終完成可行區域的繪制。

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

最后通過drawnow和pause命令生成動畫，并實時顯示當前可行解及其對應的目標函數值，當動畫停止時所顯示的即為最優解和最優值。

在此基礎上，通過改變線性規劃約束中的系數我們可以實現三維線性規劃圖解法的動態展示。

總結與展望

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

參考文獻：

[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] 關玉昆 三維空間線性規劃問題的圖解法[J]，遼寧大學學報， 1999，18卷1期。

[4] 鄧先禮，最優化技術，重慶大學出版社，1998.

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

[6] 燕子宗，費浦生，萬仲平. 線性規劃的單純形法及其發展，計算數學，2007，1期.

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

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

[9] 錢俊，吳金洪，程茗. 線性規劃問題的MATLAB求解. 科技創新導報. 2011，25期，p158.

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

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