運籌學3運輸問題

1、 3 運輸問題 3.1 運輸問題及其數(shù)學模型 3.2 表上作業(yè)法 3.2.1 初始方案的給定 最小元素法 Vogel法 3.2.2 最優(yōu)性檢驗 閉回路法位勢法 3.2.3 方案的調整閉回路法 3.3 產(chǎn)銷不平衡的運輸問題 3.4 應用舉例3.1 運輸問題及其模型例 某公司經(jīng)銷一種產(chǎn)品，它下設三個工廠、四個銷售部。三個工廠的日產(chǎn)量分別為：A17噸，A24噸，A39噸；各銷售部的日銷量分別為：B13噸，B26噸，B35噸，B46噸。各廠到各銷售部的單位產(chǎn)品的運價如下表。問該公司應如何調運產(chǎn)品，才能完成運輸任務而使運費最省。min z= 3x11+11x12+3x13+10 x14 +x21 +9x

2、22 +2x23 +8x24 +7x31 +4x32+10 x33+5x34解：設由產(chǎn)地i到銷地j的運量為xij，模型為： x11+x12+x13+x14=7 x21+x22+x23+x24=4 x31+x32+x33+x34=9 x11+x21+x31=3 x12+x22+x32=6 x13+x23+x33=5 x14+x24+x34=6 xij0 (i=1,2,3; j=1,2,3,4)運輸問題的典型數(shù)學形式：運輸問題一般用表上作業(yè)法求解，需建立表格模型：產(chǎn)銷平衡表單位運價表3.2 表上作業(yè)法 表上作業(yè)法的步驟類似于單純形法: (1)給出初始調運方案。 (2)檢驗方案是否最優(yōu),若是最優(yōu)解,

3、則停止計算;否則轉下一步。 (3)調整調運方案，得新的方案。 (4)重復(2),(3)直到求出最優(yōu)方案。3.2.1 初始方案的給定最小元素法 表上作業(yè)法要求，調運方案的有數(shù)字格必須為m+n-1個，且有數(shù)字格不構成閉回路。一般，用最小元素法給出的方案符合這一要求。314633此時，z=86元。產(chǎn)銷平衡表及初始調運方案單位運價表最小元素法中的退化情況360542 出現(xiàn)退化時，要在同時被劃去的行或列中任選一個空格填0，此格作為有數(shù)字格。3.2.1 初始方案的給定 Vogel法0112 5 1 30122 1 3012 1 276 1 2536312此時，z=85元。314633536312兩種方法確

4、定的初始調運方案對比最小元素法確定的初始調運方案Vogel法確定的初始調運方案3.2.2 最優(yōu)性檢驗的方法閉回路法根據(jù)基的定義，非基變量可以由基變量唯一地線性表示。在表上作業(yè)法中，這種線性表示關系可以由閉回路的形式來體現(xiàn)。（1）（2）（1）（10）（12）（-1）若所有檢驗數(shù)非負則是最優(yōu)解任一空格與有限個有效的有數(shù)字格有且只有唯一的閉回路檢驗數(shù)表3.2.2 最優(yōu)性檢驗的方法位勢法位勢表10219-48（2）（9）（8）（9）（-3）（-2）檢驗數(shù)表（1）從一個檢驗數(shù)為負數(shù)且最小的空格出發(fā)，和其它數(shù)字格構成閉回路。（2）在閉回路上進行運量調整，使選定空格處的運量盡可能地增加。 （3）運量調整后，

5、必然使某個數(shù)字格變成零。把一個變成零的數(shù)字格抹去，得新的調運方案。3.2.3 方案調整的方法閉回路法位勢表10219-48（2）（9）（8）（9）（-3）（-2）檢驗數(shù)表有檢驗數(shù)為負,不是最優(yōu)解。3.2.4 表上作業(yè)法舉例位勢表10128-37（3）（9）（7）（1）（-2）（-2）檢驗數(shù)表表上作業(yè)法舉例(續(xù))檢驗數(shù)都非負，得最優(yōu)解。表上作業(yè)法是以產(chǎn)銷平衡為前提的，即當實際問題產(chǎn)銷不平衡時，需要轉化為產(chǎn)銷平衡的運輸問題，具體來說有兩種情況： （1）產(chǎn)大于銷，即 此時增加一個假想的銷地n+1，該銷地的銷量為 ，而各產(chǎn)地到假想銷地的單位運價定為0，就轉化成產(chǎn)銷平衡的運輸問題。 （2）銷大于產(chǎn)，即

6、此時增加一個假想的產(chǎn)地m+1，該產(chǎn)地的產(chǎn)量為 ，而假想產(chǎn)地到各銷地的單位運價定為0，就轉化成產(chǎn)銷平衡的運輸問題。 3.3 產(chǎn)銷不平衡的運輸問題 產(chǎn)銷不平衡的運輸問題舉例 設有三個化肥廠供應四個地區(qū)的農(nóng)用化肥。各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)運送化肥的單位運價如又表： 試求出總運費最省的花費調運方案。 解：三個廠的總產(chǎn)量為160萬噸，四個地區(qū)的最低需求為110萬噸，最高需求為無限。地區(qū)每年最多能分配到60萬噸，這樣四個地區(qū)最高需求為210萬噸，銷大于產(chǎn)。于是，增加虛產(chǎn)地D，產(chǎn)量為50萬噸。還要把地區(qū)和的產(chǎn)量分為兩部分。建立如下表格模型： 50 20 10 3030 20 0 3

7、0 20 例 某廠按合同規(guī)定須于當年每個季度末分別提供10、15、25、20臺同一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機的成本如右表。又知如果生產(chǎn)出來的柴油機當季度不交貨，每臺每季度的存儲維護費為0.15萬元。試安排全年生產(chǎn)計劃，使總費用最低。 3.4 應用舉例 解：各季度都產(chǎn)出產(chǎn)品，都可看作產(chǎn)地；各季度都有定貨，都可看作銷地。 這是一個產(chǎn)大于銷的運輸問題，需增加虛銷地D。表格模型如下： 產(chǎn)銷平衡表10.810.9511.1011.250 M11.1011.2511.40 0 M M11.0011.15 0 M MM11.30 0單位運價表10 15 0 5 30 20 10 10 例 某航運公司承擔六個港口城市A,B,C,D，E,F間四條航線的貨物運輸任務。各航線的起點、終點、日航班數(shù)如下：假定各航線使用的船只相同，各城市間的航程天數(shù)如下： 又知每條船每次裝卸貨時間各需1天，問該公司至少應配備多少條船？ 為使配備船只數(shù)盡可能少，建立