規(guī)劃的綜合方法

1、規(guī)劃的綜合方法1、 線性規(guī)劃法 線性規(guī)劃（Linear programming,簡(jiǎn)稱LP）是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支，它是輔助人們進(jìn)行科學(xué)管理的一種數(shù)學(xué)方法。研究線性約束條件下線性目標(biāo)函數(shù)的極值問題的數(shù)學(xué)理論和方法。英文縮寫LP。它是運(yùn)籌學(xué)的一個(gè)重要分支，廣泛應(yīng)用于軍事作戰(zhàn)、經(jīng)濟(jì)分析、經(jīng)營(yíng)管理和工程技術(shù)等方面。為合理地利用有限的人力、物力、財(cái)力等資源作出的最優(yōu)決策，提供科學(xué)的依據(jù)。 線性規(guī)劃方法是在第二次世界大戰(zhàn)中發(fā)展起來的一種重要的數(shù)量方法，線性規(guī)劃方法是企業(yè)進(jìn)行總產(chǎn)量計(jì)劃時(shí)常用的一種定量方法。線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)最重要的分支，理論上最完善，實(shí)際應(yīng)用得

2、最廣泛。主要用于研究有限資源的最佳分配問題，即如何對(duì)有限的資源作出最佳方式地調(diào)配和最有利地使用，以便最充分地發(fā)揮資源的效能去獲取最佳的經(jīng)濟(jì)效益。由于有成熟的計(jì)算機(jī)應(yīng)用軟件的支持，采用線性規(guī)劃模型安排生產(chǎn)計(jì)劃，并不是一件困難的事情。在總體計(jì)劃中，用線性規(guī)劃模型解決問題的思路是，在有限的生產(chǎn)資源和市場(chǎng)需求條件約束下，求利潤(rùn)最大的總產(chǎn)量計(jì)劃。該方法的最大優(yōu)點(diǎn)是可以處理多品種問題。數(shù)學(xué)模型：1）列出約束條件及目標(biāo)函數(shù)2）畫出約束條件所表示的可行域3）在可行域內(nèi)求目標(biāo)函數(shù)的最優(yōu)解及最優(yōu)值從實(shí)際問題中建立數(shù)學(xué)模型一般有以下三個(gè)步驟；1.根據(jù)影響所要達(dá)到目的的因素找到?jīng)Q策變量；2.由決策變量和所在達(dá)到目的之

3、間的函數(shù)關(guān)系確定目標(biāo)函數(shù)；3.由決策變量所受的限制條件確定決策變量所要滿足的約束條件。所建立的數(shù)學(xué)模型具有以下特點(diǎn)：1、 每個(gè)模型都有若干個(gè)決策變量（x1，x2，x3，xn），其中n為決策變量個(gè)數(shù)。決策變量的一組值表示一種方案，同時(shí)決策變量一般是非負(fù)的。2、目標(biāo)函數(shù)是決策變量的線性函數(shù)，根據(jù)具體問題可以是最大化（max）或最小化（min），二者統(tǒng)稱為最優(yōu)化（opt）。3、約束條件也是決策變量的線性函數(shù)。當(dāng)我們得到的數(shù)學(xué)模型的目標(biāo)函數(shù)為線性函數(shù)，約束條件為線性等式或不等式時(shí)稱此數(shù)學(xué)模型為線性規(guī)劃模型。發(fā)展：法國(guó)數(shù)學(xué)家J.- B.- J.傅里葉和C.瓦萊普森分別于1832和1911年獨(dú)立地提出線性

4、規(guī)劃的想法，但未引起注意。1939年蘇聯(lián)數(shù)學(xué)家.康托羅維奇在生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法一書中提出線性規(guī)劃問題，也未引起重視。1947年美國(guó)數(shù)學(xué)家G.B.Dantzing提出求解線性規(guī)劃的單純形法，為這門學(xué)科奠定了基礎(chǔ)。1947年美國(guó)數(shù)學(xué)家J.von諾伊曼提出對(duì)偶理論,開創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力。1951年美國(guó)經(jīng)濟(jì)學(xué)家T.C.庫(kù)普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟(jì)領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。50年代后對(duì)線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如，1954年C.萊姆基提出對(duì)偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規(guī)劃的

5、靈敏度分析和參數(shù)規(guī)劃問題，1956年A.塔克提出互補(bǔ)松弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解算法等。 線性規(guī)劃的研究成果還直接推動(dòng)了其他數(shù)學(xué)規(guī)劃問題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計(jì)算機(jī)的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個(gè)變量的線性規(guī)劃問題。1979年蘇聯(lián)數(shù)學(xué)家L. G. Khachian提出解線性規(guī)劃問題的橢球算法，并證明它是多項(xiàng)式時(shí)間算法。1984年美國(guó)貝爾電話實(shí)驗(yàn)室的印度數(shù)學(xué)家N.卡馬卡提出解線性規(guī)劃問題的新的多項(xiàng)式時(shí)間算法。用這種方法求解線性規(guī)劃問題在變量個(gè)數(shù)為5000時(shí)只要單純形法所用

6、時(shí)間的1/50?，F(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論。50年代后線性規(guī)劃的應(yīng)用范圍不斷擴(kuò)大。實(shí)際運(yùn)用線性規(guī)劃模型進(jìn)行總生產(chǎn)計(jì)劃時(shí)需要注意的一些問題1、 線性規(guī)劃模型考慮的因素可能不全面，實(shí)際中有些情況沒有被考慮到，這就使得線性規(guī)劃模型過于理想化；2、實(shí)際運(yùn)用線性規(guī)劃模型時(shí)，雖然一些因素或約束條件被考慮到了，但是由于這些因素或約束條件不易量化或求得（如進(jìn)行總生產(chǎn)計(jì)劃常需考慮到的能源單耗就不易求得）時(shí)，線性規(guī)劃模型的運(yùn)用和有效性因而受到了一定的限制；3、對(duì)一些基礎(chǔ)管理不善的企業(yè)而言，模型中的單位產(chǎn)品資源消耗系數(shù)a很難得到；4、目標(biāo)函數(shù)中的產(chǎn)為成本系數(shù)c實(shí)際上是個(gè)變量，他隨計(jì)劃的數(shù)量結(jié)構(gòu)和品種結(jié)構(gòu)而變。這

7、些問題給機(jī)械行業(yè)應(yīng)用線性規(guī)劃模型帶來許多困難，如處理不好，求得的結(jié)果的可靠性會(huì)很低的。2、 多目標(biāo)決策法多目標(biāo)決策是對(duì)多個(gè)相互矛盾的目標(biāo)進(jìn)行科學(xué)、合理的選優(yōu)，然后作出決策的理論和方法。它是 20世紀(jì) 70年代后迅速發(fā)展起來的管理科學(xué)的一個(gè)新的分支。多目標(biāo)決策與只為了達(dá)到一個(gè)目標(biāo)而從許多可行方案中選出最佳方案的一般決策有所不同。在多目標(biāo)決策中，要同時(shí)考慮多種目標(biāo)，而這些目標(biāo)往往是難以比較的，甚至是彼此矛盾的；一般很難使每個(gè)目標(biāo)都達(dá)到最優(yōu)，作出各方面都很滿意的決策。因此多目標(biāo)決策實(shí)質(zhì)上是在各種目標(biāo)之間和各種限制之間求得一種合理的妥協(xié)，這就是多目標(biāo)最優(yōu)化的過程。國(guó)外一般認(rèn)為，多目標(biāo)優(yōu)化問題最早是在1

8、9世紀(jì)末由意大利經(jīng)濟(jì)學(xué)家帕累托（V.Pareto）從政治經(jīng)濟(jì)學(xué)的角度提出來的，他把許多本質(zhì)上不可比較的目標(biāo)，設(shè)法變換成一個(gè)單一的最優(yōu)目標(biāo)來進(jìn)行求解。到了20世紀(jì)40年代，馮諾曼等人由從對(duì)策論的角度提出在彼此有矛盾的多個(gè)決策人之間如何進(jìn)行多目標(biāo)決策問題。1950年代初，考普曼（T.C.koopmans）從生產(chǎn)和分配的活動(dòng)分析中提出多目標(biāo)最優(yōu)化問題，并引入了帕累托最優(yōu)的概念。1960年代初，菜恩思（F.Charnes）和考柏（J.Cooper）提出了目標(biāo)規(guī)劃方法來解決多目標(biāo)決策問題。目標(biāo)規(guī)劃是線性規(guī)劃的修正和發(fā)展，這一方法不只是對(duì)一些目標(biāo)求得最優(yōu)，而是盡量使求得的最優(yōu)解與原定的目標(biāo)值之間的偏差為最

9、小。1970年代中期，甘尼（R.L.Keeney）和拉發(fā)用比較完整的描述多屬性效用理論來求解多目標(biāo)決策問題。1970年代末，薩蒂（A.L.Saaty）提出了影響廣泛的AHP(theanalyticalhierarchyprocess)法，并在1980年代初纂寫了有關(guān)AHP法的專著。自1970年代以來，有關(guān)研究和討論多目標(biāo)決策的方法也隨之出現(xiàn)?？傊?，多目標(biāo)決策問題正愈來愈多的受到人們的重視，尤其是在經(jīng)濟(jì)、管理、系統(tǒng)工程、控制論和運(yùn)籌學(xué)等領(lǐng)域中得到了更多的研究和關(guān)注。多目標(biāo)決策法的基本原理從人們?cè)诙嗄繕?biāo)條件下合理進(jìn)行決策的過程和機(jī)制從上分析，多目標(biāo)決策的理論主要有：多目標(biāo)決策過程的分析和描述；沖突

10、性的分解和理想點(diǎn)轉(zhuǎn)移的理論；多屬性效用理論；需求的多重性和層次性理論等。它們是構(gòu)成多目標(biāo)決策分析方法的理論基礎(chǔ)。在多目標(biāo)決策中，有一部分方案經(jīng)比較后可以淘汰，稱為劣解；但還有一批方案既不能淘汰，又不能互相比較，從多目標(biāo)上考慮又都不是最優(yōu)解，稱為“非劣解”(或“有效解”、“帕累托解)。多目標(biāo)決策的方法多目標(biāo)決策的方法很多，有的要用線性規(guī)劃、非線性規(guī)劃、目標(biāo)規(guī)劃等方法。對(duì)于多目標(biāo)的方案有限的決策問題一般先采用列表的方式。舉例：城市新區(qū)人口容量測(cè)算中多目標(biāo)決策法的運(yùn)用多目標(biāo)決策問題除了目標(biāo)不至一個(gè)這一明顯的特點(diǎn)外，最顯著的有以下兩點(diǎn)：目標(biāo)間的不可公度性和目標(biāo)間的矛盾性。目標(biāo)間的不可公度性是指各個(gè)目標(biāo)

11、沒有統(tǒng)一的度量標(biāo)準(zhǔn)，因而難以直接進(jìn)行比較。例如房屋設(shè)計(jì)問題中，造價(jià)的單位是元/平方米，建造時(shí)間的單位是年，而結(jié)構(gòu)、造型等則為定性指標(biāo)。目標(biāo)間的矛盾性是指如果選擇一種方案以改進(jìn)某一目標(biāo)的值，可能會(huì)使另一目標(biāo)的值變壞。如房屋設(shè)計(jì)中造型、抗震性能的提高可能會(huì)使房屋建造成本提高。一個(gè)多目標(biāo)決策問題一般包括目標(biāo)體系、備選方案和決策準(zhǔn)則三個(gè)基本因素。目標(biāo)體系是指由決策者選擇方案所考慮的目標(biāo)組及其結(jié)構(gòu)；備選方案是指決策者根據(jù)實(shí)際問題設(shè)計(jì)出的解決問題的方案。有的被選方案是明確的、有限的，而有的備選方案不是明確的，還有待于在決策過程中根據(jù)一系列約束條件解出。決策準(zhǔn)則是指用于選擇的方案的標(biāo)準(zhǔn)。通常有兩類，一類是最

12、優(yōu)準(zhǔn)則，可以把所有方案依某個(gè)準(zhǔn)則排序。另一類是滿意準(zhǔn)則，它犧牲了最優(yōu)性使問題簡(jiǎn)化，把所有方案分為幾個(gè)有序的子集。如“可接受”與“不可接受”；“好的”、“可接受的”、“不可接受的”與“壞的”。由于直接求多目標(biāo)決策問題比較困難，而單目標(biāo)決策問題又較易求解，因此就出現(xiàn)了先把多目標(biāo)問題轉(zhuǎn)換成單目標(biāo)問題然后再進(jìn)行求解的許多方法。下面介紹幾種較為常見的方法。1) 主要目標(biāo)優(yōu)化兼顧其它目標(biāo)的方法設(shè)有m個(gè)目標(biāo)f1(x)，f2(x)，.，fm(x)，xR均要求為最優(yōu)，但在這m個(gè)目標(biāo)中有一個(gè)是主要目標(biāo)，例如為f1(x)，并要求其為最大。在這種情況下，只要使其它目標(biāo)值處于一定的數(shù)值范圍內(nèi)，就可把多目標(biāo)決策問題轉(zhuǎn)化為

13、下列單目標(biāo)決策問題。2) 線性加權(quán)和法 設(shè)有一多目標(biāo)決策問題，共有f1(x)，f2(x)，fm(x)等m個(gè)目標(biāo)，則可以對(duì)目標(biāo)fi(x)分別給以權(quán)重系數(shù)il（i=1，2，m），然后構(gòu)成一個(gè)新的目標(biāo)函數(shù)，計(jì)算所有方案的F(x)值，從中找出最大值的方案，即為最優(yōu)方案。 在多目標(biāo)決策問題中，或由于各個(gè)目標(biāo)的量綱不同，或有些目標(biāo)值要求最大而有些要求最小，則可首先將目標(biāo)值變換成效用值或無量綱值，然后再用線性加權(quán)和法計(jì)算新的目標(biāo)函數(shù)值并進(jìn)行比較，以決定方案取舍。3) 平方和加權(quán)法 設(shè)有m個(gè)目標(biāo)的決策問題，現(xiàn)要求各方案的目標(biāo)值f1(x)，f2(x)，fm(x)與規(guī)定的m個(gè)滿意值f1*，f2*，fm*的差距盡可

14、能小，這時(shí)可以重新設(shè)計(jì)一個(gè)總的目標(biāo)函數(shù)：并要求minF(x)，其中il是第i(i=1,2,)個(gè)目標(biāo)的權(quán)重系數(shù)。4) 乘除法當(dāng)有m個(gè)目標(biāo)f1(x)，f2(x)，fm(x)時(shí)，其中目標(biāo)f1(x)，f2(x)，fk(x)的值要求越小越好，目標(biāo)fk(x)，fk+1(x)，fm(x)的值要求越大越好，并假定fk(x)，fk+1(x)，fm(x)都大于0。并要求min F(x)。5) 功效系數(shù)法設(shè)有m個(gè)目標(biāo)f1(x)，f2(x)，fm(x)，其中k1個(gè)目標(biāo)要求最大，k2個(gè)目標(biāo)要求最小。賦予這些目標(biāo)f1(x)，f2(x)，fm(x) 以一定的功效系數(shù)di(i=1,2,m)， 10id。當(dāng)?shù)趇個(gè)目標(biāo)達(dá)到最滿意

15、時(shí)di=1，最不滿意時(shí)di=0，其它情形di則為0， 1之間的某個(gè)值。描述di與fi(x)關(guān)系的函數(shù)叫作功效函數(shù)，用di=F(fi)表示。 不同性質(zhì)或不同要求的目標(biāo)可以選擇不同類型的功效函數(shù)，如線性功效函數(shù)、指數(shù)型功效函數(shù)等。3、 動(dòng)態(tài)規(guī)劃法動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理(principle of optimality)，把

16、多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法動(dòng)態(tài)規(guī)劃。1957年出版了他的名著Dynamic Programming，這是該領(lǐng)域的第一本著作。動(dòng)態(tài)規(guī)劃一般可分為線性動(dòng)規(guī)，區(qū)域動(dòng)規(guī)，樹形動(dòng)規(guī)，背包動(dòng)規(guī)四類。舉例：線性動(dòng)規(guī)：攔截導(dǎo)彈，合唱隊(duì)形，挖地雷，建學(xué)校，劍客決斗等；區(qū)域動(dòng)規(guī)：石子合并， 加分二叉樹，統(tǒng)計(jì)單詞個(gè)數(shù)，炮兵布陣等；樹形動(dòng)規(guī)：貪吃的九頭龍，二分查找樹，聚會(huì)的歡樂，數(shù)字三角形等；背包問題：01背包問題，完全背包問題，分組背包問題，二維背包，裝箱問題，擠牛奶（同濟(jì)ACM第1132題）等；動(dòng)態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技

17、術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫(kù)存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動(dòng)態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過程的優(yōu)化問題，但是一些與時(shí)間無關(guān)的靜態(tài)規(guī)劃(如線性規(guī)劃、非線性規(guī)劃)，只要人為地引進(jìn)時(shí)間因素，把它視為多階段決策過程，也可以用動(dòng)態(tài)規(guī)劃方法方便地求解。動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)是對(duì)解最優(yōu)化問題的一種途徑、一種方法，而不是一種特殊算法。不像搜索或數(shù)值計(jì)算那樣，具有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法。動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)往往是針對(duì)一種最優(yōu)化問題，由于各種問題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動(dòng)態(tài)規(guī)劃的設(shè)計(jì)方法對(duì)不同

18、的問題，有各具特色的解題方法，而不存在一種萬能的動(dòng)態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問題。因此讀者在學(xué)習(xí)時(shí)，除了要對(duì)基本概念和方法正確理解外，必須具體問題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。我們也可以通過對(duì)若干有代表性的問題的動(dòng)態(tài)規(guī)劃算法進(jìn)行分析、討論，逐漸學(xué)會(huì)并掌握這一設(shè)計(jì)方法。多階段決策過程的最優(yōu)化問題：含有遞推的思想以及各種數(shù)學(xué)原理（加法原理，乘法原理等等）。在現(xiàn)實(shí)生活中，有一類活動(dòng)的過程，由于它的特殊性，可將過程分成若干個(gè)互相聯(lián)系的階段，在它的每一階段都需要作出決策，從而使整個(gè)過程達(dá)到最好的活動(dòng)效果。當(dāng)然，各個(gè)階段決策的選取不是任意確定的，它依賴于當(dāng)前面臨的狀態(tài)，

19、又影響以后的發(fā)展，當(dāng)各個(gè)階段決策確定后，就組成一個(gè)決策序列，因而也就確定了整個(gè)過程的一條活動(dòng)路線，如圖所示：（看詞條圖）這種把一個(gè)問題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過程就稱為多階段決策過程，這種問題就稱為多階段決策問題。動(dòng)態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題。在這類問題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的解。動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個(gè)子問題，先求解子問題，然后從這些子問題的解得到原問題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨(dú)立的。若用分治法來解這類問題，則分解得到

20、的子問題數(shù)目太多，有些子問題被重復(fù)計(jì)算了很多次。如果我們能夠保存已解決的子問題的答案，而在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算，節(jié)省時(shí)間。我們可以用一個(gè)表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到，只要它被計(jì)算過，就將其結(jié)果填入表中。這就是動(dòng)態(tài)規(guī)劃法的基本思路。具體的動(dòng)態(tài)規(guī)劃算法多種多樣，但它們具有相同的填表格式。多階段決策問題：如果一類活動(dòng)過程可以分為若干個(gè)互相聯(lián)系的階段，在每一個(gè)階段都需作出決策(采取措施)，一個(gè)階段的決策確定以后，常常影響到下一個(gè)階段的決策，從而就完全確定了一個(gè)過程的活動(dòng)路線，則稱它為多階段決策問題。各個(gè)階段的決策構(gòu)成一個(gè)決策序列，稱為一個(gè)

21、策略。每一個(gè)階段都有若干個(gè)決策可供選擇，因而就有許多策略供我們選取，對(duì)應(yīng)于一個(gè)策略可以確定活動(dòng)的效果，這個(gè)效果可以用數(shù)量來確定。策略不同，效果也不同，多階段決策問題，就是要在可以選擇的那些策略中間，選取一個(gè)最優(yōu)策略，使在預(yù)定的標(biāo)準(zhǔn)下達(dá)到最好的效果.基本模型：根據(jù)上例分析和動(dòng)態(tài)規(guī)劃的基本概念，可以得到動(dòng)態(tài)規(guī)劃的基本模型如下：(1)確定問題的決策對(duì)象。 (2)對(duì)決策過程劃分階段。 (3)對(duì)各階段確定狀態(tài)變量。 (4)根據(jù)狀態(tài)變量確定費(fèi)用函數(shù)和目標(biāo)函數(shù)。 (5)建立各階段狀態(tài)變量的轉(zhuǎn)移過程，確定狀態(tài)轉(zhuǎn)移方程。適用條件任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動(dòng)態(tài)規(guī)劃也并不是

22、萬能的。適用動(dòng)態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。1.最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)） 最優(yōu)化原理可這樣闡述：一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡(jiǎn)而言之，一個(gè)最優(yōu)化策略的子策略總是最優(yōu)的。一個(gè)問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2.無后效性將各階段按照一定的次序排列好之后，對(duì)于某個(gè)給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當(dāng)前的這個(gè)狀態(tài)。換句話說，每個(gè)狀態(tài)都是過去歷史的一個(gè)完整總結(jié)。這就是無后向性，又稱為無后效性。3.子問題的重疊性 動(dòng)態(tài)規(guī)劃將原來具有指數(shù)級(jí)時(shí)間復(fù)雜度的搜索算法

23、改進(jìn)成了具有多項(xiàng)式時(shí)間復(fù)雜度的算法。其中的關(guān)鍵在于解決冗余，這是動(dòng)態(tài)規(guī)劃算法的根本目的。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是一種以空間換時(shí)間的技術(shù)，它在實(shí)現(xiàn)的過程中，不得不存儲(chǔ)產(chǎn)生過程中的各種狀態(tài)，所以它的空間復(fù)雜度要大于其它的算法。動(dòng)態(tài)規(guī)劃分類1、 背包模型包括0-1背包、無限背包、有限背包、有價(jià)值背包、小數(shù)背包（貪心即可)等，是極為經(jīng)典的模型，其轉(zhuǎn)化與優(yōu)化也是很重要的。2、 最長(zhǎng)非降子序列模型改版：渡河問題、合唱隊(duì)型等3、最大子段和模型改版：K大子段和、最佳游覽，最大子矩陣和等。4、 LCS模型改版：回文字串、多串的LCS等5、 括號(hào)序列模型改版：關(guān)燈問題（TSOJ）、charexp（TSOJ）、最大算式等，

24、核心思想在于以串的長(zhǎng)度為階段。6、 遞推模型這類題是屬于徘徊在DP與遞歸之間得一類題，本質(zhì)是類似于記憶化搜索的一種填表，有很強(qiáng)的數(shù)學(xué)味。7、線段覆蓋問題改版：Tom的煩惱（TOJ）等。經(jīng)常利用到離散化等技巧輔助。8、 單詞劃分模型和LCS基本上構(gòu)成了字符串DP的主要類型。改版：奇怪的門（TOJ）等。9、 股票模型這是DP優(yōu)化的經(jīng)典模型。改版有換外匯等。10、 連續(xù)段劃分模型即要求把數(shù)列劃分成k個(gè)連續(xù)段，使每段和的最大值最小。改版有任務(wù)調(diào)度等。11、游戲模型這類題的階段（一般是時(shí)間）和決策（一般就是游戲目標(biāo)）很清楚，因此比較容易想到。改版：免費(fèi)餡餅（NOI98）、HelpJimmy（CEOI20

25、00）、瑰麗華爾茲（NOI2005，優(yōu)化需要多費(fèi)功夫）。4、 系統(tǒng)工程法系統(tǒng)工程方法是一種現(xiàn)代的科學(xué)決策方法，也是一門基本的決策技術(shù)。系統(tǒng)工程方法把要處理的問題及其有關(guān)情況加以分門別類、確定邊界，又強(qiáng)調(diào)把握各門類之間和各門類內(nèi)部諸因素之間的內(nèi)在聯(lián)系和完整性、整體性，否定片面和靜止的觀點(diǎn)和方法。在此基礎(chǔ)上，它沒有遺漏地有區(qū)別地針對(duì)主要問題、主要情況和全過程，運(yùn)用有效工具進(jìn)行全面的分析和處理。系統(tǒng)工程方法的特點(diǎn)是整體性、綜合性、協(xié)調(diào)性、科學(xué)性、實(shí)踐性。系統(tǒng)工程方法是人類在自然科學(xué)和社會(huì)科學(xué)領(lǐng)域的不斷實(shí)踐中而產(chǎn)生的一系列科學(xué)處理問題的方法，它包括整體觀念、綜合觀念、科學(xué)觀念、創(chuàng)新觀念等。1)整體觀念

26、，就是要用系統(tǒng)的方法研究系統(tǒng)的對(duì)象，立足整體，統(tǒng)籌全局，全面規(guī)劃，協(xié)調(diào)處理，使系統(tǒng)的總體與部分之間、部分之間、系統(tǒng)與環(huán)境之間達(dá)到辯證統(tǒng)一。我們說系統(tǒng)是由各部分組成的，系統(tǒng)的功能要大于各部分的功能。古代哲學(xué)中就有總體大于各部分總和的論點(diǎn)，這里的大于，指的是各部分組成一個(gè)整體后，產(chǎn)生了總體的功能，即系統(tǒng)的功能，這種功能的產(chǎn)生是一種質(zhì)變，因?yàn)檫@種功能是各部分所不具備的，系統(tǒng)之所以為系統(tǒng)，不僅是各個(gè)組成部分的簡(jiǎn)單的總和，而在于它具備總體的系統(tǒng)的功能。如三個(gè)臭皮匠，頂過諸葛亮，又比如說一個(gè)球隊(duì)，個(gè)人技術(shù)再好，如果沒有正確的戰(zhàn)略戰(zhàn)術(shù)以及相互的默契配合，也難以取勝。因此我們強(qiáng)調(diào)在處理問題時(shí)，要有全局觀念，整

27、體觀念。2)綜合觀念，即要求從系統(tǒng)的總目標(biāo)出發(fā)，將各種有關(guān)的經(jīng)驗(yàn)和知識(shí)予以有機(jī)結(jié)合，協(xié)調(diào)運(yùn)用，從而開發(fā)出全新的系統(tǒng)概念，創(chuàng)造出全新的系統(tǒng)結(jié)合和功能，這就是1+12的系統(tǒng)綜合效果，即綜合出創(chuàng)造，綜合出效益?，F(xiàn)在我們經(jīng)常講的整合資源也是講的綜合觀念。如世界著名的阿波羅登月計(jì)劃中，登月艙是其中關(guān)鍵的一項(xiàng)工程，但其中所采取的單項(xiàng)技術(shù)都是已有的成就技術(shù)，只是很巧妙地把它們綜合起來，起了卓越的作用。3)科學(xué)觀念，即要求分析問題時(shí)樹立科學(xué)的觀念，按照科學(xué)規(guī)律辦事，努力開發(fā)系統(tǒng)的潛在價(jià)值。也就是說，我們?cè)谔幚韱栴}時(shí)，一方面要有嚴(yán)格的工作步驟和工作順序，做到定性與定量相結(jié)合，另一方面要遵照科學(xué)規(guī)律辦事，充分認(rèn)識(shí)

28、到整體與部分的統(tǒng)一、協(xié)同與矛盾的統(tǒng)一。即整體是相對(duì)的，它既是更大系統(tǒng)的部分，又是本系統(tǒng)的整體，整體是具有一定結(jié)構(gòu)、層次和特定功能的有機(jī)整體，整體的各組成部分相互聯(lián)系又相互作用。4)創(chuàng)新觀念，系統(tǒng)工程方法是現(xiàn)代科學(xué)技術(shù)與社會(huì)實(shí)踐相結(jié)合的產(chǎn)物，它要求人們?cè)谶\(yùn)用現(xiàn)代科學(xué)技術(shù)的同時(shí)，充分發(fā)揮人的創(chuàng)新能力，大膽地進(jìn)行系統(tǒng)的概念開發(fā)和結(jié)構(gòu)開發(fā)，以實(shí)現(xiàn)系統(tǒng)的最優(yōu)效果。由于現(xiàn)代社會(huì)實(shí)踐發(fā)展的節(jié)奏加快，社會(huì)運(yùn)動(dòng)加速，未來的因素成為現(xiàn)實(shí)的過程，要求我們加強(qiáng)超前性預(yù)測(cè)，不斷創(chuàng)新，以便為進(jìn)行目的性的活動(dòng)提供保證。1.系統(tǒng)工程的方法體系工具：計(jì)算機(jī)、算法技術(shù)：使用工具的方法。方法：選擇什么技術(shù)來達(dá)到目的的辦法。方法論：

29、處理系統(tǒng)工程問題的一整套思想、原則，是運(yùn)用方法的方法。方法論研究：從哪里開始著手解決問題？如何設(shè)計(jì)解決問題的過程？如何最終實(shí)現(xiàn)問題的解決？2. 系統(tǒng)工程方法論的特點(diǎn).研究方法強(qiáng)調(diào)整體.技術(shù)應(yīng)用強(qiáng)調(diào)綜合.管理決策強(qiáng)調(diào)科學(xué)性3.具有代表性的系統(tǒng)工程方法霍爾(Hall)“三維結(jié)構(gòu)”切克蘭德的“學(xué)習(xí)調(diào)查”法并行工程綜合集成方法霍爾“三維結(jié)構(gòu)1969年美國(guó)貝爾電話公司工程師霍爾（ADHall）提出了系統(tǒng)工程三維結(jié)構(gòu)，簡(jiǎn)稱為霍爾模型?；舅枷耄喝魏螐?fù)雜問題都可以歸結(jié)為工程問題來研究，它強(qiáng)調(diào)明確目標(biāo)，其核心思想是優(yōu)化，應(yīng)用定量的手段求得最優(yōu)解。 二、霍爾模型 模型將系統(tǒng)的整個(gè)管理過程分為六個(gè)階段（時(shí)間維）和

30、七個(gè)步驟（邏輯維），并同時(shí)考慮到為完成這些階段和步驟的工作所需的各種專業(yè)管理知識(shí)（知識(shí)維）。 1. 時(shí)間維（時(shí)間進(jìn)程） 表示系統(tǒng)工程的工作階段或進(jìn)程。即：從規(guī)劃到更新，按時(shí)間順序排列的系統(tǒng)工程全過程。 2. 邏輯維（方法步驟） 每個(gè)階段需進(jìn)行的工作步驟，是運(yùn)用系統(tǒng)工程方法進(jìn)行思考、分析和解決問題應(yīng)遵循的一般程序。 3. 知識(shí)維（科學(xué)技術(shù)） 表示從事系統(tǒng)工程工作所需要的知識(shí)。即：完成上述各階段和各步驟所需要的各種專業(yè)知識(shí)和管理知識(shí)。 4. 霍爾管理矩陣 把三維結(jié)構(gòu)中的六個(gè)時(shí)間階段（時(shí)間維）和七個(gè)邏輯步驟（邏輯維）結(jié)合起來，形成一個(gè)二維結(jié)構(gòu)，稱為系統(tǒng)工程的活動(dòng)矩陣，也稱霍爾管理矩陣。 5. 霍爾模

31、型的特點(diǎn) 研究方法上的整體性（三維） 技術(shù)應(yīng)用上的綜合性（知識(shí)維） 組織管理上的科學(xué)性（時(shí)間維與邏輯維） 系統(tǒng)工程工作的問題導(dǎo)向性（邏輯維）6. 霍爾模型的優(yōu)勢(shì)運(yùn)用系統(tǒng)工程過程管理方法，決策的可靠性可提高一倍以上，節(jié)約時(shí)間和總投資平均15%以上，而用于管理的費(fèi)用一般只占總投資的3%6%。切克蘭德的“調(diào)查學(xué)習(xí)”模式切克蘭德1981年提出“調(diào)查學(xué)習(xí)”模式?；舅枷耄悍椒ǖ暮诵牟皇菍ぁ白顑?yōu)化”，而是“調(diào)查、比較”或者說是“學(xué)習(xí)”，從模型和現(xiàn)狀比較中，研究改善現(xiàn)存系統(tǒng)的途徑。方法步驟：1. 不良結(jié)構(gòu)系統(tǒng)現(xiàn)狀說明通過調(diào)查分析，對(duì)現(xiàn)存的不良結(jié)構(gòu)系統(tǒng)的現(xiàn)狀進(jìn)行說明。2.弄清關(guān)聯(lián)因素初步弄清、改善與現(xiàn)狀有關(guān)的

32、各種因素及其相互關(guān)系。3.建立概念模型用結(jié)構(gòu)模型或語言模型來描述系統(tǒng)的現(xiàn)狀。4.改善概念模型進(jìn)一步用更合適的模型或方法改進(jìn)上述概念模型。5.比較將概念模型與現(xiàn)狀進(jìn)行比較，找出符合決策者意圖，而且可行的改革途徑或方案。6.實(shí)施實(shí)施提出的改革方案。概念模型代替數(shù)學(xué)模型，思路更加開闊。滿意解代替最優(yōu)解，價(jià)值觀方面的重要變化。兩種方法論的比較可用數(shù)學(xué)模型描述，有定量方法可以計(jì)算出系統(tǒng)的行為和最佳結(jié)果。特點(diǎn)：用霍爾模型等“硬方法”求出最佳的定量結(jié)果。工程、機(jī)理明顯的物理型的硬系統(tǒng)結(jié)構(gòu)系統(tǒng)方法定義難用數(shù)學(xué)模型描述，只能用半定量、半定性或者只能用定性的方法來處理問題。特點(diǎn)用調(diào)查學(xué)習(xí)法等“軟方法”求出可行的滿

33、意解。社會(huì)、機(jī)理不清的生物型的軟系統(tǒng)不良結(jié)構(gòu)系統(tǒng)方法定義調(diào)查學(xué)習(xí)法建立概念模型系統(tǒng)現(xiàn)狀說明弄清關(guān)聯(lián)因素改善概念模型比較實(shí)施系統(tǒng)綜合方案優(yōu)化系統(tǒng)分析霍爾模型明確問題選擇目標(biāo)決策實(shí)施并行工程一、概述并行工程(ConcurrentEngineering，簡(jiǎn)稱CE)是美國(guó)在80年代末提出的，在CIMS和系統(tǒng)工程中發(fā)展起來的工程技術(shù)；也是美國(guó)國(guó)防部在90年代乃至21世紀(jì)發(fā)展武器裝備系統(tǒng)的基本管理模式。二、方法描述把序列化的研制過程：設(shè)計(jì)生產(chǎn)保障變?yōu)椴⑿械?、交互作用的綜合研制過程，達(dá)到縮短研制周期de目的。傳統(tǒng)專業(yè)綜合工程專業(yè)綜合綜合系統(tǒng)傳統(tǒng)專業(yè)綜合工程專業(yè)綜合綜合系統(tǒng)硬件軟件人員設(shè)施數(shù)據(jù)建立交互作用、互

34、相協(xié)調(diào)的并行研制過程，將產(chǎn)品的設(shè)計(jì)、制造、保障過程用系統(tǒng)工程方法綜合在一起。三、方法的主要思想1.約束信息的并行性；2.功能的并行性；3.集成性；4.協(xié)同性；5.科學(xué)性。綜合集成法一、概述二十世紀(jì)80年代錢學(xué)森提出的綜合集成（Meta-Synthesis）方法是從整體上考慮并解決復(fù)雜問題的方法論。即“從定性到定量綜合集成方法”。其實(shí)質(zhì)是將專家群體、數(shù)據(jù)和各種信息與計(jì)算機(jī)仿真有機(jī)地結(jié)合，把各種學(xué)科的理論和人的經(jīng)驗(yàn)與知識(shí)結(jié)合起來，發(fā)揮整體優(yōu)勢(shì)?！熬C合即創(chuàng)造”綜合集成：重點(diǎn)在綜合，目的是創(chuàng)造、創(chuàng)新“集大成，出智慧”綜合集成：“大成智慧工程”的方法論綜合集成綜合集成組合綜合的集成從定性到定量集成聯(lián)合集

35、融合集科學(xué)與人文相結(jié)合確定與不確定相結(jié)合宏觀與微觀相結(jié)合定性與定量相結(jié)合多學(xué)科交叉人機(jī)結(jié)合管理方法的集成數(shù)學(xué)模型的集成技術(shù)的集成概念的集成5、 過程決策圖法過程決策程序圖法（PDPC）是在制定計(jì)劃階段或進(jìn)行系統(tǒng)設(shè)計(jì)時(shí)，事先預(yù)測(cè)可能發(fā)生的障礙（不理想事態(tài)或結(jié)果），從而設(shè)計(jì)出一系列對(duì)策措施以最大的可能引向最終目標(biāo)（達(dá)到理想結(jié)果）。該法可用于防止重大事故的發(fā)生，因此也稱之為重大事故預(yù)測(cè)圖法。由于一些突發(fā)性的原因，可能會(huì)導(dǎo)致工作出現(xiàn)障礙和停頓，對(duì)此需要用過程決策程序圖法進(jìn)行解決。過程決策圖法的優(yōu)點(diǎn) 過程決策圖法具有很多優(yōu)點(diǎn)，具體來說主要有以下四點(diǎn)： 1、 能從整體上掌握系統(tǒng)的動(dòng)態(tài)并依此判斷全局 據(jù)說象

36、棋大師可以一個(gè)人同時(shí)和20個(gè)人下象棋，20個(gè)人可能還下不過他一個(gè)人。這就在于象棋大師胸有全局，因此能夠有條不紊，即使面對(duì)20個(gè)對(duì)手，也能有把握戰(zhàn)而勝之。2、具有動(dòng)態(tài)管理的特點(diǎn)PDPC法具有動(dòng)態(tài)管理的特征，它是在運(yùn)動(dòng)的，而不像系統(tǒng)圖是靜止的。3、具有可追蹤性PDPC法很靈活，它既可以從出發(fā)點(diǎn)追蹤到最后的結(jié)果，也可以從最后的結(jié)果追蹤中間發(fā)生的原因。4、能預(yù)測(cè)那些通常很少發(fā)生的重大事故，并在設(shè)計(jì)階段預(yù)先考慮應(yīng)付事故的措施PDPC法可以預(yù)測(cè)那些通常很少發(fā)生的重大事故，并且在設(shè)計(jì)階段，預(yù)先就制定出應(yīng)付事故的一系列措施和辦法。換句話說，掌握了這些思考方法以后，所有的人都可以成為一個(gè)諸葛亮，做到運(yùn)籌帷幄，料

37、事于先。PDPC法的分類PDPC法可分為兩種，一種是順向思維法；一種是逆向思維法。順向思維法順向思維法是定好一個(gè)理想的目標(biāo)，然后按順序考慮實(shí)現(xiàn)目標(biāo)的手段和方法。這個(gè)目標(biāo)可以是任何的東西，比如大的工程、一項(xiàng)具體的革新、一個(gè)技術(shù)改造方案等。為了能夠穩(wěn)步達(dá)到目標(biāo)，需要設(shè)想很多條路線。總而言之，無論怎樣走，一定要走到目的地。但行走的方案，并不需要真正等到碰得頭破血流以后才去解決，而應(yīng)該事先就已經(jīng)討論過了，所有的問題應(yīng)該預(yù)先都預(yù)測(cè)到了。這樣的話，在計(jì)劃的實(shí)施過程中，就不會(huì)害怕突發(fā)性的事故了。逆向思維法 當(dāng)為理想狀態(tài)（或非理想狀態(tài)）時(shí)，從出發(fā)，逆向而上，從大量的觀點(diǎn)中展開構(gòu)思，使其和初始狀態(tài)0連接起來，詳

38、細(xì)研究其過程做出決策，這就是逆向思維法。逆向思維應(yīng)該考慮從理想狀態(tài)開始，考慮實(shí)現(xiàn)這個(gè)目標(biāo)的前提是什么，為了滿足這個(gè)前提又應(yīng)該具備什么條件。一步一步退回來，一直退到出發(fā)點(diǎn)。通過正反兩個(gè)方面的連接，倒著走得通，順著也可以走得通，這就是PDPC法一個(gè)正確的思考辦法。逆向思維應(yīng)該考慮從理想狀態(tài)開始，考慮實(shí)現(xiàn)這個(gè)目標(biāo)的前提是什么，為了滿足這個(gè)前提又應(yīng)該具備什么條件。一步一步退回來，一直退到出發(fā)點(diǎn)。通過正反兩個(gè)方面的連接，倒著走得通，順著也可以走得通，這就是PDPC法一個(gè)正確的思考辦法。編輯PDPC法的運(yùn)用及實(shí)例PDPC法有五大方面的用處，它們分別是：1、制定目標(biāo)管理中間的實(shí)施計(jì)劃，怎樣在實(shí)施過程中解決各

39、種困難和問題；2、制定科研項(xiàng)目的實(shí)施計(jì)劃；3、對(duì)整個(gè)系統(tǒng)的重大事故進(jìn)行預(yù)測(cè)；4、制定工序控制的一些措施；5、義務(wù)選擇處理糾紛的各種方案。實(shí)際上PDPC法在哪里都可以應(yīng)用，遠(yuǎn)遠(yuǎn)不止這五個(gè)。只要做事情，就可能有失敗，如果能把可能失敗的因素提前都找出來，制定出一系列的對(duì)策措施，就能夠穩(wěn)步地、輕松地到達(dá)目的地。任何一件事情的調(diào)整都是很不容易的，整個(gè)生產(chǎn)系統(tǒng)就像一張巨大的網(wǎng)，要?jiǎng)右粋€(gè)地方跟著就要?jiǎng)右黄?。所以說，PDPC法是一個(gè)系統(tǒng)思考問題的方法，而生產(chǎn)、生活的復(fù)雜性，也要求人們?cè)谵k事情、做計(jì)劃、干事業(yè)的時(shí)候要深思熟慮，不能馬虎大意、隨隨便便，否則的話就會(huì)一招不慎，滿盤皆輸。這也是“成于思，毀于隨”的真正

40、意義所在。如果決策問題只要求做一次決策，就是單級(jí)決策問題，圖中只有一個(gè)決策結(jié)點(diǎn)。如果要求分幾次做出決策，即為多級(jí)決策問題，在決策樹中就會(huì)有多個(gè)決策結(jié)點(diǎn)。對(duì)于多級(jí)決策問題，處理問題的思路與單級(jí)決策問題基本上是相似的。因?yàn)橄乱患?jí)的決策問題一旦解決以后，這個(gè)決策結(jié)點(diǎn)的作用就同狀態(tài)結(jié)點(diǎn)一樣了。所以，處理多級(jí)決策問題時(shí)只要從最末一級(jí)的決策開始往上進(jìn)行，逐級(jí)遞推就可以了。單級(jí)決策問題的解決思路與表式?jīng)Q策法的基本思路是一致的。只要求出各方案分枝的損益期望值就可以了。根據(jù)各方案分枝的損益期望值和各方案的初始投資情況，就可以對(duì)各方案分枝決定取舍，稱之為剪枝。1、明確所要處理的決策問題是幾級(jí)決策問題，明確各級(jí)決策

41、之間的邏輯關(guān)系以及各級(jí)決策各有幾種方案，明確各級(jí)決策所面臨的有幾種自然狀態(tài)及各種自然狀態(tài)發(fā)生的概率。2、畫出決策樹圖，畫圖時(shí)應(yīng)注意各類結(jié)點(diǎn)的層次關(guān)系，并將某決策方案在某種自然狀態(tài)下的損益值標(biāo)于樹圖的相應(yīng)的末端位置。3、從右向左計(jì)算各結(jié)點(diǎn)的期望值，術(shù)語稱為滾回或折回。遇到?jīng)Q策結(jié)點(diǎn)時(shí)則應(yīng)先視為單級(jí)決策問題進(jìn)行決策。經(jīng)過取舍，剪枝后再參加下一級(jí)的決策。4、逐級(jí)剪枝，滾回上行，完成所有決策結(jié)點(diǎn)的剪枝工作，則整個(gè)決策問題就決定了。對(duì)于單級(jí)決策問題。最后得到一個(gè)決策方案；對(duì)于多級(jí)決策問題，最后得到的是一個(gè)若干個(gè)相關(guān)決策組成的決策組合。覆蓋的分布式計(jì)算機(jī)系統(tǒng)（Distributed computer sys

42、tems，DCS）的可靠性分析。在這種基于多態(tài)二元決策圖（Multi-state BDD，MBDD）方法中，用一個(gè)布爾變量表達(dá)部件的每個(gè)狀態(tài)，變量等于 0 或 1 代表該部件不處于或處于這個(gè)特定狀態(tài)，根據(jù)所有的布爾變量即可生成系統(tǒng)的二元決策圖。Miller提出了多值決策（Multiple-valued decision diagram，MDD）的概念，多值決策圖是將二元決策圖的二元邏輯擴(kuò)展為多值邏輯，也就是將布爾變量擴(kuò)展為多態(tài)變量。Miller 等描述了在多值決策圖中排序交換的矩陣方法。多值決策圖在多個(gè)領(lǐng)域得到廣泛應(yīng)用。在馬爾可夫鏈中，為了盡量減少迭代次數(shù)，Ciardo 等將系統(tǒng)下一個(gè)狀態(tài)的函

43、數(shù)編碼為一個(gè)交叉乘積的整數(shù)函數(shù)；Miner 和 Cheng分別用多路決策圖（Multiway decision diagram）和邊賦值決策圖（Edge-valued decision diagram）表示狀態(tài)集合和距離信息。在 Petri 網(wǎng)領(lǐng)域，Ciardo介紹了針對(duì) Petri 網(wǎng)及類似的異步模型的數(shù)據(jù)結(jié)構(gòu)和算法；受二元決策圖和多值決策圖的啟發(fā)，轉(zhuǎn)移運(yùn)輸效果的概念被用于生成和存儲(chǔ) Petri 網(wǎng)的可達(dá)集。在符號(hào)模型檢驗(yàn)領(lǐng)域，Chechik 等人提出了幾種用決策圖實(shí)現(xiàn)多值集的選擇。在容錯(cuò)系統(tǒng)的領(lǐng)域，Xing 和 Dugan將多值決策圖應(yīng)用于容錯(cuò)系統(tǒng)的可靠性分析；Xing提出了三元決策圖（Ternary decision diagrams，TDD）的概念，在三元決策圖中，每個(gè)變量具有三種狀態(tài)，被用于計(jì)算帶有雙級(jí)模塊不完全覆蓋廣義任務(wù)階段系（Generalizedphased-mission system，GPMS）的可靠性。近年來，Xing 等針對(duì)狀態(tài)依賴問題提出了多態(tài)多值決策圖（Multi-statemulti-valued decision diagram，MM