第七章運(yùn)輸問(wèn)題

第七章運(yùn)輸問(wèn)題一、運(yùn)輸問(wèn)題模型及其求解思路二、幾種特殊情況三、運(yùn)輸問(wèn)題的應(yīng)用一、運(yùn)輸問(wèn)題模型及其求解思路1、問(wèn)題的提出：某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷(xiāo)地B1、B2、B3。各產(chǎn)地的產(chǎn)量、各銷(xiāo)地的銷(xiāo)量和各產(chǎn)地運(yùn)往各銷(xiāo)地每件物品的運(yùn)費(fèi)如下表所示。問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？一、運(yùn)輸問(wèn)題模型及其求解思路B1B2B3產(chǎn)量A1646200A2655300銷(xiāo)量150150200運(yùn)價(jià)表銷(xiāo)量和＝產(chǎn)量和產(chǎn)銷(xiāo)平衡一、運(yùn)輸問(wèn)題模型及其求解思路B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷(xiāo)量150150200為建立模型，設(shè)xij為從產(chǎn)地Ai運(yùn)往銷(xiāo)地Bj的運(yùn)輸量，得到下表：運(yùn)量表一、運(yùn)輸問(wèn)題模型及其求解思路據(jù)題意，可建立線性規(guī)劃模型：Minf=6x11+4x12+6x13+6x21+5x22+5x23s.t.x11+x12+x13=200

x21+x22+x23=300

x11+x21=150

x12+x22=150

x13+x23=200xij≥0(i=1,2；j=1,2,3）一、運(yùn)輸問(wèn)題模型及其求解思路2、產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題模型的特點(diǎn)從模型的建立可知：列數(shù)為2（產(chǎn)地?cái)?shù)）×3（銷(xiāo)地?cái)?shù)）＝6；行數(shù)為2（產(chǎn)地?cái)?shù)）+3（銷(xiāo)地?cái)?shù)）＝5；再觀察模型的系數(shù)矩陣：一、運(yùn)輸問(wèn)題模型及其求解思路111000200

000111300100100150

010010150

001001200前2行之和＝后3行之和一、運(yùn)輸問(wèn)題模型及其求解思路對(duì)于產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題，若產(chǎn)地為m個(gè)，銷(xiāo)地為n個(gè)，則變量個(gè)數(shù)為m×n個(gè)，線性無(wú)關(guān)的約束條件個(gè)數(shù)為m+n-1，故基本解中的基變量個(gè)數(shù)為m+n-1。一、運(yùn)輸問(wèn)題模型及其求解思路3、運(yùn)輸問(wèn)題求解思路——表上作業(yè)法由于運(yùn)輸規(guī)劃系數(shù)矩陣的特殊性，如果直接使用線性規(guī)劃單純形法求解計(jì)算，則無(wú)法利用這些有利條件。人們?cè)诜治鲞\(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對(duì)運(yùn)輸問(wèn)題的表上作業(yè)法。（表上作業(yè)法略）運(yùn)輸問(wèn)題的應(yīng)用1、產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題例：某公司從兩個(gè)產(chǎn)地A1、A2將物品運(yùn)往三個(gè)銷(xiāo)地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷(xiāo)地的銷(xiāo)量和各產(chǎn)地運(yùn)往各銷(xiāo)地每件物品的運(yùn)費(fèi)如下表所示。問(wèn)：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？銷(xiāo)量<產(chǎn)量運(yùn)輸問(wèn)題的應(yīng)用B1B2B3產(chǎn)量A1646300A2655300銷(xiāo)量150150200運(yùn)輸問(wèn)題的應(yīng)用100x24x14庫(kù)存量200150150銷(xiāo)量300x23x22x21A2300x13x12x11A1產(chǎn)量B3B2B1多余的產(chǎn)量100作為庫(kù)存，A1和A2各庫(kù)存多少待定。運(yùn)輸問(wèn)題的應(yīng)用10000庫(kù)存量200150150銷(xiāo)量300556A2300646A1產(chǎn)量B3B2B1在運(yùn)價(jià)表中也增加庫(kù)存的相應(yīng)列：庫(kù)存量運(yùn)價(jià)為0。運(yùn)輸問(wèn)題的應(yīng)用結(jié)論：對(duì)于產(chǎn)量大于銷(xiāo)量的運(yùn)輸問(wèn)題，在運(yùn)輸作業(yè)表上增加一列，其銷(xiāo)量等于總產(chǎn)量和總銷(xiāo)量之差，運(yùn)價(jià)均為0?？梢詫⒃黾拥囊涣欣斫鉃榧傧脘N(xiāo)地，其銷(xiāo)量即庫(kù)存量。思考：對(duì)于銷(xiāo)量大于產(chǎn)量的問(wèn)題怎么辦？銷(xiāo)量>產(chǎn)量運(yùn)輸問(wèn)題的應(yīng)用B1B2B3產(chǎn)量A1646200A2655300銷(xiāo)量250150200運(yùn)輸問(wèn)題的應(yīng)用辦法：增加一行表示缺貨量。100000缺貨量200150250銷(xiāo)量300556A2200646A1產(chǎn)量B3B2B1運(yùn)輸問(wèn)題的應(yīng)用實(shí)際應(yīng)用中，可能出現(xiàn)的其他情況：（1）某些運(yùn)輸線路上的運(yùn)輸能力有限制；處理辦法：直接在約束條件中增加該約束，即保證X14的取值不超過(guò)產(chǎn)量、銷(xiāo)量和線路最大運(yùn)輸能力。（2）目標(biāo)函數(shù)求最大值不是最小值；運(yùn)輸問(wèn)題的應(yīng)用（3）銷(xiāo)量大于產(chǎn)量，但某些銷(xiāo)地的銷(xiāo)量必須完全滿足，不能有缺貨；處理辦法：對(duì)缺貨量到該銷(xiāo)地的運(yùn)價(jià)定為一個(gè)充分大的值M。（類(lèi)似于大M法）運(yùn)輸問(wèn)題的應(yīng)用如表中B2銷(xiāo)量不能短缺：1000M0缺貨量200150250銷(xiāo)量300556A2200646A1產(chǎn)量B3B2B1運(yùn)輸問(wèn)題的應(yīng)用（4）銷(xiāo)量大于產(chǎn)量時(shí)，若某地的銷(xiāo)量可以有一定量缺貨，但供應(yīng)量必須不小于某個(gè)值p；處理辦法：將該銷(xiāo)地分解為兩個(gè)銷(xiāo)地Bj1和Bj2，Bj1對(duì)應(yīng)必須滿足的銷(xiāo)量p，Bj2對(duì)應(yīng)缺貨的銷(xiāo)量bj-p。其中，缺貨量到Bj1的運(yùn)價(jià)為“大M”。運(yùn)輸問(wèn)題的應(yīng)用如表中B2銷(xiāo)量不能低于100：10000缺貨量200150250銷(xiāo)量300556A2200646A1產(chǎn)量B3B2B1B21B22100504455M0運(yùn)輸問(wèn)題的應(yīng)用例1：石家莊北方研究院有一、二、三，三個(gè)區(qū)。每年分別需要用煤3000、1000、2000t，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價(jià)格、質(zhì)量相同。供應(yīng)能力分別為1500、4000t，運(yùn)價(jià)如下表。由于需大于求，經(jīng)院研究決定一區(qū)供應(yīng)量可減少0—300t，二區(qū)必須滿足需求量，三區(qū)供應(yīng)量不少于1500t，試求總費(fèi)用為最低的調(diào)運(yùn)方案。一區(qū)二區(qū)三區(qū)產(chǎn)量臨城1.801.701.554000盂縣1.601.501.751500銷(xiāo)量300010002000運(yùn)輸問(wèn)題的應(yīng)用一區(qū)一區(qū)二區(qū)三區(qū)三區(qū)產(chǎn)量臨城1.801.801.701.551.554000盂縣1.601.601.501.751.751500假想產(chǎn)地M0MM0500銷(xiāo)量270030010001500500解：根據(jù)題意，作出產(chǎn)銷(xiāo)平衡的運(yùn)價(jià)表，取M代表一個(gè)很大的正數(shù)，其作用是強(qiáng)迫相應(yīng)的x31、x33、x34取值為0。運(yùn)輸問(wèn)題的應(yīng)用1234產(chǎn)量A1613221750B1413191560C192023——50最低需要量3070010最高需要量507030不限例2：設(shè)有A、B、C三個(gè)化肥廠供應(yīng)1、2、3、4四個(gè)地區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表。試求總費(fèi)用為最低的化肥調(diào)撥方案。運(yùn)輸問(wèn)題的應(yīng)用1’1’’234’4’’產(chǎn)量A16161322171750B14141319151560C19192023MM50DM0M0M050銷(xiāo)量302070301050解：根據(jù)題意，作出產(chǎn)銷(xiāo)平衡的運(yùn)價(jià)表運(yùn)輸問(wèn)題的應(yīng)用2、生產(chǎn)與儲(chǔ)存問(wèn)題例1：某廠按合同規(guī)定須于當(dāng)年每個(gè)季度末分別提供10、15、25、20臺(tái)同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺(tái)柴油機(jī)的成本如下表。如果生產(chǎn)出來(lái)的柴油機(jī)當(dāng)季不交貨，每臺(tái)每積壓一個(gè)季度需儲(chǔ)存、維護(hù)等費(fèi)用0.15萬(wàn)元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。運(yùn)輸問(wèn)題的應(yīng)用運(yùn)輸問(wèn)題的應(yīng)用解：設(shè)xij為第i季度生產(chǎn)的第j季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足：交貨：

生產(chǎn)：x11

=10x11+x12+x13+x14≤25

x12+x22=15x22+x23+x24≤35

x13+x23+x33

=25x33+x34≤30

x14+x24+x34+x44=20x44≤10

運(yùn)輸問(wèn)題的應(yīng)用把第i季度生產(chǎn)的柴油機(jī)數(shù)目看作第i個(gè)生產(chǎn)廠的產(chǎn)量；把第j季度交貨的柴油機(jī)數(shù)目看作第j個(gè)銷(xiāo)售點(diǎn)的銷(xiāo)量；成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)?？蓸?gòu)造下列產(chǎn)銷(xiāo)平衡問(wèn)題：例2：光明儀器廠生產(chǎn)電腦繡花機(jī)是以產(chǎn)定銷(xiāo)的。已知1至6月份各月的生產(chǎn)能力、合同銷(xiāo)量和單臺(tái)電腦繡花機(jī)平均生產(chǎn)費(fèi)用見(jiàn)下表：運(yùn)輸問(wèn)題的應(yīng)用已知上年末庫(kù)存103臺(tái)繡花機(jī)，如果當(dāng)月生產(chǎn)出來(lái)的機(jī)器當(dāng)月不交貨，則需要運(yùn)到分廠庫(kù)房，每臺(tái)增加運(yùn)輸成本0.1萬(wàn)元,每臺(tái)機(jī)器每月的平均倉(cāng)儲(chǔ)費(fèi)、維護(hù)費(fèi)為0.2萬(wàn)元。在7—8月份銷(xiāo)售淡季，全廠停產(chǎn)1個(gè)月，因此在6月份完成銷(xiāo)售合同后還要留出庫(kù)存80臺(tái)。加班生產(chǎn)機(jī)器每臺(tái)增加成本1萬(wàn)元。問(wèn)應(yīng)如何安排1—6月份的生產(chǎn)，可使總的生產(chǎn)費(fèi)用（包括運(yùn)輸、倉(cāng)儲(chǔ)、維護(hù)）最少？運(yùn)輸問(wèn)題的應(yīng)用解：這個(gè)生產(chǎn)存儲(chǔ)問(wèn)題可化為運(yùn)輸問(wèn)題來(lái)做?？紤]：各月生產(chǎn)與交貨分別視為產(chǎn)地和銷(xiāo)地。1）1-6月份合計(jì)生產(chǎn)能力（包括上年末儲(chǔ)存量）為743臺(tái)，銷(xiāo)量為707臺(tái)。設(shè)一假想銷(xiāo)地銷(xiāo)量為36；2）上年末庫(kù)存103臺(tái)，只有倉(cāng)儲(chǔ)費(fèi)和運(yùn)輸費(fèi)，把它列為的0行；3）6月份的需求除70臺(tái)銷(xiāo)量外，還要80臺(tái)庫(kù)存，其需求應(yīng)為70+80=150臺(tái)；4）1-6表示1-6月份正常生產(chǎn)情況，1’-6’表示1-6月份加班生產(chǎn)情況。運(yùn)輸問(wèn)題的應(yīng)用產(chǎn)銷(xiāo)平衡的運(yùn)價(jià)表：運(yùn)輸問(wèn)題的應(yīng)用3、轉(zhuǎn)運(yùn)問(wèn)題原運(yùn)輸問(wèn)題上增加若干轉(zhuǎn)運(yùn)站。運(yùn)輸方式有：產(chǎn)地轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)站銷(xiāo)地、產(chǎn)地產(chǎn)地、產(chǎn)地銷(xiāo)地、銷(xiāo)地轉(zhuǎn)運(yùn)站、銷(xiāo)地產(chǎn)地等。例：某公司有A1、A2、A3三個(gè)分廠生產(chǎn)某種物質(zhì)，分別供應(yīng)B1、B2、B3、B4四個(gè)地區(qū)的銷(xiāo)售公司銷(xiāo)售。假設(shè)質(zhì)量相同，有關(guān)數(shù)據(jù)如下表：運(yùn)輸問(wèn)題的應(yīng)用假設(shè)：

1、每個(gè)分廠的物資不一定直接發(fā)運(yùn)到銷(xiāo)地,可以從其中幾個(gè)產(chǎn)地集中一起運(yùn)；

2、運(yùn)往各銷(xiāo)地的物資可以先運(yùn)給其中幾個(gè)銷(xiāo)地，再轉(zhuǎn)運(yùn)給其他銷(xiāo)地；

3、除產(chǎn)銷(xiāo)地之外，還有幾個(gè)中轉(zhuǎn)站，在產(chǎn)地之間、銷(xiāo)地之間或在產(chǎn)地與銷(xiāo)地之間轉(zhuǎn)運(yùn)。運(yùn)價(jià)