運(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è)有三個(gè)加工廠，每天的糖果生產(chǎn)量分別為：設(shè)有三個(gè)加工廠，每天的糖果生產(chǎn)量分別為： ， ， 。該公司把這些糖果分別運(yùn)往四個(gè)地區(qū)。該公司把這些糖果分別運(yùn)往四個(gè)地區(qū)的門市部銷售，各地區(qū)每天的銷售量：的門市部銷售，各地區(qū)每天的銷售量： ， ， ， 。已知從每個(gè)加工廠到各銷售門市部每。已知從每

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

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

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

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

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

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

8、得到的初始方案為例：利用前面最小元素法得到的初始方案為例：計(jì)算計(jì)算x11的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)1) 1(1) 1(2) 1(3) 1(3將上述檢驗(yàn)數(shù)填入檢驗(yàn)數(shù)表中：將上述檢驗(yàn)數(shù)填入檢驗(yàn)數(shù)表中：計(jì)算計(jì)算 x31 的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)10) 1(5) 1(10) 1(3) 1(2) 1(1) 1(7計(jì)算計(jì)算 x12 的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)以此類推，算出所有檢驗(yàn)數(shù)：以此類推，算出所有檢驗(yàn)數(shù)： 如果檢驗(yàn)數(shù)表中，所有數(shù)字大于等于零，則此時(shí)為最如果檢驗(yàn)數(shù)表中，所有數(shù)字大于等于零，則此時(shí)為最優(yōu)解，如果有小于零的，在該格所對(duì)應(yīng)的調(diào)運(yùn)方案表中按優(yōu)解，如果有小于零的，在該格所對(duì)應(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)方案： 計(jì)算得該方案運(yùn)費(fèi)為計(jì)算得該方案運(yùn)費(fèi)為85元。元。 需要對(duì)該方案每一空格需要對(duì)該方案每一空格重新求出檢驗(yàn)數(shù)，判斷是否最優(yōu)，如果不是最優(yōu)，需繼續(xù)重新求出檢驗(yàn)數(shù)，判斷是否最優(yōu)，如果不是最優(yōu)，需繼續(xù)調(diào)整，計(jì)算后可知該方案為最優(yōu)。調(diào)整，計(jì)算后可知該方案為最優(yōu)。注：若減少運(yùn)量的地方有兩個(gè)以上相等的最小數(shù)時(shí)，注：若減少運(yùn)量的地方有兩個(gè)以上相等的最小數(shù)時(shí)，會(huì)出現(xiàn)多個(gè)變會(huì)出現(xiàn)多個(gè)變0成空格，此時(shí)應(yīng)補(bǔ)成空格，此時(shí)應(yīng)補(bǔ)0到到(m+n-1)個(gè)基變量個(gè)基變量調(diào)整得新的調(diào)運(yùn)方案：調(diào)整得新的調(diào)運(yùn)方案：2.位勢(shì)法位勢(shì)法仍以上例中最小元素法確定的初始調(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)價(jià)表中對(duì)應(yīng)格的運(yùn)價(jià)。即由下述兩換為單位運(yùn)價(jià)表中對(duì)應(yīng)格的運(yùn)價(jià)。即由下述兩表：表：得：得： 第二步第二步：在表格下方和右方增加一行和一列，并填：在表格下方和右方增加一行和一列，并填上一些數(shù)字，使得格中數(shù)字正好等于它所在行與所在列數(shù)上一些數(shù)字，使得格中數(shù)字正好等于它所在行與所在列數(shù)字之和。字之和。依次計(jì)算填入各數(shù)：依次計(jì)算填入各數(shù)：最終得：最終得：將將 vi 與與 uj 相加求出空格處數(shù)字：相加求出空格處數(shù)字：用單位運(yùn)價(jià)表中數(shù)字減掉上表中對(duì)應(yīng)數(shù)字，得：用單位運(yùn)價(jià)表中數(shù)字減

11、掉上表中對(duì)應(yīng)數(shù)字，得：該表即檢驗(yàn)數(shù)表，與閉回路法求出的檢驗(yàn)數(shù)表相同。該表即檢驗(yàn)數(shù)表，與閉回路法求出的檢驗(yàn)數(shù)表相同。 當(dāng)所得檢驗(yàn)數(shù)不全非負(fù)的時(shí)候，仍然需要對(duì)方案進(jìn)行當(dāng)所得檢驗(yàn)數(shù)不全非負(fù)的時(shí)候，仍然需要對(duì)方案進(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三個(gè)產(chǎn)地生產(chǎn)某種物資，其產(chǎn)三個(gè)產(chǎn)地生產(chǎn)某種物資，其產(chǎn)量分別為量分別為7t、5t、7t ，b1、b2、b3、b4 四個(gè)銷地需要該種四個(gè)銷地需要該種物資，銷量分別為物資，銷量分別為2t、3t、4t、6t ，又知各產(chǎn)銷地之間的，又

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

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

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

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

16、各地區(qū)每天銷售量為： ， ， ， 。ta71ta42ta93tb31tb62tb53tb64 如果假定如果假定： （1）每個(gè)工廠生產(chǎn)的糖果不一定直接發(fā)運(yùn)到銷售點(diǎn)，）每個(gè)工廠生產(chǎn)的糖果不一定直接發(fā)運(yùn)到銷售點(diǎn)，可以將其中幾個(gè)產(chǎn)地的糖果集中起來一起運(yùn)?？梢詫⑵渲袔讉€(gè)產(chǎn)地的糖果集中起來一起運(yùn)。 （2）運(yùn)往各銷地的糖果可以先運(yùn)給其中幾個(gè)銷地，）運(yùn)往各銷地的糖果可以先運(yùn)給其中幾個(gè)銷地，再轉(zhuǎn)運(yùn)給其他銷地。再轉(zhuǎn)運(yùn)給其他銷地。 （3）除產(chǎn)地、銷地外，中間還可以有幾個(gè)轉(zhuǎn)運(yùn)站，）除產(chǎn)地、銷地外，中間還可以有幾個(gè)轉(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)價(jià)，已知各產(chǎn)地、銷地、中間轉(zhuǎn)運(yùn)站之間的單位運(yùn)價(jià)，求如何在各地之間進(jìn)行調(diào)運(yùn)，使總的運(yùn)費(fèi)最小。求如何在各地之間進(jìn)行調(diào)運(yùn)，使總的運(yùn)費(fèi)最小。產(chǎn)地、銷地、中間轉(zhuǎn)運(yùn)站間運(yùn)價(jià)表：產(chǎn)地、銷地、中間轉(zhuǎn)運(yùn)站間運(yùn)價(jià)表： 首先通過該表建立單位運(yùn)價(jià)表，由于各個(gè)地點(diǎn)間糖首先通過該表建立單位運(yùn)價(jià)表，由于各個(gè)地點(diǎn)間糖果可以相互運(yùn)送，因此都可以作為產(chǎn)地，也都可以作為果可以相互運(yùn)送，因此都可以作為產(chǎn)地，也都可以作為銷地來考慮，將產(chǎn)地和銷地都擴(kuò)大為銷地來考慮，將產(chǎn)地和銷地都擴(kuò)大為11個(gè)，不能夠直接個(gè)，不能夠直接運(yùn)送到的地點(diǎn)間運(yùn)價(jià)設(shè)為運(yùn)送到的地點(diǎn)間運(yùn)價(jià)設(shè)為m ，運(yùn)送到本地的運(yùn)價(jià)設(shè)為，運(yùn)送到本地的運(yùn)價(jià)設(shè)為0。單單 位位 運(yùn)運(yùn) 價(jià)價(jià) 表表下面考慮如何建立產(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)量等于銷量，同時(shí)因?yàn)樵谶\(yùn)費(fèi)最小時(shí)不可能出現(xiàn)一為產(chǎn)量等于銷量，同時(shí)因?yàn)樵谶\(yùn)費(fèi)最小時(shí)不可能出現(xiàn)一批糖果在兩地見來回倒運(yùn)的現(xiàn)象，并且已知批糖果在兩地見來回倒運(yùn)的現(xiàn)象，并且已