運籌學 運輸問題

運籌學運輸問題第一頁，共八十三頁，編輯于2023年，星期三第四章運輸問題第1節(jié)運輸問題及其數(shù)學模型第2節(jié)表上作業(yè)法第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法第4節(jié)應(yīng)用問題舉例第二頁，共八十三頁，編輯于2023年，星期三第1節(jié)運輸問題及其數(shù)學模型一、運輸問題運輸問題屬于線性規(guī)劃問題，因為其約束方程組的系數(shù)矩陣A具有特殊的結(jié)構(gòu)，所以專門介紹一種比單純形法更簡便的求解方法，以節(jié)約計算時間和費用。第三頁，共八十三頁，編輯于2023年，星期三第1節(jié)運輸問題及其數(shù)學模型例1：某食品公司經(jīng)銷的主要產(chǎn)品之一是糖果。它下面設(shè)有三個加工廠，每天的糖果生產(chǎn)量分別為A1－7t（噸）；A2－4t；A3－9t。該公司把這些糖果分別運往四個地區(qū)的門市部銷售，各地區(qū)每天的銷售量為B1－3t（噸）；B2－6t；B3－5t；B4－6t。已知從每個加工廠到各銷售門市部每噸糖果的運價，如下表所示。試問該食品公司應(yīng)如何調(diào)運，在滿足各門市部銷售需要的情況下，使總的運費支出最少。門市部加工廠B1B2B3B4產(chǎn)量A1A2A3749銷量3656門市部加工廠B1B2B3B4A1A2A3311310192874105第四頁，共八十三頁，編輯于2023年，星期三第1節(jié)運輸問題及其數(shù)學模型二、運輸問題的數(shù)學模型已知有m個生產(chǎn)地點（簡稱產(chǎn)地）可供應(yīng)某種物資，其供應(yīng)量（產(chǎn)量）分別為；有n個銷售地點（簡稱銷地），其需要量（銷量）分別為，從到運輸單位物資的運價（單位運價）為，將這些數(shù)據(jù)表示在如下頁的兩個表中。問應(yīng)如何調(diào)運，在滿足各銷地銷量的情況下，使總的運費支出最少？第五頁，共八十三頁，編輯于2023年，星期三第1節(jié)運輸問題及其數(shù)學模型產(chǎn)銷平衡表兩個表合二為一

銷地產(chǎn)地B1B2…

Bn產(chǎn)量A1A2…Ama1a2…am銷量b1b2…bn

銷地產(chǎn)地B1B2…

BnA1A2…Amc11c12…

c1nc21c22…

c2n…

…

…

…

cm1cm2…

cmn銷地產(chǎn)地B1B2…

Bn產(chǎn)量A1A2…Amc11c12…

c1nc21c22…

c2n…

…

…

…cm1cm2…

cmna1a2…am銷量b1b2…bn

單位運價表第六頁，共八十三頁，編輯于2023年，星期三第1節(jié)運輸問題及其數(shù)學模型例1：解：設(shè)xij為第i加工廠向第j門市部的糖果的供應(yīng)量，cij表示第i加工廠向第j門市部供應(yīng)糖果的單位運費第七頁，共八十三頁，編輯于2023年，星期三第1節(jié)運輸問題及其數(shù)學模型產(chǎn)銷平衡運輸問題的數(shù)學模型：設(shè)xij表示從產(chǎn)地Ai運往銷地Bj的產(chǎn)品數(shù)量第八頁，共八十三頁，編輯于2023年，星期三第1節(jié)運輸問題及其數(shù)學模型特征（1）決策變量：m×n（2）約束方程：m＋n；都是等式約束（3）目標函數(shù)：最小化（4）約束方程組系數(shù)矩陣A①A中只有數(shù)字0或1②A的每一列只有兩個非零元素1（5）各產(chǎn)地產(chǎn)量之和等于各銷地銷量之和（6）基變量：m＋n－1（7）對于產(chǎn)銷平衡的運輸問題，必有可行解和最優(yōu)解第九頁，共八十三頁，編輯于2023年，星期三第1節(jié)運輸問題及其數(shù)學模型第十頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法一、表上作業(yè)法的解題思路表上作業(yè)法的實質(zhì)是單純形法在求解運輸問題時的一種簡化方法，屬于單純形法，又稱為運輸單純形法?；尚薪庾顑?yōu)否結(jié)束換基是否第十一頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法二、表上作業(yè)法的特點表上作業(yè)法是一種迭代法用表上作業(yè)法求解運輸問題，直接在表上進行，不必寫出數(shù)學模型第十二頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法三、表上作業(yè)法的解題步驟（一）找出初始基可行解：在產(chǎn)銷平衡表上找出(m+n-1)個數(shù)字格，形成初始產(chǎn)銷平衡表方法（二）求非基變量檢驗數(shù)：計算初始產(chǎn)銷平衡表中空格的檢驗數(shù)，判別是否達到最優(yōu)解，如果已達到，停止計算；否則轉(zhuǎn)入3方法（三）確定換入變量和換出變量，找出新的基可行解方法：閉回路調(diào)整法（四）重復（二）～（三），直到求出最優(yōu)解第十三頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法（一）確定初始基可行解方法一：最小元素法1、基本思路從運費上考慮，優(yōu)先安排單位運價最小的產(chǎn)地和銷地之間的運輸業(yè)務(wù)，最大限度地滿足其產(chǎn)銷量，從而實現(xiàn)“就近供應(yīng)”。第十四頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法2、求解步驟第一，從單位運價表中找出最小運價，（有兩個或兩個以上的最小單位運價，則任選其一），比較產(chǎn)量和銷量：產(chǎn)量＞銷量，則劃去該運價所在列；產(chǎn)量＜銷量，則劃去該運價所在行。并在初始產(chǎn)銷平衡表上填上相應(yīng)的數(shù)字。第二，從單位運價表中未被劃去的運價中再找最小運價，重復第一～第二，直到單位運價表中所有運價都被劃去，并找出(m+n-1)個數(shù)字格。第十五頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例2：用最小元素法找出例1的初始基可行解。產(chǎn)銷平衡表和單位運價表合二為一，如下所示：門市部加工廠B1B2B3B4產(chǎn)量A1A2A3311310192874105749銷量3656第十六頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例2：解：初始產(chǎn)銷平衡表門市部加工廠B1B2B3B4產(chǎn)量A1A2A3

433163749銷量3656第十七頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法3、小結(jié)（1）在初始產(chǎn)銷平衡表上每填入一個數(shù)字，在單位運價表上就劃去一行或一列（當表中只剩一個元素時，在初始產(chǎn)銷平衡表上填數(shù)字時，在單位運價表上同時劃去一行和一列）（2）在單位運價表上共劃去（m＋n）條直線，（相當于單位運價表上所有cij都被劃去兩次）（3）在初始產(chǎn)銷平衡表上填了（m＋n－1）個數(shù)字格，每行數(shù)字之和＝該行產(chǎn)量，每列數(shù)字之和＝該列銷量第十八頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例3：用最小元素法求出下述運輸問題的初始基可行解。門市部加工廠B1B2B3B4產(chǎn)量A1A2A331145773812106749銷量3656第十九頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例3：解：初始基可行解門市部加工廠B1B2B3B4產(chǎn)量A1A2A3

016

04360

0749銷量3656第二十頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例4：判斷下表給出的運輸方案能否作為用‘最小元素法’求解出的初始基可行解？銷地產(chǎn)地1234產(chǎn)量1230151510515255銷量5151510第二十一頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法（一）確定初始基可行解方法二：伏格爾法1、基本思路按某一最小單位運價優(yōu)先安排物品調(diào)運時，可能導致其他產(chǎn)銷點不得不采用很高的單位運價進行運輸，從而使整個運輸費用增加。對每一個產(chǎn)地或銷地，找出最小單位運價和次小單位運價，求二者之差。若差值不大，當不能按最小單位運價安排運輸時造成的運費損失不大；反之，若二者之差很大，不按最小單位運價組織運輸就會造成很大損失，所以應(yīng)盡量按最小單位運價安排運輸。第二十二頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法2、求解步驟第一，在單位運價表中分別計算各行和各列的最小運價與次小運價的差額，并填在該表的最右列和最下行。第二，從行或列差額中選出最大者，（有兩個或兩個以上的最大差額，則選擇差額所在行（或列）中的最小單位運價），選擇它所在行或列中的最小運價，按照最小元素法確定初始基可行解。第三，對單位運價表中未被劃去的運價再計算各行和各列的最小運價與次小運價的差額，并仍填入該表的最右列和最下行，重復第二、三，直至給出初始基可行解為止，即找出（m+n-1）個數(shù)字格。第二十三頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例5：用伏格爾法找出例1的初始基可行解。門市部加工廠B1B2B3B4A1A2A3311310192874105門市部加工廠B1B2B3B4產(chǎn)量A1A2A3749銷量3656第二十四頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例5：解：初始產(chǎn)銷平衡表門市部加工廠B1B2B3B4產(chǎn)量A1A2A3

523163749銷量3656第二十五頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法3、小結(jié)（1）伏格爾法和最小元素法僅在確定產(chǎn)銷關(guān)系的原則上不同，其余步驟都相同（伏格爾法是在最小元素法的基礎(chǔ)上改進的一種方法）（2）伏格爾法給出的初始基可行解比用最小元素法給出的初始基可行解更接近最優(yōu)解（伏格爾法給出的解的目標函數(shù)值比最小元素法給出的解的目標函數(shù)值?。?）伏格爾法得出的初始基可行解常作為運輸問題最優(yōu)解的近似解第二十六頁，共八十三頁，編輯于2023年，星期三作業(yè)10作業(yè)10：1、用最小元素法找出下述運輸問題的初始基可行解。2、找出下述運輸問題的近似最優(yōu)解。（其中M為任意大正數(shù)，表示含義為從A4到B4不存在運輸路線）銷地產(chǎn)地123產(chǎn)量12351824136712144銷量91011銷地產(chǎn)地12345產(chǎn)量12341023159510152415514715201513M825302030銷量2020301025第二十七頁，共八十三頁，編輯于2023年，星期三作業(yè)10答案1、2、銷地產(chǎn)地123產(chǎn)量123210311412144銷量91011銷地產(chǎn)地12345產(chǎn)量1234

0250

2000100

020000

502525302030銷量2020301025第二十八頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法（二）求檢驗數(shù)，判別最優(yōu)解基本思路計算空格（非基變量）的檢驗數(shù)，（運輸問題的目標函數(shù)要求實現(xiàn)最小化）當所有檢驗數(shù)≥0時，所得的解是最優(yōu)解，否則要進行解的改進。第二十九頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法（二）求檢驗數(shù)，判別最優(yōu)解方法一：閉回路法1、求解步驟第一，在初始產(chǎn)銷平衡表上，從每一空格出發(fā)找一條閉回路：以某空格為起點，用水平或垂直線向前畫，碰到一數(shù)字格轉(zhuǎn)90°（有些情況下也可以不改變方向），然后繼續(xù)前進，直到回到起始空格為止。第二，在一閉回路上，令某空格取值為‘+1’，表示增加的運量，然后變化相應(yīng)數(shù)字格的值，并計算該閉回路上運費的變化值，即為該空格的檢驗數(shù)，填入檢驗數(shù)表。第三十頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法2、檢驗數(shù)的含義檢驗數(shù)表示變化的運費。即：若某空格（Ai，Bj）的檢驗數(shù)＜0，表示將該空格變?yōu)閿?shù)字格使運輸費用減少，則當前這個解不是最優(yōu)解；反之，若所有空格的檢驗數(shù)都＞0，表示不管怎樣變換，都使運輸費用增加，則目標函數(shù)已無法改進，當前這個解就是最優(yōu)解第三十一頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例6：用閉回路法求例5所得的初始基可行解的檢驗數(shù)。門市部加工廠B1B2B3B4產(chǎn)量A1A2A3

523163749銷量3656第三十二頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例6：解：檢驗數(shù)表門市部加工廠B1B2B3B4A1A2A3

0221912第三十三頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例7：用閉回路法求例2所得的初始基可行解的檢驗數(shù)。門市部加工廠B1B2B3B4產(chǎn)量A1A2A3

433163749銷量3656第三十四頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例7：解：檢驗數(shù)表門市部加工廠B1B2B3B4A1A2A3

121-11012第三十五頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法3、小結(jié)（1）閉回路的頂點，除出發(fā)點為空格外，其他均為數(shù)字格（2）每個空格唯一存在一條閉回路（3）對于產(chǎn)銷點過多的運輸問題，空格的數(shù)目很大，計算檢驗數(shù)很繁瑣第三十六頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法（二）求檢驗數(shù)，判別最優(yōu)解方法二：位勢法1、求解步驟第一，仿照初始產(chǎn)銷平衡表做一個表，在對應(yīng)的數(shù)字格處填入單位運價cij。第二，在表的最右列和最下行分別增加一列ui和一行vj，使表中的單位運價等于它所在行和列的ui與vj之和，求出所有的ui和vj，并填寫在表中。第三，計算各空格的檢驗數(shù)，填入檢驗數(shù)表。第三十七頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例8：用位勢法求例2所得的初始基可行解的檢驗數(shù)。門市部加工廠B1B2B3B4產(chǎn)量A1A2A3

433163749銷量3656第三十八頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例8：解：檢驗數(shù)表門市部加工廠B1B2B3B4A1A2A3

121-11012第三十九頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例9：用位勢法求例5所得的初始基可行解的檢驗數(shù)。門市部加工廠B1B2B3B4產(chǎn)量A1A2A3

523163749銷量3656第四十頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例9：解：檢驗數(shù)表門市部加工廠B1B2B3B4A1A2A3

0221912第四十一頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法2、小結(jié)當運輸問題的產(chǎn)地和銷地很多時，空格的數(shù)目很大，采用位勢法計算檢驗數(shù)簡便第四十二頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法（三）確定換入和換出變量，找出新的基可行解，直至求出最優(yōu)解方法：閉回路調(diào)整法1、基本思想在初始產(chǎn)銷平衡表中，選取檢驗數(shù)為負的所有空格中的最小者作為換入格，以對應(yīng)空格為出發(fā)點畫出閉回路，在經(jīng)過的數(shù)字格中選擇（-1）的最小者，對應(yīng)的數(shù)字格為換出格，然后對閉回路上各頂點的數(shù)據(jù)進行調(diào)整，得到另一個更好的基可行解。第四十三頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法2、求解步驟第一，確定換入格。在初始產(chǎn)銷平衡表上，最小的負檢驗數(shù)所在的空格為換入格，（有兩個或兩個以上的最小者，則任選其一），并以此空格為出發(fā)點，作一閉回路。第二，確定換出格：選擇閉回路上標記為‘-1’的數(shù)字格中的最小者，記做θ，則該數(shù)字格為換出格。第三，調(diào)整：將閉回路上標記為‘+1’的數(shù)字格‘加θ’，標記為‘-1’的數(shù)字格‘減θ’，得到新的基可行解。第四，采用閉回路法或位勢法求空格的檢驗數(shù)，若所有檢驗數(shù)都‘≥0’，則獲得最優(yōu)解；否則重復第一～第三，直至求出最優(yōu)解。第四十四頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例10：以例8所求的檢驗數(shù)為依據(jù)，求例1的最優(yōu)解。檢驗數(shù)表初始產(chǎn)銷平衡表門市部加工廠B1B2B3B4產(chǎn)量A1A2A3

433163749銷量3656門市部加工廠B1B2B3B4A1A2A3121-11012第四十五頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例10：解：最優(yōu)解檢驗數(shù)表

z*=85門市部加工廠B1B2B3B4產(chǎn)量A1A2A3

5231

63749銷量3656門市部加工廠B1B2B3B4A1A2A3

0221912第四十六頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法四、表上作業(yè)法的解1、無窮多（多重）最優(yōu)解某個空格（非基變量）的檢驗數(shù)為0時，該運輸問題有無窮多（多重）最優(yōu)解。在已求得一個最優(yōu)解的表中，以這樣的空格出發(fā)做閉回路重新進行調(diào)整，得到另一個最優(yōu)解。第四十七頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法2、退化解某個數(shù)字格（基變量）為0時，該運輸問題為退化解。退化解出現(xiàn)的情況：確定初始解的各供需關(guān)系時，若在某格填入某數(shù)字后，出現(xiàn)該處的供應(yīng)量與需求量相等。用閉回路調(diào)整法調(diào)整時，在閉回路上出現(xiàn)兩個或兩個以上的具有（-1）標記的相等的最小值。第四十八頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例11：已知某初始產(chǎn)銷平衡表，如下表：空格A2B4格的檢驗數(shù)‘＜0’，其余空格的檢驗數(shù)均‘≥0’，試確定換入、換出格，求出新的基可行解。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3

413163549銷量3654第四十九頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例11：解：下一個基可行解銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3

5031

63549銷量3654第五十頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例11：解：再下一個基可行解銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A30

531

63549銷量3654第五十一頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法五、表上作業(yè)法計算步驟框圖分析實際問題列出產(chǎn)銷平衡表及單位運價表確定初始調(diào)運方案（最小元素法或伏格爾法）求檢驗數(shù)（閉回路法或位勢法）所有檢驗數(shù)≥0唯一最優(yōu)解算出總的運價找出最小的負檢驗數(shù)用閉回路調(diào)整，得出新的調(diào)運方案是否某空格檢驗數(shù)＝0是否無窮多最優(yōu)解第五十二頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例12：已知三個產(chǎn)地A1，A2，A3，四個銷地B1，B2，B3，B4的產(chǎn)銷量即單位運價如下表所示，求使總運費最少的調(diào)運方案。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3223743591678500600300銷量300200500400第五十三頁，共八十三頁，編輯于2023年，星期三第2節(jié)表上作業(yè)法例12：解：無窮多最優(yōu)解、退化解

z*=6000銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3

05002000400300

500600300銷量300200500400第五十四頁，共八十三頁，編輯于2023年，星期三作業(yè)11作業(yè)11：用表上作業(yè)法求解下列運輸問題的最優(yōu)解。（要求采用伏格爾法、閉回路法求解）1、2、銷地產(chǎn)地甲乙丙丁產(chǎn)量123376424324385523銷量3322銷地產(chǎn)地甲乙丙丁產(chǎn)量123106712161059541010494銷量5246第五十五頁，共八十三頁，編輯于2023年，星期三作業(yè)11答案1、2、銷地產(chǎn)地甲乙丙丁產(chǎn)量123302

023523銷量3322銷地產(chǎn)地甲乙丙丁產(chǎn)量123121364494銷量5246第五十六頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法一、求解思路總產(chǎn)量不等于總銷量，為使用表上作業(yè)法求解，將產(chǎn)銷不平衡運輸問題轉(zhuǎn)化為產(chǎn)銷平衡運輸問題。第五十七頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法二、求解方法1、總產(chǎn)量＞總銷量（）銷地產(chǎn)地B1B2…

Bn產(chǎn)量A1A2…Amc11c12…

c1nc21c22…

c2n…

…

…

…cm1cm2…

cmna1a2…am銷量b1b2…bn第五十八頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法數(shù)學模型：第五十九頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法銷地產(chǎn)地B1B2…

BnBn+1產(chǎn)量A1A2…Amc11c12…

c1n

0c21c22…

c2n0…

…

…

…

…cm1cm2…

cmn0a1a2…am銷量b1b2…bn

bn+1

第六十頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法解題思路：為借助于產(chǎn)銷平衡的表上作業(yè)法求解，增加一個假想的銷地Bn+1，由于實際上它不存在，因而由產(chǎn)地Ai（i=1，2，…，m）調(diào)運到這個假想銷地的物品數(shù)量xi,n+1，就是就地存貯在Ai的物品數(shù)量。就地存貯的物品未經(jīng)運輸，所以其單位運價ci,n+1=0（i=1，2，…，m）。第六十一頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法數(shù)學模型：第六十二頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法數(shù)學模型變化：→第六十三頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法2、總產(chǎn)量＜總銷量（）銷地產(chǎn)地B1B2…

Bn產(chǎn)量A1A2…Amc11c12…

c1n

c21c22…

c2n…

…

…

…cm1cm2…

cmna1a2…am銷量b1b2…bn第六十四頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法數(shù)學模型：第六十五頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法銷地產(chǎn)地B1B2…

Bn產(chǎn)量A1A2…AmAm+1c11c12…

c1n

c21c22…

c2n…

…

…

…cm1cm2…

cmn

0

0

…

0a1a2…amam+1銷量b1b2…bn第六十六頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法解題思路：為借助于產(chǎn)銷平衡的表上作業(yè)法求解，增加一個假想的產(chǎn)地Am+1，由于實際上它不存在，因而由它發(fā)往各個銷地的物品數(shù)量xm+1,j（j=1，2，…，n），就是各銷地Bj所需物品的欠缺額。欠缺的物品未經(jīng)運輸，所以其單位運價cm+1,j=0（j=1，2，…，n）。第六十七頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法數(shù)學模型：第六十八頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法數(shù)學模型變化：→第六十九頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法例13：用表上作業(yè)法求解下述運輸問題的最優(yōu)解。銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A321134103597812757銷量2346第七十頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法例13：解：不產(chǎn)銷平衡→產(chǎn)銷平衡銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A1A2A321134010359078120

757銷量23464

1915+4第七十一頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法無窮多最優(yōu)解

z*=35銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A1A2A3

2323243

757銷量23464

1915+4第七十二頁，共八十三頁，編輯于2023年，星期三第3節(jié)產(chǎn)銷不平衡的運輸問題及其求解方法小結(jié)采用最小元素法或伏格爾法求初始基可行解時，由于虛擬產(chǎn)地或銷地不存在，所以盡管二者的單位運價ci,n+1=0或cm+1,j=0，但不能作為最小運價（元素）優(yōu)先使用。應(yīng)從有實際運輸任務(wù)的產(chǎn)地或銷地之間安排運量，最后再考慮虛擬產(chǎn)、銷地的‘0’運價。第七十三頁，共八十三頁，編輯于2023年，星期三作業(yè)12作業(yè)12：用表上作業(yè)法求解下列運輸問題的最優(yōu)調(diào)運方案和最小總運費。（要求采用最小元素法、位勢法求解）1、2、銷地產(chǎn)地B1B2B3B4產(chǎn)量A1A2A3359474859752300500600銷量150100400450銷地產(chǎn)地B1B2B3產(chǎn)量A1A26543721525銷量201015第七十四頁，共八十三頁，編輯于2023年，星期三作業(yè)12答案1、2、銷地產(chǎn)地B1B2B3B4B5產(chǎn)量A1A2A3150150100100300400200300500600銷量15010040045030014001100+300銷地產(chǎn)地B1B2B3產(chǎn)量A1A2A31051510

515255銷量20101540+545第七十五頁，共八十三頁，編輯于2023年，星期三第4節(jié)應(yīng)用問題舉例例14：設(shè)有三個化肥廠（A，B，C）供應(yīng)四個地區(qū)1，2，3，4的農(nóng)用化肥。假定等量的化肥在這些地區(qū)使用效果相同。各化肥廠年產(chǎn)量，各地區(qū)需要量及從各化肥廠到各地區(qū)運送單位化肥的運價如下表所示。試求出總的運費最節(jié)省的化肥調(diào)運方案。需求地區(qū)化肥廠1234產(chǎn)量（萬噸）ABC1613221714131915192023－506050最低需求（萬噸）最高需求（萬噸）3070010507030不限

第七十六頁，共八十三頁，編輯于2023年，星期三第4節(jié)應(yīng)用問題舉例例14：解：不產(chǎn)銷平衡→產(chǎn)銷平衡需求地區(qū)化肥廠1′1〞2′2〞3′3〞4′4〞產(chǎn)量（萬噸）ABCD16161313222217171414131319191515191920202323MM

M0M0(M)M(0)0M0

50605050需求量（萬噸）30207000