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

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

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

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

4、出最小，其數(shù)學(xué)模型如下：1111min 1, 1,0mnijijijnijijmijjiijzc xxaimxbjnx2 2表上作業(yè)法表上作業(yè)法 用表上作業(yè)法求解運(yùn)輸問題時，用表上作業(yè)法求解運(yùn)輸問題時，首先首先給出一個初始方案，給出一個初始方案，其其次次給出一個判別準(zhǔn)則，給出一個判別準(zhǔn)則，然后然后對初始方案進(jìn)行調(diào)整，直到求出最優(yōu)對初始方案進(jìn)行調(diào)整，直到求出最優(yōu)解。解。 由上節(jié)例子來具體說明表上作業(yè)法的步驟，首先列出產(chǎn)銷平由上節(jié)例子來具體說明表上作業(yè)法的步驟，首先列出產(chǎn)銷平衡表和單位運(yùn)價表。衡表和單位運(yùn)價表。一、初始方案的給定初始方案的給定方法很多，這里介紹兩種：初始方案的給定方法很多，這里介紹

5、兩種：1. 最小元素法最小元素法 基本思想是就近供應(yīng)，即從單位運(yùn)價表中最小的運(yùn)基本思想是就近供應(yīng)，即從單位運(yùn)價表中最小的運(yùn)價處開始確定供銷關(guān)系，依次類推，直到求出全部方案價處開始確定供銷關(guān)系，依次類推，直到求出全部方案第一步：第一步：第二步：第二步：第三步：第三步：第四步：第四步：第五步：第五步：第六步：第六步： 這時單位運(yùn)價表中所有元素已經(jīng)都劃掉了，產(chǎn)銷平這時單位運(yùn)價表中所有元素已經(jīng)都劃掉了，產(chǎn)銷平衡表中數(shù)字就是一個調(diào)運(yùn)方案，這個方案的總費用為：衡表中數(shù)字就是一個調(diào)運(yùn)方案，這個方案的總費用為：865310321344613 在選定最小元素后，如果該元素所在行的產(chǎn)量與在選定最小元素后，如果該元

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

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

8、得到的初始方案為例：利用前面最小元素法得到的初始方案為例：計算計算x11的檢驗數(shù)的檢驗數(shù)1) 1(1) 1(2) 1(3) 1(3將上述檢驗數(shù)填入檢驗數(shù)表中：將上述檢驗數(shù)填入檢驗數(shù)表中：計算計算 x31 的檢驗數(shù)的檢驗數(shù)10) 1(5) 1(10) 1(3) 1(2) 1(1) 1(7計算計算 x12 的檢驗數(shù)的檢驗數(shù)以此類推，算出所有檢驗數(shù)：以此類推，算出所有檢驗數(shù)： 如果檢驗數(shù)表中，所有數(shù)字大于等于零，則此時為最如果檢驗數(shù)表中，所有數(shù)字大于等于零，則此時為最優(yōu)解，如果有小于零的，在該格所對應(yīng)的調(diào)運(yùn)方案表中按優(yōu)解，如果有小于零的，在該格所對應(yīng)的調(diào)運(yùn)方案表中按閉回路進(jìn)行調(diào)整。閉回路進(jìn)行調(diào)整。閉

9、回路調(diào)整：閉回路調(diào)整：由此得新的調(diào)運(yùn)方案：由此得新的調(diào)運(yùn)方案： 計算得該方案運(yùn)費為計算得該方案運(yùn)費為85元。元。 需要對該方案每一空格需要對該方案每一空格重新求出檢驗數(shù)，判斷是否最優(yōu)，如果不是最優(yōu)，需繼續(xù)重新求出檢驗數(shù)，判斷是否最優(yōu)，如果不是最優(yōu)，需繼續(xù)調(diào)整，計算后可知該方案為最優(yōu)。調(diào)整，計算后可知該方案為最優(yōu)。注：若減少運(yùn)量的地方有兩個以上相等的最小數(shù)時，注：若減少運(yùn)量的地方有兩個以上相等的最小數(shù)時，會出現(xiàn)多個變會出現(xiàn)多個變0成空格，此時應(yīng)補(bǔ)成空格，此時應(yīng)補(bǔ)0到到(m+n-1)個基變量個基變量調(diào)整得新的調(diào)運(yùn)方案：調(diào)整得新的調(diào)運(yùn)方案：2.位勢法位勢法仍以上例中最小元素法確定的初始調(diào)運(yùn)方案為例。

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

11、掉上表中對應(yīng)數(shù)字，得：該表即檢驗數(shù)表，與閉回路法求出的檢驗數(shù)表相同。該表即檢驗數(shù)表，與閉回路法求出的檢驗數(shù)表相同。 當(dāng)所得檢驗數(shù)不全非負(fù)的時候，仍然需要對方案進(jìn)行當(dāng)所得檢驗數(shù)不全非負(fù)的時候，仍然需要對方案進(jìn)行調(diào)整，調(diào)整方法與前面提到的相同。調(diào)整，調(diào)整方法與前面提到的相同。3. 3. 產(chǎn)銷不平衡的運(yùn)輸產(chǎn)銷不平衡的運(yùn)輸 問題及其應(yīng)用問題及其應(yīng)用 例例2 設(shè)有設(shè)有a1、a2、a3三個產(chǎn)地生產(chǎn)某種物資，其產(chǎn)三個產(chǎn)地生產(chǎn)某種物資，其產(chǎn)量分別為量分別為7t、5t、7t ，b1、b2、b3、b4 四個銷地需要該種四個銷地需要該種物資，銷量分別為物資，銷量分別為2t、3t、4t、6t ，又知各產(chǎn)銷地之間的，又

12、知各產(chǎn)銷地之間的單位運(yùn)價如下表，試決定總運(yùn)費最少的調(diào)運(yùn)方案。單位運(yùn)價如下表，試決定總運(yùn)費最少的調(diào)運(yùn)方案。 解解：產(chǎn)地總產(chǎn)量為：產(chǎn)地總產(chǎn)量為19t ，銷地總銷量為，銷地總銷量為15t ，所以這，所以這是一個產(chǎn)大于銷的運(yùn)輸問題。此時我們假想一個銷地，是一個產(chǎn)大于銷的運(yùn)輸問題。此時我們假想一個銷地，這個銷地的銷量等于前面的總產(chǎn)量與總銷量的差這個銷地的銷量等于前面的總產(chǎn)量與總銷量的差4t ，我，我們也可視其為庫存量，這樣使得產(chǎn)銷達(dá)到平衡。這時對們也可視其為庫存量，這樣使得產(chǎn)銷達(dá)到平衡。這時對它的運(yùn)費為它的運(yùn)費為0，現(xiàn)在我們建立與之對應(yīng)的產(chǎn)銷平衡表和單，現(xiàn)在我們建立與之對應(yīng)的產(chǎn)銷平衡表和單位運(yùn)價表。位運(yùn)

13、價表。單單 位位 運(yùn)運(yùn) 價價 表表產(chǎn)產(chǎn) 銷銷 平平 衡衡 表表利用表上作業(yè)法求解得：利用表上作業(yè)法求解得： 例例3 設(shè)有三個化肥廠供應(yīng)四個地區(qū)的農(nóng)用化肥，假設(shè)有三個化肥廠供應(yīng)四個地區(qū)的農(nóng)用化肥，假定等量的化肥在這些地區(qū)使用效果相同，已知各化肥廠定等量的化肥在這些地區(qū)使用效果相同，已知各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)單位化年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)單位化肥的運(yùn)價表如下，試決定使總的運(yùn)費最節(jié)省的化肥調(diào)撥肥的運(yùn)價表如下，試決定使總的運(yùn)費最節(jié)省的化肥調(diào)撥方案。方案。 解解：這是一個產(chǎn)銷不平衡的運(yùn)輸問題，總產(chǎn)量為：這是一個產(chǎn)銷不平衡的運(yùn)輸問題，總產(chǎn)量為160萬萬t，四個

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

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

16、各地區(qū)每天銷售量為： ， ， ， 。ta71ta42ta93tb31tb62tb53tb64 如果假定如果假定： （1）每個工廠生產(chǎn)的糖果不一定直接發(fā)運(yùn)到銷售點，）每個工廠生產(chǎn)的糖果不一定直接發(fā)運(yùn)到銷售點，可以將其中幾個產(chǎn)地的糖果集中起來一起運(yùn)?？梢詫⑵渲袔讉€產(chǎn)地的糖果集中起來一起運(yùn)。 （2）運(yùn)往各銷地的糖果可以先運(yùn)給其中幾個銷地，）運(yùn)往各銷地的糖果可以先運(yùn)給其中幾個銷地，再轉(zhuǎn)運(yùn)給其他銷地。再轉(zhuǎn)運(yùn)給其他銷地。 （3）除產(chǎn)地、銷地外，中間還可以有幾個轉(zhuǎn)運(yùn)站，）除產(chǎn)地、銷地外，中間還可以有幾個轉(zhuǎn)運(yùn)站，在產(chǎn)地之間、銷地之間或產(chǎn)地與銷地之間轉(zhuǎn)運(yùn)。在產(chǎn)地之間、銷地之間或產(chǎn)地與銷地之間轉(zhuǎn)運(yùn)。 已知各產(chǎn)地、

17、銷地、中間轉(zhuǎn)運(yùn)站之間的單位運(yùn)價，已知各產(chǎn)地、銷地、中間轉(zhuǎn)運(yùn)站之間的單位運(yùn)價，求如何在各地之間進(jìn)行調(diào)運(yùn)，使總的運(yùn)費最小。求如何在各地之間進(jìn)行調(diào)運(yùn)，使總的運(yùn)費最小。產(chǎn)地、銷地、中間轉(zhuǎn)運(yùn)站間運(yùn)價表：產(chǎn)地、銷地、中間轉(zhuǎn)運(yùn)站間運(yùn)價表： 首先通過該表建立單位運(yùn)價表，由于各個地點間糖首先通過該表建立單位運(yùn)價表，由于各個地點間糖果可以相互運(yùn)送，因此都可以作為產(chǎn)地，也都可以作為果可以相互運(yùn)送，因此都可以作為產(chǎn)地，也都可以作為銷地來考慮，將產(chǎn)地和銷地都擴(kuò)大為銷地來考慮，將產(chǎn)地和銷地都擴(kuò)大為11個，不能夠直接個，不能夠直接運(yùn)送到的地點間運(yùn)價設(shè)為運(yùn)送到的地點間運(yùn)價設(shè)為m ，運(yùn)送到本地的運(yùn)價設(shè)為，運(yùn)送到本地的運(yùn)價設(shè)為0。單單 位位 運(yùn)運(yùn) 價價 表表下面考慮如何建立產(chǎn)銷平衡表：下面考慮如何建立產(chǎn)銷平衡表： 1. 中間轉(zhuǎn)運(yùn)站產(chǎn)、銷量的確定中間轉(zhuǎn)運(yùn)站產(chǎn)、銷量的確定 由于中間轉(zhuǎn)運(yùn)站所有的糖果都不保留，所以我們認(rèn)由于中間轉(zhuǎn)運(yùn)站所有的糖果都不保留，所以我們認(rèn)為產(chǎn)量等于銷量，同時因為在運(yùn)費最小時不可能出現(xiàn)一為產(chǎn)量等于銷量，同時因為在運(yùn)費最小時不可能出現(xiàn)一批糖果在兩地見來回倒運(yùn)的現(xiàn)象，并且已知批糖果在兩地見來回倒運(yùn)的現(xiàn)象，并且已