吉林大學(xué)本科運(yùn)籌學(xué)課件動(dòng)態(tài)規(guī)劃應(yīng)用舉例_第1頁(yè)
吉林大學(xué)本科運(yùn)籌學(xué)課件動(dòng)態(tài)規(guī)劃應(yīng)用舉例_第2頁(yè)
吉林大學(xué)本科運(yùn)籌學(xué)課件動(dòng)態(tài)規(guī)劃應(yīng)用舉例_第3頁(yè)
吉林大學(xué)本科運(yùn)籌學(xué)課件動(dòng)態(tài)規(guī)劃應(yīng)用舉例_第4頁(yè)
吉林大學(xué)本科運(yùn)籌學(xué)課件動(dòng)態(tài)規(guī)劃應(yīng)用舉例_第5頁(yè)
已閱讀5頁(yè),還剩100頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

第七章動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃的基本方法動(dòng)態(tài)規(guī)劃應(yīng)用舉例1清華大學(xué)出版社動(dòng)態(tài)規(guī)劃應(yīng)用舉例

第1節(jié)資源分配問題第2節(jié)生產(chǎn)與存儲(chǔ)問題第3節(jié)*背包問題第4節(jié)*復(fù)合系統(tǒng)工作可靠性問題第5節(jié)排序問題第6節(jié)設(shè)備更新問題第7節(jié)*貨郎擔(dān)問題2清華大學(xué)出版社第1節(jié)資源分配問題所謂分配問題,就是將數(shù)量一定的一種或若干種資源(例如原材料、資金、機(jī)器設(shè)備、勞力、食品等等),恰當(dāng)?shù)胤峙浣o若干個(gè)使用者,而使目標(biāo)函數(shù)為最優(yōu)。3清華大學(xué)出版社1.1資源分配問題設(shè)有某種原料,總數(shù)量為a,用于生產(chǎn)n種產(chǎn)品。若分配數(shù)量xi用于生產(chǎn)第i種產(chǎn)品,其收益為問應(yīng)如何分配,才能使生產(chǎn)n產(chǎn)品的總收入最大?此問題可寫成靜態(tài)規(guī)劃問題:當(dāng)都是線性函數(shù)時(shí),它是一個(gè)線性規(guī)劃問題;當(dāng)是非線性函數(shù)時(shí),它是一個(gè)非線性規(guī)劃問題。但當(dāng)n比較大時(shí),具體求解是比較麻煩的。由于這類問題的特殊結(jié)構(gòu),可以將它看成一個(gè)多階段決策問題,并利用動(dòng)態(tài)規(guī)劃的遞推關(guān)系來(lái)求解。4清華大學(xué)出版社1.1資源分配問題在應(yīng)用動(dòng)態(tài)規(guī)劃方法處理這類“靜態(tài)規(guī)劃”問題時(shí),通常以把資源分配給一個(gè)或幾個(gè)使用者的過程作為一個(gè)階段,把問題中的變量xi為決策變量,將累計(jì)的量或隨遞推過程變化的量選為狀態(tài)變量。5清華大學(xué)出版社1.1資源分配問題設(shè)狀態(tài)變量sk表示分配用于生產(chǎn)第k種產(chǎn)品至第n種產(chǎn)品的原料數(shù)量。決策變量uk表示分配給生產(chǎn)第k種產(chǎn)品的原料數(shù),即uk=xk狀態(tài)轉(zhuǎn)移方程:允許決策集合:令最優(yōu)值函數(shù)表示以數(shù)量為sk的原料分配給第k種產(chǎn)品至第n種產(chǎn)品所得到的最大總收入。因而可寫出動(dòng)態(tài)規(guī)劃的逆推關(guān)系式為:利用這個(gè)遞推關(guān)系式進(jìn)行逐段計(jì)算,最后求得即為所求問題的最大總收入。6清華大學(xué)出版社1.1資源分配問題例1某工業(yè)部門根據(jù)國(guó)家計(jì)劃的安排,擬將某種高效率的設(shè)備五臺(tái),分配給所屬的甲、乙、丙三個(gè)工廠,各工廠若獲得這種設(shè)備之后,可以為國(guó)家提供的盈利如表9-1所示。問:這五臺(tái)設(shè)備如何分配給各工廠,才能使國(guó)家得到的盈利最大。7清華大學(xué)出版社1.1資源分配問題解:

將問題按工廠分為三個(gè)階段,甲、乙、丙三個(gè)工廠分別編號(hào)為1、2、3設(shè)sk表示為分配給第k個(gè)工廠至第n個(gè)工廠的設(shè)備臺(tái)數(shù)。xk表示為分配給第k個(gè)工廠的設(shè)備臺(tái)數(shù)。則為分配給第k+1個(gè)工廠至第n個(gè)工廠的設(shè)備臺(tái)數(shù)。表示為xk臺(tái)設(shè)備分配到第k個(gè)工廠所得的盈利值。表示為sk臺(tái)設(shè)備分配給第k個(gè)工廠至第n個(gè)工廠時(shí)所得到的最大盈利值。因而可寫出逆推關(guān)系式為 8清華大學(xué)出版社1.1資源分配問題下面從最后一個(gè)階段開始向前逆推計(jì)算。第三階段:設(shè)將s3臺(tái)設(shè)備(s3=0,1,2,3,4,5)全部分配給工廠丙時(shí),則最大盈利值為其中x3=s3=0,1,2,3,4,5因?yàn)榇藭r(shí)只有一個(gè)工廠,有多少臺(tái)設(shè)備就全部分配給工廠丙,故它的盈利值就是該段的最大盈利值,如下表。x3s3P3(x3)f3(s3)x3*012345000014412662311113412124512125表中x3*表示使f3(s3)為最大值時(shí)的最優(yōu)決策。9清華大學(xué)出版社1.1資源分配問題第二階段:設(shè)把s2臺(tái)設(shè)備(s2=0,1,2,3,4,5)分配給工廠乙和工廠丙時(shí),則對(duì)每個(gè)s2值,有一種最優(yōu)分配方案,使最大盈利值為其中 因?yàn)榻o乙工廠x2臺(tái),其盈利為p2(x2),余下的s2?x2臺(tái)就給丙工廠,則它的盈利最大值為f3(s2?x2)?,F(xiàn)要選擇x2的值,使取最大值。其數(shù)值計(jì)算如表9-3所示。10清華大學(xué)出版社1.1資源分配問題表9-3012345000010+45+05120+65+410+010230+115+610+411+014240+125+1110+611+411+0161,250+125+1210+1111+611+411+021211清華大學(xué)出版社1.1資源分配問題第一階段:設(shè)把s1臺(tái)(這里只有s1=5的情況)設(shè)備分配給甲、乙、丙三個(gè)工廠時(shí),則最大盈利值為

其中因?yàn)榻o甲工廠x1臺(tái),其盈利為p1(x1),剩下的5?x1臺(tái)就分給乙和丙兩個(gè)工廠,則它的盈利最大值為f2(5?x1)?,F(xiàn)要選擇x1值,使取最大值,它就是所求的總盈利最大值,其數(shù)值計(jì)算如表9-4所示。01234550+213+167+149+1012+513+0210,2表9-412清華大學(xué)出版社1.1資源分配問題然后按計(jì)算表格的順序反推算,可知最優(yōu)分配方案有兩個(gè):(1)由于x1*=0,根據(jù)查表9-3知x2*=2,由故即得甲工廠分配0臺(tái),乙工廠分配2臺(tái),丙工廠分配3臺(tái)。(2)由于x1*=2,根據(jù)查表9-3知x2*=2,由故即得甲工廠分配2臺(tái),乙工廠分配2臺(tái),丙工廠分配1臺(tái)。以上兩個(gè)分配方案所得到的總盈利均為21萬(wàn)元。13清華大學(xué)出版社第一節(jié)資源分配問題例2

有4萬(wàn)元資金,分配給A、B、C三個(gè)項(xiàng)目,每個(gè)項(xiàng)目得到不同的資金能夠產(chǎn)生的效益如下表。如何分配資金,使得獲得的總效益最大。獲得的資金(萬(wàn)元)產(chǎn)生的效益(萬(wàn)噸)ABC0000115131122829303404345451555814清華大學(xué)出版社分析:1、階段32、狀態(tài):每階段待分配資源決策:分配給該階段項(xiàng)目的資源數(shù)量T:xk+1=xk-uk

3、范圍:Q:x1=4,xn+1=00≤xk≤4Dk:0≤uk≤xkun=xn4、階段函數(shù):rk(uk)為該階段項(xiàng)目收益15清華大學(xué)出版社項(xiàng)目A項(xiàng)目B項(xiàng)目Ck=歪1k=鍛2k=挪3k=福4x1=4x2x3x4階段k狀態(tài)隆變量燥:項(xiàng)目檢投資剖前的雁資金楊余額決策載變量沒:項(xiàng)目泳的投晉資u1u2u3決策符允許熟集合巷:項(xiàng)目喂的投劍資的雷范圍0≤利u1≤x10≤離u2≤x20≤貌u3≤x3狀態(tài)裝轉(zhuǎn)移徐方程缸:資威金余趴額和能投資拍額的套關(guān)系階段沫指標(biāo)櫻:rk(uk)每個(gè)殖項(xiàng)目撤不同扔投資哪額的德投資衡的效帝益最優(yōu)舒指標(biāo)位:fk(xk)=ma曠x{護(hù)rk(約uk)+蜘fk+代1(xk+渾1)}終端悠條件致:f4(x4)=兔0x2=x1-u1x3=x2-u2x4=x3-u316清華筐大學(xué)鼓出版燥社x3D3(x3)x4r3(u3)r3(u3)+f4(x4)f3(x3)u3*00000+0=000101100110+0=011+0=111112012210011300+0=011+0=1130+0=3030230123321001130450+0=011+0=1130+0=3045+0=45453401234432100113045580+0=011+0=1130+0=3045+0=4558+0=58584f4(x4)=策0,女k=毅317清華家大學(xué)舉出版躍社x2D2(x2)x3r2(u2)r2(u2)+f3(x3)f2(x2)u2*00000+0=000101100130+11=1113+0=131312012210013290+30=3013+11=2429+0=2930030123321001329430+45=4513+30=4329+11=4043+0=43450401234432100132943550+58=5813+45=5829+30=5943+11=5455+0=5559218清華封大學(xué)乖出版肥社x1D1(x1)x2r1(u1)r1(x1,u1)+f2(x2)f1(x1)u1*401234432100152840510+59=5915+45=6028+30=5840+13=5351+0=51601最優(yōu)嫩解為刺:項(xiàng)目A投資1萬(wàn)元墳,項(xiàng)填目B不投證資,枯項(xiàng)目C投資3萬(wàn)元富。最鄉(xiāng)豐大效低益為60萬(wàn)噸佩。19清華寫大學(xué)觸出版襖社例3分配滔投資縮慧問題某公福司有支資金10萬(wàn)元沒,若藍(lán)投資麥于項(xiàng)乖目k細(xì)(k救=吊1,2,3)的投濱資額建為xk時(shí),砌其收勵(lì)益分梯別為g1(x1)=芝4籍x1,g2(x2)=敗9雹x2,g3(x3)=席2孝x32,問應(yīng)勇該如券何分型配投疑資數(shù)獲額才謊能使要總收慣益最延大?該問卷題表禿面上竿看與攪時(shí)間國(guó)無(wú)明顆顯關(guān)味系,尺其靜犯態(tài)模送型:Ma適x巴z順=4x1+9x2+2x32x1+x2+x3=創(chuàng)10xi≥0(i尾=糟1,2,3)20清華鄭大學(xué)截出版佩社如何睛應(yīng)用早動(dòng)態(tài)洲規(guī)劃鏡方法珠求解膨此類摧靜態(tài)雨規(guī)劃載問題返?一婚般我僚們可乘以人絞為地奴給它瞧賦予贊“時(shí)段”的著概念詢,將聰投資鑄項(xiàng)目起按任蘋意順裳序進(jìn)蝦行排搖序,稀如首奇先考醬慮項(xiàng)女目1的投舟資,屈然后奔考慮管項(xiàng)目2的投粗資……,即停將問陪題人卵為劃住分為判若干坡個(gè)階流段,喬每個(gè)兔階段診只決糞定對(duì)哨一個(gè)鴿項(xiàng)目蘆應(yīng)投席資的駱金額織。這俊樣,汗可以素將上忍述問簽題轉(zhuǎn)蚊化為耍一個(gè)n階段爭(zhēng)決策丙過程頸。分配唱投資湊問題薄的分糠析求伏解如冒下:階段k坡=擺1,2,3,分瓣別表慕示項(xiàng)雪目1,2,3狀態(tài)插變量sk:第k段初泉擁有貼的資抬金總泰量(分配暖給第k至第3個(gè)項(xiàng)仍目的挪資金怪?jǐn)?shù)量)決策差變量xk:第k段的末投資速量(分配竹給第k個(gè)項(xiàng)抖目的鵲資金漁數(shù)量),決策素集合Dk(sk)=xk嗓0造≤xk≤sk狀態(tài)孩轉(zhuǎn)移定方程sk+濁1=sk-xk21清華遇大學(xué)婦出版敏社階段燭指標(biāo)愛值(函數(shù))vk(sk,xk)=gk(xk)定義fk(sk):第k段初圓擁有牛的資擁金總業(yè)量為sk時(shí),筍第k至第3段按秒最優(yōu)鋤投資柴策略淚所獲斃得的腹第k至第3段的攤總收宏益。建立辱動(dòng)態(tài)辮規(guī)劃小基本碎方程梁:(逆序揪遞推孟方程)fk(sk)=max[gk(xk)+fk+1(sk+1)],k=3,2,10≤xk≤skf4(s4)=022清華險(xiǎn)大學(xué)歐出版殊社逆序更遞推讀求解冤動(dòng)態(tài)萍規(guī)劃復(fù)基本屑方程k雜=林3k=歷2f3(s3)=置M諸ax分[2x32+繩f4(s4)]弓=桐M繞ax破[2x32+港0皂]0趙≤x3≤s30倚≤x3≤s3f3*(睛s3)=2s32,xk*恐=s3f2(s2)=前M幻玉ax似[9x2+云f3(s3)]蹦=蔽M蘋ax舟[9x2+2s32]0津≤x2≤s2=偏Ma吧x犬[9x2+2(貪s2–x2)2]可以鳳證明然極大愉值只您可能勒在端季點(diǎn)取犁得,英即:f2(0貪)=2s22f2(s2)=9s2s2>9/腸2時(shí),f2(0路)>f2(s2),此碌時(shí)x2*忠=0(f2(0俯)=2s22)s2<9/避2時(shí),f2(0市)<f2(s2),此勺時(shí)x2*雙=s2(f2(s2)=9s2)23清華耀大學(xué)展出版末社k們=掀1當(dāng)f2(s2)=9s2,f1(1刮0)倆=胖Ma茶x賭[4x1+齊f2(s2)]0今≤x1≤10=漲Ma旦x認(rèn)[9s1–5x1]良=9s1,x1*鳥=0但此域時(shí)s2=s1–x1=1藍(lán)0卸-倒0>9/膽2與s2<9/比2矛盾抹,故墨舍去資。當(dāng)f2(s2)=2s22,f1(1旨0)守=蟲Ma掛x賊[4x1+侄f2(s2)]0然≤x1≤10=炕Ma司x杠[4s1+2(指s1–x1)2]同樣盯可以爽證明梨極大剩值只享可能咐在端參點(diǎn)取適得,霧比較隙兩個(gè)癥端點(diǎn)缸:x1=恐0時(shí),f1(1律0)完=喉20混0,x1=踩10時(shí),f1(1閘0)桿=拆40所以x1*左=娘024清華刮大學(xué)虎出版渾社順序哥確定最優(yōu)員策略s1=購(gòu)10x1*岔=0s2=s1–x1*=觀10>9/顛2x2*雞=醫(yī)0s3=s2–x2*=鏡10x3*爆=笨10最優(yōu)某投資糠方案砍為全擴(kuò)部資插金投奶資于魯?shù)?個(gè)項(xiàng)糾目,色可獲責(zé)最大境收益20虛0萬(wàn)元除。25清華惑大學(xué)微出版喝社1.賤1資源傳分配朝問題資源賓連續(xù)童分配挨問題設(shè)有奸數(shù)量哲為s1的某屠種資浪源,奧可投缸入A和B兩種叮生產(chǎn)繞。第壞一年若以閑數(shù)量u1投入隔生產(chǎn)A,剩反下的綱量s1?u1就投火入生伸產(chǎn)B,則哲可得叢收入慨為其中g(shù)(頸u1)和h(彈u1)為已濤知函米數(shù),疼且g(填0)調(diào)=h批(0萌)=男0。這幟種資狼源在薄投入A、B生產(chǎn)豈后,紹年終朽還可糾回收控再投證入生湊產(chǎn)。通設(shè)年駁回收間率分乓別為0<a<1和0<b<1,則才在第賞一年啟生產(chǎn)課后,或回收脹的資之源量紫合計(jì)趴為第二塑年再乎將資裕源數(shù)送量s2中的u2和s2?u2分別途再投刑入A、B兩種拌生產(chǎn)躍,則均第二癥年又然可得屈到收皺入為如此輔繼續(xù)輕進(jìn)行n年,種試問食:應(yīng)泊當(dāng)如禾何決央定每雨年投鎖入A生產(chǎn)口的資扎源量才能渾使總我的收捎入最衫大?26清華祝大學(xué)絞出版檢社1.蔽1資源指分配關(guān)問題此問棚題寫明成靜滋態(tài)規(guī)謀劃問旁題為27清華聾大學(xué)茅出版彎社1.李1資源寫分配幅問題下面盜用動(dòng)玻態(tài)規(guī)嗽劃方姥法來(lái)專處理段。設(shè)sk為狀攀態(tài)變躬量,窄它表窯示在煎第k階段(第k年)可投階入A、B兩種個(gè)生產(chǎn)傷的資犁源量。uk為決釀策變?cè)?,訂它表?jié)示在予第k階段(第k年)用于A生產(chǎn)蒜的資供源量輝,則sk?uk表示勇用于B生產(chǎn)崖的資召源量普。狀態(tài)誤轉(zhuǎn)移霞方程喊為最優(yōu)拳值函愛數(shù)fk(sk)表示快有資哨源量sk,從領(lǐng)第k階段袍至第n階段膏采取伴最優(yōu)皺分配著方案抖進(jìn)行廊生產(chǎn)對(duì)后所盞得到蟻的最少大總償收入掘。因此誼可寫哄出動(dòng)訪態(tài)規(guī)角劃的則逆推添關(guān)系稈式為最后悼求出f1(s1)即為烘所求皂問題鍵的最敞大總氧收入己。28清華藝大學(xué)蠻出版濫社1.新1資源乖分配行問題例4機(jī)器庸負(fù)荷螺分配尖問題某種凱機(jī)器逆可在將高低流兩種季不同托的負(fù)品荷下尾進(jìn)行遵生產(chǎn)針,設(shè)脅機(jī)器沾在高時(shí)負(fù)荷驕下生隆產(chǎn)的息產(chǎn)量混函數(shù)銜為g=8改u1,其墨中u1為投勝入生艦產(chǎn)的示機(jī)器希數(shù)量錫,年飼完好噴率a=0比.7;在店低負(fù)獅荷下系生產(chǎn)斃的產(chǎn)傍量函關(guān)數(shù)為h=洞5y,其習(xí)中y為投博入生性產(chǎn)的姨機(jī)器縫數(shù)量謀,年遞完好陵率為b=0救.9。假定修開始敘生產(chǎn)誓時(shí)完零好的盒機(jī)器缺數(shù)量s1=1丹00紡0臺(tái),烏試問晚每年名如何仗安排秀機(jī)器悉在高樸、低慣負(fù)荷種下的益生產(chǎn)瓦,使粉在五億年內(nèi)斧生產(chǎn)的的產(chǎn)抵品總捉產(chǎn)量胖最高客。29清華連大學(xué)柴出版掌社1.帶1資源厘分配航問題構(gòu)造好這個(gè)技問題揭的動(dòng)阿態(tài)規(guī)派劃模躲型:設(shè)階丟段序已數(shù)k表示宗年度替。狀態(tài)任變量sk為第k年度樣初擁界有的貓完好加機(jī)器暮數(shù)量覆,同羽時(shí)也箱是第k?蜘1年度淚末時(shí)話的完菊好機(jī)味器數(shù)班量。決策圾變量uk為第k年度楚中分諒配高其負(fù)荷叢下生貨產(chǎn)的小機(jī)器臟數(shù)量柜,于卻是sk?uk為該描年度夸中分懶配在義低負(fù)寺荷下迷生產(chǎn)踢的機(jī)塌器數(shù)垮量。這里sk和uk均取潤(rùn)連續(xù)魄變量揉,它惑們的晚非整婆數(shù)值腹可以悼這樣樣理解乎,如sk=0西.6,就處表示券一臺(tái)曬機(jī)器部在k年度傷中正篩常工且作時(shí)鑒間只付占6/市10;uk=0花.3,就羽表示恩一臺(tái)永機(jī)器眾在該俊年度槽只有3/拳10的時(shí)法間能探在高臨負(fù)荷抽下工跪作。狀態(tài)繭轉(zhuǎn)移絡(luò)方程迫為k段允膠許決覽策集豆合為設(shè)為第k年度陽(yáng)的產(chǎn)歡量,腥則故指見標(biāo)函貓數(shù)為30清華國(guó)大學(xué)猴出版峽社1.且1資源剩分配元問題令最勵(lì)優(yōu)值拳函數(shù)fk(sk)表示哲由資迫源量sk出發(fā)溜,從征第k年開跨始到赴第5年結(jié)財(cái)束時(shí)雁所生崗產(chǎn)的袋產(chǎn)品未的總版產(chǎn)量陪最大組值。繁因而丑有逆違推關(guān)康系式宰:31清華煎大學(xué)集出版璃社1.茶1資源辯分配售問題從第5年度位開始雁,向些前逆憤推計(jì)安算。當(dāng)k=懷5時(shí),驅(qū)有因f5是u5的線辰性單樣調(diào)增德函數(shù)鍛,故庭得最海大解u5*,相睡應(yīng)的惠有32清華宴大學(xué)拔出版孕社1.戴1資源吹分配脊問題當(dāng)k=抬4時(shí),框有故得循最大別解,u4*=熔s4,相械應(yīng)的勤有依此暑類推池,可鞭求得因s1=1加00兔0,故33清華乖大學(xué)染出版乓社1.簡(jiǎn)1資源萍分配寇問題計(jì)算襖結(jié)果俱表明詠:最滋優(yōu)策揮略為即前兩滔年應(yīng)驚把年逢初全停部完從好機(jī)獻(xiàn)器投修入低雹負(fù)荷嫁生產(chǎn),后雹三年緒應(yīng)把陰年初騙全部陜完好薄機(jī)器禁投入事高負(fù)憑荷生瞞產(chǎn)。粒這樣端所得梢的產(chǎn)赤量最個(gè)高,截其最消高產(chǎn)亞量為23抖70摟0臺(tái)。34清華胡大學(xué)勿出版巧社1.形1資源豎分配德問題在得刻到整橫個(gè)問舌題的屢最優(yōu)穗指標(biāo)投函數(shù)倉(cāng)值和鴨最優(yōu)舉策略島后,金還需燭反過碌來(lái)確蓮定每主年年照初的貼狀態(tài)慨,即斥從始慨端向居終端鋸遞推泊計(jì)算活出每行年年匯初完商好機(jī)變器數(shù)煎。已膊知s1=1姜00赤0臺(tái),暮于是撇可得35清華廈大學(xué)障出版極社第2節(jié)乓生虜產(chǎn)與墻存貯才問題在生鋪產(chǎn)和稍經(jīng)營(yíng)憂管理貼中,釣經(jīng)常角遇到迷要合煮理地兼安排諸生產(chǎn)(或購(gòu)梯買)與庫(kù)庭存的抬問題介,達(dá)霞到既達(dá)要滿準(zhǔn)足社園會(huì)的全需要婦,又邊要盡氏量降征低成取本費(fèi)蔬用。膏因此乖,正在確制構(gòu)定生獻(xiàn)產(chǎn)(或采泉購(gòu))策略閱,確飛定不靠同時(shí)末期的續(xù)生產(chǎn)令量(或采鴿購(gòu)量)和庫(kù)過存量慘,以捧使總的聰生產(chǎn)勺成本過費(fèi)用臣和庫(kù)熔存費(fèi)逢用之鏡和最恭小,這架就是階生產(chǎn)靠與存燥儲(chǔ)問拳題的泉最優(yōu)絞化目緊標(biāo)。36清華享大學(xué)程出版眾社企業(yè)深一年軟中的居產(chǎn)品方生產(chǎn)澡往往故是分遍期分策批生尤產(chǎn)的洪。組織財(cái)每批斯產(chǎn)品雷的生喊產(chǎn),糕都要沈花費(fèi)們一些著生產(chǎn)墓準(zhǔn)備滴費(fèi)和睡存貯陡費(fèi)用嚷。若某謀一時(shí)編期增盜大生徐產(chǎn)批飯量則爸可減憑少生渠產(chǎn)批淡次,保從而總降低且生產(chǎn)層成本抗。與此關(guān)同時(shí)早,批館量大立了,若必然嗚增加宅庫(kù)存繪而使循存貯億費(fèi)用改增加康。在企質(zhì)業(yè)產(chǎn)銹品的忙生產(chǎn)棄成本孝、存隔貯費(fèi)煉用、攀市場(chǎng)帆需求伸量確劈燕定的含情況批下,浸正確頑計(jì)劃晴各時(shí)在期的言生產(chǎn)搭量,跨既滿斗足市焰場(chǎng)需離求,絮又使遭總支娛出最卻少,伶這是藍(lán)一個(gè)碎多階售段決東策問遮題。生產(chǎn)所與存震儲(chǔ)問暢題37清華殲大學(xué)舞出版攝社2.鏡1生產(chǎn)嬸與存燒貯問編題設(shè)某禁公司敢對(duì)某受種產(chǎn)坑品要哄制定炊一項(xiàng)貝多階右段的藍(lán)生產(chǎn)(或購(gòu)腔買)計(jì)劃悉。已恐知它鞭的初氧始庫(kù)俗存量民為零鹿,每食階段悄生產(chǎn)(或購(gòu)攔買)該產(chǎn)順品的梢數(shù)量尺有上避限的預(yù)限制俘;每?jī)€階段次社會(huì)迎對(duì)該務(wù)產(chǎn)品廊的需歉求量紛是已系知的牧,公沾司保若證供傳應(yīng);喇在n階段茄末的岡終結(jié)詞庫(kù)存貝量為填零。館問該伐公司勤如何蝕制定峰每個(gè)影階段捏的生妹產(chǎn)(或采招購(gòu))計(jì)劃寇,從負(fù)而使債總成檔本最陣小。38清華雷大學(xué)鋼出版蛋社生產(chǎn)印計(jì)劃宜周期息分為n個(gè)階仁段,辜即k=缺1~炎n;已知投最初授庫(kù)存射量為S1=0;階段四需求喪量為dk;單位沃產(chǎn)品社的消辦耗費(fèi)餅用為L(zhǎng)k;單位聲產(chǎn)品幕的階紀(jì)段庫(kù)肺存費(fèi)茫用為hk;倉(cāng)庫(kù)巴容量緞為Mk;階段迷生產(chǎn)桌能力碑為Bk;生產(chǎn)遙的準(zhǔn)撕備費(fèi)輔用為房誠(chéng):生產(chǎn)—存貯盆問題因原型39清華難大學(xué)壞出版身社問應(yīng)血如何組安排乏各階圈段產(chǎn)釋量,捆使計(jì)珠劃期鏡總費(fèi)漢用最盤小。1、階激段2、狀唇態(tài)變鵲量sk階段k的初盾始庫(kù)企存量駕,決策養(yǎng)變量uk階段k的生璃產(chǎn)量末。T:期末背庫(kù)存=期初健庫(kù)存+生產(chǎn)跌量-本期助需求40清華槐大學(xué)既出版槽社即階段k的庫(kù)惕存既腿不能碑超過擋庫(kù)存憤容量,也不孔應(yīng)超艘過階忍段k至階稠段n的需揉求總況量(dk+dk+失1+…兇+dn),否則漂將與Sn+慌1=0的假狹設(shè)相做違背吸。3Sk的范毒圍:館計(jì)劃僻初期碑的庫(kù)綿存量S1是已哈知的沉,末吼期的嗎庫(kù)存斜量通錢常也常是給瞞定的毅,為凈簡(jiǎn)單廣起見辣這里忍假定sn+邪1=0,于是消問題搶是始仰端末陜端固刪定的艘問題社。關(guān)聰于狀常態(tài)sk的約按束條賤件是41清華雨大學(xué)播出版慢社庫(kù)容量限制以后需求缺口本期需求缺口uk的范股圍:誕自身辜的要旨求及券由T與Q確定塞的范酒圍。洲階段仿產(chǎn)量塞要在版不超賤過生鋼產(chǎn)能露力Bk的條桑件下剪,充紀(jì)分滿拘足該繁階段肢的需固求dk,同時(shí)臨還要安滿足捉計(jì)劃描末期開的庫(kù)為存量悄為0的要富求。辦因此怎關(guān)于方?jīng)Q策型變量雨的約笨束條佩件就喘是42清華統(tǒng)大學(xué)圓出版蹄社4、階役段k的生點(diǎn)產(chǎn)費(fèi)腿用是庫(kù)存楊費(fèi)用注意uk自身迷的特篩殊要軍求可欄能反覺過來(lái)言作用喬于Sk,比如衰庫(kù)存術(shù)上限沈的要觸求43清華床大學(xué)免出版覺社例5某工笛廠與披用戶底簽訂扇了4個(gè)月?lián)u的交化貨合吃同如督表所禿示該廠柔生產(chǎn)策能力御為每零月5萬(wàn)件謙,倉(cāng)厲庫(kù)的來(lái)存貨帶能力滿為4萬(wàn)件花。已知和生產(chǎn)供費(fèi)用從為c=1千元/萬(wàn)件拿,在類進(jìn)行兔生產(chǎn)期的月衰份,眼工廠肚要支根出固喬定費(fèi)泳用b=2千元單,每法月倉(cāng)勒庫(kù)保闖管費(fèi)己用h=0.截2千元/萬(wàn)件/月。假定1月初劈燕無(wú)存莊貨,啞要求4月底牧交貨兔后無(wú)量存貨鳥,試狐問應(yīng)標(biāo)在每嗚月各船生產(chǎn)白多少捧件產(chǎn)遼品,跨才能妖滿足虜交貨唇任務(wù)罷,又侄使總阿費(fèi)用旁最小鑰?月1234需求量dk(萬(wàn)件)323244清華疑大學(xué)品出版哥社動(dòng)態(tài)樸規(guī)劃繪的數(shù)壟學(xué)模巴型每個(gè)酒月為內(nèi)一個(gè)醉階段狂,即僚階段飲變量k=亮1,予2,臥3,肢4分別插表示杏這四殊個(gè)月;狀態(tài)住變量sk表示第k月初及的產(chǎn)伶品庫(kù)闖存量殃,0≤sk≤4;決策儲(chǔ)變量xk表示第k月的夾生產(chǎn)痕量盒,計(jì)允襖許決甜策集闊合Xk(sk)=晃{xk︱0≤xk≤5};狀態(tài)掏轉(zhuǎn)移策方程替為sk+莖1=sk+xk–dk;階段披指標(biāo)vk(sk,xk)表示獸第k月的豎費(fèi)用魔:蹈本月混若不旺安排甘生產(chǎn)減,則薪僅需蜓支出秀保管肚費(fèi);獲本月呼若安輪排生學(xué)產(chǎn),恩則需匪支出財(cái)生產(chǎn)舍費(fèi)用嫁和固帆定費(fèi)黎,同鉆時(shí)還敲需交乏付保搏管費(fèi)胃。當(dāng)xk=0時(shí),vk(sk,xk)=h爬·sk=0.籍2sk當(dāng)xk>0時(shí),vk(sk,xk)=b+壤c·罷xk+h造·sk=2+佛xk+0.男2sk最優(yōu)站指標(biāo)轉(zhuǎn)函數(shù)fk(sk)表示盟第k階段廳從sk開始離到最儀后階紛段采逮用最呈優(yōu)生叫產(chǎn)策遍略實(shí)何現(xiàn)的向最低融生產(chǎn)止費(fèi)用趟。45清華隆大學(xué)氏出版距社逆序練求解K=尾4x4s4v4

(s4,x4)=0.2

s4v4

(s4,x4)=2+

x4+0.2

s4f4

(s4)x4*012012----4--3.2--0.4----43.20.4210d4=2,4月末帥無(wú)庫(kù)蠻存則s5=0,狀態(tài)溝轉(zhuǎn)移扎方程s5=s4+x4–d4,則s4=d4–x4=2–x4x4≥0筒,則s4=2–x4={幼0,瓜1,哈2}s4≥0翼,則x4=2–s4={0菌,1殃,2塊}46清華碎大學(xué)險(xiǎn)出版釀社k=誤3x3s30.2

s3+f4(s4)v3

(s3,x3)+f4(s4)=2+

x3+0.2

s3+f4(s4)f3

(s3)x3*012340123457.46.65.84.64.54300------9.09.27.4----8.28.46.6----7.47.65.8----4.66.85.0------44.2--------d3=3,0≤s4≤2,狀態(tài)串轉(zhuǎn)移候方程s4=s3+x3–d3,則0≤s3+x3–d3≤2,即3≤s3+x3≤50≤s3≤4,溪?jiǎng)ts3={故0,季1,葬2,棋3,福4}生產(chǎn)至能力繩限制0≤x3≤5,則x3={0玻,1聽,2費(fèi),3律,4欲,5悼}4月在框庫(kù)存谷量為s4時(shí)的山最低汪生產(chǎn)繪成本47清華腫大學(xué)清出版長(zhǎng)社k=馳2x2s20.2

s2+f3(s3)v2

(s2,x2)+f3(s3)=2+

x2+0.2

s2+f3(s3)f2

(s2)x2*01201234511.410.67.8210----11.411.611.811.6--10.610.811.010.811.27.810.010.210.010.4--d2=2,0≤s3≤4,狀態(tài)娘轉(zhuǎn)移亦方程s3=s2+x2–d2,則0≤s2+x2–d2≤4,即2≤s2+x2≤6s1=0,沒則s2=s1+x1–d1=x1–3;x1≤5,則s2≤2生產(chǎn)仁能力培限制0≤x2≤5,則x2={0壘,1扔,2攝,3鬧,4徑,5阿}3月在芝庫(kù)存預(yù)量為s3時(shí)的減最低陸生產(chǎn)飯成本48清華肆大學(xué)躍出版溜社k=獲1x1s1v1(s1,x1)+f2(s2)=2+x2+0.2s2+f2(s2)f1(s1)x1*3452月在閉庫(kù)存濕量為s2時(shí)的下最低非生產(chǎn)件成本014福.85順序牽遞推億,得服出結(jié)止論第1月生兩產(chǎn)5萬(wàn)件s2=s1+x1–d1=0惡+5請(qǐng)-3女=2,第2月不徐生產(chǎn)s3=s2+x2–d2=2城+0恐-2嗓=0,第3月生妖產(chǎn)5萬(wàn)件s4=s3+x3–d3=0托+5或-3之=2,第4月不澆生產(chǎn)16.416.614.8d1=3,s1=0,狀態(tài)魂轉(zhuǎn)移性方程涌則s2=s1+x1–d1=x1–3;s2≥0,則x1≥3,生產(chǎn)嚇能力連限制x1≤5,則3≤x1≤5,x1={3厘,4浴,5艦}49清華補(bǔ)大學(xué)垂出版煉社例6某車聽間需代要按加月在鑰月底宏供應(yīng)叮一定蛋數(shù)量燒的某寒種部蹤蝶件給基總裝途車間齒,由沉于生匯產(chǎn)條裂件的療變化沖,該秩車間土在各笑月份嘴中生辭產(chǎn)每捏單位居這種麗部件召所需迎耗費(fèi)警的工東時(shí)不回同,東各月界份的面生產(chǎn)麻量于倍當(dāng)月勸的月馳底前絹,全籍部要存入茄倉(cāng)庫(kù)確以備忘后用。已允知總絕裝車臘間的星各個(gè)潮月份蒙的需求騎量以及腔在加碎工車域間生句產(chǎn)該撲部件撫每單膏位數(shù)盟量所格需工煩時(shí)數(shù)愧如表9-欣7所示燒。月份k0123456需求量dk0853274單位工時(shí)ak111813172010設(shè)倉(cāng)神庫(kù)容養(yǎng)量限勿制為H=副9,開阿始庫(kù)怕存量污為2,期判終庫(kù)演存量怪為0,需灑要制航定一棒個(gè)半丹年的林逐月連生產(chǎn)挑計(jì)劃職,既孫使得重滿足勞需要兄和庫(kù)剪容量影的限廉制,陵又使鞭得生胞產(chǎn)這懶種部宴件的總耗豬費(fèi)工蓋時(shí)數(shù)為最悉少。表9-屆750清華馬大學(xué)典出版巡壽社解:按月協(xié)份劃煌分階余段,欲用可她表示敲月份打序號(hào)臣。設(shè)狀斬態(tài)變劉量sk為第k段開氧始時(shí)(本段御需求互量送謊出之販前,疏上段鞋產(chǎn)品箏送入幻玉之后)部件墊庫(kù)存擁量。(現(xiàn)存瞇的能篩滿足遲當(dāng)月扮需求)決策銅變量uk為第k段內(nèi)湖的部購(gòu)件生朋產(chǎn)量程。狀態(tài)凝轉(zhuǎn)移奮方程捕:且故允緊許決扣策集康合為51清華嗚大學(xué)塊出版騎社最優(yōu)同值函昌數(shù)橡表忘示在麗第k段開鋒始的柴庫(kù)存答量為sk時(shí),佛從第k段至音第6段所冰生產(chǎn)犯部件座的最疲小累蝦計(jì)工穿時(shí)數(shù)傘。因孟而可蘭寫出轎逆推襖關(guān)系剪式為當(dāng)k=俯6時(shí),鋤因要巧求期砍終庫(kù)扭存量?jī)|為0,即s7=0。因能每月良的生勺產(chǎn)是古供應(yīng)纏下月決的需召要,斃故第6個(gè)月榴不用庫(kù)生產(chǎn)銷,即u6=0。因捷此f6(s6)=液0,而困由(9備-9飄)式有當(dāng)k=掠5時(shí),痛由(9暢-9干)式有故及最婆優(yōu)解52清華砌大學(xué)漲出版態(tài)社當(dāng)k=掙4時(shí),天有其中u4的允垮許決校策集營(yíng)合D4(s4)由(9耀-1撒1)式確掏定為由,故別有又,因謠而而由(9惜-1獵0)式知惑:,所犧以為故得及最凱優(yōu)解53清華騾大學(xué)瓜出版諸社當(dāng)k=罩3時(shí),由(9縫-1堤1)式得D3(s3)為故得及最緊優(yōu)解當(dāng)k=盼2時(shí),其中D2(s2)為故得及最萄優(yōu)解54清華懲大學(xué)姜出版票社當(dāng)k=五1時(shí),其中D1(s1)為故得及最高優(yōu)解當(dāng)k=姓0時(shí),其中D0(s0)為故得及最啞優(yōu)解因s0=2,所擦以f0=3糖57和u0*=道7再按已計(jì)算烤順序桂反推蚊,即盤得各焰階段殘最優(yōu)天決策褲為:所以憤,0至5月最鼠優(yōu)生誓產(chǎn)計(jì)摟劃為滔:7,4,9,3,0,4,最替小總唐工時(shí)初為35該7。55清華優(yōu)大學(xué)奇出版鼻社2.滴2不確副定性螺的采朽購(gòu)問啟題在實(shí)幅際問崇題中幅,還瀉會(huì)遇共到某凡些多討階段槽決策窩過程震,其挖狀態(tài)再轉(zhuǎn)移熔不是痛完全也確定替的,胸出現(xiàn)瓶了隨慢機(jī)性飛因素限,狀治態(tài)轉(zhuǎn)藥移是伶按照框某種饒已知史概率筒分布懸取值羨的。具有吉這種頂性質(zhì)獅的多龍階段躺決策壤過程叼稱為臣隨機(jī)記性決訂策過緞程。用動(dòng)鐵態(tài)規(guī)唱?jiǎng)澐绞莘ㄒ叉@可處鄰理這響類隨啄機(jī)性覆問題餡,又米稱為伴隨機(jī)帆性動(dòng)鉤態(tài)規(guī)贊劃。56清華怕大學(xué)抹出版育社2.轎2不確痕定性投的采商購(gòu)問娛題例7采購(gòu)授問題蟻。某齊廠生惡產(chǎn)上決需要拼在近洲五周培內(nèi)必序須采裳購(gòu)一身批原查料,董而估勇計(jì)在相未來(lái)窗五周嶺內(nèi)價(jià)罪格有轟波動(dòng)性,其壯浮動(dòng)部?jī)r(jià)格床和概背率已帳測(cè)得窯如表9-患8所示察。試孔求在極哪一投周以桌什么縮慧價(jià)格尸購(gòu)入斤,使斬其采雙購(gòu)價(jià)廉格的寒?dāng)?shù)學(xué)仰期望耍值最篇小,蒼并求世出期挺望值茄。單價(jià)概率5000.36000.37000.4表9-管857清華談大學(xué)柜出版懶社2.遞2不確羅定性足的采餓購(gòu)問巨題解:價(jià)格迷是一向個(gè)隨選機(jī)變櫻量,納按某低種已睛知的附概率較分布青取值伍。用恐動(dòng)態(tài)融規(guī)劃章方法娘處理予,按欲采購(gòu)浸期限5周分候?yàn)?個(gè)階弓段,捉將每障周的嬸價(jià)格很看作島該階且段的勸狀態(tài)耳。設(shè)yk——狀態(tài)儲(chǔ)變量增,表穿示第k周的報(bào)實(shí)際而價(jià)格然。xk——決策歉變量運(yùn),xk=1時(shí)表槐示第k周決棕定采騾購(gòu);xk=0時(shí)表洪示第k周決汗定等甜待。ykE——第k周決久定等葵待,終而在覆以后團(tuán)采取煤最優(yōu)腿決策冊(cè)時(shí)采蘇購(gòu)價(jià)暫格的樂期望叢值。fk(yk)—飲—第k周實(shí)塑際價(jià)命格為yk時(shí),楊從第k周至令第5周采近取最鄙優(yōu)決本策所共得的嶺最小岡期望頂值因而潑可寫騙出逆盤序遞魚推關(guān)蜻系式劈燕為其中由ykE和fk(yk)的定條義可乞知:并且或得出買最優(yōu)印決策呢為:58清華投大學(xué)郵出版上社2.藝2不確儲(chǔ)定性鍬的采吧購(gòu)問永題從最逃后一那周開楊始,友逐步特向前夾遞推作計(jì)算鋼,具茅體計(jì)摘算過俊程如棒下。k=揚(yáng)5時(shí),翼因,故文有即在山第五龍周時(shí)伸,若暴所需籍的原托料尚楚未買腿入,蟲則無(wú)奪論市抓場(chǎng)價(jià)究格如刊何,榮都必些須采襖購(gòu),鞠不能員再等茶。k=劍4時(shí),而由(9獎(jiǎng)-1做6)式可島知于是寬,由(9怕-1舊3)式得由(9脅-1催7)式,任第4周最倆優(yōu)決客策為59清華擊大學(xué)央出版陸社2.編2不確撈定性老的采傾購(gòu)問洪題同理窄求得所以60清華賴大學(xué)號(hào)出版捷社2.叛2不確灶定性蹈的采踐購(gòu)問修題所以61清華夢(mèng)大學(xué)房誠(chéng)出版指社2.咐2不確圓定性暈的采廚購(gòu)問裂題所以由上蕉可知臭,最住優(yōu)采問購(gòu)策烤略為拴:在使第一朽、二鵝、三窗周時(shí)波,若尾價(jià)格值為50流0就采角購(gòu),戰(zhàn)否則薯應(yīng)該歸等待封;在戚第四纖周時(shí)瘦,價(jià)稍格為50獵0或60澇0應(yīng)采然購(gòu),燈否則坡就等挪待;執(zhí)在第掩五周競(jìng)時(shí),捕無(wú)論床什么金價(jià)格沖都要供采購(gòu)裂。62清華武大學(xué)佩出版框社2.捧2不確安定性煩的采葉購(gòu)問宇題依照梅上述冒最優(yōu)桶策略夠進(jìn)行論采購(gòu)株時(shí),意價(jià)格(單價(jià))的數(shù)慚學(xué)期歸望值刷為f1(s1)=許0.井3*淡f1(5砌00憐)+犬0.趣3*王f1(6拌00受)+衫0.親4*坑f1(7恢00憤)=0絨.3巖*5申00耀+0盆.3彩*5瀉36緞.2耳6+宏0.腦4*翻53排6.縮慧26≈5遮2563清華始大學(xué)涌出版虜社第3節(jié)早背改包創(chuàng)問耐題有一瓦個(gè)人量帶一節(jié)個(gè)背馳包上腐山,倚其可詞攜帶削物品必重量警的限驢度為a公斤設(shè)。設(shè)虜有n種物用品可鋤供他果選擇纏裝入偽背包至中,獎(jiǎng)這n種物倍品編蔽號(hào)為1,2,…,n。已劑知第i種物劣品每冷件重競(jìng)量為wi公斤淚,在迅上山心過程盒中的敞作用(價(jià)值)是攜彩帶數(shù)些量xi的函滅數(shù)ci(xi)。問懲此人睛應(yīng)如由何選羅擇攜慣帶物尿品(各幾箭件),使電所起答作用(總價(jià)克值)最大輕。這尖就是罩著名勾的背亦包問鄰題。類似煙的問扣題有法工廠躁里的脈下料移問題闖,運(yùn)熄輸中戰(zhàn)的貨謹(jǐn)物裝億載問悔題,仰人造薄衛(wèi)星稍內(nèi)的冠物品賽裝載混問題次等等位。64清華始大學(xué)妄出版共社第3節(jié)銳背芒包熱問利題設(shè)xi為第i種物叉品的你裝入配件數(shù)奸,則特問題近的數(shù)幸學(xué)??匦蜑樗沁B一個(gè)整數(shù)澆規(guī)劃送問題。如柳果xi只取0或1,又梯稱為0—骨1背包始問題共。下私面用侵動(dòng)態(tài)皇規(guī)劃乳方法易來(lái)求子解。65清華皂大學(xué)螞出版跑社第3節(jié)多背驢包涉問噸題設(shè)按縮慧可裝確入物膏品的n種類演劃分斜為n個(gè)階姐段。狀態(tài)鎖變量w表示蚊用于撐裝第1種物旁品至來(lái)第k種物讓品的復(fù)總重區(qū)量。決策拜變量xk表示繳裝入邀第k種物蜓品的扔件數(shù)嶼。則畢狀態(tài)疾轉(zhuǎn)移億方程最為允許胞決策防集合懶為最優(yōu)麗值函球數(shù)fk(w)是當(dāng)搭總重斜量不兄超過w公斤循,背罷包中倍可以凈裝入鎖第1種到奧第k種物遼品的不最大局使用尾價(jià)值循。即66清華租大學(xué)噸出版甩社第3節(jié)予背皇包吧問同題因而盛可寫足出動(dòng)態(tài)樓規(guī)劃噴的順榜序遞塌推關(guān)姓系為很:然后府,逐酸步計(jì)風(fēng)算出及相材應(yīng)的塊決策僑函數(shù)最后譜得出川的就是荒所求書的最捷大價(jià)虹值,董其相頌應(yīng)的志最優(yōu)屬策略尼由反廁推運(yùn)蔥算即簡(jiǎn)可得揭出。67清華楚大學(xué)且出版愁社第3節(jié)夕背棵包定問落題例8解:用動(dòng)棵態(tài)規(guī)差劃方丈法來(lái)筒解,漸此問嫁題變偉為求f3(1陵0)。68清華價(jià)大學(xué)皮出版符社第3節(jié)芬背造包策問贏題由此桐看到敗,要暫計(jì)算f3(1各0),必農(nóng)須先捷計(jì)算觸出69清華赴大學(xué)吩出版鍬社第3節(jié)起背值包芹問也題為了么要計(jì)岡算出f2(1旗0)冷,f2(5墓),f2(塘0),必恭須先議計(jì)算煉出f1(1雷0)僑,f1(6勁),f1(5扮),f1(2仆),f1(1孕),f1(0戲),一佩般地晚有相應(yīng)拌的最退優(yōu)決確策為x1=[w/仔3],愚于是畫得到70清華評(píng)大學(xué)辣出版鉗社第3節(jié)架背鋤包斗問臂題從而故最樹后得針到所以疏,最稅優(yōu)裝若入方鳥案為最大它使用盈價(jià)值亭為13。71清華屬大學(xué)遼出版賺社背包筋問題-逆序李解法例9一只企背包腫可裝扇載重序量為5公斤取。有界三A、B、C種物所品,企每種凳物品櫻每件躬的價(jià)鄭值和塵重量獵如下予表。鵲在背甩包中智每種謙物品去裝載業(yè)多少館件,奮使背鳥包中隆物品莫的總腐價(jià)值之最大注。ABC價(jià)值ck(元/件)658030重量wk(公斤/件)23172清華籃大學(xué)膏出版冰社階段肺:3狀態(tài)膠:k階段憑可裝慕載容窗量決策:k階段遵裝載盞的件烏數(shù)T:術(shù)xk+欺1=xk-wKukQ:珠x1=5慈0憐≤xk≤5Dk:由0≤信xk-wKuk≤5得0≤衫uk≤xk/wk范圍漂內(nèi)的裳整數(shù)rk:ckuk73清華彈大學(xué)擴(kuò)出版寨社物品A物品B物品Ck=爐1k=恥2k=呼3k=紹4x1=5x2x3x4階段k狀態(tài)朝變量鉛:裝載糖前背慕包的迫容量決策義變量繩:裝載漠的件抖數(shù)u1u1u1決策吩允許碼集合斤:裝載緒件數(shù)兔的范發(fā)圍0≤程u1≤x1/w1u1為整母數(shù)狀態(tài)贈(zèng)轉(zhuǎn)移名方程蛙:背模包容陜量和衛(wèi)裝載送件數(shù)鴨的關(guān)辨系階段散指標(biāo)務(wù):vk(xk,uk)=ckuk在背便包中頃第k種物百品的蕩價(jià)值最優(yōu)秘指標(biāo)落:fk(xk)=旅ma賠x{執(zhí)ck,uk+fk+盡1(xk+淚1)}終端旁條件抓:f4(x4)=遇0x2=x1-w1u1x3=x2-w2u2x4=x3-w3u30≤扇u1≤x1/w1u1為整斃數(shù)0≤愁u1≤x1/w1u1為整粉數(shù)74清華剖大學(xué)油出版位社x3D3(x3)x4c3u3c3u3+f4(x4)f3(x3)u*300000+0=0*00101100300+0=030+0=30*3012012210030600+0=030+0=3060+0=60*60230123321003060900+0=030+0=3060+0=6090+0=90*9034012344321003060901200+0=030+0=3060+0=6090+0=90120+0=120*1204501234554321003060901201500+0=030+0=3060+0=6090+0=90120+0=120150+0=150*1505k=放3,裝載卡物品C,f3(x3)75清華俘大學(xué)賠出版陸社x2D2(x2)x3c2u2c2u2+f3(x3)f2(x2)u*2第二次裝載前的容量(公斤)第二種物品可以裝載的件數(shù)(件)第二次裝載后剩余的容量(公斤)第二次裝載的價(jià)值(元)第二次裝載的價(jià)值+裝載后的容量可以產(chǎn)生的價(jià)值(元)第二次裝載前的容量的最大價(jià)值(元)第二次裝載的最優(yōu)件數(shù)(件)00000+0=00010100+30=3030020200+60=60600301300800+90=90*80+0=80900401410800+120=120*80+30=1101200501520800+150=150*80+60=1401500k=鈔2,裝載攔物品B,f2(x2)76清華展大學(xué)換出版耍社x1D1(x1)x2c1u1c1u1+f2(x2)f1(x1)u*1第一次裝載前的容量(公斤)第一種物品可以裝載的件數(shù)(件)第一次裝載后剩余的容量(公斤)第二次裝載的價(jià)值(元)第二次裝載的價(jià)值+裝載后的容量可以產(chǎn)生的價(jià)值(元)第二次裝載前的容量的最大價(jià)值(元)第二次裝載的最優(yōu)件數(shù)(件)50125310651300+150=15065+90=155130+30=160*1602k=弊1,裝載澇物品A,f1(x1)最優(yōu)顛解為是:x1=5拋,封u1*=此2,磨x2=x1-2悅u1=1浮,弦u2*=涉0,蠶x3=x2-3躲u2,躺u3*=中1,宇x4=x3-u3=0即:收物品A裝2件,芒物品B不裝塘,物史品C裝1件。遞最大近價(jià)值被為16琴0元。77清華劇大學(xué)數(shù)出版賠社本問鬼題由爆于狀均態(tài)轉(zhuǎn)主移方昂程中uk的系數(shù)巷不為肚一,蝴而uk為整賭數(shù),污因此惠每階瞇段xk的可促達(dá)狀態(tài)距集合暢不連坊續(xù),貝這是羞決策兄對(duì)狀旬態(tài)的宋反作烘用產(chǎn)刺生的喬。為蔬使計(jì)北算更鼓簡(jiǎn)便友可以上采用夜試算買的辦喝法先供確定專各階廊段的某狀態(tài)睛。78清華來(lái)大學(xué)沙出版欣社5012531x1D1(x1)x25015230130101x2D2(x2)x3x3D3(x3)x40001011020122103012332105015279清華杠大學(xué)無(wú)出版好社第4節(jié)復(fù)斯合系巧統(tǒng)工遮作可艷靠性招問題若某究種機(jī)剃器的帳工作教系統(tǒng)燃由n個(gè)部酷件串饑聯(lián)組壘成,元只要拼有一謀個(gè)部偵件失烘靈,致整個(gè)病系統(tǒng)帶就不爪能工肅作。猴為提剖高系中統(tǒng)工滅作的給可靠貌性,奮在每忌一個(gè)育部件首上均理裝有溪主要春元件遠(yuǎn)的備膜用件甩,并灰且設(shè)駝?dòng)?jì)了叮備用土元件舌自動(dòng)拐投入諷裝置薄。顯克然,步備用芬元件村越多顆,整朗個(gè)系挪統(tǒng)正伍常工育作的糾可靠勇性越棕大。乒但備向用元妖件多百了,李整個(gè)煌系統(tǒng)疤的成捆本、遣重量考、體及積均誤相應(yīng)拴加大姥,工威作精巡壽度也和降低化。因坐此,盆最優(yōu)草化問幻玉題是謝在考擁慮上雀述限召制條徑件下康,應(yīng)葉如何閥選擇俊各部坦件的濤備用吐元件熔數(shù),劈燕使整樸個(gè)系撞統(tǒng)的提工作利可靠跌性最倘大。80清華省大學(xué)矛出版飛社第4節(jié)復(fù)毛合系池統(tǒng)工勾作可揪靠性堵問題設(shè)部顧件可上錢裝有ui個(gè)備梢用件獅時(shí),偶它正耕常工葬作的出概率嘆為pi(ui)。因湖此,趣整個(gè)怨系統(tǒng)葵正常收工作井的可在靠性眼,可予用它雄正常饞工作焦的概奏率衡圣量。筒即設(shè)裝療一個(gè)腰部件i備用請(qǐng)?jiān)瀑M(fèi)用問為ci,重拒量為wi,要俗求總遼費(fèi)用當(dāng)不超豆過c,總飛重量育不超懸過w,則圈這個(gè)鑼問題夠有兩駁個(gè)約御束條哄件,扒它的礦靜態(tài)信規(guī)劃榨模型幅為:這是襖一個(gè)茅非線凱性整療數(shù)規(guī)瞞劃問宣題,臭因ui要求釘為整嫂數(shù),盛且目遲標(biāo)函御數(shù)是詳非線羅性的館。此擋問題灶用動(dòng)何態(tài)規(guī)飾劃方為法來(lái)港解,焦比較觀容易濕。81清華才大學(xué)鳳出版豈社第4節(jié)復(fù)旁合系含統(tǒng)工材作可環(huán)靠性秀問題為構(gòu)甚造動(dòng)謙態(tài)規(guī)偶劃模嬸型,午根據(jù)梯兩個(gè)骨約束戴條件程,取肆二維純狀態(tài)亭變量平,采濱用兩俯個(gè)狀黨態(tài)變堂量:xk——由第k個(gè)到穴第n個(gè)部辦件所效容許納使用脅的總躲費(fèi)用普。yk——由第k個(gè)到恰第n個(gè)部翁件所捷容許術(shù)具有委的總除重量歡。決策辱變量uk為部舉件k上裝很的備帥用元口件數(shù)丹,這謙里決氣策變門量是為一維算的。這樣嫁,狀碎態(tài)轉(zhuǎn)嗚移方收程為良:允許架決策站集合爸為最優(yōu)穴值函池?cái)?shù)為由鍵狀態(tài)xk和yk出發(fā)侍,從拳部件k到部蔬件n的系枝統(tǒng)的觀最大楊可靠臣性。82清華餡大學(xué)塑出版覆社第4節(jié)復(fù)躬合系碼統(tǒng)工參作可袋靠性合問題因此貫,整西機(jī)可茂靠性均的動(dòng)雪態(tài)規(guī)父劃基觸本方鍵程為誼:邊界常條件妻為1,這熊是因漫為xn+射1、yn+君1均為難零,挨裝置預(yù)根本擁不工解作,滾故可竟靠性啊當(dāng)然挨為1。最騾后計(jì)侍算得即為莊所求鋪問題捏的最庫(kù)大可讓靠性趙。83清華扮大學(xué)維出版惠社第4節(jié)復(fù)跡合系曬統(tǒng)工救作可也靠性納問題例10某廠鴨設(shè)計(jì)獨(dú)一種演電子倒設(shè)備宿,由帥三種喘元件D1,D2,D3組成昌。已霉知這爽三種惡元件朋的價(jià)羽格和災(zāi)可靠厭性如賞表9-琴9所示務(wù),要菊求在魔設(shè)計(jì)抵中所麗使用亞元件感的費(fèi)資用不生超過10概5元。罩試問摧應(yīng)如追何設(shè)液計(jì)使企設(shè)備之的可料靠性棕達(dá)到睡最大(不考陜慮重化量的慨限制)。表9-襪9元件單位/元可靠性D1300.9D2150.8D3200.584清華脫大學(xué)罷出版和社第4節(jié)復(fù)撈合系緣瑞統(tǒng)工遲作可圍靠性莫問題解:按元呆件種撲類劃蜂分為耳三個(gè)辯階段炊,設(shè)狀渡態(tài)變很量sk表示疤能容鞭許用附在Dk元件獲至D3元件殘的總騙費(fèi)用;決滑策變搶量xk表示翼在Dk元件穗上的構(gòu)并聯(lián)亦個(gè)數(shù)譽(yù);pk表示壞一個(gè)Dk元件泰正常糞工作今的概嘩率,鞠則(1心?pk)xk為xk個(gè)Dk元件掏不正燭常工突作的嘩概率役。令最黎優(yōu)值問函數(shù)fk(sk)表示痛由狀跨態(tài)sk開始稿從Dk元件坦至D3元件足組成慮的系膚統(tǒng)的藍(lán)最大扒可靠西性。因譽(yù)而有由于s1=1環(huán)05,故繁此問蛇題為所求出f1(1貨05警)即可膜。85清華濁大學(xué)懲出版午社第4節(jié)復(fù)雅合系啞統(tǒng)工滔作可脅靠性糟問題而但可是86清華和大學(xué)攤出版剛社第4節(jié)復(fù)援合系決統(tǒng)工霜作可鄰靠性杰問題所以同理故從而障求得為最逆優(yōu)方瓦案,你即D1元件歐用1個(gè)D2元件涉用2個(gè),D3元件躍用2個(gè)。括其總暈費(fèi)用錄為10旱0元,就可靠鏡性為0.且64是8。87清華釋大學(xué)通出版雜社第5節(jié)理設(shè)牢備更項(xiàng)新問犯題在工億業(yè)和腥交通匯運(yùn)輸倚企業(yè)待中,貴經(jīng)常遍碰到池設(shè)備呢陳舊得或部摔分損咽壞需偉要更較新的盤問題黃。從福經(jīng)濟(jì)甘上來(lái)涉分析翼,一鄉(xiāng)豐種設(shè)白備應(yīng)靠該用膝多少源年后炒進(jìn)行耕更新死為最豬恰當(dāng)夠,即殿更新賢的最證佳策吹略應(yīng)剝?cè)撊玳l何,析從而雖使在殲?zāi)骋稽c(diǎn)時(shí)間盆內(nèi)的君總收鐵入達(dá)芒到最偶大(或總量費(fèi)用騎達(dá)到者最小)。88清華考大學(xué)薪出版魔社第5節(jié)閑設(shè)場(chǎng)備更罷新問翠題現(xiàn)以板一臺(tái)鼠機(jī)器塌為例罰,隨肆著使晨用年弊限的被增加匹,機(jī)給器的料使用吹效率新降低艦,收坐入減登少,暮維修走費(fèi)用黨增加遣。而葉且機(jī)領(lǐng)器使例用年朋限越遇長(zhǎng),俘它本序身的僑價(jià)值制就越御小,初因而耐更新假時(shí)所吹需的傷凈支箏出費(fèi)補(bǔ)用就靜愈多線。設(shè):Ij(t)販——在第j年機(jī)予器役饞齡為t年的披一臺(tái)樹機(jī)器酷運(yùn)行厚所得勺的收責(zé)入?!诘趈年機(jī)桿器役返齡為t年的摩一臺(tái)樓機(jī)器達(dá)運(yùn)行秧時(shí)所遷需的叢運(yùn)行矮費(fèi)用匙?!诘趈年機(jī)起器役迷齡為t年的商一臺(tái)堤機(jī)器狡更新戒時(shí)所給需更艘新凈飽費(fèi)用機(jī)。——折扣流因子(),表馬示一良年以夕后的甲單位德收入商的價(jià)棟值視賞為現(xiàn)案年的單位計(jì)。T——在第蜻一年槐開始暑時(shí),良正在卸使用貼的機(jī)謀器的見役齡屈。n——計(jì)劃水的年蹦限總輪數(shù)。gj(t)啄——在第j年開腎始使箱用一鏟個(gè)役汗齡為t年的分機(jī)器頂時(shí),周從第j年至模第n年內(nèi)繞的最離佳收湊入。xj(t)零——給出gj(t)時(shí),段在第j年開膨始時(shí)奮的決偷策(保留康或更均新)。89清華燭大學(xué)對(duì)出版準(zhǔn)社第5節(jié)絨設(shè)禽備更針

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論