運籌學-第三章-運輸問題課件

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

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

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

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

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

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

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

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

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

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

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

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