運(yùn)輸問(wèn)題與指派問(wèn)題第ppt課件.ppt

《運(yùn)輸問(wèn)題與指派問(wèn)題第ppt課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、OR課件回顧到目前為止，針對(duì)規(guī)劃問(wèn)題所建立的算法有一個(gè)共同的特征：但是：在決策的實(shí)踐中，有些問(wèn)題約束條件存在一定的特殊性，按常規(guī)辦法有可能出現(xiàn)嚴(yán)重退化而導(dǎo)致問(wèn)題無(wú)法順利求解。如：運(yùn)輸問(wèn)題、指派問(wèn)題等。從約束條件入手OR課件運(yùn)籌帷幄之中決勝千里之外運(yùn)輸問(wèn)題與指派問(wèn)題第五章TransportationProblem—IP&AssignmentProblem—APOR課件運(yùn)輸問(wèn)題與指派問(wèn)題運(yùn)輸問(wèn)題和指派問(wèn)題是一種特殊的LP問(wèn)題，要求了解兩問(wèn)題的基本特征；掌握兩問(wèn)題的求解算法原理及計(jì)算過(guò)程；學(xué)會(huì)對(duì)它們的特殊形式的處理。本章的要求TP&APOR課件運(yùn)輸問(wèn)題與指派問(wèn)題重點(diǎn)本

2、章重點(diǎn)與難點(diǎn)難點(diǎn)TP&AP運(yùn)輸與指派問(wèn)題模型及其特征算法原理特殊問(wèn)題的處理兩算法的思想及其實(shí)現(xiàn)OR課件運(yùn)輸問(wèn)題與指派問(wèn)題運(yùn)輸問(wèn)題主要內(nèi)容指派問(wèn)題TP&AP運(yùn)輸問(wèn)題及其數(shù)學(xué)模型求解方法－－表上作業(yè)法特殊運(yùn)輸問(wèn)題的求解指派問(wèn)題及其數(shù)學(xué)模型求解方法－－匈牙利法特殊指派問(wèn)題的求解OR課件運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題及其數(shù)學(xué)模型TP&AP設(shè)某種物資有m個(gè)產(chǎn)地：A1,A2,…,Am；產(chǎn)量分別為：a1,a2,…,am個(gè)單位；n個(gè)銷地：B1,B2,…,Bn；銷量分別為：b1,b2,…,bn個(gè)單位；假設(shè)產(chǎn)銷總量是平衡的，即單位運(yùn)價(jià)：Ai?Bj：cij問(wèn)：如何調(diào)運(yùn)這種物資才能使總的運(yùn)費(fèi)最??？O

3、R課件運(yùn)輸問(wèn)題單位運(yùn)價(jià)表與平衡表（合表）TP&AP單位運(yùn)價(jià)產(chǎn)銷量（平衡）OR課件運(yùn)輸問(wèn)題模型TP&AP設(shè)：xij為Ai?Bj的運(yùn)量OR課件運(yùn)輸問(wèn)題表上作業(yè)法TP&AP【簡(jiǎn)例】已知有關(guān)資料如下表算法的提出：觀測(cè)模型的特征要求建立總運(yùn)費(fèi)最小的模型。OR課件運(yùn)輸問(wèn)題模型TP&AP約束條件個(gè)數(shù)為m+n，但只有m+n-1個(gè)是線性無(wú)關(guān)元素只有0和1，每列只有兩個(gè)1OR課件表上作業(yè)法算法思想TP&AP與單純形法一樣，最優(yōu)解在基本可行解中產(chǎn)生。但基于模型的特征，初始基本可行解是通過(guò)分析單位運(yùn)價(jià)表，首先滿足局部最優(yōu)，然后通過(guò)調(diào)整（迭代）使整體達(dá)到最優(yōu)。平衡表OR課件表上作業(yè)法步驟

4、算法步驟及要點(diǎn)TP&AP初始調(diào)運(yùn)方案檢驗(yàn)數(shù)?ij?0?Y最優(yōu)解N調(diào)整：找到新的調(diào)運(yùn)方案特征：解變量（基變量）個(gè)數(shù)為m+n-1；以解變量為頂點(diǎn)不構(gòu)成折現(xiàn)閉回路。方法：最小元素法、差值法方法：閉回路法、位勢(shì)法方法：閉回路法OR課件表上作業(yè)法?初始方案折現(xiàn)閉回路：TP&AP頂點(diǎn):x11,x12,x32,x31頂點(diǎn)：x12,x13,x33,x34,x24,x22定理：以m+n-1個(gè)變量構(gòu)成的基本可行解的充要條件是它不含折現(xiàn)閉回路。OR課件表上作業(yè)法?初始方案最小元素法TP&AP基本思想：“就近供應(yīng)”或稱“就廉供應(yīng)”3?????42?345Z=1×3＋9×5＋4×3＋2×

5、4＋7×4＋2×2＝100OR課件表上作業(yè)法?初始方案差值法[伏格爾（Vogel)法]TP&AP基本思想：在考慮最大差值的基礎(chǔ)上，就近供應(yīng)差值（行、列）＝次小元素－最小元素Z=2×3＋9×5＋4×3＋2×4＋7×1＋2×5＝883??25??2854?13?15OR課件表上作業(yè)法?最優(yōu)性檢驗(yàn)閉回路法TP&AP基本原理：以任一非基變量為頂點(diǎn)，其它頂點(diǎn)為基變量，所構(gòu)成的閉回路是唯一的。3?????42?345－47－1323OR課件表上作業(yè)法?最優(yōu)性檢驗(yàn)TP&AP位勢(shì)法基本原理：由于找閉回路帶來(lái)的麻煩，根據(jù)對(duì)偶理論，設(shè)兩組變量（對(duì)偶變量）ui和vj，及基變量的檢驗(yàn)數(shù)

6、等于0，建立一組參數(shù)方程：基變量所對(duì)應(yīng)的價(jià)格系數(shù)非基變量所對(duì)應(yīng)的價(jià)格系數(shù)行位勢(shì)列位勢(shì)OR課件表上作業(yè)法?最優(yōu)性檢驗(yàn)TP&AP3?????42?345vjui令u1=00-5-56977-47-1323OR課件表上作業(yè)法?方案調(diào)整TP&AP3?????42?345-47-1313閉回路法基本思想：確定換入、換出變量。在閉回路上采用“奇加偶減”調(diào)整運(yùn)量xij，閉回路以外xij不變。315???OR課件表上作業(yè)法?方案調(diào)整TP&AP????45?3153?vjui0297-5-57411-1323560???40?363??5vjui027-58-464101432S

7、=83OR課件運(yùn)輸問(wèn)題TP&AP特殊運(yùn)輸問(wèn)題及其求解目標(biāo)取極大（MaxZ）：用?ij?0進(jìn)行最優(yōu)性檢驗(yàn)。供過(guò)于求（產(chǎn)>銷）：加虛銷點(diǎn)，且Ci虛＝0，銷量為產(chǎn)銷之差【例】供不應(yīng)求（銷>產(chǎn)）：加虛產(chǎn)點(diǎn)，且C虛j=0，產(chǎn)量為銷產(chǎn)之差【例】OR課件特殊運(yùn)輸問(wèn)題及求解TP&AP2115OR課件特殊運(yùn)輸問(wèn)題及求解TP&AP2125OR課件指派問(wèn)題TP&AP問(wèn)題的提出設(shè)有n個(gè)人，需要分派他們?nèi)プ鰊件工作。要求一個(gè)人做一件事，一件事只能由一個(gè)人完成；由于每人的專長(zhǎng)不同，各人做任一種工作的效率可能不同，因而創(chuàng)造的價(jià)值也不同。問(wèn)如何安排，才能使創(chuàng)造的總價(jià)值最大？OR課件指派問(wèn)題TP

8、&AP數(shù)學(xué)模型【例】現(xiàn)有