管理運籌學-05-運輸模型ppt課件

1、 5.1 運輸問題及其數(shù)學模型運輸問題及其數(shù)學模型5.2 表上作業(yè)法表上作業(yè)法5.3 運輸模型的應用運輸模型的應用第第5章章 運輸模型運輸模型5.1 運輸問題及其數(shù)學模型運輸問題及其數(shù)學模型問題的提出問題的提出 運輸問題：產地、銷地、產量、銷量運輸問題：產地、銷地、產量、銷量 例例1 有有A1，A2，A3三座鐵礦，每天要把生產三座鐵礦，每天要把生產的鐵礦石運往的鐵礦石運往B1，B2，B3，B4四個煉鐵廠。各礦四個煉鐵廠。各礦的的產量、各廠的銷量以及各廠礦間的運價如下表所示。產量、各廠的銷量以及各廠礦間的運價如下表所示。問應如何組織調運才能使運費最少？問應如何組織調運才能使運費最少？5.1 運輸

2、問題及其數(shù)學模型運輸問題及其數(shù)學模型B1 B2 B3 B4產量產量A1A2A36 3 2 57 5 8 43 2 9 7523銷量銷量2 3 1 4(百元百元/百噸百噸 )xij Ai運給運給Bj的鐵礦石數(shù)量百噸）的鐵礦石數(shù)量百噸）z 總運費百元）總運費百元）5.1 運輸問題及其數(shù)學模型運輸問題及其數(shù)學模型B1B2B3B4產量產量A163255A275842A332973銷量銷量2314(百元百元/百噸百噸 )x11x12x13x14x21x22x23x24x31x32x33x345.1 運輸問題及其數(shù)學模型運輸問題及其數(shù)學模型 數(shù)學模型為數(shù)學模型為: min z = 6x11+3x12+2x

3、13+5x14+7x21+5x22+8x23+4x24 +3x31+2x32+9x33+7x34 x11+x12+x13+x14 = 5 x21+x22+x23+x24 = 2 x31+x32+x33+x34 = 3 x11 +x21 +x31 = 2 x12 +x22 +x32 = 3 x13 +x23 +x33 = 1 x14 +x24 +x34 = 4 xij0 ( i =1, 2, 3; j =1, 2, 3, 4 )s.t.5.1 運輸問題及其數(shù)學模型運輸問題及其數(shù)學模型表式模型表式模型 產銷平衡的運輸問題產銷平衡的運輸問題: ai=bj 產大于銷的運輸問題產大于銷的運輸問題: ai

4、bj 產小于銷的運輸問題產小于銷的運輸問題: aibjB1B2Bn 產量產量 A1c11 x11c12 x12c1n x1n a1A2c21 x21c22 x22c2n x2na2Amcm1 xm1 cm2 xm2 cmn xmnam銷量銷量b1b2bn aib bj5.1 運輸問題及其數(shù)學模型運輸問題及其數(shù)學模型xij 0 xij = ai i = 1, 2, ，mj=1n xij = bj j = 1, 2, ，ni=1ns.t.min z = i=1nj=1n cij xijLP式式 產銷平衡模型產銷平衡模型 LP式式 產大于銷模型產大于銷模型5.1 運輸問題及其數(shù)學模型運輸問題及其數(shù)學

5、模型xij 0 xij ai i = 1, 2, ，mj=1n xij = bj j = 1, 2, ，ni=1ns.t.min z = i=1nj=1n cij xij5.1 運輸問題及其數(shù)學模型運輸問題及其數(shù)學模型xij 0 xij = ai i = 1, 2, ，mj=1n xij bj j = 1, 2, ，ni=1ns.t.min z = i=1nj=1n cij xijLP式式 產小于銷模型產小于銷模型5.1 運輸問題及其數(shù)學模型運輸問題及其數(shù)學模型 運輸模型有兩個特點：運輸模型有兩個特點： (1) 它有它有mn個變量，個變量，m+n個約束方程個約束方程 (2) 其系數(shù)陣具有特殊的

6、結構其系數(shù)陣具有特殊的結構 m=3行行n=4行行A = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5.2 表上作業(yè)法表上作業(yè)法 基本步驟基本步驟 (1) 確定初始方案；確定初始方案； (2) 進行最優(yōu)性檢驗；進行最優(yōu)性檢驗； (3) 調整、改進非最優(yōu)方案。調整、改進非最優(yōu)方案。5.2 表上作業(yè)法表上作業(yè)法 5.2.1 初始方案的確定初始方案的確定 一、最小元素法一、最小元素法 所謂最小元素，是指作業(yè)表中最小運價所謂最小元素，是指作業(yè)表中最小運價cij。即先給最小運價。即先給最小運價那格安排那格安排運量，然后劃去該運價所在行或列；直到求出初始

7、方案為止。運量，然后劃去該運價所在行或列；直到求出初始方案為止。 1430022222B1B2B3B4產量產量A163255A275842A332973銷量銷量2314 為了保證畫圈數(shù)字為m+n-1個，最小元素法有以下三條原則: (1) 在確定了某一基變量 xlk及其數(shù)值并畫圈以后，若它所在的Al行或Bk列中其余變量均應取 0 值, 也不能同時把Al行和Bk列都劃去，而只能劃去其中之一。 (2) 在確定為最小元素的某一空格上，若該變量 xij = min ai, bj = 0此時也不能保留該空格，而必須把 0 填上并畫圈。 (3) 最后一個空格必須畫圈，即便該格的xij= 0也要填上0并畫圈。

8、 5.2 表上作業(yè)法表上作業(yè)法5.2 表上作業(yè)法表上作業(yè)法 (1) 為了保證畫圈個數(shù)為m +n-1個，每畫1個圈, 只許劃去1行/列，即，行列總數(shù)減少1； 因為行列總數(shù)為 m+n；(2) 再如，當只剩下最后再如，當只剩下最后1行行/列時列時: 當畫了當畫了m+n -2個圈時，未劃去的行列總數(shù)為個圈時，未劃去的行列總數(shù)為即只剩下即只剩下1個空格，只能再畫個空格，只能再畫1個圈，這樣，畫圈個數(shù)個圈，這樣，畫圈個數(shù)恰為恰為m +n -1。 222不僅劃去不僅劃去1 1行，同時也劃行，同時也劃去了所有的列，不可！去了所有的列，不可！5.2 表上作業(yè)法表上作業(yè)法 “最小元素法和“最大差額法所確定的初始方

9、案滿足以下條件： (1) 畫圈數(shù)字的個數(shù)恰好等于線性無關的約束 個數(shù)，即m+n-1個 。 (2) 可行：滿足所有約束條件。 (3) 表中不存在“以畫圈數(shù)字為頂點的閉回路”。 5.2 表上作業(yè)法表上作業(yè)法畫圈數(shù)字為頂點的閉回路畫圈數(shù)字為頂點的閉回路B1B2B3B4產量產量A163255A275842A332973銷量銷量23141132215.2 表上作業(yè)法表上作業(yè)法二、最大差額法二、最大差額法 步驟如下：步驟如下：1 1對每行每列的運價對每行每列的運價cijcij分別計算兩最小元素之差分別計算兩最小元素之差( (取正值取正值) ) ，將將 “行差行差” 記于表右側，記于表右側， “列差列差”

10、記于表下端。記于表下端。2 2在所有行差、列差中選一最大差額，若有幾個同時最大，則在所有行差、列差中選一最大差額，若有幾個同時最大，則可任選其中可任選其中 之一。之一。3 3在最大差額所在行在最大差額所在行( (列列) ) 中選一最小運價，若有幾個同時最小，中選一最小運價，若有幾個同時最小，則可則可 任選其一。任選其一。 4在所確定的最小運價格內，確定基變量數(shù)值并畫圈，然后劃去其所在行 或列，具體做法同最小元素法。 5對剩余未劃去的行列重復上述步驟，但當只剩下最后一行(列) 時，不再 計算行(列)差，而直接按最小元素法分配運量并劃去相應的行或列。 5.2 表上作業(yè)法表上作業(yè)法B1B2B3B4產

11、量產量A163255A275842A332973銷量銷量2314行行 差差列列差差1 11 11 13 31 16 61 16314 42 21 11 121 12 21 15 55212 22 221 12 222 225.2 表上作業(yè)法表上作業(yè)法 5.2.2 最優(yōu)性檢驗最優(yōu)性檢驗 一、位勢法一、位勢法 在初始方案表中在初始方案表中, 可將基變量所在格的運價可將基變量所在格的運價cij分解為兩部分分解為兩部分 ui + vj = cij 其中其中ui代表產地代表產地Ai所在行的行位勢量，所在行的行位勢量，vj代表銷地代表銷地Bj所在列所在列的列位勢量，的列位勢量，cij為畫圈數(shù)字所在格的運價

12、。為畫圈數(shù)字所在格的運價。 所有所有ui，vj的值確定以后，可以證明，的值確定以后，可以證明，ij可按下式計算：可按下式計算： ij = cij ui vj 基變量對應的檢驗數(shù)顯然全都為基變量對應的檢驗數(shù)顯然全都為0，因此，只需計算非基，因此，只需計算非基變量的檢驗數(shù)。這種計算檢驗數(shù)的方法就是位勢法。變量的檢驗數(shù)。這種計算檢驗數(shù)的方法就是位勢法。 5.2 表上作業(yè)法表上作業(yè)法 B1 B2 B3 B4 產產量量 A1 6 3 2 5 5 A2 7 5 8 4 2 A3 3 2 9 7 3 銷銷量量 2 3 1 4 130222ui0-3-3-1-1-2-22171055.2 表上作業(yè)法表上作業(yè)法

13、 二、閉回路法二、閉回路法 閉回路是指以一個非基變量的格子為始點和終點，閉回路是指以一個非基變量的格子為始點和終點，而其而其 余頂點均為畫圈數(shù)字的一條封閉回路。余頂點均為畫圈數(shù)字的一條封閉回路。 符號符號 + 表示始點非基變量），它及其閉回路上標表示始點非基變量），它及其閉回路上標 “+”號的頂點稱為偶點，而標號的頂點稱為偶點，而標 “”號的頂點稱為奇點。號的頂點稱為奇點。 奇偶點的確定：奇偶點的確定： 的某一行進方向交錯地標記奇偶符號。的某一行進方向交錯地標記奇偶符號。 那那么么 標標 號，號， +-然后沿著閉回路然后沿著閉回路即即5.2 表上作業(yè)法表上作業(yè)法B1B2B3B4產量產量A163

14、255A275842A332973銷量銷量2314121222 +- - - -+補表補表 以最大差額法所確定方案及其閉回路為例以最大差額法所確定方案及其閉回路為例= 45.2 表上作業(yè)法表上作業(yè)法 5.2.3 非優(yōu)方案的調整 在進基變量的閉回路上的所有奇點中, 選擇數(shù)值最小的那個作為離基變量, 并且取它的值作為調整量。 B1 B2 B3 B4 產產量量 A1 6 3 2 5 5 A2 7 5 8 4 2 A3 3 2 9 7 3 銷銷量量 2 3 1 4 130222ui0-3 -3 -1 -1 -2 -2 217105 +- - -+5.2 表上作業(yè)法表上作業(yè)法 B1 B2 B3 B4 產

15、產量量 A1 6 3 2 5 5 A2 7 5 8 4 2 A3 3 2 9 7 3 銷銷量量 2 3 1 4 13022ui0-3-3-1-1-2-2217105 +- - -+2調整之，調整之，2215.2 表上作業(yè)法表上作業(yè)法122122ui0-1-1-1-1243783為最優(yōu)方案，為最優(yōu)方案，對所得新方案用位勢法檢驗：對所得新方案用位勢法檢驗：與最大差額法初始方案相同。與最大差額法初始方案相同。5.2 表上作業(yè)法表上作業(yè)法調整非優(yōu)方案的一般步驟與規(guī)則調整非優(yōu)方案的一般步驟與規(guī)則 1進基變量的確定進基變量的確定規(guī)則規(guī)則 按按 min ijij i ). cij = ci + c( j - i ) 130100 15 25 35 25 銷 量30354520 c11 c12 c13 c14 c21 c22 c23 c24 c31 c32 c33 c34 c41 c42 c43 c44 產產 量量 銷期i