【天津大學】《運籌學》（精品課） P25 - 25. 運輸問題—教學錄像（1）

大家好,我們現在開始上課,線性規劃問題的第五節是運輸問題,運輸問題在我們日常生活中隨處可見,比如說我們有某種產品,它有m個不同的產地,有n個銷地,那麼我們運輸問題要解決的什麼樣的問題呢? 就是假設有產地愛運往銷地z的單運輸單價一隻的情況下,如何確定最優的調運方案能夠使得我們總的運費最低,這就是我們所要解決的運輸問題,如果用數學語言來描述這一類問題呢,應該怎樣進行描述? 假設生產某種產品,它有m個產地,我們分別命名爲大a1a2一直到am,每個產地對應的產量呢,分別爲小a1a2一直到am,同時存在n個銷地,這些銷地分別命名爲b1b2一直到bn,它們對應的銷量分別爲小b1b2到bn, 並且已知有產地ai運送到銷地bz的運輸單價爲cij,那麼問題是如何確定有產地ai運往銷地bz的運輸量xij使得總運費最低,從這個問題的一般表述形式,我們可以看到運輸問題的定義主要是根據產量與銷量或者說產銷之間的關係來進行定義, 那麼我與此對應呢,我們對它進行分類的時候呢,也是主要根據產銷的關係來進行分類的,最簡單的一類問題應該是什麼問題啊,對產銷平衡的問題,所謂產銷平衡的問題就是產量是等於銷量的,這種情況下也就是cij從1到m是等於cij從1到n的, 那麼既然存在產銷平衡問題,那就存在產銷不平衡問題,產銷不平衡問題呢又可以分爲兩類,一類是產小於銷,也就是我們經濟學中經常講到的供不應求的問題,這時候應該存在這樣的關係,cij從1到m是小於cij從1到n的,與此相反,那就是產大於銷,也就是供過於求的問題,存在的關係是cij從1到m是小於cij從1到n的,與此相反,那就是產大於銷,也就是供過於求的問題,存在的關係是cij從1到m是小於cij從1到n的,與此相反,那就是產大於銷,也就是供 現在的研究表明,就是所有的產銷不平衡問題,都可以轉化爲產銷平衡問題,如何進行轉化呢? 我們將在本一節的,後面一部份內容,進行講解,那麼給出了這類問題的一般的提法,同時給出了這個運輸問題的分類方式, 那麼接下來我們要看 如果求解這類問題 我們應該如何來進行 表示顯然呢 大家想他最起碼的有一個什麼樣的表述方式啊 線性規劃模型是不是 最傻瓜的一個定理是我們將他放在了線性規劃這一章來講 當然他是一個線性規劃 問題那麼除此之外還有沒有其他的表述方式呢 我們課堂上會講到如下兩種表述方式 一種是網絡圖的表述方式 通過教材的目錄可以看到呢 圖與網絡分析是我們本課程的 非常重要的內容之一 那麼有關網絡圖的表示呢 當然也是非常重要的 運輸問題的網絡圖表示 我們今天課堂上會講到 那麼他的求解方式呢 將在圖與網絡分析這一章中的進行講解 另外一種表示方式呢 就是運輸表的表示方式 這也是運輸問題的 典型特點之一 也是我們爲什麼把它作爲一種非常典型的特殊的吸引性規劃問題 單獨提出來進行講解的重要原因之一 下面我們首先看一道例題 某食品公司下設三個加工廠 a1 a2 a3和四個門市部 b1 b2 b3 b4 各加工廠每天的產量 各門市部每天的銷量 以及從各加工廠到各門市部的運價 以致 該公司應如何確定 調運方案在滿足各門市部銷售需要的情況下 使得運費支出爲最少 我們先看一下這個表 這個表告訴我們現在呢 它有幾個產地a1a2a3三個產地有幾個銷地呢 b1 b2b3b4有四個銷地 產地a1的產量爲7 a2的產量爲4a3的產量爲9 消地b1的銷量爲3b2的銷量爲6b3的銷量爲5b4的銷量爲6 由產地a1運送到消地b1的單位運價爲3 由產地a1運送到消地b2的單位運價爲 11同樣的我們可以將其他的單位運價都填在這個表中 9287是15 好 這就是告訴我們的已知信息 那麼通過這個已知信息呢 我們看呢 如果用網絡圖如何來對對它進行描述 首先已知有三個產地 所以我們 產地也就是供應地存在a1a2a3它們的產量分別爲7是9 供應量也就是產量 那麼共有幾個需求地呢 四個需求地也就是四個銷地b1b2b3b4對應的銷量分別爲3656 需求量爲3656 也就是說 那麼有產地a1是可以將產品運送到任何一個 消地的 所以由a1可以 與所有的消地進行聯繫 那麼 由a1運往b1的運價呢 單位運價是3 我們將它標在對應的線條上31130 那麼同樣由a2也可以運送到所有的銷地 他們對應的這個單位運價也是一致的1928 由這個產地a3也可以運送到所有的銷地 對應的單位運價也是一致的 那麼好 但呢 我們看這個網絡圖是否已經表示了我們的所有的已知信息 對答案是肯定的 我們接着再看 如果用運輸表的形式來表示的話 應該怎樣進行表示呢 這樣一個表 我們看與剛纔我們黑板上所給出的這個表有什麼區別 這個表我們看到呢 他將單位運價標在了由產地ai到消地bj對應的那個格的左上角 在右下角表示的是什麼 運輸量 對不對 那麼這個表是不是表示了所有的已知信息呢 答案是肯定的 那麼再看第三種表示方式 也就是線性規劃的 表示方式 這一類問題或者說這種表述方式大家應該非常熟悉 首先 我們看是否他是滿足我們線性規劃的表述方式的呢 三要素 我們看是否具備呢 是具備三要素的 對嗎 決策變量應該怎樣設呢 這個決策變量應該是由產地ai運送到消地bj的運輸量表示爲xij 那麼目標函數呢 應該是 大家想最後我們是運輸成本最低 所以他的目標函數應該是什麼型啊 極小型 那麼總的運費怎麼表示呢 任何一條運輸線路上都有可能發生費用 對不對 那麼在這條運輸線路上發生的費用怎麼表示呢 他的單位運價 這條線路的單位運價爲cij 他的運輸量爲xij 那麼這條線路上的 將會發生的運費是cij乘以xij 那麼所有線路上所發生的 運費呢 將是求和 也就是西格瑪對i求和再對z求和 然後將所有的這個cijxij呢 相加得到總運費 那麼他的約束條件應該是怎樣的呢 首先 現在我們呢 主要研究的是簡單的一類問題 因爲產銷平衡問題呢 顯然是比產銷不平衡問題更容易求解的 那麼產銷平衡問題呢 那就必然是他所有的產量都要運輸出去 而所有的需求地的銷量都能夠得到滿足 所以第一類約束應該是 什麼約束 產量約束 也就是所有產地的產量都給運輸出去了 那麼共有多少個產地呢 m個產地 所以i從1到m 所以我們是 有產對產 比如說對於產地a1來說 有產地a1運送到所有銷地的銷量和應該怎樣表示 西格瑪xij應該是對z求和 爲什麼對z求和 是他對應了所有的銷地 這就是產量約束 那麼銷量約束呢 與此相對應 那就是對i求和 讓它最後等於對應的這個銷地的銷量 同時還應該滿足什麼約束 非負約束 是不是 就是我們的運輸量呢 最小爲0 不可能爲負值 接下來我們看運輸問題怎樣進行求解呢 首先我們剛纔講到了運輸問題呢 它仍然是線性規劃問題 所以呢 它是可以用單純刑法來進行求解的 但是呢 在這個過程中我們發現 運輸問題呢 它涉及的變量很多 比如剛纔我們所講的例12 它一共是三個產地四個銷地 共有多少個決策變量呢 三乘是12個對不對 12個決策變量 大家想我們前面課堂上講過的內容中 如果用手工計算 大家可以想見這個工作量已經非常龐大 現實生活中是不是產地和銷地的數量比三合四還會大 那當然計算會更加複雜 第二呢 就是我們想在這個問題中 它的技術係數矩陣呢 是怎樣一個形式啊 我們先把它寫出來 技術係數矩陣呢 只要主要是對於什麼表示 什麼就是x ij的係數對不對 那麼首先看第一個等式的約束就是 sigma x ij z從1到n等於a i 所以它的技術係數矩陣呢 應該是1 全都是1前面 是一共有n個 是第一行 第二行呢 那就是從第n加1這個位置開始 還是一共有n個 接着來就是一共有m個這樣的約束 從n個1來組成 接着再看 下面的n行約束是怎樣表示的 1還是1 只不過這時候變成了對角線上的元素 也就是構成了單位陣 這個單位陣是什麼 m階的單位陣 是不是 好 所以在這呢 對應的還是1 大家想這樣一個矩陣有一個什麼樣的特點 零元素非常多是不是 如果我們將用單純行法去進行求解的過程 必然會有一個結果 就是將現在入這麼多的零元素這個優勢呢 給去掉 轉換爲非零元素 零元素好求解還非零元素好求解 顯然是零元素好求解 所以如果我們按照單純行法一步步去進行迭代呢 將會使得技術係數矩陣呢更加複雜 論題求解呢也更加複雜 那以上兩個原因使得我們不得不考慮 是否還存在更簡單的求解方式 這也是我們這堂課呢主要要講的內容 那麼更簡單的求解方式之一呢 比如說表上作業法 那麼表上作業法呢 它實質還是單純行法 下面呢我們給出來這個表上作業法的基本步驟 基本步驟是第一步確定一個初始可行調運方案 這個呢可以通過最小元素法 西北角法或者福格爾法來完成 大家想我們單純行法在求解過程中 第一步是什麼 第一步是確定一個既可行解 我們再看第二步 檢驗當前可行方案是否最優 常用的方法呢有避諱路法和類似法 用這兩種方法呢計算檢驗數 從而判斷該方案是否最優 我們再回顧一下單純行法中第二步是怎樣 檢驗當前解是否爲最優解 如果是最優解呢則停止計算 那麼檢驗的原則呢是什麼 也是計算檢驗數對不對 判斷它是否最優 第三步呢方案調整 從當前方案出發尋找更優方案 採用避諱路法 那麼在單純行法中呢 第三步也是方案調整 判斷當前解是否爲最優解 如果判斷的準則呢就是 如果當前解是最優解呢則停止 如果呢不是最優解 則要進行進一步的迭代 尋找更優的解 好可以看到呢 這個的步驟與我們單純行法的步驟是一一對應的 好下面我們就講一下如何來求解運輸問題 那麼表上作業法的第一步呢 就是最小元素法確定初始可行調運方案 最小元素法的基本思想是就近儘量滿足供應 我們在這裏啊 其實運輸問題隱含了一個基本假設 就是單位運費 這樣跟他的運輸距離是成正比的 那麼在這種情況下就近儘量滿足供應 也就是說我總是優先選擇單位運價最低的線路來進行供應 這個思想是不是很容易理解 因爲我們總的目標是成本最優 當然就是儘量選擇成本低的線路來進行運輸了 那麼首先看這樣這個例題 就是我們剛纔所講的這個食品廠的這個例題 那麼看在這個問題中 我們如果按照這個最小元素法的思想來進行求解的話 變攬一下這個表格 我們尋找最小元素 最小元素是幾啊 是1對不對 那麼所以我們第一步呢 就是尋找這個最小元素1 那麼最小元素1它對應在哪個格 由產地A2運送到銷地B1 那麼這種情況下 我們應該選擇它的運輸量是多少呢 A2的產量是多少 是B1的銷量是幾啊 3大家想我們應該選擇的運輸量是多少 是3對不對 爲什麼是3啊 因爲如果運輸多了 B1根本銷售不了沒有意義對不對 所以選擇運輸量爲3 那麼選擇3之後 我們想B1的是否所有的銷量都已經被滿足了 對所有的銷量都滿足之後 它還需要的銷量呢 當然就是零了 那麼零這一行 我們是否後面還需要考慮呢 不需要考慮對不對 那麼經過這個線路的運輸之後 A2的產量還剩餘多少 4-3還剩餘1 那麼我們將這個表格呢 進行一下優化 因爲B1的銷量已經得到滿足了 B1所在的這一列 我們就不需要考慮了 將這一列劃去 劃去之後我們再看剩餘的這個表格 最小元數是幾啊 是2 那麼2呢是指由A2運往B3 那麼這個運輸量應該是幾啊 應該是1 爲什麼是1啊 因爲A2只有一個產量可以對外運輸 B3的儘管B3的需求量爲5 但是因爲它只能提供一個單位 所以呢運輸量的應該是1 運輸量是1這種情況下 那麼A2呢所有的產量都被運輸出去 它的剩餘產量呢將是0 B3呢有一個單位的需求量被滿足 還需要有四個單位呢由其他的產地來提供 所以呢它對應的是4 那麼這種情況下哪一個產地或者說銷地不需要考慮呢 A2是不是啊 因爲它所有的產量都運輸出去了 同樣的我們再看剩餘的沒有劃掉的數字格中 最小的元素是幾啊 3對不對 那麼它的運輸量應該是多少呢 運輸量應該是4對不對 7和4做比較 同樣的我們將B3這一列呢就能夠得到滿足 而A1呢剩餘的產量爲3 將B3對應的列劃掉 類似的我們可以呢分別將4 5 類似的我們將整個表格呢都填寫完畢 那麼最後呢我們會劃掉多少條線呢 大家想一共會劃掉多少條線 三行四列我們會劃掉幾條線 七條線對不對 那麼從而呢我們得到了這個初始可行方案 初始可行方案是多少呢 是啊 是就是由A1運往B3呢是四個單位 由A1運往B4呢是幾個單位啊 A1 A2 A3 B1 B2 B3 B4 這時候是4 3 3 1 6 3 將這個我們黑板最左端和我剛剛寫的這個表格呢 對應上我們呢求解一下它的當前的運輸成本是多少 運輸成本呢是86元對不對 這裏有一個情況需要特別加以說明 就是說如果填上一個運量之後 能夠同時劃去兩條線一行和一列 那麼這時候呢就需在劃去的該行或該列上填上一個零 這個零格呢當做有數格來進行對待 爲什麼要這麼做呢 我們簡單想象一下 我們就定性的理解一下 看一下我們這樣一個矩陣 大家想這個矩陣的質是多少 前面是m行後邊是n行 大家想我如果將前面的從第二行開始到第m行 它們都乘以1加到第一行 將後面的n行都乘以-1也加到第一行 那第一行將會變成怎樣 所有的元素都是零 所以說這個矩陣呢 它的質將會是多少 m加n-1 爲什麼不是m加n-1而並非其他的數字呢 大家再回顧一下我們線性代數中所講的質的求法 當前如果說第一行出現零之後 後面的這些行將是非線性相關的 更進一步的證明呢 大家去複習一下線性代數的知識 那麼這種情況下 我們要想使得這個問題有解 它的基變量就應該說有多少個元素裏面 m加n-1個 所以我們可以看到這個表格中有數字格的個數是多少 m加n-1 也就是說爲什麼如果說填上一個韻量之後 同時可以劃去兩條線 一行一列我們要加入一個零的原因 好下面呢 大家再看一下這樣一個練習題 自己嘗試着做一下 我們求一下它的初始解 好這個問題 我們看一下結果 好 我們可以發現呢 初始方案的運費呢 是150元 那除了最小元素法之外呢 求解運輸問題呢 還有其他的解法 課堂上呢 我們也做一下簡單的介紹 比如說西北角法 西北角法呢 它的基本思想呢 就是說呢 每次呢 都考慮我們表格上的西北角的位置 大家想我們地圖上怎麼表示 地圖是上北下南左西右東對不對 所以說它呢 也就是每次都考慮的是左上角的元素 原來以我們剛纔這個歷史二爲例呢 也就是說最優先的考慮哪一個元素啊 它考慮的是左上角有A1B1對應的這個數字格 3它最先考慮的這個元素 滿足了這個元素之後呢 它再考慮 比如說我們看一下 這個3A1B1呢 A1的產量爲7 B1的銷量爲3 那麼這個運輸量應該爲幾啊 3 那麼也就是說B1得到了滿足 A1呢還會剩餘4個單位的產量需要對外運輸 滿足了B1這一列的要求就把B1列劃掉了 把B1列劃掉之後 剩餘的這樣一個運輸表中 它的左上角應該是哪了 西北角應該是A1B2這個位置對不對 A1B2這個位置呢 它的應該運輸量應該是多少 A1還能夠提供的產量是7-3 4個單位 B2的需求量的是多少 6個單位 所以這樣的運輸量應該爲4個單位 類似的呢 依此類推 我們可以發現的最終能夠求解出來 大家可以想象一下 最後這個運輸都在哪個位置上實現 基本都在對角線上對不對 那麼初始方案的運費呢是135元 我們剛纔那個方案的 就是說用最小元數法求解出來的初始解 它的運費是多少 86元 顯然135是大約86的 也就是說呢 西北角法所得出來的初始解是 不如最小元數法得出來的初始解呢 更有效 什麼原因呢 因爲它僅考慮地理位置 而沒有考慮運價 因而呢效果呢不如最小元數法 好 我們接着呢再看第三種方法 福格爾法 福格爾法的基本思想呢是這樣的 求各行各列運價最小於次小之差額 選其中最大的行或列中最小運價 進行供應 大家想這個思想跟我們前面是這樣的 還是有區別 區別體現在哪兒 我們剛纔這個最小元數法只考慮了 最小的那個元數 並沒有考慮 如果說我無法選擇最小的這個元數 就會有一個備選方案 這個備選方案或者說次小的這個格 跟我這個最小的這個元 元數最小的這個格進行對比 它將會帶來的費用增加有多少 從這個定義的描述上 或這個步驟的描述讓我們想 這個方法應該是比最小元數法考慮的問題 更全面 是不是接着再看第二步 如果某一行或某一列 按照這種方法已被供應滿 則劃去該行或該列 在剩下的行列中 重複這種方法 既得最優方案 這個跟我們最小元數法是類似的 對不對 下面我們仍然以歷史二爲例呢 來求解一下這個問題 首先我們看呢 歷史二的這個表格 我們還是這樣已經描述出來了 接着看第一步要求的什麼 每行每列的最小元數約次小元數之差額 我們先看根據行來看 根據行來看 最小元數是三次小元數也是三 所以呢 應該是零 第二行呢 一二之間的差額爲一 第三行呢 四五之間的差額爲一 同樣的我們可以看到 B1對應的列是二 B2對應的列五 B3對應的列一 B4對應的列是三 那麼找出來最小元數與次小元數的差額之後 我們怎樣選取的是哪一個 差額最大的那個優先進行供應 是不是爲什麼差額最大的優先進行供應呢 我們步驟上是這麼給出的 然後在這裏差額最大的是哪一個呢 五對不對 大家看我們優先選擇五對應的這一個列進行供應 那優先選擇誰呢 最小的那個元數也就是是這個元數 A3B2這個格優先進行供應 它的供應量應該爲多少呢 A3的能夠供應的量爲九 B2呢銷量爲六 所以供應的數字格應該是六 然後呢 如果把這個運輸量滿足之後 大家想啊 那麼我們這個B2這一列就已經得到滿足了 是不是我們就要把這一列劃掉 那麼A3這一行呢 它呢有六個單位的產量已經運輸出去 還剩餘三個單位 所以呢 我們將九呢改爲三 那想做完這一步之後 是否對於我們剛纔的這個表有影響 影響在哪呢 主要對於誰有影響 首先B2這一列去掉了 其次呢 A3這一行最小元數與次小元數的差額 是多少 不再是一了 而是二 原來的一呢 是四和五得到的 現在這個二呢 是五和七得到的 那麼對這樣一個表 我們重複同樣的步驟 再看差額最大的是幾呢 三對不對 這個三它對應的是B4這一列 B4這一列的最小元數是幾啊 五 那麼五這個格 我們應該填的運輸量是多少呢 三和六做比較對不對 應該填入三 那麼填入三之後 哪一個行或列被完全滿足了 A3這一行對不對 把它劃掉 把它劃掉之後呢 同時B4這一列呢 還有三個單位的銷量沒有被滿足 所以呢也改爲三 那麼改爲三之後 我們再看這個表 如果我們還用這個福格爾法進一步求解 應該是怎樣呢 是不是對應的下面這些列的數字呢 差額呢我們也要進行重新計算 會發現B1B3列呢沒有變化 但B4這一列呢變更爲二 依此類推 我們接着呢 再按同樣的方法去進行迭代 當然呢每次迭代的時候 如果說像現在呢存在多個二的情況下 你選擇哪一個呢 都是一樣的 最後呢都能夠得到相同的結果 因爲我們還有後面的這個避迴路法呢 來對它進行調整 大家看最後的結果是這樣的 最後的這個結果 大家看填完這個結果 我們算一下它的初始方案的運費是多少 85對不對 這個85跟我們剛纔用最小元數法 以及用西北角法確定的這個運費相比 怎樣要小對不對 這說明什麼福格爾法比最小元數法和西北角法呢 更容易得到最優方案 好這就是用這個表上作業法 第一步呢是要求解一個初始可行方案的幾種方法