運(yùn)籌學(xué) 第三章 運(yùn)輸問題課件

2022/12/251運(yùn)籌學(xué)

OPERATIONSRESEARCH

2022/12/252第三章運(yùn)輸問題運(yùn)輸問題的數(shù)學(xué)模型表上作業(yè)法產(chǎn)銷不平衡的運(yùn)輸問題及應(yīng)用2022/12/253§1運(yùn)輸問題的典例及數(shù)學(xué)模型

一、引例某公司從三個(gè)產(chǎn)地，，將產(chǎn)品運(yùn)往四個(gè)銷地，

，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最小？2022/12/255目標(biāo)函數(shù)：約束條件：產(chǎn)量約束銷量約束20202022/12/256設(shè)有m個(gè)產(chǎn)地，分別為;n個(gè)銷地，分別是；從產(chǎn)地運(yùn)往銷地的單位運(yùn)價(jià)是，運(yùn)量是產(chǎn)地的產(chǎn)量；是銷地的銷量。

二、一般運(yùn)輸問題數(shù)學(xué)模型則該運(yùn)輸問題的模型如下：2022/12/257說明：當(dāng)時(shí)，稱其為產(chǎn)銷平衡的運(yùn)輸問題，否則產(chǎn)銷不平衡。2022/12/258說明：從上述模型可以看出：（1）這是一個(gè)線性規(guī)劃的模型；（2）變量有m×n個(gè)；（3）約束條件有m+n個(gè)；（4）系數(shù)矩陣非常稀疏；系數(shù)矩陣的秩一般為（m+n-1),而非m+n。若直接用單純形法求解，顯然單純形表比較龐大，于是在單純形法的基礎(chǔ)上創(chuàng)建了表上作業(yè)法求解運(yùn)輸問題這一特殊的線性規(guī)劃問題2022/12/2510表上作業(yè)法一般步驟：1、找出初始基本可行解；2、檢查各非基變量的檢驗(yàn)數(shù)，是否達(dá)到最優(yōu)性條件，若達(dá)到，則得最優(yōu)解；否則轉(zhuǎn)第三步；3、確定出基變量、進(jìn)基變量，用閉回路方法進(jìn)行調(diào)整，得到新的基可行解；4、重復(fù)第二、第三步，直至得到最優(yōu)解。2022/12/2512那么在該例中，應(yīng)有3+4-1=6個(gè)基變量。3113108510294712022/12/2515表中填有數(shù)字的格對應(yīng)于基變量(取值即為格中數(shù)字），而空格對應(yīng)的是非基變量（取值為零）.在求初始基本可行解時(shí)要注意的一個(gè)問題：當(dāng)我們?nèi)《▁ij的值之后，會出現(xiàn)Ai的產(chǎn)量與Bj的銷量都改為零的情況，這時(shí)只能劃去Ai行或Bj列，但不能同時(shí)劃去Ai行與Bj列。（或者在同時(shí)劃去Ai行與Bj列時(shí)，在該行或該列的任意空格處填加一個(gè)0。）這樣可以保證填過數(shù)或零的格為m+n-1個(gè)，即保證基變量的個(gè)數(shù)為m+n-1個(gè)。2022/12/25162.Vogel法

Vogel法的思想是:一地的產(chǎn)品如果不能按照最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)，這就有差額，差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加得越多。因而差額越大處，就應(yīng)當(dāng)采用最小運(yùn)費(fèi)調(diào)運(yùn)。2022/12/25173113102947110852022/12/2518二、最優(yōu)解的判別

判別解的最優(yōu)性需要：計(jì)算檢驗(yàn)數(shù)。方法有兩種閉回路：是在已給出的調(diào)運(yùn)方案的運(yùn)輸表上從一個(gè)代表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)，遇到代表基變量的填入數(shù)字的格可轉(zhuǎn)90度（當(dāng)然也可以不改變方向）繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個(gè)空格，由此形成的封閉折線叫做閉回路。一個(gè)空格存在唯一的閉回路。1.閉回路法因?yàn)槿我夥腔蛄烤杀硎緸榛蛄康奈ㄒ痪€性組合，因此對于任意空格都能夠找到、并且只能找到唯一的一條閉回路。2022/12/2520108531131029471從非基變量出發(fā)，找到一個(gè)閉回路如上表所示?；芈酚兴膫€(gè)頂點(diǎn)，除

外，其余都為基變量。調(diào)整調(diào)運(yùn)量：，運(yùn)費(fèi)增加了3元；，運(yùn)費(fèi)減少3元，運(yùn)費(fèi)增加2元；，運(yùn)費(fèi)減少1元調(diào)整后，總運(yùn)費(fèi)增加：3-3+2-1=1元。說明如果讓為基變量，運(yùn)費(fèi)就會增加，其增加值1作為的檢驗(yàn)數(shù)，2022/12/2521閉回路法計(jì)算檢驗(yàn)數(shù)：就是對于代表非基變量的空格（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為1，由于產(chǎn)銷平衡的要求,必須對這個(gè)空格的閉回路中的各頂點(diǎn)的調(diào)運(yùn)量加上或減少1。最后計(jì)算出由這些變化給整個(gè)運(yùn)輸方案的總運(yùn)輸費(fèi)帶來的變化。以這個(gè)變化的數(shù)值，作為各空格（非基變量）的檢驗(yàn)數(shù)。判別最優(yōu)解準(zhǔn)則：如果所有代表非基變量的空格的檢驗(yàn)數(shù)都大于等于零，則已求得最優(yōu)解；否則繼續(xù)改進(jìn)找出最優(yōu)解。3113108510294711085311310294712022/12/2524

我們先給u1賦個(gè)任意數(shù)值，不妨設(shè)u1=0，則從基變量x11的檢驗(yàn)數(shù)求得v3=c13-u1=3-0=3。同理可以求得v4=10，u2=-1，等等見上表。檢驗(yàn)數(shù)的求法，即用公式，如。3113108510294712022/12/2526三、改進(jìn)運(yùn)輸方案的辦法——閉回路調(diào)整法當(dāng)表中的某個(gè)檢驗(yàn)數(shù)小于零時(shí)，方案不為最優(yōu)，需要調(diào)整。方法是：選取所有負(fù)檢驗(yàn)數(shù)中最小的非基變量作為入基變量，以求盡快實(shí)現(xiàn)最優(yōu)。（1）確定調(diào)整量：例：取，表明增加一個(gè)單位的運(yùn)輸量，可使得總運(yùn)費(fèi)減少1。在以為出發(fā)點(diǎn)的閉回路中，找出所有偶數(shù)頂點(diǎn)的調(diào)運(yùn)量：，則調(diào)整量（2）調(diào)整方法：把所有閉回路上為偶數(shù)頂點(diǎn)的運(yùn)輸量都減少這個(gè)值，奇數(shù)頂點(diǎn)的運(yùn)輸量都增加這個(gè)值(見下表)。2022/12/2527311310851029471311310851029471調(diào)整運(yùn)量后的新方案：2022/12/2530表上作業(yè)法的一般步驟：1、用最小元素法或Vogel法確定初始基可行解；2、判斷是否為最優(yōu)：用閉回路法或位勢法計(jì)算空格檢驗(yàn)數(shù)，若所有檢驗(yàn)數(shù)均非負(fù)，則已得到最優(yōu)解；否則進(jìn)入第三步；3、從所有負(fù)檢驗(yàn)數(shù)中選擇最小者對應(yīng)空格作為進(jìn)基變量，從此點(diǎn)出發(fā)作閉回路，確定調(diào)整量，奇點(diǎn)處增加，偶點(diǎn)處減少。2022/12/2531例：用表上作業(yè)法，求解下面的運(yùn)輸問題：解:用最小元素法確定初始基可行解，如下表所示：2022/12/2532++--2022/12/2533++--2022/12/2534此時(shí)所有非基變量的檢驗(yàn)數(shù)均非負(fù)，故已達(dá)最優(yōu)解。2022/12/2535一、產(chǎn)銷不平衡的運(yùn)輸問題例1：某公司從兩個(gè)產(chǎn)地，，將產(chǎn)品運(yùn)往三個(gè)銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最??？§3

產(chǎn)銷不平衡的運(yùn)輸問題及應(yīng)用

例1：某公司從兩個(gè)產(chǎn)地，，將產(chǎn)品運(yùn)往三個(gè)銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最小？例1：某公司從兩個(gè)產(chǎn)地，，將產(chǎn)品運(yùn)往三個(gè)銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最小？例1：某公司從兩個(gè)產(chǎn)地，，將產(chǎn)品運(yùn)往三個(gè)銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最??？例1：某公司從兩個(gè)產(chǎn)地，，將產(chǎn)品運(yùn)往三個(gè)銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最??？例1：某公司從兩個(gè)產(chǎn)地，，將產(chǎn)品運(yùn)往三個(gè)銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最小？例1：某公司從兩個(gè)產(chǎn)地，，將產(chǎn)品運(yùn)往三個(gè)銷地，，，各產(chǎn)地的產(chǎn)量，各銷地的銷量，及各產(chǎn)地往各銷地的運(yùn)費(fèi)單價(jià)如表所示。應(yīng)如何調(diào)運(yùn)可使運(yùn)費(fèi)最小？2022/12/2536易知這個(gè)問題中：總產(chǎn)量＜總銷量，即這時(shí)可考慮增加一個(gè)假想產(chǎn)地，其產(chǎn)量是（總銷量－總產(chǎn)量＝150)他到各銷地的單位運(yùn)費(fèi)是０．于是得到如下的表格：2022/12/2537例2：某單位有三個(gè)區(qū)，一區(qū)、二區(qū)、三區(qū)；每年需要生活用煤和取暖用煤各3000噸，1000噸，2000噸；由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，兩地價(jià)格和煤質(zhì)相同，兩煤礦的供應(yīng)能力分別是1500噸，和4000噸。由煤礦至該單位三個(gè)區(qū)的單位運(yùn)價(jià)如表所示。由于供應(yīng)能力限制，經(jīng)研究決定，一區(qū)供應(yīng)量可減少0~300噸，二區(qū)全部滿足，三區(qū)不能少于1500噸，試求使得運(yùn)費(fèi)最小的運(yùn)輸方案？2022/12/2538根據(jù)題意，添加虛擬產(chǎn)地后，可作出產(chǎn)銷平衡的運(yùn)價(jià)表：2022/12/2539例３：設(shè)有三個(gè)化肥廠供應(yīng)四個(gè)地區(qū)的化肥，假設(shè)等量的化肥在這個(gè)地區(qū)的使用效果相同。各廠的產(chǎn)量、各地區(qū)的需要量、單位運(yùn)價(jià)如表所示。求出運(yùn)費(fèi)最省的調(diào)撥方案。2022/12/2540解：無論考慮需求的上限還是下限，這都是一個(gè)產(chǎn)銷不平衡的問題。當(dāng)考慮下限時(shí)，產(chǎn)〉銷；當(dāng)考慮需求上限時(shí)，產(chǎn)〈銷。于是可以考慮在滿足最低需求的情況下，兼顧最高需求。即將每個(gè)地區(qū)的需求分為最低需求和（最高-最低）需求，最低部分必須滿足，高出的部分可滿足也可不滿足。雖然銷地Ⅳ的需求無上限，但根據(jù)生產(chǎn)能力，最多可以給她分配60萬噸。另外若將最高需求考慮進(jìn)來，則需添加虛擬產(chǎn)地D，其產(chǎn)量應(yīng)為

50萬噸。于是可給出如下的產(chǎn)銷平衡及運(yùn)價(jià)表。2022/12/25412022/12/2542二、生產(chǎn)與存儲問題例4：某廠按照合同規(guī)定須于當(dāng)年每季度末分別提供10，15，25，20臺同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如表所示。又如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺每積壓一個(gè)季度，存儲維護(hù)費(fèi)用0.15萬元。要求在完成合同的情況下，使得全年生產(chǎn)（存儲）費(fèi)用最小的決策。2022/12/2543注意：單位運(yùn)價(jià)如何確定故設(shè)：表示第季度生產(chǎn)，用于第季度交貨的產(chǎn)品數(shù)量?？山?shù)學(xué)模型。2022/12/2544三、轉(zhuǎn)運(yùn)問題以本章引例為例，產(chǎn)品從3個(gè)產(chǎn)地運(yùn)往4個(gè)銷地?，F(xiàn)考慮;1、各產(chǎn)地的產(chǎn)品不一定直接運(yùn)往銷地，可以將產(chǎn)品集中后再一起運(yùn)；2、運(yùn)往個(gè)銷地的產(chǎn)品也可先運(yùn)給其中幾個(gè)，再轉(zhuǎn)運(yùn)給其他銷地；3、除產(chǎn)、銷地外還可以有幾個(gè)中間轉(zhuǎn)運(yùn)站，在產(chǎn)地之間、銷地之間、或產(chǎn)地與銷地之間進(jìn)行轉(zhuǎn)運(yùn)；已知單位運(yùn)價(jià)表如下，問在考慮產(chǎn)銷地之間直接運(yùn)輸和非直接運(yùn)輸?shù)母鞣N可能方案下，如何安排運(yùn)輸方案，可使總運(yùn)費(fèi)最??？2022