運(yùn)用Lingo和Matlab軟件求解線性規(guī)劃問(wèn)題的比較研究

摘要：本文就一個(gè)給定的線性規(guī)劃模型，通過(guò)介紹優(yōu)化軟件Lingo和科學(xué)計(jì)算軟件Matlab中求解線性規(guī)劃問(wèn)題的命令和函數(shù)，指出Lingo軟件在求解線性規(guī)劃問(wèn)題上占有一定優(yōu)勢(shì)。

關(guān)鍵詞：線性規(guī)劃 Lingo軟件 Matlab軟件 最優(yōu)解

線性規(guī)劃由前蘇聯(lián)經(jīng)濟(jì)學(xué)家康托洛維奇提出，它主要研究的是在線性等式（或不等式）約束條件下，使某一線性目標(biāo)函數(shù)取得最大值（或最小值）的問(wèn)題。隨著計(jì)算機(jī)技術(shù)的發(fā)展，借助軟件可以快速對(duì)線性規(guī)劃問(wèn)題進(jìn)行求解和分析。目前，能夠求解規(guī)劃問(wèn)題的數(shù)學(xué)軟件比較多，常見(jiàn)的有優(yōu)化軟件Lingo和科學(xué)計(jì)算軟件Matlab。

本文以如下線性規(guī)劃為例，分別利用這二種軟件來(lái)求解，并就它們?cè)谇蠼饩€性規(guī)劃上的差異進(jìn)行對(duì)比分析。

minz=10.8x11+10.95x12+11.1x13+11.25x14+11.1x22+

11.25x23+11.4x24+11x33+11.15x34+11.3x44；

s.t.x11+x12+x13+x14<25；x22+x23+x24<35；x33+x34<30；x44<10；x11=10；x12+x22=15；x13+x23+x33=25；x14+x24+x34+x44=20。

1 Lingo求解線性規(guī)劃

1.1 Lingo軟件簡(jiǎn)介 Lindo和Lingo是美國(guó) Lindo系統(tǒng)公司開(kāi)發(fā)的一套專門(mén)用于求解最優(yōu)化問(wèn)題的軟件包。Lindo 用于求解線性規(guī)劃和二次規(guī)劃問(wèn)題，Lingo除了具有Lindo的全部功能外，還可以用于求解非線性規(guī)劃問(wèn)題，也可以用于一些線性和非線性方程（組）的求解等等。

1.2 Lingo中求解線性規(guī)劃的命令介紹 按照Lingo語(yǔ)法規(guī)則，要求計(jì)算的模型首行以Max 或Min 開(kāi)始，并按線性規(guī)劃問(wèn)題的自然形式錄入，程序最后以end結(jié)束.程序中，不區(qū)分變量中的大小寫(xiě)字符，注釋使用“！”來(lái)引導(dǎo)，約束條件中的“≥”與“≤”以“>”“<”來(lái)替換。Lingo中矩陣數(shù)據(jù)是逐行存儲(chǔ)的，另外，由于Lingo中已假設(shè)所有變量非負(fù)，故無(wú)需再錄入非負(fù)約束.

1.3 Lingo求解上述線性規(guī)劃的具體實(shí)現(xiàn) Lingo程序1：

min=10.8*x11+10.95*x12+11.1*x13+11.25*x14+11.1*

x22+11.25*x23+11.4*x24+11*x33+11.15*x34+11.3*x44；

x11+x12+x13+x14<25；

x22+x23+x24<35；

x33+x34<30；

x44<10；

x11=10；

x12+x22=15；

x13+x23+x33=25；

x14+x24+x34+x44=20。

運(yùn)行后，得（Lingo的輸出結(jié)果很豐富，但由于版面限制，此處僅摘取部分）：

Objective value： 773.0000

Variable Value

X11 10.00000

X12 15.00000

X13 0.000000

X14 0.000000

X22 0.000000

X23 0.000000

X24 5.000000

X33 25.00000

X34 5.000000

X44 10.00000

即最優(yōu)解為x11=10、x12=15、x24=5、x33=25、x34=5、x44=10，其余都是0，最優(yōu)值為773.

下面介紹運(yùn)用Lingo中提供的集合定義形式來(lái)重新編寫(xiě)程序.

Lingo程序2：

sets：

warehouse/1..4/： capacity；

vendors/1..4/： demand；

links（warehouses，vendors）： c，x；

endsets

min=@sum（links： c*x）；！目標(biāo)函數(shù)；

@for（warehouses（i）：@sum（vendors（j）： x（i，j））<=

capacity（i））；

@for（vendors（j）：@sum（warehouses（i）： x（i，j））=

demand（j））；

data： ！變量的賦值；

capacity=25 35 30 10；

demand=10 15 25 20；

c=10.8 10.95 11.1 11.25

0 11.1 11.25 11.4

0 0 11 11.15

0 0 0 11.3；

x=，，，，0，，，，0，0，，，0，0，0，；！x21=x31=x32=x41=x42=x43=0；

enddata

end

運(yùn)行后，得（僅摘取部分輸出結(jié)果）：

X（1，1） 10.00000

X（1，2） 15.00000

X（1，3） 0.000000

X（1，4） 0.000000

X（2，1） 0.000000

X（2，2） 0.000000

X（2，3） 0.000000

X（2，4） 5.000000

X（3，1） 0.000000

X（3，2） 0.000000

X（3，3） 25.00000

X（3，4） 5.000000

X（4，1） 0.000000

X（4，2） 0.000000

X（4，3） 0.000000

X（4，4） 10.00000

顯然最優(yōu)解同上，只是輸出格式不同而已。

2 Matlab求解線性規(guī)劃

2.1 Matlab軟件簡(jiǎn)介 目前，Matlab提供了四十多個(gè)工具箱，這些工具箱專門(mén)針對(duì)某些具體應(yīng)用領(lǐng)域。Matlab優(yōu)化工具箱中提供了linprog函數(shù)來(lái)求解線性規(guī)劃問(wèn)題。

2.2 Matlab求解線性規(guī)劃的命令介紹 Matlab中一般使用“[ ]”、 “，”或空格以及“；”來(lái)創(chuàng)建數(shù)組，“[ ]”中給出數(shù)組的所有元素，同行間的元素用“，”或者空格隔開(kāi)，不同行之間用分號(hào)“；”隔開(kāi)，并且用符號(hào)“■”置于矩陣右上角表示矩陣的轉(zhuǎn)置運(yùn)算。

Linprog函數(shù)的常見(jiàn)形式如下：

形式1：X=linprog（f，A，b）

用于求解目標(biāo)函數(shù)為Minf′*x ，約束條件為A*x≤b的線性規(guī)劃問(wèn)題。其中X表示最優(yōu)解，f 表示價(jià)值列向量，A表示約束不等式中的系數(shù)矩陣（二維數(shù)組），b（列向量）表示約束不等式中右端資源常數(shù)向量。

形式2：[X，fval]=Linprog（c，A，b，Aeq，beq）

相比較上面的問(wèn)題，增加了等式約束，即Aeq*x=beq。其中X、c、A、b含義同上，fval表示最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值。若沒(méi)有不等式存在，則令A(yù)=[]、b=[].

形式3：[X，fval]=Linprog（c，A，b，Aeq，beq，vlb，vub）

增加了決策變量的上下界約束，即Vlb≤x≤vub，其中vlb、vub分別以列向量形式存儲(chǔ)。如果沒(méi)有不等式約束，令A(yù)=[]和b=[]；若沒(méi)有等式約束，則令A(yù)eq=[]、beq=[].

2.3 Matlab求解上述線性規(guī)劃的具體實(shí)現(xiàn)

Matlab程序如下：

>> clear

c=[10.8 10.95 11.1 11.25；0 11.1 11.25 11.4；0 0 11 11.15；0 0 0 11.3]；

A=[1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0

0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1]；

b=[25；35；30；10]；

Aeq=[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1]；

beq=[10；15；25；20]；

f=c（：）； %把f變成列向量

vlb=zeros（16，1）； %確定決策變量的下界

vub=[inf 0 0 0 inf inf 0 0 inf inf inf 0 inf inf inf inf]；

%通過(guò)取上下界值都為0，保證決策變量x21=x31=x41

=x32=x42=x43=0

[x，fval]=linprog（f，A，b，Aeq，beq，vlb，vub）

運(yùn)行后，得結(jié)果：

x =10.0000

0

0

0

12.5784

2.4216

0

0

1.6173

1.5529

21.8299

0

0.8044

1.0255

8.1701

10.0000

fval =773.0000

即最優(yōu)解為x11=10，x12=12.5784，x13=1.6173，x14=

0.8044，x22=2.4216，x23=1.5529，x24=1.0255，x33=21.8299，x34=8.1701，x44=10，最優(yōu)值為773。

3 小結(jié)

通過(guò)以上介紹，我們發(fā)現(xiàn)不管是使用Lingo還是Matlab軟件，計(jì)算的最優(yōu)值都是一樣的，但最優(yōu)解有些差異，而且求解的程序在形式上有較大差異。Lingo程序中，第一種方法的結(jié)構(gòu)形式簡(jiǎn)單，符合原規(guī)劃問(wèn)題中的書(shū)寫(xiě)習(xí)慣，初學(xué)者容易上手，但可拓展性不強(qiáng)，而且對(duì)于規(guī)模較大、變量數(shù)較多的問(wèn)題編程比較費(fèi)時(shí)費(fèi)力，對(duì)于非線性規(guī)劃問(wèn)題使用更是不便。第二種方法使用集合的概念，程序易于擴(kuò)展，尤其在求解規(guī)模較大的問(wèn)題時(shí)優(yōu)勢(shì)明顯。相比較而言，Matlab中的矩陣（二維數(shù)組）的輸入規(guī)律稍難理解些，而且輸出結(jié)果也不如Lingo那么直接明了。另外，linprog命令只能求一般的線性規(guī)劃，而不能求整數(shù)線性規(guī)劃，因?yàn)镸atlab沒(méi)有內(nèi)置命令求解整數(shù)線性規(guī)劃，如果要解，需要自己編算法實(shí)現(xiàn)。這種算法的編制，對(duì)普通的軟件使用者來(lái)說(shuō)受到一定的約束。總的來(lái)說(shuō)，盡管Matlab功能很強(qiáng)大，但Lingo在求解線性規(guī)劃模型的計(jì)算上還是相對(duì)簡(jiǎn)便的，而且可以得到內(nèi)容豐富的結(jié)果輸出，在關(guān)于線性規(guī)劃的實(shí)際問(wèn)題分析中Lingo應(yīng)用得更為多些。

參考文獻(xiàn)：

[1]田維.用Matlab與Lindo求解線性規(guī)劃[J].德宏師范高等專科學(xué)校學(xué)報(bào)，2006，1：107-111.

[2]滕飛.應(yīng)用SAS/OR與LINGO求解優(yōu)化問(wèn)題的比較研究[J].吉林師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，3：36-38.

[3]葉向.實(shí)用運(yùn)籌學(xué)[M].北京：中國(guó)人民大學(xué)出版社，2006.

[4]王正林，劉明.精通MATALB7[M].北京：電子工業(yè)出版社，2007.