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

南京工業(yè)大學(xué)教案用紙．當(dāng)目標(biāo)函數(shù)變（=2\*romanii），就是要了解第三優(yōu)先級中兩目標(biāo)權(quán)系數(shù)取值對原解的影響。表4—90000013/233/45/4100000010-10001001/21-1/41/4-1/2-11/4-1/41/201/4-1/4-1/20-1/41/4001000-10P1P2P3P4000000001001000000W2/4-101-W2/4100W1-W2/4000W2/40000000W20

第18次課2學(xué)時(shí)上次課復(fù)習(xí)：目標(biāo)規(guī)劃單純形法、靈敏度分析本次課題（或教材章節(jié)題目）：§4.5目標(biāo)規(guī)劃應(yīng)用舉例教學(xué)要求：掌握目標(biāo)規(guī)劃數(shù)學(xué)模型的建立重點(diǎn)：目標(biāo)規(guī)劃數(shù)學(xué)模型的建立難點(diǎn)：數(shù)學(xué)模型中目標(biāo)函數(shù)的確定教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：§4.5目標(biāo)規(guī)劃應(yīng)用舉例運(yùn)輸問題目標(biāo)規(guī)劃 50分鐘生產(chǎn)問題目標(biāo)規(guī)劃 50分鐘課后作業(yè)P1326參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁§4.5目標(biāo)規(guī)劃應(yīng)用舉例例6某電子公司生產(chǎn)錄音機(jī)和收音機(jī)兩種產(chǎn)品，它們均需經(jīng)過兩個(gè)工廠加工，每一臺錄音機(jī)在第一個(gè)工廠加工2小時(shí)，然后送到第二個(gè)工廠裝配試驗(yàn)2.5小時(shí)才變?yōu)槌善?；每一臺收音機(jī)需在第一個(gè)工廠加工4小時(shí)，在第二個(gè)工廠裝配試驗(yàn)1.5小時(shí)才變?yōu)槌善贰ｄ浺魴C(jī)與收音機(jī)每臺廠內(nèi)的每月儲存成本分別為8元和15元。第一個(gè)工廠有12部制造機(jī)器，每部每天工作8小時(shí)，每月正常工作天數(shù)為25天，第二個(gè)工廠有7部裝配試驗(yàn)設(shè)備，每部每天工作16小時(shí)，每月正常工作天數(shù)仍為25天。每臺機(jī)器每小時(shí)的運(yùn)轉(zhuǎn)成本是：第一個(gè)工廠為18元，第二個(gè)工廠為15元。每臺錄音機(jī)的銷售利潤為20元，收音機(jī)為23元。依市場預(yù)測，下月錄音機(jī)與收音機(jī)的銷售量估計(jì)分別為1500臺和1000臺。該公司確定下列次序?yàn)槟繕?biāo)優(yōu)先次序：：廠內(nèi)的儲存成本不超過23000元。：錄音機(jī)銷售量必須完成1500臺。：第一、二工廠的生產(chǎn)設(shè)備應(yīng)全力運(yùn)轉(zhuǎn)，避免有空閑時(shí)間。兩廠運(yùn)轉(zhuǎn)成本當(dāng)作它們間的權(quán)系數(shù)。：第一個(gè)工廠的超時(shí)作業(yè)時(shí)間全月份不宜超過30小時(shí)。：收音機(jī)銷售量必須完成1000臺。：兩個(gè)工廠的超時(shí)工作時(shí)間總應(yīng)予限制，其限制的比率依各廠每小時(shí)運(yùn)轉(zhuǎn)成本為準(zhǔn)。試建立這個(gè)問題的目標(biāo)規(guī)劃模型。解設(shè)分別表示次月份錄音機(jī)與收音機(jī)的產(chǎn)量。分別為第個(gè)目標(biāo)的負(fù)、正偏差變量。（1）第一、二工廠設(shè)備運(yùn)轉(zhuǎn)時(shí)間約束：第一個(gè)工廠設(shè)備總能力：8×12×25=2400小時(shí)第二個(gè)工廠設(shè)備總能力：16×7×25=2800小時(shí)于是（2）廠內(nèi)儲存成本約束：（3）銷售目標(biāo)約束：（4）第一個(gè)工廠超時(shí)作業(yè)之約束：注意：這里對偏差變量引進(jìn)它的偏差變量，且用分別表示它的負(fù)、正偏差變量。（5）達(dá)成函數(shù)為：達(dá)成函數(shù)中級目標(biāo)的權(quán)系數(shù)是取第一、第二兩工廠每小時(shí)運(yùn)轉(zhuǎn)成本比率18：15=6：5。綜合上述分析，即得這個(gè)問題的目標(biāo)規(guī)劃模型如下：約束條件：本章小結(jié)目標(biāo)規(guī)劃能夠適應(yīng)更復(fù)雜的實(shí)際問題建模和求解的需要。本章重點(diǎn)掌握下列內(nèi)容：1.正確理解偏差變量，優(yōu)先因子、目標(biāo)約束等基本概念；2.目標(biāo)規(guī)劃建模的方法與步驟，尤其是適當(dāng)構(gòu)成目標(biāo)約束和正確建立目標(biāo)函數(shù)的方法；3.目標(biāo)規(guī)劃的單純形法，它與普通單純形法的共同點(diǎn)和區(qū)別（從單純形表的構(gòu)成、檢驗(yàn)數(shù)的寫法、迭代運(yùn)算的各個(gè)環(huán)節(jié)等方面對兩者進(jìn)行分析比較）。

第19次課2學(xué)時(shí)上次課復(fù)習(xí)：目標(biāo)規(guī)劃主要內(nèi)容回顧：數(shù)學(xué)模型圖解法靈敏度分析本次課題（或教材章節(jié)題目）：第五章整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃問題的提出及其特點(diǎn)第二節(jié)分支定界法教學(xué)要求：掌握整數(shù)規(guī)劃數(shù)學(xué)模型的特點(diǎn)、分支定界法重點(diǎn)：整數(shù)規(guī)劃數(shù)學(xué)模型；分枝定界法難點(diǎn)：分枝定界法教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：第一節(jié)整數(shù)規(guī)劃問題的提出及其特點(diǎn)1.1整數(shù)規(guī)劃問題的提出 35分鐘1.2解的特點(diǎn) 15分鐘第二節(jié)分支定界法 50分鐘課后作業(yè)P1581；4、（2）參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁第五章整數(shù)規(guī)劃本章學(xué)習(xí)過程中注意掌握：分枝定界法、割平面法、0-1規(guī)劃解法、指派問題解法第一節(jié)整數(shù)規(guī)劃問題的提出及其特點(diǎn)整數(shù)規(guī)劃問題的提出例1某公司擬建設(shè)A、B兩種類型的生產(chǎn)基地若干個(gè)，兩種類型的生產(chǎn)基地每個(gè)占地面積，所需經(jīng)費(fèi)，建成后生產(chǎn)能力及現(xiàn)有資源情況如表5-1所示。問A、B類型基地各建設(shè)多少個(gè)，可使總生產(chǎn)能力最大？表5-1AB資源限制占地（m2）費(fèi)用（萬元）20005500041300024生產(chǎn)能力（百件/年）2010解設(shè)A、B兩種類型基地各建設(shè)x1,x2個(gè)，則其模型為：解的特點(diǎn)圖5-1圖5-1第二節(jié)分支定界法例1求解下面整數(shù)規(guī)劃(P(P0)x1=3.25x2=2.5z(0)=14.755(P2)x1=2.5x2=3z(2)=13.5(P3)x1=3x2=2z(3)=13(P4)x1=4x2=1z(4)=14(P1)x1=3.5x2=2z(1)=14.5*×圖5–3圖5-2圖5-2解：從以上解題過程可得用分枝定界法求解整數(shù)規(guī)劃(最大化)問題的步驟為：（1）先求解整數(shù)規(guī)劃的松弛問題，若其無最優(yōu)解，這時(shí)IP也無最優(yōu)解，停止求解；若其有最優(yōu)解，且符合整數(shù)條件，則此整數(shù)最優(yōu)解即為相應(yīng)IP的最優(yōu)解，停止求解；若其是非整數(shù)最優(yōu)解，記其目標(biāo)函數(shù)值為z’，轉(zhuǎn)下一步。（2）定界，用觀察法找IP的一個(gè)整數(shù)可行解，求得其目標(biāo)函數(shù)值，并記作z,以z*表示IP的最優(yōu)值,這時(shí)有:z≤z*≤z’(3)對z’問題分支，在z’問題的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量xj，其值為bj，以[bj]表示不大于bj的最大整數(shù)，構(gòu)造兩個(gè)約束條件xj≤[bj]，和xj≥[bj]+1將這兩個(gè)約束條件分別加到z‘所代表的問題，構(gòu)成兩個(gè)新的線性規(guī)劃分支，求解它們。（4）比較、定界與剪枝，新分支中（包括未剪掉且未分的分支）的最大最優(yōu)值作為IP新的上界z’，可得到的最大整數(shù)最優(yōu)解的目標(biāo)函數(shù)值作為IP新的下界z，若IP新的上下界相等，則此新上（下）界即為IP的最優(yōu)值，對應(yīng)的解為最優(yōu)解，停止計(jì)算；否則對無最優(yōu)解的分支、最優(yōu)目標(biāo)函數(shù)小于z的分枝予以剪枝，以后不再考慮，轉(zhuǎn)（3）。

第20次課2學(xué)時(shí)上次課復(fù)習(xí)：整數(shù)規(guī)劃數(shù)學(xué)模型分支定界法本次課題（或教材章節(jié)題目）：第三節(jié)割平面法第四節(jié)0-1規(guī)劃教學(xué)要求：掌握割平面法、0-1規(guī)劃數(shù)學(xué)模型的建立及解法重點(diǎn)：割平面法；0-1規(guī)劃難點(diǎn)：0-1規(guī)劃數(shù)學(xué)模型的建立教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：第三節(jié)割平面法 50分鐘第四節(jié)0-1規(guī)劃 50分鐘課后作業(yè)P1595、（1）；6、（1）參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁第三節(jié)割平面法割平面法(CuttingPlaneApproach)適用于求解純整數(shù)規(guī)劃的情形。例1考慮純整數(shù)規(guī)劃問題解先不考慮整數(shù)條件，求得其松弛問題的最優(yōu)單純形表為表5-4。表5-4Cj1100CBXBbx1x2x3x40x15/3105/6－1/60x28/301－2/31/3σj00－1/6－1/6x1+x3－x4＝ x2－x3+x4=將系數(shù)和常數(shù)都分解成整數(shù)和非負(fù)真分?jǐn)?shù)之和x1+x3+（－１+）x4＝１+ x2+(–1+)x3+x4=2+解題經(jīng)驗(yàn)表明，考慮式子右端最大真分?jǐn)?shù)的式子，往往會較快地找到所需割平面約束條件。x2–x3–2=－（x3+x4）因?yàn)樗凶兞烤≌麛?shù)，所以式子左端必為整數(shù)，右端則也為整數(shù)，且右端括號項(xiàng)為正數(shù)，則右端應(yīng)為非正數(shù)，即－x3－x4≤0（5.1）移項(xiàng)并引入松弛變量s1后得－x3－x4+s1＝－（5.2）將此約束條件加到表5-4，得表5-5，繼續(xù)求解如下。表5-5Cj11000CBXBbx1x2x3x4s10x35/3105/6－1/600x48/301－2/31/300s1－2/300[－1/3]－1/31σj00－1/6－1/601x10100－101x240101－20x320011－3σj0000－1/2割平面法的求解步驟歸納為：對于整數(shù)規(guī)劃IP maxz=i=1,2,…,mxj≥0,且為整數(shù)，j=1,2,…,n設(shè)其中aij和bi皆為整數(shù)（若不為整數(shù)時(shí)，可乘上一個(gè)倍數(shù)化為整數(shù)）。先求其松弛問題最優(yōu)解，令xj是最優(yōu)解中為分?jǐn)?shù)值的一個(gè)基變量，在松弛問題的最優(yōu)單純形表中，得(5.3)這里xk為非基變量,將bi和aik都分解成整數(shù)部分N與非負(fù)真分?jǐn)?shù)f之和，即bi=Ni+fi,0<fi<1aik=Nik+fik,0≤fik<1將上二式代入（5.3）式，得上式由左邊看為整數(shù)，右邊也應(yīng)為整數(shù)，又因?yàn)?<fi<1，所以不能為正，即得到一個(gè)未排除整數(shù)解的約束條件：（5.4）加入松弛變量，將（5.4）添加到上一步最優(yōu)單純形表中，繼續(xù)求解，直到得到整數(shù)最優(yōu)解。第四節(jié)0-1規(guī)劃4.1問題的提出例1項(xiàng)目選擇問題。現(xiàn)有資金總額為B?？晒┻x擇的投資項(xiàng)目有n個(gè)，項(xiàng)目j所需投資額和預(yù)期收益分別為aj和cj（j=1，2，…，n）。此外，有三個(gè)附加條件：第一，若選擇項(xiàng)目1，就必須同時(shí)選擇項(xiàng)目2。反之，則不一定；第二，項(xiàng)目3和4中至少選擇一個(gè)；第三，項(xiàng)目5，6和7中恰好選擇兩個(gè)。應(yīng)當(dāng)怎樣投資項(xiàng)目，才能使總預(yù)期收益最大？解每一個(gè)投資項(xiàng)目都有被選擇和不被選擇兩種可能，為此令這樣，問題可表示為maxz=在這一問題中，所有變量只有兩個(gè)取值，0或1，即0-1變量，或叫二進(jìn)制變量(binaryvariable)，或叫邏輯變量（logicalvariable）這樣的問題稱為0-1規(guī)劃問題。解0—1型整數(shù)規(guī)劃的隱枚舉法：例5 ◎表5–7點(diǎn)（x1，x2，x3）滿足條件？滿足所有條件？z值◎①②③④（0，0，0）××（0，0，1）××（0，1，0）√4（0，1，1）√√√×（1，0，0）√√××（1，0，1）√√√√√√8（1，1，0）√√√√√√9（1，1，1）√××

第21次課2學(xué)時(shí)上次課復(fù)習(xí)：割平面法0-1規(guī)劃本次課題（或教材章節(jié)題目）：第五節(jié)指派問題教學(xué)要求：掌握指派問題的解法重點(diǎn)：匈牙利解法；人、事數(shù)不等的指派問題；最大化的指派問題難點(diǎn)：匈牙利解法教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：5.1問題的提出 20分鐘5.2求解指派問題的匈牙利法 30分鐘5.3一般的指派問題 50分鐘課后作業(yè)P1607、9、參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁第五節(jié)指派問題5.1問題的提出指派問題的標(biāo)準(zhǔn)形式為：Minz=cijxijxij=1，j=1，2…nxij=1，I=1，2…nxij=1或05.2求解指派問題的匈牙利法5.2.1指派問題最優(yōu)解的性質(zhì)5.2.2匈牙利法第一步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即(1)從（cij）的每行元素都減去該行的最小元素；(2)再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。第二步：進(jìn)行試指派，以尋求最優(yōu)解。在(bij)中找盡可能多的獨(dú)立0元素，若能找出n個(gè)獨(dú)立0元素，就以這n個(gè)獨(dú)立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨(dú)立0元素，常用的步驟為：(1)從只有一個(gè)0元素的行(列)開始，給這個(gè)0元素加圈，記作◎。然后劃去◎所在列(行)的其它0元素，記作；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。(2)給只有一個(gè)0元素的列(行)中的0元素加圈，記作◎；然后劃去◎所在行的0元素，記作．(3)反復(fù)進(jìn)行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。(4)若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個(gè)，則從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。（5）若◎元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m<n,則轉(zhuǎn)入下一步。第三步：作最少的直線覆蓋所有0元素。(1)對沒有◎的行打√號；(2)對已打√號的行中所有含?元素的列打√號；(3)再對打有√號的列中含◎元素的行打√號；(4)重復(fù)(2)，(3)直到得不出新的打√號的行，列為止；(5)對沒有打√號的行畫橫線，有打√號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù)l。l應(yīng)等于m，若不相等，說明試指派過程有誤，回到第二步(4)，另行試指派；若l＝m<n，須再變換當(dāng)前的系數(shù)矩陣，以找到n個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第四步。第四步：變換矩陣(bij)以增加0元素。在沒有被直線覆蓋的所有元素中找出最小元素，然后打√各行都減去這最小元素；打√各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第二步。5.3一般的指派問題5.3.1對極大化問題maxz=cijxij可令bij=M－cij，M是足夠大的常數(shù)（選cij中最大元素為M即可）這時(shí)系數(shù)矩陣可變換為（bij）,bij≥0符合匈牙利法，而z’=bijxij=（M－cij）xij=nM－cijxij=nM－z所以maxz相當(dāng)于minz’=bijxij,（bij）最小解即為原問題（cij）最大解。5.3.2人數(shù)和事數(shù)不等的指派問題

第22次課2學(xué)時(shí)上次課復(fù)習(xí)：整數(shù)規(guī)劃復(fù)習(xí)：分支定界法割平面法指派問題本次課題（或教材章節(jié)題目）：第七章動態(tài)規(guī)劃§7.1多階段決策問題§7.2動態(tài)規(guī)劃的基本概念和基本原理教學(xué)要求：掌握動態(tài)規(guī)劃的基本概念和基本原理重點(diǎn)：動態(tài)規(guī)劃基本概念、標(biāo)號法難點(diǎn)：動態(tài)規(guī)劃基本概念教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：第七章動態(tài)規(guī)劃§7.1多階段決策問題 20分鐘§7.2動態(tài)規(guī)劃的基本概念和基本原理§7.2.1動態(tài)規(guī)劃的基本概念 §7.2.2動態(tài)規(guī)劃的基本思想與基本原理 40分鐘課后作業(yè)P2321、（1）、（2）參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁第七章動態(tài)規(guī)劃本章要求準(zhǔn)確熟練地掌握動態(tài)規(guī)劃的基本概念，特別是狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程、指標(biāo)函數(shù)和動態(tài)規(guī)劃基本方程等，了解最優(yōu)性原理，掌握動態(tài)規(guī)劃的逆序解法并能夠應(yīng)用于典型問題的求解?！?.1多階段決策問題例7-1最短路問題如圖7-1所示，要從A地到E地鋪設(shè)管線，中間需要經(jīng)過三個(gè)中間站，兩點(diǎn)之間的連線上的數(shù)字表示距離，問應(yīng)該選擇什么路線，使總距離最短？335256321737562254321B1AB2B3C1C2C3C4ED2D1B1B1B1B1B1B1B1B1B1B1B1B1B1A§7.2動態(tài)規(guī)劃的基本概念和基本原理§7.2.11.階段（stage）2.狀態(tài)（state）3.決策（decision）4.策略（policy）5.狀態(tài)轉(zhuǎn)移方程（statetransferequation）6.指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)§7.2.2動態(tài)規(guī)劃的基本思想與基本原理動態(tài)規(guī)劃的基本思想概括歸結(jié)如下：1.將多階段決策問題按照空間或時(shí)間順序劃分成相互聯(lián)系的階段，即把一個(gè)大問題分解成一族同類型的子問題，選取恰當(dāng)?shù)臓顟B(tài)變量和決策變量，寫出狀態(tài)轉(zhuǎn)移方程，定義最優(yōu)指標(biāo)函數(shù)，寫出遞推關(guān)系式和邊界條件。2.從邊界條件開始，由后向前逐段遞推尋找最優(yōu)，在每一個(gè)階段的計(jì)算中都要用到前一階段的最優(yōu)結(jié)果，依次進(jìn)行，求得最后一個(gè)子問題的最優(yōu)解就是整個(gè)問題的最優(yōu)解。3.在多階段決策過程中，確定階段k的最優(yōu)決策時(shí)，不是只考慮本階段最優(yōu)，而是要考慮本階段及其所有后部子過程的整體最優(yōu)，也就是說，它是把當(dāng)前效益和未來效益結(jié)合起來考慮的一種方法。R.Bellman等人在深入研究多階段決策問題的基礎(chǔ)上，提出了著名的最優(yōu)性原理：“作為整個(gè)過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略?！币簿褪钦f，一個(gè)最優(yōu)策略的子策略也是最優(yōu)的。這一原理是動態(tài)規(guī)劃方法的核心，根據(jù)最優(yōu)原理可以將一個(gè)多階段決策過程化為若干個(gè)單階段決策過程，當(dāng)然這種轉(zhuǎn)化要滿足兩個(gè)基本條件，這就是前文所述的指標(biāo)函數(shù)的可分離性和狀態(tài)變量的無后效性。

第23次課2學(xué)時(shí)上次課復(fù)習(xí)：動態(tài)規(guī)劃的基本概念標(biāo)號法本次課題（或教材章節(jié)題目）：§7.3動態(tài)規(guī)劃模型及求解方法教學(xué)要求：掌握動態(tài)規(guī)劃模型的建立及求解方法重點(diǎn)：動態(tài)規(guī)劃建模方法及求解方法難點(diǎn)：動態(tài)規(guī)劃模型的建立教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：§7.3動態(tài)規(guī)劃模型及求解方法§7.3.1動態(tài)規(guī)劃的數(shù)學(xué)模型 30分鐘§7.3.2動態(tài)規(guī)劃的求解方法 70分鐘課后作業(yè)P2332、（1）、參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁§7.3動態(tài)規(guī)劃模型及求解方法§7.3.1動態(tài)規(guī)劃的數(shù)學(xué)模型1.動態(tài)規(guī)劃的基本方程2.建立動態(tài)規(guī)劃模型的步驟建立動態(tài)規(guī)劃數(shù)學(xué)模型，一般有如下步驟：（1）劃分階段劃分階段是運(yùn)用動態(tài)規(guī)劃求解多階段決策問題的第一步，在確定多階段特性后，按時(shí)間或空間先后順序，將過程劃分為若干相互聯(lián)系的階段。對于靜態(tài)問題要人為地賦予“時(shí)間”概念，以便劃分階段。（2）正確選擇狀態(tài)變量sk選擇變量既要能確切描述過程演變又要滿足無后效性，而且各階段狀態(tài)變量的取值能夠確定。一般地，狀態(tài)變量的選擇是從過程演變的特點(diǎn)中尋找。（3）確定決策變量uk及允許決策集合Dk（sk）通常選擇所求解問題的關(guān)鍵變量作為決策變量，同時(shí)要給出決策變量的取值范圍，即確定允許決策集合。（4）確定狀態(tài)轉(zhuǎn)移方程根據(jù)k階段狀態(tài)變量sk和決策變量uk（sk）寫出k+1階段狀態(tài)變量sk+1，即sk+1=Tk（sk，uk），狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。（5）確定階段指標(biāo)函數(shù)和最優(yōu)指標(biāo)函數(shù)，建立動態(tài)規(guī)劃基本方程階段指標(biāo)函數(shù)vk（sk，uk）是指第k階段的收益，最優(yōu)指標(biāo)函數(shù)fk（sk）是指從第k階段狀態(tài)sk出發(fā)到第n階段末所獲得收益的最優(yōu)值，最后寫出動態(tài)規(guī)劃基本方程。以上五步是建立動態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。由于動態(tài)規(guī)劃模型與線性規(guī)劃模型不同，動態(tài)規(guī)劃模型沒有統(tǒng)一的模式，建模時(shí)必須根據(jù)具體問題具體分析，只有通過不斷實(shí)踐總結(jié)，才能較好掌握建模方法與技巧?！?.3.2動態(tài)規(guī)劃的求解方法逆序解法是求解動態(tài)規(guī)劃問題的一般常用方法，即由k=n遞推至k=1得到問題的最優(yōu)解。一般地，如果階段指標(biāo)函數(shù)vk（sk，uk）是線性函數(shù)或凸函數(shù)時(shí)，最優(yōu)指標(biāo)函數(shù)fk（sk）的表達(dá)式比較容易得到，但是當(dāng)vk（sk，uk）不具備上述特性時(shí)，最優(yōu)指標(biāo)函數(shù)fk（sk）的表達(dá)式不易得到，就需要采用數(shù)值法，即對連續(xù)變量進(jìn)行離散化處理，再分散求解。例如靜態(tài)規(guī)劃模型其動態(tài)規(guī)劃基本方程為：狀態(tài)轉(zhuǎn)移方程為sk+1=sk－xk s1=a狀態(tài)變量sk及決策變量xk都是連續(xù)變量，對其進(jìn)行離散化處理，具體做法是：1.對區(qū)間[0，a]進(jìn)行分割，分割數(shù)m=，其中Δ是分割后的小區(qū)間的長度，其大小可以根據(jù)所求解問題要求的精度及計(jì)算機(jī)運(yùn)算能力而定，分割點(diǎn)為0，Δ，2Δ，…，mΔ=a。2.規(guī)定狀態(tài)變量sk及決策變量xk僅在離散點(diǎn)0，Δ，2Δ，…，mΔ處取值，最優(yōu)指標(biāo)函數(shù)fk（sk）也定義在這些離散點(diǎn)上。動態(tài)規(guī)劃基本方程可以寫為：其中sk=qΔ，xk=pΔ。3.由后向前逐段遞推，直至求出整個(gè)過程最優(yōu)解。需要指出的是當(dāng)連續(xù)變量離散化處理以后，由于狀態(tài)變量和決策變量只在給定的離散點(diǎn)上取值，故有可能漏掉最優(yōu)解，因此需要慎重選擇參數(shù)m與Δ。

第24次課2學(xué)時(shí)上次課復(fù)習(xí)：動態(tài)規(guī)劃建模方法及求解方法本次課題（或教材章節(jié)題目）：§7.4動態(tài)規(guī)劃的應(yīng)用舉例§7.4.1資源分配問題教學(xué)要求：掌握資源分配問題模型及求解方法重點(diǎn)：資源分配問題模型及求解方法難點(diǎn)：資源分配問題的求解方法教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：§7.4.1資源分配問題 50分鐘作業(yè)3、利潤最大化問題 50分鐘課后作業(yè)P2344、參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁§7.4動態(tài)規(guī)劃的應(yīng)用舉例動態(tài)規(guī)劃應(yīng)用十分廣泛，通過具體實(shí)例展示它在管理領(lǐng)域的應(yīng)用，并進(jìn)一步闡述動態(tài)規(guī)劃方法?！?.4.1資源分配問題資源分配問題就是將一定數(shù)量的一種或若干種資源（原材料、資金、設(shè)備等）合理分配給若干使用者，使得資源分配后總結(jié)果最優(yōu)。一種資源的分配問題稱為一維資源分配問題，兩種資源的分配問題稱為二維資源分配問題。假設(shè)有一種資源，數(shù)量為a，將其分配給n個(gè)使用者，分配給第i個(gè)使用者數(shù)量xi時(shí)，相應(yīng)的收益為gi（xi），問如何分配使得總收入最大？這就是一維資源分配問題，該問題的數(shù)學(xué)模型為： （7.3）解式（7.3）是一個(gè)靜態(tài)規(guī)劃問題，應(yīng)用動態(tài)規(guī)劃方法求解時(shí)人為賦予時(shí)間概念，將其看作是一個(gè)多階段決策問題。按變量個(gè)數(shù)劃分階段，k=1，2，…，n；設(shè)決策變量uk=xk，表示分配給第k個(gè)使用者的資源數(shù)量；設(shè)狀態(tài)變量為sk，表示分配給第k個(gè)至第n個(gè)使用者的總資源數(shù)量；狀態(tài)轉(zhuǎn)移方程：sk+1=sk－xk，其中s1=a；允許決策集合：Dk（sk）=｛xk|0≤xk≤sk｝階段指標(biāo)函數(shù)：vk（sk，uk）=gk（xk）表示分配給第k個(gè)使用者數(shù)量xk時(shí)的收益；最優(yōu)指標(biāo)函數(shù)fk（sk）表示以數(shù)量sk的資源分配給第k個(gè)至第n個(gè)使用者所得到的最大收益，則動態(tài)規(guī)劃基本方程為：由后向前逐段遞推，f1（a）即為所求問題的最大收益。

第25次課2學(xué)時(shí)上次課復(fù)習(xí)：資源分配問題模型及求解方法本次課題（或教材章節(jié)題目）：機(jī)器負(fù)荷問題、生產(chǎn)-庫存問題教學(xué)要求：掌握機(jī)器負(fù)荷問題、生產(chǎn)-庫存問題模型及求解方法重點(diǎn)：機(jī)器負(fù)荷問題、生產(chǎn)-庫存問題模型及求解方法難點(diǎn)：機(jī)器負(fù)荷問題、生產(chǎn)-庫存問題模型的建立教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：機(jī)器負(fù)荷問題 50分鐘生產(chǎn)—庫存問題 50分鐘課后作業(yè)P2345、6、參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁例7-7機(jī)器負(fù)荷問題某工廠有100臺機(jī)器，擬分四期使用，每一期都可在高、低兩種不同負(fù)荷下進(jìn)行生產(chǎn)。若把x臺機(jī)器投入高負(fù)荷下進(jìn)行生產(chǎn)，則在本期結(jié)束時(shí)將有1/3的機(jī)器損壞報(bào)廢；余下的機(jī)器全部投入低負(fù)荷下進(jìn)行生產(chǎn)，則在期末有1/10的機(jī)器報(bào)廢。如果高負(fù)荷下生產(chǎn)時(shí)每臺機(jī)器可獲利潤為10，低負(fù)荷下生產(chǎn)時(shí)每臺機(jī)器可獲利潤為7，問怎樣分配機(jī)器使四期的總利潤最大？解將問題按周期分為4個(gè)階段，k=1，2，3，4；狀態(tài)變量sk表示第k階段初完好的機(jī)器數(shù)，s1=100，0≤sk≤100；決策變量xk表示第k階段投入高負(fù)荷下生產(chǎn)的機(jī)器數(shù)，則sk－xk表示第k階段投入低負(fù)荷下生產(chǎn)的機(jī)器數(shù)；允許決策集合：Dk（sk）=｛xk|0≤xk≤sk｝狀態(tài)轉(zhuǎn)移方程：sk+1=Tk（sk，xk），即第k+1階段初擁有的完好機(jī)器數(shù)sk+1為：；階段指標(biāo)函數(shù)：vk（sk，xk）=10xk+7（sk－xk）表示第k階段所獲得的利潤；最優(yōu)指標(biāo)函數(shù)fk（sk）表示從第k階段初完好機(jī)器數(shù)為sk至第四階段的最大利潤，動態(tài)規(guī)劃基本方程為：§7.4.2例7-8（生產(chǎn)—庫存問題）某工廠要對一種產(chǎn)品制定今后四個(gè)時(shí)期的生產(chǎn)計(jì)劃，據(jù)估計(jì)在今后四個(gè)時(shí)期內(nèi)，市場對該產(chǎn)品的需求量分別為2，3，2，4單位，假設(shè)每批產(chǎn)品固定成本為3千元，若不生產(chǎn)為0，每單位產(chǎn)品成本為1千元，每個(gè)時(shí)期最大生產(chǎn)能力不超過6個(gè)單位，每期期末未出售產(chǎn)品，每單位需付存貯費(fèi)0.5千元，假定第1期初和第4期末庫存量均為0，問該廠如何安排生產(chǎn)與庫存，可在滿足市場需求的前提下總成本最小。解以每個(gè)時(shí)期作為一個(gè)階段，該問題分為4個(gè)階段，k=1，2，3，4；決策變量xk表示第k階段生產(chǎn)的產(chǎn)品數(shù)；狀態(tài)變量sk表示第k階段初的庫存量；以dk表示第k階段的需求，則狀態(tài)轉(zhuǎn)移方程：sk+1=sk+xk－dkk=4，3，2，1 由于期初及期末庫存為0，所以s1=0，s5=0；允許決策集合Dk（sk）的確定：當(dāng)sk≥dk時(shí)，xk可以為0，當(dāng)sk<dk時(shí)，至少應(yīng)生產(chǎn)dk－sk，故xk的下限為max（0，dk－sk）；每期最大生產(chǎn)能力為6，xk最大不超過6，由于期末庫存為0，xk還應(yīng)小于本期至4期需求之和減去本期的庫存量，，所以xk的上限為min（，6），故有：Dk（sk）=｛xk|max（0，dk－sk）≤xk≤min（，6）｝階段指標(biāo)函數(shù)rk（sk，xk）表示第k期的生產(chǎn)費(fèi)用與存貯費(fèi)用之和： 最優(yōu)指標(biāo)函數(shù)fk（sk）表示第k期庫存為sk到第4期末的生產(chǎn)與存貯最低費(fèi)用，動態(tài)規(guī)劃基本方程為：

第26次課2學(xué)時(shí)上次課復(fù)習(xí)：機(jī)器負(fù)荷問題模型及求解方法、生產(chǎn)-庫存問題模型及求解方法本次課題（或教材章節(jié)題目）：庫存-銷售問題、背包問題、復(fù)合系統(tǒng)工作可靠性問題模型及求解教學(xué)要求：掌握庫存-銷售問題、背包問題、復(fù)合系統(tǒng)工作可靠性問題模型及求解方法重點(diǎn)：庫存-銷售問題、背包問題、復(fù)合系統(tǒng)工作可靠性問題模型及求解方法難點(diǎn)：庫存-銷售問題、背包問題、復(fù)合系統(tǒng)工作可靠性問題模型的建立教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：庫存-銷售問題 40分鐘背包問題 30分鐘復(fù)合系統(tǒng)工作可靠性問題 30分鐘課后作業(yè)P2358、9、參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁例7-9（庫存—銷售問題）設(shè)某公司計(jì)劃在1至4月份從事某種商品經(jīng)營。已知倉庫最多可存儲600件這種商品，已知1月初存貨200件，根據(jù)預(yù)測知1至4月份各月的單位購貨成本及銷售價(jià)格如表7-13所示，每月只能銷售本月初的庫存，當(dāng)月進(jìn)貨供以后各月銷售，問如何安排進(jìn)貨量和銷售量，使該公司四個(gè)月獲得利潤最大（假設(shè)四月底庫存為零）。表7-13月份購貨成本C銷售價(jià)格P12344038404245423944解按月份劃分階段，k=1，2，3，4；狀態(tài)變量sk表示第k月初的庫存量，s1=200，s5=0；決策變量xk表示第k月售出的貨物數(shù)量，yk表示第k月購進(jìn)的貨物數(shù)量；狀態(tài)轉(zhuǎn)移方程：sk+1=sk+yk－xk；允許決策集合：0≤xk≤sk，0≤yk≤600－（sk－xk）；階段指標(biāo)函數(shù)為：pkxk－ckyk表示k月份的利潤，其中pk為第k月份的單位銷售價(jià)格，ck為第k月份的單位購貨成本；最優(yōu)指標(biāo)函數(shù)fk（sk）表示第k月初庫存為sk時(shí)從第k月至第4月末的最大利潤，則動態(tài)規(guī)劃基本方程為： §7.4.3背包問題有人攜帶背包上山，其可攜帶物品的重量限度為a公斤，現(xiàn)有n種物品可供選擇，設(shè)第i種物品的單件重量為ai公斤，其在上山過程中的價(jià)值是攜帶數(shù)量xi的函數(shù)ci（xi），問應(yīng)如何安排攜帶各種物品的數(shù)量，使總價(jià)值最大。這就是背包問題，類似的貨物裝載問題，下料問題都等同于背包問題。背包問題的數(shù)學(xué)模型為：下面用動態(tài)規(guī)劃方法求解：按照裝入物品的種類劃分階段，k=1，2，…，n；狀態(tài)變量sk表示裝入第k種至第n種物品的總重量；決策變量xk表示裝入第k種物品的件數(shù)；狀態(tài)轉(zhuǎn)移方程為： sk+1=sk－akxk允許決策集合為： 其中表示不超過的最大整數(shù)；階段指標(biāo)函數(shù)ck（xk）表示第k階段裝入第k種商品xk件時(shí)的價(jià)值；最優(yōu)指標(biāo)函數(shù)fk（sk）表示第k階段裝入物品總重量為sk時(shí)的最大價(jià)值，動態(tài)規(guī)劃基本方程為：§7.4.4復(fù)合系統(tǒng)工作可靠性問題某個(gè)機(jī)器工作系統(tǒng)由n個(gè)部件串聯(lián)而成，其中只要有一個(gè)部件失效，則整個(gè)系統(tǒng)不能正常工作，因此為了提高系統(tǒng)工作的可靠性，在設(shè)計(jì)時(shí)，每個(gè)主要部件上都裝有備用元件，一旦某個(gè)主要部件失效，備用元件會自動投入系統(tǒng)工作，顯然備用元件越多，系統(tǒng)工作可靠性越大，但是備用元件越多，系統(tǒng)的成本、重量、體積相應(yīng)增大，工作精度降低，因此在上述限制條件下，應(yīng)選擇合理的備用元件數(shù)，使整個(gè)系統(tǒng)的工作可靠性最大。設(shè)第i（i=1，2，…，n）個(gè)部件上裝有ui個(gè)備用元件，正常工作的概率為pi（ui），則整個(gè)系統(tǒng)正常工作的可靠性為，裝第i個(gè)部件的費(fèi)用為ci，重量為wi，要求總費(fèi)用不超過c，總重量不超過w，則靜態(tài)規(guī)劃數(shù)學(xué)模型為：下面用動態(tài)規(guī)劃方法求解。按部件個(gè)數(shù)劃分階段，k=1，2，…，n；決策變量uk表示部件k上的備用元件數(shù)；狀態(tài)變量xk表示從第k個(gè)到第n個(gè)部件的總費(fèi)用， yk表示從第k個(gè)到第n個(gè)部件的總重量；狀態(tài)轉(zhuǎn)移方程為： xk+1=xk－ckuk yk+1=yk－wkuk允許決策集合為： 階段指標(biāo)函數(shù)為pk（uk），表示第k個(gè)部件的正常工作概率；最優(yōu)指標(biāo)函數(shù)fk（xk，yk）表示由狀態(tài)xk，yk出發(fā)，從部件k到部件n的系統(tǒng)工作最大可靠性，則動態(tài)規(guī)劃基本方程為：f1（c，w）即為整個(gè)系統(tǒng)工作的最大可靠性。本章小結(jié)一般來講，任何多階段決策問題只要滿足無后效性，且整個(gè)過程具有遞推性，這樣的多階段決策問題都可以用動態(tài)規(guī)劃方法來處理。運(yùn)用動態(tài)規(guī)劃解決實(shí)際問題易于確定全局最優(yōu)解，能得到一族最優(yōu)解。但是動態(tài)規(guī)劃方法也存在不足之處，一是沒有統(tǒng)一的標(biāo)準(zhǔn)模型可供使用，建模時(shí)需要根據(jù)問題性質(zhì)及數(shù)學(xué)特點(diǎn)加以解決，這就需要靈活的技巧及大量的實(shí)踐；二是應(yīng)用局限性，動態(tài)規(guī)劃模型中的狀態(tài)變量必須滿足無后效性，而許多實(shí)際問題往往不能滿足這一條件；三是存在“維數(shù)障礙”，即當(dāng)變量個(gè)數(shù)（維數(shù)）太大時(shí)，問題雖然可以用動態(tài)規(guī)劃方法來描述，但由于計(jì)算機(jī)內(nèi)存容量的限制而難以求解，一般地超過三維（含三維）的問題通常不采用動態(tài)規(guī)劃方法來求解。

第27次課2學(xué)時(shí)上次課復(fù)習(xí)：動態(tài)規(guī)劃回顧：數(shù)學(xué)模型特點(diǎn)求解方法特點(diǎn)本次課題（或教材章節(jié)題目）：第八章圖與網(wǎng)絡(luò)分析§8.1圖與網(wǎng)絡(luò)的基本知識§8.2樹教學(xué)要求：掌握圖與網(wǎng)絡(luò)的基本概念、樹的概念和性質(zhì)重點(diǎn)：圖的基本概念、樹的概念和性質(zhì)難點(diǎn)：樹的概念和性質(zhì)教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：§8.1圖與網(wǎng)絡(luò)的基本知識 50分鐘§8.2樹 50分鐘課后作業(yè)P2659、參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁第八章圖與網(wǎng)絡(luò)分析通過對本章的學(xué)習(xí)，正確理解圖的基本概念與基本定理，掌握用圖形與矩陣表示圖的方法，理解樹與最小支撐數(shù)的概念及求最小樹的算法。理解歐拉圖與最優(yōu)投遞路線問題的解法。熟練掌握賦權(quán)的最短通路問題及其Dijkstra算法，會用逐次逼近法求解帶有負(fù)權(quán)的最短路問題。理解最大流問題，掌握求最大流的標(biāo)號算法。會求網(wǎng)絡(luò)系統(tǒng)的最大流和最小費(fèi)用最大流?！?.1圖與網(wǎng)絡(luò)的基本知識§8.1.1圖與網(wǎng)絡(luò)的基本概念定義1一個(gè)圖是由點(diǎn)集和中元素的無序?qū)Φ囊粋€(gè)集合所構(gòu)成的二元組，記為G=(V，E)，其中中的元素叫做頂點(diǎn)，V表示圖G的點(diǎn)集合；E中的元素叫做邊，E表示圖G的邊集合。一條邊的兩個(gè)端點(diǎn)是相同的,那么稱為這條邊是環(huán)。如果兩個(gè)端點(diǎn)之間有兩條以上的邊，那么稱為它們?yōu)槎嘀剡叀６x2一個(gè)無環(huán)，無多重邊的圖稱為簡單圖，一個(gè)無環(huán)，有多重邊的圖稱為多重圖。定義3每一對頂點(diǎn)間都有邊相連的無向簡單圖稱為完全圖。有個(gè)頂點(diǎn)的無向完全圖記作。有向完全圖則是指任意兩個(gè)頂點(diǎn)之間有且僅有一條有向邊的簡單圖。定義4以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn)v的度，記作。度為零的點(diǎn)稱為弧立點(diǎn)，度為1的點(diǎn)稱為懸掛點(diǎn)。懸掛點(diǎn)的邊稱為懸掛邊。度為奇數(shù)的點(diǎn)稱為奇點(diǎn)，度為偶數(shù)的點(diǎn)稱為偶點(diǎn)。定理1所有頂點(diǎn)度數(shù)之和等于所有邊數(shù)的2倍。定理2在任一圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。定義5有向圖中，以為始點(diǎn)的邊數(shù)稱為點(diǎn)的出次，用表示；以為終點(diǎn)的邊數(shù)稱為點(diǎn)的入次，用表示；點(diǎn)的出次和入次之和就是該點(diǎn)的次。定義6設(shè)G1=（V1,E1），G2=（V2,E2）如果V2V1,E2E1稱G2是G1的子圖；如果V2=V1,E2E1稱G2是G1的部分圖或支撐子圖。在實(shí)際應(yīng)用中，給定一個(gè)圖G=（V，E）或有向圖D=（V，A），在V中指定兩個(gè)點(diǎn)，一個(gè)稱為始點(diǎn)（或發(fā)點(diǎn)），記作v1，一個(gè)稱為終點(diǎn)（或收點(diǎn)），記作vn，其余的點(diǎn)稱為中間點(diǎn)。對每一條弧，對應(yīng)一個(gè)數(shù)，稱為弧上的“權(quán)”。通常把這種賦權(quán)的圖稱為網(wǎng)絡(luò)。§8.1.2定義7由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列稱為鏈。如：v0，e1，v1，e2，v2，e3，v3,…,vn-1,en，vn，記作（v0，v1，v2，v3,…,vn-1，vn），其鏈長為n，其中v0，vn分別稱為鏈的起點(diǎn)和終點(diǎn)。若鏈中所含的邊均不相同，則稱此鏈為簡單鏈；所含的點(diǎn)均不相同的鏈稱為初等鏈，也稱通路。定義8無向圖G中，連接v0與vn的一條鏈，若v0≠vn則稱該鏈為開鏈，否則稱為閉鏈或回路或圈；如果在一個(gè)圈中所含的邊均不相同，稱此圈為簡單圈；除起點(diǎn)和終點(diǎn)外鏈中所含的點(diǎn)均不相同的圈，叫做初等圈。定義9圖中任意兩點(diǎn)之間均至少有一條通路，則稱此圖為連通圖，否則稱為不連通圖?！?.1.3定義11對于賦權(quán)圖G=（V，E），其中邊有權(quán)，構(gòu)造矩陣，其中：稱矩陣A為網(wǎng)絡(luò)G的權(quán)矩陣。定義12設(shè)圖G=（V，E）中頂點(diǎn)的個(gè)數(shù)為，構(gòu)造一個(gè)矩陣，其中：稱矩陣A為網(wǎng)絡(luò)G的鄰接矩陣?！?.2樹§8.2.1定義13一個(gè)連通的無圈的無向圖叫做樹。樹中次為1的點(diǎn)稱為樹葉，次大于1的點(diǎn)稱為分支點(diǎn)。作為樹T的定義，下列定義是等價(jià)的：（1）T是一個(gè)樹。（設(shè)其頂點(diǎn)數(shù)為n，邊數(shù)為m）（2）T無圈，且。（3）T連通，且。（4）T無圈，但在樹中不相鄰的兩個(gè)點(diǎn)之間加上一條邊，那么恰好得到一個(gè)圈。（5）T中任意兩個(gè)頂點(diǎn)之間有且僅有一條鏈。（6）T連通，但去掉T的任一條邊，T就不連通。§8.2.2定義14設(shè)圖是圖G=(V,E)的支撐子圖，如果圖是一個(gè)樹,那么稱K是G的一個(gè)生成樹（支撐樹），或簡稱為圖G的樹定理4一個(gè)圖G有生成樹的充要條件是G是連通圖。§8.2.3定義15如果圖是圖G的一個(gè)生成樹，那么稱E1上所有邊的權(quán)的和為生成樹T的權(quán)，記作S(T)。如果圖G的生成樹T*的權(quán)S(T*)，在G的所有生成樹T中的權(quán)最小，即，那么稱T*是G的最小生成樹。定理5用Kruskal算法得到的子圖是一棵最小樹。

第28次課2學(xué)時(shí)上次課復(fù)習(xí)：圖與網(wǎng)絡(luò)的基本概念樹的概念和性質(zhì)本次課題（或教材章節(jié)題目）：§8.3最短路問題教學(xué)要求：掌握最短路問題的算法重點(diǎn)：狄克斯屈拉(Dijkstra)算法難點(diǎn)：狄克斯屈拉(Dijkstra)算法教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：最短路問題解法思路 20分鐘狄克斯屈拉(Dijkstra)算法及實(shí)例 80分鐘課后作業(yè)P26612、參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁§8.3最短路問題最短路的一般提法為：設(shè)為連通圖，圖中各邊有權(quán)（表示之間沒有邊），為圖中任意兩點(diǎn)，求一條路，使它為從到的所有路中總權(quán)最短。即：最小?！?.3.1狄克斯屈拉(DijkstraDijkstra算法，是Dijkstra在1959年提出來的。目前公認(rèn)，在所有的權(quán)wij≥0時(shí)，這個(gè)算法是尋求最短路問題最好的算法。并且，這個(gè)算法實(shí)際上也給出了尋求從一個(gè)始定點(diǎn)vs到任意一個(gè)點(diǎn)vj的最短路。Dijkstra算法的基本思想是：從vs出發(fā)，逐步向外尋找最短路。在運(yùn)算過程中，與每個(gè)點(diǎn)對應(yīng)，記錄一個(gè)數(shù)，叫做一個(gè)點(diǎn)的標(biāo)號。它或者表示從vs到該點(diǎn)的最短路權(quán)叫做P標(biāo)號，為永久性標(biāo)號（permanentlabel）。或者表示從vs到該點(diǎn)最短路權(quán)的上界，叫做T標(biāo)號，為試探性標(biāo)號（tentativelabel）。算法的每一步是去修改T標(biāo)號，把某一個(gè)具有T標(biāo)號的點(diǎn)改變?yōu)榫哂蠵標(biāo)號的點(diǎn)，使圖D中具有P標(biāo)號的頂點(diǎn)多一個(gè)。這樣，對于有個(gè)頂點(diǎn)的圖，至多經(jīng)過步，就可求出從始點(diǎn)vs到各點(diǎn)vj及終點(diǎn)的最短路。算法步驟：1.給始點(diǎn)vs以P標(biāo)號，這表示從vs到vs的最短距離為0，其余節(jié)點(diǎn)均給T標(biāo)號，。（2）設(shè)節(jié)點(diǎn)為剛得到P標(biāo)號的點(diǎn)，考慮點(diǎn)，其中，且為T標(biāo)號。對的T標(biāo)號進(jìn)行如下修改：。（3）比較所有具有T標(biāo)號的節(jié)點(diǎn)，把最小者改為P標(biāo)號，即：當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號。若全部節(jié)點(diǎn)均為P標(biāo)號，則停止，否則用代替，返回步驟（2）。

第29次課2學(xué)時(shí)上次課復(fù)習(xí)：狄克斯屈拉(Dijkstra)算法本次課題（或教材章節(jié)題目）：§8.3最短路問題教學(xué)要求：掌握最短路問題的逐次逼近算法、掌握最短路問題的應(yīng)用重點(diǎn)：逐次逼近算法難點(diǎn)：逐次逼近算法教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：逐次逼近算法 60分鐘最短路問題應(yīng)用實(shí)例 40分鐘課后作業(yè)P26613、參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁§8.3.2逐次逼近法Dijkstra算法只能計(jì)算非負(fù)權(quán)的情況，本算法可用于網(wǎng)絡(luò)中帶有負(fù)權(quán)的邊時(shí)，求某指定點(diǎn)到網(wǎng)絡(luò)中任意點(diǎn)的最短距離。算法的基本思路與步驟：首先設(shè)任一點(diǎn)到任一點(diǎn)都有一條弧，如果在圖G中，，則添加弧，并令。顯然，從到的最短路是從出發(fā)，沿著這條路到某個(gè)點(diǎn)，再沿弧到。則到的這條路必然也是到的最短路。否則，從到的這條路將不是最短的。于是，設(shè)表示從到的最短路長，表示從到的最短路長，則有下列方程：利用如下的遞推公式：開始時(shí)，令即用到的直接距離做初始解。從第二步起，使用遞推公式：求，當(dāng)進(jìn)行到第步，若出現(xiàn)則停止計(jì)算，即為到各點(diǎn)的最短路長。最短路的應(yīng)用：例8.9某工廠使用一種設(shè)備，這種設(shè)備在一定的年限內(nèi)隨著時(shí)間的推移逐漸損壞。所以工廠在每年年初都要決定設(shè)備是否更新。若購置設(shè)備，每年需支付購置費(fèi)用；若繼續(xù)使用舊設(shè)備，需要支付維修與運(yùn)行費(fèi)用，而且隨著設(shè)備的老化會逐年增加。計(jì)劃期（五年）內(nèi)中每年的購置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)如表8—2所示，工廠要制定今后五年設(shè)備更新計(jì)劃，問采用何種方案才能使包括購置費(fèi)、維修費(fèi)與運(yùn)行費(fèi)在內(nèi)的總費(fèi)用最小。這個(gè)問題可以轉(zhuǎn)化為圖的問題，考慮六個(gè)節(jié)點(diǎn)v1、v2、v3、v4、v5、v6，其中vi(i=1,2,3,4,5)表示在第i年初要購置新設(shè)備。節(jié)點(diǎn)v6是虛設(shè)點(diǎn)，表示第五年的年底才購置新設(shè)備。再從點(diǎn)vi(i=1,2,3,4,5)引出指向vi+1，vi+2，…，v6的弧，?。╲i,vj）表示第i年年初購進(jìn)的新設(shè)備一直使用到第j年（(j=2,3,4,5，6)的年初?；。╲i,vj）上所賦的權(quán)為第i年的購置費(fèi)加上從第i年初使用到第j年初的維修費(fèi)用的總和。這樣，我們得到一個(gè)賦權(quán)的有向圖,于是，問題就變?yōu)橛米疃搪穯栴}來求解。表8——2計(jì)劃期內(nèi)費(fèi)用表年份12345購置費(fèi)1820212324使用年數(shù)0—11—22—33—44—5維修費(fèi)571218252828v1v2v3v4v5v62325262930426085324462334535

第30次課2學(xué)時(shí)上次課復(fù)習(xí)：逐次逼近算法本次課題（或教材章節(jié)題目）：§8.4最大流問題教學(xué)要求：掌握最大流問題的求解方法重點(diǎn)：基本概念、截集、標(biāo)號法難點(diǎn)：截集、標(biāo)號法教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：§8.4.1基本概念 30分鐘§8.4.2Fold—Fulkerson定理 §8.4.3求最大流的標(biāo)號法 課后作業(yè)P26614、參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁§8.4最大流問題8.4.1基本概念定義19設(shè)一個(gè)賦權(quán)有向圖D=（V,A）,在V中指定一個(gè)發(fā)點(diǎn)vs和一個(gè)收點(diǎn)vt,其它的點(diǎn)叫做中間點(diǎn)。對于D中的每一個(gè)?。╲i,vj）∈A,都有一個(gè)非負(fù)數(shù),叫做弧的容量。我們把這樣的圖D叫做一個(gè)容量網(wǎng)絡(luò)，簡稱網(wǎng)絡(luò)，記做D=（V，A，C）。網(wǎng)絡(luò)D上的流，是指定義在弧集合E上的一個(gè)函數(shù)，其中f(vi,vj)=fij叫做弧(vi，vj)上的流量。稱滿足下列條件的流為可行流：（1）容量條件：對于每一個(gè)?。╲i,vj）∈E，有0≤fij≤cij。（2）平衡條件：對于發(fā)點(diǎn)vs，有對于收點(diǎn)vt，有對于中間點(diǎn)，有設(shè)流f={fij}是網(wǎng)絡(luò)D上的一個(gè)可行流。我們把D中fij＝cij的弧叫做飽和弧，fij＜cij的弧叫做非飽和弧。fij＞0的弧為非零流弧，fij＝0的弧叫做零流弧。定義20容量網(wǎng)絡(luò)G=（V，E，C），vs為始點(diǎn)，vt為終點(diǎn)。如果把V分成兩個(gè)非空集合，使，則所有始點(diǎn)屬于S，而終點(diǎn)屬于的弧的集合，稱為由S決定的截集，記作。截集中所有弧的容量之和，稱為這個(gè)截集的容量，記為。由于V的分解方法不同，所以截集就不相同，對應(yīng)的截集的容量也不相同，其中容量最小的稱為最小截集。§8.4.2(Fold—Fulkerson)定義21容量網(wǎng)絡(luò)G，若為網(wǎng)絡(luò)中從vs到vt的一條鏈，給定向?yàn)閺膙s到vt，上的邊凡與方向相同的稱為前向邊，凡與方向相反的稱為后向邊，其集合分別用和表示，f是一個(gè)可行流，如果滿足：則稱為從vs到vt的（關(guān)于f的）一條可增廣鏈。定理6設(shè)f為網(wǎng)絡(luò)G=（V，E，C）的任一可行流，流量為W，為任一截集，則有。由定理可知，如果網(wǎng)絡(luò)上的一個(gè)可行流和網(wǎng)絡(luò)中的一個(gè)截集，滿足條件，那么f*一定是D上的最大流，而一定是G的最小截集。定理7（Fold—Fulkerson定理）在任何網(wǎng)絡(luò)中，從到的最大流的流量等于最小截集的容量。推論可行流f是最大流的充分必要條件是不存在從vs到vt的（關(guān)于f的）一條可增廣鏈?！?.4.3標(biāo)號法是從網(wǎng)絡(luò)中的一個(gè)可行流f出發(fā)（如果D中沒有可行流f，可以令f是零流），運(yùn)用標(biāo)號法，經(jīng)過標(biāo)號過程和調(diào)整過程，可以得到網(wǎng)絡(luò)中的一個(gè)最大流。一、標(biāo)號過程：1.給發(fā)點(diǎn)vs標(biāo)號（0，+∞）。2.取一個(gè)已標(biāo)號的點(diǎn)vi，對于vi一切未標(biāo)號的鄰接點(diǎn)vj按下列規(guī)則處理：（1）如果邊，且，那么給vj標(biāo)號，其中：（2）如果邊，且，那么給vj標(biāo)號，其中：。3.重復(fù)步驟（2），直到被標(biāo)號或標(biāo)號過程無法進(jìn)行下去，則標(biāo)號法結(jié)束。若被標(biāo)號，則存在一條可增廣鏈，轉(zhuǎn)調(diào)整過程（第二步）；若未被標(biāo)號，而標(biāo)號過程無法進(jìn)行下去，這時(shí)的可行流就是最大流。二、調(diào)整過程設(shè)是一條從到的可增廣鏈，的前向邊和后向邊分別用和表示。設(shè)，，如果上沒有后向弧，則令，取1．令2．去掉所有標(biāo)號，回到第一步，對可行流重新標(biāo)號。

第31次課2學(xué)時(shí)上次課復(fù)習(xí)：最大流問題的概念最大流問題的解法截集的概念本次課題（或教材章節(jié)題目）：§8.5最小費(fèi)用流問題教學(xué)要求：掌握最小費(fèi)用流問題的概念、求解方法重點(diǎn)：基本概念、最小費(fèi)用流問題的求解方法難點(diǎn)：最小費(fèi)用流問題的求解方法教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：最小費(fèi)用流問題的基本概念 25分鐘最小費(fèi)用流問題求解方法 75分鐘課后作業(yè)P26815、參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁§8.5最小費(fèi)用流問題定義23已知網(wǎng)絡(luò)G=（V，A，C，d），是G上的一個(gè)可行流，為一條（關(guān)于的）從vs到vt的可增廣鏈，稱為鏈的費(fèi)用。若*是從vs到vt的可增廣鏈中費(fèi)用最小的鏈，則稱*是最小費(fèi)用可增廣鏈。結(jié)論：如果可行流f在流量為W(f)的所有可行流中的費(fèi)用最小，并且*是關(guān)于f的所有增廣鏈中的費(fèi)用最小的增廣鏈，那么沿增廣鏈*調(diào)整可行流f，得到的新可行流f*也是流量為W(f*)的所有可行流中的最小費(fèi)用流。依次類推，當(dāng)f*是最大流時(shí)，就是所要求的最小費(fèi)用流。算法的基本思路為：先找一個(gè)流量為的最小費(fèi)用流，然后尋找從vs到vt的可增廣鏈，用最大流的方法將調(diào)整到，使的流量為，且保證是在下最小的費(fèi)用流，再對重復(fù)上述步驟。因?yàn)?，顯然，零流f={0}是流量為0的最小費(fèi)用流。一般地，尋求最小費(fèi)用流，總可以從零流={0}開始。下面的問題是：如果已知f是流量為W(f)的最小費(fèi)用流，如何尋找關(guān)于f的最小費(fèi)用增廣鏈？對此，重新構(gòu)造一個(gè)賦權(quán)有向圖，其頂點(diǎn)是原網(wǎng)絡(luò)G的頂點(diǎn)，而將G中的每一條邊(vi,vj)變成兩個(gè)相反方向的邊（vi，vj）和(vj,vi)，并且定義圖中邊的權(quán)為：1.當(dāng)邊，令（其中的含義為：這條邊已經(jīng)飽和，不管付出多大代價(jià)，也不能再增大流量，權(quán)為的邊可從網(wǎng)絡(luò)中去掉。）2.當(dāng)邊為原來網(wǎng)絡(luò)G中邊（vi，vj）的反向邊，令其中的含義為：此邊流量已經(jīng)減少到0，不能再減少，權(quán)為的邊可從網(wǎng)絡(luò)中去掉。這樣，在網(wǎng)絡(luò)G中尋找關(guān)于f的最小費(fèi)用可增廣鏈就等價(jià)于在L(f)中尋求從vs到vt的最短路。其算法步驟為：（1）取零流為初始可行流，f(0)={0}。（2）一般地，如果在第步得到最小費(fèi)用流，則構(gòu)造圖L(f(k-1))。（3）在圖L(f(k-1))中，尋求從vs到vt的最短路。若不存在最短路，則就是最小費(fèi)用最大流，停止計(jì)算；否則轉(zhuǎn)（4）。（4）如果存在最短路，則在可行流f(k－1)的圖中得到與此最短路相對應(yīng)的可增廣鏈，在可增廣鏈上，對進(jìn)行調(diào)整，調(diào)整量為：令則得到新可行流。對重復(fù)上面的步驟，返回步驟（2）。

第32次課2學(xué)時(shí)上次課復(fù)習(xí)：最小費(fèi)用流問題的概念最小費(fèi)用流問題的求解方法本次課題（或教材章節(jié)題目）：§8.6中國郵遞員問題補(bǔ)充習(xí)題教學(xué)要求：掌握中國郵遞員問題的解法重點(diǎn)：奇偶圖上作業(yè)法難點(diǎn)：奇偶圖上作業(yè)法教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：歐拉回路與道路 15分鐘奇偶圖上作業(yè)法 35分鐘補(bǔ)充習(xí)題 50分鐘課后作業(yè)P26816、參考資料《運(yùn)籌學(xué)》 錢頌迪主編清華大學(xué)出版社《運(yùn)籌學(xué)教程》 胡運(yùn)權(quán)主編清華大學(xué)出版社《運(yùn)籌學(xué)》 牛映武主編西安交大出版社《運(yùn)籌學(xué)應(yīng)用案例》 陶謙坎主編機(jī)械工業(yè)出版社注：本頁為每次課教案首頁§8.6中國郵遞員問題問題的提出：一個(gè)郵遞員從郵局出發(fā)，要走遍他所負(fù)責(zé)的每條街道去送信，問應(yīng)當(dāng)如何選擇適當(dāng)?shù)穆肪€，可使所走的總路程最短?！?.5.1歐拉回路與道路定義24連通圖G中，若存在一條道路，經(jīng)過每邊一次且僅一次，則稱這條路為歐拉道路。若存在一條回路，經(jīng)過每邊一次且僅一次，則稱這條回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖。定理8一個(gè)多重連通圖G是歐拉圖的充分必要條件是G中無奇點(diǎn)。定理9一個(gè)多重連通有向圖G是歐拉圖的充分必要條件是它每個(gè)頂點(diǎn)的出次等于入次?！?.5.2奇偶圖上作業(yè)法計(jì)算步驟如下：（1）找出圖G中的所有的奇頂點(diǎn)（必有偶數(shù)個(gè)，如無奇點(diǎn)，則已是歐拉圖，找出歐拉回路即可），所以如果一個(gè)連通圖有奇點(diǎn)，就可以把它們兩兩配成對，而每對奇點(diǎn)之間必有一條通路（圖是連通的），我們把這條通路上的所有邊作為重復(fù)邊追加到圖中去，這樣得到的新連通圖必?zé)o奇點(diǎn)。（2）如果邊上的重復(fù)邊多于一條，則可從的重復(fù)邊中去掉偶數(shù)條，使得其重復(fù)邊至多為一條，圖中的頂點(diǎn)仍全部都是偶頂點(diǎn)。（3）檢查圖中的每一個(gè)圈，如果每一個(gè)圈的重復(fù)邊的總長不大于該圈總長的一半，則已經(jīng)求得最優(yōu)方案。如果存在一個(gè)圈，重復(fù)邊的總長大于該圈總長的一半時(shí)，則進(jìn)行調(diào)整：將這個(gè)圈中的重復(fù)邊去掉，再將該圈中原來沒有重復(fù)邊的各邊加上重復(fù)邊，其它各圈的邊不變，返回步驟（2）。通常用來判別最優(yōu)路線的判別標(biāo)準(zhǔn)為：判定標(biāo)準(zhǔn)1:在最優(yōu)郵遞路線上，圖中的每一條邊至多有一條重復(fù)邊。判定標(biāo)準(zhǔn)2:在最優(yōu)郵遞路線上，圖中每一個(gè)圈的重復(fù)邊的總權(quán)小于或者等于該圈總權(quán)的一半。一個(gè)最優(yōu)郵遞路線一定滿足判定標(biāo)準(zhǔn)1和判定標(biāo)準(zhǔn)2。反之，不難證明，一個(gè)郵遞路線如果滿足判定標(biāo)準(zhǔn)1和判定標(biāo)準(zhǔn)2，那么它一定是最優(yōu)郵遞路線。以上的過程可以表述為：先分奇偶點(diǎn)，奇點(diǎn)對對連，連線不重疊，重疊需改變，圈上連線長，不得過半圈。本章小結(jié)本章共分六節(jié)內(nèi)容。第一節(jié)介紹了關(guān)于圖的各種定義，這是本章的重點(diǎn)內(nèi)容，只有弄清第一節(jié)的概念，才是學(xué)好后面五節(jié)的關(guān)鍵。同時(shí)還要正確理解本章所介紹的圖與一般的幾何圖形、工程制圖區(qū)別。第二節(jié)中主要介紹了樹的有關(guān)概念和應(yīng)用。第三節(jié)介紹了最短路問題及求解最短路的Dijkstra算法和逐次逼近法，用來解決不同條件下的最短路問題。在第四節(jié)中介紹了求最大流問題的標(biāo)號算法。而如何在考慮流量的同時(shí)，考慮到流量的費(fèi)用，就是第五節(jié)介紹的求最小費(fèi)用流的問題。第六節(jié)在介紹歐拉圈和歐拉道路的基礎(chǔ)上，給出了中國郵遞員問題的解法。而學(xué)會如何把一些實(shí)際問題與圖聯(lián)系起來并用圖描述，然后用我們介紹的方法把問題優(yōu)化，是我們學(xué)習(xí)本章的真正目的。

第33次課2學(xué)時(shí)上次課復(fù)習(xí)：圖與網(wǎng)絡(luò)分析主要內(nèi)容回顧：最短路問題最大流問題中國郵遞員問題本次課題（或教材章節(jié)題目）：第九章網(wǎng)絡(luò)計(jì)劃§9.1網(wǎng)絡(luò)圖§9.2關(guān)鍵路線與時(shí)間參數(shù)教學(xué)要求：掌握網(wǎng)絡(luò)圖的繪制、關(guān)鍵路線與時(shí)間參數(shù)的求解方法重點(diǎn)：關(guān)鍵路線與時(shí)間參數(shù)的求解方法難點(diǎn)：關(guān)鍵路線的求解方法教學(xué)手段及教具：多媒體教學(xué)。講授內(nèi)容及時(shí)間分配：§9.1網(wǎng)絡(luò)圖§9.1.1畫網(wǎng)絡(luò)圖的規(guī)則 §9.1.2繪制網(wǎng)絡(luò)圖 §9.1.3網(wǎng)絡(luò)圖分類 §9.2關(guān)鍵路線與時(shí)間參數(shù)§9.2.1路與關(guān)鍵路線