規(guī)劃的綜合方法

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

2、主要用于研究有限資源的最佳分配問題，即如何對有限的資源作出最佳方式地調(diào)配和最有利地使用，以便最充分地發(fā)揮資源的效能去獲取最佳的經(jīng)濟效益。由于有成熟的計算機應(yīng)用軟件的支持，采用線性規(guī)劃模型安排生產(chǎn)計劃，并不是一件困難的事情。在總體計劃中，用線性規(guī)劃模型解決問題的思路是，在有限的生產(chǎn)資源和市場需求條件約束下，求利潤最大的總產(chǎn)量計劃。該方法的最大優(yōu)點是可以處理多品種問題。數(shù)學(xué)模型:線性規(guī)劃法的數(shù)學(xué)模生如下：設(shè)X2JXuxn為各變量.D為變量個數(shù)，m為約束條件數(shù)，駒(i=l.2.m；j=l.2”，b)為各種系數(shù)，bibhs%為常數(shù),CpQtd，C九為目標(biāo)函數(shù)系數(shù).Z為弓標(biāo)值，則線性規(guī)劃?？缦拢篴nX

3、i+ai2?<2+=，+ainXn/-(=)bt也1X1+出2天2+”+anXnMW)6缶1天1+缶送2+"+3mnXnS-(=)bmXi'天2；0討標(biāo)函數(shù)Zmin(max)=ClXl+C2X2+1) 列出約束條件及目標(biāo)函數(shù)2) 畫出約束條件所表示的可行域3) 在可行域內(nèi)求目標(biāo)函數(shù)的最優(yōu)解及最優(yōu)值從實際問題中建立數(shù)學(xué)模型一般有以下三個步驟；1. 根據(jù)影響所要達(dá)到目的的因素找到?jīng)Q策變量；2. 由決策變量和所在達(dá)到目的之間的函數(shù)關(guān)系確定目標(biāo)函數(shù)；3. 由決策變量所受的限制條件確定決策變量所要滿足的約束條件。所建立的數(shù)學(xué)模型具有以下特點：1、每個模型都有若干個決策變量(xl,

4、x2,x3，xn)，其中n為決策變量個數(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ù)學(xué)模型為線性規(guī)劃模型。發(fā)展：法國數(shù)學(xué)家J.-B.-J.傅里葉和C.瓦萊一普森分別于1832和1911年獨立地提出線性規(guī)劃的想法，但未引起注意。1939年蘇聯(lián)數(shù)學(xué)家JI.康.托羅維奇在生產(chǎn)組織與計劃中的數(shù)學(xué)方法一書中提出線性規(guī)劃問題，也未引起重視。1947年美國數(shù)學(xué)家G.B.

5、Dantzing提出求解線性規(guī)劃的單純形法，為這門學(xué)科奠定了基礎(chǔ)。1947年美國數(shù)學(xué)家J.von諾伊曼提出對偶理論，開創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴大了它的應(yīng)用范圍和解題能力。1951年美國經(jīng)濟學(xué)家T.C.庫普曼斯把線性規(guī)劃應(yīng)用到經(jīng)濟領(lǐng)域，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟學(xué)獎。50年代后對線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如，1954年C.萊姆基提出對偶單純形法，1954年S.加斯和T.薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問題，1956年A.塔克提出互補松弛定理，1960年G.B.丹齊克和P.沃爾夫提出分解算線性規(guī)劃的研究成果還直接推動了其他數(shù)學(xué)規(guī)劃問

6、題包括整數(shù)規(guī)劃、隨機規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計算機的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個變量的線性規(guī)劃問題。1979年蘇聯(lián)數(shù)學(xué)家L.G.Khachian提出解線性規(guī)劃問題的橢球算法，并證明它是多項式時間算法。1984年美國貝爾電話實驗室的印度數(shù)學(xué)家N.卡馬卡提出解線性規(guī)劃問題的新的多項式時間算法。用這種方法求解線性規(guī)劃問題在變量個數(shù)為5000時只要單純形法所用時間的1/50?，F(xiàn)已形成線性規(guī)劃多項式算法理論。50年代后線性規(guī)劃的應(yīng)用范圍不斷擴大。實際運用線性規(guī)劃模型進(jìn)行總生產(chǎn)計劃時需要注意的一些問題1、線性規(guī)劃模型考慮的因

7、素可能不全面，實際中有些情況沒有被考慮到，這就使得線性規(guī)劃模型過于理想化；2、實際運用線性規(guī)劃模型時，雖然一些因素或約束條件被考慮到了,但是由于這些因素或約束條件不易量化或求得（如進(jìn)行總生產(chǎn)計劃常需考慮到的能源單耗就不易求得）時，線性規(guī)劃模型的運用和有效性因而受到了一定的限制；3、對一些基礎(chǔ)管理不善的企業(yè)而言，模型中的單位產(chǎn)品資源消耗系數(shù)a很難得到；4、目標(biāo)函數(shù)中的產(chǎn)為成本系數(shù)c實際上是個變量，他隨計劃的數(shù)量結(jié)構(gòu)和品種結(jié)構(gòu)而變。這些問題給機械行業(yè)應(yīng)用線性規(guī)劃模型帶來許多困難，如處理不好，求得的結(jié)果的可靠性會很低的。二、多目標(biāo)決策法多目標(biāo)決策是對多個相互矛盾的目標(biāo)進(jìn)行科學(xué)、合理的選優(yōu)，然后作出決

8、策的理論和方法。它是20世紀(jì)70年代后迅速發(fā)展起來的管理科學(xué)的一個新的分支。多目標(biāo)決策與只為了達(dá)到一個目標(biāo)而從許多可行方案中選出最佳方案的一般決策有所不同。在多目標(biāo)決策中，要同時考慮多種目標(biāo)，而這些目標(biāo)往往是難以比較的，甚至是彼此矛盾的；一般很難使每個目標(biāo)都達(dá)到最優(yōu)，作出各方面都很滿意的決策。因此多目標(biāo)決策實質(zhì)上是在各種目標(biāo)之間和各種限制之間求得一種合理的妥協(xié)，這就是多目標(biāo)最優(yōu)化的過程。國外一般認(rèn)為，多目標(biāo)優(yōu)化問題最早是在19世紀(jì)末由意大利經(jīng)濟學(xué)家帕累托(V.Pareto)從政治經(jīng)濟學(xué)的角度提出來的，他把許多本質(zhì)上不可比較的目標(biāo)，設(shè)法變換成一個單一的最優(yōu)目標(biāo)來進(jìn)行求解。到了20世紀(jì)40年代，馮

9、諾曼等人由從對策論的角度提出在彼此有矛盾的多個決策人之間如何進(jìn)行多目標(biāo)決策問題。1950年代初，考普曼(T.C.koopmans)從生產(chǎn)和分配的活動分析中提出多目標(biāo)最優(yōu)化問題，并引入了帕累托最優(yōu)的概念。I960年代初，菜恩思(F.Charnes)和考柏(J.Cooper)提出了目標(biāo)規(guī)劃方法來解決多目標(biāo)決策問題。目標(biāo)規(guī)劃是線性規(guī)劃的修正和發(fā)展，這一方法不只是對一些目標(biāo)求得最優(yōu)，而是盡量使求得的最優(yōu)解與原定的目標(biāo)值之間的偏差為最小。1970年代中期，甘尼(R.L.Keeney)和拉發(fā)用比較完整的描述多屬性效用理論來求解多目標(biāo)決策問題。1970年代末，薩蒂(A.L.Saaty)提出了影響廣泛的AHP

10、(theanalyticalhierarchyprocess)法，并在1980年代初纂寫了有關(guān)AHP法的專著。自1970年代以來，有關(guān)研究和討論多目標(biāo)決策的方法也隨之出現(xiàn)?？傊?，多目標(biāo)決策問題正愈來愈多的受到人們的重視，尤其是在經(jīng)濟、管理、系統(tǒng)工程、控制論和運籌學(xué)等領(lǐng)域中得到了更多的研究和關(guān)注。多目標(biāo)決策法的基本原理從人們在多目標(biāo)條件下合理進(jìn)行決策的過程和機制從上分析，多目標(biāo)決策的理論主要有：多目標(biāo)決策過程的分析和描述；沖突性的分解和理想點轉(zhuǎn)移的理論；多屬性效用理論；需求的多重性和層次性理論等。它們是構(gòu)成多目標(biāo)決策分析方法的理論基礎(chǔ)。在多目標(biāo)決策中，有一部分方案經(jīng)比較后可以淘汰，稱為劣解；但還

11、有一批方案既不能淘汰，又不能互相比較，從多目標(biāo)上考慮又都不是最優(yōu)解，稱為“非劣解”（或“有效解”、“帕累托解）。多目標(biāo)決策的方法多目標(biāo)決策的方法很多，有的要用線性規(guī)劃、非線性規(guī)劃、目標(biāo)規(guī)劃等方法。對于多目標(biāo)的方案有限的決策問題一般先采用列表的方式。第一層：總目標(biāo)第二層：分目標(biāo)第三層：準(zhǔn)則層可供選擇的方案總體冃標(biāo)廿標(biāo)集構(gòu)成因素人口容景F二f自然資源生態(tài)資源Xu可供淡水13-心可建&用地面積/淼林rin'枳舉例：城市新區(qū)人口容量測算中多目標(biāo)決策法的運用約束條件JuYhit!的MhMoM2|圖2人口容量目標(biāo)的塊嶷模型圖多目標(biāo)決策問題除了目標(biāo)不至一個這一明顯的特點外，最顯著的有以下兩點

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

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

14、種情況下，只要使其它目標(biāo)值處于一定的數(shù)值范圍內(nèi)，就可把多目標(biāo)決策問題轉(zhuǎn)化為下列單目標(biāo)決策問題。2) 線性加權(quán)和法設(shè)有一多目標(biāo)決策問題，共有fl(x),f2(x),，fm(x)等m個目標(biāo)，則可以對目標(biāo)fi(x)分別給以權(quán)重系數(shù)i口(i=l,2,，m),然后構(gòu)成一個新的目標(biāo)函數(shù)，計算所有方案的F(x)值，從中找出最大值的方案，即為最優(yōu)方案。在多目標(biāo)決策問題中，或由于各個目標(biāo)的量綱不同，或有些目標(biāo)值要求最大而有些要求最小，則可首先將目標(biāo)值變換成效用值或無量綱值，然后再用線性加權(quán)和法計算新的目標(biāo)函數(shù)值并進(jìn)行比較，以決定方案取舍。3) 平方和加權(quán)法設(shè)有m個目標(biāo)的決策問題，現(xiàn)要求各方案的目標(biāo)值f1(x)，

15、f2(x)，.，fm(x)與規(guī)定的m個滿意值fl*，f2*，.，fm*的差距盡可能小，這時可以重新設(shè)計一個總的目標(biāo)函數(shù)：并要求minF(x)，其中i口是第i(i=l,2,.)個目標(biāo)的權(quán)重系數(shù)。4) 乘除法當(dāng)有m個目標(biāo)fl(x)，f2(x)，fm(x)時，其中目標(biāo)fl(x)，f2(x)，fk(x)的值要求越小越好，目標(biāo)fk(x)，fk+1(x)，fm(x)的值要求越大越好，并假定fk(x)，fk+1(x)，fm(x)都大于0。并要求minF(x)。5) 功效系數(shù)法設(shè)有m個目標(biāo)fl(x)，f2(x)，fm(x)，其中kl個目標(biāo)要求最大，k2個目標(biāo)要求最小。賦予這些目標(biāo)fl(x)，f2(x)，fm(

16、x)以一定的功效系數(shù)di(i=l,2,.,m),10口口id當(dāng)?shù)趇個目標(biāo)達(dá)到最滿意時di=1，最不滿意時di=0，其它情形di則為0,1之間的某個值。描述di與fi(x)關(guān)系的函數(shù)叫作功效函數(shù)，用di=F(fi)表示。不同性質(zhì)或不同要求的目標(biāo)可以選擇不同類型的功效函數(shù)，如線性功效函數(shù)、指數(shù)型功效函數(shù)等。三、動態(tài)規(guī)劃法動態(tài)規(guī)劃(dynamicprogramming)是運籌學(xué)的一個分支，是求解決策過程(decisionprocess)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優(yōu)化問題時，提出了著

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

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

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

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

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

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

23、，超出了特定條件，它就失去了作用。同樣，動態(tài)規(guī)劃也并不是萬能的。適用動態(tài)規(guī)劃的問題必須滿足最優(yōu)化原理和無后效性。1. 最優(yōu)化原理（最優(yōu)子結(jié)構(gòu)性質(zhì)）最優(yōu)化原理可這樣闡述：一個最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。簡而言之，一個最優(yōu)化策略的子策略總是最優(yōu)的。一個問題滿足最優(yōu)化原理又稱其具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2. 無后效性將各階段按照一定的次序排列好之后，對于某個給定的階段狀態(tài)，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當(dāng)前的這個狀態(tài)。換句話說，每個狀態(tài)都是過去歷史的一個完整總結(jié)。這就是無后向性，又稱為無后效性。3.

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

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

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

27、觀念、科學(xué)觀念、創(chuàng)新觀念等。1）整體觀念，就是要用系統(tǒng)的方法研究系統(tǒng)的對象，立足整體，統(tǒng)籌全局，全面規(guī)劃，協(xié)調(diào)處理，使系統(tǒng)的總體與部分之間、部分之間、系統(tǒng)與環(huán)境之間達(dá)到辯證統(tǒng)一。我們說系統(tǒng)是由各部分組成的，系統(tǒng)的功能要大于各部分的功能。古代哲學(xué)中就有"總體大于各部分總和"的論點，這里的大于，指的是各部分組成一個整體后，產(chǎn)生了總體的功能，即系統(tǒng)的功能，這種功能的產(chǎn)生是一種質(zhì)變，因為這種功能是各部分所不具備的，系統(tǒng)之所以為系統(tǒng)，不僅是各個組成部分的簡單的總和，而在于它具備總體的系統(tǒng)的功能。如"三個臭皮匠，頂過諸葛亮"，又比如說一個球隊，個人技術(shù)再好，如果沒有

28、正確的戰(zhàn)略戰(zhàn)術(shù)以及相互的默契配合，也難以取勝。因此我們強調(diào)在處理問題時，要有全局觀念，整體觀念。2）綜合觀念，即要求從系統(tǒng)的總目標(biāo)出發(fā)，將各種有關(guān)的經(jīng)驗和知識予以有機結(jié)合，協(xié)調(diào)運用，從而開發(fā)出全新的系統(tǒng)概念，創(chuàng)造出全新的系統(tǒng)結(jié)合和功能，這就是1+1>2的系統(tǒng)綜合效果，即綜合出創(chuàng)造，綜合出效益。現(xiàn)在我們經(jīng)常講的"整合資源"也是講的綜合觀念。如世界著名的阿波羅登月計劃中，登月艙是其中關(guān)鍵的一項工程，但其中所采取的單項技術(shù)都是已有的成就技術(shù)，只是很巧妙地把它們綜合起來，起了卓越的作用。3）科學(xué)觀念，即要求分析問題時樹立科學(xué)的觀念，按照科學(xué)規(guī)律辦事，努力開發(fā)系統(tǒng)的潛在價值。也

29、就是說，我們在處理問題時，一方面要有嚴(yán)格的工作步驟和工作順序，做到定性與定量相結(jié)合，另一方面要遵照科學(xué)規(guī)律辦事，充分認(rèn)識到整體與部分的統(tǒng)一、協(xié)同與矛盾的統(tǒng)一。即整體是相對的，它既是更大系統(tǒng)的部分，又是本系統(tǒng)的整體，整體是具有一定結(jié)構(gòu)、層次和特定功能的有機整體，整體的各組成部分相互聯(lián)系又相互作用。4）創(chuàng)新觀念，系統(tǒng)工程方法是現(xiàn)代科學(xué)技術(shù)與社會實踐相結(jié)合的產(chǎn)物，它要求人們在運用現(xiàn)代科學(xué)技術(shù)的同時，充分發(fā)揮人的創(chuàng)新能力，大膽地進(jìn)行系統(tǒng)的概念開發(fā)和結(jié)構(gòu)開發(fā)，以實現(xiàn)系統(tǒng)的最優(yōu)效果。由于現(xiàn)代社會實踐發(fā)展的節(jié)奏加快，社會運動加速，未來的因素成為現(xiàn)實的過程，要求我們加強超前性預(yù)測，不斷創(chuàng)新，以便為進(jìn)行&quo

30、t;目的性"的活動提供保證。1. 系統(tǒng)工程的方法體系工具：計算機、算法技術(shù)：使用工具的方法。方法：選擇什么技術(shù)來達(dá)到目的的辦法。方法論：處理系統(tǒng)工程問題的一整套思想、原則，是運用方法的方法。方法論研究：從哪里開始著手解決問題？如何設(shè)計解決問題的過程？如何最終實現(xiàn)問題的解決？2. 系統(tǒng)工程方法論的特點.研究方法強調(diào)整體.技術(shù)應(yīng)用強調(diào)綜合.管理決策強調(diào)科學(xué)性3. 具有代表性的系統(tǒng)工程方法霍爾（Hall）“三維結(jié)構(gòu)”切克蘭德的“學(xué)習(xí)調(diào)查”法并行工程綜合集成方法霍爾三維結(jié)構(gòu)1969年美國貝爾電話公司工程師霍爾（A-D-Hall）提出了系統(tǒng)工程三維結(jié)構(gòu)，簡稱為霍爾模型。基本思想：任何復(fù)雜問題都

31、可以歸結(jié)為工程問題來研究，它強調(diào)明確目標(biāo)，其核心思想是優(yōu)化，應(yīng)用定量的手段求得最優(yōu)解。二、霍爾模型模型將系統(tǒng)的整個管理過程分為六個階段（時間維）和七個步驟（邏輯維），并同時考慮到為完成這些階段和步驟的工作所需的各種專業(yè)管理知識（知識維）。1. 時間維（時間進(jìn)程）表示系統(tǒng)工程的工作階段或進(jìn)程。即：從規(guī)劃到更新，按時間順序排列的系統(tǒng)工程全過程。2. 邏輯維（方法步驟）每個階段需進(jìn)行的工作步驟，是運用系統(tǒng)工程方法進(jìn)行思考、分析和解決問題應(yīng)遵循的一般程序。3. 知識維（科學(xué)技術(shù)）表示從事系統(tǒng)工程工作所需要的知識。即：完成上述各階段和各步驟所需要的各種專業(yè)知識和管理知識。4. 霍爾管理矩陣把三維結(jié)構(gòu)中的

32、六個時間階段（時間維）和七個邏輯步驟（邏輯維）結(jié)合起來，形成一個二維結(jié)構(gòu)，稱為系統(tǒng)工程的活動矩陣，也稱霍爾管理矩陣。5. 霍爾模型的特點研究方法上的整體性（三維）技術(shù)應(yīng)用上的綜合性（知識維）組織管理上的科學(xué)性（時間維與邏輯維）系統(tǒng)工程工作的問題導(dǎo)向性（邏輯維）6. 霍爾模型的優(yōu)勢運用系統(tǒng)工程過程管理方法，決策的可靠性可提高一倍以上，節(jié)約時間和總投資平均15%以上，而用于管理的費用一般只占總投資的3%6%。切克蘭德的“調(diào)査學(xué)習(xí)”模式切克蘭德1981年提出“調(diào)查學(xué)習(xí)”模式?；舅枷耄悍椒ǖ暮诵牟皇菍ぁ白顑?yōu)化”，而是“調(diào)查、比較”或者說是“學(xué)習(xí)”，從模型和現(xiàn)狀比較中，研究改善現(xiàn)存系統(tǒng)的途徑。方法步驟

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

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

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

36、成：重點在綜合，目的是創(chuàng)造、創(chuàng)新“集大成，出智慧，綜合集成：“大成智慧工程”的方法論綜合集成綜合集成組合綜合的集成從定性到定量集成聯(lián)合集融合集科學(xué)與人文相結(jié)合確定與不確定相結(jié)合宏觀與微觀相結(jié)合定性與定量相結(jié)合多學(xué)科交叉人機結(jié)合.管理方法的集成數(shù)學(xué)模型的集成技術(shù)的集成概念的集成五、過程決策圖法過程決策程序圖法（PDPC）是在制定計劃階段或進(jìn)行系統(tǒng)設(shè)計時，事先預(yù)測可能發(fā)生的障礙（不理想事態(tài)或結(jié)果），從而設(shè)計出一系列對策措施以最大的可能引向最終目標(biāo)（達(dá)到理想結(jié)果）。該法可用于防止重大事故的發(fā)生，因此也稱之為重大事故預(yù)測圖法。由于一些突發(fā)性的原因，可能會導(dǎo)致工作出現(xiàn)障礙和停頓，對此需要用過程決策程序圖

37、法進(jìn)行解決。過程決策圖法的優(yōu)點過程決策圖法具有很多優(yōu)點，具體來說主要有以下四點：1、能從整體上掌握系統(tǒng)的動態(tài)并依此判斷全局據(jù)說象棋大師可以一個人同時和20個人下象棋，20個人可能還下不過他一個人。這就在于象棋大師胸有全局，因此能夠有條不紊，即使面對20個對手，也能有把握戰(zhàn)而勝之。2、具有動態(tài)管理的特點PDPC法具有動態(tài)管理的特征，它是在運動的，而不像系統(tǒng)圖是靜止的。3、具有可追蹤性PDPC法很靈活，它既可以從出發(fā)點追蹤到最后的結(jié)果，也可以從最后的結(jié)果追蹤中間發(fā)生的原因。4、能預(yù)測那些通常很少發(fā)生的重大事故，并在設(shè)計階段預(yù)先考慮應(yīng)付事故的措施PDPC法可以預(yù)測那些通常很少發(fā)生的重大事故，并且在設(shè)

38、計階段，預(yù)先就制定出應(yīng)付事故的一系列措施和辦法。換句話說，掌握了這些思考方法以后，所有的人都可以成為一個諸葛亮，做到運籌帷幄，料事于先。PDPC法的分類PDPC法可分為兩種，一種是順向思維法；一種是逆向思維法。順向思維法順向思維法是定好一個理想的目標(biāo)，然后按順序考慮實現(xiàn)目標(biāo)的手段和方法。這個目標(biāo)可以是任何的東西，比如大的工程、一項具體的革新、一個技術(shù)改造方案等。為了能夠穩(wěn)步達(dá)到目標(biāo)，需要設(shè)想很多條路線?？偠灾瑹o論怎樣走，一定要走到目的地。但行走的方案，并不需要真正等到碰得頭破血流以后才去解決，而應(yīng)該事先就已經(jīng)討論過了，所有的問題應(yīng)該預(yù)先都預(yù)測到了。這樣的話，在計劃的實施過程中，就不會害怕突

39、發(fā)性的事故了。逆向思維法當(dāng)Z為理想狀態(tài)（或非理想狀態(tài)）時，從Z出發(fā)，逆向而上，從大量的觀點中展開構(gòu)思，使其和初始狀態(tài)A0連接起來，詳細(xì)研究其過程做出決策，這就是逆向思維法。逆向思維應(yīng)該考慮從理想狀態(tài)開始，考慮實現(xiàn)這個目標(biāo)的前提是什么，為了滿足這個前提又應(yīng)該具備什么條件。一步一步退回來，一直退到出發(fā)點。通過正反兩個方面的連接，倒著走得通，順著也可以走得通，這就是PDPC法一個正確的思考辦法。逆向思維應(yīng)該考慮從理想狀態(tài)開始，考慮實現(xiàn)這個目標(biāo)的前提是什么，為了滿足這個前提又應(yīng)該具備什么條件。一步一步退回來，一直退到出發(fā)點。通過正反兩個方面的連接，倒著走得通，順著也可以走得通，這就是PDPC法一個正確

40、的思考辦法。編輯PDPC法的運用及實例PDPC法有五大方面的用處，它們分別是：1、制定目標(biāo)管理中間的實施計劃，怎樣在實施過程中解決各種困難和問題；2、制定科研項目的實施計劃；3、對整個系統(tǒng)的重大事故進(jìn)行預(yù)測；4、制定工序控制的一些措施；5、義務(wù)選擇處理糾紛的各種方案。實際上PDPC法在哪里都可以應(yīng)用，遠(yuǎn)遠(yuǎn)不止這五個。只要做事情，就可能有失敗，如果能把可能失敗的因素提前都找出來，制定出一系列的對策措施，就能夠穩(wěn)步地、輕松地到達(dá)目的地。任何一件事情的調(diào)整都是很不容易的，整個生產(chǎn)系統(tǒng)就像一張巨大的網(wǎng)，要動一個地方跟著就要動一片。所以說，PDPC法是一個系統(tǒng)思考問題的方法，而生產(chǎn)、生活的復(fù)雜性，也要求

41、人們在辦事情、做計劃、干事業(yè)的時候要深思熟慮，不能馬虎大意、隨隨便便，否則的話就會一招不慎，滿盤皆輸。這也是“成于思，毀于隨”的真正意義所在。如果決策問題只要求做一次決策，就是單級決策問題，圖中只有一個決策結(jié)點。如果要求分幾次做出決策，即為多級決策問題，在決策樹中就會有多個決策結(jié)點。對于多級決策問題，處理問題的思路與單級決策問題基本上是相似的。因為下一級的決策問題一旦解決以后，這個決策結(jié)點的作用就同狀態(tài)結(jié)點一樣了。所以，處理多級決策問題時只要從最末一級的決策開始往上進(jìn)行，逐級遞推就可以了。單級決策問題的解決思路與表式?jīng)Q策法的基本思路是一致的。只要求出各方案分枝的損益期望值就可以了。根據(jù)各方案分

42、枝的損益期望值和各方案的初始投資情況，就可以對各方案分枝決定取舍，稱之為剪枝。1、明確所要處理的決策問題是幾級決策問題，明確各級決策之間的邏輯關(guān)系以及各級決策各有幾種方案，明確各級決策所面臨的有幾種自然狀態(tài)及各種自然狀態(tài)發(fā)生的概率。2、畫出決策樹圖，畫圖時應(yīng)注意各類結(jié)點的層次關(guān)系，并將某決策方案在某種自然狀態(tài)下的損益值標(biāo)于樹圖的相應(yīng)的末端位置。3、從右向左計算各結(jié)點的期望值，術(shù)語稱為滾回或折回。遇到?jīng)Q策結(jié)點時則應(yīng)先視為單級決策問題進(jìn)行決策。經(jīng)過取舍，剪枝后再參加下一級的決策。4、逐級剪枝，滾回上行，完成所有決策結(jié)點的剪枝工作，則整個決策問題就決定了。對于單級決策問題。最后得到一個決策方案；寸于

43、多級決策問題,最后得到的是一個若干個相關(guān)決策組成的決策組合。覆蓋的分布式計算機系統(tǒng)(Distributedcomputersystems，DCS)的可靠性分析。在這種基于多態(tài)二元決策圖(Multi-stateBDD，MBDD)方法中，用一個布爾變量表達(dá)部件的每個狀態(tài)，變量等于0或1代表該部件不處于或處于這個特定狀態(tài)，根據(jù)所有的布爾變量即可生成系統(tǒng)的二元決策圖。Miller提出了多值決策(Multiple-valueddecisiondiagram，MDD)的概念，多值決策圖是將二元決策圖的二元邏輯擴展為多值邏輯，也就是將布爾變量擴展為多態(tài)變量。Miller等描述了在多值決策圖中排序交換的矩陣方

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