東北大學管理科學與工程運籌學必備知識點

第一章線性規(guī)劃與單純性法1、線性規(guī)劃問題的數(shù)學模型及各要素的基本特征線性規(guī)劃問題的三個要素的基本特征決策變量：每一個問題都用一組決策變量(X1,x2，…,xn)表示某一方案，這組決策變量的值就代表一個具體方案。一般這些變量取值是非負且連續(xù)的。約束條件：存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示。目標函數(shù)：都有一個要求達到的目標，它可用決策變量的線性函數(shù)(稱為目標函數(shù))來表示。按問題的不同，要求目標函數(shù)實現(xiàn)最大化或最小化。數(shù)學模型，其一般形式為：目標函數(shù)ifax(min)二=c\ai十心十.…十”,一心fZfiiTi十￡112Al十…+Hi“A芒(=,蘭)Z；2JTi+￡&一七+…+HiA芒(=)R滿足約束條件< …a；ilAl+"兩志+?，.+UmaA )fe.'.'i< .ViAz*….匚*0標準型式為:|mux宅=習小件』muxJ-]b.(i=\-2- -ft)>(j=1.2. -/I)其中，x(/=1，2,...,〃)為決策變量，a〃(i=1,2,...,mj=1,2,...,n)為工藝系數(shù)，b.(i=1,2,..,m)為資源系數(shù)，W=1,2,...,〃)為價值系數(shù)。2、如何將線性規(guī)劃問題轉(zhuǎn)變?yōu)闃藴市腿裟繕撕瘮?shù)要實現(xiàn)最小化，minZ=CX。需將最小化轉(zhuǎn)變?yōu)樽畲蠡?，令Z’=-Z，的maxZ’=-CX。約束方程為不等式A：約束方程為W的不等式，左端加入非負松弛變量。B:約束方程為巳的不等式，左端減去非負松弛變量。若變量xk無約束時，令xk：=xk，-xk，,，xk?xk，,N03、可行解，基，基可行解，可行基的概念及相互關(guān)系可行解：滿足約束方程不等式，并且滿足xkN0，稱為線性規(guī)劃問題的可行解。其中使目標函數(shù)達到最大值的可行解稱為最優(yōu)解?；涸O(shè)A是約束方程組mxn維系數(shù)矩陣，其秩為m,B是矩陣A中的mXm階的非奇異子矩陣，則稱B為線性規(guī)劃問題的一個基?；尚薪猓簼M足非負條件（xkN0）的基解，稱為基可行解?？尚谢夯尚薪鈱?yīng)的基，稱為可行基。4、 解的幾何意義（1） 若線性規(guī)劃問題有可行解「其所有訶行解構(gòu)成的區(qū)域稱為可行域，則此可行域D=■：XI 白'可直‘=hz=1-2.….山0}i=I必是?個凹集.（2） 線性規(guī)劃問題的基本可行解與可行域D的頂點一一對應(yīng)。（3） 如果線性規(guī)劃問題有有限的最優(yōu)解，則其目標函數(shù)的最優(yōu)值一定可以在可行域的頂點上達到.5、 線性規(guī)劃問題的幾何意義定理1：“若線性規(guī)劃問題存在可行域，則其可行域是凸集”，要會證明。引理1：“線性規(guī)劃問題的可行解X="X1,x2,□,xn）T為基可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量是線性獨立的”，要會證明（記住從必要性和充分性兩方面證明）。定理2“線性規(guī)劃問題的基可行解X對應(yīng)于可行域D的頂點?！币獣C明（利用反證法，從兩個方面證明）。定理3“若可行域有界，線性規(guī)劃問題的目標函數(shù)一定可以在其可行域的頂點上達到最優(yōu)”要會證明。6、 單純形法求解線性規(guī)劃的思路一般線性規(guī)劃問題具有線性方程組的變量數(shù)大于方程個數(shù)，這時有不定的解。但可以從線性方程組中找出一個個的單純形，每一個單純形可以求得一組解，然后再判斷該解使目標函數(shù)值是增大還是變小，決定下一步選擇的單純形。這就是迭代，直到目標函數(shù)實現(xiàn)最大值或最小值為止。（從可行域中的某個基可行解開始到另一個基可行解，直到目標函數(shù)達到最優(yōu)）7、 線性規(guī)劃解的判別定理最優(yōu)解判別定理若=5」.偵：-，、’,0,—，0）「為基"行娜.II一全由5",0,/=m+I,，則上'眼為M優(yōu)俐.唯一最優(yōu)辯判別定理若X㈣=（",妃、…妃n…為L31行帆II一全部％<07=0/+l,.--,rrj；ll]V（CK為唯?-最優(yōu)解.無窮多最優(yōu)解判別定理若耙二5「，心…,y,o,…,官為墓可行解，且全部彳woj=折+1,…m,且存在一個非基變量…的…=o,則存在無窮多最優(yōu)解.無界解判別定理若有一個非基變量孔4的七祎,0,而其對應(yīng)非基變量的所有系數(shù)人E，W0J二1,2,小,叫則具有無界解n8、 單純形法的計算步驟①我出初始可行基，確定初始基本可行解，建立初始單純形表.甕檢驗此基本可行解是否為最優(yōu)解.即檢驗各非基變量七的檢彩數(shù)％?.若所有刀〈0。=科41,…，國則已經(jīng)得到最優(yōu)解，計算停止；否則轉(zhuǎn)下?,步■③在內(nèi)：>0（/=淅+1廣?5）中若有某個檢驗數(shù)辦對或的非基變量m的系數(shù)列向量日=（皿，皿“??、珈）1<。,則此問題為無界解，停止計算.否則轉(zhuǎn)下一步，?根據(jù)maK^.>0）=欠?確定非基變寅力為換人變量;布?根據(jù)H法則（2=min/— >0\=—1W￡ faft.確定基變量心為換出變雖"⑤實施樞軸運算’即以％為主元素進行樞釉運算（亦即進行矩陣的行變換），使R變換為第1行的兀素為L其余的元素為內(nèi)并將Xb列中的豹換為幻，從而得新的單純形費；重復(fù)②?⑤?直到終止.9、 單純形法的進一步討論（1） 大M法在一個線性規(guī)劃問題的約束條件中加進人工變量后，要求人工變量對目標函數(shù)取值不受影響，為此假定人工變量在目標函數(shù)中的系數(shù)為（-M）（M為任意大的正數(shù)），這樣目標函數(shù)要實現(xiàn)最大化時，必須把人工變量從基變量換出。否則目標函數(shù)不可能實現(xiàn)最大化。（2） 兩階段法嗥理邊I：方法是將加Ak「一變量后的線性觀對M題分成舛個階段某求解，第一階段：不考慮原問題是否存在基可行解；給原線性規(guī)劃問題加入人工變量，并構(gòu)造僅含人工變量的目標函數(shù)和要求實現(xiàn)最小化。或 】」H】Lg=]+J'nT十…十"iuF」]，下] +J-jrk] f)4-4-*s..LJj-rt-I—f—+++—t—/rr ―r—?■ fr1■J=」, ‘2UJI—lji 15="lhJU-r￡gjTj,J"孑。-J-,,.]?"i,J", 然后用單純形法求解上述模型，若得到3=0，這說明原問題存在基可行解，可以進行第二段計算。否則原問題無可行解，應(yīng)停止計算。第二階段：將第一階段計算得到的最終表，除去人工變量。將目標函數(shù)行的系數(shù)，換原問題的目標函數(shù)系數(shù)，作為第二階段計算的初始表。10、 退化解及勃蘭特規(guī)則退化：單純形法計算中用。規(guī)則確定換出變量時，有時存在兩個和兩個以上最小比值，這樣在下一次的迭代中就有一個或者幾個基變量等于零，這就出現(xiàn)退化解。勃蘭特規(guī)則：(1)選取c-z>0中下標最小的非基變量xk為換入變量。當按。規(guī)則存在兩個和兩個以上最小比值時，選取下標最小的基變量為換出變量時。11、 (實際問題)建立線性規(guī)劃模型的條件(1)要求解問題的目標函數(shù)能用數(shù)值指標來反映，且為線性函數(shù)；(2)存在著多種方案；(3)要求達到的目標是在一定約束條件下實現(xiàn)的，這些約束條件可用線性等式或不等式來描述。12、 圖解法(1)優(yōu)缺點：圖解法；圖解法簡單直瀾，求解線性規(guī)劃問題時不需將數(shù)學模型化為標準型，可以直接在平面上作圖，但此法只適用于二維問題，故有一定局限性。I②用圖解法求解，有助于了解線性規(guī)劃問題求解的基本原理。它可以直接看出線性規(guī)劃問題解的幾種情況：r有惟一最優(yōu)解；/有無窮多組最優(yōu)解；3"無可有解；4"無有限最優(yōu)解(即為無界解)，(2)圖解法的羅驟：建立平面直角坐標系；圖示約束條件，找出可行域；圖示目標函數(shù)，即為一條直稅？④將日標函數(shù)直線沿其法線h向在可彳丁域內(nèi)向nnJ-域邊界平移直至]【標函數(shù)o第二章對偶理論和靈敏度分析1、對偶問題的基本性質(zhì)（1） 對稱性：對偶問題的對偶是原問題。（2） 弱對偶性：若X是原問題的可行解，Y是對偶問題的可行解。則存在CXWYb。（3） 無界性：若原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行解。（4） 可行解的最優(yōu)性質(zhì)：設(shè)X是原問題的可行解，Y是對偶問題的可行解，當CX=Yb時，X，Y是最優(yōu)解。（5） 對偶定理：若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解；且目標函數(shù)值相等。（6） 互補松弛性：若X，Y分別是原問題和對偶問題的可行解。那么YXS=0和YSX=0，當且僅當X，Y為最優(yōu)解。（必須都會證明）2、對偶問題的經(jīng)濟解釋一子價格y：的值代表對第i種資源的估價。這種估價是針對具體工廠的具體產(chǎn)品而存在的一種特殊價格，稱它為“影子價格”。影子價格隨具體情況而異，在完全市場經(jīng)濟的條件下，當某種資源的市場價低于影子價格時，企業(yè)應(yīng)買進該資源用于擴大生產(chǎn)；而當某種資源的市場價高于企業(yè)影子價格時，則企業(yè)的決策者應(yīng)把已有資源賣掉?？梢娪白觾r格對市場有調(diào)節(jié)作用。3、對偶單純形法的計算步驟如下（L）將問題化為標準型,列出初始單純形表格°（￡）若存在初始對偶可行的基本解’則進行迭代，⑶檢毓b列的數(shù)字■若檢驗數(shù)全部非正而b列都為非負,則問題已得到最優(yōu)解,線止一迭代；否則,若檢驗數(shù)全部非正而B列至少還有…個負分量，進行下一步°（4）確定換出變量-即按對成的基變量刀為換出變量。3）確定挽人變量：檢查的所所在行的各系數(shù)皿= …仃門。若所仃"云0,叩］無彳r解停I上選代，若存盅u<0,接伊法叩］,皿8—nmi所對應(yīng)的列的非基變量叫為換人變量。（6）實施樞軸運算,即以七為主元素接原單純形法在表中避彳「選代運算,得新的單純形表格，轉(zhuǎn)步驟3）繼續(xù)迭低4對偶單純行法與單純行法的區(qū)別對偶單純行法是運用對偶原理求解原問題的一種方法，而不是求解對偶問題的單純行法。它和單純行法的主要區(qū)別在于：單純行法是從一個原問題的基本可行解轉(zhuǎn)到另一個基本可行解，即迭代中始終保持原問題

的基本可行解，常數(shù)列bN0,5則由正分量變成W0。對偶單純行法則是保持對偶問題是基本可行解(即檢驗數(shù)5N0)，而原問題在非可行解(bW0)的基礎(chǔ)上逐步迭代達到基本可行解(bN0)。5、對偶單純形法有以下優(yōu)缺點初始解可以是非可行解，當檢驗數(shù)都為負數(shù)時，就可以進行基的變換，這時不需要加入人工變量,因此可以簡化計算。當變量多于約束條件，對這樣的線性規(guī)劃問題，用對偶單純形法計算可以減少計算工作量，因此對變量較少，而約束條件很多的線性規(guī)劃問題，可先將它變換成對偶問題，然后用對偶單純形法求解。在靈敏度分析及求解整數(shù)規(guī)劃的割平面法中，有時需要用對偶單純形法，這樣可使問題的處理簡化。對偶單純形法的局限性主要是，對大多數(shù)線性規(guī)劃問題，很難找到一個初始可行基，因而這種方法在求解線性規(guī)劃問題時很少單獨應(yīng)用。6、改進單純形法對單純形法的改進當用單純形表求解線性規(guī)劃問題時，每行每列的數(shù)字都需要進行計算，而有些行列的數(shù)字在下一步計算時并不需要，改進單純形法通過矩陣運算求解線性規(guī)劃問題。第三章運輸問題1、運輸問題的數(shù)學模型產(chǎn)銷平衡條件下運輸問題的數(shù)學模型具仃m個產(chǎn)地&(i=1?『.???m)和H個箱地E(/=1M?…?)的運輸問題的&學模型為:mi】】rw'rw'￡以=卜e-=1,3,…，肩它包含彤X月個變量,3+Q個約萬程,其系數(shù)矩昨的結(jié)構(gòu)松散,且比較特殊b2、表上作業(yè)法的步驟找出初始基可行解。求各非基變量的檢驗數(shù)，即在表上計算空格的檢驗數(shù)，判別是否達到最優(yōu)解。如已是最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一步。確定換入變量和換出變量，找出新的基可行解。在表上用閉回路法調(diào)整。（4）重復(fù)（2）,（3）直到得到最優(yōu)解為止。3、 確定初始基可行解（1） 最小元素法最小元素法的基本思想是就近供應(yīng)，即從單位運價表中最小的運價開始確定供銷關(guān)系，然后次小。一直到給出初始基可行解為止。最小元素法的缺點是：為了節(jié)省一處的費用，有時造成在其他處要多花幾倍的運費。（2） 伏格爾法伏格爾法考慮到，一產(chǎn)地的產(chǎn)品假如不能按最小運費就近供應(yīng)，就考慮次小運費，這就有一個差額。差額越大，說明不能按最小運費調(diào)運時，運費增加越多。因而對差額最大處，就應(yīng)當采用最小運費調(diào)運。伏格爾法同最小元素法除在確定供求關(guān)系的原則上不同，其步驟相同。伏格爾法給出的初始解比用最小元素法給出的初始解更接近最優(yōu)解。4、 最優(yōu)解的判別（1） 閉合回路法需給每一空格找一條閉回路。用水平或者垂直線向前劃，當碰到一數(shù)字格時可以轉(zhuǎn)90度后，繼續(xù)前進，直到回到起始空格為止。當產(chǎn)銷點很多時，這種計算很繁。（2） 位勢法5、 運輸問題一般運輸問題是要把某種產(chǎn)品（或物資）從若干個產(chǎn)地調(diào)運到若干個銷地，每個產(chǎn)地煩人產(chǎn)量、每個銷地的銷量和產(chǎn)銷各地之間的單位運價（或運距）已知，要求確定出使總運輸費用最小的運輸方案。第五章整數(shù)規(guī)劃1、 整數(shù)規(guī)劃<15整數(shù)觀劃：換策變及要求取整數(shù)的線性規(guī)刖”<2）燧敬規(guī)劃時分為純整數(shù)規(guī)劃和況合整數(shù)規(guī)劃”<3?整數(shù)規(guī)劃的可行城為離散點集”2、 分值定界法基本思想：設(shè)有最大化的整數(shù)規(guī)劃問題A，與它相應(yīng)的線性規(guī)劃為問題B，從解問題B開始，若其最優(yōu)解不符合A的整數(shù)條件，那么B的最優(yōu)目標函數(shù)必是A的最優(yōu)目標函數(shù)z*的上界，記作N；而A的任意可行解的目標函數(shù)值將是z*的一個下界Z。分支定界法就是將B的可行域分成子區(qū)域（稱為分支）的方法，逐步減小Z和增大Z，最終求到z*。優(yōu)缺點：可解純整數(shù)規(guī)劃問題和混合整數(shù)規(guī)劃問題，它比窮舉發(fā)優(yōu)越，因為它只在一部分可行解的整數(shù)解中尋求最優(yōu)解，計算量比窮舉法小，但變量數(shù)目很大時，計算量也較大。3、割平面法意義及原理：割平面法的基礎(chǔ)仍然是用解線性規(guī)劃的方法去解整數(shù)規(guī)劃問題，首先不考慮變量X］是整數(shù)這一條件，但增加線性約束條件（用幾何術(shù)語，稱為割平面）使得由原可行域中切割掉一部分，這部分只包含非整數(shù)解，但沒有切割掉任何整數(shù)可行解。這個方法就是指出怎樣找到適當?shù)母钇矫妫ú灰姷靡淮尉驼业剑?，使切割后最終得到這樣的可行域，它的一個有整數(shù)坐標的極點恰好是問題的最優(yōu)解。求切割方程的步驟：（1）先不?考慮整數(shù)條件，求解（1）相對應(yīng)的線性規(guī)劃問題與分支定界法步躁⑴I一樣，同樣可彳晶到=種結(jié)果之一。（2）求個切割方程；切割方程叩由單純形表的最終表中的任一個含有非整數(shù)基變量的等式約束演變而來,因此，切割方程不惟一，r令匚?為相應(yīng)的線性規(guī)劃（L）的最優(yōu)解中為分數(shù)值的一個基變量，由單純形的最終表得到，4 =If ①JII1泛Q表示構(gòu)成基變量號碼的集合36 K表示構(gòu)成非基變量號碼的集?匚廠將快和"都分解成整數(shù)部分E和非負直分數(shù)f之和，即=M 其中QVEVlTOC\o"1-5"\h\zJt1!1 "而n為不超過力的最大整數(shù),即N=m.并將①代人②.得七―訐k一x=f一 &工\ ③A A虹提出變量為整數(shù)的條件（當然還有非負條件）?由③式左邊看必須是整數(shù)，但右邊因為0</<1,所以不能為正.故得切割方程ft- ?MMWQ ?仃）在（切的基礎(chǔ)上，增加第一個切割方程,即構(gòu)成線性規(guī)劃問題用單純形法或?qū)ε紗渭冃畏ㄇ笞顑?yōu)解,若（LQ得到的仍為非整數(shù)解，則返回步（2》，繼續(xù)求第二『切割方程。4、指派問題概念：在生活中經(jīng)常遇到這樣的問題，某單位需完成n項任務(wù)，恰好有n個人可承擔這些任務(wù)。由于每人的專長不同，各人完成任務(wù)不同（或所費時間），效率也不同。于是產(chǎn)生應(yīng)指派哪個人去完成哪項任務(wù)，使完成n項任務(wù)的總效率最高（或所需總時間最?。＿@類問題稱為指派問題或分派問題。當指派問題要求極小化時數(shù)學模型是：TOC\o"1-5"\h\ziwin.-=已三2C助 ①：丁方=1nJ=1.W ⑵習叫=1一 …一時 ③.x』j=I或0 ④5、 分值定界法求解最大化正數(shù)規(guī)劃問題的步驟m解與整敬現(xiàn)劃同題4相應(yīng)的線性規(guī)劃”HB網(wǎng)能博到以VII種情配之-:H投方可行解m也沒有可行解，停止計算『B擊■最憂解?并符合向題也的整數(shù)條件,則此最優(yōu)解即為A的最優(yōu)解，停It計算.曲H有最優(yōu)解5!不符合坎的嫌數(shù)條件，吧它的H標函數(shù)S(2)用觀察法找問函A的?-?個整散Mirffh求得其目標函SUiL并E作？以廠心小問度A的最優(yōu)目標皴則三W二-WJF而JH行迭伐e分是,在的最說所小任迷個不對合糧散象M自勺至p：」.1ftn'i為入…構(gòu)造兩個約束條件MSJ ①、T>M「如二+1 ②苴中「由.1為不超Mt農(nóng)的最大常姓，將這兩個約束條件+刖加人問題jl求兩個后推規(guī)劃問題r;,和門…不考忘整教約束條件求酈這兩個后繼問題。定群,以舟個后維問哩為-弁就衍明求解的結(jié)果°第-步〉七不考?晦整數(shù)約束，變典-般的戢性規(guī)劃問度,JI：圖淅法或單純形法求其最優(yōu)酈,記為%，"第:^=告求得的最優(yōu)酈-Y1(1>，HJ好就是整數(shù)辯?瀏反整數(shù)就是康整數(shù)規(guī)劃的最優(yōu)講■汗財，專下-步m第?-.步=CJ原IF建坦1J-5T芝尋求整教最伉的”彥取非整數(shù)解X.,的一個非整數(shù)分遷工；=&,其小數(shù)部分為a,以詼非整數(shù)部陌N?的.用鄰整靚丹.一止和￡.一/.+I為由.睥啊原I試理丹￡為兩個FIE題?并拋券宜兩個整皴之間的升常數(shù)區(qū)以^也在京戢性規(guī)劃模型；1「添加命史約束一H,-構(gòu)成第-介JTE哽"匿在京線性規(guī)劃模型中季加分芝約束―巳-+I,構(gòu)成第：個「問題」第四步=利I一面兩十「問距按娘及性規(guī)劃方法求最脫解。若玷個E?淄的料是帕牧前平-則倍止昧了T可客的分玄,并且把它的目標值勺上一步?點出的最優(yōu)整數(shù)解￥1I比收以決定取舍「再則、時■「問題縫續(xù)班I」?命￡°第.吭步=重復(fù)簞：..四步H至荻得蝦問腐最機整皴酈為|二『6、 隱枚舉法0—1規(guī)劃的隱枚舉法的基本思想是；首先令全部變量取0(因為目標函數(shù)的系數(shù)全非正，此時，相應(yīng)的目標函數(shù)值f就是上界兀如果此解可行，則為最優(yōu)解,計算終止；否則，選擇某個變量為0或1,將問題分析成兩個子間題，繼續(xù)分別對它們進行檢驗「即令沒有被選擇的變量全部為。，檢查是否2行。如此下去，或者再分支，或者使所有的子問題停止分支，并以最大下界值對應(yīng)的可行解為最優(yōu)第八章動態(tài)規(guī)劃的基本方法1、 動態(tài)規(guī)劃的基本概念和基本方程（1） 階段變量：把所給問題的過程，恰當?shù)胤譃槿舾蓚€相互聯(lián)系的階段，以便能按一定的次序去求解。描述階段的變量稱為階段變量，常用k表示。（2） 狀態(tài)：表示每個階段開始所處的自然狀況或客觀條件，它描述了研究問題過，程的狀況，又稱不可控因素。狀態(tài)變量應(yīng)具有無后效性（馬爾科夫性）：如果某階段狀態(tài)給定后，則在這階段以后過程的發(fā)展不受這階段以前各段狀態(tài)的影響。換句話說，過程的過去歷史只能通過當前的狀態(tài)去影響它未來的發(fā)展，當前的狀態(tài)是以往歷史的一個總結(jié)。（3） 決策：決策表示當過程處于某一階段的某個狀態(tài)時可以作出不同的決定（或選擇），從而確定下一階段的狀態(tài)，這種決定稱為決策。在最優(yōu)控制中也稱為控制。描述決策的變量，稱為決策變量。（4） 策略：策略是一個按順序排列的決策組成的集合。（5） 指標函數(shù)：用來衡量所實現(xiàn)過程優(yōu)劣的一種數(shù)量指標，稱為指標函數(shù)。對于，要構(gòu)成動態(tài)規(guī)劃模型的指標函數(shù)，應(yīng)具有可分離性，并滿足遞推關(guān)系。2、 動態(tài)規(guī)劃方法的基本思想（1） 動態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當?shù)倪吔鐥l件（簡言之為基本方程）。要做到這一點，必須先將問題的過程分成幾個相互聯(lián)系的階段，恰當?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個大問題化成一族同類型的子問題，然后逐個求解。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。（2） 在多階段決策過程中，動態(tài)規(guī)劃方法是既把當前一段和未來各段分開又把當前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的。（3） 在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐次變換得到，從而確定了最優(yōu)路線。3、 建立動態(tài)規(guī)劃模型的5個注意點（1） 將問題的過程劃分成恰當?shù)碾A段；（2） 正確選擇狀態(tài)變量％，使它既能描述過程的演變，又要滿足無后效性；（3） 確定決策變量*，及每階段的允許決策集合Dk（sk）；（4） 正確寫出狀態(tài)轉(zhuǎn)移方程；（5） 正確寫出指標函數(shù)Vien的關(guān)系，它應(yīng)滿足下面三個性質(zhì)：是定義在全過程和所有后部子過程上的數(shù)量函數(shù)；要具有可分離性，并滿足遞推關(guān)系。即Vk，n（Sk，kk，…，Sn+1）—"k[Sk，Uk，Vk+1，n（Sk+1，Uk+1，…，Sn+1）]③函數(shù)虹（Sk，Uk，vk+1，n）對于變量Vk+1，n要嚴格單調(diào)。以上五點是構(gòu)造動態(tài)規(guī)劃模型的基礎(chǔ)，是正確寫出動態(tài)規(guī)劃基本方程的關(guān)鍵。4、動態(tài)規(guī)劃的逆序遞推方程和順序遞推方程（1）逆序解法的基本方程：{k=u.it—1-■■■-2■1）?邊界條件為f?4Cm,）=0（2）順序解法的基本方程：Mi)=*瞄雄十i(^=1-2-■■■-a邊界條件為尤（而）=0第九章動態(tài)規(guī)劃應(yīng)用舉例1、最優(yōu)排序的規(guī)則（1） 先作工件的加工時間的工時矩陣；（2） 在工時矩陣M中找出最小元素（若最小的不止一個，可任選其一）；若它在上行，則將相應(yīng)的工件排在最前位置；若它在下行，則將相應(yīng)的工件排在最后位置。（3） 將排定位置的工件所對應(yīng)的列從M中劃掉，然后對余下的工件重復(fù)按（2）進行。但那時的最前位置（或最后位置）是在已排定位置的工件之后（或之前）。如此繼續(xù)下去，直至把所有工件都排完為止。第十四章對策論基礎(chǔ)1、對策論的概念對策論：對策論就是研究對策行為中斗爭各方是否存在著最合理行動方案，以及如何找到最合理行動方案的數(shù)學理論和方法。局中人：在一個對策行為（或一局對策）中，有權(quán)決定自己行動方案的對策參加者，稱為局中人。通常用I表示局中人的集合。需要強調(diào)的一點是，在對策中總是假定每一個局中人都是“理智的”決策者或競爭者,即對任一局中人來講，不存在利用其他局中人決策的失誤來擴大自身利益的可能性。策略集：一局對策中，可供局中人選擇的一個實際可行的完整的行動方案稱為一個策略。參加對策的每一局中人i,iGI,都有自己的策略集S］。一般，每一局中人的策略集中至少應(yīng)包括兩個策略。2、矩陣對策的基本原理二人有限零和對策就是矩陣對策：是指只有兩個參加對策的局中人，每個局中人都只有有限個策略可供選擇。在任一局勢下，兩個局中人的贏得之和總是等于零，即雙方的利益是激烈對抗的。定理1矩陣對策3= ,.0小}布純策略意義F有解的充分■必要條件是：存在純局勢W?傷)使得對一切l(wèi)1廣-.心._/=1,“-.廿.均有崩CW心。定理2矩陣對?策仁=，"、.圣；劣：住混弁策略意義卜仃解的允班條件是：存在￡O/ES「使(/，丘)為函數(shù)日字刃的-個鞍點，即—一切jt€-S/■yF -4}以j-y'-了'定理3設(shè)”e*勺FW?則?！?)是對策仁11勺斛「I勺充要荼件是：刈任意i=1*2-■■■ifi和』=1 ,打?-fjFf.iy)MF3a)丁玖工、/定理4設(shè)15頊.則3-.》')為對?策(；的解的充要條件是：存：在數(shù)4使得”和W分別是不等式組i(J=1.2?…5〕京.=1i(J=1,2-…」HJ毛瑟。和不等式組Wp.2 )=1(j=1,2/=1、*壬。的解JLv=v?.ohnlNV；,.=MX'q「'j=A5、i=1f=1定理5.司仆,矩陣.時策G=gWm2.A}.-定存一在混合灌路點一義FIN解定理6設(shè)3、也”J是炬陣對策「；的解.則對某-個，或』Wj(1HAO?則￡」點；=v,.Q』=1(2〕若>0T［jjl］〉：七工：=叫；ai=I.(3J若〉［y「V”，則=0a(1〕若 >□,則燈=0a定理7設(shè)有兩個矩陣對策I=(SI-.Sg：.4I?Gi={Sl,SnAi}\cd'A：>.：.%.g.u‘.mt-常數(shù)-則仃(2)r(G,)=T(6)U(G)表示矩陣G的解集L定il8設(shè)有兩個矩陣X寸策M.=$$:A}Ctj=〈5i-S:a\-其中兀AQ為任一常數(shù)，則(1)I"=uV，-;⑵T(G)=T?兒定理9設(shè)仁= A}為-矩陣對策，且凡=一A”為斜對稱炬陣.則(l>Ve=Of《2)「WG)=J\(G),其中TJG)和T2(G)分別為局中人I和II的最優(yōu)策略集.定理10設(shè)C；={SL，脆A}為矩陣對策，其中Sl=0?的?…不},$=w亂}"=頃弁、如果純策略a,被其余純策略電-…-f中之，所優(yōu)超-Ul仁可得到一個新的矩陣對策廿:其中Si.=■：Of；；,…}A_i.iij](m—I.TXm/可=E..■!=2?…；J=1 "I「是有(1〕V；=F；:(2H/+局中人||的最優(yōu)策略就是其布G中的最優(yōu)策略；⑶若京"M…MT是G'中局中人I的最優(yōu)策略，則！=CO一35-…篇尸便是其在■中的最優(yōu)策略.第十五章單目標決策1、 決策的分類決策：決策是人們在政治、經(jīng)濟、技術(shù)以及日常生活中普遍遇到的一種選擇方案的行為。其困難是如何從多種方案中作出正確的選擇,以便獲得好的結(jié)果或達到預(yù)期的目標。從不同的角度出發(fā)可得不同的決策分類：（1） 按性質(zhì)的重要性分類。可將決策分為戰(zhàn)略決策、策略決策和執(zhí)行決策，或叫戰(zhàn)略計劃、管理控制和運行控制；（2） 按決策的結(jié)構(gòu)分類。分為程序決策和非程序決策。（3） 按定量和定性分類。分為定量決策和定性決策，描述決策對象的指標都可，以量化時可用定量決策，否則只能用定性決策。總的發(fā)展趨勢是盡可能地把決策問題量化。（4） 按決策環(huán)境分類?？蓪Q策問題分為確定型的、風險型的和不確定型的三種。確定型的決策是指決策環(huán)境是完全確定的，作出的選擇的結(jié)果也是確定的。風險型決策是指決策的環(huán)境不是完全確定的，而其發(fā)生的概率是已知的。不確定型決策是指決策者對將發(fā)生結(jié)果的概率一無所知，只能憑決策者的主觀傾向進行決策。（5） 按決策過程的連續(xù)性分類。可分為單項決策和序貫決策。2、 決策過程構(gòu)造人們決策行為的模型主要有兩種方法：一種是面向決策結(jié)果的方法；另一種是面向決策過程的方法。面向決策結(jié)果的方法認為：若決策者能正確地預(yù)見到?jīng)Q策結(jié)果，其核心是決策的結(jié)果和正確的預(yù)測。通常的單目標和多目標決策是屬這類型的。面向決策過程的方法認為：若決策者了解了決策過程，掌握了過程和能控制過程，他就能正確地預(yù)見決策的結(jié)果。3、 決策模型的構(gòu)成要素（1） 決策者：其任務(wù)是進行決策。決策者可以是個人、委員會或某個組織。一般指領(lǐng)導(dǎo)者或領(lǐng)導(dǎo)集體。（2） 可供選擇的方案：了解研究對象的屬性，確定目的和目標。（3） 準則：是衡量選擇方案的標準。（4） 事件：不為決策者所控制的客觀存在的將發(fā)生的狀態(tài)。（5） 結(jié)果：每一事件的發(fā)生將會產(chǎn)生某種結(jié)果，如獲得收益或損失。（6） 決策者的價值觀：如決策者對貨幣額或不同風險程度的主觀價值觀念。4、 不確定型決策概念：指決策者對環(huán)境情況一無所知。這時決策者是根據(jù)自己的主觀傾向進行決策，由決策者的主觀態(tài)度不同基本可分為四種準則：悲觀主義準則、樂觀主義準則、等可能性準則、最小機會準則。基本特征：決策過程中含有不確定性因素，且無法確定其發(fā)生的概率。決策準則：悲觀主義準則、樂觀主義準則、等可能性準則、最小機會準則。悲觀主義決策準則亦稱保守主義決策準則。當決策者面臨著各事件的發(fā)生概率不清時，決策者考慮可能由于決策錯誤而造成重大經(jīng)濟損失。由于自己的經(jīng)濟實力比較脆弱，他在處理問題時就較謹慎。他分析各種最壞的可能結(jié)果，從中選擇最好者，以它對應(yīng)的策略為決策策略。樂觀主義(maxmax)決策準則的決策者對待風險的態(tài)度與悲觀主義者不同，當他面臨情況不明的策略問題時，他絕不放棄任何一個可獲得最好結(jié)果的機會，以爭取好中之好的樂觀態(tài)度來選擇他的決策策略。等可能性(Laplace)準則是19世紀數(shù)學家Laplace提出的。他認為：當一個人面臨著某事件集合，在沒有什么確切理由來說明這一事件比那一事件有更多發(fā)生機會時，只能認為各事件發(fā)生的機會是均等的。決策者計算各策略的收益期望值，然后在所有這些期望值中選擇最大者，以它對應(yīng)的策略為決策策略。最小機會損失決策準則亦稱最小遺憾值決策準則或Savage決策準則。其含義是：當某一事件發(fā)生后，由于決策者沒有選用收益最大的策略，而形成的損失值。折中主義準則，令a為樂觀系數(shù)，且0WQW1，并用以下關(guān)系式表示H=初皿密+。一a)amin5、 風險決策風險決策的概念：風險決策是指決策者對客觀情況不甚了解，但對將發(fā)生各事件的概率是已知的。決策者往往通過調(diào)查，根據(jù)過去的經(jīng)驗或主觀估計等途徑獲得這些概率。在風險決策中一般采用期望值作為決策準則，常用的有最大期望收益決策準則和最小機會損失決策準則。最大期望收益決策準則(expectedmonetaryvalue,EMV):決策矩陣的各元素代表“策略一事件”對的收益值，各事件發(fā)生的概率為p.先計算各策略的期望收益值：Zpa^。然后從這些期望收益值中選取j最大者，它對應(yīng)的策略為決策應(yīng)選策略。最小機會損失決策準則(expectedopportunityloss,EOL):矩陣的各元素代表“策略一事件”對的機會損失值，各事件發(fā)生的概率為p.,先計算各策略的期望損失值：Zpa〃。然后從這些期望損失值中選