第27講 運(yùn)籌學(xué)初步

第27講運(yùn)籌學(xué)初步（一）運(yùn)籌學(xué)是利用數(shù)學(xué)來研究人力、物力的運(yùn)用和籌劃，使它們能發(fā)揮最大效率的科學(xué)。它包含的內(nèi)容非常廣泛，例如物資調(diào)運(yùn)、場地設(shè)置、工作分配、排隊(duì)、對策、實(shí)驗(yàn)最優(yōu)等等，每類問題都有特定的解法。運(yùn)籌學(xué)作為一門科學(xué)，要運(yùn)用各種初等的和高等的數(shù)學(xué)知識(shí)及方法，但是其中分析問題的某些樸素的思想方法，如高效率優(yōu)先的原則、調(diào)整比較的思想、嘗試探索的方法等，都是我們小學(xué)生能夠掌握的。這些來源于生活實(shí)際的問題，正是啟發(fā)同學(xué)們學(xué)數(shù)學(xué)、用數(shù)學(xué)最好的思維鍛煉題目。本講主要研究物資調(diào)運(yùn)問題。將一些物資從某些地方調(diào)彳主另一些地方，要求總運(yùn)費(fèi)或物資運(yùn)行的總噸千米數(shù)最少，就是物資調(diào)運(yùn)問題。例1A，B，C三地的距離（單位：千米）如左下圖所示?，F(xiàn)有一輛載重量4噸的汽車要完成下列任務(wù)：從A地運(yùn)12噸煤到B地，從B地運(yùn)8噸鋼材到C地，從C地運(yùn)16噸糧食到A地。怎樣安排才能使汽車空駛里程最短？分析與解：如右上圖所示，將各段需運(yùn)輸?shù)拇螖?shù)（括號(hào)內(nèi)的數(shù)）及運(yùn)輸走向（箭頭指向）標(biāo)在圖上。由于:到A的次數(shù)最多，所以應(yīng)從C開始。按C-A—B-C，兩次循環(huán)后，B地的鋼材運(yùn)完，C地還有8噸糧食待運(yùn)，A地還有4噸煤待運(yùn)。再從C運(yùn)4噸糧食到入，然后空駛回C地，再從C運(yùn)4噸糧食到A,最后從A運(yùn)4噸煤到B。這樣的安排只空駛了7千米，空駛里程最短。例2在一條公路上，每隔10千米有一座倉庫（如下圖），共有五座，圖中數(shù)字表示各倉庫庫存貨物的重量?，F(xiàn)在要把所有的貨物集中存放在一個(gè)倉庫里，如果每噸貨物運(yùn)輸1千米需要運(yùn)費(fèi)0.9元，那么集中到哪個(gè)倉庫運(yùn)費(fèi)最少？AEcnEIIIII噸％噸-網(wǎng)噸1口噸3噸分析與解：最簡單的方法是逐個(gè)計(jì)算集中到各個(gè)倉庫所需的運(yùn)費(fèi)，然后加以比較。但這種方法計(jì)算繁瑣，我們只需比較各點(diǎn)的優(yōu)劣。例如，比較集中到C和集中到D的優(yōu)劣。1口噸如噸處噸川噸6。噸如上圖所示，從右向左運(yùn)的貨物，如果集中到D，那么只有E倉庫的60噸運(yùn)到D；如果集中到C，那么等于E倉庫的60噸運(yùn)到D，再將D倉庫的10噸及E倉庫運(yùn)來的60噸一起運(yùn)到C。所以運(yùn)到C倉庫比運(yùn)到D倉庫多（60+10）X10=700（噸千米）。同理，從左向右運(yùn)的貨物，運(yùn)到C倉庫比運(yùn)到D倉庫少（10+30+20）X10=600（噸千米）。兩相比較，集中到D比集中到C好。經(jīng)過對各點(diǎn)的比較，貨物集中到D倉庫運(yùn)費(fèi)最少，運(yùn)費(fèi)為：(10X30+30X20+20X10+60X10)X0.9=1530(元)例3北京、洛陽分別有11臺(tái)和5臺(tái)完全相同的機(jī)器，準(zhǔn)備給杭州7臺(tái)、西安9臺(tái)，每臺(tái)機(jī)器的運(yùn)費(fèi)如下表：發(fā)站f-杭州西安北京8Q01000??洛陽700600；如何調(diào)運(yùn)能使總運(yùn)費(fèi)最?。糠治雠c解：由表中看出，北京到杭州的運(yùn)費(fèi)比到西安便宜，而洛陽正相反，到西安的運(yùn)費(fèi)比到杭州便宜。所以，北京的機(jī)器應(yīng)盡量運(yùn)彳主杭州，洛陽的機(jī)器應(yīng)盡量運(yùn)彳主西安。最佳的調(diào)運(yùn)方案為：北京發(fā)彳主杭州7臺(tái)，發(fā)彳主西安4臺(tái)，洛陽發(fā)彳主西安5臺(tái)。總運(yùn)費(fèi)為800X7+1000X4+600X5=12600（元】例4北京、上海分別有10臺(tái)和6臺(tái)完全相同的機(jī)器，準(zhǔn)備給武漢11臺(tái)，西安5臺(tái)，每臺(tái)機(jī)器的運(yùn)費(fèi)如下表：發(fā)曰.武漢西安北京500'：600上海1000如何調(diào)運(yùn)能使總運(yùn)費(fèi)最??？分析與解：與例3不同的是，北京、上海到西安的運(yùn)費(fèi)都比到武漢的高，沒有出現(xiàn)一高一低的情況。此時(shí)，可以通過比較運(yùn)輸中的差價(jià)大小來決定最佳方案。上表中第一行的差價(jià)為600-500=100（元），第二行的差價(jià)為1000-700=300（元）。說明從北京給西安多發(fā)1臺(tái)機(jī)器要多付運(yùn)費(fèi)100元，而從上海給西安多發(fā)1臺(tái)機(jī)器要多付運(yùn)費(fèi)300元。所以應(yīng)盡量把北京的產(chǎn)品運(yùn)彳主西安，而西安只要5臺(tái)，于是可知北京調(diào)彳主西安5臺(tái)，其余5臺(tái)調(diào)彳主武漢，上海6臺(tái)全部調(diào)彳主武漢，總運(yùn)費(fèi)為：600X5+500X5+700X6=9700（元）。如果改為看表中的列，那么由于第一列的差價(jià)為700-500=200（元），第二列差價(jià)為1000—600=400（元），所以武漢需要的機(jī)器應(yīng)盡量從上海調(diào)運(yùn)，而上海只有6臺(tái)，不足的部分由北京調(diào)運(yùn)。這個(gè)結(jié)論同前面得到的相同。例5A，B兩個(gè)糧店分別有70噸和60噸大米，甲、乙、丙三個(gè)居民點(diǎn)分別需要30噸、40噸和50噸大米。從A，B兩糧店每運(yùn)1噸大米到三個(gè)居民點(diǎn)的運(yùn)費(fèi)如下表所示：「申丙A27.3.3IQ5如何調(diào)運(yùn)才能使運(yùn)費(fèi)最少？分析與解：A，B糧店共有大米70+60=130（噸），甲、乙、丙三個(gè)居民點(diǎn)需要大米30+40+50=120（噸），供應(yīng)量與需求量不相等，這與例4不同。但是我們?nèi)钥梢酝ㄟ^差價(jià)的大小來決定最佳方案。觀察上表各列兩數(shù)之差，最大的是第二列10—7=3，因此A糧店的大米應(yīng)盡可能多地供應(yīng)乙，即A供應(yīng)乙40噸。在剩下的兩列中，第三列的差大于第一列的差，所以A糧店剩下的30噸應(yīng)全部供應(yīng)丙。因?yàn)锳糧店的的大米已分配完，其余的由B糧店供應(yīng)，即B供應(yīng)甲30噸，供應(yīng)丙20噸。調(diào)運(yùn)方案如右表。相應(yīng)的運(yùn)費(fèi)為：發(fā)虹r*丙A0.'40--30B即：Q-遂30X3+40X7+30X3+20X5=560（元）例6下圖中有四個(gè)倉庫（用。表示）和五個(gè)工廠（用△表示）四個(gè)倉庫中存放著五個(gè)工廠需要的同一種物資，。內(nèi)數(shù)字表示該倉庫可調(diào)出物資的數(shù)量（單位：噸），△內(nèi)數(shù)字表示該工廠需調(diào)入物資的數(shù)量（單位：噸）兩地之間連線上的數(shù)字表示兩地間的距離（單位:千米）。已知每噸千米運(yùn)費(fèi)5元，請?jiān)O(shè)計(jì)一個(gè)調(diào)運(yùn)方案，使總運(yùn)費(fèi)最少？為解決這類問題，我們先介紹流向圖的概念。在物資調(diào)運(yùn)問題中，如果要將a噸物資從A地調(diào)彳主B地，那么從A沿路線右邊向B畫一箭頭，并標(biāo)上a，稱為流向（見下圖）。由（若十個(gè)）流向構(gòu)成的圖稱為流向圖。每一個(gè)調(diào)運(yùn)方案對應(yīng)一個(gè)流向圖。A B

10用數(shù)學(xué)的方法可以證明，一個(gè)調(diào)運(yùn)方案是最佳的，當(dāng)且僅當(dāng)：（1）流向圖上沒有對流；（2）如果流向圖中有環(huán)形路線，在每一個(gè)環(huán)形路線（叫做圈）內(nèi)，順時(shí)針和逆時(shí)針方向調(diào)動(dòng)的路程都不超過半圈長度。判斷是否最佳調(diào)運(yùn)方案的兩條標(biāo)準(zhǔn)從直觀上很容易接受。如在下圖中，右邊的方案就比左邊的好。B—§—— E?—AI 1 1 DAl 1 1 D在實(shí)際圖上作業(yè)時(shí)，可以先采取就近分配的方法，然后再逐步調(diào)整，使流向圖滿足最佳方案的兩個(gè)條件。用流向圖的方法可得本題的最佳調(diào)運(yùn)方案如下圖：總運(yùn)費(fèi)為：5X（20X8+10X13+20X14+30X9+30X12+40X10+80X7+20X5）=11300（元）。練習(xí)27如右圖所示，工地上要挫車渣土從A運(yùn)到B,把2車磚從C運(yùn)到D。一輛汽車最少跑多遠(yuǎn)可完成任務(wù)？A，B兩個(gè)糧店分別有80噸和60噸大米，甲、乙兩個(gè)居民點(diǎn)分別需要55噸和85噸大米。從A，B兩個(gè)糧店每運(yùn)1噸大米到兩個(gè)居民點(diǎn)的運(yùn)費(fèi)如下表所示。運(yùn)費(fèi)最少是多少元？*用?’咨A67B58A，B兩化肥廠分別可以提供化月尊500噸和4000噸，甲、乙兩地分別需要化肥3000噸和3500噸。從A，B兩個(gè)化肥廠每運(yùn)1噸化肥到甲、乙兩地的運(yùn)費(fèi)如下表所示。運(yùn)費(fèi)最少是多少？甲」社A1216B1521有A，B兩個(gè)金屬倉庫，分別存有鋁材60噸和40噸，另有甲、乙兩個(gè)工廠，分別需要鋁林5噸和45噸。從A，B兩倉庫每運(yùn)1噸鋁材

到這兩個(gè)工廠的運(yùn)費(fèi)如下表所示。運(yùn)費(fèi)最少是多少？5.某學(xué)校調(diào)整教室桌椅，右圖中標(biāo)出了教室的位置，圖中口內(nèi)的數(shù)字表示該教室要搬出桌椅的數(shù)量，。內(nèi)的數(shù)字表示該教室要搬入桌椅的數(shù)量。怎樣搬運(yùn)最省事？6.60個(gè)同學(xué)去野營，他們搭的五頂帳蓬正好位于正五邊形的五個(gè)頂點(diǎn)上（見左下圖），圖中圓圈內(nèi)的數(shù)字表示各個(gè)帳