運籌學教案(胡運權(quán)版)

土木工程與建筑學院教師備課紙第．當目標函數(shù)變（=2\*romanii），就是要了解第三優(yōu)先級中兩目標權(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二.課堂練習（20分鐘）三.課堂小結(jié)（5分鐘）四.布置作業(yè)授課題目：第五章整數(shù)規(guī)劃第一節(jié)：整數(shù)規(guī)劃的數(shù)學模型及解的特點第三節(jié)：分支定界法教學目的與要求：1.知識目標：掌握整數(shù)規(guī)劃的概念、類型和作用及其求解方法概述；掌握分支定界法的基本概念與求解思路；2.能力目標：掌握分支定界法的求解步驟；3.素質(zhì)目標：培養(yǎng)學生良好的職業(yè)道德、樹立愛崗精神教學重點：1、分支定界法的基本概念；2、分支定界法的操作原理與步驟。教學難點：1、分支與定界的方法；2、圖解法在分支定界法中的應(yīng)用。教學過程：1.舉例引入（5分鐘）2.新課講解（80分鐘）（1）分支與定界原則與方法（20分鐘）（2）分支定界法操作步驟（40分鐘）（3）學生操作（20分鐘）3.課堂小結(jié)（5分鐘）5.布置作業(yè)《整數(shù)規(guī)劃：定義、類型、求解綜述和分支定界法》（2課時）【教學流程圖】舉例引入整數(shù)規(guī)劃整數(shù)規(guī)劃的定義與分類整數(shù)規(guī)劃的定義、分類與求解綜述整數(shù)規(guī)劃的松馳問題整數(shù)規(guī)劃的幾種求解方法分支方法定界方法分支定界法的求解過程解的搜索法最優(yōu)解的確定課堂練習（結(jié)合例題講解進行）課堂小結(jié)布置作業(yè)【教學方法】本課主要采用任務(wù)驅(qū)動和程序式思維相結(jié)合的教學方法，過程當中輔以案例講解、啟發(fā)提問、自主學習和協(xié)作學習等方式。任務(wù)驅(qū)動是實現(xiàn)本課教學目標和完成教學內(nèi)容的主要方法，任務(wù)是師生活動內(nèi)容的核心，在教學過程中，任務(wù)驅(qū)動被多次利用。自主學習能提高學生的自主探究能力，競賽和協(xié)作學習調(diào)動學生的積極性，激發(fā)學生參與的熱情。學生之間互幫互助，共同分享勞動果實，從而激發(fā)了學生的團隊意識，達到理想的教學效果?！窘虒W內(nèi)容】一、教學過程：舉例引入整數(shù)規(guī)劃：（5分鐘）（1）整數(shù)規(guī)劃的定義（2）整數(shù)規(guī)劃的分類（3）整數(shù)規(guī)劃的求解綜述導(dǎo)入提問：怎樣運用分支定界法？（二）新課：第五章整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學模型及解的特點一、整數(shù)規(guī)劃的定義與分類二、整數(shù)規(guī)劃的求解方法綜述第三節(jié)分支定界法主要思路1、要求一部分或全部決策變量必須取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃。不考慮整數(shù)條件，其相對應(yīng)的線性規(guī)劃問題叫該整數(shù)規(guī)劃的松弛問題。求解整數(shù)規(guī)劃時，首先求解與它相對應(yīng)的松弛問題，如果它的松弛問題的最優(yōu)解滿足整數(shù)要求，則得該整數(shù)規(guī)劃的最優(yōu)解，否則通過增加新的函數(shù)約束來縮小其松弛問題的可行域，將原整數(shù)規(guī)劃模型分為兩個子規(guī)劃模型，并除去可行域中的無整數(shù)解的部分，達到分枝的目的。然后對每一個子規(guī)劃模型的松弛問題再求解，以此類推，并不斷定界，最后求得原問題的最優(yōu)解。2、分枝的方法：選擇目標函數(shù)中系數(shù)絕對值最大的變量先分枝；選擇與整數(shù)值相差最大的非整數(shù)變量先分枝；人為地按變量的相對重要性進行選擇。3、定界與剪枝1）定界方法：①求解整數(shù)規(guī)劃時，如果解它的松弛問題得到的不是一個整數(shù)解，則最優(yōu)整數(shù)解一定不會優(yōu)于所得松弛問題的目標函數(shù)值，即松弛問題的的解必是整數(shù)規(guī)劃問題的目標函數(shù)值的一個界，它對于最大值問題是上界，對于最小值問題是下界。②如果在求解整數(shù)規(guī)劃的松弛問題的過程中已經(jīng)得到了一個整數(shù)解，則最優(yōu)整數(shù)解一定不會劣于該整數(shù)解，因此該整數(shù)解可構(gòu)成最優(yōu)整數(shù)解的另一個界，對于最大化問題它為下界，對于最小化問題它為上界。③以上討論可用不等式表示如下：松弛問題的解；目前已找到的整數(shù)解，最優(yōu)整數(shù)解；上界，下界。則最優(yōu)整數(shù)解滿足：對于最大化問題：；對于最小化問題：。顯然如能找到一種方法，或降低上界或提出高下界，最后使得上界等于下界，就可以搜索得到最優(yōu)整數(shù)解。2）求解任何一個問題或子問題都有三種結(jié)果：子問題無可行解，此時無須繼續(xù)向下分枝，將其剪枝；得到一個非整數(shù)解，繼續(xù)向下分枝；如得到一組整數(shù)解，則不必繼續(xù)向下分枝，因該點有整數(shù)解而被關(guān)閉。二、例題分析例1求解下列整數(shù)規(guī)劃：G(4.81，1.82）G(4.81，1.82）第一步：用圖解法求出原整數(shù)規(guī)劃問題的松馳問題的解。對=4.81按和進行分支，得到原整數(shù)規(guī)劃問題的松馳問題的兩個子松馳問題如下。然后對原整數(shù)規(guī)劃問題的松馳問題進行定界（上界與下界）。兩個子問題由原問題的松馳問題分別加上分支的兩個約束條件組成，再用圖解法求出它們的解。和54G(4.81，1.82）54G(4.81，1.82）第二步：根據(jù)對節(jié)點分支的三種情況：剪支、停止分支和繼續(xù)分支，對上述兩個子問題進行繼續(xù)分支。又分別得到兩個子問題。如此下去，是否無窮次分支？需由定界來確定。第三步：最后如果得到一個整數(shù)解，即為最優(yōu)整數(shù)解；如得到幾個整數(shù)解，取目標函數(shù)值最大者為最優(yōu)整數(shù)解。問題B 問題B1問題B2問題B3問題B4問題B5問題B6問題B1問題B2問題B3問題B4問題B5問題B6三、課堂小結(jié)四、學生作業(yè)，安排下次課內(nèi)容。授課題目：第五章整數(shù)規(guī)劃第二節(jié)：解整數(shù)規(guī)劃的割平面法教學目的與要求：1.知識目標：掌握解整數(shù)規(guī)劃的割平面法的概念與求解思路；2.能力目標：掌握解整數(shù)規(guī)劃的割平面法的求解步驟；3.素質(zhì)目標：培養(yǎng)學生良好的職業(yè)道德、樹立愛崗精神教學重點：1、割平面法的概念與求解思路；2、割平面法的操作原理與步驟。教學難點：1、割平面法的概念與求解思路；2．單純形表的最終表結(jié)構(gòu)；2、割平面法的操作原理與步驟。教學過程：1.舉例引入（5分鐘）2.新課講解（80分鐘）（1）割平面法的概念（20分鐘）（2）割平面法的求解思路（20分鐘）（3）割平面法的求解步驟（20分鐘）（3）學生操作（20分鐘）3.課堂小結(jié)（5分鐘）5.布置作業(yè)《整數(shù)規(guī)劃：割平面法》（2課時）【教學流程圖】舉例引入整數(shù)規(guī)劃的割平面法解整數(shù)規(guī)劃的割平面法的基本思路單純形法的最優(yōu)表的結(jié)構(gòu)割平面方程的確定解整數(shù)規(guī)劃的割平面求解過程插入割平面約束的單純形表對偶單純形法用割平面方程求解整數(shù)規(guī)劃時解的收斂性課堂練習（結(jié)合例題講解進行）課堂小結(jié)布置作業(yè)【教學方法】本課主要采用任務(wù)驅(qū)動和程序式思維相結(jié)合的教學方法，過程當中輔以案例講解、啟發(fā)提問、自主學習和協(xié)作學習等方式。任務(wù)驅(qū)動是實現(xiàn)本課教學目標和完成教學內(nèi)容的主要方法，任務(wù)是師生活動內(nèi)容的核心，在教學過程中，任務(wù)驅(qū)動被多次利用。自主學習能提高學生的自主探究能力，競賽和協(xié)作學習調(diào)動學生的積極性，激發(fā)學生參與的熱情。學生之間互幫互助，共同分享勞動果實，從而激發(fā)了學生的團隊意識，達到理想的教學效果?！窘虒W內(nèi)容】一、教學過程：舉例引入整數(shù)規(guī)劃：（5分鐘）（1）整數(shù)規(guī)劃的定義（2）整數(shù)規(guī)劃的分類（3）整數(shù)規(guī)劃的求解綜述導(dǎo)入提問：怎樣運用分支定界法？（二）新課：一、割平面法（一）基本原理線性規(guī)劃的任一約束方程是n維空間的一個半平面，故先用單純形法解它的松弛問題得最優(yōu)解，若滿足整數(shù)向量，則的最優(yōu)解。若不全為整數(shù)，則設(shè)法給松弛問題增加一個線性約束條件（叫割平面方程），它將松弛問題的可行域割去一塊，且這個非整數(shù)解恰恰在被割掉的區(qū)域內(nèi)，但原問題的任何一個可行解都不會被割去。若把原松弛問題的最優(yōu)單純形表記為，把增加了割平面方程的問題記為，為原問題的一個改進的松弛問題，用對偶單純形法求解，若得到的最優(yōu)解為整數(shù)向量，則計算結(jié)束，否則對再增加一個割約束，形成問題，…，直到得到最優(yōu)整數(shù)解。（二）例題分析例1用割平面法求解純整數(shù)規(guī)劃：解1、松弛問題的單純形表為：目標函數(shù)1100常數(shù)決策變量基變量最優(yōu)表11013/41/410-1/41/47/43/400-1/2-1/2-5/22、求割平面方程割平面方程并不惟一，一般取基變量的小數(shù)部分具有最大絕對值的變量所在行的約束方程為導(dǎo)出方程，能夠更快地得出最優(yōu)整數(shù)解。這里選取第二個約束，寫出約束方程：（1）將上式左邊的非基變量的系數(shù)和右端常數(shù)寫成一個整數(shù)和一個非負真分數(shù)之和：（2）把上式系數(shù)為真分數(shù)的各項移到等式右端，將整數(shù)移到左端：（3）因為整數(shù)，原整數(shù)規(guī)劃約束條件中各系數(shù)和右端常數(shù)也為整數(shù)，所以也為整數(shù)。由于上式左邊為整數(shù)，右邊也應(yīng)為整數(shù)。又，由于從所以3/4減去兩個正數(shù)必有：（4）得：（因上式左邊為整數(shù)）（5）為避免引入工變量，將上式改寫成：（6）加入松弛變量，化為等式約束：（7）（6）式和（7）式分別為割平面約束條件和割平面約束方程。將（7）式添加到原的約束條件中，得：由靈敏度分析可知，增加一個割平面約束，只需把（7）式加入最優(yōu)表作為第3行，由于為基變量，它的檢驗數(shù)為0，而原來的各變量的檢驗數(shù)和目標值均保持不變。現(xiàn)用對偶單純形法求解如下：目標函數(shù)11000常數(shù)決策變量基變量↓原最優(yōu)表110013/41/4010-1/41/4000[-3/4]-1/417/43/4-3/4→00-1/2-1/20新最優(yōu)表110010001001/3-1/30011/3-4/3111000-1/3-2/3二、學生練習（結(jié)合例題講解進行）三、課程小結(jié)四．布置下次課的教學內(nèi)容授課題目：第五章整數(shù)規(guī)劃第四節(jié)指派問題教學目的：掌握整數(shù)規(guī)劃的指派問題求解的步驟。教學要求：要求與學生與教師配合能操作上次課的例1。教學重點：掌握整數(shù)規(guī)劃指派問題的求解原則。教學難點：整數(shù)規(guī)劃指派問題求解中匈牙利法的步驟。教學手段與方法：先用實例引入，再采用比較演示方法。實例引入例1有一項說明書要由漢語分別譯成英、日、德、俄四種文字，交由甲、乙、丙、丁4個譯員去完成。因各人專業(yè)不同，因此譯成不同文字所需要的時間不同。假設(shè)各人完成各項工作的時間如下表，問應(yīng)如何分配才能完成4項給定任務(wù)的總時間最少？工作譯員1234（漢譯英）（漢譯日）（漢譯德）（漢譯俄）甲乙丙丁3109715414813141611415139解用0-1模型，1分配第i人做第j件工作0不分配第i人做第j件工作那么有：s.t.定理1如果從分配效率矩陣[]的每一行元素分別加（減）一個常數(shù)，從每一列元素分別加（減）一個常數(shù)，得到新的效率矩陣[]的最優(yōu)解等價于原效率矩陣的最優(yōu)解。定理2若某矩陣A中的元素分為零元素和非零元素兩部分，則覆蓋零元素的最少直線數(shù)等于位于不同行不同列的零元素（稱為獨立零元素）的最大個數(shù)。此定理告訴了效率表中有多少獨立零元素的辨別方法。二、指派問題的匈牙利解法第一步轉(zhuǎn)換效率矩陣[]，使各行各列都有出現(xiàn)零元素從每行元素減去該行最小元素；再從所得的效率矩陣每列減去該列的最小元素。若某行（列）已有零元素，就不必再減了。上例中：3109707640714=154148=110104=1105413141611235023004151390119501145第二步試求最優(yōu)解，找出m個獨立零元素1、從第一行開始，遇到每行只有一個零元素就用括號括上，記作（0），然后劃去其所在列的其他零元素，用○表示，遇到有兩個及其以上零元素的行先跳過去；2、進行列檢驗，從第一列開始，給只有一個零元素的列中的那個零元素用括號括上，然后劃去它所在行中的其它零元素。反復(fù)進行1、2步，直到所有零元素被劃去或括上為止。3、以上已劃去或括上的零元素不算在內(nèi)。經(jīng)過第二步以后，會出現(xiàn)三種情況：其一、打上括號的零元素分布在不同的行與列，且其個數(shù)等于系數(shù)矩陣的階n，即得最優(yōu)解。令其對應(yīng)的1，其余的為0；其二、仍存在未括上與劃去的零元素，且同行（列）的零元素至少有兩個（即零元素形成閉回路），這時從含零元素最少的行（列）開始，比較該行（列）各零元素所在列（行）中零元素的個數(shù)，選擇含零元素最少的那一列（行）的這個零元素加上括號，然后劃去與這個零元素同行同列的其它零元素。如此反復(fù)進行，直到所有零元素被劃去或括上為止。其三、經(jīng)過以上幾步后，若被括上的零元素數(shù)目等于系數(shù)矩陣的階n，即得最優(yōu)解，否則進入第三步。上例：（0）71411（0）5423（0）○○1145第三步增加零元素1、作能覆蓋所有零元素（指括上的和劃去的零元素）的最少直線，其數(shù)目等于加括號的零元素個數(shù)。方法：1）對沒有（0）的行打√；2）對打√的行上所有○元素所在的列打√；3）再對打√的列上所有（0）元素所在的行打√。重復(fù)2）和3），直到得不出新的打√的行和列。4）對沒有打√的行畫橫直線，對所有打√的列畫縱直線，得到能覆蓋所有零元素的直線。（0）71411（0）5423（0）○○11452、再對系數(shù)矩陣進行變換，以增加零元素對沒有被直線覆蓋的部分找出最小元素，對沒有畫直線的行中所有非零元素各減去，對畫直線的列中所有非零元素各加上，并保持原來零元素（劃去和打括號的）不變，得到新的系數(shù)矩陣。第四步對新的系數(shù)矩陣又從第二步開始，若能求n個不同行與列的零元素，即得最優(yōu)解，否則又進入第三步：增加零元素。060306031105412054230033000103401034本例又從第二步開始：○6（0）312（0）5433○（0）（0）1034授課題目：第七章動態(tài)規(guī)劃

第一節(jié)多階段決策過程的最優(yōu)化

第二節(jié)動態(tài)規(guī)劃的基本概念和基本原理教學目的：掌握動態(tài)規(guī)劃的基本概念、基本思想和模型特點。教學要求：要求與學生與教師配合能操作上次課的例1。教學重點：掌握動態(tài)規(guī)劃的基本思想和模型特點。教學難點：動態(tài)規(guī)劃的逆序解法和順序解法。教學手段與方法：先用實例引入，再采用比較演示方法。第七章動態(tài)規(guī)劃一、動態(tài)規(guī)劃的基本概念動態(tài)規(guī)劃是解決多階段決策各過程最優(yōu)化問題的一種數(shù)學規(guī)劃的方法。二、基本概念1、階段：按時間/空間分解成若干相互聯(lián)系的段落，用…表示。2、狀態(tài)：各階段開始時的客觀條件，用狀態(tài)變量表示，的取值集合用表示，不具備無后效性的變量不能作狀態(tài)變量；當某階段的狀態(tài)給定以后，這階段以后過程的發(fā)展只受該階段狀態(tài)的影響，而與該階段以前的狀態(tài)無關(guān)，狀態(tài)的這一性質(zhì)叫無后效性3、決策和策略當各階段的狀態(tài)給定以后，就可以做出不同決定選擇，從而確定下一階段的狀態(tài)，這種選擇決定叫做決策，用表示第階段的當狀態(tài)為時的決策變量，其取值在一定范圍內(nèi)，此范圍叫允許決策集合，用表示，因此有整個問題的決策序列叫策略。用表示。4、狀態(tài)轉(zhuǎn)移方程用表示第階段的狀態(tài)是第階段的狀態(tài)和決策變的函數(shù)。5、指標函數(shù)用來衡量所選定策略優(yōu)劣的數(shù)量指標。用表示。三、動態(tài)規(guī)劃求解的基本思想把一個多目標決策劃分為若干階段，恰當?shù)剡x取狀態(tài)變量和決策變量及定義最優(yōu)指標函數(shù)，從而把整個決策問題分解為一簇同類型的子問題，再從邊界條件開始，逆（或順）過程行進方向，逐段遞推求出最優(yōu)解。順推法：逆推法：動態(tài)規(guī)劃在經(jīng)濟管理中的應(yīng)用（一）背包問題1、基本模型一維背包：一位旅行者能承受重量bkg,，現(xiàn)有n種物品供他選擇裝入背包，第物品的單件重量為,總價值是攜帶數(shù)量的函數(shù)，求應(yīng)如何選擇攜帶物品的件數(shù)使總價值最大？二維背包：如增加到兩個約束條件，如背包體積限限制為立方米，并假設(shè)第i種物品每件體積為立方米，應(yīng)如何選擇攜帶物品的件數(shù)使總價值最大？模型：一維背包二維背包2、求解方法：①階段序，每時間段裝入一種物品，那么共需個時間段。②狀態(tài)變量表示第第階段開始時允許裝入前種物品的總重量，有，因已知，故用順序解法。③決策變量種物品的件數(shù)。④狀態(tài)轉(zhuǎn)移方程：⑤允許的決策集合是︱，為整數(shù)}，式中為不超過的最大整數(shù)。這里的最大值表示只裝運第種物品，其余-1種物品的裝運量為0。⑥最優(yōu)指標函數(shù)表示在背包中允許裝入物品的總重量不超過公斤時背包中允許裝入第1-種物品的最大使用權(quán)用價值。⑦于是得到動態(tài)規(guī)劃的順序遞推方程：階段指標為，遞推方程為：例1貨物裝載問題L準備在一艘貨船上裝載3種貨物，每箱重量和單價見下表，貨物總載重為7t，求3種貨物各裝多少箱才使總價值最大？貨物編號123每箱重量345每箱價值456解：1、012356789100000101012012012012301230000404048048048048120481200044888121200011222332、012345678910000001010101012012012000005050505051005100510=-012340506172830940105000044040808484012401280+00044545858989101291012131000045589101213000110102021210310320000011012013、0123456789100000001010101010120000006060606060612=-01235506102839410505588101251350+5581012131112130由=13，對應(yīng)=10，=0；由=-=-0*5=10，此時=1；由=-=10-4*1=6，對應(yīng)=2。3、總結(jié)建立動態(tài)規(guī)劃模型的步驟：1）劃分階段2）確定狀態(tài)變量及其取值范圍：原則是它能描述過程演變的狀態(tài)，又滿足無后效性的要求；3）確定決策變量及其取值范圍；4）建立狀態(tài)轉(zhuǎn)移方程，必須具有遞推關(guān)系；5）確定階段效應(yīng)函數(shù)，建立動態(tài)規(guī)劃的函數(shù)方程：函數(shù)方程是動態(tài)規(guī)劃最優(yōu)指標的函數(shù)形式，一種為加法型，一種為乘法型。階段效應(yīng)函數(shù)可以為收益函數(shù)（利潤、產(chǎn)量等），也可為損失函數(shù)（成本）。第階段的最優(yōu)指標函數(shù)是從第階段到第n階段單調(diào)遞增或遞減的總效應(yīng)。授課題目：第三節(jié)動態(tài)規(guī)劃模型的建立與求解教學目的：掌握動態(tài)規(guī)劃中的生產(chǎn)與存貯問題求解的步驟。教學要求：要求與學生與教師配合能操作上次課的例1。教學重點：掌握生產(chǎn)與存貯問題的求解原則。教學難點：生產(chǎn)與存貯問題的求解步驟。教學手段與方法：先用實例引入，再采用比較演示方法。況課后小結(jié)：例2某工廠生產(chǎn)并銷售某種產(chǎn)品，已知今后四個月的市場需求量預(yù)測如下表：階段（月）1234需求量2324單位生產(chǎn)成本為：03+1·…，6已知該廠最大的庫存容量為3單位，每月最大生產(chǎn)能力為6單位，并假設(shè)第+1個月的庫存量為第個月可銷售量（等于第個月庫存量與生產(chǎn)量之和）與該月用戶需求量之差。每批產(chǎn)品的固定生產(chǎn)成本為3千元，不生產(chǎn)時設(shè)固定生產(chǎn)成本為0元，單位產(chǎn)品的生產(chǎn)變動成本為1千元，每月單位產(chǎn)品的庫存費用為0.5千元。試制訂4個月的生產(chǎn)計劃，在滿足用戶需求條件下實現(xiàn)總費用最?。磸牡?月初至第4月末的總生產(chǎn)成本最小）。解：1、分析：階段為月；狀態(tài)變量為第月初的庫存量，其取值范圍為0，1，2，3；決策變量月的生產(chǎn)量：當≥時，可以為0；當時，至少應(yīng)生產(chǎn)；由于每月最大生產(chǎn)能力為6，故6，而第月末（第月初）的庫存為，其小于等于第月最大庫存量故有：，。故有允許決策集：（1）狀態(tài)轉(zhuǎn)移方程逆推基本方程：由于每月的庫存量是前一月庫存量的函數(shù)，故采用逆推，指標函數(shù)為第月狀態(tài)為時，采用最佳生產(chǎn)，從第月初到第4月末的總成本。上式中生產(chǎn)成本+庫存成本=+0.50，若各階段的允許狀態(tài)集合和允許決策集合：={0，1，2，3}，其中={0}，={0，1，2，3}。上式中第4個月因為=0，即。2、逆推表：1）的分布，由公式（1）得下表1：表10123{3，4，5，6}{2，3，4，5}{1，2，3，4}{0，1，2，3}0123{2，3，4，5}{1，2，3，4}{0，1，2，3}{0，1，2}012343212）=4表2=4遞推表狀態(tài)（期末庫存）決策（可能生產(chǎn)量）本期費用總費用生產(chǎn)費用庫存費用合計043+4=70.5*077133+3=60.5*16.56.5223+2=50.5*266313+1=40.5*35.55.5遞推方程為：。3）=3遞推方程為：對=0，1，2，3分別求出表3=3遞推表狀態(tài)決策本期費用期末庫存=以后各期最小費用總費用生產(chǎn)費用庫存費用合計02345567800005678012376.565.5121123445670.50.50.50.54.55.56.57.5012376.565.511.520123045611111567012376.565.5830120451.51.51.51.55.56.51236.56.05.584)=2表3=2遞推表狀態(tài)決策本期費用期末庫存=以后各期最小費用總費用生產(chǎn)費用庫存費用合計0345667890000678901231211．588161234556780.50.50.50.55．56．57．58．501231211．58815.52123445671111567801231211．588153012304561．51．51．51．51．55．56．57．501231211．58813.55）=1表4=1遞推表合計0012323455678000056781615.51513.5567821授課題目第四節(jié)動態(tài)規(guī)劃在經(jīng)濟管理中的應(yīng)用教學目的：掌握動態(tài)規(guī)劃中貨郎擔問題求解的步驟。教學要求：要求與學生與教師配合能操作上次課的例1。教學重點：掌握貨郎擔問題的求解原則。教學難點：貨郎擔問題求解的步驟。教學手段與方法：先用實例引入，再采用比較演示方法。況課后小結(jié)：求解方法貨郎擔問題的一般描述：一個貨郎從某村鎮(zhèn)出發(fā)，經(jīng)過若干個村鎮(zhèn)、，…，一次且僅一次，最后仍回到原出發(fā)的村鎮(zhèn)，已知從到的距離為，問應(yīng)如何選擇行走路線可使總行程最短？順推法分析：設(shè)S為從到中間所有可能經(jīng)過的村鎮(zhèn)之集合，但S中點的個數(shù)要隨階段數(shù)而改變。為從到經(jīng)過中間點的個數(shù)，以它來劃分階段。狀態(tài)變量（,S）表示從出發(fā)經(jīng)過S集合中所有村鎮(zhèn)一次最后到達。最優(yōu)指標函數(shù)表示從從出發(fā)經(jīng)過含個村鎮(zhèn)的S集合到的最短距離。,S）表示從出發(fā)經(jīng)過含個村鎮(zhèn)的S集合到的最短路線上鄰接的前一個村鎮(zhèn)。那么順推方程為：,,例1已知四個村鎮(zhèn)之間的距離如下表，求從某村鎮(zhèn)出發(fā)，經(jīng)過村鎮(zhèn)、，一次且僅一次，最后仍回到原出發(fā)的村鎮(zhèn)，問應(yīng)如何選擇行走路線可使總行程最短？0679809758086550解：（為方便起見，下面均以1，2，3，4代替、、、。）由邊界條件，。當=1（表示從出發(fā)經(jīng)過由一個村鎮(zhèn)組成的S集合到達的最短距離為：；；；上述計算中，由于S集合中只有一個村鎮(zhèn)，無需最小化。當=2（表示從出發(fā)經(jīng)過由二個村鎮(zhèn)組成的S集合到達的最短距離為，所以所以所以當=3（表示從出發(fā)經(jīng)過由三個村鎮(zhèn)組成的S集合到達的最短距離為所以逆過程遞推，————————，最短距離為23。2、順推法分析例22004年美國選舉活動前一周，位于紐約的候選人WalterGlenn先生必須訪問邁阿密、達拉斯和芝加哥三個城市，然后返回紐約。已知這些城市之間的距離如下表。WalterGlenn先生希望最小化他必須經(jīng)過的總距離，應(yīng)該以什么順序訪問這些城市？編號城市紐約邁阿密達拉斯芝加哥1234紐約邁阿密達拉斯芝加哥—133415598091334—1343130715591343—9218091397921—解：采用逆推法，按已經(jīng)訪問過的的城市數(shù)量來編號階段；在任意階段的狀態(tài)由上一次訪問過的城市和已經(jīng)訪問過的城市集組成。因為在任意階段要確定接下來要訪問哪一座城市需知道兩個事件：Walter當前所處的位置城市和他已經(jīng)訪問過的城市集C（其中在任意階段已經(jīng)訪問過的城市集C中有-1座城市），并規(guī)定為完成旅程所必須經(jīng)過的最短距離，為他目前處于城市與下一步將要訪問城市之間的距離。1、=4（階段4），這時這時狀態(tài)變量，狀態(tài)集={（2，{2，3，4}）、（3，{2，3，4}）、（4，{2，3，4}）}。，，。2、=3（階段3）由于Walter目前位于城市，并且將要到達城市，那么他需經(jīng)過的距離為。然后他將處于階段4，已經(jīng)訪問了城市，并且已經(jīng)訪問了中的每一個城市，因此他的剩余行程的距離將為。因此有：（）使用上公式時，注意Walter目前必須訪問了{2，3}或{2，4}或{3，4}，并且接下來必須訪問不等于1的非城市集C的城市。現(xiàn)用上式計算：一般來說，對于這里。因為如他現(xiàn)位于城市，并且接下來將要訪問城市，那么他需經(jīng)過的距離為。因此他的剩余的行程將從城市開始，，并且已經(jīng)訪問了中的每一個城市，因此剩余的行程距離必定為]。3、=2（階段2）在階段2，因為Walter只訪問了一個城市，因此唯一可能的狀態(tài)為（2，{2}）、（3，{3}）和（4，{4}）。4、=1（階段1）因此時Walter位于紐約，并且還沒有訪問過任何城市，因此狀態(tài)為，故有：因此，Walter可以從城市1到2或4，任意地使其選擇到4。然后必須選擇訪問可以得出的城市，這個城市要求Walter接下來訪問3。然后必須訪問可以得出的城市，這個城市要求Walter接下來訪問2。然后必須選取擇訪問可以得出的城市，這個城市要求Walter接下來訪問1。所以最優(yōu)行程為：1-4-3-2-1，長度為。授課題目：第八章圖與網(wǎng)絡(luò)分析第一節(jié)圖與網(wǎng)絡(luò)的基本知識教學目的：掌握圖與網(wǎng)絡(luò)的的基本知識。教學要求：要求學生掌握歐拉圖和中國郵遞員問題。教學重點：掌握歐拉圖和中國郵遞員問題。教學難點：中國郵遞員問題。教學手段與方法：先用實例引入，再采用比較演示方法。況第八章圖與網(wǎng)絡(luò)分析第一節(jié)圖與網(wǎng)絡(luò)的的基本知識一、引入：例1（數(shù)學家歐拉與圖）歐拉圖普瑞拉爾河從古城哥尼斯堡市中心流過，河中有小島兩座，筑有七座古橋，1736年，該市一市民向數(shù)學家提出一個問題：從家里出發(fā)，對七座橋每橋恰好通過一次，再回到家里，是否可行？分析：歐拉把兩岸分別用C、D表示，兩島分別用A、B表示。此問題是尋找一條遍歷多重圖每條邊恰好一次的回路，具有此性質(zhì)的多重圖叫歐拉圖，對應(yīng)的回路叫歐拉回路。AABCAB D二、圖與網(wǎng)絡(luò)的基本知識1、圖的定義圖是由點集和V中元素的無序?qū)Φ囊粋€集合組成的一個二元組，記為。1）頂點和邊2）關(guān)聯(lián)邊2、圖的分類1）有向圖和無向圖2）簡單圖與完全圖環(huán)和多重邊3）二部圖3、頂點的次1）孤立點2）懸掛點和懸掛邊4、子圖、支撐子圖和生成子圖5、網(wǎng)絡(luò)1）有向網(wǎng)絡(luò)和無向網(wǎng)絡(luò)2）權(quán)和最短路問題6、連通圖1）點邊序列和鏈、初等鏈2）圈和初等圈3）道路和回路對于無向圖，道路和鏈、回路和圈的意義相同。7、圖的兩個定理定理1任何圖中頂點次數(shù)的總和等于邊數(shù)的兩倍；定理2任何圖中次為奇數(shù)的頂點必有偶數(shù)個；三、圖的矩陣表示四、歐拉回路與中國郵路問題1、歐拉回路與歐拉圖歐拉注意到哥尼斯堡多重圖中每個結(jié)點的度都是奇數(shù)，因此圖中任何結(jié)點都不能作為起始結(jié)點，因為回路都是從某個結(jié)點出發(fā)，再回到該結(jié)點，然后再從該結(jié)點出發(fā)，再返回，如此循環(huán)，那么這個結(jié)點的度應(yīng)為偶數(shù)。歐拉定理：多重圖G是歐拉圖當且僅當G是連通的且每個結(jié)點的度是偶數(shù)。定理3無向連通圖G是歐拉圖，當且僅當G中無奇點。定理4連通有向圖G是歐拉圖，當且僅當每個頂點的出次等于入次。2、中國郵路問題例2中國郵遞員問題：中國郵遞員從郵局出發(fā)，經(jīng)過他所投遞范圍的每一條街道至少一次，完成投遞任務(wù)后返回郵局，問應(yīng)如何安排郵遞員的行走路線才能使總行程路線最短？解1）、如G是歐拉回路，Euler設(shè)計了一條求歐拉回路的算法：2）、對于非歐拉圖，郵遞員返回郵局必須將圖轉(zhuǎn)換成歐拉圖，為此需添加重復(fù)邊以清除奇次頂點，與奇點關(guān)聯(lián)的邊應(yīng)添加奇數(shù)條，與偶點關(guān)聯(lián)的邊應(yīng)添加偶數(shù)條（含0條），現(xiàn)在的問題是求解使重復(fù)邊總權(quán)重值最小的方案。具體方法；1）、如果在配送范圍內(nèi)，街道拐彎處沒有奇點，那么郵遞員可以從配送中心出發(fā)，走過每條街道一次且僅一次最后回到配送中心，他走的路徑為最短路徑。2）、對于有奇點的街道圖，必須在一些街道重復(fù)走一次或多次，這樣相當于我們在圖中如之間增加幾條重復(fù)邊，令每條重復(fù)邊的權(quán)與原來的邊的權(quán)相等，于是這條路線就是新圖中的歐拉圖，它使新圖不含奇點，并且重復(fù)邊的總權(quán)最小。這一方案分兩步（見下例）：例1一車輛從某配送中心出發(fā)，給街道上的7個超市-送貨，求使總行程最短的送貨方案。第一步：使新圖不含奇點而增加重復(fù)邊由圖論，在任何一個連通圖中，奇點個數(shù)必為偶數(shù)，所以如圖中有奇點，可把它們配對。又因為圖是連通的，故每一對奇點之間必有一條鏈，我們把這條鏈的所有邊作為重復(fù)邊加到圖中去，新圖中必無奇點。這就得出第一可行方案，即把使新圖不含奇點而增加的重復(fù)邊叫可行（重復(fù)邊）方案。圖1未加重復(fù)邊前的圖245336454494圖2將連接奇點和之間的一條鏈路加上重復(fù)邊245336454494在圖1中，將奇點和、和配對。對前者連接兩奇點的鏈路有好多條，任取一條（，，，，，，），把該鏈路上的每一條邊加上重復(fù)邊（見圖2）。同樣對和之間的一條鏈（，，，，，，）也加上重復(fù)邊（見圖3）。在圖3中沒有奇點，故它為歐拉圖。其全部重復(fù)邊的總權(quán)為51。圖3對連接和之間的一條鏈路加上重復(fù)邊245336454494第二步調(diào)整可行方案一般情況下如果在邊[]上有兩條或兩條以上的重復(fù)邊時，我們可以去掉偶數(shù)條，就能得到一個總長度較短的可行方案?，F(xiàn)在我們圖3進行這種處理，得到圖4的最優(yōu)方案。這種方案調(diào)整主要依據(jù)下面兩個條件：1）在最優(yōu)方案中，圖的每一邊最多有一條重復(fù)邊。2）在最優(yōu)方案中，圖中每個圈上重復(fù)邊的總權(quán)不大于該圈總權(quán)的一半。圖4對有兩條或兩條以上重復(fù)邊的邊去掉偶數(shù)條245336454494在圖4中，重復(fù)邊的總權(quán)下降為21，但我們看到，的圖4中某個圈上的重復(fù)邊去掉，而給原來沒有重復(fù)邊的邊上加上重復(fù)邊，圖中仍然沒有重復(fù)邊。因而如果在某個圈上重復(fù)邊的總權(quán)大于這個圈的總權(quán)的一半時，按這條原則又做一次調(diào)整，使重復(fù)邊的總長度下降為17，得最優(yōu)方案（見圖5）圖5對圖4進行調(diào)整后得到的可行方案245336454494第三步判斷最優(yōu)的標準從上分析，一個最優(yōu)方案，一定滿足1）和2）的可行方案，反之，一個可行方案若滿足1）和2），則一定為最優(yōu)。因此對上述給定的可行方案圖5，檢查它是否滿足1）和2），否則對該方案繼續(xù)進調(diào)整，直至1）和2）均滿足為止。在圖5中，圈（，，）中重復(fù)邊的總權(quán)為13，而圈的權(quán)為24，不滿足條件2），對其再次進行調(diào)整得圖6，使總權(quán)下降為15。圖6滿足條件1）和2），其中任一個歐拉圈為汽車最優(yōu)配送路線。圖6最優(yōu)方案245336454494授課題目：第二節(jié)樹第三節(jié)最短路問題教學目的：掌握樹的基本概念與最小生成樹算法及求某點至某點的Dijkstra算法。教學要求：要求學生用表操作Dijkstra算法。教學重點：掌握用表操作Dijkstra算法。教學難點：用表操作Dijkstra算法。教學手段與方法：先用實例引入，再采用比較演示方法。第二節(jié)樹一、樹的概念和性質(zhì)1、樹的定義：連通且不含圈的無向圖叫樹。2、定理6（略）二、圖的生成樹1、若圖的生成子圖是一棵樹，叫該圖的生成樹。2、找圖的生成樹的方法①探測法②廣探法三、最小生成樹問題1、具有最小權(quán)的生成樹叫最小生成樹。2、求最小生成樹的算法①避圈法思路：從具有個點的圖中的要邊中選取條權(quán)盡量小的邊，并且使之不構(gòu)成回路，從而構(gòu)成一棵最小樹。方法：將網(wǎng)絡(luò)中所有邊按權(quán)的大小由小到大排列起來，每步從未選的邊中選取一條權(quán)最小的邊逐條銜接，但不能連接成圈。在每一步中，若有兩條或更多條邊都是權(quán)最小的邊，則從中任選取一條。第一步：挑選邊；第二步：若已選定的邊為：，則從中選取使：1）所組成的圈為無圈圖；2）是滿足1）的盡可能小的權(quán)。第三步：當?shù)诙讲荒芾^續(xù)執(zhí)行時停止。例1某地有五個鎮(zhèn)，擬架設(shè)電話線連接這五個鎮(zhèn)，下圖中邊上的數(shù)字表示架設(shè)費用，問應(yīng)如何架設(shè)電話線才能使總費用最?。拷猓喝鐖D，可先連接權(quán)為1的—，再連接權(quán)為2的—，再連接權(quán)為3的—，再連接權(quán)為5的—，最后是權(quán)為5的—。4268 1535②破圈法思路：將圖每一個圈權(quán)最大的一條邊去掉，直到圖中不含圈為止。方法：在圖中選取任何一個圈，從圈中去掉一條權(quán)最大的邊（如有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中的一條。然后在余下的圈中重復(fù)這個步驟，直到得到一個不含圈的圖為止。這時的圖就是最小樹。再以上圖為例。1）在圖中找到一個圈，先去掉最大權(quán)8對應(yīng)的邊（，），得圖；2）在圖中找到一個圈，去掉最大權(quán)數(shù)為6的邊（，），得圖；3）在圖中找到一個圈，去掉最大權(quán)數(shù)4對應(yīng)的邊（，），得圖；4）在圖中找到一個圈，去掉最大權(quán)數(shù)5對應(yīng)的邊（，）或（，），得圖或，它們均為圖的最小樹。第三節(jié)最短路問題一、Dijkstra算法適用于所有權(quán)數(shù)為非負（則一切）的網(wǎng)絡(luò)。能注出任意一點到各點的最短路徑。其其基本思路是：若（，，…，，）是從到的最短路徑，則（，，…，）也是從到的最短路徑。因此可采用標號的方法，從始點開始，逐步向外收縮從始點到其他各點的最短路徑。例1．（6分）運用Dijkstra算法求出下面運輸網(wǎng)絡(luò)中從到的最短路徑(不要求寫出運算過程，可直接把最短路徑填入下面的括號內(nèi))。5944745456176設(shè)為連通圖，圖中各邊（，）有權(quán)。令分別為固定標號集和臨時標號集。固定標號最短路權(quán)，臨時標號的估計最短路權(quán)的上界。節(jié)點迭代序號1，∞，∞，∞，∞，∞，∞，∞2，4，634，9，846，9，858，13，1469，13，14713，14，17814，15915步驟：1）給以標號，則；其余各點給予標號，則；2）若為剛得到標號的點，考慮這樣的點：（，）屬于且為標號，則對的標號值進行如下修改：；3）比較所有標號的點的值，把最小者改為標號：。當存在兩個最小值時，可同時改為標號；若全部點為標號時則停止，否則用代替，轉(zhuǎn)向2）。以上列表如上。答：從到的最短路徑為（）；路長。例2運用Dijkstra算法求出下面運輸網(wǎng)絡(luò)中從A到B的最短路徑和最短距離。（不要求在試卷上寫出求解過程，可直接把結(jié)果寫在下面的橫線上）●300●200275200●100400100●150●175●●250175150200275●●300●125節(jié)點迭代序號B1，∞，∞，∞，∞，∞，∞，∞，∞，∞2100150175310040037541503503254255150325425632572557573505508425550550550650550答：A到B的最短路徑為：AB；最短距離為650。授課題目：第八章第3節(jié)某點到各點和某點到某點的距離摹乘法。教學目的：掌握距離摹乘法的操作程序。教學要求：學生能輪流上黑板做題。教學重點：掌握距離摹乘法的操作程序。教學難點：同重點。教學手段與方法：先用實例引入，再采用比較演示方法。況課后小結(jié)：二、、逐次逼近算法（距離矩陣摹乘法）適用于一切網(wǎng)絡(luò)的最短路徑的求解（含負權(quán)）。它基于這樣的事實：從到的最短路徑總是沿該路先到，再沿（，）到，。于是若從到為最短路，那么從到也為最短路。用分別表示從到和從到的最短路長，則必有下列方程：。該方程可用迭代式求解：1）令的直接距離作初始解，若它們之間無邊，則2）使用迭代法求，當進行到第則停止計算。則為最多經(jīng)t步到各點的最短路長。（一）求各點到某點的最短路徑設(shè)距離矩陣為，先從走一步到（），再從走一步到，得到從走兩步到的最短路徑（）：（1）這里為距離矩陣中的第i行元素，列的元素。它們的對應(yīng)元素相加再取小，再從各點走一步到，然后走兩步到（）：（2）最后得到從走一步到，再從走步到：（3）最后得到的列中各元素是從第i行第個元素加取小而來，設(shè)這個元素為從到最短路徑上的鄰接點，最后按鄰接點扒出最短路徑。例1求下圖中各點到的最短路徑。解：第一步：寫出網(wǎng)絡(luò)的距離矩陣如下：其中第6列為各點到的距離。從至2345623456052∞∞∞∞043∞∞∞40∞-3∞∞-2501∞∞∞4204∞∞∞-2∞0-2②④35-24552⑥244⑤②-3第二步：設(shè)從先走一步到中間點（），再從走一步到，得到從走兩步到的最短路徑（）：，相當于用距離矩陣各行與對應(yīng)元素相加再取小。052∞∞∞∞∞∞043∞∞∞∞=∞40∞-3∞*∞1∞-2501∞∞=9∞∞420444∞∞∞-2∞000第三步：設(shè)從走一步到中間點（），再從走兩步到：052∞∞∞∞3∞043∞∞∞5=∞40∞-3∞*11∞-2501∞9=6∞∞420444∞∞∞-2∞000如此迭代得351=6迭代終止得從走一步到的最短路徑為：40由～05（2）∞∞∞∞0（4）3∞∞∞40∞（-3）∞記為∞（-2）501∞∞∞420（4）∞∞∞-2∞（0）中第4個元素3來自（-2）+5，因0+3表示在原地踏步一次，得不到期最路徑，故不予考慮。由上矩陣，知—，—，—，—，—，—在各點到的最短路徑上。最短路徑最短距離———3———5——1————3—4—0（二）、求某點到各點的最短路徑例1求下圖中到各點的最短路徑。42-2-3356442-3-17025-3∞∞∞∞∞0-2∞4∞∞∞∞∞0∞∞6∞∞∞∞40∞∞∞∞∞∞∞∞0∞∞∞∞∞∞∞-30∞4∞∞∞7∞20∞∞∞∞∞3∞-100025-3∞∞∞∞02∞0-2∞4∞∞∞25∞∞0∞∞6∞∞0-3*∞∞40∞∞∞∞=-3∞∞∞∞∞0∞∞∞6∞∞∞∞∞-30∞411∞∞∞∞7∞20∞∞∞∞∞∞∞3∞-10∞的各列對應(yīng)元素相加再取最小，得各行的元素?！?，當時停止。025-3∞∞∞∞∞0-2∞4∞∞∞06400-3047203-10所以—，—，—，—，—，—，—，-在到各點的最短路徑上。最短路徑最短距離—0—2——0—-3————3———6————-9————10（三）從各點到各點的最短路徑——Floyd算法基本思路：1、輸入權(quán)矩陣，表示各點不經(jīng)任何中間點到各點的最短路徑長。2、記，其中，表示從最多經(jīng)一個中間點到達的最短路長。3、一般有若>0，則關(guān)于P值的估計為此時給出各點到各點的最短距離。例2求下圖中任意兩點間的最短路。解：該圖有四條無向邊，每條均可以化為方向相反的有向邊。則0512∞5010∞2230282∞604∞24401），其中，表示從最多經(jīng)一個中間點到達的最短路長。按此規(guī)則修改得，如。0512∞50（6）（7）2230282（7）（3）04∞24402）0512（7）506722302（5）27304（7）2440表示經(jīng)過最多、兩個中間點的最短路長。如0（4）12（6