線性規(guī)劃課件

數(shù)學(xué)規(guī)劃其中，x是決策變量，f(x)是目標(biāo)函數(shù)，gi(x)0是約束條件。數(shù)學(xué)規(guī)劃問題模型的一般形式數(shù)學(xué)規(guī)劃問題劃分線性規(guī)劃：目標(biāo)函數(shù)和約束條件都是線性的非線性規(guī)劃：目標(biāo)函數(shù)或者約束條件是非線性的整數(shù)規(guī)劃：決策變量是整數(shù)值多目標(biāo)規(guī)劃：具有多個目標(biāo)函數(shù)目標(biāo)規(guī)劃：具有不同優(yōu)先級的目標(biāo)和偏差動態(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é)模型簡寫形式目標(biāo)函數(shù)約束條件決策變量

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

1.目標(biāo)函數(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é)模型非標(biāo)準(zhǔn)形線性規(guī)劃問題的標(biāo)準(zhǔn)化

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

3.決策變量a)若xk0，

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

0

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

例：將下述線性規(guī)劃模型化為標(biāo)準(zhǔn)形式

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

x3-x3，且x30，x30得原問題的等價標(biāo)準(zhǔn)形1.2線性規(guī)劃問題的數(shù)學(xué)模型1.可行解：滿足約束條件的解X=(x1,…,xn)T2.可行域：可行解的集合3.最優(yōu)解：使目標(biāo)函數(shù)達到最大值的可行解4.最優(yōu)值：最優(yōu)解對應(yīng)到目標(biāo)函數(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)的目標(biāo)函數(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ù)表示目標(biāo)，并確定是求極小還是極大；④根據(jù)變量的物理性質(zhì)研究變量是否有非負性。

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

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

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

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

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

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

投資的收益和風(fēng)險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的求解

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

投資的收益和風(fēng)險1.4線性規(guī)劃問題應(yīng)用實例2.投資越分散，投資者承擔(dān)的風(fēng)險越小，即:冒險的投資者會出現(xiàn)集中投資的情況，保守的投資者則盡量分散投資。1.風(fēng)險大，收益也大；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é)果分析

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

x1

x2x3

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

投資的收益和風(fēng)險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目標(biāo)函數(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

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

約束條件：規(guī)格要求4個，供應(yīng)量限制3個配料問題1.4線性規(guī)劃問題應(yīng)用實例利潤=總收入-總成本=三種產(chǎn)品單價*產(chǎn)品數(shù)量-使用的原料單價*原料數(shù)量目標(biāo)函數(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+