規(guī)劃模型一演示文稿當(dāng)前第1頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)（優(yōu)選）規(guī)劃模型一當(dāng)前第2頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)案例一、

家具生產(chǎn)的安排

家具公司生產(chǎn)桌子和椅子，用于生產(chǎn)的勞力共計(jì)450個(gè)工時(shí)，木材共有4立方米每張桌子要使用15個(gè)工時(shí)，0.2立方木材售價(jià)80元。每張椅子使用10個(gè)工時(shí)，0.05立方木材售價(jià)45元。問為達(dá)到最大的收益，應(yīng)如何安排生產(chǎn)？當(dāng)前第3頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)分析：

1.求什么？生產(chǎn)多少桌子？生產(chǎn)多少椅子？

2.優(yōu)化什么？收益最大

3.限制條件？原料總量勞力總數(shù)x1x2MaxZ=80x1+45x20.2x1+0.05x2

≤415x1+10x2≤450當(dāng)前第4頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)模型I：以產(chǎn)值為目標(biāo)取得最大收益.設(shè)：生產(chǎn)桌子x1張,椅子x2張,(決策變量)

要優(yōu)化的目標(biāo)表示為：maxf=80x1+45x2

對(duì)決策變量的約束（約束條件）：

0.2x1+0.05x2≤415x1+10x2≤450,x1≥0,x2≥0,

模型II.在不降低當(dāng)前生產(chǎn)水平的前提下評(píng)估資源的貢獻(xiàn)，使“成本”投入最低。（將在下一講中介紹）當(dāng)前第5頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)規(guī)劃問題：在約束條件下求目標(biāo)函數(shù)的最優(yōu)值點(diǎn)。規(guī)劃問題包含3個(gè)組成要素:

決策變量(decisionvariable)目標(biāo)函數(shù)(objectivefunction)

約束條件(constraint)當(dāng)目標(biāo)函數(shù)和約束條件都是決策變量的線性函數(shù)時(shí)，稱為線性規(guī)劃問題,

否則稱為非線性規(guī)劃問題。當(dāng)前第6頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)可行解（feasiblesolution）

使得約束條件成立的決策變量的一組值可行域（feasibleregion）

全體可行解組成的集合（經(jīng)常記為S）

最優(yōu)解（optimalsolution）

可行域中使目標(biāo)函數(shù)達(dá)到所需最大或最小的可行解

當(dāng)前第7頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)線性規(guī)劃問題求解方法1、圖解法(Graphicalmethod)

：(解兩個(gè)變量的線性規(guī)劃問題)

在平面上畫出可行域（凸多邊形），計(jì)算目標(biāo)函數(shù)在各極點(diǎn)(多邊形頂點(diǎn))處的值比較后，取最值點(diǎn)為最優(yōu)解。當(dāng)前第8頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)凸集(Convexset)凸集非凸集如果某個(gè)集合中任意兩點(diǎn)連起來的直線都屬于該集合，則稱其為凸集，否則為非凸集，如下圖所示數(shù)學(xué)定義：是凸集當(dāng)且僅當(dāng)對(duì)任意實(shí)數(shù)和任意的均成立當(dāng)前第9頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)極點(diǎn)(Extremepoint)

設(shè)K是凸集，，若X不能用K中兩個(gè)不同的點(diǎn)的凸組合表示為<)10()1()2()1(<-+=aaaXXX則稱X是K的一個(gè)極點(diǎn)或頂點(diǎn)。X是凸集K的極點(diǎn)是指X不可能是K中某一線段的內(nèi)點(diǎn)，只能是K中某一線段的端點(diǎn)。O當(dāng)前第10頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)命題1

線性規(guī)劃問題的可行解集是凸集

可行解集：線性不等式組的解（可行域）

0.2x1+0.05x2=415x1+10x2=450

可行解：滿足約束條件的解。綠色區(qū)域中的每一個(gè)點(diǎn)（包括邊界點(diǎn)）都是可行解。此區(qū)域是【案例一】的線性規(guī)劃問題的解的集合（可行解域）?？尚杏虍?dāng)前第11頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)命題2

線性規(guī)劃問題的目標(biāo)函數(shù)關(guān)于不同的目標(biāo)值是一族平行直線,目標(biāo)值的大小描述了直線距離原點(diǎn)的遠(yuǎn)近

【案例一】的目標(biāo)函數(shù)Z=80x1+45x2在這個(gè)坐標(biāo)平面上，它可以表示以Z為參數(shù)、-16/9為斜率的一族平行線：位于同一直線上的點(diǎn)，具有相同的目標(biāo)函數(shù)值，稱為“等值線”。當(dāng)前第12頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)當(dāng)Z值由小變大時(shí)，直線沿其法線方向向右上方移動(dòng)。當(dāng)移動(dòng)到C時(shí)，Z值在可行域的邊界上實(shí)現(xiàn)最大化。最優(yōu)解（14，24），Z=2200。最優(yōu)生產(chǎn)方案:桌子生產(chǎn)14張，椅子生產(chǎn)24張，最大利潤(rùn)2200元(最優(yōu)值）。C當(dāng)前第13頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)命題3

線性規(guī)劃問題的最優(yōu)解一定在可行解集的某個(gè)極點(diǎn)上達(dá)到(穿過可行域的目標(biāo)直線組中最遠(yuǎn)離(或接近)原點(diǎn)的直線所穿過的凸多邊形的頂點(diǎn)).

當(dāng)前第14頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)2、單純形法（SimplexMethod

）:

通過確定約束方程組的基本解,

并計(jì)算相應(yīng)目標(biāo)函數(shù)值,

在可行解集的極點(diǎn)中搜尋最優(yōu)解.

當(dāng)前第15頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)在用單純法求解線性規(guī)劃問題時(shí)，為了討論問題方便，需將線性規(guī)劃模型化為統(tǒng)一的標(biāo)準(zhǔn)形式。線性規(guī)劃問題的標(biāo)準(zhǔn)型為:1．目標(biāo)函數(shù)求最大值（或求最小值）2．約束條件都為等式方程3．變量xj非負(fù)4．常數(shù)bi非負(fù)線性規(guī)劃的標(biāo)準(zhǔn)型(StandardformofLP)當(dāng)前第16頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)

模型的標(biāo)準(zhǔn)化決策變量:x1,x2,…,xn.

目標(biāo)函數(shù):Z=c1x1+c2x2+…+cnxn.

約束條件:a11x1+…+a1nxn≤b1,……am1x1+…+amnxn≤bm,當(dāng)前第17頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)模型的標(biāo)準(zhǔn)化

10.引入松弛變量將不等式約束變?yōu)榈仁郊s束若有ai1x1+…+ainxn≤bi,則引入xn+i≥0,使得

ai1x1+…+ainxn+xn+i=bi

若有aj1x1+…+ajnxn≥bj,則引入xn+j≥0,使得

aj1x1+…+ajnxn-xn+j=bj.

且有Z=c1x1+c2x2+…+cnxn+0xn+1+…+0xn+m.

當(dāng)前第18頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)20.將目標(biāo)函數(shù)的優(yōu)化變?yōu)槟繕?biāo)函數(shù)的極大化.若求minZ,令Z’=–Z,則問題變?yōu)閙axZ’.30.引入人工變量,使得所有變量均為非負(fù).若xi

沒有非負(fù)的條件,則引入xi’≥0和xi’’≥0,令xi=xi’–xi’’,則可使得問題的全部變量均非負(fù).當(dāng)前第19頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)標(biāo)準(zhǔn)化模型

求變量x1,x2,…,xn,maxZ=c1x1+…+cnxn,s.t.a11x1+…+a1nxn=b1,……am1x1+…+amnxn=bm,x1≥0,…,xn≥0,當(dāng)前第20頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)【例】將下列線性規(guī)劃化為標(biāo)準(zhǔn)形【解】（１）因?yàn)閤3無符號(hào)要求，即x3取正值也可取負(fù)值，標(biāo)準(zhǔn)型中要求變量非負(fù)，所以令當(dāng)前第21頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)(2)第一個(gè)約束條件是≤號(hào)，在≤左端加入松馳變量(slackvariable)x4，x4≥0,化為等式；(4)第三個(gè)約束條件是≤號(hào)且常數(shù)項(xiàng)為負(fù)數(shù)，因此在≤左邊加入松馳變量x6，x6≥0，同時(shí)兩邊乘以－1。（5）目標(biāo)函數(shù)是最小值，為了化為求最大值，令Z′=－Z,得到maxZ′=－Z，即當(dāng)Z達(dá)到最小值時(shí)Z′達(dá)到最大值，反之亦然。(3)第二個(gè)約束條件是≥號(hào)，在≥左端減去剩余變量(Surplusvariable)x5，x5≥0。也稱松馳變量當(dāng)前第22頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)綜合起來得到下列標(biāo)準(zhǔn)型當(dāng)前第23頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)當(dāng)某個(gè)變量xj≤0時(shí),令x/j=－xj

。當(dāng)某個(gè)約束是絕對(duì)值不等式時(shí)，將絕對(duì)值不等式化為兩個(gè)不等式，再化為等式，例如約束將其化為兩個(gè)不等式再加入松馳變量化為等式。當(dāng)前第24頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)【例】將下例線性規(guī)劃化為標(biāo)準(zhǔn)型【解】

此題關(guān)鍵是將目標(biāo)函數(shù)中的絕對(duì)值去掉。令則有當(dāng)前第25頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)得到線性規(guī)劃的標(biāo)準(zhǔn)形式

當(dāng)前第26頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)單純形法的基本思想

對(duì)于一個(gè)標(biāo)準(zhǔn)型LP問題，從一個(gè)初始基可行解出發(fā)，判斷其是否為最優(yōu)解，若是則結(jié)束；否則求一個(gè)與其“相鄰”的、改進(jìn)的基可行解。再判斷這個(gè)解是否最優(yōu)，若是則結(jié)束，否則再求一個(gè)“相鄰”的、改進(jìn)的基可行解……如此迭代下去，直到找到基最優(yōu)解或判定問題無解為止。x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2如例1，OQ1Q2或OQ4Q3Q2當(dāng)前第27頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)單純形法要解決的三方面的問題：（1）如何確定初始的基可行解？（2）如何進(jìn)行解的最優(yōu)性判別？（3）如何尋找改進(jìn)的基可行解？當(dāng)前第28頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)標(biāo)準(zhǔn)形式LP的基本可行解

在n個(gè)變量m個(gè)約束的標(biāo)準(zhǔn)LP中，指定其中

n–m個(gè)變量為0，從約束條件中可解得其余m個(gè)變量的唯一非負(fù)解，此時(shí)所對(duì)應(yīng)的線性規(guī)劃的可行解稱為該LP的基本可行解（basicfeasiblesolution），上述n-m個(gè)變量稱為自由變量（freevariables），剩下的m個(gè)變量稱為基變量，簡(jiǎn)稱基（basic）用單純形法解線性規(guī)劃問題的具體步驟將在矩陣的學(xué)習(xí)之后做詳細(xì)的介紹當(dāng)前第29頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)3、用MATLAB軟件求解線性規(guī)劃問題線性規(guī)劃問題的求解方法包括圖解法、單純形法、矩陣法等.但在決策變量個(gè)數(shù)較多，求解過程都比較復(fù)雜時(shí)，用MATLAB軟件求解線性規(guī)劃問題則比較簡(jiǎn)單.當(dāng)前第30頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)MATLAB求解線性規(guī)劃問題的命令⑴X=linprog(f,A,b)求解LP問題命令格式命令函數(shù)linprog()當(dāng)前第31頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)⑵[X,fval]=linprog(f,A,b,Aeq,Beq,LB,UB)求解LP問題當(dāng)前第32頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)⑶[X,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,Beq,LB,UB,X0,options).其功能是求解有初始值X0和用options指定優(yōu)化參數(shù)進(jìn)行優(yōu)化的LP問題.函數(shù)說明(1)fAXb線性規(guī)劃的不等式約束條件AeqBeq線性規(guī)劃的等式約束條件目標(biāo)函數(shù)取得極值的決策變量組成的列向量矩陣向量矩陣向量目標(biāo)函數(shù)的系數(shù)組成的向量當(dāng)前第33頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)LBX0OptionsfvalUB變量的上界約束變量的初始值變量的下界約束控制規(guī)劃過程的參數(shù)系列優(yōu)化結(jié)束后得到的目標(biāo)函數(shù)值當(dāng)前第34頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)[X,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,Beq,LB,UB,X0,options)目標(biāo)函數(shù)取得極值的決策變量組成的列向量?jī)?yōu)化結(jié)束后得到的目標(biāo)函數(shù)值目標(biāo)函數(shù)的系數(shù)組成的向量線性規(guī)劃的不等式約束條件矩陣向量控制規(guī)劃過程的參數(shù)系列變量的初始值變量的下界約束變量的上界約束線性規(guī)劃的等式約束條件矩陣向量當(dāng)前第35頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)(2)運(yùn)用linprog()命令時(shí)，系統(tǒng)默認(rèn)為它的各種linprog(f,A,b,Aeq,Beq,LB,UB,X0,options)都存在，且按固定順序排列。本例中，在存在約束LB的情況下，它后面的參數(shù)沒給出，可以不聲明，但是LB前面的參數(shù)即使沒給出（例如等式約束條件）也要用空矩陣“[

]”的方式給出聲明，不能省略。函數(shù)說明(3)返回值exitflag有3種情況：exitflag=－1表示優(yōu)化結(jié)果不收斂。exitflag=1表示優(yōu)化過程中變量收斂于解X。

exitflag=0表示優(yōu)化結(jié)果已經(jīng)超過函數(shù)的估計(jì)值或者已聲明的最大疊代次數(shù)；當(dāng)前第36頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)(4)返回值output有3個(gè)分量，iterations表示優(yōu)化過程的疊代次數(shù)，cgiterations表示PCG疊代次數(shù)，algorithm表示優(yōu)化采用的運(yùn)算規(guī)則。函數(shù)說明(5)返回值lambda有4個(gè)分量，ineqlin是線性不等式約束條件，eqlin是線性等式約束條件，upper是變量的上界約束條件，lower是變量的下界約會(huì)條件。它們的返回值分別表示相應(yīng)的約束條件在優(yōu)化過程中是否有效，本例中可以看到，三個(gè)不等式約束中的后兩個(gè)是有效的。當(dāng)前第37頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)(6)線性規(guī)劃問題沒有可行解時(shí),系統(tǒng)提示

Warning:Theconstraintsareoverlystringent;thereisnofeasiblesolution.如果優(yōu)化成功,系統(tǒng)將會(huì)提示:Optimizationterminatedsuccessfully函數(shù)說明當(dāng)前第38頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)

案例二（生產(chǎn)計(jì)劃的問題）某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)Ⅰ、Ⅱ的兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需的設(shè)備臺(tái)時(shí)，A、B兩種原材料的消耗以及每件產(chǎn)品可獲的利潤(rùn)如下表所示。問應(yīng)如何安排計(jì)劃使該工廠獲利最多？

ⅠⅡ資源限量設(shè)備128(臺(tái)時(shí))原材料A4016(kg)原材料B0412(kg)單位產(chǎn)品利潤(rùn)（萬元）23

返回當(dāng)前第39頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)用MATLAB

求解案例二中關(guān)于生產(chǎn)計(jì)劃的LP問題解原LP問題為

MATLAB命令的標(biāo)準(zhǔn)形是求目標(biāo)函數(shù)的最小值,通常將maxf通常轉(zhuǎn)變?yōu)閙in-f來編程求解。原問題轉(zhuǎn)化為當(dāng)前第40頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)在MATLAB中輸入>>clear>>f=-[2,3];>>A=[1,2;4,0;0,4];>>B=[8,16,12];>>lb=[0,0];>>[X,fval]=linprog(f,A,B,[],[],lb)擊回車鍵，顯示最優(yōu)解及目標(biāo)函數(shù)最優(yōu)值Optimizationterminatedsuccessfully.X=

4.0000

2.0000當(dāng)前第41頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)fval=

-14.0000所以，工廠應(yīng)選擇生產(chǎn)第Ⅰ、Ⅱ產(chǎn)品的產(chǎn)量分別為4件和2件，工廠最多可獲利14萬元。當(dāng)前第42頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)案例三(營(yíng)養(yǎng)配餐問題)

假定一個(gè)成年人每天需要從食物中獲取3000卡路里熱量，55克蛋白質(zhì)和800毫克鈣。如果市場(chǎng)上只有四種食品可供選擇，它們每千克所含熱量和營(yíng)養(yǎng)成份以及市場(chǎng)價(jià)格如下表所示。試建立滿足營(yíng)養(yǎng)的前提下使購(gòu)買食品費(fèi)用最小的數(shù)學(xué)模型。序號(hào)食品名稱熱量(卡路里)蛋白質(zhì)(克)鈣(mg)價(jià)格(元)1豬肉100050400102雞蛋8006020063大米9002030034白菜200105002返回當(dāng)前第43頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)用MATLAB求解案例三中的線性規(guī)劃問題。解原LP模型為在MATLAB中輸入>>clear>>f=[10,6,3,2];>>A=[-10,-8,-9,-2;-5,-6,-2,-1;-4,-2,-3,-5];b=[-30,-5.5,-8];>>lb=[0,0,0,0];>>[X,fval]=linprog(f,A,b,[],[],lb)當(dāng)前第44頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)顯示最優(yōu)解及目標(biāo)函數(shù)最優(yōu)值Optimizationterminatedsuccessfully.X=0.00000.00003.3333

0.0000

所以應(yīng)購(gòu)買3.3333千克大米才能既滿足營(yíng)養(yǎng)需求，又能使購(gòu)買食品的費(fèi)用最小。當(dāng)前第45頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)

案例四(投資問題)某公司有一批資金用于4個(gè)工程項(xiàng)目的投資，其投資各項(xiàng)目時(shí)所得的凈收益如下表：

工程項(xiàng)目ABCD收益(%)1510812由于某種原因，決定用于項(xiàng)目A的投資不大于其他各項(xiàng)投資之和而用于項(xiàng)目B和C的投資要大于項(xiàng)目D的投資。試建立該公司收益最大的投資分配方案的數(shù)學(xué)模型。

返回當(dāng)前第46頁(yè)\共有50頁(yè)\編于星期三\11點(diǎn)用MATL