MATLAB求解線性規(guī)劃(含整數(shù)規(guī)劃和01規(guī)劃)問(wèn)題.pdf

《MATLAB求解線性規(guī)劃(含整數(shù)規(guī)劃和01規(guī)劃)問(wèn)題.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、MATLAB求解線性規(guī)劃（含整數(shù)規(guī)劃和0-1規(guī)劃）問(wèn)題線性規(guī)劃是數(shù)學(xué)規(guī)劃中的一類(lèi)最簡(jiǎn)單規(guī)劃問(wèn)題，常見(jiàn)的線性規(guī)劃是一個(gè)有約束的，變量范圍為有理數(shù)的線性規(guī)劃。如：maxzx??y712?9xy??4300??4xy??5200s.t??3xy??10300??xy,0?對(duì)于這類(lèi)線性規(guī)劃問(wèn)題，數(shù)學(xué)理論已經(jīng)較為完善，可以有多種方法求解此類(lèi)問(wèn)題。但寫(xiě)這篇文章的目的并不是為了介紹數(shù)學(xué)理論，我們這里主要講解如果利用工具求解這一類(lèi)線性規(guī)劃問(wèn)題。最著名，同時(shí)也是最強(qiáng)大的數(shù)學(xué)最優(yōu)化軟件是LINGO/LINDO軟件包，它能夠求解

2、多種的數(shù)學(xué)規(guī)劃問(wèn)題，同時(shí)還提供了多種的分析能力。但LINGO軟件并不容易上手，同時(shí)，應(yīng)用LINGO的場(chǎng)合一般是大規(guī)模的線性規(guī)劃問(wèn)題，小小的線性規(guī)劃完全可以不使用它。一個(gè)更受科研人員歡迎的數(shù)學(xué)軟件是MATLAB，它以功能強(qiáng)大而稱(chēng)著，并有數(shù)學(xué)軟件中的“航空母艦”之稱(chēng)。我們這里就是要學(xué)習(xí)使用MATLAB軟件求解線性規(guī)劃（含整數(shù)規(guī)劃和0-1規(guī)劃）問(wèn)題。為了使得不熟悉MATLAB的人員也能夠使用MATLAB進(jìn)行線性規(guī)劃問(wèn)題求解，本文將對(duì)MATALB中使用到的函數(shù)和過(guò)程以及結(jié)果進(jìn)行詳細(xì)的分析，最后會(huì)對(duì)每一個(gè)問(wèn)題都給出一

3、個(gè)可以完全“套用”的MATLAB程序。我們首先從上面的線性規(guī)劃問(wèn)題開(kāi)始，為了便于表達(dá)，將上面的式子寫(xiě)成矩陣形式：maxz??7x12y??94??300??????x???45????200s.t???????y??????310??300???xy,0?于是約束就表達(dá)為了一個(gè)Axb?不等式。求解MATLAB線性規(guī)劃時(shí)，最常用的函數(shù)是linprog函數(shù)，下面來(lái)介紹一下這個(gè)函數(shù)的使用。打開(kāi)MATLAB幫助文檔（PS:幫助文檔的內(nèi)容是最全的，只要你的英文過(guò)了專(zhuān)業(yè)8級(jí)），可以看到linprog函數(shù)求解的是具有如下

4、標(biāo)準(zhǔn)形式的線性規(guī)劃：Tminfxx?AX?b?stAeqX.??beq??lb??xub公式中各符號(hào)的意義是自明的，在這里簡(jiǎn)單介紹下，首先MATLAB中求解的是目標(biāo)函數(shù)是最小值的問(wèn)題，但如果我們的目標(biāo)函數(shù)是求最大值，可以通過(guò)對(duì)目標(biāo)函數(shù)中每一項(xiàng)中乘以-1，將求最大值問(wèn)題轉(zhuǎn)化為求最小值問(wèn)題；A，b分別為不等式約束中的系數(shù)矩陣。Aeq和beq分別為等式約束中的系數(shù)矩陣，lb，和ub分別為每個(gè)變量的上下區(qū)間；最后f為目標(biāo)函數(shù)中各變量的系數(shù)矩陣?，F(xiàn)在，是時(shí)候動(dòng)動(dòng)手，使用MATLAB編寫(xiě)代碼求解這個(gè)線性規(guī)劃了。MATL

5、AB代碼如下所示：f=[-7,-12];A=[94;45;310];b=[300;200;300];lb=zeros(2,1);%生成一個(gè)2行1列的全1矩陣[x,fval]=linprog(f,A,b,[],[],lb,[])我們來(lái)解釋下linprog函數(shù)中每參數(shù)的意義，linprog中的一個(gè)原型如下：[x,fval,exitflag]=linprog(f,A,b,Aeq,beq,lb,ub)這7個(gè)參數(shù)的意義和上面f、A、b的意義是一樣的。f為目標(biāo)函數(shù)的系數(shù)矩陣，A為線性規(guī)劃不等式約束的變量系數(shù)矩陣，b為不

6、等式約束的資源數(shù)（如上面的[300;200;300]），這是一個(gè)N行1列的矩陣，N為變量的個(gè)數(shù)。Aeq和beq是相應(yīng)等式約束的變量系數(shù)矩陣和資源數(shù)（很明顯，上面的例子中并沒(méi)有等式約束）。lb和ub分別為保變量的上下區(qū)間。在上面的例子中，x和y和最小值都為0但都無(wú)最大值約束。而linprog的返回值x為求得的各變量的值，這是一個(gè)向量，fval為最優(yōu)化的值，一般是一個(gè)標(biāo)量，exitflag意為函數(shù)的退出標(biāo)志。上面所示的代碼[x,fval]=linprog(f,A,b,[],[],lb,[])中，[]代表不存在或

7、空，因?yàn)樵谏厦娴睦又胁淮嬖诘仁郊s束，所以Aeq和beq的位置為[]。而ub也為空，是因?yàn)樽兞繘](méi)有最大值約束。運(yùn)行上面的程序，行到結(jié)果為：x=20.000024.0000fval=-428.0000解釋為：當(dāng)x=20,y=24時(shí)，可以求得最優(yōu)化的值，最大值為428（因?yàn)檫@里的求目標(biāo)最大值，但MATLAB只能求目標(biāo)函數(shù)最小值，所以對(duì)目標(biāo)函數(shù)進(jìn)行了乘-1處理，所以也要對(duì)最后的結(jié)果乘以-1才是目標(biāo)函數(shù)所求）.上面解決了簡(jiǎn)單的線性規(guī)劃問(wèn)題的求解，線性規(guī)范有兩種比較特殊的情況，即整數(shù)規(guī)劃和0-1整數(shù)規(guī)劃。在之前（不知

8、MATLAB幾之前……），MATLAB是不能直接求解這兩種規(guī)劃的，bintprog函數(shù)可以用來(lái)求0-1整數(shù)規(guī)劃，但求解過(guò)程比較麻煩，而且最新版的MATLAB已經(jīng)遺棄了這個(gè)函數(shù)，同時(shí)提供了一個(gè)比較新的、專(zhuān)用于求解整數(shù)規(guī)劃和0-1整數(shù)規(guī)劃的函數(shù)——intlinprog。intlinprog的一個(gè)原型為：[x,fval,exitflag]=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)該函