運籌學完整教案

《運籌學》教案（本教案適用于32課時的班級）

第一章線性規(guī)劃與單純形法1、教學計劃第1次課2學時授課章節(jié)緒論；第一章第1節(jié)、第2節(jié)、第3節(jié)授課方式□√理論課□討論課□實驗課□習題課□其他課堂教學目的及要求了解線性規(guī)劃模型的背景、掌握建模方法以及線性規(guī)劃的標準形式。掌握兩個決策變量線性規(guī)劃問題可行域（凸集）、最優(yōu)解的位置；了解無解（無界解、無可行解）、有解（唯一解、無窮多個解）的幾何意義。課堂教學重點及難點重點：線性規(guī)劃的數(shù)學模型及其標準形。在數(shù)學模型中，要求熟悉矩陣形式；在標準形中，要求學生掌握非標準形式的幾種具體情形及其相應(yīng)的標準化方法；如何用幾何的方法求兩個決策變量的線性規(guī)劃問題的最優(yōu)解。難點：線性規(guī)劃的基本概念，例如基、基變量、基解、基可行解和可行基；多個最優(yōu)解如何表示。教學過程教學過程教學方法及手段引言 運籌學模型，運籌學發(fā)展歷史與現(xiàn)狀，研究方法；考核方法與教學大綱等。1.1線性規(guī)劃問題及其數(shù)學模型線性規(guī)劃的數(shù)學模型：變量的確定、約束條件與目標函數(shù)。1.2線性規(guī)劃問題的標準形式線性規(guī)劃的標準形式及非標準形式的標準化處理。1.3線性規(guī)劃問題的解基、基變量、基解、基可行解和可行基。多媒體講解實例講解第2次課2學時授課章節(jié)第一章第4節(jié)授課方式□√理論課□討論課□實驗課□習題課□其他課堂教學目的及要求掌握單純形法思想以及具體操作過程。課堂教學重點及難點重點：單純形法迭代過程：（1）換入基變量的確定；（2）換出基變量的確定；（3）判定當前解已經(jīng)最優(yōu)。難點：單純形法思想。教學過程教學過程教學方法及手段1.4單純形法單純形數(shù)表的構(gòu)造，要注意代數(shù)形式和表格形式的一一對應(yīng)性。單純形法迭代過程：（1）換入基變量的確定；（2）換出基變量的確定；（3）判定當前解已經(jīng)最優(yōu)。多媒體講解實例講解第3次課2學時授課章節(jié)第一章第5節(jié)授課方式□√理論課□討論課□實驗課□習題課□其他課堂教學目的及要求掌握人工變量法的基本思想以及大M法和兩階段法的求解。課堂教學重點及難點重點：人工變量法的基本思想。難點：大M法和兩階段法的求解。教學過程教學過程教學方法及手段1.5單純形法的進一步討論及小結(jié)人工變量法的思想，大M法和兩階段法的求解思路和步驟。單純形法小結(jié)多媒體講解實例講解2、課件1.1線性規(guī)劃問題及其數(shù)學模型線性規(guī)劃模型的建立就是將現(xiàn)實問題用數(shù)學的語言表達出來。例1：某工廠要安排生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，每單位產(chǎn)品生產(chǎn)所需的設(shè)備、材料消耗及其利潤如下表所示。問應(yīng)如何安排生產(chǎn)計劃使工廠獲利最多？ⅠⅡ設(shè)備128臺時原材料A4016kg原材料B0412kg單位產(chǎn)品的利潤（元）23解：設(shè)生產(chǎn)產(chǎn)品Ⅰ、Ⅱ的數(shù)量分別為和。首先，我們的目標是要獲得最大利潤，即其次，該生產(chǎn)計劃受到一系列現(xiàn)實條件的約束，設(shè)備臺時約束：生產(chǎn)所用的設(shè)備臺時不得超過所擁有的設(shè)備臺時，即原材料約束：生產(chǎn)所用的兩種原材料A、B不得超過所用有的原材料總數(shù)，即非負約束：生產(chǎn)的產(chǎn)品數(shù)必然為非負的，即由此可得該問題的數(shù)學規(guī)劃模型：總結(jié)：線性規(guī)劃的一般建模步驟如下：（1）確定決策變量確定決策變量就是將問題中的未知量用變量來表示，如例1中的和。確定決策變量是建立數(shù)學規(guī)劃模型的關(guān)鍵所在。（2）確定目標函數(shù)確定目標函數(shù)就是將問題所追求的目標用決策變量的函數(shù)表示出來。（3）確定約束條件將現(xiàn)實的約束用數(shù)學公式表示出來。線性規(guī)劃數(shù)學模型的特點（1）有一個追求的目標，該目標可表示為一組變量的線性函數(shù)，根據(jù)問題的不同，追求的目標可以是最大化，也可以是最小化。（2）問題中的約束條件表示現(xiàn)實的限制，可以用線性等式或不等式表示。（3）問題用一組決策變量表示一種方案，一般說來，問題有多種不同的備選方案，線性規(guī)劃模型正式要在這眾多的方案中找到最優(yōu)的決策方案（使目標函數(shù)最大或最?。?，從選擇方案的角度看，這是規(guī)劃問題，從目標函數(shù)最大或最小的角度看，這是最優(yōu)化問題。1.2線性規(guī)劃問題的標準形式根據(jù)問題的性質(zhì)，線性規(guī)劃有多種形式，目標函數(shù)有要求最大化的，也有要求最小化的；約束條件可以是“”或“”的不等式，也可以是“=”；雖然決策變量一般是非負的，但也可是無約束的，即，可以在取值。為了分析問題的簡化，一般規(guī)定如下的標準形式：非標準形式轉(zhuǎn)化為標準形式：（1）若目標函數(shù)要求實現(xiàn)最小化，則可令，可將原問題的目標函數(shù)轉(zhuǎn)化為即可。（2）若約束方程為“”，則可在“”的左邊加上非負的松弛變量；若約束方程為“”，則可在“”的左邊減去非負的剩余變量。（3）若存在取值無約束的變量，則可令，其中，。例：將如下問題轉(zhuǎn)化為標準形式：解：首先，用替換，其中，；其次，在第一個約束條件的左端加上非負的松弛變量；再次，在第二個約束條件的左端減去非負的剩余變量；最后，令，將求改為求。由此，可得標準形如下：1.3線性規(guī)劃問題的解首先，將線性問題的標準形式用矩陣和向量形式表示如下：其中，；，1、可行解和最優(yōu)解滿足約束條件的所有解成為線性規(guī)劃問題的可行解，其中，使目標函數(shù)達到最大的可行解成為最優(yōu)解。2、基和基解設(shè)為約束方程組的維矩陣，其秩為。設(shè)為矩陣中的階非奇異子矩陣（），則稱為線性規(guī)劃的一個基。不妨設(shè)前個變量的系數(shù)矩陣為線性規(guī)劃的一個基，則為對應(yīng)于這個基的基變量。用高斯消去法可求得一個解該解得非零分量的數(shù)目不大于方程個數(shù)，稱為基解。3、基可行解若基解滿足非負約束，則稱其為基可行解。4、可行基對應(yīng)于基可行解的基，成為可行基。1.4單純形法一、單純形表考察一種最簡單的形式：目標函數(shù)最大化、所有約束條件均為“”。利用所有約束條件化為等號的方法，在每個約束條件的左端加一個松弛變量，并整理，重新對變量及系數(shù)矩陣進行編號，得將其與目標函數(shù)的變換形式組成個變量、個方程的方程組。若將看成不參與基變換的基變量，它與的系數(shù)構(gòu)成一個基，利用初等變換將變?yōu)榱悖瑒t可得據(jù)此，可設(shè)計如下的數(shù)表…………1…0…0…0……………0…1…0……列表示基變量，在這里為；列為基變量對應(yīng)的價值系數(shù)；列為約束方程的右端項；行為所有變量的價值系數(shù)；列的數(shù)字是在確定換入變量后，按規(guī)則計算后填入；最后一行為各變量的檢驗數(shù)，尤其要注意的是非基變量的檢驗數(shù)。例，求解首先將其轉(zhuǎn)換為標準形式，構(gòu)造初始單純形表如下：230000812100401640010-0120[4]001323000由上表可得初始基可行解由于和的檢驗數(shù)大于零，表明上述解不是最優(yōu)解，由于的檢驗數(shù)更大，所以，先以為換入變量。根據(jù)規(guī)則，可確定為換出變量，計算得新表如下：2300002[1]010-1/220164001043301001/4-2000-3/4可得新解，目標函數(shù)取值。的檢驗數(shù)為2，換入。根據(jù)規(guī)則，可確定為換出變量，計算得新表如下：23000221010-1/2-0800-41[2]43301001/41200-201/4得新解，目標函數(shù)取值。的檢驗數(shù)為1/4，換入。根據(jù)規(guī)則，可確定為換出變量，計算得：23000241001/400400-21/2132011/2-1/8000-3/2-1/80得解，目標函數(shù)取值。由于所有的檢驗都小于零，達到最優(yōu)。PS：如果目標函數(shù)是求最小化，則，檢驗數(shù)的最優(yōu)準則為檢驗數(shù)大于零。1.5單純形法的進一步討論及小結(jié)一、人工變量法如果初始約束條件不全是小于等于號，則不能直接得到初始基（單位基）和初始基可行解，此時必須要構(gòu)造人工變量。在迭代結(jié)束后，如果最后基變量中不再含有非零的人工變量，表示原問題有解；反之，則表示無可行解。例：在第一個約束條件中加入松弛變量；在第二個約束條件中加入剩余變量和人工變量；在第三個約束條件中加入人工變量。（1）大M法：在一個線性規(guī)劃問題的約束條件中加入人工變量后，要求人工變量對目標函數(shù)值不產(chǎn)生影響，可假定人工變量在目標函數(shù)中的系數(shù)為（-M）（M為很大的正數(shù)），這樣在目標函數(shù)要實現(xiàn)最大化時，必須將人工變量從基變量中換出，否則目標函數(shù)不會實現(xiàn)最大化。對上例求解，加入人工變量后，規(guī)劃問題變成然后，利用單純形法求解，詳見P33。（2）兩階段法第一階段：不考慮原問題是否有基可行解；給原線性規(guī)劃問題加上人工變量后，構(gòu)造僅含人工變量的目標函數(shù)和要求實現(xiàn)最小化；然后用單純形法求解，若得到該規(guī)劃的最優(yōu)解為零，說明原問題存在基可行解，否則原問題無可行解，停止計算。第二階段：將第一階段的最重計算表出去人工變量，換回原目標函數(shù)的系數(shù)作為第二階段計算的初始表，利用單純形法求解。前一個例子的兩階段法求解如下：構(gòu)造出第一階段的數(shù)學模型如下：00000110111-2110001113-4120-1103/211-20[1]000116-1-3010000000110103-20100-1-110[1]00-11-2101-2010001-0-10010000000110123001-22-5-010100-11-2101-2010001-0000011得最優(yōu)解。由于人工變量，說明是原問題的基可行解，可進行第二階段運算。利用單純形法，從下表開始：-31100012[3]001-2-110100-1111-20100--10001-31100-341001/3-2/3-110100-11190012/3-4/3-0001/31/3二、解的退化所有的檢驗數(shù)均1、基變量中有非零的人工變量，無可行解；2、某非基變量的檢驗數(shù)為零，有無窮多解；對于任一檢驗數(shù)，若對應(yīng)的系數(shù)向量，則有無界解。單純形法小結(jié)變量不需處理令；無約束令，約束條件不需處理約束條件兩端同乘-1加松弛變量=加人工變量減剩余變量，加人工變量目標函數(shù)加入變量的系數(shù)松弛變量0人工變量

第三章運輸問題1、教學計劃第4次課2學時授課章節(jié)第三章授課方式□√理論課□討論課□實驗課□習題課□其他課堂教學目的及要求掌握運輸問題的模型特點；熟悉表上作業(yè)法的基本步驟如初始調(diào)運方案的確定，非基變量檢驗數(shù)的確定方法，當前解是否最優(yōu)解的判斷，閉回路調(diào)整方法；非平衡運輸問題的求解。課堂教學重點及難點重點：初始調(diào)運方案的確定，非基變量檢驗數(shù)的確定，判斷當前解是否最優(yōu)解，閉回路調(diào)整方法，非平衡運輸問題的求解方法。難點：初始基可行解的確定、判斷，非平衡問題的求解思路。教學過程教學過程教學方法及手段3.1運輸問題的提出及其模型特征運輸問題的提出背景及其模型特征3.2運輸問題的求解：表上作業(yè)法表上作業(yè)法的思路和步驟如初始基可行解的確定（最小元素法和伏格爾法），最優(yōu)解的判斷方法，閉回路調(diào)整方法。3.3產(chǎn)銷不平衡的運輸問題將不平衡問題轉(zhuǎn)化為平衡問題。多媒體講解實例講解2、課件3.1運輸問題的提出及其模型特征1、背景大規(guī)模的物資調(diào)運，將物資從生產(chǎn)地點運往消費地點，要求在現(xiàn)有的交通網(wǎng)絡(luò)下，制定出總費用最小的運輸方案。2、模型特征銷地產(chǎn)地12…產(chǎn)量1…2…………..……銷量…個變量，個約束方程，但由于總產(chǎn)量等于總銷量的關(guān)系存在，所以，獨立的約束方程為，因此，其可行解中的基變量個數(shù)必然是。系數(shù)矩陣：變量的系數(shù)向量除第個分量和第個為1外其余為零。3.2運輸問題的求解：表上作業(yè)法表上作業(yè)法實際上是單純形法在求解運輸問題時的一個簡化，主要步驟：（1）找出初始基可行解：最小元素法和伏格爾（Vogel）法最小元素法：優(yōu)先滿足運價最小的供銷關(guān)系例：銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A219284A3741059銷量（噸）3656銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A2eq\o\ac(○,1)（3）9284A3741059銷量（噸）3656銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A13113107A2eq\o\ac(○,1)（3）9eq\o\ac(○,2)（1）84A3741059銷量（噸）3656銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1311eq\o\ac(○,3)（4）107A2eq\o\ac(○,1)（3）9eq\o\ac(○,2)（1）84A3741059銷量（噸）3656銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1311eq\o\ac(○,3)（4）107A2eq\o\ac(○,1)（3）9eq\o\ac(○,2)（1）84A37eq\o\ac(○,4)（6）1059銷量（噸）3656銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1311eq\o\ac(○,3)（4）10（3）7A2eq\o\ac(○,1)（3）9eq\o\ac(○,2)（1）84A37eq\o\ac(○,4)（6）10eq\o\ac(○,5)（3）9銷量（噸）3656銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1437A2314A3639銷量（噸）3656伏格爾法：優(yōu)先滿足最小運價與次小運價差值最大的行、列中的最小運價所對應(yīng)的供銷關(guān)系。銷地產(chǎn)地B1B2B3B4行差A13113100A219281A37eq\o\ac(○,4)1051列差2513（2）求各非基變量（空格）的檢驗數(shù)。閉回路法：首先找到與空格對應(yīng)的閉回路，規(guī)則是從要檢驗空格出發(fā)用水平或垂直線向前滑，碰到數(shù)字格轉(zhuǎn)90度（也可不轉(zhuǎn)，空格處絕不轉(zhuǎn)），最后回到出發(fā)空格形成閉回路。然后，在該空格處試著增加1單位運量，并保持平衡，在閉回路作相應(yīng)的調(diào)整，調(diào)整后回路的總運費相對于調(diào)整前的變動量就是該空格的檢驗數(shù)銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1①②437A231③4A3639銷量（噸）3656銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1437A23④14A3⑤6⑥39銷量（噸）3656如空格A3B1的檢驗數(shù)：7*1-5*1+10*1-3*1+2*1-1*1=10空格A2B4的檢驗數(shù)：8*1-2*1+3*1-10*1=-1位勢法：構(gòu)造位勢和；由基變量的檢驗數(shù)，可得；任取、其中之一為零，可求得其他、；最后，由可求得個非基變量（空格）的檢驗數(shù)。銷地產(chǎn)地B1B2B3B4UiA13-(-8+10)11-(10-1)31010A219-(9-1)28-(9+0)9A37-(-8+5)410-(-7+5)55Vj-8-1-70（3）若存在檢驗數(shù)為負的空格，用閉回路法進行調(diào)整，檢驗數(shù)最小的空格優(yōu)先調(diào)整。調(diào)整時，以相應(yīng)的空格位調(diào)入格（以它對應(yīng)的非基變量為換入變量），以相應(yīng)的閉回路進行調(diào)整，調(diào)入量為閉回路中數(shù)字格中所能調(diào)出量的最小者。銷地產(chǎn)地B1B2B3B4產(chǎn)量（噸）A1437A2314A3639銷量（噸）3656三、運輸問題的特殊情況：1、多重解當非基變量的檢驗數(shù)為零時，會出現(xiàn)多重解。2、退化①當在某空格處填入數(shù)值時，恰好該處供應(yīng)量等于需求量，在此填入相應(yīng)的數(shù)值時須同時劃去一行一列，此時，必須在劃去的該行、該列的任意空格處添一個零。②閉回路調(diào)整時，如出現(xiàn)兩個或兩個以上調(diào)出格的數(shù)值相等，此時只能選擇其中一個作為調(diào)出格，另一個格中必須填零。3.3產(chǎn)銷不平衡的運輸問題相對于標準形式的運輸問題，產(chǎn)銷不平衡問題的求解關(guān)鍵在于將其轉(zhuǎn)化為標準形式的運輸問題，即產(chǎn)銷平衡問題。如果是產(chǎn)量大于銷量，則可增加一個虛擬銷地，任何運往虛擬銷地的產(chǎn)量等同于就地儲存，因此，所有產(chǎn)地運往虛擬銷地的運費為0。如果是銷量大于產(chǎn)量，則可增加一個虛擬產(chǎn)地，由虛擬產(chǎn)地運往各銷地的運量實際上就是供給的缺口，表示現(xiàn)實中沒有實際的供給，因此，由虛擬產(chǎn)地運往各銷地的運費為0。產(chǎn)銷不平衡問題轉(zhuǎn)化為產(chǎn)銷平衡問題之后，利用表上作業(yè)法進行求解的思路和步驟和前一節(jié)的內(nèi)容完全相同。銷地產(chǎn)地B1B2B3B4B5產(chǎn)量（噸）A131131007A2192804A37410509銷量（噸）36533如果存在某些特定的約束，如某地存在一個最低的需求，則應(yīng)注意該部分不能由虛擬產(chǎn)地供給，即，虛擬產(chǎn)地運往該地的單位運輸費用應(yīng)用是一個很大的正數(shù)M。需求地區(qū)化肥廠1234產(chǎn)量A1613221750B1413191560C192023M50D50最低需求3070010最高需求50703060需求地區(qū)化肥廠112344產(chǎn)量A16161322171750B14141319151560C19192023MM50DM0M0M050銷量302070301050

第四章目標規(guī)劃1、教學計劃第5次課2學時授課章節(jié)第四章授課方式□√理論課□討論課□實驗課□習題課□其他課堂教學目的及要求了解目標規(guī)劃的數(shù)學模型、目標規(guī)劃的圖解法，掌握目標規(guī)劃數(shù)學模型的建立方法及其單純形解法和靈敏度分析。課堂教學重點及難點重點：目標規(guī)劃的數(shù)學模型特征，建立目標規(guī)劃的數(shù)學模型，目標規(guī)劃的單純形法及其靈敏度分析。難點：目標規(guī)劃數(shù)學模型的建立、單純形解法及靈敏度分析。教學過程教學過程教學方法及手段4.1目標規(guī)劃的數(shù)學模型目標規(guī)劃數(shù)學模型的特征4.2目標規(guī)劃的圖解法兩決策變量目標規(guī)劃的圖解法。4.3目標規(guī)劃的單純形解法及靈敏度分析目標規(guī)劃的單純形法與靈敏度分析。多媒體講解實例講解2、課件4.1目標規(guī)劃的數(shù)學模型前面所講的線性規(guī)劃模型是在一種靜態(tài)、理想環(huán)境中的最優(yōu)決策行為。但現(xiàn)實決策的背景要復雜得多，某些約束條件、目標均是“軟”的。目標規(guī)劃數(shù)學模型具有下列特征：（1）對于決策目標來說，它允許一定的偏差，這直接表現(xiàn)為決策變量可以有某種偏差或；為正偏差變量，表示決策超過目標值的部分，為負偏差變量，表示決策未達到目標值的部分?？紤]到?jīng)Q策值不可能超過同時又未達到目標值，所以，（2）絕對約束和目標約束絕對約束是指必須嚴格滿足的等式約束和不等式約束，如線性規(guī)劃中的約束，不能滿足這些條件的即為非可行解。目標約束則可將右端項視為要達到的目標，但允許發(fā)生證或負的偏差，因此在這些約束中加入正、負偏差變量。在線性規(guī)劃的硬約束中加入正負偏差變量（加上負偏差變量、減去正偏差變量），將符號變?yōu)榈忍柧娃D(zhuǎn)變?yōu)槟繕思s束。（3）優(yōu)先因子（優(yōu)先等級）與權(quán)系數(shù)在現(xiàn)實的決策背景下，決策者往往具有多個目標，但這些目標是有主次輕重的不同。賦予優(yōu)先因子，規(guī)定，表示級目標比級具有絕對的優(yōu)先權(quán)，在優(yōu)先保證級目標時可不考慮級目標。權(quán)系數(shù)可區(qū)別同級目標中兩個目標的差異。（4）目標規(guī)劃的目標函數(shù)目標規(guī)劃的目標函數(shù)由各目標約束的正負偏差變量和賦予相應(yīng)的優(yōu)先因子構(gòu)造而成。當每一目標給定后，決策者的要求是盡可能地縮小偏離目標值。因此，目標規(guī)劃的目標函數(shù)只能是，其基本形式有三種：要求恰好達到目標值，即正負偏差都要求盡可能地小，此時②要求不超過目標值，即允許達不到目標值，就是正偏差要盡可能地小，即③要求超過目標值，即超過量不限，就是負偏差要盡可能地小，此時4.2目標規(guī)劃的圖解法與線性規(guī)劃相同，具有兩變量的目標規(guī)劃也可以用圖解法進行求解。具體步驟與線性規(guī)劃的圖解法相似。4.3目標規(guī)劃的單純形解法及靈敏度分析（1）目標規(guī)劃的單純形解法目標規(guī)劃的單純形解法與線性規(guī)劃的單純形解法基本相似，當然也具有一些獨特之處：①由于目標函數(shù)都市要求最小化，所以為最優(yōu)準則；②非基變量的檢驗數(shù)中含有不同等級的優(yōu)先因子，即，由于，因此，檢驗數(shù)的正、負取決于其中所含最高優(yōu)先因子的系數(shù)的正負。例略。（2）靈敏度分析目標規(guī)劃的靈敏度分析與線性規(guī)劃也很相似，但還有優(yōu)先因子的變化問題。當優(yōu)先因子發(fā)生改變時，實際上就是將最終單純形數(shù)表中各有優(yōu)先因子對應(yīng)的行向量交換位置即可，然后計算它們的檢驗數(shù)，看是否還需要進一步的處理。

第五章整數(shù)規(guī)劃1、教學計劃第6次課2學時授課章節(jié)第五章授課方式□√理論課□討論課□實驗課□習題課□其他課堂教學目的及要求掌握整數(shù)規(guī)劃的數(shù)學模型、特點以及求解方法；用匈牙利法求解指派問題。課堂教學重點及難點重點：用匈牙利法求解指派問題。難點：用匈牙利法求解指派問題。教學過程教學過程教學方法及手段5.1整數(shù)規(guī)劃問題的提出及一般求解方法整數(shù)規(guī)劃的數(shù)學模型及特點，一般求解方法簡介：分支定界法和割平面法。5.2指派問題指派問題的匈牙利法求解。多媒體講解實例講解2、課件5.1整數(shù)規(guī)劃的數(shù)學模型的提出及一般求解方法要求一部分或全部決策變量必須取整數(shù)值得規(guī)劃問題稱為整數(shù)規(guī)劃。其模型為：Max(或min)z=中部分或全部取整數(shù)s.t中部分或全部取整數(shù)若要求決策變量只能取值0或1的整數(shù)規(guī)劃稱為0-1型整數(shù)線性規(guī)劃。對于一般的整數(shù)規(guī)劃問題，可采用分支定界法和割平面法進行求解。5.2指派問題及其應(yīng)用指派問題的標準形式及數(shù)學模型在現(xiàn)實生活中，有各種性質(zhì)的指派問題。例如，有若干項工作需要分配給若干人（或部門）來完成；有若干項合同需要選擇若干個投標者來承包；有若干班級需要安排在各教室上課等等。諸如此類的問題，它們的基本要求是在滿足特定的指派要求條件下，使指派方案的總體效果最佳。由于指派問題的多樣性，有必要定義指派問題的標準形式。指派問題的標準形式（以人和事為例）是：有n個人和n件事，已知第i個人作第j件事的費用為，要求確定人和事之間的一一對應(yīng)的指派方案，是完成這n件事的總費用最少。為了建立標準指派問題的數(shù)學模型，引入個0-1變量：若指派第i人作第j件事若不指派第i人作第j事i，j=1,2,…n若指派第i人作第j件事若不指派第i人作第j事i，j=1,2,…n這樣，問題的數(shù)學模型可寫成（5.1）（5.4）（5.2）s.t（5.3）（5.4）（5.2）其中，（5.1）表示每件事必優(yōu)且只有一個人去做，（5.2）表示每個人必做且只做一件事。注：eq\o\ac(○,1)指派問題是產(chǎn)量（）、銷量（）相等，且==1，i，j=1,2,…n的運輸問題。eq\o\ac(○,2)有時也稱為第i個人完成第j件工作所需的資源數(shù)，稱之為效率系數(shù)（或價值系數(shù)）。并稱矩陣C==（5.5）為效率矩陣（或價值系數(shù)矩陣）。并稱決策變量排成的n×n矩陣X==（5.6）為決策變量矩陣。(5.6)的特征是它有n個1，其它都是0。這n個1位于不同行、不同列。每一種情況為指派問題的一個可行解。共n!個解。其總的費用z=C⊙X這里的⊙表示兩矩陣對應(yīng)元素的積，然后相加。問題是：把這n個1放到X的個位置的什么地方可使耗費的總資源最少？（解最優(yōu)）例1已知效率矩陣C=則X（1）=，X（2）=都是指派問題的最優(yōu)解例12/P-149：某商業(yè)公司計劃開辦五家新商店。為了盡早建成營業(yè)，商業(yè)公司決定由5家建筑公司分別承建。已知建筑公司Ai（i=1，2，…5）對新商店Bj（1，2，…5）的建造費用的報價（萬元）為（i，j=1,2,…5）,見表5-9。商業(yè)公司應(yīng)當對5家建筑公司怎樣分派建筑任務(wù)，才能使總的建筑費用最少？表5-9B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106解：這是一標準的指派問題。若設(shè)0-1變量i,j=1,2,…5當Ai不承建Bi,j=1,2,…5當Ai不承建Bj時當Ai承建Bj時則問題的數(shù)學模型為Minz=4+8+…+10+6s.t若看成運輸問題，且如上所述，則表5-9為商店公司B1B2B3B4B5任務(wù)A1（4）（8）（7）（15）（12）1A2（7）(9)(17)(14)(10)1A3(6)(9)(12)(8)(7)1A4(6)(7)(14)(6)(10)1A5(6)(9)(12)(10)(6)1所選的公司數(shù)111115當然，第一行的1應(yīng)放在（1，1）位置，此位置同時是第一列的費用最小。但一般情況下沒有這么好。需找一適合一般的方法。匈牙利解法原理：雖然指派問題是一類特殊的整數(shù)規(guī)劃問題，又是特殊的0-1規(guī)劃問題和特殊的運輸問題，因此，它可以用多種相應(yīng)的解法來求解。但是，這些解法都沒有充分利用指派問題的特殊性質(zhì)，有效地減少計算量。1955年，庫恩（W.W.Kuhn）提出了匈牙利法。定理1：設(shè)指派問題的效率矩陣為C=，若將該矩陣的某一行（或某一列）的各個元素都減去統(tǒng)一常數(shù)t（t可正可負），得到新的效率矩陣，則以為效率矩陣的新的指派問題與原指派問題的最優(yōu)解相同。但其最優(yōu)解比原最優(yōu)解之減少t.證明：設(shè)式（5.1）～（5.4）為原指派問題?，F(xiàn)在C矩陣的第k行個元素東減去同一常數(shù)t,記新的指派問題的目標函數(shù)為.則有==+=+=+-t=-t·1=Z-t因此有Min=min(Z-t)=minZ-t而新問題的約束方程同原指派問題。因此其最優(yōu)解比相同，而最優(yōu)解差一個常數(shù)。推論：若將指派問題的效率矩陣每一行即每一列分別減去各行及各列的最小元素，則得到新指派問題與原指派問題有相同的最優(yōu)解。證明：結(jié)論是顯然的。只要反復運用定理1便可得證。當將效率矩陣的每一行都減去各行的最小元素，將所得的矩陣的每一列在減去當前列中最小元素，則最后得到新效率矩陣中必然出現(xiàn)一些零元素。設(shè)=0，從第i行來看，它表示第i個人去干第j項工作效率（相對）最好。而從第j列來看，這個0表示第j項工作以第i人來干效率(相對)最高。定義：在效率矩陣C中，有一組在不同行不同列的零元素，稱為獨立零元素組，此時每個元素稱為獨立零元素。例2:已知C=則｛=0，=0，=0，=0｝是一個獨立零元素組，=0，=0，=0，=0分別稱為獨立零元素。｛=0，=0，=0，=0｝也是一個獨立零元素組，而｛=0，=0，=0，=0｝就不是一個獨立零元素組，因為=0與=0這兩個零元素位于同一列中。根據(jù)以上對效率矩陣中零元素的分析，對效率矩陣C中出現(xiàn)的的獨立零元素組中零元素所處的位置，在決策變量矩陣中令相應(yīng)的=1，其余的=0。就可找到指派問題的一個最優(yōu)解。就上例中X（1）=，就是一個最優(yōu)解。同理X（2）=也是一個最優(yōu)解。但是在有的問題中發(fā)現(xiàn)效率矩陣C中獨立零元素的個數(shù)不夠n個，這樣就無法求出最優(yōu)指派方案，需作進一步的分析。首先給出下述定理。定理2效率矩陣C中獨立零元素的最多個數(shù)等于能覆蓋所有零元素的最少直線數(shù)。我們不證它，說一下意思：例3：已知矩陣C1=，C2=，C3=分別用最少直線去覆蓋各自矩陣中的零元素：C1=，C2=，C3=可見，C1最少需要4條線，C2最少需要4條線，C3最少需要5條線，方能劃掉矩陣中所有的零。即它們獨立零元素組中零元素最多分別為4，4，5。匈牙利法求解步驟：我們以例題來說明指派問題如何求解：例4給定效率矩陣C=求解該指派問題。解：?。┳儞Q效率矩陣，將各行各列都減去當前各行、各列中最小元素。minmin列變換行變換7942C==列變換行變換7942MMin0042這樣得到的新矩陣中，每行每列都必然出現(xiàn)零元素。ⅱ）用圈0法求出新矩陣中獨立零元素。（1）進行行檢驗對進行逐行檢驗，對每行只有一個未標記的零元素時，用○記號將該零元素圈起。然后將被圈起的零元素所在的列的其它未標記的零元素用記號×劃去。如中第2行、第3行都只有一個未標記的零元素，用○分別將它們?nèi)ζ?。然后用×劃去?列其它未被標記的零元素（第2列沒有），見=在第i行只有一個零元素=0時，表示第i人干第j件工作效率最好。因此優(yōu)先指派第i人干第j項工作，而劃去第j列其它未標記的零元素，表示第j項工作不再指派其它人去干（即使其它人干該項工作也相對有最好的效率）。重復行檢驗，直到每一行都沒有未被標記的零元素或至少有兩個未被標記的零元素時為止。本題中第1行此時也只有1個未被標記的零元素。因此圈起中第1行第4列的零元素，然后用×劃去第4列中未被標記的零元素。這是第4行也只有一個未被標記的零元素，再用○圈起，見=（2）進行列檢驗與進行行檢驗相似，對進行了行檢驗的矩陣逐列進行檢驗，對每列只有一個未被標記的零元素，用記號○將該元素圈起，然后技改元素所在行的其他未被標記的零元素打×。重復上述列檢驗，直到每一列都沒有未被標記的零元素或有兩個未被標記的零元素為止。這時可能出現(xiàn)以下三種情況：eq\o\ac(○,1)每一行均有圈0出現(xiàn)，圈0的個數(shù)m恰好等于n,即m=n.eq\o\ac(○,2)存在未標記的零元素，但他們所在的行和列中，為標記過的零元素均至少有兩個。eq\o\ac(○,3)不存在未被標記過的零元素，當圈0的個數(shù)m<n.ⅲ)進行試指派若情況eq\o\ac(○,1)出現(xiàn)，則可進行試指派：令圈0為止的決策變量取值為1，其他決策變量取值均為零，得到一個最優(yōu)指派方案，停止計算。上例中得到后，出現(xiàn)了情況eq\o\ac(○,1)，可令=1，=1，=1，=1，其余=0。即為最優(yōu)指派。若情況eq\o\ac(○,2)出現(xiàn)，則在對每行、每列的其它未被標記的零元素任選一個，加上標記○，即圈上該零元素。然后給同行、同列的其它未被標記的零元素加標記×。然后再進行行、列檢驗，可能出現(xiàn)情況eq\o\ac(○,1)或eq\o\ac(○,3)，出現(xiàn)情況eq\o\ac(○,1)則由上述得到一最優(yōu)指派，停止計算。若情況eq\o\ac(○,3)出現(xiàn)，則要轉(zhuǎn)入下一步。ⅳ）：做最少直線覆蓋當前所有零元素。我們還以例12來說明過程：已知例12指派問題的系數(shù)矩陣為：先對各行元素分別減去本行的最小元素，然后對各列也如此，即列變換行變換C=列變換行變換此時，中各行各列都已出現(xiàn)零元素。為了確定中的獨立零元素，對加圈，即=由于只有4個獨立零元素，少于系數(shù)矩陣階數(shù)n=5,不能進行指派，為了增加獨立零元素的個數(shù)，需要對矩陣作進一步的變換，變換步驟如下：（1）對中所有不含圈0元素的行打√，如第3行。（2）對打√的行中，所有零元素所在的列打√，如第1列。（3）對所有打√列中圈0元素所在行打√，如第2行。（4）重復上述（2），（3）步，直到不能進一步打√為止。（5）對未打√的每一行劃一直線，如第1，3，5行。對已打√的每一列劃一縱線，如第1列，既得到覆蓋當前0元素的最少直線數(shù)。見。==Ⅴ）：對矩陣作進一步變換，以增加0元素。在未被直線覆蓋過的元素中找最小元素，將打√行的各元素減去這個最小元素，將打√裂的各元素加上這個最小元素（以避免打√行中出現(xiàn)負元素），這樣就增加了零元素的個數(shù)。如中未被直線覆蓋過的元素中，最小元素為==1，對打√的第2，3行各元素都減去2，對打√的第1列各元素都加上1，得到矩陣。=Ⅵ）：回到步驟Ⅱ），對已增加了零元素的矩陣，再用圈0法找出獨立零元素組。=中已有5個獨立零元素，故可確定指派問題的最優(yōu)方案。本例的最優(yōu)解為承建X*=承建也就是說，最優(yōu)指派方案是：讓A1B3A2B2A3B1A4B4A5B5這樣按排能使總的建造費最少，為z=7＋9＋6＋6＋6=34（萬元）一般的指派問題在實際應(yīng)用中，常會遇到非標準形式，解決的思路是：先化成標準形式，然后再用匈牙利法求解。最大化的指派問題其一般形式為s.t處理辦法：設(shè)最大化的指派問題的系數(shù)矩陣為C=，m=max｛｝,令B==，則以B為系數(shù)矩陣的最小化指派問題和以C為系數(shù)矩陣的原最大化指派問題有相同的最優(yōu)解。例5：某工廠有4名工人A1，A2，A3，A4，分別操作4臺車床B1，B2，B3，B4。每小時單產(chǎn)量如下表，求產(chǎn)值最大的分配方案。車床工人B1B2B3B4A1A2A3A410987345621124356解：C==，m=max｛10,9,8,7,…5,6｝=10,B=====中的◎數(shù)=n=4,所以X=（5.7）即為最優(yōu)解。從而產(chǎn)值最大的分配方案也為（5.7），最大產(chǎn)值為Z=10＋6＋1＋5=22人數(shù)和事數(shù)不等的指派問題。eq\o\ac(○,1)若人數(shù)<事數(shù)，添一些虛擬的“人”，此時這些虛擬的“人”做各件事的費用系數(shù)取為0，理解為這些費用實際上不會發(fā)生。eq\o\ac(○,2)若人數(shù)>事數(shù)，添一些虛擬的“事”，此時這些虛擬的“事”被各個人做的費用系數(shù)同樣也取為0。例6：現(xiàn)有4個人，5件工作。每人做每件工作所耗時間如下表：工作工人B1B2B3B4B5A11011428A2711101412A35691214A4131511107問指派那個人去完成哪項工作，可是總消耗最??？解：添加虛擬人A5，構(gòu)造標準耗時陣：行變換C==行變換所圈0數(shù)=4<5=n,下找最少覆蓋0的直線。=從未劃去的元素中找最小者：｛4，3，7，5，1，4，7，9｝=1。未劃去的行減去此最小者1，劃去的列加上次最小者1，得。=◎個數(shù)=n,從而的一最優(yōu)指派：=從而最少耗時為z=2＋7＋6＋7=223.一個人可做幾件事的指派問題。若某人可作幾件事，則可將該人化作相同的幾個“人”來接受指派。這幾個“人”做同一件事的費用系數(shù)當然一樣。例6：對例12的指派問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司A4和A5，讓技術(shù)力量較強的建筑公司A1、A2、A3來承建。根據(jù)實際情況，可以允許每家建筑公司承建一家或兩家商店。求使總費用最少的指派方案。B1B1B2B3B4B5A1AA1A2A3B1B2B1B2B3B4B5上面的系數(shù)矩陣有6行5列，為了使“人”和“事”的數(shù)目相同，引入一件虛擬事，使之成為標準的指派問題，其系數(shù)矩陣為：B1B1B2B3B4B5B6列變換C=列變換的◎數(shù)=5<6=n,下找0元素的最少直線覆蓋。√-1√-1==√-1√-1從而得一最優(yōu)指派：B4B5A3B2B6=ψψA2B1B3A1承建B4B5A3B2B6=ψψA2B1B3A1承建商店公司總費用為z=7＋4＋9＋7＋8=35(萬元)4．某事不能由某人去做的指派問題某事不能由某人去做，可將此人做此時的費用取作足夠大的M。例7：分配甲、乙、丙、丁四個人去完成A、B、C、D、E五項任務(wù)，每人完成各項任務(wù)的時間如下表。由于任務(wù)重，人數(shù)少，考慮：a).任務(wù)E必須完成，其它4項任務(wù)可選3項完成。但甲不能做A項工作。b)其中有一人完成兩項，其他人每人完成一項。試分別確定最優(yōu)分配方案，使完成任務(wù)的總時間最少。任務(wù)人ABCDE甲乙丙丁2931423738262033272840322442362345解：這是一人數(shù)與工作不等的指派問題，若用匈牙利法求解，需作一下處理。a)由于任務(wù)數(shù)大于人數(shù)，所以需要有一個虛擬的人，設(shè)為戊。因為工作E必須完成，故設(shè)戊完成E的時間為M（M為非常大的數(shù)），即戊不能做工作E，其余的假想時間為0，建立的效率矩陣表如下：任務(wù)人ABCDE甲乙丙丁戊M293142373938262033342728403224423623450000M用匈牙利法求解過程如下：列變換行變換C=列變換行變換由于◎數(shù)=4<5=階數(shù)，下找最少覆蓋0的直線√-1√-1=√-1√-1m=｛19,18.6.13,1,19,13,22｝=1,第2、4行減去1，第4列加上1得：A丁E丙乙B甲D=從而得最優(yōu)指派：A丁E丙乙B甲D最少的耗時數(shù)z=29＋20＋32＋24=105.b)思路：方案1：甲，eq\o\ac(○,甲)，乙，丙，丁。方案2：甲，乙，eq\o\ac(○,乙)，丙，丁。方案3：甲，乙，丙，eq\o\ac(○,丙)，丁。方案4：甲，乙，丙，丁，eq\o\ac(○,丁)。方案5：甲，eq\o\ac(○,甲)，乙，eq\o\ac(○,乙)，丙，eq\o\ac(○,丙)，丁，eq\o\ac(○,丁)。此為人；而工作：A，B，C，D，E，虛擬工作：F，G，H。這些思路都比較煩，請看下面的思路：設(shè)有虛擬人戊，它集五人優(yōu)勢為一身。即戊的費用是每人的最低。戊所做的工作即為此項工作的費用最低者的工作。任務(wù)人ABCDE甲乙丙丁戊25293142373938262033342728403224423623452427262032以下用匈牙利法求解：列變換行變換C=列變換行變換=對加圈確定獨立0元素，◎個數(shù)=3<5=n,作0元素的最少直線覆蓋：√√√=√√√在未劃去的數(shù)中選最小者1，未劃取得行都減去1，劃去的列都加上1得：=再圈0且試指派：◎個數(shù)=3<5，再作0元素的最少直線覆蓋。從未劃取的元素中找最小者4，未劃取得行都減去這個4，劃去的列都加上這個4，得：BEDA丙丁乙甲=再圈0試指派，結(jié)果為：BEDA丙丁乙甲C戊C戊其中戊是虛擬人，不能真作，它作C工作是借乙（此列最小時數(shù)26是C所創(chuàng)業(yè)績）優(yōu)勢，應(yīng)由C來作。即C做兩件工作：D，C。

第八章動態(tài)規(guī)劃的基本方法1、教學計劃第7次課2學時授課章節(jié)第五章授課方式□√理論課□討論課□實驗課□習題課□其他課堂教學目的及要求了解動態(tài)規(guī)劃模型的基本概念，理解無后效性，掌握最短路問題的求解方法。課堂教學重點及難點重點：動態(tài)規(guī)劃模型的基本概念和最短路問題。難點：最短路問題。教學過程教學過程教學方法及手段8.1動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念。8.2最短路問題無后效性與最短路問題的求解。多媒體講解實例講解2、課件8.1動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃（DynamicProgramming）是20世紀50年代由美國數(shù)學家貝爾曼（RichardBellman）及他的學生們一同建立和發(fā)展起來的一種解多階段決策問題的優(yōu)化方法。所謂多階段決策問題是指一類活動過程。它可按時間或空間把問題分為若干個相互聯(lián)系的階段。在每一階段都要作出選擇（決策），這個決策不僅僅決定這一階段的效益，而且決定下一階段的初始狀態(tài)，從而決定整個過程的走向（從而稱為動態(tài)規(guī)劃）。每當一階段的決策一一確定之后，就得到一個決策序列，稱為策略。所謂多階段決策問題就是求一個策略，使各個階段的效益總和達到最優(yōu)。概念：（1）階段與階段變量：先把問題從中間站B，C，D，E用空間位置分成5個階段，階段用階段變量k來描述，k=1,表示第一階段，k=2表示第二階段，…（2）狀態(tài)與狀態(tài)變量：每一階段的左端點（初始條件）集合稱為本階段的狀態(tài)（即開始的客觀條件，或稱階段初態(tài)）。如第三階段有四個狀態(tài)S3=｛C1,C2，C3，C4｝,第四階段有三個狀態(tài)S4=｛D1,D2,D3｝,…描述過程狀態(tài)的變量稱為狀態(tài)變量：用小寫s1,s2,s3…表示第一，第二，第三…階段的狀態(tài)變量。當處在狀態(tài)C2時，我們可記s3=C2正像離散型R.V“X=2”代表一事件一樣。(3)決策與決策變量：如當處于C2狀態(tài)時，下一步怎么走？如何選擇路線？即如何決策。是走向D1，還是走向D2？當過程處于某一階段的某一狀態(tài)時，可以作出不同的決策（或選擇），從而確定下一階段的狀態(tài)，這種決定（或選擇）叫決策。如選擇D2，記u3（C2）=D2說，當處于C2狀態(tài)時，下一步的決策為D2。其中表示第k階段當狀態(tài)處于時的決策變量。一般地，用表示第k階段從狀態(tài)出發(fā)的允許決策集合。如=｛D1，D2｝顯然，∈。（4）策略與最優(yōu)策略：每一階段產(chǎn)生一個決策，5個階段的決策就構(gòu)成一個決策序列：，，，，稱為一策略。所謂策略是指按一定的順序排列的決策組成的集合，也稱決策序列。這里的最短路徑成為最優(yōu)策略。動態(tài)規(guī)劃就是在允許策略集中選最優(yōu)策略。（5）狀態(tài)轉(zhuǎn)移方程：是描述由第k階段到第k+1階段狀態(tài)轉(zhuǎn)移規(guī)律的關(guān)系式。=上例中狀態(tài)轉(zhuǎn)移方程為：=（6）指標函數(shù)與最優(yōu)指標函數(shù)：用于衡量所選定策略優(yōu)劣的數(shù)量指標稱為指標函數(shù)。相當于動態(tài)的目標函數(shù)，最后一個階段的目標函數(shù)就是總的目標函數(shù)。它分階段指標函數(shù)和過程指標函數(shù)。階段指標函數(shù)是指第k階段，從狀態(tài)出發(fā)，采用決策時的效益，用表示。最優(yōu)指標函數(shù)是指從第k階段狀態(tài)采用最優(yōu)策略到過程終止時的最佳效益值，用表示。8.2最短路問題首先應(yīng)該指出：下面研究的解決多階段的決策問題的最優(yōu)化的稱之為動態(tài)規(guī)劃的數(shù)學方法，僅僅是一種解決問題的思路，而不是一種算法。這一點與線性規(guī)劃不同。線性規(guī)劃是一種算法。下面從一典型的例子去說明動態(tài)規(guī)劃的基本思想與原理：某地要從A向F地鋪設(shè)一條輸油管道，各點間連線上的數(shù)字表示距離。問應(yīng)選擇什么路線，可是總距離最短？5C5C1228D18D1433B433B154E1C254E1C26456E2C4C3F6456E2C4C3FA3D23D2328532851471473B2D33B2D3878744第一階段第二階段第三階段第四階段第五階段逆序遞推法：倒退著從F向A走，每倒退一步，思想上問自己：“從現(xiàn)在出發(fā)，退向何處？到F的距離最短？”我們分5步來解決問題：k=5時求=？此時狀態(tài)集S5=｛E1，E2｝，故分情況討論，先說=？若最佳路徑從A出發(fā)通過E1的話，由E1到終點F的最短距離為=5同理，=3。（只有唯一的選擇）故最優(yōu)決策為：=F，=Fk=2時求=？由于S4=｛D1,D2,D3｝，下分四種情況進行討論：=min=min=7,=E1.=min=min=5,=E2.=min=min=5,=E1.(3)k=3時S3=｛C1,C2，C3，C4｝,=min=min=12,=D1.同理，=10，=D2.=8，=D2.=9，=D3.（4）k=4時S2=｛B1,B2｝=min=min=13,=C2.同理，=15，=C3.（5）k=1時，S1=｛A｝=min=min=17,=B1.再按計算順序的反推可得最優(yōu)策略：=B1.=C2.=D2.=E2.=F.從而得最優(yōu)路徑：A—B1—C2—D2—E2—F最短距離為=17。由上面的過程可以看出，在求解的各個階段利用了第k段和第k+1段的如下關(guān)系：這種遞推關(guān)系稱為動態(tài)規(guī)劃的基本方程。（7.3b）式稱為邊界條件。逆向標號法每退到一站，看終點F，找最短路徑及最短路徑的距離，標號。畫路徑。（12）（7）C12（12）（7）C125（13）（13）（10）8D1（10）8D13（4）B14C24E153（4）B14C24E153（17）（5）（17）（5）（8）5646E2C4C3FA（8）5646E2C4C3FA23D223D2（15）1（3）385（15）1（3）385（5）47（5）47（9）3B2D3（9）3B2D3878744此時的（？）？=最優(yōu)指標函數(shù)值f.得最優(yōu)路徑：A—B1—C2—D2—E2—F總距離為17.順序遞推法：此法類似于逆序遞推法。從起點A向終點F倒退。k=1時，=0，此為初始條件。退向允許決策集S1=｛B1,B2｝此時退向B1時看起點A，最短距離為=4，此時路徑（或最優(yōu)決策）是唯一的：=A；記，同理，k=2時，直接用遞推式：k=3時。類似的，同理，，最后逆推最優(yōu)策略：A—B1—C2—D2—E2—F。與前相同。全部計算情況如圖7-3（11）C152（6）（4）（11）C152（6）（4）（7）8D1（7）8D13（14）B1C2E144353（14）B1C2E14435（12）（12）（10）（17）5646E2C4C3FA（10）（17）5646E2C4C3FA23D223D2（14）（5）1385（14）（5）1385（14）47（14）47（12）3B2D3（12）3B2D3878744遞推關(guān)系式：此與逆序法無本質(zhì)的區(qū)別。一般來說，當初始狀態(tài)給定時，用逆序解法，當終止狀態(tài)給定時，用順序解法。若既給定了初始狀態(tài)又給定了終止狀態(tài)，則兩種方法均可使用。如習題7.2/P237，終點有三個，用逆序解法較好。8.3資源分配問題一維資源分配問題例：公司計劃在三個不同的地區(qū)設(shè)置4個銷售店，根據(jù)市場預測，在不同的地區(qū)設(shè)置不同數(shù)量的銷售店，每月可獲得的利潤如下表所示。試問應(yīng)如何設(shè)置，才能使每月所獲得的總利潤最大？其值是多少？（15分）地地區(qū)利潤店數(shù)12300001161210225171433021164322217設(shè)：sk表示在第k地區(qū)至第n地區(qū)設(shè)置的銷售店數(shù)量；xk表示在第k地區(qū)設(shè)置銷售店數(shù)量；Pk(xk)表示在第k地區(qū)設(shè)置xk個銷售店數(shù)量所得的利潤；fk(sk)表示在第k地區(qū)至第n地區(qū)設(shè)置sk個銷售店數(shù)量所得的最大利潤總值。第一階段：x3x3s3012340000110101214142316163417174第二階段：x2x2s201234000010+1012+012120+1412+101722130+1612+1417+102127240+1712+1617+1421+1022312，3第三階段：x1x1s10123440+3116+2725+2230+1232+0472因此，最優(yōu)方案為、、。最大利潤為47。

第十章圖與網(wǎng)絡(luò)優(yōu)化1、教學計劃第8次課2學時授課章節(jié)第十章第1節(jié)和第2節(jié)授課方式□√理論課□討論課□實驗課□習題課□其他課堂教學目的及要求理解圖、樹的基本概念，掌握最小支撐樹的求解方法。。課堂教學重點及難點重點：圖、樹的基本概念，最小支撐樹的求解。難點：最小支撐樹的求解方法——破圈法和避圈法。教學過程教學過程教學方法及手段8.1動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃的基本概念。8.2最短路問題樹的基本概念與性質(zhì)，最小支撐樹的求解方法破圈法和避圈法。多媒體講解實例講解第9次課2學時授課章節(jié)第十章第3節(jié)授課方式□√理論課□討論課□實驗課□習題課□其他課堂教學目的及要求了解路的概念，掌握最短路問題的求解方法。課堂教學重點及難點重點：最短路問題的Dijkstra算法。難點：最短路問題的Dijkstra算法。教學過程教學過程教學方法及手段10.3最短路問題路的基本概念，最短路問題的Dijkstra算法思想及步驟。多媒體講解實例講解第10次課2學時授課章節(jié)第五章第4節(jié)授課方式□√理論課□討論課□實驗課□習題課□其他課堂教學目的及要求了解網(wǎng)絡(luò)、流、可行流、增廣鏈、截集與截量的基本概念，掌握最大流問題的求解方法。課堂教學重點及難點重點：網(wǎng)絡(luò)、流、可行流、增廣鏈、截集與截量的基本概念，最大流問題的求解。難點：增廣鏈的尋找方法，最大流的標號法。教學過程教學過程教學方法及手段10.4最大流問題網(wǎng)絡(luò)、流、可行流、增廣鏈、截集與截量的基本概念，增廣鏈的尋找方法，最大流的標號法。多媒體講解實例講解第11次課2學時授課章節(jié)第五章第5節(jié)授課方式□√理論課□討論課□實驗課□習題課□其他課堂教學目的及要求了解最小費用最大流的基本概念，掌握最小費用最大流問題的求解方法。課堂教學重點及難點重點：最小費用最大流的基本概念，最小費用最大流的求解方法。難點：構(gòu)造賦權(quán)有向圖。教學過程教學過程教學方法及手段10.5最小費用最大流問題最小費用最大流的基本概念，最小費用最大流的求解方法。多媒體講解實例講解第12次課2學時授課章節(jié)第五章第6節(jié)授課方式□√理論課□討論課□實驗課□習題課□其他課堂教學目的及要求了解中國郵遞員問題的基本概念入歐拉鏈、歐拉圈，掌握中國郵遞員問題的求解方法。課堂教學重點及難點重點：動態(tài)規(guī)劃模型的基本概念和最短路問題。難點：最短路問題。教學過程教學過程教學方法及手段10.5中國郵遞員問題一筆畫與歐拉鏈、歐拉圈概念，中國郵遞員問題的求解思路和步驟。多媒體講解實例講解2、課件10.1圖的基本概念圖的定義：圖是在紙上用點和線畫出反映對象之間關(guān)系的示意圖。圖中點的相對位置如何、長短曲直并不重要。例1圖10-2（P252）是我國北京、上海等十個城市間的鐵路交通圖。這里的點代表城市，點與點的連線代表兩個城市間的鐵路線。例2P252種圖10-3與圖10-5沒有本質(zhì)的區(qū)別。關(guān)系的種類及其表示：（1）對稱性的關(guān)系甲與乙有這種關(guān)系，同時乙與甲也有這種關(guān)系。如同學關(guān)系（2）非對稱的關(guān)系甲與乙有這種關(guān)系，乙與甲未必有這種關(guān)系。如甲認識乙，乙未必認識甲；一場比賽中，球隊A勝球隊B，球隊B不能勝球隊A。圖的構(gòu)造：一個圖是由一些點及點之間的連線（帶箭頭或不帶箭頭）所組成。不帶箭頭的連線稱為邊，帶箭頭的連線稱為弧。如果一個圖是由點及邊組成的，則稱為無向圖，記為。、分別為圖的點集合和邊集合，一條連結(jié)點的邊記為。如果一個圖是由點及弧所構(gòu)成的，則稱為有向圖，記為。、分別為圖的點集合和弧集合，一條從指向的弧記為。若，稱是的端點，是相鄰的，是及的關(guān)連邊。若圖重某個邊的兩個端點相同，則稱是環(huán)；若兩個點之間有多于一條的邊，則稱這些邊為多重邊；一個無環(huán)、無多重邊的圖稱為簡單圖；無環(huán)但有多重邊的圖成為多重圖。以點為端點的邊的個數(shù)稱為的次，記為或。環(huán)在計算次時算兩次。次數(shù)為奇數(shù)的點稱為奇點；次數(shù)為偶數(shù)的點稱為偶點；次數(shù)為1的點稱為懸掛點，它的關(guān)連邊稱為懸掛邊，次為零的點為孤立點。定理1：圖中，所有點的次數(shù)之和是邊數(shù)的兩倍。定理2：任何一個圖中，奇點的個數(shù)必為偶數(shù)。圖中，一個點、邊交錯序列，如果滿足（），則稱為一條聯(lián)結(jié)和的鏈，記為，稱點為鏈的中間點。鏈中，若，則稱為一個圈，記為；若鏈中所有的點都是不同的，則稱為初等鏈；若圈中的點都是不同的，則稱之為初等圈；以后所涉及到的鏈（圈），除非特別交代，均指初等鏈（圈）。若鏈（圈）中含的邊均不相同，則稱為簡單圈。圖中，如任何兩點之間至少有一條鏈，則稱是連通圖；否則為不連通圖，不連通的每個連通的部分稱為其一個連通分圖。給定圖，如果圖，有、，則稱是的一個支撐子圖。給定有向圖，去掉其所有弧上的箭頭，就得到一個無向圖，該圖為的基礎(chǔ)圖，記為。給定中的一條弧，稱為的始點，為的終點。設(shè)點弧交錯序列在基礎(chǔ)圖中所對應(yīng)的點邊序列是一條鏈，則稱該點弧交錯序列是的一條鏈；而且如果滿足（），則稱為從到的一條路；如果第一點和最后一點相同，則稱之為回路。10.2樹的基本概念與性質(zhì)一、樹及其性質(zhì)定義：一個無圈的連通圖稱為樹。定理3：設(shè)圖是一個樹，（點數(shù)），則中至少有兩個懸掛點。定理4：圖是一個樹的充分必要條件是不含圈，且恰有條邊。定理5：圖是一個樹的充分必要條件是是連通圖，且，（邊數(shù)）。定理6：圖是一個樹的充分必要條件是任意兩頂點之間恰有一條鏈。推論1：從一個樹中去掉任意一條邊，則余下的圖是不連通的，因此，在點集合相同的所有圖中，樹是含邊數(shù)最少的連通圖。推論2：在樹中不相鄰的兩點間添一條邊，則恰好得到一個圈。二、圖的支撐樹定義：設(shè)圖是圖的一個支撐子圖，如果圖恰好又是一棵樹，則稱是的一個支撐樹。定理7：圖有支撐樹的充分必要條件是圖是連通的。破圈法：在任何一個圖中，任取一個圈，從中能夠去掉一邊，然后重復此過程，直到不含圈為止，即得到一個支撐樹。例6避圈法：在任何一個圖中，任取一條邊，找一條與該邊不構(gòu)成圈的邊，再尋找一條與該兩條邊不構(gòu)成圈的邊，繼續(xù)此過程，直到不能進行為止。例7三、最小支撐樹定義3：給圖上所有的邊都賦予一個數(shù)，則稱這樣的圖為賦權(quán)圖，為邊上的權(quán)。這里的權(quán)是指與邊有關(guān)的數(shù)量指標，根據(jù)實際問題可表示距離，時間，費用等等。定義4：如果圖是圖的一個支撐樹，稱中所有邊的權(quán)之和為支撐樹的權(quán)，如果支撐樹的權(quán)是的所有支撐樹的權(quán)中最小者，則稱是的最小支撐樹。最小支撐樹的求解方法：避圈法首先選一條最小權(quán)的邊，然后每一步總從與已選邊不構(gòu)成圈的那些未選邊中選擇一條權(quán)最小的邊（如果有兩條或兩條以上的邊都是權(quán)最小的邊，任選其中一條），重復此步驟直到不能進行為止。（2）破圈法任取一個圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，任意去掉一條），在余下的圖中重復該步驟直到不能進行為止。例：求下圖的最小支撐樹。避圈法（2）破圈法10.3最短路問題問題的引出：存在一個賦權(quán)有向圖，對其中每一個弧，相應(yīng)地有權(quán)；給定中的兩個頂點、，設(shè)是中從到的一條路，定義路的權(quán)是中所有弧的權(quán)之和，記為。最短路問題就是要在所有從到的路中，尋找一條權(quán)最小的路，使稱是從到的最短路，也成為從到的距離。即，最短路問題的本質(zhì)是在在一個賦權(quán)有向圖中，求出從給定一個點到任一點的最短路。最短路問題的算法：（1）權(quán)的情形：Dijkstra算法Dijkstra（1930-2002），二十世紀最偉大的計算機科學家之一，提出編程的“goto有害論，信號量和PV原語，解決了“哲學家聚餐”問題，Dijkstra最短路徑算法的創(chuàng)造者，第一個Algol60編譯器的設(shè)計者和實現(xiàn)者，THE操作系統(tǒng)的設(shè)計者和開發(fā)者?；舅枷耄簭某跏键c出發(fā)，與每個點對應(yīng)，記錄下一個數(shù)（稱為這個點的標號），它或者表示從到該點的最短路的權(quán)（稱為P標號），或者是從到該點的最短路的權(quán)的上界（稱為T標號），方法的每一步是去修改T標號，并且把某一個具有T標號的點變?yōu)镻標號，使中P標號的頂點數(shù)多一個，如此，至多經(jīng)過步，就可求出從到各點的最短路。步驟：開始（），令，，，對于每一個，令，，令。①如果，算法終止，此時，對于每個，；否則轉(zhuǎn)入②；②考察每個使且的點，如果，則把修改為，把修改為，否則轉(zhuǎn)入③；③令。如果，則把的標號變?yōu)闃颂?，即，，令，，把換成，轉(zhuǎn)入①；否則終止，此時對每一個，，而對每一個，。例：求下圖中到各頂點的最短路。解：，，，；，，；令；考察所有從出發(fā)指向其余點的?。ń?jīng)1步可達到的不屬于點：，，）。<，所以，將修改為6，；同樣的方法可得、，、。在所有的標號中，最小，所以，，得，。，考察從、出發(fā)指向其余點的弧（經(jīng)1步可以達到的不屬于點：，，）?？傻?、，、，、。所有標號中，最小，得，，。，考察從、、出發(fā)指向其余點的?。ń?jīng)1步可以達到的不屬于點：，）。得、，、。所有標號中，最小，因此，，，。，考察從、、、出發(fā)指向其余點的?。ń?jīng)1步可以達到的不屬于點：，）。得、，、。所有標號中，最小，因此，，，。，考察從、、、、出發(fā)指向其余點的?。ń?jīng)1步可以達到的不屬于點：，，）。得、，、，、。所有標號中，最小，因此，，，。，考察從、、、、、出發(fā)指向其余點的?。ń?jīng)1步可以達到的不屬于點：，）。得、，、。所有標號中，最小，因此，，，。，考察從、、、、、、出發(fā)指向其余點的?。ń?jīng)1步可以達到的不屬于點：）。得、，，。，只剩余，沒有任何指向的弧，因此，，。計算完畢。綜合計算結(jié)果：，，，，，，，，。，，，，，，，，。若是無向圖（如P264，例11），則將其任何一邊視為兩條具有相同權(quán)的弧和，然后把Dijkstra方法的②改為“考察每個使且的點”，采用同樣的思路可求得無向圖中某一點到其余任何一點的最短路（也叫最短鏈）。（2）含負權(quán)的情形Dijkstra算法只適用于的情形，在含負權(quán)的情況下，算法實效。如下圖，根據(jù)Dijkstra算法，得到的最短路的權(quán)是1，但事實上，從經(jīng)由到的權(quán)為-1。引理：如果從到的最短路是從出發(fā)，經(jīng)某一條路到點再沿到，則，從到的這條路必然是從到的最短路，可記為。從到的最短路必滿足如下方程：為求得該方程的解，可用如下地推公式：，（）對，，若進行到某一步，對所有，有則，（）為到各點最短路的權(quán)。例：求下圖中從到各點的最短路。點0-1-230000602-1-5-5-5-30-51-2-2-2-2023-7-7-7-101-3-31017-1-1-1-105-5-5-3-5066鏈的確定：（1）采用類似于Dijkstra的方法，在迭代過程中，如果則，。（2）反向追蹤法：求出最短路之后，進行反向追蹤。例如，已知，尋找點，使，記錄下，再考察，尋找一點，使，記錄下，依此類推，直到為止，從而求出到的最短路。10.4網(wǎng)絡(luò)最大流問題一、基本概念與基本定理1網(wǎng)絡(luò)與流給定有向圖，在中指定了一點稱為發(fā)點（記為），另一點稱為受點（記為），其余點叫做中間點；對于每一個弧，對應(yīng)有一個（或記為），稱為弧的容量。稱上述有向圖為一個網(wǎng)絡(luò)，記為網(wǎng)絡(luò)上的流，是指定義在弧集合上的一個函數(shù)，并稱為弧上的流量（也可記為）。2可行流與最大流通過運輸網(wǎng)絡(luò)的實際問題可知：一，每個弧上的流量不能超過該弧的最大通過能力（弧的容量）；二，中間點的凈流量為零，即，流入量等于流出量，發(fā)點的凈流出量等于收點的凈流入量。因此，定義滿足如下條件的流稱為可行流：（1）容量限制：對于每一弧，有（2）平衡條件：對于中間點：流出量等于流入量，對于每個，有對于發(fā)點，有對于收點，有稱為這個可行流的流量?？尚辛骺偸谴嬖诘摹Ｗ畲罅鲉栴}就是求一個流使其流量達到最大，且滿足：，3增廣鏈給定一個可行流，網(wǎng)絡(luò)中的弧稱為飽和弧，的弧稱為非飽和弧，的弧稱為零流弧，的弧稱為非零流弧。設(shè)是網(wǎng)絡(luò)中聯(lián)結(jié)發(fā)點和收點的一條鏈，并定義鏈的方向是從到，則鏈上的弧分為兩類：方向與鏈的方向一致的弧稱為前向弧，前向弧的全體記為；方向與鏈的方向相反的弧稱為后向弧，后向弧的全體記為。定義：設(shè)是一個可行流，是從到的一條鏈，若滿足如下條件，則稱其為（關(guān)于可行流）的增廣鏈。條件一，在弧上，，即中每一條弧是非飽和弧。條件二，在弧上，，即中每一條弧是非零流弧。4截集與截量定義給網(wǎng)絡(luò)，若點集被剖分為兩個非空集合和，使，，則把弧集（，）稱為是分離和的截集。定義給一截集（，），把截集（，）所有弧的容量之和稱為這個截集的容量，簡稱為截量，記為，即性質(zhì)：任何一個可行流的流量都不會超過任何一個截集的容量，即，，當且僅當最大、最小時，二者取等號，定理可行流是最大流，當且僅當不存在關(guān)于的增廣鏈。最大流量最小截量定理：任一個網(wǎng)絡(luò)中，從到的最大流的流量等于分離和的最小截集的容量。尋求最大流的標號法：基本：思想根據(jù)上述定理，利用標號法進行求解：利用給頂點標號的方法來定義，在標號的過程中，有標號的頂點表示屬于的點，無標號的頂點表示不屬于的點；一旦有了標號，表示找到了一條增廣鏈；如果標號進行不下去，而尚未標號，則說明不存在增廣鏈，而且同時也得到一個截量最小的截集。具體步驟如下：（1）標號過程在整個過程中，網(wǎng)絡(luò)中的點或者是標號點（已檢查或未檢查），或者是未標號點。每個標號點的標號漢兩部分：第一個標號表示它的標號從哪一點得到的，目的是為了找出增廣鏈；第二個標號是為了確定增廣鏈的調(diào)整量的。首先，總給標上，此時，為標號而未檢查的點，其余都是標號點。一般情況下，取一個標號而未檢查過的點，對一切為標號的點：在弧上，，則給標號，；在弧上，，則給標號，。此時，成為標號、已檢查的點。重復上述過程，一旦被標上號，標明得到一條從到的的增廣鏈，轉(zhuǎn)入調(diào)整過程。（2）調(diào)整過程首先按及其他點的第一個標號，利用反向追蹤法找出增廣鏈。調(diào)整量是標號點的第二個標號，為該增廣鏈中各點所能調(diào)整的量中最小者，也就是，因為，根據(jù)標號的過程必有最小。令，去掉所有的標號，對新的可行流進行新的標號過程。例如：利用標號法求下圖所示網(wǎng)絡(luò)的最大流?；∨缘臄?shù)是。（1）標號：①首先，給標上②檢查，在弧上，，不滿足標號條件?；∩?，，則的標號為，③檢查，在弧上，，不滿足標號條件?；∩?，，則給標號為，。④檢查，在弧上，，給標號，在弧上，，給標號為，⑤在、中任選一個進行檢查。在弧，，給標號為，。有了標號，轉(zhuǎn)入調(diào)整過程。（2）調(diào)整按點的第一個標號找到一條從到的增廣鏈，如下圖所示。在此增廣鏈中，調(diào)整，調(diào)整量。因此，在上：，在上，，其余弧的流量均不變，由此，得調(diào)整后網(wǎng)絡(luò)的可行流，繼續(xù)標號過程，結(jié)果發(fā)現(xiàn)，在給標號、給標號之后，無法繼續(xù)標號，即找不到增廣鏈了，因此，上圖所示的流就是最大流，流量為5。同時找到了最小截集，，，此時，該截集的容量也