第六章動(dòng)態(tài)規(guī)劃

第六章動(dòng)態(tài)規(guī)劃1第一頁，共一百一十二頁，2022年，8月28日動(dòng)態(tài)規(guī)劃的方法，在工程技術(shù)、企業(yè)管理、工農(nóng)業(yè)生產(chǎn)及軍事等部門中有著廣泛的應(yīng)用，并且獲得了顯著的效果。在經(jīng)濟(jì)管理方面，動(dòng)態(tài)規(guī)劃可以用來解決最優(yōu)路徑問題、資源分配問題、生產(chǎn)調(diào)度問題、庫存問題、裝載問題、排序問題、設(shè)備更新問題、生產(chǎn)過程最優(yōu)控制問題等等，他是現(xiàn)代企業(yè)管理中的一種重要的決策方法。許多實(shí)際問題采用動(dòng)態(tài)規(guī)劃方法去處理，常比線性規(guī)劃或非線性規(guī)劃更加有效。特別對于離散性的問題，由于解析數(shù)學(xué)無法施展其術(shù)，而動(dòng)態(tài)規(guī)劃的方法就成為一種非常有效的工具。第二頁，共一百一十二頁，2022年，8月28日應(yīng)特別指出的是，動(dòng)態(tài)規(guī)劃是解決某一類問題的一種方法，是分析問題的一種途徑，而不是一種特殊算法（如線性規(guī)劃是一種算法）。因而，它不象線性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而必須對具體問題進(jìn)行具體分析處理。因此，在學(xué)習(xí)動(dòng)態(tài)規(guī)劃時(shí)，除了對基本概念和方法正確地理解外，應(yīng)以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。正如貝爾曼本人所說：“由于動(dòng)態(tài)規(guī)劃的最優(yōu)化原理僅僅是一種基本原理，正是它的某種不確定性為你提供了發(fā)揮你創(chuàng)造性思維的巨大空間!

第三頁，共一百一十二頁，2022年，8月28日本部分我們主要研究離散決策過程，介紹動(dòng)態(tài)規(guī)劃的基本概念、理論和方法，在通過一些典型的應(yīng)用問題來說明它的應(yīng)用。

動(dòng)態(tài)規(guī)劃所研究的對象是多階段決策問題。所謂多階段決策問題是指一類活動(dòng)過程，它可以分為若干個(gè)相互聯(lián)系的階段，在每個(gè)階段都需要作出決策。這個(gè)決策不僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)。每個(gè)階段的決策確定以后，就得到一個(gè)決策序列，稱為策略。多階段決策問題就是求一個(gè)策略，使各階段的效益的總和達(dá)到最優(yōu)。第四頁，共一百一十二頁，2022年，8月28日第一節(jié)多階段決策問題在生產(chǎn)經(jīng)營活動(dòng)中，某些問題決策過程可以劃分為若干相互聯(lián)系的階段，每個(gè)階段需要做出決策，從而使整個(gè)過程取得最優(yōu)。當(dāng)每個(gè)階段的決策確定以后，全部過程的決策就是這些階段決策所組成的一個(gè)決策序列，所以多階段決策問題也稱為序貫決策問題。動(dòng)態(tài)規(guī)劃方法與“時(shí)間”關(guān)系很密切，隨著時(shí)間過程的發(fā)展而決定各時(shí)段的決策，產(chǎn)生一個(gè)決策序列，這就是“動(dòng)態(tài)”的意思。然而它也可以處理與時(shí)間無關(guān)的靜態(tài)問題，只要在問題中人為地引入“時(shí)段”因素，就可以將其轉(zhuǎn)化為一個(gè)多階段決策問題。在本章中將介紹這種處理方法。第五頁，共一百一十二頁，2022年，8月28日

動(dòng)態(tài)規(guī)劃求解的多階段決策問題的特點(diǎn)通常多階段決策過程的發(fā)展是通過狀態(tài)的一系列變換來實(shí)現(xiàn)的。一般情況下，系統(tǒng)在某個(gè)階段的狀態(tài)轉(zhuǎn)移除與本階段的狀態(tài)和決策有關(guān)外，還可能與系統(tǒng)過去經(jīng)歷的狀態(tài)和決策有關(guān)。因此，問題的求解就比較困難復(fù)雜。而適合于用動(dòng)態(tài)規(guī)劃方法求解的只是一類特殊的多階段決策問題，即具有“無后效性”的多階段決策過程。所謂無后效性，又稱馬爾柯夫性，是指系統(tǒng)從某個(gè)階段往后的發(fā)展，僅由本階段所處的狀態(tài)及其往后的決策所決定，與系統(tǒng)以前經(jīng)歷的狀態(tài)和決策(歷史)無關(guān)。第六頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2為了說明動(dòng)態(tài)規(guī)劃的基本思想方法和特點(diǎn)，以下圖所示為例，討論求最短路問題的方法。求從A到E的最短路徑第七頁，共一百一十二頁，2022年，8月28日第一種方法稱做全枚舉法或窮舉法。它的基本思想是列舉出所有可能發(fā)生的方案和結(jié)果，再對它們一一進(jìn)行比較，求出最優(yōu)方案。這里從A到E的路程可以分為4個(gè)階段。第一、二階段的走法有三種，第三階段的走法有兩種，第四段的走法僅一種，因此共有3×3×2×1＝18條可能的路線，分別算出各條路線的距離，最后進(jìn)行比較，可知最優(yōu)路線是A→B2→

C1→

D1→E,最短距離是19．第八頁，共一百一十二頁，2022年，8月28日顯然，當(dāng)組成交通網(wǎng)絡(luò)的節(jié)點(diǎn)很多時(shí)，用窮舉法求最優(yōu)路線的計(jì)算工作量將會(huì)十分龐大，而且其中包含著許多重復(fù)計(jì)算．第二種方法即所謂“局部最優(yōu)路徑”法，是說某人從A出發(fā)，他并不顧及全線是否最短，只是選擇當(dāng)前最短途徑，“逢近便走”，錯(cuò)誤地以為局部最優(yōu)會(huì)致整體最優(yōu)，在這種想法指導(dǎo)下，所取決策必是A→B2→

C1→

D1→E，全程長度是25；顯然，這種方法的結(jié)果常是錯(cuò)誤的．第九頁，共一百一十二頁，2022年，8月28日第三種方法是動(dòng)態(tài)規(guī)劃方法。動(dòng)態(tài)規(guī)劃方法尋求該最短路問題的基本思想是，如果A=S1→S2→…

→

Sk→…

→

Sn→E是A到E的最短路，則Sk到E的最短路一定是Sk→…

→

Sn→E。首先將問題劃分為4個(gè)階段，每次的選擇總是綜合后繼過程的一并最優(yōu)進(jìn)行考慮，在各段所有可能狀態(tài)的最優(yōu)后繼過程都已求得的情況下，全程的最優(yōu)路線便也隨之得到。為了找出所有可能狀態(tài)的最優(yōu)后繼過程，動(dòng)態(tài)規(guī)劃方法總是從過程的最后階段開始考慮，然后逆著實(shí)際過程發(fā)展的順序，逐段向前遞推計(jì)算直至始點(diǎn)。第十頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0第十一頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0第十二頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5第十三頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5第十四頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8第十五頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7第十六頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8第十七頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=21第十八頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14第十九頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21第二十頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2第二十一頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1第二十二頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1（C1，D1）D1第二十三頁，共一百一十二頁，2022年，8月28日2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)最優(yōu)決策狀態(tài)A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E從A到E的最短路徑為19，路線為A→B2→C1→D1→E第二十四頁，共一百一十二頁，2022年，8月28日綜上所述可見，全枚舉法雖可找出最優(yōu)方案，但不是個(gè)好算法，局部最優(yōu)法則完全是個(gè)錯(cuò)誤方法，只有動(dòng)態(tài)規(guī)劃方法屬較科學(xué)有效的算法。它的基本思想是，把一個(gè)比較復(fù)雜的問題分解為一系列同類型的更易求解的子問題，便于應(yīng)用計(jì)算機(jī)。整個(gè)求解過程分為兩個(gè)階段，先按整體最優(yōu)的思想逆序地求出各個(gè)子問題中所有可能狀態(tài)的最優(yōu)決策與最優(yōu)路線值，然后再順序地求出整個(gè)問題的最優(yōu)策略和最優(yōu)路線。計(jì)算過程中，系統(tǒng)地刪去了所有中間非最優(yōu)的方案組合，從而使計(jì)算工作量比窮舉法大為減少。第二十五頁，共一百一十二頁，2022年，8月28日第二節(jié)

動(dòng)態(tài)規(guī)劃的基本概念和基本原理多階段決策過程：整個(gè)決策過程可按時(shí)間或空間順序分解成若干相互聯(lián)系的階段，每一階段都需作出決策，全部過程的決策是一個(gè)決策序列。多階段決策過程最優(yōu)化的目標(biāo)：達(dá)到整個(gè)活動(dòng)過程的總體效果最優(yōu)，而非各單個(gè)階段最優(yōu)的簡單總和。

使用動(dòng)態(tài)規(guī)劃方法解決多階段決策問題，首先要將實(shí)際問題寫成動(dòng)態(tài)規(guī)劃模型，同時(shí)也為了今后敘述和討論方便，這里需要對動(dòng)態(tài)規(guī)劃的下述一些基本術(shù)語進(jìn)一步加以說明和定義：第二十六頁，共一百一十二頁，2022年，8月28日1、階段（stage）為了便于求解和表示決策過程的發(fā)展順序，而把所給問題恰當(dāng)?shù)貏澐譃槿舾蓚€(gè)相互聯(lián)系又有區(qū)別的子問題，稱之為多段決策問題的階段。一個(gè)階段，就是需要作出一個(gè)決策的子問題，通常，階段是按決策進(jìn)行的時(shí)間順序或空間特征上先后順序劃分的。用以描述階段的變量叫作階段變量，一般以k表示階段變量．階段數(shù)等于多段決策過程從開始到結(jié)束所需作出決策的數(shù)目，例如上面的最短路問題就是一個(gè)四階段決策過程。第二十七頁，共一百一十二頁，2022年，8月28日2、狀態(tài)（state）每個(gè)階段開始時(shí)過程所處的自然狀況或客觀條件。反映狀態(tài)變化的量叫做狀態(tài)變量，它可以用一個(gè)數(shù)，一組數(shù)或一向量來描述，

。狀態(tài)變量必須包含在給定的階段上確定全部允許決策所需要的信息。它應(yīng)能描述過程的特征并具有“無后效性”，即當(dāng)前階段狀態(tài)給定時(shí)，這個(gè)階段以后過程的演變與該階段以前各階段的狀態(tài)無關(guān)。用sk表示狀態(tài)變量（statevariable）。第二十八頁，共一百一十二頁，2022年，8月28日一般狀態(tài)變量的取值有一定的范圍或允許集合，稱為可能狀態(tài)集（setofadmissiblestates）?？赡軤顟B(tài)集實(shí)際上是關(guān)于狀態(tài)的約束條件。通?？赡軤顟B(tài)集用相應(yīng)階段狀態(tài)sk的大寫字母Sk表示，可能狀態(tài)集可以是一離散取值的集合，也可以為一連續(xù)的取值區(qū)間，視具體問題而定．例如上面的最短路問題中，第一階段狀態(tài)為A，狀態(tài)變量s1的狀態(tài)集合S1={A}；第二階段則有三個(gè)狀態(tài)：B1,B2,B3,狀態(tài)變量s2的狀態(tài)集合S2={B1,B2,B3}

.第二十九頁，共一百一十二頁，2022年，8月28日3、決策（decision）

當(dāng)一個(gè)階段的狀態(tài)確定后，可以作出不同的決定或選擇，從而演變到下一階段的某個(gè)狀態(tài)，這種決定或選擇稱為決策。用以描述決策變化的量稱之決策變量（decisionvariable）。和狀態(tài)變量一樣，決策變量可以用一個(gè)數(shù)，一組數(shù)或一向量來描述，由于各階段的決策取決于狀態(tài)變量sk，所以用uk(sk)，表示階段k的狀態(tài)為sk時(shí)的決策變量。決策變量的取值往往也有一定的允許范圍，稱之允許決策集合（setofadmissibledecision）。決策變量uk(sk)的允許決策集用Uk(sk)表示,允許決策集合實(shí)際是決策的約束條件。第三十頁，共一百一十二頁，2022年，8月28日

4、策略（policy）

一組有序的決策序列構(gòu)成一個(gè)策略，從第k階段至第n階段的一個(gè)策略稱為k后部子策略記為pk,n(sk)={uk，uk+1，…，un}，當(dāng)k=1時(shí)的k部子策略稱為全過程策略，簡稱策略，記為p1,n(s1)。在實(shí)際問題中，由于在各個(gè)階段可供選擇的決策有許多個(gè)，因此，它們的不同組合就構(gòu)成了許多可供選擇的決策序列(策略)，由它們組成的集合，稱之允許策略集合，記作P1,n，從允許策略集中，找出具有最優(yōu)效果的策略稱為最優(yōu)策略。第三十一頁，共一百一十二頁，2022年，8月28日5、狀態(tài)轉(zhuǎn)移方程（equationofstatetransition）反映前后階段狀態(tài)之間關(guān)系的方程稱為狀態(tài)轉(zhuǎn)移方程。在確定型多階段決策過程中，一旦某階段的狀態(tài)和決策為已知，下一階段的狀態(tài)便完全確定，用狀態(tài)轉(zhuǎn)移方程反映這種狀態(tài)間的演變規(guī)律，記作：有些問題的狀態(tài)轉(zhuǎn)移方程不一定存在數(shù)學(xué)表達(dá)式，但是它們的狀態(tài)轉(zhuǎn)移，還是有一定規(guī)律可循的。第三十二頁，共一百一十二頁，2022年，8月28日6、階段指標(biāo)值（objectivevalueinastage）階段指標(biāo)值是第k階段的狀態(tài)為sk和采取決策uk時(shí)的效益，通常表示為dk(sk，uk)。對不同問題，階段指標(biāo)值可以是諸如費(fèi)用、成本、產(chǎn)值、利潤、產(chǎn)量、耗量、距離、時(shí)間，等等。例如上面的最短路問題中，如果第二階段地狀態(tài)為B2,采取決策是由B2到達(dá)C1,則階段指標(biāo)值為6。第三十三頁，共一百一十二頁，2022年，8月28日7、指標(biāo)函數(shù)（objectivefunction）衡量在選定某策略時(shí)，其優(yōu)劣的數(shù)量指標(biāo)。定義在整個(gè)過程（1到n階段）上的指標(biāo)函數(shù)記為：V1,n（s1，u1，s2，…，sn，un），定義在后部子過程（k到n階段）上的指標(biāo)函數(shù)記為：Vk,n（sk，uk，…，sn，un）。Vk,n（sk，uk，…，sn，un）表示第k階段處于sk狀態(tài)且所作決策為uk,uk+1,…,un時(shí)的決策效果。由此可見，Vk,n（sk，uk，…，sn，un）不僅跟當(dāng)前狀態(tài)sk有關(guān)，還跟該子過程策略pk,n(sk)有關(guān)，因此它是sk和pk,n(sk)的函數(shù)，因此它可簡記為：Vk,n（sk，pk,n）第三十四頁，共一百一十二頁，2022年，8月28日指標(biāo)函數(shù)Vk,n(sk,pk,n)通常是描述所實(shí)現(xiàn)的全過程或k后部子過程效果優(yōu)劣的數(shù)量指標(biāo)，它是由各階段的階段指標(biāo)函數(shù)dk(sk,uk)累積形成的，適于用動(dòng)態(tài)規(guī)劃求解的問題的指標(biāo)函數(shù)，必須具有關(guān)于階段指標(biāo)的可分離形式．對于后部子過程的指標(biāo)函數(shù)可以表示為：式中，表示某種運(yùn)算，可以是加、減、乘、除、開方等。第三十五頁，共一百一十二頁，2022年，8月28日總之，具體問題的目標(biāo)函數(shù)表達(dá)形式需要視具體問題而定。多階段決策問題中，常見的目標(biāo)函數(shù)形式之一是取各階段效應(yīng)之和的形式，即:有些問題，如系統(tǒng)可靠性問題，其目標(biāo)函數(shù)是取各階段效應(yīng)的連乘積形式，如：第三十六頁，共一百一十二頁，2022年，8月28日8、最優(yōu)指標(biāo)函數(shù)（optimalvaluefunction）指標(biāo)函數(shù)的最優(yōu)值稱為最優(yōu)指標(biāo)函數(shù)，記為fk(sk)，它表示從第k階段狀態(tài)sk出發(fā)，采用最優(yōu)策略到終止?fàn)顟B(tài)時(shí)的后部子過程指標(biāo)函數(shù)值，即式中opt即optimization，根據(jù)具體問題可取max或min。與它相應(yīng)的子策略稱為在sk狀態(tài)下的最優(yōu)子策略，記為pk*(sk)；而構(gòu)成該子策略的各段決策稱為該過程上的最優(yōu)決策，記為第三十七頁，共一百一十二頁，2022年，8月28日即

簡記為特別當(dāng)k=1時(shí)，f1(s1)就是問題的最優(yōu)值，而p1*就是最優(yōu)策略。例如上面的最短路問題中，有唯一最優(yōu)值f1(s1)=18，而就是其最優(yōu)策略。第三十八頁，共一百一十二頁，2022年，8月28日

多階段決策問題的數(shù)學(xué)模型綜上所述，適于應(yīng)用動(dòng)態(tài)規(guī)劃方法求解的一類多階段決策問題，亦即具有無后效性的多階段決策問題的數(shù)學(xué)模型呈以下形式:第三十九頁，共一百一十二頁，2022年，8月28日則對上述策略中所隱含的任一狀態(tài)而言，第k子過程上對應(yīng)于該狀態(tài)的最優(yōu)策略必然包含在上述全過程最優(yōu)策略p1*中，即為最優(yōu)化原理（貝爾曼最優(yōu)化原理）作為一個(gè)全過程的最優(yōu)策略具有這樣的性質(zhì)：對于最優(yōu)策略過程中的任意狀態(tài)而言，無論其過去的狀態(tài)和決策如何，余下的諸決策必構(gòu)成一個(gè)最優(yōu)子策略。該原理的具體解釋是，若某一全過程最優(yōu)策略為：第四十頁，共一百一十二頁，2022年，8月28日其中，表示從狀態(tài)sk到由決策uk(sk)所決定的狀態(tài)sk+1之間的距離。動(dòng)態(tài)規(guī)劃的基本方程在上面最短路問題的求解過程中，在求解的各階段利用了第k階段和第k+1階段的如下遞推關(guān)系：第三節(jié)動(dòng)態(tài)規(guī)劃模型的建立與求解

第四十一頁，共一百一十二頁，2022年，8月28日一般地，對于n個(gè)階段的決策過程，假設(shè)只考慮指標(biāo)函數(shù)是“和”與“積”的形式，第k階段和第k+1階段間的遞推公式可表示如下：(1)當(dāng)指標(biāo)函數(shù)為下列“和”的形式時(shí)，其相應(yīng)的基本方程為是邊界條件。第四十二頁，共一百一十二頁，2022年，8月28日(2)當(dāng)過程指標(biāo)函數(shù)為下列“積”的形式時(shí),其相應(yīng)的基本方程為一般來說,要用函數(shù)基本方程逆推求解,首先要有效地建立動(dòng)態(tài)規(guī)劃模型,然后再遞推求解,最后得出結(jié)論.然而,要把一個(gè)實(shí)際問題用動(dòng)態(tài)規(guī)劃方法來求解,還必須首先根據(jù)問題的要求。把它構(gòu)造成動(dòng)態(tài)規(guī)劃模型,這是非常重要的一步。正確地建立一個(gè)動(dòng)態(tài)規(guī)劃模型,往往問題也就解決了一大半,而一個(gè)正確的動(dòng)態(tài)規(guī)劃模型,應(yīng)該滿足哪些條件呢?第四十三頁，共一百一十二頁，2022年，8月28日建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型的步驟

1．應(yīng)將實(shí)際問題恰當(dāng)?shù)胤指畛蒼個(gè)子問題(n個(gè)階段)。通常是根據(jù)時(shí)間或空間而劃分的，或者在經(jīng)由靜態(tài)的數(shù)學(xué)規(guī)劃模型轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃模型時(shí)，常取靜態(tài)規(guī)劃中變量的個(gè)數(shù)n，即k=n。2．正確地定義狀態(tài)變量sk，使它既能正確地描述過程的狀態(tài)，又能滿足無后效性．動(dòng)態(tài)規(guī)劃中的狀態(tài)與一般控制系統(tǒng)中和通常所說的狀態(tài)的概念是有所不同的，動(dòng)態(tài)規(guī)劃中的狀態(tài)變量必須具備以下三個(gè)特征：第四十四頁，共一百一十二頁，2022年，8月28日(1)要能夠正確地描述受控過程的變化特征。(2)要滿足無后效性。即如果在某個(gè)階段狀態(tài)已經(jīng)給定，那么在該階段以后，過程的發(fā)展不受前面各段狀態(tài)的影響，如果所選的變量不具備無后效性，就不能作為狀態(tài)變量來構(gòu)造動(dòng)態(tài)規(guī)劃的模型。(3)要滿足可知性。即所規(guī)定的各段狀態(tài)變量的值，可以直接或間接地測算得到。一般在動(dòng)態(tài)規(guī)劃模型中，狀態(tài)變量大都選取那種可以進(jìn)行累計(jì)的量。此外，在與靜態(tài)規(guī)劃模型的對應(yīng)關(guān)系上，通常根據(jù)經(jīng)驗(yàn)，線性與非線性規(guī)劃中約束條件的個(gè)數(shù)，相當(dāng)于動(dòng)態(tài)規(guī)劃中狀態(tài)變量sk的維數(shù)．而前者約束條件所表示的內(nèi)容，常就是狀態(tài)變量sk所代表的內(nèi)容。第四十五頁，共一百一十二頁，2022年，8月28日3．正確地定義決策變量及各階段的允許決策集合Uk(sk)，根據(jù)經(jīng)驗(yàn)，一般將問題中待求的量，選作動(dòng)態(tài)規(guī)劃模型中的決策變量。或者在把靜態(tài)規(guī)劃模型(如線性與非線性規(guī)劃)轉(zhuǎn)換為動(dòng)態(tài)規(guī)劃模型時(shí)，常取前者的變量xj為后者的決策變量uk。4.能夠正確地寫出狀態(tài)轉(zhuǎn)移方程，至少要能正確反映狀態(tài)轉(zhuǎn)移規(guī)律。如果給定第k階段狀態(tài)變量sk的值，則該段的決策變量uk一經(jīng)確定，第k+1段的狀態(tài)變量sk+1的值也就完全確定，即有sk+1=Tk(sk,uk)第四十六頁，共一百一十二頁，2022年，8月28日5．根據(jù)題意,正確地構(gòu)造出目標(biāo)與變量的函數(shù)關(guān)系——目標(biāo)函數(shù)，目標(biāo)函數(shù)應(yīng)滿足下列性質(zhì)：(1)可分性，即對于所有k后部子過程，其目標(biāo)函數(shù)僅取決于狀態(tài)sk及其以后的決策uk,uk+1,┈,un,就是說它是定義在全過程和所有后部子過程上的數(shù)量函數(shù)。(2)要滿足遞推關(guān)系，即

(3)函數(shù)對其變元Vk+1,n來說要嚴(yán)格單調(diào)。第四十七頁，共一百一十二頁，2022年，8月28日6．寫出動(dòng)態(tài)規(guī)劃函數(shù)基本方程例如常見的指標(biāo)函數(shù)是取各段指標(biāo)和的形式

其中表示第i階段的指標(biāo)，它顯然是滿足上述三個(gè)性質(zhì)的。所以上式可以寫成：第四十八頁，共一百一十二頁，2022年，8月28日第五節(jié)動(dòng)態(tài)規(guī)劃在經(jīng)濟(jì)管理中的應(yīng)用

一、資源分配問題假設(shè)有一種資源，數(shù)量為a，將其分配給n個(gè)使用者，分配給第i個(gè)使用者數(shù)量xi時(shí)，相應(yīng)的收益為gi（xi），問如何分配使得總收入最大？這就是一維資源分配問題，該問題的數(shù)學(xué)模型為：（6.23）第四十九頁，共一百一十二頁，2022年，8月28日式（6.23）是一個(gè)靜態(tài)規(guī)劃問題，應(yīng)用動(dòng)態(tài)規(guī)劃方法求解時(shí)人為賦予時(shí)間概念，將其看作是一個(gè)多階段決策問題。按變量個(gè)數(shù)劃分階段，k=1，2，…，n；設(shè)決策變量uk=xk，表示分配給第k個(gè)使用者的資源數(shù)量；設(shè)狀態(tài)變量為sk，表示分配給第k個(gè)至第n個(gè)使用者的總資源數(shù)量；狀態(tài)轉(zhuǎn)移方程：sk+1=sk－xk，其中s1=a；允許決策集合：Dk(sk)=｛xk|0≤xk≤sk｝階段指標(biāo)函數(shù)：vk(sk，uk)=gk(xk)表示分配給第k個(gè)使用者數(shù)量xk時(shí)的收益；第五十頁，共一百一十二頁，2022年，8月28日最優(yōu)指標(biāo)函數(shù)fk(sk)表示以數(shù)量sk的資源分配給第k個(gè)至第n個(gè)使用者所得到的最大收益，則動(dòng)態(tài)規(guī)劃基本方程為：由后向前逐段遞推，f1(a)即為所求問題的最大收益。第五十一頁，共一百一十二頁，2022年，8月28日例7某公司打算在3個(gè)不同的地區(qū)設(shè)置4個(gè)銷售點(diǎn)，根據(jù)市場部門估計(jì)，在不同地區(qū)設(shè)置不同數(shù)量的銷售點(diǎn)每月可得到的利潤如表6.4所示。試問在各地區(qū)如何設(shè)置銷售點(diǎn)可使每月總利潤最大。表6.4利潤值地區(qū)銷售點(diǎn)01234123000161210251714302116322217第五十二頁，共一百一十二頁，2022年，8月28日解：如前所述，建立動(dòng)態(tài)規(guī)劃數(shù)學(xué)模型：將問題分為3個(gè)階段，k=1，2，3；決策變量xk表示分配給第k個(gè)地區(qū)的銷售點(diǎn)數(shù)；狀態(tài)變量為sk表示分配給第k個(gè)至第3個(gè)地區(qū)的銷售點(diǎn)總數(shù)；狀態(tài)轉(zhuǎn)移方程：sk+1=sk－xk，其中s1=4；允許決策集合：Dk（sk）=｛xk|0≤xk≤sk｝階段指標(biāo)函數(shù)：gk（xk）表示xk個(gè)銷售點(diǎn)分配給第k個(gè)地區(qū)所獲得的利潤；最優(yōu)指標(biāo)函數(shù)fk（sk）表示將數(shù)量為sk的銷售點(diǎn)分配給第k個(gè)至第3個(gè)地區(qū)所得到的最大利潤，動(dòng)態(tài)規(guī)劃基本方程為：第五十三頁，共一百一十二頁，2022年，8月28日數(shù)值計(jì)算如表所示。表6.5k=3時(shí)計(jì)算結(jié)果fx3s3g3（x3）f3(s3)x3*0123401234000001010101014141416161701014161701234第五十四頁，共一百一十二頁，2022年，8月28日表6.6k=2時(shí)計(jì)算結(jié)果g2(x2)+f3(s2－x2)f2(s2)x2*012340123400+100+140+160+1712+012+1012+1412+1617+017+1017+1421+021+1022+001222273101122,3fx3s3fx3s3表6.7k=1時(shí)計(jì)算結(jié)果g1(x1)+f2(s1－x1)f1(s1)x1*0123440+3116+2725+2230+1232+0472第五十五頁，共一百一十二頁，2022年，8月28日所以最優(yōu)解為：x1*=2，x2*=1，x3*=1，f1(4)=47，即在第1個(gè)地區(qū)設(shè)置2個(gè)銷售點(diǎn)，第2個(gè)地區(qū)設(shè)置1個(gè)銷售點(diǎn)，第3個(gè)地區(qū)設(shè)置1個(gè)銷售點(diǎn)，每月可獲利潤47。這個(gè)例子是決策變量取離散值的一類分配問題，在實(shí)際問題中，相類似的問題還有設(shè)備或人力資源的分配問題等。在資源分配問題中，還有一種決策變量為連續(xù)變量的資源分配問題，見下面例子。第五十六頁，共一百一十二頁，2022年，8月28日例8機(jī)器負(fù)荷問題某種機(jī)器可在高低兩種不同的負(fù)荷下進(jìn)行生產(chǎn)，設(shè)機(jī)器在高負(fù)荷下生產(chǎn)的產(chǎn)量（件）函數(shù)為g1=8x，其中x為投入高負(fù)荷生產(chǎn)的機(jī)器數(shù)量，年度完好率α=0.7（年底的完好設(shè)備數(shù)等于年初完好設(shè)備數(shù)的70%）；在低負(fù)荷下生產(chǎn)的產(chǎn)量（件）函數(shù)為g2=5y，，其中y為投入低負(fù)荷生產(chǎn)的機(jī)器數(shù)量，年度完好率β=0.9。假定開始生產(chǎn)時(shí)完好的機(jī)器數(shù)量為1000臺(tái)，試問每年應(yīng)如何安排機(jī)器在高、低負(fù)荷下的生產(chǎn)，才能使5年生產(chǎn)的產(chǎn)品總量最多？第五十七頁，共一百一十二頁，2022年，8月28日解：設(shè)階段k表示年度（k=1,2,3,4,5）；狀態(tài)變量Sk為第k年度初擁有的完好機(jī)器數(shù)量（同時(shí)也是第k-1年度末時(shí)的完好機(jī)器數(shù)量）。決策變量xk為第k年度分配高負(fù)荷下生產(chǎn)的機(jī)器數(shù)量，于是Sk-xk為該年度分配在低負(fù)荷下生產(chǎn)的機(jī)器數(shù)量。這里的Sk和xk均為連續(xù)變量，它們的非整數(shù)值可以這樣理解：如Sk=0.6就表示一臺(tái)機(jī)器在第k年度中正常工作時(shí)間只占全部時(shí)間的60%；xk=0.3就表示一臺(tái)機(jī)器在第k年度中只有30%的工作時(shí)間在高負(fù)荷下運(yùn)轉(zhuǎn)。狀態(tài)轉(zhuǎn)移方程為：第五十八頁，共一百一十二頁，2022年，8月28日允許決策集合：設(shè)階段指標(biāo)Qk(Sk,xk)為第k年度的產(chǎn)量，則：過程指標(biāo)是階段指標(biāo)的和，即：令最優(yōu)值函數(shù)fk(Sk)表示從資源量Sk出發(fā)，采取最優(yōu)子策略所生產(chǎn)的產(chǎn)品總量，因而有逆推關(guān)系式：邊界條件f6(S6)=0。第五十九頁，共一百一十二頁，2022年，8月28日當(dāng)k=5時(shí)：因f5(S5)是關(guān)于x5的單調(diào)遞增函數(shù)，故取x5*=S5，相應(yīng)有f5(S5)=8S5。當(dāng)k=4時(shí)：第六十頁，共一百一十二頁，2022年，8月28日因f4(S4)是關(guān)于x4的單調(diào)遞增函數(shù)，故取x4*=S4，相應(yīng)有f4(S4)=13.6S4；依次類推，可求得：當(dāng)k=3時(shí)：x3*=S3，f3(S3)=17.5S3當(dāng)k=2時(shí)：x2*=0，f2(S2)=20.8S2當(dāng)k=1時(shí)：x1*=0，f1(S1=1000)=23.7S1=23700計(jì)算結(jié)果表明最優(yōu)策略為：x1*=0，x2*=0，x3*=S3，x4*=S4，x5*=S5；即前兩年將全部設(shè)備都投入低負(fù)荷生產(chǎn)，后三年將全部設(shè)備都投入高負(fù)荷生產(chǎn)，這樣可以使5年的總產(chǎn)量最大，最大產(chǎn)量是23700件。有了上述最優(yōu)策略，各階段的狀態(tài)也就隨之確定了，即按階段順序計(jì)算出各年年初的完好設(shè)備數(shù)量。第六十一頁，共一百一十二頁，2022年，8月28日上面所討論的過程始端狀態(tài)S1是固定的，而終端狀態(tài)S6是自由的，實(shí)現(xiàn)的目標(biāo)函數(shù)是5年的總產(chǎn)量最高。第六十二頁，共一百一十二頁，2022年，8月28日二、生產(chǎn)與存貯問題在生產(chǎn)和經(jīng)營管理中，經(jīng)常遇到要合理地安排生產(chǎn)（或購買）與庫存問題，達(dá)到既要滿足社會(huì)的需要，又要盡量降低成本費(fèi)用，因此，正確制定生產(chǎn)（后采購）策略，確定不同時(shí)期的生產(chǎn)量（或采購量）和庫存量，以使總的生產(chǎn)成本費(fèi)和庫存費(fèi)用之和最小，這就是生產(chǎn)與存貯問題的最有目標(biāo)第六十三頁，共一百一十二頁，2022年，8月28日1.生產(chǎn)計(jì)劃問題例9（生產(chǎn)—庫存問題）某工廠要對一種產(chǎn)品制定今后四個(gè)時(shí)期的生產(chǎn)計(jì)劃，據(jù)估計(jì)在今后四個(gè)時(shí)期內(nèi)，市場對該產(chǎn)品的需求量分別為2，3，2，4單位，假設(shè)每批產(chǎn)品固定成本為3千元，若不生產(chǎn)為0，每單位產(chǎn)品成本為1千元，每個(gè)時(shí)期最大生產(chǎn)能力不超過6個(gè)單位，每期期末未出售產(chǎn)品，每單位需付存貯費(fèi)0.5千元，假定第1期初和第4期末庫存量均為0，問該廠如何安排生產(chǎn)與庫存，可在滿足市場需求的前提下總成本最小。第六十四頁，共一百一十二頁，2022年，8月28日解:以每個(gè)時(shí)期作為一個(gè)階段，該問題分為4個(gè)階段，k=1，2，3，4；決策變量xk表示第k階段生產(chǎn)的產(chǎn)品數(shù)；狀態(tài)變量sk表示第k階段初的庫存量；以dk表示第k階段的需求，則狀態(tài)轉(zhuǎn)移方程：sk+1=sk+xk－dk；k=4，3，2，1由于期初及期末庫存為0，所以s1=0，s5=0；允許決策集合Dk（sk）的確定：當(dāng)sk≥dk時(shí)，xk可以為0，當(dāng)sk<dk時(shí)，至少應(yīng)生產(chǎn)dk－sk，故xk的下限為max（0，dk－sk）每期最大生產(chǎn)能力為6，xk最大不超過6，由于期末庫存為0，xk還應(yīng)小于本期至4期需求之和減去本期的庫存量，第六十五頁，共一百一十二頁，2022年，8月28日所以xk的上限為故有：階段指標(biāo)函數(shù)rk（sk，xk）表示第k期的生產(chǎn)費(fèi)用與存貯費(fèi)用之和：最優(yōu)指標(biāo)函數(shù)fk（sk）表示第k期庫存為sk到第4期末的生產(chǎn)與存貯最低費(fèi)用，動(dòng)態(tài)規(guī)劃基本方程為：第六十六頁，共一百一十二頁，2022年，8月28日先求出各狀態(tài)允許狀態(tài)集合及允許決策集合，如表6.8所示。表6.8狀態(tài)允許狀態(tài)集合及允許決策集合s10D1(s1)｛2,3,4,5,6｝s201234D2(s2)｛3,4,5,6｝｛2,3,4,5,6｝｛1,2,3,4,5,6｝｛0,1,2,3,4,5,6｝｛0,1,2,3,4,5｝s30123456D3(s3)｛2,3,4,5,6｝｛1,2,3,4,5｝｛0,1,2,3,4｝｛0,1,2,3｝｛0,1,2｝｛0,1｝｛0｝s401234D4(s4)｛4｝｛3｝｛2｝｛1｝｛0｝第六十七頁，共一百一十二頁，2022年，8月28日由基本方程計(jì)算各階段策略，結(jié)果如下表所示。表6.9k=4時(shí)計(jì)算結(jié)果s4x4r4(s4,x4)f4(s4)x4*012344321076.565.527*6.5*6*5.5*2*4*3*2*1*0*第六十八頁，共一百一十二頁，2022年，8月28日表6.10k=3時(shí)計(jì)算結(jié)果x3s3r3（s3,x3）+f4(s4)f3(s3)x3*012345601234561+71.5+6.52+62.5+5.53+24.5+75+6.55.5+66+5.56.5+25+75.5+6.56+66.5+5.57+26+6.56.5+67+5.57.5+27+67.5+5.58+28+5.58.5+29+21110.5888856500000第六十九頁，共一百一十二頁，2022年，8月28日表6.11k=2時(shí)計(jì)算結(jié)果x2s2r2（s2,x2）+f3(s3)f2(s2)x2*0123456012341.5+112+10.55+115.5+10.56+85.5+116+10.56.5+87+86+116.5+10.57+87.5+88+87+10.57.5+88+88.5+89+88+88.5+89+89.5+810+59+89.5+810+810.5+51615.51512.5854300第七十頁，共一百一十二頁，2022年，8月28日表6.12k=1時(shí)計(jì)算結(jié)果x1s1r1（s1,x1）+f2(s2)f1(s1)x1*2345605+166+15.57+158+12.59+12.520.55逆向追蹤可得：x1*=5，s2=3，x2*=0，s3=0，x3*=6，s4=4，x4*=0，即第1時(shí)期生產(chǎn)5個(gè)單位，第3時(shí)期生產(chǎn)6個(gè)單位，第2，4時(shí)期不生產(chǎn)，可使總費(fèi)用最小，最小費(fèi)用為20.5千元。第七十一頁，共一百一十二頁，2022年，8月28日例11某鞋店銷售一種雪地防潮鞋，以往的銷售經(jīng)歷表明，此種鞋的銷售季節(jié)是從10月1日至3月31日。下個(gè)銷售季節(jié)各月的需求預(yù)測值如表6.14所示。表6.14需求預(yù)測值(單位：雙)月份101112123需求402030403020該鞋店的此種鞋完全從外部生產(chǎn)商進(jìn)貨，進(jìn)貨價(jià)每雙4美元。進(jìn)貨批量的基本單位是箱，每箱10雙。由于存貯空間的限制，每次進(jìn)貨不超過5箱。對應(yīng)不同的訂貨批量，進(jìn)價(jià)享受一定的數(shù)量折扣，具體數(shù)值如表6.15所示。第七十二頁，共一百一十二頁，2022年，8月28日表6.15數(shù)量折扣數(shù)值表進(jìn)貨批量1箱2箱3箱4箱5箱數(shù)量折扣4%5%10%20%25%假設(shè)需求是按一定速度均勻發(fā)生的，訂貨不需時(shí)間，但訂貨只能在月初辦理一次，每次訂貨的采購費(fèi)（與采購數(shù)量無關(guān)）為10美元。月存貯費(fèi)按每月月底鞋的存量計(jì)，每雙0.2美元。由于訂貨不需時(shí)間，所以銷售季節(jié)外的其他月份的存貯量為“0”。試確定最佳的進(jìn)貨方案，以使總的銷售費(fèi)用最小。第七十三頁，共一百一十二頁，2022年，8月28日解：階段：將銷售季節(jié)6個(gè)月中的每一個(gè)月作為一個(gè)階段，即k=1,2,…,6；狀態(tài)變量：第k階段的狀態(tài)變量Sk代表第k個(gè)月初鞋的存量；決策變量：決策變量xk代表第k個(gè)月的采購批量；狀態(tài)轉(zhuǎn)移律：：sk+1=sk+xk－dk（dk是第k個(gè)月的需求量）；邊界條件：s1=s7=0，f7(s7)=0；階段指標(biāo)函數(shù)：rk(sk,xk)代表第k個(gè)月所發(fā)生的全部費(fèi)用，即與采購數(shù)量無關(guān)的采購費(fèi)Ck、與采購數(shù)量成正比的購置費(fèi)Gk和存貯費(fèi)Zk.其中：

第七十四頁，共一百一十二頁，2022年，8月28日最優(yōu)指標(biāo)函數(shù)：最優(yōu)指標(biāo)函數(shù)具有如下遞推形式當(dāng)k=6時(shí)（3月）：表6.16k=6時(shí)計(jì)算結(jié)果S601020x620100f6（S6）86480第七十五頁，共一百一十二頁，2022年，8月28日當(dāng)k=5時(shí)（2月）：表6.17k=5時(shí)計(jì)算結(jié)果x5S501020304050x5*f5(s5)020418816450164101721681424014220134136122301223086989008640505205050404第七十六頁，共一百一十二頁，2022年，8月28日當(dāng)k=4時(shí)（1月）：表6.18k=4

時(shí)計(jì)算結(jié)果x4S401020304050x4*f4(s4)0302304403021028228228630、4028220250262264252202503021223024423021810212401641922122101961700164501441741781761520144601261401441320126第七十七頁，共一百一十二頁，2022年，8月28日當(dāng)k=3時(shí)（12月）：表6.19k=3時(shí)計(jì)算結(jié)果x3S301020304050x3*f3(s4)04204224145041410388402392384503842035037037236233250332303023323403423103140302402843023102902922980284第七十八頁，共一百一十二頁，2022年，8月28日當(dāng)k=2時(shí)（11月）：表6.20k=2時(shí)計(jì)算結(jié)果x2S201020304050x2*f2(s2)0500504474468504681046247245444645240446當(dāng)k=1時(shí)（10月）：表6.21k=1時(shí)計(jì)算結(jié)果x1S101020304050x1*f1(s1)060660840606第七十九頁，共一百一十二頁，2022年，8月28日利用狀態(tài)轉(zhuǎn)移律，按上述計(jì)算的逆序可推算出最優(yōu)策略：10月份采購4箱（40雙），11月份采購5箱（50雙），12月份不采購，1月份采購4箱（40雙），2月份采購5箱（50雙），3月份不采購；最小的銷售費(fèi)用為606美元。第八十頁，共一百一十二頁，2022年，8月28日三、背包問題有人攜帶背包上山，其可攜帶物品的重量限度為a公斤，現(xiàn)有n種物品可供選擇，設(shè)第i種物品的單件重量為ai公斤，其在上山過程中的價(jià)值是攜帶數(shù)量xi的函數(shù)ci（xi），問應(yīng)如何安排攜帶各種物品的數(shù)量，使總價(jià)值最大。這就是背包問題，類似的貨物裝載問題，下料問題都等同于背包問題。背包問題的數(shù)學(xué)模型為：第八十一頁，共一百一十二頁，2022年，8月28日下面用動(dòng)態(tài)規(guī)劃方法求解：按照裝入物品的種類劃分階段，k=1，2，…，n；狀態(tài)變量sk表示裝入第k種至第n種物品的總重量；決策變量xk表示裝入第k種物品的件數(shù)；狀態(tài)轉(zhuǎn)移方程為：sk+1=sk－akxk允許決策集合為： 其中階段指標(biāo)函數(shù)ck（xk）表示第k階段裝入第k種商品xk件時(shí)的價(jià)值；表示不超過的最大整數(shù)；第八十二頁，共一百一十二頁，2022年，8月28日最優(yōu)指標(biāo)函數(shù)fk（sk）表示第k階段裝入物品總重量為sk時(shí)的最大價(jià)值，動(dòng)態(tài)規(guī)劃基本方程為：例13某工廠生產(chǎn)三種產(chǎn)品，各產(chǎn)品重量與利潤關(guān)系如表6.24所示，現(xiàn)將此三種產(chǎn)品運(yùn)往市場銷售，運(yùn)輸能力總重量不超過6噸，問如何安排運(yùn)輸使總利潤最大？表6.24重量與利潤關(guān)系表種類123單位重量（噸）234單位利潤（元）80130180第八十三頁，共一百一十二頁，2022年，8月28日解：設(shè)xi為裝載第i種貨物的件數(shù)，i=1,2,3，該問題數(shù)學(xué)模型為：按照裝入物品的種類劃分階段，k=1，2，3；狀態(tài)變量sk表示裝入第k種至第n種物品的總重量；決策變量xk表示裝入第k種物品的件數(shù)；狀態(tài)轉(zhuǎn)移方程為：sk+1=sk－akxk第八十四頁，共一百一十二頁，2022年，8月28日表6.25k=3時(shí)計(jì)算結(jié)果x3s3

c3(x3)f3(s3)x3*010,1,2,34,5,600180018001計(jì)算結(jié)果如表6.25所示。k=3時(shí)，第八十五頁，共一百一十二頁，2022年，8月28日表6.26k=2時(shí)計(jì)算結(jié)果x3s3

c2(x2)+f3(s2－3x2)f2(s2)x2*0120,1,234,560+00+00+1800+1800130+0130+0260+001301802600102計(jì)算結(jié)果如表6.26所示。k=2時(shí)，第八十六頁，共一百一十二頁，2022年，8月28日x3s3

c1(x1)+f2(s1－2x1)f1(s1)x1*012360+26080+180160+0240+02600,1反向追蹤得最優(yōu)方案Ⅰ：x1*=0，x2*=2，x3*=0；最優(yōu)方案Ⅱ：x1*=1，x2*=0，x3*=1最大總利潤為260元。表6.27k=1時(shí)計(jì)算結(jié)果k=1時(shí)，計(jì)算結(jié)果如表6.27所示。第八十七頁，共一百一十二頁，2022年，8月28日四、復(fù)合系統(tǒng)工作可靠性問題某個(gè)機(jī)器工作系統(tǒng)由n個(gè)部件串聯(lián)而成，其中只要有一個(gè)部件失效，則整個(gè)系統(tǒng)不能正常工作，因此為了提高系統(tǒng)工作的可靠性，在設(shè)計(jì)時(shí)，每個(gè)主要部件上都裝有備用元件，一旦某個(gè)主要部件失效，備用元件會(huì)自動(dòng)投入系統(tǒng)工作，顯然備用元件越多，系統(tǒng)工作可靠性越大，但是備用元件越多，系統(tǒng)的成本、重量、體積相應(yīng)增大，工作精度降低，因此在上述限制條件下，應(yīng)選擇合理的備用元件數(shù)，使整個(gè)系統(tǒng)的工作可靠性最大。第八十八頁，共一百一十二頁，2022年，8月28日設(shè)第i（i=1，2，…，n）個(gè)部件上裝有ui個(gè)備用元件，正常工作的概率為pi（ui），則整個(gè)系統(tǒng)正常工作的可靠性為裝第i個(gè)部件的費(fèi)用為ci，重量為wi，要求總費(fèi)用不超過c，總重量不超過w，則靜態(tài)規(guī)劃數(shù)學(xué)模型為：第八十九頁，共一百一十二頁，2022年，8月28日按部件個(gè)數(shù)劃分階段，k=1，2，…，n；決策變量uk表示部件k上的備用元件數(shù)；狀態(tài)變量xk表示從第k個(gè)到第n個(gè)部件的總費(fèi)用，

yk表示從第k個(gè)到第n個(gè)部件的總重量；狀態(tài)轉(zhuǎn)移方程為：xk+1=xk－ckukyk+1=yk－wkuk允許決策集合為：階段指標(biāo)函數(shù)為pk（uk），表示第k個(gè)部件的正常工作概率；第九十頁，共一百一十二頁，2022年，8月28日最優(yōu)指標(biāo)函數(shù)fk（xk，yk）表示由狀態(tài)xk，yk出發(fā)，從部件k到部件n的系統(tǒng)工作最大可靠性，則動(dòng)態(tài)規(guī)劃基本方程為：f1（c，w）即為整個(gè)系統(tǒng)工作的最大可靠性。第九十一頁，共一百一十二頁，2022年，8月28日例14某廠設(shè)計(jì)的一種電子設(shè)備由三種元件A、B、C串聯(lián)而成，已知三種元件的價(jià)格及可靠性如表6.28所示，要求設(shè)計(jì)中使用元件的總費(fèi)用不超過10萬元，問如何設(shè)計(jì)使設(shè)備的可靠性達(dá)到最大（不考慮重量限制）。表6.28價(jià)格及可靠性元件單價(jià)（萬元）單件可靠性A