線性規(guī)劃課件

數(shù)學(xué)規(guī)劃其中，x是決策變量，f(x)是目標函數(shù)，gi(x)0是約束條件。數(shù)學(xué)規(guī)劃問題模型的一般形式數(shù)學(xué)規(guī)劃問題劃分線性規(guī)劃：目標函數(shù)和約束條件都是線性的非線性規(guī)劃：目標函數(shù)或者約束條件是非線性的整數(shù)規(guī)劃：決策變量是整數(shù)值多目標規(guī)劃：具有多個目標函數(shù)目標規(guī)劃：具有不同優(yōu)先級的目標和偏差動態(tài)規(guī)劃：求解多階段決策問題的最優(yōu)化方法等等一、線性規(guī)劃1.1線性規(guī)劃問題提出1.2線性規(guī)劃問題的數(shù)學(xué)模型1.3線性規(guī)劃問題的解1.4線性規(guī)劃問題應(yīng)用實例例：某車間有甲、乙兩臺機床，可用于加工三種工件。假定兩臺機床的可用臺時數(shù)分別為800和900，三種工件的數(shù)量分別為400、600和500，且已知用不同機床加工單位工件所需的臺時數(shù)和加工費用如下表。問怎樣分配機床的加工任務(wù)，才能既滿足加工工件的要求，又使加工費用最低？1.1線性規(guī)劃問題提出解：設(shè)在甲機床上加工工件1、2、3的數(shù)量分別為x1、x2、x3，

在乙機床上加工工件1、2、3的數(shù)量分別為x4、x5、x6,1.1線性規(guī)劃問題提出例：某廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，分別在A、B、C三種不同的設(shè)備上加工。生產(chǎn)每件產(chǎn)品Ⅰ需占用各設(shè)備分別為2h、4h、0h，生產(chǎn)每件產(chǎn)品Ⅱ需占用各設(shè)備分別為2h、0h、5h。已知各設(shè)備計劃期內(nèi)生產(chǎn)能力分別為12h、16h、15h，又知每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2w，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3w。問該廠應(yīng)安排生產(chǎn)兩種產(chǎn)品各多少件，可使總利潤最大。1.1線性規(guī)劃問題提出解：設(shè)生產(chǎn)產(chǎn)品I、Ⅱ分別x1、x2件一般線性規(guī)劃問題的數(shù)學(xué)模型1.2線性規(guī)劃問題的數(shù)學(xué)模型簡寫形式目標函數(shù)約束條件決策變量

1.2線性規(guī)劃問題的數(shù)學(xué)模型向量形式矩陣形式1.2線性規(guī)劃問題的數(shù)學(xué)模型非線性規(guī)劃問題轉(zhuǎn)化為線性規(guī)劃問題簡寫線性規(guī)劃問題的標準形式1.2線性規(guī)劃問題的數(shù)學(xué)模型集合形式1.2線性規(guī)劃問題的數(shù)學(xué)模型向量形式矩陣形式標準形式簡寫非標準形線性規(guī)劃問題的標準化

1.目標函數(shù)minz=CX令z=-z，有maxz=-CX2.約束條件a)bi<0的情況

例

x1-2x2=-1-x1+2x2=11.2線性規(guī)劃問題的數(shù)學(xué)模型2.約束條件b)約束條件為“”的情況令x3=12-2x1-2x20

x4=16-4x10x5=15-5x20例1.2線性規(guī)劃問題的數(shù)學(xué)模型非標準形線性規(guī)劃問題的標準化

2.約束條件b)約束條件為“”的情況1.2線性規(guī)劃問題的數(shù)學(xué)模型非標準形線性規(guī)劃問題的標準化

3.決策變量a)若xk0，

令xk=-xk，則xk0b)若xk為自由變量，令xk=xk-xk，且xk

0

，xk01.2線性規(guī)劃問題的數(shù)學(xué)模型非標準形線性規(guī)劃問題的標準化

例：將下述線性規(guī)劃模型化為標準形式

解：令z=-z，則1.2線性規(guī)劃問題的數(shù)學(xué)模型令x1=-x1，x3=

x3-x3，且x30，x30得原問題的等價標準形1.2線性規(guī)劃問題的數(shù)學(xué)模型1.可行解：滿足約束條件的解X=(x1,…,xn)T2.可行域：可行解的集合3.最優(yōu)解：使目標函數(shù)達到最大值的可行解4.最優(yōu)值：最優(yōu)解對應(yīng)到目標函數(shù)值1.3線性規(guī)劃問題的解線性規(guī)劃問題解的概念1.3線性規(guī)劃問題的解圖解法求解z=15x1x2A(6,0)B(0,6)2x1+2x2=12O4x1=165x2=15Q1Q2Q3Q4(3,3)x2OQ1Q2Q3Q4x1線性規(guī)劃問題求解的幾種可能結(jié)局1.唯一最優(yōu)解2.無窮多最優(yōu)解1.3線性規(guī)劃問題的解線性規(guī)劃問題求解的幾種可能結(jié)局1.唯一最優(yōu)解2.無窮多最優(yōu)解3.無界解Ox1x21.3線性規(guī)劃問題的解線性規(guī)劃問題求解的幾種可能結(jié)局1.唯一最優(yōu)解2.無窮多最優(yōu)解3.無界解4.無可行解x2Ox11.3線性規(guī)劃問題的解用Matlab求解線性規(guī)劃問題的解Matlab函數(shù)linprog()的調(diào)用形式：[x,fval]=linprog(c,A,b,Aeq,beq,lb,ub,x0,Options)其中：x為最優(yōu)解，fval返回對應(yīng)的目標函數(shù)最優(yōu)值，x0是x的初始值，Options是控制參數(shù)。1.3線性規(guī)劃問題的解例：c=[2;3;-5];A=[-2,5,-1;1,3,1];b=[-10;12];Aeq=[1,1,1];beq=7;x=linprog(-c,A,b,Aeq,beq,zeros(3,1))value=c'*x1.3線性規(guī)劃問題的解用Matlab求解線性規(guī)劃問題的解c=[2;3;1];A=[1,4,2;3,2,0];b=[8;6];[x,y]=linprog(c,-A,-b,[],[],zeros(3,1))1.3線性規(guī)劃問題的解用Matlab求解線性規(guī)劃問題的解例：1.4線性規(guī)劃問題應(yīng)用實例線性規(guī)劃建模步驟:①設(shè)立決策變量；②明確約束條件并用變量的線性等式或不等式表示；③用變量的線性函數(shù)表示目標，并確定是求極小還是極大；④根據(jù)變量的物理性質(zhì)研究變量是否有非負性。

投資的收益和風險1.4線性規(guī)劃問題應(yīng)用實例二、基本假設(shè)和符號規(guī)定

投資的收益和風險1.4線性規(guī)劃問題應(yīng)用實例三、模型的建立與分析1.總體風險用所投資的Si中最大的一個風險來衡量,即max{qixi|i=1，2,…,n}

投資的收益和風險1.4線性規(guī)劃問題應(yīng)用實例4.模型簡化：三、模型的建立與分析

投資的收益和風險1.4線性規(guī)劃問題應(yīng)用實例三、模型的建立與分析

投資的收益和風險1.4線性規(guī)劃問題應(yīng)用實例四、模型1的求解

由于a是任意給定的風險度，到底怎樣給定沒有一個準則，不同的投資者有不同的風險度。因此，從a=0開始，以步長△a=0.001進行循環(huán)搜索。

投資的收益和風險1.4線性規(guī)劃問題應(yīng)用實例a=0;whilea<=0.1c=[-0.05-0.27-0.19-0.185-0.185];Aeq=[11.011.021.0451.065];beq=[1];A=[00.025000;000.01500;0000.0550;00000.026];b=[a;a;a;a];vlb=[0,0,0,0,0];vub=[];[x,val]=linprog(c,A,b,Aeq,beq,vlb,vub);Q=-valplot(a,Q,'.')，axis([00.100.5])，holdona=a+0.001;endxlabel('a'),ylabel('Q')四、模型1的求解

投資的收益和風險1.4線性規(guī)劃問題應(yīng)用實例Matlab計算結(jié)果：四、模型1的求解

投資的收益和風險1.4線性規(guī)劃問題應(yīng)用實例2.投資越分散，投資者承擔的風險越小，即:冒險的投資者會出現(xiàn)集中投資的情況，保守的投資者則盡量分散投資。1.風險大，收益也大；a=0.003

x=0.49490.12000.20000.05450.1154Q=0.1266a=0.006

x=0.00000.24000.40000.10910.2212Q=0.2019a=0.008

x=0.00000.32000.53330.12710.0000Q=0.2112a=0.010

x=0.00000.40000.58430.00000.0000Q=0.2190a=0.020

x=0.00000.80000.18820.00000.0000Q=0.2518a=0.040

x=0.00000.99010.00000.00000.0000Q=0.2673

五、結(jié)果分析

投資的收益和風險1.4線性規(guī)劃問題應(yīng)用實例3.曲線上任一點都表示該風險水平的最大可能收益和該收益要求的最小風險。對于不同風險的承受能力，選擇該風險水平下的最優(yōu)投資組合。4.在a=0.006附近有一個轉(zhuǎn)折點，在該點左邊，風險增加很少時，利潤增長很快，在該點右邊，風險增加很大時，利潤增長很慢。所以對于風險和收益沒有特殊偏好的投資者來說，應(yīng)該選擇曲線的拐點作為最優(yōu)投資組合，投資方案為:風險度收益x0

x1

x2x3

x40.00600.201900.24000.40000.10910.2212五、結(jié)果分析

投資的收益和風險1.4線性規(guī)劃問題應(yīng)用實例某食品公司有三個糖果加工廠，每天的糖果生產(chǎn)量分別為：A1—7t，A2—4t，A3—9t。該公司把這些糖果分別運往四個地區(qū)銷售，各地區(qū)每天的銷售量為：B1—3t，B2—6t，B3—5t，B4—6t。已知從每個加工廠到各地區(qū)每噸糖果的運價如下表所示。問該食品公司應(yīng)如何調(diào)運，在滿足各地區(qū)需要的情況下，使總的運費支出為最小。

單位：元/t運輸問題1.4線性規(guī)劃問題應(yīng)用實例產(chǎn)銷表運價表運輸問題1.4線性規(guī)劃問題應(yīng)用實例解：設(shè)xij為從第i個產(chǎn)地調(diào)運給第j個銷地的物資的數(shù)量，使總的運費支出最小，可以表為以下數(shù)學(xué)形式：運輸問題1.4線性規(guī)劃問題應(yīng)用實例m行n行運輸問題1.4線性規(guī)劃問題應(yīng)用實例

有一份說明書，要分別譯成英、日、德、俄四種文字，交甲、乙、丙、丁四個人去完成。因個人專長不同，他們完成翻譯不同文字所需的時間如表所示。應(yīng)如何分配，使四個人分別完成這四項任務(wù)總的時間為最小。指派問題1.4線性規(guī)劃問題應(yīng)用實例解：設(shè)[aij]表示分配問題的效率矩陣，令則指派問題的數(shù)學(xué)模型一般寫為：指派問題1.4線性規(guī)劃問題應(yīng)用實例某晝夜服務(wù)的公交線路每天各時間段內(nèi)所需司機和乘務(wù)人員數(shù)如下：設(shè)司機和乘務(wù)人員分別在各時間段開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務(wù)人員，既能滿足工作需要，又配備最少司機和乘務(wù)人員?人力資源分配問題1.4線性規(guī)劃問題應(yīng)用實例分析：不同上班班次時段的司機和乘務(wù)人員數(shù)結(jié)束時段開工時段1234566:00-10:0010:00-14:0014:00-18:0018:00-22:0022:00-2:002:00-6:0016:00-10:00210:00-14:00314:00-18:00418:00-22:00522:00-2:0062:00-6:00每時段需要的總?cè)藬?shù)607060502030人力資源分配問題1.4線性規(guī)劃問題應(yīng)用實例解：設(shè)xi

表示第i班次時開始上班的司機和乘務(wù)人員數(shù)，則有結(jié)束時段開工時段1234566:00-10:0010:00-14:0014:00-18:0018:00-22:0022:00-2:002:00-6:0016:00-10:00210:00-14:00314:00-18:00418:00-22:00522:00-2:0062:00-6:00每時段需要的總?cè)藬?shù)607060502030人力資源分配問題1.4線性規(guī)劃問題應(yīng)用實例解：設(shè)xi

表示第i班次時開始上班的司機和乘務(wù)人員數(shù)，則有結(jié)束時段開工時段1234566:00-10:0010:00-14:0014:00-18:0018:00-22:0022:00-2:002:00-6:0016:00-10:00x1x1210:00-14:00x2x2314:00-18:00x3x3418:00-22:00x4x4522:00-2:00x5x562:00-6:00x6x6每時段需要的總?cè)藬?shù)607060502030人力資源分配問題1.4線性規(guī)劃問題應(yīng)用實例某企業(yè)生產(chǎn)甲、乙、丙三種產(chǎn)品，每一產(chǎn)品均須經(jīng)過A、B兩道工序。A工序有兩種設(shè)備可完成，B工序有三種設(shè)備可完成，除甲產(chǎn)品和乙產(chǎn)品的A工序可隨意安排外，其余只能在要求的設(shè)備上完成。加工單位產(chǎn)品所需工序時間及其他各項數(shù)據(jù)的費用有關(guān)資料見下表。試制訂利潤最大的產(chǎn)品加工方案。設(shè)備產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙費用/有效臺時A1510300/6000A27912321/10000B168250/4000B2411783/7000B37200/4000原料單價(元/件)0.250.350.5銷售單價(元/件)1.252.002.8生產(chǎn)計劃問題1.4線性規(guī)劃問題應(yīng)用實例設(shè)備產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙費用/有效臺時A1510300/6000A27912321/10000B168250/4000B2411783/7000B37200/4000原料單價(元/件)0.250.350.5銷售單價(元/件)1.252.002.8生產(chǎn)計劃問題1.4線性規(guī)劃問題應(yīng)用實例設(shè)備產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙費用/有效臺時A15x110x6300/6000A27x29x712x8321/10000B16x38(x6+x7)250/4000B24x411x8783/7000B37x5200/4000原料單價(元/件)0.250.350.5銷售單價(元/件)1.252.002.8目標函數(shù)：利潤=收入-成本-加工費maxz=[(1.25-0.25)(x1+x2)+(2-0.35)(x6+x7)+(2.8-0.5)x8]–[0.05(5x1+10x6)+0.03(7x2+9x7+12x8)+0.06(6x3+8x6+8x7)+0.11(4x4+11x8)+0.05×7x5]=0.75x1+0.7753x2-0.375x3-0.4474x4-0.35x5

+0.65x6+0.8611x7+0.6844x8收入-成本-加工費生產(chǎn)計劃問題1.4線性規(guī)劃問題應(yīng)用實例約束條件：設(shè)備產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙費用/有效臺時A15x110x6300/6000A27x29x712x8321/10000B16x38(x6+x7)250/4000B24x411x8783/7000B37x5200/4000原料單價(元/件)0.250.350.5銷售單價(元/件)1.252.002.8生產(chǎn)計劃問題1.4線性規(guī)劃問題應(yīng)用實例要做100套鋼架，每套用長為2.9m、2.1m和1.5m的圓鋼各一根。已知原料長7.4m，問應(yīng)如何下料使所用料最??？方案長度(m)123456782.9120101002.1002211301.531203104合計7.47.37.27.16.66.56.36殘料00.10.20.30.80.91.11.4下料問題1.4線性規(guī)劃問題應(yīng)用實例解：設(shè)采用方案i下料的原料根數(shù)為xi方案長度(m)123456782.9120101002.1002211301.531203104合計7.47.37.27.16.66.56.36殘料00.10.20.30.80.91.11.4下料問題1.4線性規(guī)劃問題應(yīng)用實例解：設(shè)采用方案i下料的原料根數(shù)為xi方案長度(m)123456782.9120101002.1002211301.531203104合計7.47.37.27.16.66.56.36殘料00.10.20.30.80.91.11.4下料問題1.4線性規(guī)劃問題應(yīng)用實例產(chǎn)品名稱規(guī)格要求單價(元/kg)甲原材料1不少于50%,原材料2不超過25%50乙原材料1不少于25%,原材料2不超過50%35丙不限25某工廠要用三種原料1、2、3混合調(diào)配出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如下表。問該廠應(yīng)如何安排生產(chǎn)，使利潤為最大？原材料名稱每天最多供應(yīng)量單價(元/kg)11006521002536035配料問題1.4線性規(guī)劃問題應(yīng)用實例解：設(shè)xij

表示第i種（i=1(甲)、i=2(乙)、i=3(丙)）產(chǎn)品中原料j的含量。對于甲：x11，x12，x13；產(chǎn)品甲的產(chǎn)量為x11+x12+x13

對于乙：x21，x22，x23；產(chǎn)品乙的產(chǎn)量為x21+x22+x23

對于丙：x31，x32，x33；產(chǎn)品丙的產(chǎn)量為x31+x32+x33

對于原料1：x11，x21，x31；原料1的需求量為x11+x21+x31

對于原料2：x12，x22，x32；原料2的需求量為x12+x22+x32

對于原料3：x13，x23，x33；原料3的需求量為x13+x23+x33

目標函數(shù)：利潤最大，利潤=收入-原料支出

約束條件：規(guī)格要求4個，供應(yīng)量限制3個配料問題1.4線性規(guī)劃問題應(yīng)用實例利潤=總收入-總成本=三種產(chǎn)品單價*產(chǎn)品數(shù)量-使用的原料單價*原料數(shù)量目標函數(shù)：Maxz=50(x11+x12+x13)+35(x21+x22+x23)+25(x31+x32+x33)-65(x11+x21+x31)-25(x12+x22+x32)-35(x13+x23+x33)=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

產(chǎn)品名稱單價(元/kg)原材料名稱單價(元/kg)甲50165乙35225丙25335配料問題1.4線性規(guī)劃問題應(yīng)用實例約束條件（1）：產(chǎn)品規(guī)格要求

x11≥0.5(x11+x12+x13)x12≤0.25(x11+x12+x13)x21≥0.25(x21+x22+