賀明鳳 張艷玲

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

【關(guān)鍵詞】線性規(guī)劃 管理活動(dòng) MATLAB實(shí)現(xiàn)

【中圖分類號(hào)】O221.1 【文獻(xiàn)標(biāo)識(shí)碼】A 【文章編號(hào)】2095-3089（2018）11-0010-02

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

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

Step 1：確定可行解空間。

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

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

本問(wèn)題的MATLAB程序?yàn)椋篶=[-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的日需求量不超過(guò)A的日需求量。假設(shè)此時(shí)A、B、C三種飼料的利潤(rùn)分別為50、40和80元/公斤，哈哈農(nóng)商如何確定最優(yōu)的飼料產(chǎn)品混合，使得日總利潤(rùn)達(dá)到最大？

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

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

Tableau。

Step 2：將線性規(guī)劃模型標(biāo)準(zhǔn)化，構(gòu)造初始單純形表。

Step 3：調(diào)用自定義函數(shù)Simplex_Tableau，求解優(yōu)化問(wèn)題[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（'請(qǐng)按鍵盤上任意一個(gè)鍵繼續(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（'請(qǐng)按鍵盤上任意一個(gè)鍵繼續(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ī)劃模型標(biāo)準(zhǔn)化，構(gòu)造初始單純形表

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)化問(wèn)題，此時(shí)在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）

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

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

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

參考文獻(xiàn)：

[1]Hamdy A.Taha著.劉德綱，朱建明等譯.運(yùn)籌學(xué)導(dǎo)論.中國(guó)人民大學(xué)出版社，2014.

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

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

[4]薛長(zhǎng)虹，于凱著.MATLAB數(shù)學(xué)實(shí)驗(yàn).西南交通大學(xué)出版社，2014.

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