賀明鳳 張艷玲

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

【關鍵詞】線性規(guī)劃 管理活動 MATLAB實現(xiàn)

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

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

方法一、線性規(guī)劃的圖解法：

Step 1：確定可行解空間。

Step 2：從可行解空間所有的可行點中確定最優(yōu)解。

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

本問題的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）

方法二、線性規(guī)劃的單純形法

【例2】若上述哈哈農(nóng)商的特殊飼料生產(chǎn)中，使用大豆、玉米和麥麩三種原料部分提取物配制三種特殊飼料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元/公斤，哈哈農(nóng)商如何確定最優(yōu)的飼料產(chǎn)品混合，使得日總利潤達到最大？

用單純形法求解例線性規(guī)劃問題的MATLAB實現(xiàn)步驟：

Step 1：自定義實現(xiàn)單純形表的MATLAB函數(shù)：Simplex_

Tableau。

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

Step 3：調(diào)用自定義函數(shù)Simplex_Tableau，求解優(yōu)化問題[3]。

（1）定義函數(shù)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（'請按鍵盤上任意一個鍵繼續(xù)操作'）；

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（'請按鍵盤上任意一個鍵繼續(xù)操作'）；

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】的線性規(guī)劃模型標準化，構造初始單純形表

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）調(diào)用自定義函數(shù)Simplex_Tableau，求解【例2】的優(yōu)化問題，此時在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）

其最終的運行結(jié)果為：

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

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

參考文獻：

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

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

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

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

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