2013數(shù)學建模周末培訓-matlab課件第7講約束優(yōu)化

數(shù)學實驗約束優(yōu)化問題實驗目的實驗內(nèi)容2、用Matlab求解線性規(guī)劃問題.1、了解約束優(yōu)化問題.1、生產(chǎn)計劃、投資策略2、線性規(guī)劃的基本原理和解法3、用Matlab求解線性規(guī)劃問題

§1兩個實例

（一）生產(chǎn)規(guī)劃問題

（二）投資策略問題實例一生產(chǎn)規(guī)劃問題某廠生產(chǎn)甲乙兩種口味的飲料，每百箱甲飲料需用原料6千克，工人10名，可獲利10萬元，每百箱乙飲料需用原料5千克，工人20名，可獲利9萬元，今工廠共有原料60千克，工人150名，又由于其他條件所限甲飲料產(chǎn)量不能超過8百箱，問如何安排生產(chǎn)計劃，即兩種飲料各生產(chǎn)多少使獲利最大？數(shù)學模型設決策變量為甲乙兩種飲料的產(chǎn)量，分別為x1,x2（以百箱為單位，但可以為小數(shù)），目標函數(shù)是總獲利，約束條件是原料，工人及對甲飲料產(chǎn)量的限制，則有：實例二投資策略問題某部門現(xiàn)有資金10萬元，五年內(nèi)有以下投資項目供選擇：項目A從第一年到第四年每年初投資，次年末收回本金且獲利15%；項目B第三年初投資，第五年末收回本金且獲利25%，最大投資額為4萬元；項目C第二年初投資，第五年末收回本金且獲利40%，最大投資額為3萬元；項目D每年初投資，年末收回本金且獲利6%。問如何確定投資策略使第五年末本息總額最大？目標函數(shù)是第五年末的本息總額，決策變量是每年初各個項目的投資額，約束條件是每年初擁有的資金，用xij表示第i年初（i=1,2,…,5）項目j（j=1,2,3,4分別代表A,B,C,D）的投資額，根據(jù)所給條件只有下表中的xij才是需要求解的。表投資方案選擇中的決策變量

年份

項目ABCD1X11X142X21X23X243X31X32X344X41X445X54因為項目D每年初可以投資，且年末能收回本息，所以每年初都應把字金全部投出去，由此可得如下的約束條件：第1年初：10萬元全部投向A,D，有

第2年初：擁有的資金為項目D第1年投資x14收回的本息，全部投向A,C,D，有：第3年初：擁有的資金為項目A第1年投資x11和D第2年投資x24收回的本息，全部投向A,B,D，有：第4年初：類似地有：第5年初：此外，項目B,C對投資額有限制，即第五年末的本息總額為

數(shù)學模型§2線性規(guī)劃的基本原理和解法實際問題一般都是有約束的，即使是最小二乘擬合，對擬合的系數(shù)也常常有所要求（如大于零）。反之，有些有約束的問題作為無約束優(yōu)化求解時優(yōu)化模型的一般形式：（1）

（2）

（2）式所界定的x的取值范圍是模型的可行域，滿足（2）的解是可行解，滿足（1）的可行解才是約束優(yōu)化的最優(yōu)解。一般問題都是有約束的，即使是最小二乘擬合，對擬合的系數(shù)也常常有所要求（如大于零），當然，有些有約束的問題作為無約束優(yōu)化求解時，得到的最優(yōu)解也許會滿足約束條件，多半是這個解在可行域的內(nèi)部，那么它當然也是約束問題的最優(yōu)解。但也有最優(yōu)解在可行域的邊界上取得的情況，此時不能用無約束優(yōu)化的方法求解，必須研究最優(yōu)解位于可行域邊界上時的性質(zhì)，進而尋求解法，當變量數(shù)目n和約束數(shù)目m較大時，通常使用的是數(shù)值解法。線性規(guī)劃的一般模型為：其中，均為已知。2.1線性規(guī)劃的圖解法

由于A、B、C三種元素都是原料市場上十分緊缺的貨品,工廠每月所能得到的這些元素的供應量分別為200kg、200kg和360kg.工廠生產(chǎn)每噸甲種合金的利潤為30萬元，生產(chǎn)每噸乙種合金的利潤為40萬元.

例1某合金工廠生產(chǎn)甲、乙兩種合金，生產(chǎn)每A元素20kg、B元素40kg和C元素90kg，噸甲種合金需用而生產(chǎn)每噸乙種合金需用A元素100kg、B元素80kg和C元素60kg.

試問：該工廠應如何安排生產(chǎn)，才能獲得最大利潤？數(shù)學模型

設每月生產(chǎn)甲種合金x1

噸，乙種合金x2

噸，利潤為u萬元,那么

u=30x1+40x2

要求何時有

maxu=max(30x1+40x2)

x1,x2滿足約束條件線性規(guī)劃問題求最優(yōu)解

二元一次方程a1x1+a2x2=b代表x1x2平面上的一條直線，而二元一次不等式a1x1+a2x2

b則代表了以此直線為界的半平面圖解法a1x1+a2x2=ba1x1+a2x2

b

這問題中約束條件意味著五個半平面的交集.它是一個包含邊界的凸多邊形OPQRS線性規(guī)劃的容許集x2

pQ

R0Sx1x2

pQ

R

0Sx1

30x1+40x2=u

將u視作參數(shù)，則30x1+40x2=u代表一條直線，隨著u的增或減，直線向右上或左下方平移.若直線經(jīng)過容許集的某頂點時再增減將使直線離開容許集，則此臨界狀態(tài)直線所對應的u的就是所求的最大值，所過頂點的坐標就是問題的最優(yōu)解從圖看出最優(yōu)解應為R點

最優(yōu)解在R點，由R是直線40x1+80x2=200與直線90x1+60x2=360的交點,可得最優(yōu)解為x1=3.5,x2=0.75,此時有最大值為u=135.說明安排月生產(chǎn)甲、乙種合金分別為3.5噸、0.75噸t，才能獲得最大利潤135萬元問題的解答例2求解解：前3個約束條件的不等號改成等號，是如下的3條直線：（書中210頁）

可以看出，由于線性規(guī)劃的約束條件和目標函數(shù)均為線性函數(shù)，所以對2維情形，可行域為直線組成的凸多邊形，目標函數(shù)的等值線為直線，這樣，最優(yōu)解一定在凸多邊形的某個頂點取得。從2維例子的幾何意義可以看出，還會有下列情形：（1）若可行域為空集（如第3個約束條件改為：-3x1+2x2≥14），則無最優(yōu)解（對于實際問題往往是模型或輸入數(shù)據(jù)有誤所致）（2）若可行域無界（如將第3個約束條件去掉），則可能無最優(yōu)解（對于實際問題可能是漏掉了某些約束條件所致），不過對于此例，若z取極小，則仍有最優(yōu)解。（3）最優(yōu)解在凸多邊形的一條邊上取得（如第3個約束條件改為3x1+x2≤14，L3將與目標函數(shù)等值線平行），則有無窮多個最優(yōu)解。將2維推廣到n維，可以想到，線性規(guī)劃的可行域是超平面組成的凸多邊形，等值線是超平面，最優(yōu)解在凸多面體的某個頂點取得，由此我們得到求解線性規(guī)劃的基本思路為：從可行域的某一個頂點開始，只需在有限多個頂點中一個一個找下去，一定能得到最優(yōu)解。圖解法的局限畫圖并不方便，可以不畫圖而求出容許集所有的頂點，再將目標函數(shù)在這些頂點上的值加以比較來求出最優(yōu)解.但在約束條件多或多變量時，也是難以做到的。2.2線性規(guī)劃的標準形和基本性質(zhì)2.2.1標準形（1）目標函數(shù)一律化為求極?。ㄈ绻髽O大，則利用maxz＜=＞min(-z)）.（2）對約束條件中Ax≤b的不等式，利用加入松弛變量的方法化為等式，如對于上例，可增加變量x3,x4,x5，將3個不等式的約束化為：如果原來約束條件中Ax≥b的不等式，可以利用加負號變?yōu)?Ax≤-b。線性規(guī)劃的標準形式為：

式中x≥0的約束一般實際問題都存在，如果數(shù)學上某個xj無此約束，可令如果原來約束為

可令

2.2.2基（本）解與基可行解線性方程組Ax=b的基本（解）可以如下求得：任取m個獨立的列向量組成基AB（AB可逆），其余列向量為非基AN，將A的列向量重排次序后可寫作A=（ABAN），相應地重排x的分量有x=（xB，xN）T，xB，xN分別稱為基變量和非基變量，于是

Ax=ABxB+ANxN=b一般地，當基變量xB≥0時（令非基變量xN=0），Ax=b的基解x=(xB,xN)T也滿足約束x≥0,稱為基可行解。

2.2.3線性規(guī)劃的基本性質(zhì)（1）若存在可行域，它必須是凸集（凸多面體）；（2）基可行解對應于可行域的頂點；（3）若有最優(yōu)解，必在可行域的頂點取得；由此可知，求最優(yōu)解只需在基可行解（可行域頂點）中尋找。

3用Matlab優(yōu)化工具箱解線性規(guī)劃用Matlab優(yōu)化工具箱解線性規(guī)劃時，必須首先化為如下形式：有如下程序：x=lp(c,A,b);x=lp(c,A,b,v1);x=lp(c,A,b,v1,v2);x=lp(c,A,b,v1,v2,x0);x=lp(c,A,b,v1,v2,x0,ne);x=lp(c,A,b,v1,v2,x0,ne,dis);[x,lag]=lp(c,A,b,…)[x,lag,how]=lp(c,A,b,…)參數(shù)說明：c,A,b為規(guī)劃的系數(shù)向量，系數(shù)矩陣，常數(shù)項向量。輸出x為最優(yōu)解；v1，v2為x的下界和上界，即有約束v1≤x≤v2(v1或v2的維數(shù)k可以小于x的維數(shù)n，此時v1或v2僅表示x前k個分量的下界或上界)；x0為初始解（缺省時程序自動取x0=0）；ne為等式約束的個數(shù)，且須將等式約束置于不等式約束前面；dis給出警告信息，如解無界或不可行，當中間某個輸入?yún)?shù)缺省時，需用[]占據(jù)其位置。輸出參數(shù)lag為拉格朗日乘子，維數(shù)等于約束條件的個數(shù)，其非零分量對應于起作用的約束條件；how給出錯誤信息：無可行解(infeasible)；無有界解（unbounded）或問題順利解決(ok)。例1：

C=-[3,1];%加負號將求極大化為求極小A=[-1,1;1,-2;3,2];B=[2,2,14];v1=[0,0];x=lp(c,a,b,v1)z=-c*x;得到最優(yōu)解x=（4，1），最大值z=13；如用[x,lag]=lp(c,a,b,v1)，可得lag=(0,0.3750,0.8750,0,0)，lag的第2，3分量非零，表示第2，3個約