MBA學位課程-運籌學(二)(ppt 142頁)

一、產銷平衡的運輸問題及其解法
二、產銷不平衡的運輸問題及其求解方法
三、轉運問題及其解法

引例：某公司經銷甲產品，它下設三個加工廠，每日的產量分別為：A1-40噸，A2-40噸，A3-90噸。該公司把這些產品分別運往四個銷售點，各銷售點每日銷量為：B1-30噸，B2-40噸，B3-60噸，B4-20噸, B5-20噸。已知從各工廠到各銷售點的單位產品的運價為下表所示。問該公司應如何調運產品，在滿足各銷售點需求量的前提下，使總運費為最少
（2）用閉回路法或位勢法求空格的檢驗數
1) 用閉回路法求檢驗數：
首先，每一個空格有且僅有一個閉回路，而圈格無閉回路。
閉回路是以空格為起點，沿同一行或同一列前進，遇上圈格可轉90度繼續前進，按此方法進行下去，直到回到始點的一個封閉折線。
以始點為第0個點，依次給閉回路上的每一個頂點編號。其中奇序數對應的為奇頂點，偶數對應的為偶頂點。
其次，每一個空格的檢驗數=奇頂點運費之和 – 偶頂點運費之和。
2)用位勢法求出空格的檢驗數並進行最優解的判別
設u1,u2,…um; v1,v2,…,vn是對應運輸問題m+n個約束條件的對偶變量，B為含有人工變量的初始可行基，由LP問題的對偶理論知：CBB-1=(u1,u2,…um; v1,v2,…,vn)
而每個決策變量Xij相應的係數向量Pij=ei+em+j，所以CBB-1Pij=ui+vj， 於是，檢驗數σij=CBB-1Pij－Cij =(ui+vj)－Cij
又各基變量的檢驗數為0，故對每個基變量所在的圈格的檢驗數有

..............................