運(yùn)籌學(xué)完整教案

《運(yùn)籌學(xué)》教案（本教案適用于32課時(shí)的班級(jí)）

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

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

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

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

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

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