運籌學(xué)基礎(chǔ)及應(yīng)用第五版-胡運權(quán)第三章

1、§1．運輸問題的典例和數(shù)學(xué)模型,§ 2．表上作業(yè)法,§ 3．產(chǎn)銷不平衡的運輸問題及其應(yīng)用,第三章 運輸問題,§1．運輸問題的典例和數(shù)學(xué)模型,例1 某食品公司經(jīng)銷主要產(chǎn)品之一是糖果，它下面設(shè)有三個加工廠，每天的糖果生產(chǎn)量分別為： ， ， 。該公司把這些糖果分別運往四個地區(qū)的門市部銷售，各地區(qū)每天的銷售量： ，

2、 ， ， 。已知從每個加工廠到各銷售門市部每噸糖果的運價如下表：,單位：元/t,現(xiàn)在把問題概括一下，在線性規(guī)劃中我們研究這樣一類運輸問題：有某種物資需要調(diào)運，這種物資的計量單位可以是重量、包裝單位或其他。已知有m個地點可以供應(yīng)該種物資（以后通稱產(chǎn)地，用 表示），有n個地點需要該種物資（以后通稱銷地，用表示），又知這m個產(chǎn)地的可供量（以后通稱

3、產(chǎn)量）為 （可通寫為 ），n個銷地的需要量（以后通稱銷量）分別為 （通寫為 ）,從第i個產(chǎn)地到第j個銷地的單位物資運價為 。,產(chǎn)銷平衡表,單位運價表,如果用 xij 代表從第 i 個產(chǎn)地調(diào)運給第 j 個銷地的物資的單位數(shù)量，那么在產(chǎn)銷平衡的條件下，使總運費支出最小，其數(shù)學(xué)模型如下：,§2．表上作業(yè)法,用表上作業(yè)法

4、求解運輸問題時，首先給出一個初始方案，其次給出一個判別準(zhǔn)則，然后對初始方案進行調(diào)整，直到求出最優(yōu)解。,由上節(jié)例子來具體說明表上作業(yè)法的步驟，首先列出產(chǎn)銷平衡表和單位運價表。,一、初始方案的給定,初始方案的給定方法很多，這里介紹兩種：,1. 最小元素法,基本思想是就近供應(yīng)，即從單位運價表中最小的運價處開始確定供銷關(guān)系，依次類推，直到求出全部方案,第一步：,第二步：,第三步：,第四步：,第五步：,第六步：,這時單位運價表中所有元素已經(jīng)都劃

5、掉了，產(chǎn)銷平衡表中數(shù)字就是一個調(diào)運方案，這個方案的總費用為：,在選定最小元素后，如果該元素所在行的產(chǎn)量與所在列的銷量相同，這時須同時劃掉一行一列，并在該行或列上最小元素對應(yīng)位置之外添加一個0。 即下述例題表格中紅色的零，需要選擇且僅選擇一個保留。,2. Vogel 法,用最小元素法給定初始方案只從局部觀點考慮就近供應(yīng)，可能造成總體的不合理。,2. Vogel 法,Vogel 法的步驟：從運價表上分別找出每行與每列的最小的兩個元素之差；

6、從差值最大的行或列中找到最小運價確定供需關(guān)系和供應(yīng)數(shù)量；當(dāng)產(chǎn)地或銷地中有一方數(shù)量上供應(yīng)完畢或得到滿足時，劃去運價表中對應(yīng)的行或列；重復(fù)步驟1、2、3，直到劃去所有元素為止。,二、最優(yōu)性檢驗與方案的調(diào)整,1.閉回路法,閉回路是指調(diào)運方案中由一個空格，和有數(shù)字的格，用水平和豎直連線包圍成的封閉回路。,利用前面最小元素法得到的初始方案為例：,計算x11的檢驗數(shù),將上述檢驗數(shù)填入檢驗數(shù)表中：,計算 x31 的檢驗數(shù),計算 x12 的檢驗數(shù)

7、,以此類推，算出所有檢驗數(shù)：,如果檢驗數(shù)表中，所有數(shù)字大于等于零，則此時為最優(yōu)解，如果有小于零的，在該格所對應(yīng)的調(diào)運方案表中按閉回路進行調(diào)整。,閉回路調(diào)整：,由此得新的調(diào)運方案：,計算得該方案運費為85元。 需要對該方案每一空格重新求出檢驗數(shù)，判斷是否最優(yōu)，如果不是最優(yōu)，需繼續(xù)調(diào)整，計算后可知該方案為最優(yōu)。,注：若減少運量的地方有兩個以上相等的最小數(shù)時，會出現(xiàn)多個變0成空格，此時應(yīng)補0到(m+n-1)個基變量,調(diào)整得新的調(diào)運方案：,2

8、.位勢法,仍以上例中最小元素法確定的初始調(diào)運方案為例。,第一步：將調(diào)運方案中有數(shù)字的格內(nèi)數(shù)字改換為單位運價表中對應(yīng)格的運價。即由下述兩表：,得：,第二步：在表格下方和右方增加一行和一列，并填上一些數(shù)字，使得格中數(shù)字正好等于它所在行與所在列數(shù)字之和。,依次計算填入各數(shù)：,最終得：,將 vi 與 uj 相加求出空格處數(shù)字：,用單位運價表中數(shù)字減掉上表中對應(yīng)數(shù)字，得：,該表即檢驗數(shù)表，與閉回路法求出的檢驗數(shù)表相同。,當(dāng)所得檢驗數(shù)不全非負(fù)的時候

9、，仍然需要對方案進行調(diào)整，調(diào)整方法與前面提到的相同。,§3. 產(chǎn)銷不平衡的運輸 問題及其應(yīng)用,例2 設(shè)有A1、A2、A3三個產(chǎn)地生產(chǎn)某種物資，其產(chǎn)量分別為7t、5t、7t ，B1、B2、B3、B4 四個銷地需要該種物資，銷量分別為2t、3t、4t、6t ，又知各產(chǎn)銷地之間的單位運價如下表，試決定總運費最少的調(diào)運方案。,解：產(chǎn)地總產(chǎn)量為19t ，銷地總銷量為15t ，所以這是一個產(chǎn)大于銷的運輸問題。此時我們假想一個銷地，這個

10、銷地的銷量等于前面的總產(chǎn)量與總銷量的差4t ，我們也可視其為庫存量，這樣使得產(chǎn)銷達(dá)到平衡。這時對它的運費為0，現(xiàn)在我們建立與之對應(yīng)的產(chǎn)銷平衡表和單位運價表。,單 位 運 價 表,產(chǎn) 銷 平 衡 表,利用表上作業(yè)法求解得：,例3 設(shè)有三個化肥廠供應(yīng)四個地區(qū)的農(nóng)用化肥，假定等量的化肥在這些地區(qū)使用效果相同，已知各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)單位化肥的運價表如下，試決定使總的運費最節(jié)省的化肥調(diào)撥方案。,解：這是一個產(chǎn)銷不

11、平衡的運輸問題，總產(chǎn)量為160萬t，四個地區(qū)最低需求為110萬t ，最高需求為無限。當(dāng)其它地區(qū)都是滿足最低需求時，第Ⅳ地區(qū)每年最多能分配到60萬t ，這樣最高需求就是210萬t，大于產(chǎn)量。,產(chǎn) 銷 平 衡 表,為建立產(chǎn)銷平衡表，在表中增加一假想化肥廠D ，其年產(chǎn)量為50萬t 。并把各地區(qū)的最低需求和額外需求區(qū)分開來，建立產(chǎn)銷平衡表。,當(dāng)一個產(chǎn)地的產(chǎn)量不能運往某一個銷地的時候，認(rèn)為運價為M(表示任意大正數(shù))。額外需求部分的銷量，由

12、于是否滿足都可以，所以假想廠運往這些銷地的運價定為0。,單 位 運 價 表,利用表上作業(yè)法求解得：,例4 某食品公司經(jīng)銷主要產(chǎn)品之一是糖果，它下面設(shè)有三個加工廠，每天的糖果生產(chǎn)量分別為： ， ， 。該公司把這些糖果分別運往四個地區(qū)的門市部銷售，各地區(qū)每天銷售量為： ， ， ， 。,如果假定

13、： （1）每個工廠生產(chǎn)的糖果不一定直接發(fā)運到銷售點，可以將其中幾個產(chǎn)地的糖果集中起來一起運。,（2）運往各銷地的糖果可以先運給其中幾個銷地，再轉(zhuǎn)運給其他銷地。,（3）除產(chǎn)地、銷地外，中間還可以有幾個轉(zhuǎn)運站，在產(chǎn)地之間、銷地之間或產(chǎn)地與銷地之間轉(zhuǎn)運。,已知各產(chǎn)地、銷地、中間轉(zhuǎn)運站之間的單位運價，求如何在各地之間進行調(diào)運，使總的運費最小。,產(chǎn)地、銷地、中間轉(zhuǎn)運站間運價表：,首先通過該表建立單位運價表，由于各個地點間糖果可以相互

14、運送，因此都可以作為產(chǎn)地，也都可以作為銷地來考慮，將產(chǎn)地和銷地都擴大為11個，不能夠直接運送到的地點間運價設(shè)為M ，運送到本地的運價設(shè)為0。,單 位 運 價 表,下面考慮如何建立產(chǎn)銷平衡表：,1. 中間轉(zhuǎn)運站產(chǎn)、銷量的確定,由于中間轉(zhuǎn)運站所有的糖果都不保留，所以我們認(rèn)為產(chǎn)量等于銷量，同時因為在運費最小時不可能出現(xiàn)一批糖果在兩地見來回倒運的現(xiàn)象，并且已知 總產(chǎn)量