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

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

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

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

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

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

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

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

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

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

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

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

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

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

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