Matlab在線性規(guī)劃中的使用

1、 優(yōu)化問題及其數(shù)學(xué)模型假設(shè)有一個(gè)問題，它有幾個(gè)因素來決定，當(dāng)這些因素處于某個(gè)狀態(tài)時(shí)，可以使問題得到我們最想要的結(jié)果。優(yōu)化問題就是尋求這個(gè)狀態(tài)的過程。例如：某工廠生產(chǎn)A，B兩種產(chǎn)品，所用原料均為甲、乙、丙三種；生產(chǎn)一件產(chǎn)品所需原料和所獲利潤以及庫存原料情況如下所示：原料甲原料乙原料丙利潤(元)產(chǎn)品A8447000產(chǎn)品B68610000庫存原料380300220問題：在該廠只有庫存原料甲380單位，原料乙300單位，原料丙220單位的情況下如何安排A，B兩種產(chǎn)品的生產(chǎn)數(shù)量可以獲得最大的利潤？設(shè)生產(chǎn)A中產(chǎn)品件，生產(chǎn)B中產(chǎn)品件，z為所獲得的利潤，于是有關(guān)系式： 我們稱它為目標(biāo)函數(shù)。生產(chǎn)的條件我們可以表

2、示為： 我們把上面的不等式稱為約束條件。產(chǎn)品A的產(chǎn)量和B的產(chǎn)量是優(yōu)化問題的變量。在滿足約束條件的前提下使目標(biāo)函數(shù)得到最優(yōu)的值成為最優(yōu)解。根據(jù)以上定義，也可以說優(yōu)化運(yùn)算是通過某種計(jì)算尋求最優(yōu)解的過程。以上這個(gè)用等式或不等式來表達(dá)我們要解決的問題的過程就是優(yōu)化問題的建模過程。我們平時(shí)遇到的問題常常不是上面的這幾個(gè)數(shù)學(xué)表達(dá)式就能表達(dá)得清清楚楚的，但是建立像上面類似的數(shù)學(xué)模型卻是優(yōu)化求解的第一步。優(yōu)化問題常常表現(xiàn)為在多約束條件下求某一函數(shù)的極值問題，例如上面的這個(gè)例子。Matlab有一個(gè)優(yōu)化工具箱，可以幫助我們方便的解決好這類問題。 優(yōu)化工具箱Matlab的優(yōu)化工具箱有一些對(duì)普通非線性函數(shù)求解最小化或

3、最大化求極值的函數(shù)組成，另外還包括一些解決諸如線性規(guī)劃等標(biāo)準(zhǔn)矩陣問題的函數(shù)。所有的優(yōu)化函數(shù)都是用Matlab語言編寫的m文件，我們可以通過在命令窗口里輸入type function_name來查看這些函數(shù)。優(yōu)化工具箱的優(yōu)化功能包括： 求無約束非線性最小化； 求有約束非線性最小化； 二次和線性規(guī)劃問題； 非線性最小二乘法和曲線擬合問題； 非線性等式的求解； 約束線性最小二乘法； 稀疏和結(jié)構(gòu)化大尺度問題。工具箱中求非線性函數(shù)極小值的命令函數(shù)如下表所示：問題類型函數(shù)用法含義線性規(guī)劃問題x=linprog(f,A,b)在條件下求無限定標(biāo)量問題x=fminunc(f,x)，x為標(biāo)量無限定條件矩陣問題x=

4、fminunc(f,x)，X為矩陣有限定條件x=fmincon(fg,x)，條件為 目標(biāo)條件x=fgoalattain(f,x,goal,w)，條件為最小最大極值x=fminmax(fg,x)，條件為 非線性二次平方極值x=lsqnonneg(f,x)非線性方程x=fsolve(f,x)半無窮條件x=fsemimf(ft,n,x)，條件為任意給定w值上面表中函數(shù)可以對(duì)標(biāo)量、向量和矩陣進(jìn)行運(yùn)算；我們一般用大寫字母表示矩陣，用小寫字母表示向量和標(biāo)量。在Matlab中用符號(hào)“*”表示矩陣的元素乘。當(dāng)然，上述運(yùn)算是在定義好了一個(gè)最小化函數(shù)的前提下進(jìn)行的，也就是說要先建立數(shù)學(xué)模型。注：Matlab自身提

5、供了一個(gè)優(yōu)化演示例如，其命令為optdemo。 線性規(guī)劃問題前面6-1中所舉的例子就是一個(gè)典型的線性規(guī)劃問題。線性規(guī)劃數(shù)學(xué)模型的特點(diǎn)是：在線性不等式或線性等式的約束條件下，求能滿足目標(biāo)函數(shù)取得最大值或最小值的一組變量的值，目標(biāo)函數(shù)也要求是線性函數(shù)。命令：linprog格式：X= linprog(f,A,b)X,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,Beq,LB,UB,X0,options)功能：計(jì)算使目標(biāo)函數(shù)取得最小值的一組變量的值。說明：這里f為由目標(biāo)函數(shù)的系數(shù)組成的向量。A是一個(gè)矩陣，b是一個(gè)向量，A和b構(gòu)成了線性規(guī)劃的不等式約束條件。

6、X是一個(gè)向量，為返回的滿足目標(biāo)函數(shù)取得極小值的一組變量的值。Aeq是一個(gè)矩陣，Beq是一個(gè)向量，Aeq和Beq構(gòu)成了線性規(guī)劃的等式約束條件。LB和UB分別是變量的下界和上界約束。X0是給出的變量的初始值。Exitflag、output、lambda的意義我們放在后面的例如中給出解釋。注：如果要計(jì)算的是使目標(biāo)函數(shù)取得最大值的情況，則通過轉(zhuǎn)化為計(jì)算的最小值的方法來實(shí)現(xiàn)。例6-1 對(duì)前面6-1中所舉的例子進(jìn)行線性規(guī)劃問題的計(jì)算。分析： 優(yōu)化的目標(biāo)為使函數(shù)取得最大值，也就是使函數(shù)取得最小值，故線性規(guī)劃目標(biāo)函數(shù)的系數(shù)組成的向量為； 約束條件為三個(gè)不等式：，所以由不等式約束條件的系數(shù)構(gòu)成的矩陣為：A=8,

7、6;4,8;4,6，而b=380,300,220。程序：clearf=-7000,10000;A=8,6;4,8;4,6;b=380,300,220;X,fval=linprog(f,A,b)運(yùn)行結(jié)果：Optimization terminated.X =fval = -3.8000e+005注： 優(yōu)化的結(jié)果，目標(biāo)函數(shù)值fval = -3.8000e+005，由于我們的目標(biāo)函數(shù)是-f(x)，所以最后應(yīng)該是maxf(x)=3.8000e+005。 在優(yōu)化問題中，涉及到優(yōu)化結(jié)果只能取整數(shù)值的情況時(shí)，如果我們對(duì)優(yōu)化結(jié)果隨意的進(jìn)行取整，可能導(dǎo)致最后結(jié)果不是最優(yōu)，這一點(diǎn)需要注意。例2 中國石油天然氣集團(tuán)

8、公司天然氣的運(yùn)送案例分析中國石油天然氣集團(tuán)公司在東海有一個(gè)油氣田節(jié)點(diǎn)，該公司要將開采的天然氣通過管道運(yùn)送到上海的一個(gè)配送中心節(jié)點(diǎn)，天然氣在運(yùn)送途中要經(jīng)過兩次管道換接點(diǎn)節(jié)點(diǎn)B和C，換接前后管道長短不一，而且不同的管道對(duì)應(yīng)不同的單位流量運(yùn)費(fèi)。如圖，天然氣運(yùn)送的管道網(wǎng)絡(luò)圖，弧線表示管道，弧旁的數(shù)字為,其中表示管道上的單位流量費(fèi)用，表示管道上的容量。公司希望選擇一個(gè)經(jīng)濟(jì)實(shí)惠的管道路線運(yùn)送天然氣，既運(yùn)送最多的天然氣又使總的運(yùn)輸費(fèi)用最少。(1,4)(3,5)(1,1)(4,2)(2,1)3,3(1,3)(4,2)(2,5這是一個(gè)最小費(fèi)用最大流問題。為了建立該問題的數(shù)學(xué)模型，首先設(shè)每段管道上的流量作為問題的

9、決策變量，分別記為，稱分段流量。從始點(diǎn)處，可得流量函數(shù),且有約束條件：1；2；3；一方面要使流量最大，另一方面要是費(fèi)用最小。所以分兩部分計(jì)算，先求出最大流，再求最小費(fèi)用最大流。對(duì)應(yīng)matlab程序如下：clear f=-1,1,0,0,0,0,0,0,0; aeq=1,0,-1,-1,1,0,0,0,0;0,1,1,0,0,-1,0,0,0;0,0,0,1,0,0,1,-1,0;0,0,0,0,-1,1,-1,0,-1; beq=zeros(4,1); lb=zeros(9,1); ub=4;5;1;3;1;2;3;5;2; x,fval=linprog(f,aeq,beq,lb,ub)%求出

10、最大流 f1=1,3,1,3,2,4,1,2,4;aeq1= 1,1,0,0,0,0,0,0,0;1,0,-1,-1,1,0,0,0,0;0,1,1,0,0,-1,0,0,0;0,0,0,1,0,0,1,-1,0;0,0,0,0,-1,1,-1,0,-1;beq1=-fval;beq;z,fvall=linprog(f1,aeq1,beq1,lb,ub)程序執(zhí)行后，結(jié)果為：z =fvall =練習(xí)：某快餐店一周中每天需要不同數(shù)目的雇員，設(shè)周一至少人，周二至少人，周三至少人，周四至少人，周五至少人，周六至少人，周日至少人，又規(guī)定雇員需連續(xù)工作5天，每人每天的工資為C元。問快餐店怎樣聘用雇員才能滿足需求，又能使總聘用費(fèi)用最少。提示：由于每個(gè)雇員需連續(xù)工作5天，故快餐店聘用的總?cè)藬?shù)不一定是每天聘用人數(shù)之和。我們定義周一開始工作的