吉林大學本科運籌學課件動態(tài)規(guī)劃應用舉例

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

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

將問題按工廠分為三個階段，甲、乙、丙三個工廠分別編號為1、2、3設(shè)sk表示為分配給第k個工廠至第n個工廠的設(shè)備臺數(shù)。xk表示為分配給第k個工廠的設(shè)備臺數(shù)。則為分配給第k+1個工廠至第n個工廠的設(shè)備臺數(shù)。表示為xk臺設(shè)備分配到第k個工廠所得的盈利值。表示為sk臺設(shè)備分配給第k個工廠至第n個工廠時所得到的最大盈利值。因而可寫出逆推關(guān)系式為 8清華大學出版社1.1資源分配問題下面從最后一個階段開始向前逆推計算。第三階段：設(shè)將s3臺設(shè)備(s3=0,1,2,3,4,5)全部分配給工廠丙時，則最大盈利值為其中x3=s3=0,1,2,3,4,5因為此時只有一個工廠，有多少臺設(shè)備就全部分配給工廠丙，故它的盈利值就是該段的最大盈利值，如下表。x3s3P3(x3)f3(s3)x3*012345000014412662311113412124512125表中x3*表示使f3(s3)為最大值時的最優(yōu)決策。9清華大學出版社1.1資源分配問題第二階段：設(shè)把s2臺設(shè)備(s2=0,1,2,3,4,5)分配給工廠乙和工廠丙時，則對每個s2值，有一種最優(yōu)分配方案，使最大盈利值為其中 因為給乙工廠x2臺，其盈利為p2(x2)，余下的s2?x2臺就給丙工廠，則它的盈利最大值為f3(s2?x2)?，F(xiàn)要選擇x2的值，使取最大值。其數(shù)值計算如表9-3所示。10清華大學出版社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清華大學出版社1.1資源分配問題第一階段：設(shè)把s1臺(這里只有s1=5的情況)設(shè)備分配給甲、乙、丙三個工廠時，則最大盈利值為

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

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

3、范圍：Q：x1=4,xn＋1=00≤xk≤4Dk：0≤uk≤xkun=xn4、階段函數(shù)：rk（uk）為該階段項目收益15清華大學出版社項目A項目B項目Ck=歪1k=鍛2k=挪3k=福4x1=4x2x3x4階段k狀態(tài)隆變量燥：項目檢投資剖前的雁資金楊余額決策載變量沒：項目泳的投晉資u1u2u3決策符允許熟集合巷：項目喂的投劍資的雷范圍0≤利u1≤x10≤離u2≤x20≤貌u3≤x3狀態(tài)裝轉(zhuǎn)移徐方程缸：資威金余趴額和能投資拍額的套關(guān)系階段沫指標櫻：rk(uk)每個殖項目撤不同扔投資哪額的德投資衡的效帝益最優(yōu)舒指標位：fk(xk)=ma曠x{護rk(約uk)+蜘fk+代1(xk+渾1)}終端悠條件致：f4(x4)=兔0x2＝x1-u1x3=x2-u2x4=x3-u316清華筐大學鼓出版燥社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清華家大學舉出版躍社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清華封大學乖出版肥社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)嫩解為刺：項目A投資1萬元墳，項填目B不投證資，枯項目C投資3萬元富。最鄉(xiāng)豐大效低益為60萬噸佩。19清華寫大學觸出版襖社例3分配滔投資縮慧問題某公福司有支資金10萬元沒，若藍投資麥于項乖目k細(k救=吊1，2，3)的投濱資額建為xk時，砌其收勵益分梯別為g1(x1)=芝4籍x1，g2(x2)=敗9雹x2，g3(x3)=席2孝x32，問應勇該如券何分型配投疑資數(shù)獲額才謊能使要總收慣益最延大？該問卷題表禿面上竿看與攪時間國無明顆顯關(guān)味系，尺其靜犯態(tài)模送型：Ma適x巴z順=4x1+9x2+2x32x1+x2+x3=創(chuàng)10xi≥0(i尾=糟1，2，3)20清華鄭大學截出版佩社如何睛應用早動態(tài)洲規(guī)劃鏡方法珠求解膨此類摧靜態(tài)雨規(guī)劃載問題返？一婚般我僚們可乘以人絞為地奴給它瞧賦予贊“時段”的著概念詢，將聰投資鑄項目起按任蘋意順裳序進蝦行排搖序，稀如首奇先考醬慮項女目1的投舟資，屈然后奔考慮管項目2的投粗資……，即停將問陪題人卵為劃住分為判若干坡個階流段，喬每個兔階段診只決糞定對哨一個鴿項目蘆應投席資的駱金額織。這俊樣，汗可以素將上忍述問簽題轉(zhuǎn)蚊化為耍一個n階段爭決策丙過程頸。分配唱投資湊問題薄的分糠析求伏解如冒下：階段k坡=擺1，2，3，分瓣別表慕示項雪目1，2，3狀態(tài)插變量sk：第k段初泉擁有貼的資抬金總泰量(分配暖給第k至第3個項仍目的挪資金怪數(shù)量)決策差變量xk：第k段的末投資速量(分配竹給第k個項抖目的鵲資金漁數(shù)量)，決策素集合Dk(sk)=xk嗓0造≤xk≤sk狀態(tài)孩轉(zhuǎn)移定方程sk+濁1=sk-xk21清華遇大學婦出版敏社階段燭指標愛值(函數(shù))vk(sk，xk)=gk(xk)定義fk(sk)：第k段初圓擁有牛的資擁金總業(yè)量為sk時，筍第k至第3段按秒最優(yōu)鋤投資柴策略淚所獲斃得的腹第k至第3段的攤總收宏益。建立辱動態(tài)辮規(guī)劃小基本碎方程梁：(逆序揪遞推孟方程)fk(sk)=max[gk(xk)+fk+1(sk+1)]，k=3，2，10≤xk≤skf4(s4)=022清華險大學歐出版殊社逆序更遞推讀求解冤動態(tài)萍規(guī)劃復基本屑方程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]可以鳳證明然極大愉值只您可能勒在端季點取犁得，英即：f2(0貪)=2s22f2(s2)=9s2s2＞9/腸2時，f2(0路)＞f2(s2)，此碌時x2*忠=0（f2(0俯)=2s22）s2＜9/避2時，f2(0市)＜f2(s2)，此勺時x2*雙=s2（f2(s2)=9s2）23清華耀大學展出版末社k們=掀1當f2(s2)=9s2，f1(1刮0)倆=胖Ma茶x賭[4x1+齊f2(s2)]0今≤x1≤10=漲Ma旦x認[9s1–5x1]良=9s1，x1*鳥=0但此域時s2=s1–x1=1藍0卸-倒0＞9/膽2與s2＜9/比2矛盾抹，故墨舍去資。當f2(s2)=2s22，f1(1旨0)守=蟲Ma掛x賊[4x1+侄f2(s2)]0然≤x1≤10=炕Ma司x杠[4s1+2(指s1–x1)2]同樣盯可以爽證明梨極大剩值只享可能咐在端參點取適得，霧比較隙兩個癥端點缸：x1=恐0時，f1(1律0)完=喉20混0，x1=踩10時，f1(1閘0)桿=拆40所以x1*左=娘024清華刮大學虎出版渾社順序哥確定最優(yōu)員策略s1=購10x1*岔=0s2=s1–x1*=觀10＞9/顛2x2*雞=醫(yī)0s3=s2–x2*=鏡10x3*爆=笨10最優(yōu)某投資糠方案砍為全擴部資插金投奶資于魯?shù)?個項糾目，色可獲責最大境收益20虛0萬元除。25清華惑大學微出版喝社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)課后，或回收脹的資之源量紫合計趴為第二塑年再乎將資裕源數(shù)送量s2中的u2和s2?u2分別途再投刑入A、B兩種拌生產(chǎn)躍，則均第二癥年又然可得屈到收皺入為如此輔繼續(xù)輕進行n年，種試問食：應泊當如禾何決央定每雨年投鎖入A生產(chǎn)口的資扎源量才能渾使總我的收捎入最衫大?26清華祝大學絞出版檢社1.蔽1資源指分配關(guān)問題此問棚題寫明成靜滋態(tài)規(guī)謀劃問旁題為27清華聾大學茅出版彎社1.李1資源寫分配幅問題下面盜用動玻態(tài)規(guī)嗽劃方姥法來專處理段。設(shè)sk為狀攀態(tài)變躬量，窄它表窯示在煎第k階段(第k年)可投階入A、B兩種個生產(chǎn)傷的資犁源量。uk為決釀策變曾量，訂它表節(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)皺分配著方案抖進行廊生產(chǎn)對后所盞得到蟻的最少大總償收入掘。因此誼可寫哄出動訪態(tài)規(guī)角劃的則逆推添關(guān)系稈式為最后悼求出f1(s1)即為烘所求皂問題鍵的最敞大總氧收入己。28清華藝大學蠻出版濫社1.新1資源乖分配行問題例4機器庸負荷螺分配尖問題某種凱機器逆可在將高低流兩種季不同托的負品荷下尾進行遵生產(chǎn)針，設(shè)脅機器沾在高時負荷驕下生隆產(chǎn)的息產(chǎn)量混函數(shù)銜為g=8改u1，其墨中u1為投勝入生艦產(chǎn)的示機器希數(shù)量錫，年飼完好噴率a=0比.7；在店低負獅荷下系生產(chǎn)斃的產(chǎn)傍量函關(guān)數(shù)為h=洞5y，其習中y為投博入生性產(chǎn)的姨機器縫數(shù)量謀，年遞完好陵率為b=0救.9。假定修開始敘生產(chǎn)誓時完零好的盒機器缺數(shù)量s1=1丹00紡0臺，烏試問晚每年名如何仗安排秀機器悉在高樸、低慣負荷種下的益生產(chǎn)瓦，使粉在五億年內(nèi)斧生產(chǎn)的的產(chǎn)抵品總捉產(chǎn)量胖最高客。29清華連大學柴出版掌社1.帶1資源厘分配航問題構(gòu)造好這個技問題揭的動阿態(tài)規(guī)派劃模躲型：設(shè)階丟段序已數(shù)k表示宗年度替。狀態(tài)任變量sk為第k年度樣初擁界有的貓完好加機器暮數(shù)量覆，同羽時也箱是第k?蜘1年度淚末時話的完菊好機味器數(shù)班量。決策圾變量uk為第k年度楚中分諒配高其負荷叢下生貨產(chǎn)的小機器臟數(shù)量柜，于卻是sk?uk為該描年度夸中分懶配在義低負寺荷下迷生產(chǎn)踢的機塌器數(shù)垮量。這里sk和uk均取潤連續(xù)魄變量揉，它惑們的晚非整婆數(shù)值腹可以悼這樣樣理解乎，如sk=0西.6，就處表示券一臺曬機器部在k年度傷中正篩常工且作時鑒間只付占6/市10；uk=0花.3，就羽表示恩一臺永機器眾在該俊年度槽只有3/拳10的時法間能探在高臨負荷抽下工跪作。狀態(tài)繭轉(zhuǎn)移絡方程迫為k段允膠許決覽策集豆合為設(shè)為第k年度陽的產(chǎn)歡量，腥則故指見標函貓數(shù)為30清華國大學猴出版峽社1.且1資源剩分配元問題令最勵優(yōu)值拳函數(shù)fk(sk)表示哲由資迫源量sk出發(fā)溜，從征第k年開跨始到赴第5年結(jié)財束時雁所生崗產(chǎn)的袋產(chǎn)品未的總版產(chǎn)量陪最大組值。繁因而丑有逆違推關(guān)康系式宰：31清華煎大學集出版璃社1.茶1資源辯分配售問題從第5年度位開始雁，向些前逆憤推計安算。當k=懷5時，驅(qū)有因f5是u5的線辰性單樣調(diào)增德函數(shù)鍛，故庭得最海大解u5*，相睡應的惠有32清華宴大學拔出版孕社1.戴1資源吹分配脊問題當k=抬4時，框有故得循最大別解，u4*=熔s4，相械應的勤有依此暑類推池，可鞭求得因s1=1加00兔0，故33清華乖大學染出版乓社1.簡1資源萍分配寇問題計算襖結(jié)果俱表明詠：最滋優(yōu)策揮略為即前兩滔年應驚把年逢初全停部完從好機獻器投修入低雹負荷嫁生產(chǎn)，后雹三年緒應把陰年初騙全部陜完好薄機器禁投入事高負憑荷生瞞產(chǎn)。粒這樣端所得梢的產(chǎn)赤量最個高，截其最消高產(chǎn)亞量為23抖70摟0臺。34清華胡大學勿出版巧社1.形1資源豎分配德問題在得刻到整橫個問舌題的屢最優(yōu)穗指標投函數(shù)倉值和鴨最優(yōu)舉策略島后，金還需燭反過碌來確蓮定每主年年照初的貼狀態(tài)慨，即斥從始慨端向居終端鋸遞推泊計算活出每行年年匯初完商好機變器數(shù)煎。已膊知s1=1姜00赤0臺，暮于是撇可得35清華廈大學障出版極社第2節(jié)乓生虜產(chǎn)與墻存貯才問題在生鋪產(chǎn)和稍經(jīng)營憂管理貼中，釣經(jīng)常角遇到迷要合煮理地兼安排諸生產(chǎn)(或購梯買)與庫庭存的抬問題介，達霞到既達要滿準足社園會的全需要婦，又邊要盡氏量降征低成取本費蔬用。膏因此乖，正在確制構(gòu)定生獻產(chǎn)(或采泉購)策略閱，確飛定不靠同時末期的續(xù)生產(chǎn)令量(或采鴿購量)和庫過存量慘，以捧使總的聰生產(chǎn)勺成本過費用臣和庫熔存費逢用之鏡和最恭小，這架就是階生產(chǎn)靠與存燥儲問拳題的泉最優(yōu)絞化目緊標。36清華享大學程出版眾社企業(yè)深一年軟中的居產(chǎn)品方生產(chǎn)澡往往故是分遍期分策批生尤產(chǎn)的洪。組織財每批斯產(chǎn)品雷的生喊產(chǎn)，糕都要沈花費們一些著生產(chǎn)墓準備滴費和睡存貯陡費用嚷。若某謀一時編期增盜大生徐產(chǎn)批飯量則爸可減憑少生渠產(chǎn)批淡次，保從而總降低且生產(chǎn)層成本抗。與此關(guān)同時早，批館量大立了，若必然嗚增加宅庫存繪而使循存貯億費用改增加康。在企質(zhì)業(yè)產(chǎn)銹品的忙生產(chǎn)棄成本孝、存隔貯費煉用、攀市場帆需求伸量確劈燕定的含情況批下，浸正確頑計劃晴各時在期的言生產(chǎn)搭量，跨既滿斗足市焰場需離求，絮又使遭總支娛出最卻少，伶這是藍一個碎多階售段決東策問遮題。生產(chǎn)所與存震儲問暢題37清華殲大學舞出版攝社2.鏡1生產(chǎn)嬸與存燒貯問編題設(shè)某禁公司敢對某受種產(chǎn)坑品要哄制定炊一項貝多階右段的藍生產(chǎn)(或購腔買)計劃悉。已恐知它鞭的初氧始庫俗存量民為零鹿，每食階段悄生產(chǎn)(或購攔買)該產(chǎn)順品的梢數(shù)量尺有上避限的預限制俘；每儉階段次社會迎對該務產(chǎn)品廊的需歉求量紛是已系知的牧，公沾司保若證供傳應；喇在n階段茄末的岡終結(jié)詞庫存貝量為填零。館問該伐公司勤如何蝕制定峰每個影階段捏的生妹產(chǎn)(或采招購)計劃寇，從負而使債總成檔本最陣小。38清華雷大學鋼出版蛋社生產(chǎn)印計劃宜周期息分為n個階仁段，辜即k=缺1~炎n；已知投最初授庫存射量為S1=0；階段四需求喪量為dk；單位沃產(chǎn)品社的消辦耗費餅用為Lk；單位聲產(chǎn)品幕的階紀段庫肺存費茫用為hk；倉庫巴容量緞為Mk；階段迷生產(chǎn)桌能力碑為Bk；生產(chǎn)遙的準撕備費輔用為房誠：生產(chǎn)—存貯盆問題因原型39清華難大學壞出版身社問應血如何組安排乏各階圈段產(chǎn)釋量，捆使計珠劃期鏡總費漢用最盤小。1、階激段2、狀唇態(tài)變鵲量sk階段k的初盾始庫企存量駕，決策養(yǎng)變量uk階段k的生璃產(chǎn)量末。T:期末背庫存=期初健庫存+生產(chǎn)跌量-本期助需求40清華槐大學既出版槽社即階段k的庫惕存既腿不能碑超過擋庫存憤容量，也不孔應超艘過階忍段k至階稠段n的需揉求總況量（dk+dk+失1+…兇+dn），否則漂將與Sn+慌1=0的假狹設(shè)相做違背吸。3Sk的范毒圍：館計劃僻初期碑的庫綿存量S1是已哈知的沉，末吼期的嗎庫存斜量通錢常也常是給瞞定的毅，為凈簡單廣起見辣這里忍假定sn+邪1=0，于是消問題搶是始仰端末陜端固刪定的艘問題社。關(guān)聰于狀常態(tài)sk的約按束條賤件是41清華雨大學播出版慢社庫容量限制以后需求缺口本期需求缺口uk的范股圍：誕自身辜的要旨求及券由T與Q確定塞的范酒圍。洲階段仿產(chǎn)量塞要在版不超賤過生鋼產(chǎn)能露力Bk的條桑件下剪，充紀分滿拘足該繁階段肢的需固求dk，同時臨還要安滿足捉計劃描末期開的庫為存量悄為0的要富求。辦因此怎關(guān)于方?jīng)Q策型變量雨的約笨束條佩件就喘是42清華統(tǒng)大學圓出版蹄社4、階役段k的生點產(chǎn)費腿用是庫存楊費用注意uk自身迷的特篩殊要軍求可欄能反覺過來言作用喬于Sk，比如衰庫存術(shù)上限沈的要觸求43清華床大學免出版覺社例5某工笛廠與披用戶底簽訂扇了4個月?lián)u的交化貨合吃同如督表所禿示該廠柔生產(chǎn)策能力御為每零月5萬件謙，倉厲庫的來存貨帶能力滿為4萬件花。已知和生產(chǎn)供費用從為c=1千元/萬件拿，在類進行兔生產(chǎn)期的月衰份，眼工廠肚要支根出固喬定費泳用b=2千元單，每法月倉勒庫保闖管費己用h=0.截2千元/萬件/月。假定1月初劈燕無存莊貨，啞要求4月底牧交貨兔后無量存貨鳥，試狐問應標在每嗚月各船生產(chǎn)白多少捧件產(chǎn)遼品，跨才能妖滿足虜交貨唇任務罷，又侄使總阿費用旁最小鑰？月1234需求量dk(萬件)323244清華疑大學品出版哥社動態(tài)樸規(guī)劃繪的數(shù)壟學模巴型每個酒月為內(nèi)一個醉階段狂，即僚階段飲變量k=亮1,予2,臥3,肢4分別插表示杏這四殊個月;狀態(tài)住變量sk表示第k月初及的產(chǎn)伶品庫闖存量殃，0≤sk≤4;決策儲變量xk表示第k月的夾生產(chǎn)痕量盒，計允襖許決甜策集闊合Xk(sk)=晃{xk︱0≤xk≤5};狀態(tài)掏轉(zhuǎn)移策方程替為sk+莖1=sk+xk–dk;階段披指標vk(sk,xk)表示獸第k月的豎費用魔：蹈本月混若不旺安排甘生產(chǎn)減，則薪僅需蜓支出秀保管肚費；獲本月呼若安輪排生學產(chǎn)，恩則需匪支出財生產(chǎn)舍費用嫁和固帆定費黎，同鉆時還敲需交乏付保搏管費胃。當xk=0時，vk(sk,xk)=h爬·sk=0.籍2sk當xk＞0時，vk(sk,xk)=b+壤c·罷xk+h造·sk=2+佛xk+0.男2sk最優(yōu)站指標轉(zhuǎn)函數(shù)fk(sk)表示盟第k階段廳從sk開始離到最儀后階紛段采逮用最呈優(yōu)生叫產(chǎn)策遍略實何現(xiàn)的向最低融生產(chǎn)止費用趟。45清華隆大學氏出版距社逆序練求解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月末帥無庫蠻存則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清華碎大學險出版釀社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，溪則s3={故0,季1,葬2,棋3,福4}生產(chǎn)至能力繩限制0≤x3≤5，則x3={0玻,1聽,2費,3律,4欲,5悼}4月在框庫存谷量為s4時的山最低汪生產(chǎn)繪成本47清華腫大學清出版長社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月在芝庫存預量為s3時的減最低陸生產(chǎn)飯成本48清華肆大學躍出版溜社k=獲1x1s1v1(s1,x1)+f2(s2)=2+x2+0.2s2+f2(s2)f1(s1)x1*3452月在閉庫存濕量為s2時的下最低非生產(chǎn)件成本014福.85順序牽遞推億，得服出結(jié)止論第1月生兩產(chǎn)5萬件s2=s1+x1–d1=0惡+5請-3女=2，第2月不徐生產(chǎn)s3=s2+x2–d2=2城+0恐-2嗓=0，第3月生妖產(chǎn)5萬件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清華補大學垂出版煉社例6某車聽間需代要按加月在鑰月底宏供應叮一定蛋數(shù)量燒的某寒種部蹤蝶件給基總裝途車間齒，由沉于生匯產(chǎn)條裂件的療變化沖，該秩車間土在各笑月份嘴中生辭產(chǎn)每捏單位居這種麗部件召所需迎耗費警的工東時不回同，東各月界份的面生產(chǎn)麻量于倍當月勸的月馳底前絹，全籍部要存入茄倉庫確以備忘后用。已允知總絕裝車臘間的星各個潮月份蒙的需求騎量以及腔在加碎工車域間生句產(chǎn)該撲部件撫每單膏位數(shù)盟量所格需工煩時數(shù)愧如表9-欣7所示燒。月份k0123456需求量dk0853274單位工時ak111813172010設(shè)倉神庫容養(yǎng)量限勿制為H=副9，開阿始庫怕存量污為2，期判終庫演存量怪為0，需灑要制航定一棒個半丹年的林逐月連生產(chǎn)挑計劃職，既孫使得重滿足勞需要兄和庫剪容量影的限廉制，陵又使鞭得生胞產(chǎn)這懶種部宴件的總耗豬費工蓋時數(shù)為最悉少。表9-屆750清華馬大學典出版巡壽社解:按月協(xié)份劃煌分階余段，欲用可她表示敲月份打序號臣。設(shè)狀斬態(tài)變劉量sk為第k段開氧始時(本段御需求互量送謊出之販前，疏上段鞋產(chǎn)品箏送入幻玉之后)部件墊庫存擁量。(現(xiàn)存瞇的能篩滿足遲當月扮需求）決策銅變量uk為第k段內(nèi)湖的部購件生朋產(chǎn)量程。狀態(tài)凝轉(zhuǎn)移奮方程捕：且故允緊許決扣策集康合為51清華嗚大學塊出版騎社最優(yōu)同值函昌數(shù)橡表忘示在麗第k段開鋒始的柴庫存答量為sk時，佛從第k段至音第6段所冰生產(chǎn)犯部件座的最疲小累蝦計工穿時數(shù)傘。因孟而可蘭寫出轎逆推襖關(guān)系剪式為當k=俯6時，鋤因要巧求期砍終庫扭存量億為0，即s7=0。因能每月良的生勺產(chǎn)是古供應纏下月決的需召要，斃故第6個月榴不用庫生產(chǎn)銷，即u6=0。因捷此f6(s6)=液0，而困由(9備-9飄)式有當k=掠5時，痛由(9暢-9干)式有故及最婆優(yōu)解52清華砌大學漲出版態(tài)社當k=掙4時，天有其中u4的允垮許決校策集營合D4(s4)由(9耀-1撒1)式確掏定為由，故別有又，因謠而而由(9惜-1獵0)式知惑：，所犧以為故得及最凱優(yōu)解53清華騾大學瓜出版諸社當k=罩3時，由(9縫-1堤1)式得D3(s3)為故得及最緊優(yōu)解當k=盼2時，其中D2(s2)為故得及最萄優(yōu)解54清華懲大學姜出版票社當k=五1時，其中D1(s1)為故得及最高優(yōu)解當k=姓0時，其中D0(s0)為故得及最啞優(yōu)解因s0=2，所擦以f0=3糖57和u0*=道7再按已計算烤順序桂反推蚊，即盤得各焰階段殘最優(yōu)天決策褲為：所以憤，0至5月最鼠優(yōu)生誓產(chǎn)計摟劃為滔：7，4，9，3，0，4，最替小總唐工時初為35該7。55清華優(yōu)大學奇出版鼻社2.滴2不確副定性螺的采朽購問啟題在實幅際問崇題中幅，還瀉會遇共到某凡些多討階段槽決策窩過程震，其挖狀態(tài)再轉(zhuǎn)移熔不是痛完全也確定替的，胸出現(xiàn)瓶了隨慢機性飛因素限，狀治態(tài)轉(zhuǎn)藥移是伶按照框某種饒已知史概率筒分布懸取值羨的。具有吉這種頂性質(zhì)獅的多龍階段躺決策壤過程叼稱為臣隨機記性決訂策過緞程。用動鐵態(tài)規(guī)唱劃方瘦法也鍬可處鄰理這響類隨啄機性覆問題餡，又米稱為伴隨機帆性動鉤態(tài)規(guī)贊劃。56清華怕大學抹出版育社2.轎2不確痕定性投的采商購問娛題例7采購授問題蟻。某齊廠生惡產(chǎn)上決需要拼在近洲五周培內(nèi)必序須采裳購一身批原查料，董而估勇計在相未來窗五周嶺內(nèi)價罪格有轟波動性，其壯浮動部價格床和概背率已帳測得窯如表9-患8所示察。試孔求在極哪一投周以桌什么縮慧價格尸購入斤，使斬其采雙購價廉格的寒數(shù)學仰期望耍值最篇小，蒼并求世出期挺望值茄。單價概率5000.36000.37000.4表9-管857清華談大學柜出版懶社2.遞2不確羅定性足的采餓購問巨題解：價格迷是一向個隨選機變櫻量，納按某低種已睛知的附概率較分布青取值伍。用恐動態(tài)融規(guī)劃章方法娘處理予，按欲采購浸期限5周分候為5個階弓段，捉將每障周的嬸價格很看作島該階且段的勸狀態(tài)耳。設(shè)yk——狀態(tài)儲變量增，表穿示第k周的報實際而價格然。xk——決策歉變量運，xk=1時表槐示第k周決棕定采騾購；xk=0時表洪示第k周決汗定等甜待。ykE——第k周決久定等葵待，終而在覆以后團采取煤最優(yōu)腿決策冊時采蘇購價暫格的樂期望叢值。fk(yk)—飲—第k周實塑際價命格為yk時，楊從第k周至令第5周采近取最鄙優(yōu)決本策所共得的嶺最小岡期望頂值因而潑可寫騙出逆盤序遞魚推關(guān)蜻系式劈燕為其中由ykE和fk(yk)的定條義可乞知：并且或得出買最優(yōu)印決策呢為：58清華投大學郵出版上社2.藝2不確儲定性鍬的采吧購問永題從最逃后一那周開楊始，友逐步特向前夾遞推作計算鋼，具茅體計摘算過俊程如棒下。k=揚5時，翼因，故文有即在山第五龍周時伸，若暴所需籍的原托料尚楚未買腿入，蟲則無奪論市抓場價究格如刊何，榮都必些須采襖購，鞠不能員再等茶。k=劍4時，而由(9獎-1做6)式可島知于是寬，由(9怕-1舊3)式得由(9脅-1催7)式，任第4周最倆優(yōu)決客策為59清華擊大學央出版陸社2.編2不確撈定性老的采傾購問洪題同理窄求得所以60清華賴大學號出版捷社2.叛2不確灶定性蹈的采踐購問修題所以61清華夢大學房誠出版指社2.咐2不確圓定性暈的采廚購問裂題所以由上蕉可知臭，最住優(yōu)采問購策烤略為拴：在使第一朽、二鵝、三窗周時波，若尾價格值為50流0就采角購，戰(zhàn)否則薯應該歸等待封；在戚第四纖周時瘦，價稍格為50獵0或60澇0應采然購，燈否則坡就等挪待；執(zhí)在第掩五周競時，捕無論床什么金價格沖都要供采購裂。62清華武大學佩出版框社2.捧2不確安定性煩的采葉購問宇題依照梅上述冒最優(yōu)桶策略夠進行論采購株時，意價格(單價)的數(shù)慚學期歸望值刷為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清華始大學涌出版虜社第3節(jié)早背改包創(chuàng)問耐題有一瓦個人量帶一節(jié)個背馳包上腐山，倚其可詞攜帶削物品必重量警的限驢度為a公斤設(shè)。設(shè)虜有n種物用品可鋤供他果選擇纏裝入偽背包至中，獎這n種物倍品編蔽號為1，2，…，n。已劑知第i種物劣品每冷件重競量為wi公斤淚，在迅上山心過程盒中的敞作用(價值)是攜彩帶數(shù)些量xi的函滅數(shù)ci(xi)。問懲此人睛應如由何選羅擇攜慣帶物尿品(各幾箭件)，使電所起答作用(總價克值)最大輕。這尖就是罩著名勾的背亦包問鄰題。類似煙的問扣題有法工廠躁里的脈下料移問題闖，運熄輸中戰(zhàn)的貨謹物裝億載問悔題，仰人造薄衛(wèi)星稍內(nèi)的冠物品賽裝載混問題次等等位。64清華始大學妄出版共社第3節(jié)銳背芒包熱問利題設(shè)xi為第i種物叉品的你裝入配件數(shù)奸，則特問題近的數(shù)幸學?？匦蜑樗沁B一個整數(shù)澆規(guī)劃送問題。如柳果xi只取0或1，又梯稱為0—骨1背包始問題共。下私面用侵動態(tài)皇規(guī)劃乳方法易來求子解。65清華皂大學螞出版跑社第3節(jié)多背驢包涉問噸題設(shè)按縮慧可裝確入物膏品的n種類演劃分斜為n個階姐段。狀態(tài)鎖變量w表示蚊用于撐裝第1種物旁品至來第k種物讓品的復總重區(qū)量。決策拜變量xk表示繳裝入邀第k種物蜓品的扔件數(shù)嶼。則畢狀態(tài)疾轉(zhuǎn)移億方程最為允許胞決策防集合懶為最優(yōu)麗值函球數(shù)fk(w)是當搭總重斜量不兄超過w公斤循，背罷包中倍可以凈裝入鎖第1種到奧第k種物遼品的不最大局使用尾價值循。即66清華租大學噸出版甩社第3節(jié)予背皇包吧問同題因而盛可寫足出動態(tài)樓規(guī)劃噴的順榜序遞塌推關(guān)姓系為很：然后府，逐酸步計風算出及相材應的塊決策僑函數(shù)最后譜得出川的就是荒所求書的最捷大價虹值，董其相頌應的志最優(yōu)屬策略尼由反廁推運蔥算即簡可得揭出。67清華楚大學且出版愁社第3節(jié)夕背棵包定問落題例8解:用動棵態(tài)規(guī)差劃方丈法來筒解，漸此問嫁題變偉為求f3(1陵0)。68清華價大學皮出版符社第3節(jié)芬背造包策問贏題由此桐看到敗，要暫計算f3(1各0)，必農(nóng)須先捷計算觸出69清華赴大學吩出版鍬社第3節(jié)起背值包芹問也題為了么要計岡算出f2(1旗0)冷,f2(5墓),f2(塘0)，必恭須先議計算煉出f1(1雷0)僑,f1(6勁),f1(5扮),f1(2仆),f1(1孕),f1(0戲)，一佩般地晚有相應拌的最退優(yōu)決確策為x1=［w/仔3］，愚于是畫得到70清華評大學辣出版鉗社第3節(jié)架背鋤包斗問臂題從而故最樹后得針到所以疏，最稅優(yōu)裝若入方鳥案為最大它使用盈價值亭為13。71清華屬大學遼出版賺社背包筋問題-逆序李解法例9一只企背包腫可裝扇載重序量為5公斤取。有界三A、B、C種物所品，企每種凳物品櫻每件躬的價鄭值和塵重量獵如下予表。鵲在背甩包中智每種謙物品去裝載業(yè)多少館件，奮使背鳥包中隆物品莫的總腐價值之最大注。ABC價值ck（元/件）658030重量wk（公斤/件）23172清華籃大學膏出版冰社階段肺：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清華彈大學擴出版寨社物品A物品B物品Ck=爐1k=恥2k=呼3k=紹4x1=5x2x3x4階段k狀態(tài)朝變量鉛：裝載糖前背慕包的迫容量決策義變量繩：裝載漠的件抖數(shù)u1u1u1決策吩允許碼集合斤：裝載緒件數(shù)兔的范發(fā)圍0≤程u1≤x1/w1u1為整母數(shù)狀態(tài)贈轉(zhuǎn)移名方程蛙：背模包容陜量和衛(wèi)裝載送件數(shù)鴨的關(guān)辨系階段散指標務：vk(xk,uk)=ckuk在背便包中頃第k種物百品的蕩價值最優(yōu)秘指標落：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清華剖大學油出版位社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清華俘大學賠出版陸社x2D2(x2)x3c2u2c2u2+f3(x3)f2(x2)u*2第二次裝載前的容量（公斤）第二種物品可以裝載的件數(shù)（件）第二次裝載后剩余的容量（公斤）第二次裝載的價值（元）第二次裝載的價值＋裝載后的容量可以產(chǎn)生的價值(元)第二次裝載前的容量的最大價值(元)第二次裝載的最優(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清華展大學換出版耍社x1D1(x1)x2c1u1c1u1+f2(x2)f1(x1)u*1第一次裝載前的容量(公斤)第一種物品可以裝載的件數(shù)（件）第一次裝載后剩余的容量（公斤）第二次裝載的價值（元）第二次裝載的價值＋裝載后的容量可以產(chǎn)生的價值(元)第二次裝載前的容量的最大價值(元)第二次裝載的最優(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件。遞最大近價值被為16琴0元。77清華劇大學數(shù)出版賠社本問鬼題由爆于狀均態(tài)轉(zhuǎn)主移方昂程中uk的系數(shù)巷不為肚一，蝴而uk為整賭數(shù)，污因此惠每階瞇段xk的可促達狀態(tài)距集合暢不連坊續(xù)，貝這是羞決策兄對狀旬態(tài)的宋反作烘用產(chǎn)刺生的喬。為蔬使計北算更鼓簡便友可以上采用夜試算買的辦喝法先供確定專各階廊段的某狀態(tài)睛。78清華來大學沙出版欣社5012531x1D1(x1)x25015230130101x2D2(x2)x3x3D3(x3)x40001011020122103012332105015279清華杠大學無出版好社第4節(jié)復斯合系巧統(tǒng)工遮作可艷靠性招問題若某究種機剃器的帳工作教系統(tǒng)燃由n個部酷件串饑聯(lián)組壘成，元只要拼有一謀個部偵件失烘靈，致整個病系統(tǒng)帶就不爪能工肅作。猴為提剖高系中統(tǒng)工滅作的給可靠貌性，奮在每忌一個育部件首上均理裝有溪主要春元件遠的備膜用件甩，并灰且設(shè)駝計了叮備用土元件舌自動拐投入諷裝置薄。顯克然，步備用芬元件村越多顆，整朗個系挪統(tǒng)正伍常工育作的糾可靠勇性越棕大。乒但備向用元妖件多百了，李整個煌系統(tǒng)疤的成捆本、遣重量考、體及積均誤相應拴加大姥，工威作精巡壽度也和降低化。因坐此，盆最優(yōu)草化問幻玉題是謝在考擁慮上雀述限召制條徑件下康，應葉如何閥選擇俊各部坦件的濤備用吐元件熔數(shù)，劈燕使整樸個系撞統(tǒng)的提工作利可靠跌性最倘大。80清華省大學矛出版飛社第4節(jié)復毛合系池統(tǒng)工勾作可揪靠性堵問題設(shè)部顧件可上錢裝有ui個備梢用件獅時，偶它正耕常工葬作的出概率嘆為pi(ui)。因湖此，趣整個怨系統(tǒng)葵正常收工作井的可在靠性眼，可予用它雄正常饞工作焦的概奏率衡圣量。筒即設(shè)裝療一個腰部件i備用請元件制費用問為ci，重拒量為wi，要俗求總遼費用當不超豆過c，總飛重量育不超懸過w，則圈這個鑼問題夠有兩駁個約御束條哄件，扒它的礦靜態(tài)信規(guī)劃榨模型幅為：這是襖一個茅非線凱性整療數(shù)規(guī)瞞劃問宣題，臭因ui要求釘為整嫂數(shù)，盛且目遲標函御數(shù)是詳非線羅性的館。此擋問題灶用動何態(tài)規(guī)飾劃方為法來港解，焦比較觀容易濕。81清華才大學鳳出版豈社第4節(jié)復旁合系含統(tǒng)工材作可環(huán)靠性秀問題為構(gòu)甚造動謙態(tài)規(guī)偶劃模嬸型，午根據(jù)梯兩個骨約束戴條件程，取肆二維純狀態(tài)亭變量平，采濱用兩俯個狀黨態(tài)變堂量：xk——由第k個到穴第n個部辦件所效容許納使用脅的總躲費用普。yk——由第k個到恰第n個部翁件所捷容許術(shù)具有委的總除重量歡。決策辱變量uk為部舉件k上裝很的備帥用元口件數(shù)丹，這謙里決氣策變門量是為一維算的。這樣嫁，狀碎態(tài)轉(zhuǎn)嗚移方收程為良：允許架決策站集合爸為最優(yōu)穴值函池數(shù)為由鍵狀態(tài)xk和yk出發(fā)侍，從拳部件k到部蔬件n的系枝統(tǒng)的觀最大楊可靠臣性。82清華餡大學塑出版覆社第4節(jié)復躬合系碼統(tǒng)工參作可袋靠性合問題因此貫，整西機可茂靠性均的動雪態(tài)規(guī)父劃基觸本方鍵程為誼：邊界常條件妻為1，這熊是因漫為xn+射1、yn+君1均為難零，挨裝置預根本擁不工解作，滾故可竟靠性啊當然挨為1。最騾后計侍算得即為莊所求鋪問題捏的最庫大可讓靠性趙。83清華扮大學維出版惠社第4節(jié)復跡合系曬統(tǒng)工救作可也靠性納問題例10某廠鴨設(shè)計獨一種演電子倒設(shè)備宿，由帥三種喘元件D1,D2,D3組成昌。已霉知這爽三種惡元件朋的價羽格和災可靠厭性如賞表9-琴9所示務，要菊求在魔設(shè)計抵中所麗使用亞元件感的費資用不生超過10概5元。罩試問摧應如追何設(shè)液計使企設(shè)備之的可料靠性棕達到睡最大(不考陜慮重化量的慨限制)。表9-襪9元件單位/元可靠性D1300.9D2150.8D3200.584清華脫大學罷出版和社第4節(jié)復撈合系緣瑞統(tǒng)工遲作可圍靠性莫問題解：按元呆件種撲類劃蜂分為耳三個辯階段炊，設(shè)狀渡態(tài)變很量sk表示疤能容鞭許用附在Dk元件獲至D3元件殘的總騙費用；決滑策變搶量xk表示翼在Dk元件穗上的構(gòu)并聯(lián)亦個數(shù)譽；pk表示壞一個Dk元件泰正常糞工作今的概嘩率，鞠則(1心?pk)xk為xk個Dk元件掏不正燭常工突作的嘩概率役。令最黎優(yōu)值問函數(shù)fk(sk)表示痛由狀跨態(tài)sk開始稿從Dk元件坦至D3元件足組成慮的系膚統(tǒng)的藍最大扒可靠西性。因譽而有由于s1=1環(huán)05，故繁此問蛇題為所求出f1(1貨05警)即可膜。85清華濁大學懲出版午社第4節(jié)復雅合系啞統(tǒng)工滔作可脅靠性糟問題而但可是86清華和大學攤出版剛社第4節(jié)復援合系決統(tǒng)工霜作可鄰靠性杰問題所以同理故從而障求得為最逆優(yōu)方瓦案，你即D1元件歐用1個D2元件涉用2個，D3元件躍用2個。括其總暈費用錄為10旱0元，就可靠鏡性為0.且64是8。87清華釋大學通出版雜社第5節(jié)理設(shè)牢備更項新問犯題在工億業(yè)和腥交通匯運輸倚企業(yè)待中，貴經(jīng)常遍碰到池設(shè)備呢陳舊得或部摔分損咽壞需偉要更較新的盤問題黃。從福經(jīng)濟甘上來涉分析翼，一鄉(xiāng)豐種設(shè)白備應靠該用膝多少源年后炒進行耕更新死為最豬恰當夠，即殿更新賢的最證佳策吹略應剝該如閘何，析從而雖使在殲某一點時間盆內(nèi)的君總收鐵入達芒到最偶大(或總量費用騎達到者最小)。88清華考大學薪出版魔社第5節(jié)閑設(shè)場備更罷新問翠題現(xiàn)以板一臺鼠機器塌為例罰，隨肆著使晨用年弊限的被增加匹，機給器的料使用吹效率新降低艦，收坐入減登少，暮維修走費用黨增加遣。而葉且機領(lǐng)器使例用年朋限越遇長，俘它本序身的僑價值制就越御小，初因而耐更新假時所吹需的傷凈支箏出費補用就靜愈多線。設(shè)：Ij(t)販——在第j年機予器役饞齡為t年的披一臺樹機器酷運行厚所得勺的收責入。——在第j年機桿器役返齡為t年的摩一臺樓機器達運行秧時所遷需的叢運行矮費用匙。——在第j年機起器役迷齡為t年的商一臺堤機器狡更新戒時所給需更艘新凈飽費用機?！劭哿饕蜃?)，表馬示一良年以夕后的甲單位德收入商的價棟值視賞為現(xiàn)案年的單位計。T——在第蜻一年槐開始暑時，良正在卸使用貼的機謀器的見役齡屈。n——計劃水的年蹦限總輪數(shù)。gj(t)啄——在第j年開腎始使箱用一鏟個役汗齡為t年的分機器頂時，周從第j年至模第n年內(nèi)繞的最離佳收湊入。xj(t)零——給出gj(t)時，段在第j年開膨始時奮的決偷策(保留康或更均新)。89清華燭大學對出版準社第5節(jié)絨設(shè)禽備更針