資源描述：
《運籌學運輸問題ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、第四章運輸問題運輸問題的表示網(wǎng)絡圖、線性規(guī)劃模型、運輸表初始基礎可行解西北角法、最小元素法非基變量的檢驗數(shù)閉回路法、對偶變量法確定進基變量，調(diào)整運量，確定離基變量1運輸問題的提出運輸問題的直接背景是單一品種的物質(zhì)的運輸調(diào)度問題，其典型情況是：設某物品有m個產(chǎn)地A1,A2,…,Am,各產(chǎn)地的產(chǎn)量分別為a1,a2,…,am;n個銷地B1,B2,…,Bn,各銷地的銷量分別為b1,b2,…,bn.假定從產(chǎn)地Ai(i=1,2,…,m)向銷地Bj(j=1,2,…,n)運輸單位物質(zhì)的運價為cij,問怎樣調(diào)運這些物品才能使得總運費最??？2運
2、輸問題的表示——網(wǎng)絡圖A1A2Am產(chǎn)地B1B2Bn銷地a1a2amb1b2bnc11c12c1nc21c22c2ncm1cm2cmn若則稱該問題為平衡運輸問題，否則稱為非平衡運輸問題。3運輸問題的表示—表格表示這個表常稱為運輸表4運輸問題的數(shù)學模型平衡問題的數(shù)學模型為各產(chǎn)地運出的物資數(shù)量等于其產(chǎn)量各銷地接受的物資數(shù)量等于其銷量其中5運輸問題數(shù)學模型的特點運輸問題一定存在最優(yōu)解實際上是平衡運輸問題的一個可行解。此外由于目標函數(shù)有下界，因此平衡運輸問題存在最優(yōu)解。6運輸問題系數(shù)矩陣的特點mn7上述矩陣的列向量具有形式第i個第(m
3、+j)個因此運輸問題約束條件系數(shù)矩陣的元素只能是0或1，對應變量xij列除了第i個與第(m+j)個分量為1外，其它分量均為零8此外產(chǎn)銷平衡運輸問題的數(shù)學模型還具有特點：所有約束條件都是等式前m個約束條件的和等于后n個約束條件的和（可以證明盡管有m+n個約束條件，但獨立的約束條件只有m+n-1個）9運輸問題的例子—表格表示10運輸問題的例子—線性規(guī)劃模型供應地約束需求地約束11運輸問題的解運輸問題的解可以表示為X=(xij),它表示一個運輸方案，其中xij表示從產(chǎn)地Ai到銷地Bj運送的物質(zhì)數(shù)量在用運輸表表示運輸問題時，也常將x
4、ij取的值填入對應的格子表示一個解。但是對基可行解，通常僅將基變量取的值填入相應的格中，稱之為數(shù)字格，而對應著非基變量的格子，則不填數(shù)字，稱之為空格。注：在一個基可行解中，所有mn個變量（格子）中，只有m+n-1個基變量（數(shù)字格）12求解運輸問題的表上作業(yè)法13求初始基可行解（初始調(diào)運方案）西北角法最小元素法沃格爾法14初始基可行解—西北角法886481415初始基可行解—最小元素法8210148616沃格爾（Vogel）法2（5）130111421（3）0128（2）1201812（7）6122417檢驗數(shù)的計算兩種方法：
5、閉回路法和對偶變量法閉回路法的原理：非基變量的檢驗數(shù)等于非基變量增加一個單位時，目標函數(shù)的改變量18檢驗數(shù)的計算—閉回路法（1）82101486119檢驗數(shù)的計算—閉回路法（2）821014861220檢驗數(shù)的計算—閉回路法（3）8210148612121檢驗數(shù)的計算—閉回路法（4）82101486121-122檢驗數(shù)的計算—閉回路法（5）82101486121-11023檢驗數(shù)的計算—閉回路法（6）82101486121-1101224檢驗數(shù)的計算—對偶變量法對偶變量法也稱為位勢法，它是利用運輸問題的對偶問題求檢驗數(shù)。設運
6、輸問題的對偶變量矩陣為則對偶問題為25利用單純形法的矩陣表示可知，變量xij的檢驗數(shù)可以表示為另一方面，對于(m+n-1)個基變量而言，檢驗數(shù)等于零，故可以得到包含(m+n)個變量的(m+n-1)個方程由該方程組求出對偶變量后即可計算出所有的檢驗數(shù)。26檢驗數(shù)的計算—對偶變量法82101486u1=0v3=4v4=11u2=-1u3=-5v1=3v2=10121-1101227解的改進82101486-128解的改進8121484229解的改進81214842u1=0v3=4v4=11u2=-2u3=-5v1=4v2=100
7、22191230最優(yōu)解（最優(yōu)調(diào)運方案）81214842最小運費：31表上作業(yè)法的幾個問題換入變量的確定退化（兩種情況）無窮多個最優(yōu)解的判別32產(chǎn)銷不平衡的運輸問題解決的基本思路：將其轉(zhuǎn)化為產(chǎn)銷平衡的運輸問題求解33產(chǎn)大于銷的運輸問題這時有，數(shù)學模型為34處理的辦法為增加一個假想的銷地Bn+1，其銷量為各個產(chǎn)地運送物質(zhì)到假想銷地的單位運價為零，即ci(n+1)=035假想的銷地36這時有，數(shù)學模型為銷大于產(chǎn)的運輸問題37處理的辦法為增加一個假想的產(chǎn)地Am+1，其產(chǎn)量為假想產(chǎn)地運送物質(zhì)到各個銷地的單位運價為零，即c(m+1),1
8、=038假想的產(chǎn)地39表上作業(yè)法的計算步驟：分析實際問題列出產(chǎn)銷平衡表及單位運價表確定初始調(diào)運方案（最小元素法或Vogel法）求檢驗數(shù)（位勢法）所有檢驗數(shù)≥0找出絕對值最大的負檢驗數(shù)，用閉合回路調(diào)整，得到新的調(diào)運方案得到最優(yōu)方案，算出總運價40表上作業(yè)法計算中的問題：（1）若運輸問題的某一
