Chapter7运输问题与指派问题ppt课件.ppt

《Chapter7运输问题与指派问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter7運輸問題與指派問題17.1　緒言企業管理者經常會遇到特殊形式的線性規劃，運輸問題(transportationproblem)和指派問題(assignmentproblem)就是其中最常見的兩種。所謂「運輸問題」，是指由數個供應點將物品運送至數個需求點的問題。27.2　運輸問題的標準架構運輸問題有如下基本假設：運送的貨物為同質(亦即，無論起點與終點，貨物相同)。無論運貨數量多寡，每單位運輸成本都相同。各起點與各終點之間的運輸路線只有一條。求解過程有下列主要步驟：求初始基本可行解。為最優性測試初始解。持續

2、改進次優解。34567.3　運輸問題的初始基本可行解77.3.1　西北角法87.3.2　最佳空格法97.3.3　佛格爾法另外一個強而有力的方法是處置「第一差額」(firstdifferences)的佛格爾法(Vogel’sapproximationmethod,VAM)或稱「差額法」。所謂「第一差額」是指行或列中最低成本與次低成本相差的值。VAM的想法是著重於成本相對性的懲罰。如果解題者未能在每一行與列將所有供應量和需求量放在成本最低的位置，則必須受罰。在找到有最高罰款(penaltyvalue)的行或列後，解題者盡可

3、能指派運送量於最低成本的位置，而後再次評估所剩空位的罰款，重複進行這種程序，直到得出一個可行解。107.4　最優解的驗證117.4.1　踏石法(環路法)(1,3)(2,3)(2,2)(1,2)淨影響：5-20+15-30=-3012將西北法的結果，經由踏石法修正後，與VAM法結果一樣13大規模題目要用踏石法很困難147.6　指派問題指派問題中所有的供應與需求均等於1，即將個來源和目的地形成1對1的關係，使成本最低或總利潤最大。157.7　指派問題的解法指派問題可以採取如下三種方法之一解題：運輸問題求解。窮舉法。匈

4、牙利法。16窮舉法17181920217.8　匈牙利法222324252627282930313233343536