4-1運輸問題的數(shù)學(xué)模型

1、1第一節(jié) 運輸問題及其數(shù)學(xué)模型 運輸問題是一類特殊的線性規(guī)劃運輸問題是一類特殊的線性規(guī)劃問題，本節(jié)介紹運輸問題的數(shù)學(xué)模型問題，本節(jié)介紹運輸問題的數(shù)學(xué)模型及其約束方程組的系數(shù)矩陣結(jié)構(gòu)的特及其約束方程組的系數(shù)矩陣結(jié)構(gòu)的特殊性，運輸問題的對偶問題及其對偶殊性，運輸問題的對偶問題及其對偶變量。變量。2運輸問題運輸問題典型背景：單一物資的運輸調(diào)度問題設(shè)某種物品有: m個產(chǎn)地： 產(chǎn)量： n個銷地： 銷量： 從產(chǎn)地 到銷地 的單位運價是 。 求總運費最小的調(diào)度方案。mAAA,21nBBB,21maaa,21nbbb,21iAjBijc3運輸問題運輸問題n決策變量決策變量 表示由表示由 到到 的運量。的運量。

2、iAjBijx12c11cnc121c22cnc21mc2mcmncnmmnmmmnnnbbbaxxxAaxxxAaxxxABBB21212222212111211121銷地產(chǎn)地銷量銷量產(chǎn)量產(chǎn)量4運輸問題運輸問題n產(chǎn)銷平衡問題總產(chǎn)量=總銷量 即n產(chǎn)銷不平衡問題總產(chǎn)量=總銷量11mnijijab5運輸問題運輸問題 njmixnjbxmiaxxczijjmiijinjijminjijij,2,1,2,1,0,2,1,2,1,min1111產(chǎn)地i運到n個銷地的運量的總和，應(yīng)該等于產(chǎn)地i的產(chǎn)量。m個產(chǎn)地運到銷地j的運量的總和，應(yīng)該等于銷地j的銷量。6運輸問題運輸問題舉例說明 某部門三個工廠生產(chǎn)同一產(chǎn)品

3、的產(chǎn)量,四個銷售點的銷量及單位運價如下表：412285439611111012341231 61 02 281 41 21 44 8BBBBAAA銷量銷量產(chǎn)量產(chǎn)量銷地產(chǎn)地7運輸問題運輸問題運輸問題數(shù)學(xué)模型的特點n運輸問題肯定有最優(yōu)解n運輸問題約束條件的系數(shù)矩陣（下頁） 約束條件系數(shù)矩陣每一列只有兩個1，其余為0；對產(chǎn)銷平衡問題對產(chǎn)銷平衡問題 約束條件均為等式，且產(chǎn)量之和=銷量之和； 約束條件的獨立方程最多有m+n-1個，即1)(nmAr8運輸問題運輸問題把m+n個約束分別展開，11121121222212nnmmmnmxxxaxxxamxxxa 個11211112222212mmnnmnnxx

4、xbxxxbnxxxb 個寫出其寫出其(m+n)*(m*n)維的維的系數(shù)系數(shù)矩陣矩陣9運輸問題運輸問題111111111111111111mnmmnnxxxxxxxxx212222111211mnnP210運輸問題運輸問題00100100ijijPx 的列向量im+jimjee00100ie其中11運輸問題運輸問題運輸問題的對偶問題 對產(chǎn)銷平衡運輸問題 前m個約束等式相應(yīng)的對偶變量 后n個約束等式相應(yīng)的對偶變量即對偶變量為12,muuu12,nvvv1212( , ,)mnYu uuv vv12運輸問題運輸問題11121121222212nnmmmnmxxxaxxxamxxxa 個11211112222212mmnnmnnxxxbxxxbnxxxb 個12muuu12nvvv13運輸問題運輸問題11max,1,;. .1, .,mniijjijijijijza ub vuvcim