線性規(guī)劃課件

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

在乙機(jī)床上加工工件1、2、3的數(shù)量分別為x4、x5、x6,1.1線性規(guī)劃問(wèn)題提出例：某廠生產(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è)備計(jì)劃期內(nèi)生產(chǎn)能力分別為12h、16h、15h，又知每生產(chǎn)一件產(chǎn)品Ⅰ可獲利2w，每生產(chǎn)一件產(chǎn)品Ⅱ可獲利3w。問(wèn)該廠應(yīng)安排生產(chǎn)兩種產(chǎn)品各多少件，可使總利潤(rùn)最大。1.1線性規(guī)劃問(wèn)題提出解：設(shè)生產(chǎn)產(chǎn)品I、Ⅱ分別x1、x2件一般線性規(guī)劃問(wèn)題的數(shù)學(xué)模型1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型簡(jiǎn)寫(xiě)形式目標(biāo)函數(shù)約束條件決策變量

1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型向量形式矩陣形式1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型非線性規(guī)劃問(wèn)題轉(zhuǎn)化為線性規(guī)劃問(wèn)題簡(jiǎn)寫(xiě)線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型集合形式1.2線性規(guī)劃問(wèn)題的數(shù)學(xué)模型向量形式矩陣形式標(biāo)準(zhǔn)形式簡(jiǎn)寫(xiě)非標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題的標(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ī)劃問(wèn)題的數(shù)學(xué)模型2.約束條件b)約束條件為“”的情況令x3=12-2x1-2x20

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

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

3.決策變量a)若xk0，

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

0

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

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

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

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

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

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

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

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

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

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

投資的收益和風(fēng)險(xiǎn)1.4線性規(guī)劃問(wèn)題應(yīng)用實(shí)例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)險(xiǎn)1.4線性規(guī)劃問(wèn)題應(yīng)用實(shí)例Matlab計(jì)算結(jié)果：四、模型1的求解

投資的收益和風(fēng)險(xiǎn)1.4線性規(guī)劃問(wèn)題應(yīng)用實(shí)例2.投資越分散，投資者承擔(dān)的風(fēng)險(xiǎn)越小，即:冒險(xiǎn)的投資者會(huì)出現(xiàn)集中投資的情況，保守的投資者則盡量分散投資。1.風(fēng)險(xiǎn)大，收益也大；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)險(xiǎn)1.4線性規(guī)劃問(wèn)題應(yīng)用實(shí)例3.曲線上任一點(diǎn)都表示該風(fēng)險(xiǎn)水平的最大可能收益和該收益要求的最小風(fēng)險(xiǎn)。對(duì)于不同風(fēng)險(xiǎn)的承受能力，選擇該風(fēng)險(xiǎn)水平下的最優(yōu)投資組合。4.在a=0.006附近有一個(gè)轉(zhuǎn)折點(diǎn)，在該點(diǎn)左邊，風(fēng)險(xiǎn)增加很少時(shí)，利潤(rùn)增長(zhǎng)很快，在該點(diǎn)右邊，風(fēng)險(xiǎn)增加很大時(shí)，利潤(rùn)增長(zhǎng)很慢。所以對(duì)于風(fēng)險(xiǎn)和收益沒(méi)有特殊偏好的投資者來(lái)說(shuō)，應(yīng)該選擇曲線的拐點(diǎn)作為最優(yōu)投資組合，投資方案為:風(fēng)險(xiǎn)度收益x0

x1

x2x3

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

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

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

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

表示第i班次時(shí)開(kāi)始上班的司機(jī)和乘務(wù)人員數(shù)，則有結(jié)束時(shí)段開(kāi)工時(shí)段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每時(shí)段需要的總?cè)藬?shù)607060502030人力資源分配問(wèn)題1.4線性規(guī)劃問(wèn)題應(yīng)用實(shí)例解：設(shè)xi

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

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

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

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

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

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

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

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

約束條件：規(guī)格要求4個(gè)，供應(yīng)量限制3個(gè)配料問(wèn)題1.4線性規(guī)劃問(wèn)題應(yīng)用實(shí)例利潤(rùn)=總收入-總成本=三種產(chǎn)品單價(jià)*產(chǎn)品數(shù)量-使用的原料單價(jià)*原料數(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)品名稱單價(jià)(元/kg)原材料名稱單價(jià)(元/kg)甲50165乙35225丙25335配料問(wèn)題1.4線性規(guī)劃問(wèn)題應(yīng)用實(shí)例約束條件（1）：產(chǎn)品規(guī)格要求

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