運(yùn)輸問題及其數(shù)學(xué)模型

1、例1產(chǎn)地產(chǎn)地A1A2A3三產(chǎn)地四銷地三產(chǎn)地四銷地, 同類可互換產(chǎn)品，單位運(yùn)價同類可互換產(chǎn)品，單位運(yùn)價(元元/ t ), 如何調(diào)運(yùn)，運(yùn)費(fèi)最少？如何調(diào)運(yùn)，運(yùn)費(fèi)最少？794產(chǎn)量產(chǎn)量x 21x 22x 23x 24x 11x 12x 13x 14x 31x 32x 33x 34銷量銷量6635198231110374510B1銷地銷地B2B4B3= 3 x11 + 11 x12 + 3 x13 + 10 x 14 + x 21 + 9x22 + 2 x23 + 8x24 + 7 x 31 + 4 x32 + 10 x33 + 5 x34 x 11 +x12 + x13 + x14 = 7 . .tsx

2、11 + x21 + x31 = 3x i j 0, ( i = 1, 2, 3 ; j = 1, 2, 3, 4 )數(shù)學(xué)模型數(shù)學(xué)模型i = 13min Z = c i j x i jj = 14x 21 +x22 + x23 + x24 = 4x12 + x22 + x32 = 6x 31 +x32 + x33 + x34 = 9x13 + x23 + x33 = 5x14 + x24 + x34 = 6第一節(jié)第一節(jié) 運(yùn)輸問題及其數(shù)學(xué)模型運(yùn)輸問題及其數(shù)學(xué)模型一 、運(yùn)輸問題數(shù)學(xué)模型產(chǎn)地產(chǎn)地A1A2Am.B1銷地銷地B2B n銷量銷量b 2b nb 1a1.ama2產(chǎn)量產(chǎn)量x 11x 12x 1

3、nx 21x 22x 2nx m1x m2x m n.c 11c 12c 1nc 21c 22c 2nc m1c m2c m n產(chǎn)銷平衡運(yùn)輸問題數(shù)學(xué)模型產(chǎn)銷平衡運(yùn)輸問題數(shù)學(xué)模型i = 1mmin Z = c i j x i jj = 1n平衡平衡 (產(chǎn)產(chǎn)=銷銷)i = 1Q =j = 1m a i = b jnx i j 0 , ( i=1, 2, , m; j=1, 2, , n )( i = 1, 2, , m ) x i j = a i ,j = 1n( j = 1, 2, , n ) x i j = b j ,i = 1mm+n個方程中只有個方程中只有m+n-1個方程是獨(dú)立的個方程是獨(dú)

4、立的, 運(yùn)輸問題的運(yùn)輸問題的 基本可行解基本可行解 有有 m+n-1 個分量個分量1. 運(yùn)輸問題有有限最優(yōu)解運(yùn)輸問題有有限最優(yōu)解2. 運(yùn)輸問題約束條件的系數(shù)矩陣運(yùn)輸問題約束條件的系數(shù)矩陣二二、運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)運(yùn)輸問題數(shù)學(xué)模型的特點(diǎn)x11 x12 x1nxm1 xm2 x m n x 21 x22 x2n 1 1 1 .1 1 1 1 1 1 A i j = ( 0, , 0, 1, 0, , 0, 1, , 0 ) 第第 i 個個 第第(m+ j)個個 1 11 1 11 1 11 .m+n個方程中只有個方程中只有m+n-1個方程是獨(dú)立的個方程是獨(dú)立的, 運(yùn)輸問題的運(yùn)輸問題的 基本可行解

5、基本可行解 有有 m+n-1 個分量個分量. .n個個m個個前前m個之和等于后個之和等于后n個之和個之和 2 表上作業(yè)法表上作業(yè)法 銷量銷量6635794產(chǎn)量產(chǎn)量例1最小元素法最小元素法產(chǎn)地產(chǎn)地A1A2A33銷地銷地34361初始調(diào)運(yùn)方案初始調(diào)運(yùn)方案 ( 初始基可行解初始基可行解 )3198231110374510B1B2B 4B3134386 元元銷量銷量6635794產(chǎn)量產(chǎn)量例1最小元素法最小元素法產(chǎn)地產(chǎn)地A1A2A33銷地銷地4361初始調(diào)運(yùn)方案初始調(diào)運(yùn)方案 ( 初始基可行解初始基可行解 )198231110374510B1B2B 4B3386 元元空格空格為非為非基變量基變量銷量銷量6

6、635794產(chǎn)量產(chǎn)量例1沃格爾沃格爾(Vogel)法法 產(chǎn)地產(chǎn)地A1A2A31銷地銷地34225 ( 初始基可行解初始基可行解 )行罰數(shù)行罰數(shù)311103B1B2B 4B320列列罰罰數(shù)數(shù)19827451013 42551301121321201201363322532121217600兩最小元素之差兩最小元素之差兩最小元素之差兩最小元素之差-閉回路法閉回路法1此空格為入基變量此空格為入基變量。由一個空格和若干個有數(shù)字的水平和垂直連線包圍成的由一個空格和若干個有數(shù)字的水平和垂直連線包圍成的封閉回路封閉回路。銷量銷量6635794產(chǎn)量產(chǎn)量例1閉回路法閉回路法調(diào)整調(diào)整產(chǎn)地產(chǎn)地A1A2A33銷地銷地

7、4361非基變量（空格）的檢驗(yàn)數(shù)非基變量（空格）的檢驗(yàn)數(shù)198231110374510B1B2B 4B3386 元元 ， min(3,1)=1從空格出發(fā)沿封閉回路前進(jìn)從空格出發(fā)沿封閉回路前進(jìn), 順時逆時均可順時逆時均可.檢驗(yàn)數(shù)檢驗(yàn)數(shù)8-2+3-10= -1，需調(diào)整，需調(diào)整銷量銷量6635794產(chǎn)量產(chǎn)量例1產(chǎn)地產(chǎn)地A1A2A33銷地銷地536初始調(diào)運(yùn)方案初始調(diào)運(yùn)方案 ( 初始基可行解初始基可行解 )198231110374510B1B2B 4B3286 元元 ， min(3,1)=1從空格出發(fā)沿封閉回路前進(jìn)從空格出發(fā)沿封閉回路前進(jìn), 順時逆時均可順時逆時均可.185元元vj910230-5-1u

8、i二、解的最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn) - 位勢法位勢法2產(chǎn)地產(chǎn)地A1A2A33銷地銷地4361198231110374510B1B2B 4B3386 元元121-110127個變量個變量6個方程需補(bǔ)充一個方程個方程需補(bǔ)充一個方程 u1=0基變量的檢驗(yàn)數(shù)為基變量的檢驗(yàn)數(shù)為 0vj910230-5-1ui二、解的最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn) - 位勢法位勢法產(chǎn)地產(chǎn)地A1A2A33銷地銷地4361198231110374510B1B2B 4B3386 元元121-11012調(diào)整量：調(diào)整量：min(3, 1)=1找出找出非基變量的檢驗(yàn)數(shù)非基變量的檢驗(yàn)數(shù)為為負(fù)空格負(fù)空格的的閉回路閉回路vj910330-5-2ui二、

9、解的最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn) - 位勢法位勢法產(chǎn)地產(chǎn)地A1A2A33銷地銷地4361198231110374510B1B2B 4B3386 元元185元元52調(diào)整量：調(diào)整量：min(3, 1)=1找出找出非基變量的檢驗(yàn)數(shù)非基變量的檢驗(yàn)數(shù)為為負(fù)空格負(fù)空格的的閉回路閉回路vj910330-5-2ui二、解的最優(yōu)性檢驗(yàn)最優(yōu)性檢驗(yàn) - 位勢法位勢法產(chǎn)地產(chǎn)地A1A2A33銷地銷地2362198231110374510B1B2B 4B3086 元元185元元52非基變量的檢驗(yàn)數(shù)非基變量的檢驗(yàn)數(shù)無無負(fù)值負(fù)值，最優(yōu)方案！，最優(yōu)方案！1219最優(yōu)解不唯一最優(yōu)解不唯一表上作業(yè)法一. 給出運(yùn)輸問題的初始基可行解（初始調(diào)運(yùn)方案）三. 解的改進(jìn)1. 最小元素法二. 解的最優(yōu)性檢驗(yàn)2. 位勢法(Dual variable method)1. 閉回路法2. Vogel 法a. 閉回路；b. 每個空格都唯一存在一條閉回路 閉回路；表上作業(yè)計算框圖分析問題列出產(chǎn)銷平衡表及單位運(yùn)價表確定初始調(diào)運(yùn)方案求檢驗(yàn)數(shù)(閉回路法或位勢法)所有檢驗(yàn)數(shù)0對絕對值最大的負(fù)檢驗(yàn)數(shù)用閉回路法調(diào)整，得出新調(diào)運(yùn)方案得到最優(yōu)方案算出總運(yùn)價是是否否五. 供求不平衡運(yùn)輸問題例2B1B2B3B4產(chǎn)量A1211347A2103595A378127銷量2346B1B2B3B4B5產(chǎn)量A