第13講 簡(jiǎn)單的統(tǒng)籌規(guī)劃問(wèn)題

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

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

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

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

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

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

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

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

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

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

11、廣為一般命題：“一條公路上有n個(gè)倉(cāng)庫(kù)，它們分別存貨A1噸、A2噸、an噸.現(xiàn)在需要把所有的貨物集中存放在一個(gè)倉(cāng)庫(kù)里，應(yīng)該選取哪個(gè)倉(cāng)庫(kù)可以使總運(yùn)輸費(fèi)最少？”它的解法將涉及到一次函數(shù)的知識(shí)，同學(xué)們?cè)趯W(xué)過(guò)初三代數(shù)之后就會(huì)完全明白了。例4 189米長(zhǎng)的鋼筋要剪成4米或7米兩種尺寸，如何剪法最省材料？分析 顯然無(wú)殘料的剪法是最優(yōu)方案.于是考慮二元一次不定方程的整數(shù)解問(wèn)題。解：設(shè)4米長(zhǎng)的剪x根，7米長(zhǎng)的剪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。因此，有七種剪法都是最省材料的。說(shuō)明：本例是最簡(jiǎn)單的下料問(wèn)題，屬于“線性規(guī)劃”的范疇，線性規(guī)劃是運(yùn)用一次方程（組）、一次函數(shù)來(lái)解決規(guī)劃問(wèn)題的數(shù)學(xué)分支。規(guī)劃論研究的問(wèn)題主要有兩類(lèi)：一類(lèi)是確定了一項(xiàng)任務(wù)，研究怎樣精打細(xì)算使用最少人力、物力和時(shí)間去完成它；另一類(lèi)是在已有一定數(shù)量的人力、物力和財(cái)力的條件下，研究怎樣合理調(diào)配，使它們發(fā)揮最大限度的作用，從而完成最多的任務(wù)。例5 用10尺長(zhǎng)的竹竿做原材料，來(lái)截取3尺、4尺長(zhǎng)的甲、乙兩種短竹竿各100根，至少要用去

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

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

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

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