淺談MATLAB在線性規劃教學中的應用

賀明鳳 張艷玲

【摘要】線性規劃是運籌學中研究較早、發展較快、應用較廣泛、方法較成熟的一個重要分支，它已成為現代管理科學研究的重要工具之一，其應用范圍涉及經營規劃制定、生產任務安排、投資決策、生產計劃和庫存控制等多方面。本文討論了在企業的各項管理活動各種限制條件的組合選擇出最合理的一般計算方法，重點探討線性規劃問題的MATLAB程序設計和實現過程，充分體現MATLAB在管理運籌學教學輔助中的優越性。

【關鍵詞】線性規劃 管理活動 MATLAB實現

【中圖分類號】O221.1 【文獻標識碼】A 【文章編號】2095-3089（2018）11-0010-02

線性規劃主要用于解決生產、生活中的人力資源規劃、投資計劃、生產配料、庫存控制、資源利用等問題，它是輔助人們進行科學管理的一種重要的數學模型，研究線性約束條件下線性目標函數的極值問題的數學方法。在教學中，簡單的線性規劃指的是二維變量的線性規劃模型，主要講解用“圖解法”或者“枚舉法”求最優解；當自變量個數n和約束條件個數m較大時，教學側重講解用單純形法求最優解。

方法一、線性規劃的圖解法：

Step 1：確定可行解空間。

Step 2：從可行解空間所有的可行點中確定最優解。

【例1】哈哈農商使用大豆和玉米部分提取物配制兩種特殊飼料A和B，其中，配制每公斤特殊飼料A需使用6公斤大豆和1公斤玉米，配制每公斤特殊飼料B需使用4公斤大豆和2公斤玉米，而大豆和玉米的日最大可用量分別為2400和600公斤。一項市場調查表明，特殊飼料B的日需求量不超過A的日需求量。假設A、B兩種飼料的利潤分別為50和40元/公斤，哈哈農商打算確定最優的飼料A、B的產品混合，如何能使得日總利潤達到最大？

本問題的MATLAB程序為：c=[-50， -40]； A=[6， 4； 1， 2； 1， -1]； b=[2400； 600； 0]；

lb=zeros（2， 1）； [x， fval， exitflag]=linprog（c， A， b， [ ]， [ ]， lb）

方法二、線性規劃的單純形法

【例2】若上述哈哈農商的特殊飼料生產中，使用大豆、玉米和麥麩三種原料部分提取物配制三種特殊飼料A、B和C，其中，配制每公斤特殊飼料A需使用大豆、玉米和麥麩分別為3.5、2、1.5公斤，配制每公斤飼料B需使用大豆、玉米和麥麩分別為1.5、1.2、1.5公斤，配制每公斤新飼料C需使用大豆、玉米和麥麩分別為4.5、1、1公斤，而大豆、玉米和麥麩的日最大可用量分別為1500、750和750公斤。飼料B的日需求量不超過A的日需求量。假設此時A、B、C三種飼料的利潤分別為50、40和80元/公斤，哈哈農商如何確定最優的飼料產品混合，使得日總利潤達到最大？

用單純形法求解例線性規劃問題的MATLAB實現步驟：

Step 1：自定義實現單純形表的MATLAB函數：Simplex_

Tableau。

Step 2：將線性規劃模型標準化，構造初始單純形表。

Step 3：調用自定義函數Simplex_Tableau，求解優化問題[3]。

（1）定義函數Simplex_Tableau

function Simplex_Tableau（mat，numFreeVar）

format short

maxRow=length（mat（：，1））； maxCol=length（mat（1，：））； objEntryExcludingMaxPayOff=mat（maxRow，1：maxCol？鄄2）；

[objEnt bestColToPivot]=min（objEntryExcludingMaxPay

Off）；

while（objEnt<0）

lastColExcludingObjEntry=mat（1：（max

Row？鄄1），maxCol）；ithColExcludingObjEntry=mat（1：（maxRow？鄄1），bestColToPivot）；

for i=1：maxRow？鄄1

if （lastColExcludingObjEntry（i，1）==0&ithColExcludingObj;

Entry（i，1）<=0）

lastColExcludingObjEntry（i，1）=1；

end

end

a=lastColExcludingObjEntry./ithColExcludingObjEntry； [ val bestRowToPivot]=min（a）；

if（val<0）

[s indices]=sort（a）；

if（max（a）>0）

count=1；

while（s（ount）<0）

count=count+1；

end

bestRowToPivot=indices（count）；

end

end

sprintf（'本次迭代的單純形表的樞軸列為第%d列，樞軸行為第%d行'，bestColToPivot，bestRowToPivot）

disp（'本次迭代的單純形表為'）；

[mat，[a；0]] disp（'請按鍵盤上任意一個鍵繼續操作'）；

pause；

if（length（a）==0）

length（a）

return

end

mat=pivot（mat，bestRowToPivot，bestColToPivot）；

objEntryExcludingMaxPayOff=mat（maxRow，1：maxCol？鄄2）；

[objEnt bestColToPivot]=min（objEntryExcludingMaxPay

Off）；

end

sprintf（'本次迭代的單純形表的樞軸列為第%d列，樞軸行為第%d行'，bestColToPivot，bestRowToPivot）

disp（'本次迭代的單純形表為'）；

[mat，[a；0]]

disp（'請按鍵盤上任意一個鍵繼續操作'）；

function newMat=interChange（mat，row1，row2）

temp=mat（row1，：）； mat（row1，：）=mat（row2，：）；

mat（row2，：）=temp； newMat=mat；

function newMat=multiFromRowToRow（mat，fromRow，toRow，multiplier）

rG=mat（fromRow，：）？鄢multiplier； mat（toRow，：）=rG+mat（toRow，：）； newMat=mat；

function newMat=multMat（mat，row，mult）

mat（row，：）=mat（row，：）？鄢mult； newMat=mat；

function newMat=pivot（mat，row，col）

mat（row，：）=mat（row，：）./mat（row，col）；

for r=1：length（mat（：，1））

if（r～=row）

mat=multiFromRowToRow（mat，row，r，？鄄mat（r，col））；

end

end

newMat=mat；

（2）將【例2】的線性規劃模型標準化，構造初始單純形表

mat=[3.5，1.5，4.5，1，0，0，1500；2，1.2，1，0，1，0，750；1，1.5，1，0，0，1，

750；-50，-40，-80，0，0，0，0]

（3）調用自定義函數Simplex_Tableau，求解【例2】的優化問題，此時在MATLAB的命令窗口command window或編輯器editor中輸入：

mat=[3.5，1.5，4.5，1，0，0，1500；2，1.2，1，0，1，0，750；1，1.5，1，0，0，1，

750；-50，-40，-80，0，0，0，0]；numFreeVar=3； Simplex_Tableau（mat， numFreeVar）

其最終的運行結果為：

從運行結果可以看出，例2的線性規劃問題的最優解為x3=214，x5=107，x2=357，其他變量為0，此時哈哈農商的利潤最大值z=31429元。

事實上，線性規劃的圖解法和單純形法的手算步驟較為繁瑣，而且手算速度慢，容易出錯。能用于求解線性規劃優化問題的MATLAB內置函數除linprog外，還有LINDO、LINGO和GLPK軟件等。由上述例2的算法實現過程可以看出，線性規劃單純形法的手工計算過程可以在MATLAB編程中得以實現，簡化了手工計算的繁瑣，提高了計算效率，且自定義的Simplex_Tableau函數可以用于求解所有可以用單純形法求解的線性規劃模型，為學習者進一步應用線性規劃模型提供了方便。

參考文獻：

[1]Hamdy A.Taha著.劉德綱，朱建明等譯.運籌學導論.中國人民大學出版社，2014.

[2]耿修林著.數據、模型與決策，中國人民大學出版社，2013.

[3]吳祁宗，鄭志勇、鄧偉等編著.運籌學與最優化MATLAB編程.機械工業出版社，2009.

[4]薛長虹，于凱著.MATLAB數學實驗.西南交通大學出版社，2014.

[5]雍龍泉. 求解線性規劃的幾種方法. 江西科學，第25卷第2期，2007年4月：203-205.