清華數(shù)學(xué)建模exp2011-10

1實例 下客戶需 問題1.如何下料最節(jié)省? 問題2.客戶增加需求：本，規(guī)定切割模 過3種。如何下料最節(jié)省5米10原:每根61實例 下客戶需 問題1.如何下料最節(jié)省? 問題2.客戶增加需求：本，規(guī)定切割模 過3種。如何下料最節(jié)省5米10原:每根63x7 yy1y22, y20, y6y2, y3y2xx x4x11xi 0x 演示i線性規(guī)劃（LP）最優(yōu)解：（其他xi為x1=x2=x4=x11=1，x3=0.0833，x6=x10=四舍五入，選4門課程1/2/4/11，共19個學(xué)分,太少向上取整，選7門(加3/6/10)，共27個學(xué)分，太多整數(shù)規(guī)劃一般不能通過解LP松弛問題得到最優(yōu)LP松弛問約束條件：選修課程i時必須選修課程j y 3 63x7y23 112 yy1y22, y20, y6y2, y3y2 65 xxi選課的學(xué)分?jǐn)?shù)，y表示總學(xué)分?jǐn)?shù)實例1：選課問學(xué)分不能少于總學(xué)分的1/6， 過總學(xué)分?jǐn)?shù)的本學(xué)期必修課只有一門（2學(xué)分）；限選課有選課有1門，最少應(yīng)該選幾門課？限選課課12345678學(xué)55443332同時選修2任選課課9學(xué)3332221111同時選修864576基本內(nèi)整數(shù)規(guī)劃 rogramming實例及其數(shù)學(xué)?；驹砼c解分枝定動態(tài)規(guī)LINGO軟件的使大學(xué)數(shù)學(xué)實實驗10整數(shù)規(guī)2下料問題目標(biāo)函數(shù)（總根數(shù) 約束條滿足需 模式合理：每r11x1r12x2r13x3 余料不超過3r21x1r22x2r23x310164r115r216r312下料問題目標(biāo)函數(shù)（總根數(shù) 約束條滿足需 模式合理：每r11x1r12x2r13x3 余料不超過3r21x1r22x2r23x310164r115r216r318r4119r31x1r32x2r33x320164r125r226r328r4219rrr 整數(shù)約束xi,r1ir2ir3ir4i(i=1,2,3)為整數(shù)下料問題增加一種需求：5米10根；切割模式不超過3種現(xiàn)有4種需求：4米50根，5米10根，6米20根，815根，用枚舉法確定合理切割模式，過于復(fù)雜決策變xi~按第i種模式切割的原 根數(shù)r1i,r2i,r3i,r4i~第i種切割模式下，每根原料 對大規(guī)模問題，用模型的約束條件界定合理模下料問當(dāng)余料沒有用處時，通常以總根數(shù)最目標(biāo)2（總根數(shù)）MinZ2 3 6xx約束條件不 53x67xi為整以上兩個模型均是一般整數(shù)線性規(guī)決策變xi~按第i種模式切割的原 根數(shù)目標(biāo)1（總余量）MinZ1 3 6約 3x4x550整數(shù)約束53x67 xi為整滿足需模4米根6米根8米根余20需下料問題 合理切割模為滿足客戶需要，按照哪些種合理模式，每種模切割多少根原料 ，最為節(jié)?。?1.原料 標(biāo) 2.所用原 總根數(shù)最模4根6根8根余料(米20下 切割模按照客戶需要在一根原 上安排切割的一種組合4米1根 6米1 8米1 余料1米4米1根 6米1 6米1 余料3 8米13整數(shù)規(guī)劃問題對應(yīng)的松弛問C 目標(biāo)函數(shù)BOIP可行解對應(yīng)于整點A(2,2)和B(1,1),而最3整數(shù)規(guī)劃問題對應(yīng)的松弛問C 目標(biāo)函數(shù)BOIP可行解對應(yīng)于整點A(2,2)和B(1,1),而最優(yōu)解為A但LP松弛的最優(yōu)解為C(3.5,2.5)對松弛問題的最優(yōu)解（分量）往不是原整數(shù)規(guī)劃問題的最優(yōu)解（甚至不是可行解整數(shù)規(guī)劃問題對應(yīng)的松弛問整數(shù)規(guī)劃問 最優(yōu)松 非最優(yōu) 整松弛問 非整 舍 整原問題 下界（對Min問題松 上界（對Max問題取消整數(shù)規(guī)劃中決策變量為整數(shù)的限制（松弛），應(yīng)的連續(xù)優(yōu)化問題稱為原問題的松弛問題整數(shù)規(guī)劃問題一般形0-1規(guī)劃決策變量只取0或整數(shù)線性規(guī)劃 目標(biāo)和約束均為線性函整數(shù)非線性規(guī)劃(INLP)目標(biāo)或約束中存在非線性函純(全)整數(shù)規(guī)劃(PIP)決策變量均為混合整數(shù)規(guī)劃 決策變量有整數(shù)，也有實 f(xxZ hi(x)0,i1,...,gj(x)0,j1,...,生產(chǎn)批量問題的一般提Tminz(stytctxthtIttIt1xtIty1,xt M是一個充分大的正t0,xt （這里可取M=I0IT0,xt,It混合非線性0-1規(guī)劃？ 混合線性0-1規(guī)劃xtMytyt生產(chǎn)批量問題的一般提ct~時段t生產(chǎn)費(fèi)用(元/件 假設(shè)初始庫存為ht~時段t(末)庫存費(fèi)(元/件st~時段t生產(chǎn)準(zhǔn)備費(fèi)(元dt~時段t市場需求(件T決策變 目 minz(stytctxthtIttxt~時段t生產(chǎn)量 IxII~時段t(末)庫存量；約 t 1,xtyt=1~時段t開工生 yt(y=0~不開工) 0,xt I0IT0,xt,It制訂生產(chǎn)計劃段的總費(fèi)實例3：飲料的生產(chǎn)批量問飲料廠使用同一條生產(chǎn)線輪流生產(chǎn)多種若某周開工生產(chǎn)某種飲料,需支出生產(chǎn)準(zhǔn)備費(fèi)3某種飲料4周的需求生產(chǎn)成本（可變成本50元/箱(50千元/千箱每周每千箱飲料1安排生產(chǎn)計劃滿足每周的需求,使4周總費(fèi)用最1需求量(千箱2233244合4分枝定界算法(Min問題STEP0.令activeset={0}(原問題);U=STEP1.如果activeset=,則已經(jīng)得到原問題的最4分枝定界算法(Min問題STEP0.令activeset={0}(原問題);U=STEP1.如果activeset=,則已經(jīng)得到原問題的最優(yōu)解,結(jié)束;否則從活躍分枝點集合activeset中選擇一個分枝點k；將k從activeset中去掉繼續(xù)STEP2.STEP2.生成k的各分枝i=1,2,…,nk及其對應(yīng)的下界STEP3.對分枝i=1,2,…,nk:如果分枝i得到的是全整數(shù)解且zi<U,則令U=zicurrentbest=i；如果i得到的不是全整數(shù)解且zi<U,則把i加入activeset中.STEP4.轉(zhuǎn)P0x0(3,5)T,z=-2 x1(2,3),z=-7/2 x2(1,3 P2z2=-x x > 無可行解 x6 z0=-*無可行x4(94z0=-分枝定界算法– minzx1 2x1x212x1x22x22x,xZ1x x x x 問題(P1)的LP松弛解為x1(232不是整數(shù)解,最優(yōu)值為z1=-(P3):(P1)加上x2 (P4):(P1)加上x21該問題的LP松弛解為x,)(P1):(P0)加上x (P2):(P0)加上x11線性 minzcTs.t.Axb,x (P線性規(guī)劃松弛定界AZmn,m若在某一時刻，得到一個全整數(shù)解的費(fèi)用為m，則m為原問題的一個上界;否則得該分枝的一個下界，繼續(xù)分枝mincT mincT Ax Axx x（P1）xx0 xx0 xZ xZ整數(shù)規(guī)劃的分枝定界（BB:Branchand基 ：隱式地枚舉一切可行解（“分而治之所謂定界，是指對于每個分枝（或稱子域），要計算問題的最優(yōu)解的下界（對極小化問題）.這些下界用在求解過程中判定是否需要對目前的分枝進(jìn)一步劃分也就是盡可能去掉一些明顯的非最優(yōu)點，避免完全枚舉所謂分枝，就是逐次對解空間（可行域）進(jìn)行劃分；6 o9 6Zmax1 去掉整數(shù)限制后，可行域為點（0,0),(6,0),P(2.25,3.75)圍成的4邊從LP最優(yōu)解經(jīng)過簡單的“移動”不一定得到IP最優(yōu)maxz5x1s.t.x1x25x19x2x1x20且為整5共有個工廠，可以把問題分解為個階段：當(dāng)階段k=時，把手中設(shè)備分配給工廠5共有個工廠，可以把問題分解為個階段：當(dāng)階段k=時，把手中設(shè)備分配給工廠當(dāng)階段k=1時，把手中設(shè)備分配給工廠狀態(tài)變量xkk階段初分配者手中擁有的設(shè)備臺數(shù).由題意可知x0=M，xN+1=0決策變量uk：第k階段分配給工廠k的設(shè)備臺數(shù)0uk狀態(tài)轉(zhuǎn)移方程xk1xku階段的準(zhǔn)則函數(shù) vk(xk,uk)gk(uk應(yīng)用動態(tài)規(guī)劃方法的幾個例資源分配問題：某公司現(xiàn)有臺設(shè)備準(zhǔn)備分配給該公司所屬的家工廠.當(dāng)分配臺uk設(shè)備給工廠k時，工廠k利用這些設(shè)備為公司創(chuàng)造的利潤（假設(shè)非負(fù)）為如何分配設(shè)備資源，使得公司總利潤最大？Nmaxzgk(ukkN ukkuZk可能是非線性整數(shù)規(guī)劃,甚至gk(uk)沒有顯式表達(dá) 工廠設(shè)備數(shù)u12301234046770256803578動態(tài)規(guī)劃基本方逆序遞推 xk1 f1(x1)f2(x2 fk(xk fn(xnfk(xk)min[vk(xk,uk) T(x,u fk(xk)表示第k階段初始狀態(tài)為xk時k后部子過程(階段k,k+1,…,n)的最優(yōu)準(zhǔn)則函k建立動態(tài)規(guī)劃模型的基本過正確劃分階段，選擇階段變量對每個階段，正確選擇狀態(tài)變量xk.選擇狀態(tài)變量時應(yīng)當(dāng)注意兩點：一是要能夠正確描述受控過程的演變特性，二是要滿足無后效性.對每個階段，正確選擇決策變量uk列出相鄰階段的狀態(tài)轉(zhuǎn)移方程：xk+1=Tk(xk,列出按階段可分的準(zhǔn)則函數(shù)V1,n假設(shè)問題的目標(biāo)是極小最優(yōu)化原最優(yōu)子結(jié)構(gòu)（OptimalAnoptimalsolutiontotheproblemcontainswithinitoptimalsolutionstosubproblems.策略上某狀態(tài)以前的狀態(tài)和決策如何，對該狀態(tài)而言，余下的諸決策必 最優(yōu)子策略.”即：最優(yōu)略的任一后部子策略都是最優(yōu)的要條件.整數(shù)規(guī)劃的動態(tài)規(guī)劃例：最短路問 求各點到T的最短 8 L(imincLj)節(jié)點i到節(jié)點T的最短路(i,j)AL(T) 遞推計66具體計算過程如下f5=0; f4=3+50*4+0+0=203; f3= X=(2,5,0,4),最優(yōu)值為561（千元 f2=min{3+50(3+2+4)+1(2+4)+1*4+0,3+50(3+2)+1*2+11,f1=min{3+50(2+3+2+4)+1(3+2+4)+1(2+4)+1*4+0,3+50(2+3)+1*3+18,3+50*2+0+26}=d1 d2 d3 d4 (千件假設(shè)費(fèi)用均非負(fù)，則在I0IT0x可以證明：一定存在滿足條件It1xt0(1tT)的可以只考慮xt0dtdtdt1,Ldtdt1LdT用ft表示當(dāng)t時段初始庫存為0時，從t時段到T時段的 fT1 dtf 1tTtmin[scddhf d t1T1 it1j最優(yōu)值（費(fèi)用）f1應(yīng)用動態(tài)規(guī)劃方法解整數(shù)規(guī)實例3：單產(chǎn)品 力限制的批量問Tminz(stytctxthtItts It1xtItdt t1,2,L,Ty xt t1,2,L,T xtI0xt,It t資源分配問最優(yōu)解u*1u*2u*1,最大利潤為z*f(4)12 推廣：非線性整數(shù)規(guī)劃問題，如 M=4,minz 2 g(u)u2 g(u)2u2 g(u)4u 3k=1時f1(x1)max[g1(u1f2(x2max[g1(u1f2(x1u10u0uf(4)max[g(u)f(4umax{g(0)f(4),g(1)f(3),g(2)f(2),g(3)f(1),g(4)fmax{010,48,65,73,70}資源分配問k=2時：f(x)maxg(uf(xmaxg(uf(xuf(0)max[g(u)f(0u)]g(0)f(0)00f(1)max[g(u)f(1u)]max{g(0)f(1),g(1)ff(2)max[g(u)f(2u)]max{g(0)f(2),g(1)f(1),g(2)fmax{05,23,50}f(3)max[g(u)f(3umax{g(0)f(3),g(1)f(2),g(2)f(1),g(3)ff(4)max[g(u)f(4umax{g(0)f(4),g(1)f(3),g(2)f(2),g(3)f(1),g(4)f資源分配問fk(xk)max[gk(uk)fk1(xk1)],kN,N 0ufN1(xN1)具體計算（例k=3時：f3(x3)max[g3(u3)f4(0)]g3(x3 （增函數(shù)M=4，N=3，邊界條件f4(x4f4(0用fk(xk表示將手中資源xk分配給工廠k,k+1,…,N時的最大利潤，原問題即為f1(M)LINGO軟件的求解過確定常識別類LP 全局優(yōu)化(選1、順序線性規(guī)劃法2、廣義既約梯度法(GRG)(選單LINGO軟件的求解過確定常識別類LP 全局優(yōu)化(選1、順序線性規(guī)劃法2、廣義既約梯度法(GRG)(選單純形內(nèi)點算法(選3、多點搜索(選7實例 下料(問題增加約束，縮小可行域，便于求每根原 長19 815原