線性規(guī)劃課件

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

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

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

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

例

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

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

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

3.決策變量a)若xk0，

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

0

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

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

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

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

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

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

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

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

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

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

投資的收益和風險1.4線性規(guī)劃問題應用實例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ī)劃問題應用實例Matlab計算結果：四、模型1的求解

投資的收益和風險1.4線性規(guī)劃問題應用實例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

五、結果分析

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

x1

x2x3

x40.00600.201900.24000.40000.10910.2212五、結果分析

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

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

有一份說明書，要分別譯成英、日、德、俄四種文字，交甲、乙、丙、丁四個人去完成。因個人專長不同，他們完成翻譯不同文字所需的時間如表所示。應如何分配，使四個人分別完成這四項任務總的時間為最小。指派問題1.4線性規(guī)劃問題應用實例解：設[aij]表示分配問題的效率矩陣，令則指派問題的數學模型一般寫為：指派問題1.4線性規(guī)劃問題應用實例某晝夜服務的公交線路每天各時間段內所需司機和乘務人員數如下：設司機和乘務人員分別在各時間段開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務人員，既能滿足工作需要，又配備最少司機和乘務人員?人力資源分配問題1.4線性規(guī)劃問題應用實例分析：不同上班班次時段的司機和乘務人員數結束時段開工時段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每時段需要的總人數607060502030人力資源分配問題1.4線性規(guī)劃問題應用實例解：設xi

表示第i班次時開始上班的司機和乘務人員數，則有結束時段開工時段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每時段需要的總人數607060502030人力資源分配問題1.4線性規(guī)劃問題應用實例解：設xi

表示第i班次時開始上班的司機和乘務人員數，則有結束時段開工時段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每時段需要的總人數607060502030人力資源分配問題1.4線性規(guī)劃問題應用實例某企業(yè)生產甲、乙、丙三種產品，每一產品均須經過A、B兩道工序。A工序有兩種設備可完成，B工序有三種設備可完成，除甲產品和乙產品的A工序可隨意安排外，其余只能在要求的設備上完成。加工單位產品所需工序時間及其他各項數據的費用有關資料見下表。試制訂利潤最大的產品加工方案。設備產品甲產品乙產品丙費用/有效臺時A1510300/6000A27912321/10000B168250/4000B2411783/7000B37200/4000原料單價(元/件)0.250.350.5銷售單價(元/件)1.252.002.8生產計劃問題1.4線性規(guī)劃問題應用實例設備產品甲產品乙產品丙費用/有效臺時A1510300/6000A27912321/10000B168250/4000B2411783/7000B37200/4000原料單價(元/件)0.250.350.5銷售單價(元/件)1.252.002.8生產計劃問題1.4線性規(guī)劃問題應用實例設備產品甲產品乙產品丙費用/有效臺時A15x110x6300/6000A27x29x712x8321/10000B16x38(x6+x7)250/4000B24x411x8783/7000B37x5200/4000原料單價(元/件)0.250.350.5銷售單價(元/件)1.252.002.8目標函數：利潤=收入-成本-加工費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收入-成本-加工費生產計劃問題1.4線性規(guī)劃問題應用實例約束條件：設備產品甲產品乙產品丙費用/有效臺時A15x110x6300/6000A27x29x712x8321/10000B16x38(x6+x7)250/4000B24x411x8783/7000B37x5200/4000原料單價(元/件)0.250.350.5銷售單價(元/件)1.252.002.8生產計劃問題1.4線性規(guī)劃問題應用實例要做100套鋼架，每套用長為2.9m、2.1m和1.5m的圓鋼各一根。已知原料長7.4m，問應如何下料使所用料最??？方案長度(m)123456782.9120101002.1002211301.531203104合計7.47.37.27.16.66.56.36殘料00.10.20.30.80.91.11.4下料問題1.4線性規(guī)劃問題應用實例解：設采用方案i下料的原料根數為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ī)劃問題應用實例解：設采用方案i下料的原料根數為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ī)劃問題應用實例產品名稱規(guī)格要求單價(元/kg)甲原材料1不少于50%,原材料2不超過25%50乙原材料1不少于25%,原材料2不超過50%35丙不限25某工廠要用三種原料1、2、3混合調配出三種不同規(guī)格的產品甲、乙、丙，數據如下表。問該廠應如何安排生產，使利潤為最大？原材料名稱每天最多供應量單價(元/kg)11006521002536035配料問題1.4線性規(guī)劃問題應用實例解：設xij

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

對于乙：x21，x22，x23；產品乙的產量為x21+x22+x23

對于丙：x31，x32，x33；產品丙的產量為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

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

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

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

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