運(yùn)籌學(xué)-第三章-運(yùn)輸問題課件

1、第三章 運(yùn)輸問題第三章 運(yùn)輸問題學(xué)習(xí)目標(biāo)運(yùn)輸問題的基本概念與數(shù)學(xué)模型；運(yùn)輸平衡問題的求解方法表上作業(yè)法；運(yùn)輸不平衡問題的處理方法運(yùn)輸問題的應(yīng)用計(jì)算機(jī)求解運(yùn)輸問題的實(shí)現(xiàn)2學(xué)習(xí)目標(biāo)運(yùn)輸問題的基本概念與數(shù)學(xué)模型；2案例某公司計(jì)劃通過銀行貸款150萬元，內(nèi)部發(fā)放股票80萬元和社會(huì)發(fā)行債券120萬元來籌集資金以便發(fā)展生產(chǎn)。公司將這些資金用于開發(fā)三種產(chǎn)品生產(chǎn)線的投資。初步估計(jì)，在不同形式的資金籌集方式下，三種新產(chǎn)品的生產(chǎn)線建成后每年公司可獲得凈利潤(rùn)如下表所示（每10萬元投資帶來的凈利潤(rùn)）。問該公司如何合理安排這筆籌集資金，使每年獲得的凈利潤(rùn)最大？案例某公司計(jì)劃通過銀行貸款150萬元，內(nèi)部發(fā)放股票80萬元和

2、43-1 運(yùn)輸問題的數(shù)學(xué)模型一、示例例143-1 運(yùn)輸問題的數(shù)學(xué)模型一、示例例15二、運(yùn)輸問題描述有m 個(gè)產(chǎn)地Ai， 產(chǎn)量為 ai, i=1,2, m （sources）供n 個(gè)銷地 Bj , 需求量 bj, j=1,2, n （destinations）已知 Ai 到 Bj 的單位運(yùn)價(jià)為 cij問如何調(diào)運(yùn)使總運(yùn)費(fèi)最??？5二、運(yùn)輸問題描述有m 個(gè)產(chǎn)地Ai， 產(chǎn)量為 ai, 6表3-1 運(yùn)輸問題數(shù)據(jù)表6表3-1 運(yùn)輸問題數(shù)據(jù)表7表3-2 運(yùn)輸方案表7表3-2 運(yùn)輸方案表8三、運(yùn)輸問題的一般數(shù)學(xué)模型產(chǎn)銷平衡：ai=bj 產(chǎn) 銷：ai bj 產(chǎn) 銷： ai bj 8三、運(yùn)輸問題的一般數(shù)學(xué)模型產(chǎn)銷平衡

3、：ai=bj 9四、運(yùn)輸問題的特點(diǎn)線性規(guī)劃模型約束系數(shù)矩陣高度“退化”（系數(shù)為0）產(chǎn)銷平衡問題一定有可行解和最優(yōu)解r(A)=r ()=m+n-1 （行的秩等于列的秩就叫矩陣的秩）9四、運(yùn)輸問題的特點(diǎn)線性規(guī)劃模型103-2 表上作業(yè)法（運(yùn)輸單純形法）表上作業(yè)法的計(jì)算步驟：確定初始方案，即找出初始基可行解；求非基變量檢驗(yàn)數(shù)，判斷最優(yōu)；用閉回路法調(diào)整；重復(fù)2, 3，直至求出最優(yōu)解。103-2 表上作業(yè)法（運(yùn)輸單純形法）表上作業(yè)法的計(jì)算步驟11一、確定初始基可行解（兩種方法）1. 最小元素法（“就近調(diào)運(yùn)”）1）找到運(yùn)價(jià)中最小的元素，確定供銷關(guān)系；若銷量滿足劃掉列若產(chǎn)量滿足劃掉行若產(chǎn)、銷同時(shí)滿足，在對(duì)應(yīng)

4、同時(shí)劃掉的那行或那列的任意空格處填0，再同時(shí)劃掉那行和那列重復(fù)1）步。11一、確定初始基可行解（兩種方法）1. 最小元素法（“就近找最小運(yùn)價(jià)每填一個(gè)數(shù)字，劃掉一行或一列 填最后一個(gè)數(shù)字同時(shí)劃掉一行和一列12找最小運(yùn)價(jià)每填一個(gè)數(shù)字，劃掉一行或一列12未劃去的元素中再找出最小運(yùn)價(jià)13未劃去的元素中再找出最小運(yùn)價(jià)13得到初始可行解填入m+n-1個(gè)數(shù)字（對(duì)應(yīng)基變量）14得到初始可行解填入m+n-1個(gè)數(shù)字（對(duì)應(yīng)基變量）14152.伏格爾法1）計(jì)算各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行；2）在所有行差、列差中找到max差額，選出它所在行或列中的min元素，確定供銷關(guān)系（填入數(shù)字）

5、；劃掉滿足產(chǎn)量的行或滿足銷量的列；若產(chǎn)、銷同時(shí)滿足，在對(duì)應(yīng)同時(shí)劃掉的那行或那列的任意空格處填0，再同時(shí)劃掉那行或那列3）對(duì)未劃掉的元素再分別計(jì)算各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額，并填入該表的最右列和最下行；4）重復(fù)1）、2），直至給出初始解。152.伏格爾法1）計(jì)算各行和各列的最小運(yùn)費(fèi)和次小運(yùn)費(fèi)的差額找最大行差、列差對(duì)應(yīng)的最小運(yùn)價(jià)，確定供銷關(guān)系16找最大行差、列差對(duì)應(yīng)的最小運(yùn)價(jià)，確定供銷關(guān)系16未被劃去的元素再找最大行差、列差對(duì)應(yīng)的最小運(yùn)價(jià)，確定供銷關(guān)系17未被劃去的元素再找最大行差、列差對(duì)應(yīng)的最小運(yùn)價(jià)，確定供銷關(guān)系得到初始可行解由伏格爾法得出的解比最小元素法得出的解更接近最優(yōu)解。18得到

6、初始可行解由伏格爾法得出的解比最小元素法得出的解更接近最二、最優(yōu)解的判定閉回路法 1）尋找閉回路(空格11)19從空格出發(fā)，水平或豎直線向前劃；遇到數(shù)字拐90（不是遇到所有數(shù)字都拐），繼續(xù)前進(jìn)；二、最優(yōu)解的判定閉回路法 19從空格出發(fā)，水平或豎直線向前劃2) 計(jì)算檢驗(yàn)數(shù)202) 計(jì)算檢驗(yàn)數(shù)203）最優(yōu)性判別準(zhǔn)則當(dāng)所有ij0時(shí)，運(yùn)輸問題達(dá)到最優(yōu)。21類似的，計(jì)算其他檢驗(yàn)數(shù)，得下表3）最優(yōu)性判別準(zhǔn)則當(dāng)所有ij0時(shí)，運(yùn)輸問題達(dá)到最優(yōu)。2122由最小元素法得出初始解,如下表2. 位勢(shì)法在初始可行解的表格上增加一行一列，在列中填入ui ，在行中填入v j 22由最小元素法得出初始解,如下表2. 位勢(shì)法在

7、初始可行解的位勢(shì)的計(jì)算23位勢(shì)的計(jì)算23計(jì)算所有檢驗(yàn)數(shù)24計(jì)算所有檢驗(yàn)數(shù)24三、閉回路調(diào)整251）找出閉回路2）使最小負(fù)檢驗(yàn)數(shù)所對(duì)應(yīng)的空格達(dá)到最大的調(diào)整量: =min(偶數(shù)頂點(diǎn)數(shù)字格)=min(1,3)=1三、閉回路調(diào)整251）找出閉回路2）使最小負(fù)檢驗(yàn)數(shù)所對(duì)應(yīng)的空調(diào)整后的可行解26調(diào)整后的可行解26解的檢驗(yàn)27解的檢驗(yàn)27運(yùn)輸問題解的情況產(chǎn)銷平衡的運(yùn)輸問題一定存在最優(yōu)解。那么是有唯一最優(yōu)解，還是有無窮多最優(yōu)解？與單純形法中的結(jié)論類似，當(dāng)某個(gè)非基變量（空格）的檢驗(yàn)數(shù)為0時(shí)，該問題有無窮多最優(yōu)解。28運(yùn)輸問題解的情況產(chǎn)銷平衡的運(yùn)輸問題一定存在最優(yōu)解。那么是有唯3-3 產(chǎn)銷不平衡的運(yùn)輸問題293-

8、3 產(chǎn)銷不平衡的運(yùn)輸問題29例3.3甲、乙、丙三個(gè)城市每年需要煤炭分別為320、250、350 萬噸，由A、B兩處煤礦負(fù)責(zé)供應(yīng)。已知煤炭年供應(yīng)量分別為：A400 萬噸，B450 萬噸。由煤礦至各城市的單位運(yùn)價(jià)（萬元/萬噸）見表3-19。由于需大于供，根據(jù)實(shí)際情況決定，甲城市供應(yīng)量可減少030 萬噸，乙城市需求量必須全部滿足，丙城市供應(yīng)量不少于270 萬噸。試求將供應(yīng)量分配完又使總運(yùn)價(jià)最低的調(diào)運(yùn)方案。30例3.3甲、乙、丙三個(gè)城市每年需要煤炭分別為320、250、供小于求，虛擬產(chǎn)地C31供小于求，虛擬產(chǎn)地C31伏格爾法求出初始可行解32伏格爾法求出初始可行解32位勢(shì)法求各非基變量的檢驗(yàn)數(shù)33所有

9、非基變量的檢驗(yàn)數(shù)均為非負(fù)，得到最優(yōu)解。按照此方案調(diào)運(yùn)的總運(yùn)價(jià)最低，為14650萬元。位勢(shì)法求各非基變量的檢驗(yàn)數(shù)33所有非基變量的檢驗(yàn)數(shù)均為非負(fù)，3-4 應(yīng)用舉例例3.4 某公司在3個(gè)工廠中專門生產(chǎn)一種產(chǎn)品。在未來的4個(gè)月中，有四個(gè)處于國內(nèi)不同區(qū)域的潛在顧客（批發(fā)商）很可能大量訂購。顧客1是公司優(yōu)先級(jí)別最高的顧客，所以他的全部訂購量都應(yīng)該滿足；顧客2和顧客3也是公司很重要的顧客，所以營銷經(jīng)理認(rèn)為作為最低限度至少要滿足他們訂單的1/3；對(duì)于顧客4，銷售經(jīng)理認(rèn)為并不需要進(jìn)行特殊考慮。由于運(yùn)輸成本上的差異，銷售一件產(chǎn)品得到的凈利潤(rùn)也不同，很大程度上取決于哪個(gè)工廠供應(yīng)哪個(gè)顧客（見表3-23）。問應(yīng)向每一

10、個(gè)顧客供應(yīng)多少貨物，以使公司總利潤(rùn)最大？343-4 應(yīng)用舉例例3.4 某公司在3個(gè)工廠中專門生產(chǎn)解：該問題要求滿足不同顧客的需求（采購量），即最小采購量 實(shí)際供給量 最大采購量。三個(gè)工廠的總產(chǎn)量為20000件，4個(gè)顧客的最低采購量為12000件，最高采購量為30000件，大于總產(chǎn)量。為保持產(chǎn)銷平衡，虛擬一個(gè)工廠4，其產(chǎn)量為10000件。由于每個(gè)顧客的需求分為必須滿足和不一定滿足兩部分，故將其視為兩個(gè)顧客。必須滿足的顧客其采購量不能由虛擬工廠提供，令其單位利潤(rùn)為M（M為任意大正數(shù)），不一定滿足的顧客其采購量能由虛擬工廠提供，令其單位利潤(rùn)為0。由此可得該問題的產(chǎn)銷平衡及單位利潤(rùn)表，如表3-24所示

11、。35解：該問題要求滿足不同顧客的需求（采購量），即最小采購量 實(shí)3636設(shè)xij 為工廠 供應(yīng)給顧客j 的產(chǎn)品數(shù)量，則該問題的數(shù)學(xué)模型為37設(shè)xij 為工廠 供應(yīng)給顧客j 的產(chǎn)品數(shù)量，則該問題的數(shù)學(xué)模模型求解結(jié)果38模型求解結(jié)果38例3.5 某機(jī)床廠生產(chǎn)某一規(guī)格的機(jī)床。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本見表3-23所示。按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供15、10、20、30臺(tái)同一規(guī)格的機(jī)床。如果生產(chǎn)出來的機(jī)床當(dāng)季不交貨的，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用0.1萬元。要求在完成合同的情況下，如何做出使該廠全年生產(chǎn)（包括儲(chǔ)存、維護(hù)）費(fèi)用最小的生產(chǎn)計(jì)劃。39例3.5 某機(jī)床廠生

12、產(chǎn)某一規(guī)格的機(jī)床。已知該廠各季度的生產(chǎn)能4040414142424343用表上作業(yè)法可求得最優(yōu)方案為1季度生產(chǎn)20臺(tái)，其中15臺(tái)于當(dāng)季交貨，5臺(tái)于4季度交貨；2季度生產(chǎn)20臺(tái)，其中10臺(tái)于當(dāng)季交貨，10臺(tái)于4季度交貨；3季度生產(chǎn)35臺(tái)，其中20臺(tái)于當(dāng)季交貨，15臺(tái)于4季度交貨。按該方案生產(chǎn)，機(jī)床廠全年生產(chǎn)（包括儲(chǔ)存、維護(hù)）費(fèi)用為836萬元。44用表上作業(yè)法可求得最優(yōu)方案為443.5計(jì)算機(jī)求解運(yùn)輸問題的實(shí)現(xiàn)例3.8 某公司有三個(gè)加工廠A1、A2、A3 生產(chǎn)某產(chǎn)品，每日的產(chǎn)量分別為：7 噸、4 噸、9 噸；該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)B1、B2、B3、B4，各銷售點(diǎn)每日銷量分別為：3 噸、6 噸、5 噸、6 噸；從各工廠到各銷售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)如表3-29 所示。問該公司應(yīng)如何調(diào)運(yùn)這些產(chǎn)品，在滿足各銷售點(diǎn)的需要量的前提下，使總運(yùn)