管理運(yùn)籌學(xué)-05-運(yùn)輸模型ppt課件

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

2、問題及其數(shù)學(xué)模型運(yùn)輸問題及其數(shù)學(xué)模型B1 B2 B3 B4產(chǎn)量產(chǎn)量A1A2A36 3 2 57 5 8 43 2 9 7523銷量銷量2 3 1 4(百元百元/百噸百噸 )xij Ai運(yùn)給運(yùn)給Bj的鐵礦石數(shù)量百噸）的鐵礦石數(shù)量百噸）z 總運(yùn)費(fèi)百元）總運(yùn)費(fèi)百元）5.1 運(yùn)輸問題及其數(shù)學(xué)模型運(yùn)輸問題及其數(shù)學(xué)模型B1B2B3B4產(chǎn)量產(chǎn)量A163255A275842A332973銷量銷量2314(百元百元/百噸百噸 )x11x12x13x14x21x22x23x24x31x32x33x345.1 運(yùn)輸問題及其數(shù)學(xué)模型運(yùn)輸問題及其數(shù)學(xué)模型 數(shù)學(xué)模型為數(shù)學(xué)模型為: 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 運(yùn)輸問題及其數(shù)學(xué)模型運(yùn)輸問題及其數(shù)學(xué)模型表式模型表式模型 產(chǎn)銷平衡的運(yùn)輸問題產(chǎn)銷平衡的運(yùn)輸問題: ai=bj 產(chǎn)大于銷的運(yùn)輸問題產(chǎn)大于銷的運(yùn)輸問題: ai

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

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 運(yùn)輸問題及其數(shù)學(xué)模型運(yùn)輸問題及其數(shù)學(xué)模型xij 0 xij = ai i = 1, 2, ，mj=1n xij bj j = 1, 2, ，ni=1ns.t.min z = i=1nj=1n cij xijLP式式 產(chǎn)小于銷模型產(chǎn)小于銷模型5.1 運(yùn)輸問題及其數(shù)學(xué)模型運(yùn)輸問題及其數(shù)學(xué)模型 運(yùn)輸模型有兩個(gè)特點(diǎn)：運(yùn)輸模型有兩個(gè)特點(diǎn)： (1) 它有它有mn個(gè)變量，個(gè)變量，m+n個(gè)約束方程個(gè)約束方程 (2) 其系數(shù)陣具有特殊的

6、結(jié)構(gòu)其系數(shù)陣具有特殊的結(jié)構(gòu) 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) 進(jìn)行最優(yōu)性檢驗(yàn)；進(jìn)行最優(yōu)性檢驗(yàn)； (3) 調(diào)整、改進(jìn)非最優(yōu)方案。調(diào)整、改進(jìn)非最優(yōu)方案。5.2 表上作業(yè)法表上作業(yè)法 5.2.1 初始方案的確定初始方案的確定 一、最小元素法一、最小元素法 所謂最小元素，是指作業(yè)表中最小運(yùn)價(jià)所謂最小元素，是指作業(yè)表中最小運(yùn)價(jià)cij。即先給最小運(yùn)價(jià)。即先給最小運(yùn)價(jià)那格安排那格安排運(yùn)量，然后劃去該運(yùn)價(jià)所在行或列；直到求出初始

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

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

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

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

11、量產(chǎn)量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àn)最優(yōu)性檢驗(yàn) 一、位勢(shì)法一、位勢(shì)法 在初始方案表中在初始方案表中, 可將基變量所在格的運(yùn)價(jià)可將基變量所在格的運(yùn)價(jià)cij分解為兩部分分解為兩部分 ui + vj = cij 其中其中ui代表產(chǎn)地代表產(chǎn)地Ai所在行的行位勢(shì)量，所在行的行位勢(shì)量，vj代表銷地代表銷地Bj所在列所在列的列位勢(shì)量，的列位勢(shì)量，cij為畫圈數(shù)字所在格的運(yùn)價(jià)

12、。為畫圈數(shù)字所在格的運(yùn)價(jià)。 所有所有ui，vj的值確定以后，可以證明，的值確定以后，可以證明，ij可按下式計(jì)算：可按下式計(jì)算： ij = cij ui vj 基變量對(duì)應(yīng)的檢驗(yàn)數(shù)顯然全都為基變量對(duì)應(yīng)的檢驗(yàn)數(shù)顯然全都為0，因此，只需計(jì)算非基，因此，只需計(jì)算非基變量的檢驗(yàn)數(shù)。這種計(jì)算檢驗(yàn)數(shù)的方法就是位勢(shì)法。變量的檢驗(yàn)數(shù)。這種計(jì)算檢驗(yàn)數(shù)的方法就是位勢(shì)法。 5.2 表上作業(yè)法表上作業(yè)法 B1 B2 B3 B4 產(chǎn)產(chǎn)量量 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、 二、閉回路法二、閉回路法 閉回路是指以一個(gè)非基變量的格子為始點(diǎn)和終點(diǎn)，閉回路是指以一個(gè)非基變量的格子為始點(diǎn)和終點(diǎn)，而其而其 余頂點(diǎn)均為畫圈數(shù)字的一條封閉回路。余頂點(diǎn)均為畫圈數(shù)字的一條封閉回路。 符號(hào)符號(hào) + 表示始點(diǎn)非基變量），它及其閉回路上標(biāo)表示始點(diǎn)非基變量），它及其閉回路上標(biāo) “+”號(hào)的頂點(diǎn)稱為偶點(diǎn)，而標(biāo)號(hào)的頂點(diǎn)稱為偶點(diǎn)，而標(biāo) “”號(hào)的頂點(diǎn)稱為奇點(diǎn)。號(hào)的頂點(diǎn)稱為奇點(diǎn)。 奇偶點(diǎn)的確定：奇偶點(diǎn)的確定： 的某一行進(jìn)方向交錯(cuò)地標(biāo)記奇偶符號(hào)。的某一行進(jìn)方向交錯(cuò)地標(biāo)記奇偶符號(hào)。 那那么么 標(biāo)標(biāo) 號(hào)，號(hào)， +-然后沿著閉回路然后沿著閉回路即即5.2 表上作業(yè)法表上作業(yè)法B1B2B3B4產(chǎn)量產(chǎn)量A163

14、255A275842A332973銷量銷量2314121222 +- - - -+補(bǔ)表補(bǔ)表 以最大差額法所確定方案及其閉回路為例以最大差額法所確定方案及其閉回路為例= 45.2 表上作業(yè)法表上作業(yè)法 5.2.3 非優(yōu)方案的調(diào)整 在進(jìn)基變量的閉回路上的所有奇點(diǎn)中, 選擇數(shù)值最小的那個(gè)作為離基變量, 并且取它的值作為調(diào)整量。 B1 B2 B3 B4 產(chǎn)產(chǎn)量量 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 產(chǎn)

15、產(chǎn)量量 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調(diào)整之，調(diào)整之，2215.2 表上作業(yè)法表上作業(yè)法122122ui0-1-1-1-1243783為最優(yōu)方案，為最優(yōu)方案，對(duì)所得新方案用位勢(shì)法檢驗(yàn)：對(duì)所得新方案用位勢(shì)法檢驗(yàn)：與最大差額法初始方案相同。與最大差額法初始方案相同。5.2 表上作業(yè)法表上作業(yè)法調(diào)整非優(yōu)方案的一般步驟與規(guī)則調(diào)整非優(yōu)方案的一般步驟與規(guī)則 1進(jìn)基變量的確定進(jìn)基變量的確定規(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 產(chǎn)產(chǎn) 量量 銷期i