MATLAB求解線性規(guī)劃問題

1、第七章 最優(yōu)化計算方法,一、實驗目的：,第一節(jié) 線性方程組的應用,1、了解線性規(guī)劃問題及可行解、最優(yōu)解的概念 ；,2、掌握Matlab軟件關(guān)于求解線性規(guī)劃的語句和方法。,二、實驗原理和方法：,在生活實踐中，很多重要的實際問題都是線性的（至少能 夠用線性函數(shù)很好的近似表示），所以我們一般把這些問 題化為線性的目標函數(shù)和約束條件進行分析，通常將目標 函數(shù)和約束都是線性表達式的規(guī)劃問題稱為線性規(guī)劃 。,它的一般形式是：,也可以用矩陣形式來表示：,線性規(guī)劃的可行解是滿足約束條件的解；線性規(guī)劃的最優(yōu)解是使目標函數(shù)達到最優(yōu)的可行解。,線性規(guī)劃關(guān)于解的情況可以是：,1、無可行解，即不存在滿足約束條件的解；,

2、2、有唯一最優(yōu)解，即在可行解中有唯一的最有解；,4、有可行解，但由于目標函數(shù)值無界而無最優(yōu)解。,3、有無窮最優(yōu)解，即在可行解中有無窮個解都可使目 標函數(shù)達到最優(yōu)；,一般求解線性規(guī)劃的常用方法是單純形法和改進 的單純形法，這類方法的基本思路是先求得一個可行 解，檢驗是否為最優(yōu)解；若不是，可用迭代的方法找 到另一個更優(yōu)的可行解，經(jīng)過有限次迭代后，可以找 到可行解中的最優(yōu)解或者判定無最優(yōu)解。,三、內(nèi)容與步驟：,在Matlab優(yōu)化工具箱中，linprog函數(shù)是使用單純形法求解 下述線性規(guī)劃問題的函數(shù)。,它的命令格式為：,其中：A為約束條件矩陣，b,c分別為目標函數(shù)的系數(shù)向量和 約束條件中最右邊的數(shù)值向

3、量；也可設置解向量的上界vlb和 下界vub，即解向量必須滿足vlb=x=vub；還可預先設置 初始解向量x0。 如沒有不等式，而只有等式時，A= ,b= ; 輸出的結(jié)果：x表示最優(yōu)解向量；fval表示最優(yōu)值。,【例 1】,求解線性規(guī)劃問題：,解：考慮到linprog函數(shù)只解決形如 的線性規(guī)劃。所以先要將線性規(guī)劃 變?yōu)槿缦滦问剑?然后建立M文件如下：,c=-3;1;1;A=1 -2 1;4 -1 -2;b=11;-3; aeq=2 0 -1;beq=-1;vlb=0;0;0; x,fval=linprog(c,A,b,aeq,beq,vlb),Matlab程序： ch701.m,以ch701作

4、為文件名保存此M文件后，在命令窗口 輸入ch701后即可得到結(jié)果：,x = 4.0000 1.0000 9.0000,同時返回fval=-2,對應到原來的線性規(guī)劃中即知目標函數(shù)的最大值為2，此時 x1=4,x2=1,x3=9。,第二節(jié) 無約束規(guī)劃計算方法,一、實驗目的,1、了解無約束規(guī)劃問題的求解原理與方法 ；,2、會用Matlab軟件求解無約束規(guī)劃問題。,二、實驗原理和方法,無約束規(guī)劃問題的解法一般按目標函數(shù)的形式分為兩大類： 一類是一元函數(shù)的一維搜索法，如黃金分割法、插值法等； 另一類是求解多元函數(shù)的下降迭代法。,迭代的基本思想和步驟大致可分為以下四步：,三、實驗內(nèi)容與步驟,在Matlab

5、軟件中，求解無約束規(guī)劃的常用命令是：,x=fminunc(fun,x0),其中，fun函數(shù)應預先定義到M文件中，并設置初始 解向量為x0。,【例 2】,求解,取,解：首先建立函數(shù)文件fun702.m,以fun702為文件名保存此函數(shù)文件。,在命令窗口輸入：,x0=-2;4; x=fminunc(fun702,x0),結(jié)果顯示：,f = -1.0000,x = 1.0000 1.0000,即極小值為-1，是x1=1,x2=1時取得。,Matlab程序： ch702.m,【例 3】,解非線性方程組,解：解此非線性方程組等價于求解無約束非線性規(guī)劃問題：,然后建立函數(shù)文件fun703.m,在命令窗口輸

6、入：,x0=0;0; x=fminunc(fun703,x0),結(jié)果顯示： f =5.2979e-011 x =1.0673 0.1392,則非線性方程組的解為x1=1.0673,x2=0.1392。,Matlab程序： ch703.m,第三節(jié) 約束非線性規(guī)劃計算方法,一、實驗目的,1、了解約束非線性規(guī)劃問題的求解原理與方法；,2、會用Matlab軟件求解約束非線性規(guī)劃問題。,二、實驗原理和方法,對于約束非線性規(guī)劃，隨著目標函數(shù)和約束條件的不同， 解法也不同，一般來說，有兩類方法：,（1）、將約束問題化為無約束問題的求解方法；,（2）、用線性規(guī)劃來逼近非線性規(guī)劃；,三、實驗內(nèi)容與步驟,約束非線

7、性規(guī)劃的一般形式為：,其中，f(x)為多元實值函數(shù);g(x)為向量函數(shù),并且f(x),g(x)中至少有一個函數(shù)是非線性函數(shù)的（否則成為線性規(guī)劃問題）。,x=fmincon(fun,x0,A,b) x=fmincon(fun,x0,A,b,Aeq,beq) x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub) x=fmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon),在Matlab優(yōu)化工具箱中，fmincon函數(shù)是用SQP算法來 解決一般的約束非線性規(guī)劃的函數(shù)，它的命令格式為：,【例 4】,求解約束非線性規(guī)劃：,(初值為1;1),解:首先建立一個m

8、文件fun7041.m function y=fun7041(x) y=-exp(x(1)*x(2)2*(3-exp(x(1)-x(2)2); 存儲為fun7041.m,首先將問題轉(zhuǎn)化為matlab要求的格式;即求出fun,A,b,Aeq,Beq,X0,Lb,Ub,然后建立一個 m文件 fun7042.m function c,cep=fun7042(x) c=; % c為非線性不等式,且為c=0 cep=exp(x(1)+x(2)2-3; % cep為非線性等式 然后存儲為fun7042.m,最后在命令窗口中輸入： A=;b=;Aeq=;Beq=;Lb=;Ub=; x,f=fmincon(fun7041,1;1,fun7042) -f,因題目中有非線性約束條件，所以建立非線性約束m-文件。,Matlab程序： ch704.m,結(jié)果為:,x = 0.8852 0.7592 f = 6.2043e-016 ans= - 6.2043e-016,最后的結(jié)果為: - 6.2043e-016,【例 5】,求解約束非線性規(guī)劃：,解：首先建立一個m文件 fun705.m function y=fun705(x) y=(x(1)-1)2+(x(2)-2)2+(x(3)-3)2+(x(4)-4)2; 存儲為fun705.m文件.,x0=1;1;1;1;A=1 1 1 1;3