第4章-運輸問題和指派問題.ppt

《第4章-運輸問題和指派問題.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、第4章運輸問題和指派問題TheTransportationandAssignmentProblems本章內容要點運輸問題的基本概念運輸問題的各種變形運輸問題的建模求解與應用指派問題的基本概念指派問題的各種變形指派問題的建模求解與應用本章內容4.1運輸問題的基本概念4.2運輸問題的數(shù)學模型和電子表格模型4.3表上作業(yè)法(補充)4.4運輸問題的變形4.5運輸問題的應用舉例4.6指派問題的基本概念4.7匈牙利法(補充)4.8指派問題的變形4.9指派問題的應用舉例本章主要內容框架圖4.1運輸問題的基本概念運輸問題最初起源于在日常生活

2、中人們把某些物品或人們自身從一些地方轉移到另一些地方，要求所采用的運輸路線或運輸方案是最經(jīng)濟或成本最低的，這就成為了一個運籌學問題。隨著經(jīng)濟的不斷發(fā)展，現(xiàn)代物流業(yè)的蓬勃發(fā)展，如何充分利用時間、信息、倉儲、配送和聯(lián)運體系創(chuàng)造更多的價值，向運籌學提出了更高的挑戰(zhàn)。要求科學地組織貨源、運輸和配送，使得運輸問題變得日益復雜，但是其基本思想仍然是實現(xiàn)現(xiàn)有資源的最優(yōu)化配置。4.1運輸問題的基本概念一般的運輸問題就是解決如何把某種產(chǎn)品從若干個產(chǎn)地調運到若干個銷地，在每個產(chǎn)地的供應量和每個銷地的需求量以及各地之間的運輸單價已知的前提下，確定

3、一個使得總運輸成本最小的方案。平衡運輸問題的條件如下：（1）明確出發(fā)地（產(chǎn)地）、目的地（銷地）、供應量（產(chǎn)量）、需求量（銷量）和單位運輸成本。（2）需求假設：每一個出發(fā)地（產(chǎn)地）都有一個固定的供應量，所有的供應量都必須配送到目的地（銷地）。與之類似，每一個目的地（銷地）都有一個固定的需求量，整個需求量都必須由出發(fā)（產(chǎn)地）地滿足。即“總供應量＝總需求量”。（3）成本假設：從任何一個出發(fā)地（產(chǎn)地）到任何一個目的地（銷地）的貨物運輸成本與所運送的貨物數(shù)量成線性比例關系，因此，貨物運輸成本就等于單位運輸成本乘以所運送的貨物數(shù)量（目標

4、函數(shù)是線性的）。4.1運輸問題的基本概念典型背景——單一物資運輸調度問題設某種物品有:m個產(chǎn)地：產(chǎn)量：n個銷地：銷量：從產(chǎn)地到銷地的單位運價是。求總運費最小的調度方案。4.1運輸問題的基本概念產(chǎn)銷平衡運輸問題的數(shù)學模型：設從產(chǎn)地Ai運往銷地bj的物資數(shù)量為xij（i=1,2,?,m;j=1,2,?,n)Note1:平衡運輸問題有m?n個變量，m+n個約束條件，規(guī)模很大。x11x12?x1nx21x22?x2nxm1xm2?xmn運輸問題決策變量表示由到的物品數(shù)量。銷地產(chǎn)地銷量產(chǎn)量Note2:4.1運輸問題的基本概念例4.1某

5、公司有三個加工廠（A1、A2和A3）生產(chǎn)某種產(chǎn)品，每日的產(chǎn)量分別為：7噸、4噸、9噸；該公司把這些產(chǎn)品分別運往四個銷售點（B1、B2、B3和B4），各銷售點每日的銷量分別為：3噸、6噸、5噸、6噸；從三個加工廠（產(chǎn)地）到四個銷售點（銷地）的單位產(chǎn)品運價如表4-2所示。問該公司應如何調運產(chǎn)品，才能在滿足四個銷售點的需求量的前提下，使總運費最少？表4-2三個加工廠到四個銷售點的單位產(chǎn)品運價（千元/噸）銷售點B1銷售點B2銷售點B3銷售點B4加工廠A1311310加工廠A21928加工廠A3741054.2運輸問題的數(shù)學模型和電子

6、表格模型解：首先，三個加工廠A1、A2、A3的總產(chǎn)量為7＋4＋9＝20（噸）；四個銷售點B1、B2、B3、B4的總銷量為3＋6＋5＋6＝20（噸）。也就是說，總產(chǎn)量等于總銷量，故該運輸問題是一個產(chǎn)銷平衡的運輸問題。（1）決策變量設xij為從加工廠Ai（i＝1,2,3）運往銷售點Bj（j=1,2,3,4）的運輸量（噸）。（2）目標函數(shù)本問題的目標是使公司的總運費最少4.2運輸問題的數(shù)學模型和電子表格模型（3）約束條件①三個加工廠的產(chǎn)品都要全部運送出去（產(chǎn)量約束）②四個銷售點的產(chǎn)品都要全部得到滿足（銷量約束）③非負4.2運輸問題

7、的數(shù)學模型和電子表格模型運輸問題是一種特殊的線性規(guī)劃問題，一般采用“表上作業(yè)法”求解運輸問題，但Excel的“規(guī)劃求解”還是采用“單純形法”來求解。例4.1的電子表格模型（1）設置“條件格式”的操作請參見本章附錄Ⅱ（P142）（2）將單元格的字體和背景顏色設置為相同顏色以實現(xiàn)“渾然一體”的效果，這樣可以起到隱藏單元格內容的作用。當單元格被選中時，編輯欄中仍然會顯示單元格的真實數(shù)據(jù)。（3）本章所有例題的最優(yōu)解（運輸方案或指派方案）有一個共同特點：“0”值較多，所以都使用了Excel的“條件格式”功能。4.2運輸問題的數(shù)學模型和

8、電子表格模型需要注意的是，運輸問題有這樣一個性質（整數(shù)解性質），即只要它的供應量和需求量都是整數(shù)，任何有可行解的運輸問題就必然有所有決策變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有變量都是整數(shù)的約束條件。由于運輸量經(jīng)常以卡車、集裝箱等為單位，如果卡車不能裝滿，就很不經(jīng)濟了。整數(shù)解性質避免了