第13講 簡單的統(tǒng)籌規(guī)劃問題

1、第13講 簡單的統(tǒng)籌規(guī)劃問題解題思路：先仔細考慮達到最優(yōu)策略要遵循的原則，再想具體辦法。例1 某工地A有20輛卡車，要把60車渣土從A運到B，把40車磚從C運到D（工地道路圖如圖所示），問如何調(diào)運最省汽油？例2 一支勘探隊在五個山頭A、B、C、D、E設(shè)立了基地，人數(shù)如圖所示.為調(diào)整使各基地人數(shù)相同，如何調(diào)動最方便？（調(diào)動時不考慮路程遠近）例3 在一條公路上每隔100千米有一個倉庫（如圖），共有5個倉庫.一號倉庫存有10噸貨物，二號倉庫有20噸貨物，五號倉庫存有40噸貨物，其余兩個倉庫是空的?，F(xiàn)在想把所有的貨物集中存放在一個倉庫里，如果每噸貨物運輸1公里需要0.5元運輸費，那么最少要多少運費才行

2、？例4 189米長的鋼筋要剪成4米或7米兩種尺寸，如何剪法最省材料？例5 用10尺長的竹竿做原材料，來截取3尺、4尺長的甲、乙兩種短竹竿各100根，至少要用去原材料幾根？怎么截法最合算？例6 甲、乙兩個服裝廠每個工人和設(shè)備都能全力生產(chǎn)同一規(guī)格的西服，甲廠每月用的時間生產(chǎn)上衣，的時間生產(chǎn)褲子，全月恰好生產(chǎn)900套西服；乙廠每月用的時間生產(chǎn)上衣，的時間生產(chǎn)褲子，全月恰好生產(chǎn)1200套西服?，F(xiàn)在兩廠聯(lián)合生產(chǎn)，盡量發(fā)揮各自的特長多生產(chǎn)西服， 那么現(xiàn)在每月比過去多生產(chǎn)西服多少套？習題1.某鄉(xiāng)共有六塊甘蔗地，每塊地的產(chǎn)量如下圖所示.現(xiàn)在準備建設(shè)一座糖廠，問糖廠建于何處總運費最?。?.產(chǎn)地A1、A2、A3和

3、銷售地B1、B2、B3、B4都在鐵路線上，位置如下圖所示.已知A1、A2、A3的產(chǎn)量分別為5噸、3噸、2噸；B1、B2、B3、B4的銷售量分別是1噸、2噸、3噸、4噸.試求出使總運輸噸公里數(shù)最小的調(diào)運方案。3.把長239米的鋼筋截成17米和24米長的鋼筋，如何截法最省材料？4.鋼筋原材料每件長7.3米，每套鋼筋架子用長2.9米、2.1米和1.5米的鋼筋各1段.現(xiàn)在需要綁好鋼筋架子100套，至少要用去原材料幾件？截料方法怎樣最?。?.某車間有銑床3臺，車床3臺，自動機床1臺，生產(chǎn)一種由甲、乙兩個零件組成的產(chǎn)品.每臺銑床每天生產(chǎn)甲零件10個，或者生產(chǎn)乙零件20個；每臺車床每天生產(chǎn)甲零件20個，或者

4、生產(chǎn)乙零件30個；每臺自動機床每天生產(chǎn)甲零件30個，或者生產(chǎn)乙零件80個.如何安排這些機器的生產(chǎn)任務(wù)才能獲得最大數(shù)量的成套產(chǎn)品？每天最多可生產(chǎn)多少套產(chǎn)品？第十三講 簡單的統(tǒng)籌規(guī)劃問題這一講我們討論有關(guān)物資調(diào)運、下料問題及配套生產(chǎn)等實例。例1 某工地A有20輛卡車，要把60車渣土從A運到B，把40車磚從C運到D（工地道路圖如右圖所示），問如何調(diào)運最省汽油？分析 把渣土從A運到B或把磚從C運到D，都無法節(jié)省汽油.只有設(shè)法減少跑空車的距離，才能省汽油。解：如果各派10輛車分別運渣土和磚，那么每運一車渣土要空車跑回300米，每運一車磚則要空車跑回360米，這樣到完成任務(wù)總共空車跑了3006036040

5、=32400（米）。如果一輛車從ABCDA跑一圈，那么每運一車渣土、再運一車磚要空車跑240+90330（米）.因此，先派20輛車都從A開始運渣土到B，再空車開往C運磚到D后空車返回A，這樣每輛車跑兩圈就完成了運磚任務(wù).然后再派這20輛車都從A運渣土到B再空車返回A，則運渣土任務(wù)也完成了.這時總共空車跑了33040+3002019200（米）.后一種調(diào)運方案比前一種減少跑空車13200米，這是最佳節(jié)油的調(diào)運方案。說明：“節(jié)省跑空車的距離”是物資調(diào)運問題的一個原則：下面通過例子再介紹“避免對流”的原則。例2 一支勘探隊在五個山頭A、B、C、D、E設(shè)立了基地，人數(shù)如右圖所示.為調(diào)整使各基地人數(shù)相同

6、，如何調(diào)動最方便？（調(diào)動時不考慮路程遠近）分析 在人員調(diào)運時不考慮路程遠近的因素，就只需避免兩個基地之間相互調(diào)整，即“避免對流現(xiàn)象”。解：五個基地人員總數(shù)為17+4+16+14+9=60（人）依題意，調(diào)整后每個基地應(yīng)各有605=12（人）。因此，需要從多于12人的基地A、C、D向不足12人的基地B、E調(diào)人.為了避免對流，經(jīng)試驗容易得到調(diào)整方案如下：先從D調(diào)2人到E，這樣E尚缺1人；再由A調(diào)1人給E，則E達到要求.此時，A尚多余4人，C也多余4人，總共8人全部調(diào)到B，則B亦符合要求。調(diào)動示意圖如右圖所示.這樣的圖形叫做物資流向圖.用流向圖代替調(diào)運方案，能直觀地看出調(diào)運狀況及有無對流現(xiàn)象，又可避免

7、列表和計算的麻煩，圖中箭頭表示流向，箭桿上的數(shù)字表示流量。說明：發(fā)生對流的調(diào)運方案不可能是最優(yōu)方案.這個原則可以證明：如右圖，設(shè)A1B2a千米，B2B1=b千米，B1A2c千米.如果從A1運1噸貨物到B1，同時又從A2運1噸貨物到B2，那么在B1B2之間A1的物資從西向東運輸，A2的貨物從東向西運輸，兩者發(fā)生對流，于是這樣調(diào)動的總噸千米數(shù)為（ab）+（bc）ac+2b.而如果從A1運1噸貨物到B2，同時從A2運1噸貨物到B1，栽蛟聳渥芏智資猘+c.顯然a+ca+c+2b。例3 在一條公路上每隔100千米有一個倉庫（如右圖，）共有5個倉庫.一號倉庫存有10噸貨物，二號倉庫有20噸貨物，五號倉庫存

8、有40噸貨物，其余兩個倉庫是空的?，F(xiàn)在想把所有的貨物集中存放在一個倉庫里，如果每噸貨物運輸1公里需要0.5元運輸費，那么最少要多少運費才行？分析 欲使花費的運輸費少，關(guān)鍵在于運輸?shù)呢浳锖吐烦瘫M可能少，實際經(jīng)驗告訴我們一個原則“小往大處靠”.下面就以兩地調(diào)運問題為例加以計算驗證：如上圖，在公路上A、B兩地各有10噸、15噸麥子，問打麥場建在何處運費最少？設(shè)打麥場建在C點，則總運費是（假定每噸小麥運輸1千米的費用是a元）W10aAC15aBC10aAC10aBC5aBC10a（ACBC）5aBC=10aAB5aBC上式中10aAB是固定的值，不隨C點的選取而改變；只有5aBC隨BC的變化而改變，若

9、BC越小，則W也越小.當BC=0時，即C點與B點重合時，W的值最小.因此打麥場建在B點時總運費是10aAB（元）為最少.顯然當打麥場建在AB線段之外時，總運費都大于10aAB（元）。解：根據(jù)“小往大處靠”的原則，先把一號倉庫的10噸貨物送往二號倉庫集中，需運費100.5100=500（元）。這時可以認為二號倉庫有30噸貨物，而五號倉庫有40噸貨物，于是又應(yīng)把二號倉庫的30噸貨物運往五號倉庫集中，需運費300.5300=4500（元）。所以，把貨物集中存放在五號倉庫時所花運費最少，需要5004500=5000（元）。說明：“小往大處靠”的原則也不是一成不變的，具體問題還要具體分析。再舉兩例如下：

10、例如一號倉庫有20噸貨物，二號倉庫有30噸貨物，其他倉庫存貨照樣如前，那么應(yīng)該往哪個倉庫集中呢？首先仍應(yīng)把一號倉庫的20噸貨物運往二號倉庫集中，然后再把五號倉庫的40噸貨物也運往二號倉庫集中，這樣運費最少。又如一號倉庫有30噸貨物，二號倉庫有20噸貨物，其他倉庫存貨仍然如前，那么應(yīng)該往哪個倉庫集中呢？先把一號倉庫的30噸貨物運往二號倉庫集中，再把五號倉庫的40噸貨物也運往二號倉庫集中，這樣運費最省.（想想為什么？）還有一點值得注意，在決定貨物往何處集中時，起決定作用的是貨物的重量，至于距離僅僅是為了計算運費.如果把本題中各個倉庫之間的距離換成另外一些數(shù)值，仍應(yīng)該把貨物集中到五號倉庫。本題可以推

11、廣為一般命題：“一條公路上有n個倉庫，它們分別存貨A1噸、A2噸、an噸.現(xiàn)在需要把所有的貨物集中存放在一個倉庫里，應(yīng)該選取哪個倉庫可以使總運輸費最少？”它的解法將涉及到一次函數(shù)的知識，同學們在學過初三代數(shù)之后就會完全明白了。例4 189米長的鋼筋要剪成4米或7米兩種尺寸，如何剪法最省材料？分析 顯然無殘料的剪法是最優(yōu)方案.于是考慮二元一次不定方程的整數(shù)解問題。解：設(shè)4米長的剪x根，7米長的剪y根，依題意列方程4x7y189。根據(jù)倍數(shù)分析法可知7x（即x是7的倍數(shù)）。令x10，則7y189，解出y1=27；x27，則7y161，解出y223；x3=14，則7y133，解出y319；x4=21，

12、則7y=105，解出y4=15；x528，則7y=77，解出y5=11；x6=35，則7y49，解出y67；x7=42，則7y21，解出y7=3。因此，有七種剪法都是最省材料的。說明：本例是最簡單的下料問題，屬于“線性規(guī)劃”的范疇，線性規(guī)劃是運用一次方程（組）、一次函數(shù)來解決規(guī)劃問題的數(shù)學分支。規(guī)劃論研究的問題主要有兩類：一類是確定了一項任務(wù)，研究怎樣精打細算使用最少人力、物力和時間去完成它；另一類是在已有一定數(shù)量的人力、物力和財力的條件下，研究怎樣合理調(diào)配，使它們發(fā)揮最大限度的作用，從而完成最多的任務(wù)。例5 用10尺長的竹竿做原材料，來截取3尺、4尺長的甲、乙兩種短竹竿各100根，至少要用去

13、原材料幾根？怎么截法最合算？分析 不難想到有三種截法省料：截法1：截成3尺、3尺、4尺三段，無殘料；截法2：截成3尺、3尺、3尺三段，殘料1尺；截法3：截成4尺、4尺兩段，殘料2尺。由于截法1最理想（無殘料），因此應(yīng)該充分應(yīng)用截法1.考慮用原材料50根，可以截成100根3尺長的短竹竿，而4尺長的僅有50根，還差50根.于是再應(yīng)用截法3，截原材料25根，可以得到4尺長的短竹竿50根，留下殘料22550（尺）。解：至少要用75根原材料，其中50根用截法1，25根用截法3，這樣的截法最省料.說明：一般說來，一定長度的條形材料要截取兩種毛坯的下料問題，用本例的方法求解是比較省料的，這種解法的理論根據(jù)要

14、用到二元不等式及一次函數(shù)圖像，有興趣的讀者可參閱有關(guān)書刊。例6 甲、乙兩個服裝廠每個工人和設(shè)備都能全力生產(chǎn)同一規(guī)格的西產(chǎn)1200套西服.現(xiàn)在兩廠聯(lián)合生產(chǎn)，盡量發(fā)揮各自特長多生產(chǎn)西服，那么現(xiàn)在每月比過去多生產(chǎn)西服多少套？分析 根據(jù)已知條件，甲廠生產(chǎn)一條褲子與一件上衣的時間之比為23，因此在單位時間內(nèi)甲廠生產(chǎn)的上衣與褲子的數(shù)量之比也是23（注意：在固定時間內(nèi)，數(shù)量與每件所用時間成反比）；同理可知，在單位時間內(nèi)乙廠生產(chǎn)上衣與褲子的數(shù)量之比是34。單說明理由：如果甲廠生產(chǎn)9條褲子，則相當甲廠生產(chǎn)6件上衣；如果讓乙廠生產(chǎn)這6件上衣，則相當于生產(chǎn)8條褲子.這就是說，甲廠生產(chǎn)9條褲子時乙廠只能生產(chǎn)8條褲子.

15、顯然甲廠善于生產(chǎn)褲子.類似地，如果乙廠生產(chǎn)9件上衣，則相當于乙廠生產(chǎn)12條褲子；如果讓甲廠生產(chǎn)這12條褲子，則相當甲廠生產(chǎn)8件上衣.這就是說，乙廠生產(chǎn)9件上衣時甲廠只能生產(chǎn)8件上衣.顯然乙廠善于生產(chǎn)上衣.解：兩廠聯(lián)合生產(chǎn)，盡量發(fā)揮各自特長，安排乙廠全力生產(chǎn)上衣.由同時，安排甲廠全力生產(chǎn)褲子，則甲廠全月可生產(chǎn)褲子為了配套生產(chǎn)，甲廠先全力生產(chǎn)2100條褲子，這需要于是，現(xiàn)在聯(lián)合生產(chǎn)每月比過去多生產(chǎn)西服（210060）-（9001200）=60（套）。說明：本例是線性規(guī)劃中勞力組合問題.勞力組合最簡單的情況就是效率比問題.這里給出多種勞力（或機械）干兩種配套活的一般分工原則：習題十三1.某鄉(xiāng)共有六塊

16、甘蔗地，每塊地的產(chǎn)量如下圖所示.現(xiàn)在準備建設(shè)一座糖廠，問糖廠建于何處總運費最?。?.產(chǎn)地A1、A2、A3和銷售地B1、B2、B3、B4都在鐵路線上，位置如下圖所示.已知A1、A2、A3的產(chǎn)量分別為5噸、3噸、2噸；B1、B2、B3、B4的銷售量分別是1噸、2噸、3噸、4噸.試求出使總運輸噸公里數(shù)最小的調(diào)運方案。3.把長239米的鋼筋截成17米和24米長的鋼筋，如何截法最省材料？4.鋼筋原材料每件長7.3米，每套鋼筋架子用長2.9米、2.1米和1.5米的鋼筋各1段.現(xiàn)在需要綁好鋼筋架子100套，至少要用去原材料幾件？截料方法怎樣最??？5.某車間有銑床3臺，車床3臺，自動機床1臺，生產(chǎn)一種由甲、乙兩個零件組成的產(chǎn)品.每臺銑床每天生產(chǎn)甲零件10個，或者生產(chǎn)乙零件20個；每臺車床每天生產(chǎn)甲零件20個，或者生產(chǎn)乙零件30個；每臺自動機床每天生產(chǎn)甲零件30個，或者生產(chǎn)乙零件80個.如何安排這些機器的生產(chǎn)任務(wù)才能獲得最大數(shù)量的成套產(chǎn)品？每天最多可生產(chǎn)多少套產(chǎn)品？習題十三解答1.答：糖廠建于C處總運費最省。如下圖（a），根據(jù)“小往大處靠”的原則，把A靠到B；E靠到G，F(xiàn)靠到G，這樣就成圖（b）同理：B靠到C，D靠到C，這時，C為16噸；G為11噸.最后，G靠到C。2.答：A1運往B11噸；運往B22噸；運往B32噸。A2運往B31噸；運往B42噸。