規(guī)劃模型一演示文稿當(dāng)前1頁，總共50頁。（優(yōu)選）規(guī)劃模型一當(dāng)前2頁，總共50頁。案例一、

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

家具公司生產(chǎn)桌子和椅子，用于生產(chǎn)的勞力共計450個工時，木材共有4立方米每張桌子要使用15個工時，0.2立方木材售價80元。每張椅子使用10個工時，0.05立方木材售價45元。問為達到最大的收益，應(yīng)如何安排生產(chǎn)？當(dāng)前3頁，總共50頁。分析：

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

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

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

≤415x1+10x2≤450當(dāng)前4頁，總共50頁。模型I：以產(chǎn)值為目標取得最大收益.設(shè)：生產(chǎn)桌子x1張,椅子x2張,(決策變量)

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

對決策變量的約束（約束條件）：

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

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

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

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

否則稱為非線性規(guī)劃問題。當(dāng)前6頁，總共50頁?？尚薪猓╢easiblesolution）

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

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

最優(yōu)解（optimalsolution）

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

當(dāng)前7頁，總共50頁。線性規(guī)劃問題求解方法1、圖解法(Graphicalmethod)

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

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

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

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

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

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

可行解：滿足約束條件的解。綠色區(qū)域中的每一個點（包括邊界點）都是可行解。此區(qū)域是【案例一】的線性規(guī)劃問題的解的集合（可行解域）?？尚杏虍?dāng)前11頁，總共50頁。命題2

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

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

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

當(dāng)前14頁，總共50頁。2、單純形法（SimplexMethod

）:

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

并計算相應(yīng)目標函數(shù)值,

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

當(dāng)前15頁，總共50頁。在用單純法求解線性規(guī)劃問題時，為了討論問題方便，需將線性規(guī)劃模型化為統(tǒng)一的標準形式。線性規(guī)劃問題的標準型為:1．目標函數(shù)求最大值（或求最小值）2．約束條件都為等式方程3．變量xj非負4．常數(shù)bi非負線性規(guī)劃的標準型(StandardformofLP)當(dāng)前16頁，總共50頁。

模型的標準化決策變量:x1,x2,…,xn.

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

約束條件:a11x1+…+a1nxn≤b1,……am1x1+…+amnxn≤bm,當(dāng)前17頁，總共50頁。模型的標準化

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頁，總共50頁。20.將目標函數(shù)的優(yōu)化變?yōu)槟繕撕瘮?shù)的極大化.若求minZ,令Z’=–Z,則問題變?yōu)閙axZ’.30.引入人工變量,使得所有變量均為非負.若xi

沒有非負的條件,則引入xi’≥0和xi’’≥0,令xi=xi’–xi’’,則可使得問題的全部變量均非負.當(dāng)前19頁，總共50頁。標準化模型

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

。當(dāng)某個約束是絕對值不等式時，將絕對值不等式化為兩個不等式，再化為等式，例如約束將其化為兩個不等式再加入松馳變量化為等式。當(dāng)前24頁，總共50頁?！纠繉⑾吕€性規(guī)劃化為標準型【解】

此題關(guān)鍵是將目標函數(shù)中的絕對值去掉。令則有當(dāng)前25頁，總共50頁。得到線性規(guī)劃的標準形式

當(dāng)前26頁，總共50頁。單純形法的基本思想

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

在n個變量m個約束的標準LP中，指定其中

n–m個變量為0，從約束條件中可解得其余m個變量的唯一非負解，此時所對應(yīng)的線性規(guī)劃的可行解稱為該LP的基本可行解（basicfeasiblesolution），上述n-m個變量稱為自由變量（freevariables），剩下的m個變量稱為基變量，簡稱基（basic）用單純形法解線性規(guī)劃問題的具體步驟將在矩陣的學(xué)習(xí)之后做詳細的介紹當(dāng)前29頁，總共50頁。3、用MATLAB軟件求解線性規(guī)劃問題線性規(guī)劃問題的求解方法包括圖解法、單純形法、矩陣法等.但在決策變量個數(shù)較多，求解過程都比較復(fù)雜時，用MATLAB軟件求解線性規(guī)劃問題則比較簡單.當(dāng)前30頁，總共50頁。MATLAB求解線性規(guī)劃問題的命令⑴X=linprog(f,A,b)求解LP問題命令格式命令函數(shù)linprog()當(dāng)前31頁，總共50頁。⑵[X,fval]=linprog(f,A,b,Aeq,Beq,LB,UB)求解LP問題當(dāng)前32頁，總共50頁。⑶[X,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,Beq,LB,UB,X0,options).其功能是求解有初始值X0和用options指定優(yōu)化參數(shù)進行優(yōu)化的LP問題.函數(shù)說明(1)fAXb線性規(guī)劃的不等式約束條件AeqBeq線性規(guī)劃的等式約束條件目標函數(shù)取得極值的決策變量組成的列向量矩陣向量矩陣向量目標函數(shù)的系數(shù)組成的向量當(dāng)前33頁，總共50頁。LBX0OptionsfvalUB變量的上界約束變量的初始值變量的下界約束控制規(guī)劃過程的參數(shù)系列優(yōu)化結(jié)束后得到的目標函數(shù)值當(dāng)前34頁，總共50頁。[X,fval,exitflag,output,lambda]=linprog(f,A,b,Aeq,Beq,LB,UB,X0,options)目標函數(shù)取得極值的決策變量組成的列向量優(yōu)化結(jié)束后得到的目標函數(shù)值目標函數(shù)的系數(shù)組成的向量線性規(guī)劃的不等式約束條件矩陣向量控制規(guī)劃過程的參數(shù)系列變量的初始值變量的下界約束變量的上界約束線性規(guī)劃的等式約束條件矩陣向量當(dāng)前35頁，總共50頁。(2)運用linprog()命令時，系統(tǒng)默認為它的各種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ù)的估計值或者已聲明的最大疊代次數(shù)；當(dāng)前36頁，總共50頁。(4)返回值output有3個分量，iterations表示優(yōu)化過程的疊代次數(shù)，cgiterations表示PCG疊代次數(shù)，algorithm表示優(yōu)化采用的運算規(guī)則。函數(shù)說明(5)返回值lambda有4個分量，ineqlin是線性不等式約束條件，eqlin是線性等式約束條件，upper是變量的上界約束條件，lower是變量的下界約會條件。它們的返回值分別表示相應(yīng)的約束條件在優(yōu)化過程中是否有效，本例中可以看到，三個不等式約束中的后兩個是有效的。當(dāng)前37頁，總共50頁。(6)線性規(guī)劃問題沒有可行解時,系統(tǒng)提示

Warning:Theconstraintsareoverlystringent;thereisnofeasiblesolution.如果優(yōu)化成功,系統(tǒng)將會提示:Optimizationterminatedsuccessfully函數(shù)說明當(dāng)前38頁，總共50頁。

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

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

返回當(dāng)前39頁，總共50頁。用MATLAB

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

MATLAB命令的標準形是求目標函數(shù)的最小值,通常將maxf通常轉(zhuǎn)變?yōu)閙in-f來編程求解。原問題轉(zhuǎn)化為當(dāng)前40頁，總共50頁。在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)解及目標函數(shù)最優(yōu)值Optimizationterminatedsuccessfully.X=

4.0000

2.0000當(dāng)前41頁，總共50頁。fval=

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

假定一個成年人每天需要從食物中獲取3000卡路里熱量，55克蛋白質(zhì)和800毫克鈣。如果市場上只有四種食品可供選擇，它們每千克所含熱量和營養(yǎng)成份以及市場價格如下表所示。試建立滿足營養(yǎng)的前提下使購買食品費用最小的數(shù)學(xué)模型。序號食品名稱熱量(卡路里)蛋白質(zhì)(克)鈣(mg)價格(元)1豬肉100050400102雞蛋8006020063大米9002030034白菜200105002返回當(dāng)前43頁，總共50頁。用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頁，總共50頁。顯示最優(yōu)解及目標函數(shù)最優(yōu)值Optimizationterminatedsuccessfully.X=0.00000.00003.3333

0.0000

所以應(yīng)購買3.3333千克大米才能既滿足營養(yǎng)需求，又能使購買食品的費用最小。當(dāng)前45頁，總共50頁。

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

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

返回當(dāng)前46頁，總共50頁。用MATLAB求解案例四中的