數(shù)學(xué)建模：第五章 運(yùn)籌及優(yōu)化模型

1、1第五章 運(yùn)籌與優(yōu)化模型5.1 簡(jiǎn)單的運(yùn)籌與優(yōu)化模型 一、 線性規(guī)劃模型 線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支，它起源于工業(yè)生產(chǎn)組織管理的決策問題。在數(shù)學(xué)上它用來確定多變量線性函數(shù)在變量滿足線性約束條件下的最優(yōu)值；隨著計(jì)算機(jī)的發(fā)展，出現(xiàn)了如單純形法等有效算法，它在工農(nóng)業(yè)、軍事、交通運(yùn)輸、決策管理與規(guī)劃等領(lǐng)域中有廣泛的應(yīng)用。 2 例1、某工廠制造A.B兩種產(chǎn)品，制造A每噸需用煤9t，電力4kw，3個(gè)工作日；制造B每噸需用煤5t，電力5kw，10個(gè)工作日。已知制造產(chǎn)品A和B每噸分別獲利7000元和12000元，現(xiàn)工廠只有煤360t，電力200kw，工作日300個(gè)可以利用，問A、B兩種產(chǎn)品各應(yīng)生產(chǎn)多少噸才

2、能獲利最大？解：設(shè) ,（單位為噸）分別表示A、B產(chǎn)品的計(jì)劃生產(chǎn)數(shù)； 1x2x f表示利潤(rùn)（單位千元） 則問題歸結(jié)為如下線性規(guī)劃問題：3目標(biāo)函數(shù) 21127maxxxf約束條件 3605921 xx2005421 xx30010321xx. 0, 021xx其中( , )為決策向量， 1x2x滿足約束條件的( , )稱為可行決策。 1x2x 線性規(guī)劃問題就是指目標(biāo)函數(shù)為諸決策變量的線性函數(shù)，給定的條件可用諸決策變量的線性等式或不等式表示的決策問題。線性規(guī)劃求解的有效方法是單純形法（進(jìn)一步了解可參考有關(guān)書籍），當(dāng)然簡(jiǎn)單的問題也可用圖解法。4如用圖解法求解例1： 由約束條件決定的可行域如圖陰影所示，

3、 目標(biāo)函數(shù)的等值線向右上方移動(dòng)時(shí)其值增大，在到達(dá)點(diǎn) 時(shí)f取得最大值； 2Q5當(dāng) =20, =24時(shí)，即產(chǎn)品A生產(chǎn)20t，產(chǎn)品B生產(chǎn)24t時(shí)，生產(chǎn)方案最優(yōu)。 1x2x其最大利潤(rùn)為：7201224428千元例2：某兩個(gè)煤廠 . ，每月進(jìn)煤數(shù)量分別為60t和100t聯(lián)合供應(yīng)3個(gè)居民區(qū) 。3個(gè)居民區(qū)每月對(duì)煤的需求量依次分別為50t,70t,40t，煤廠 離3個(gè)居民區(qū) 的距離依次為10km,5km,6km，煤廠 離3個(gè)居民區(qū) 的距離依次分別為4km,8km,12km，問如何分配供煤量使得運(yùn)輸費(fèi)（即tkm）達(dá)到最??？1A2A321,BBB321,BBB2A321,BBB1A6 解：設(shè) 表示 (i=1.2)

4、煤廠提供給 （j=1.2.3)居民區(qū)的煤量； ijxiAjBf表示總運(yùn)輸費(fèi)此問題歸結(jié)為： 23222113121112846510minxxxxxxfts.60131211xxx100232221xxx502111 xx702212 xx402313 xx, 3 , 2 , 1, 2 , 1, 0jixij7一般線性規(guī)劃問題的數(shù)學(xué)表達(dá)式： nnxcxcxcf2211max(min) s.t 11212111),(bxaxaxann22222121),(bxaxaxannmnmnmmbxaxaxa),(22110,21nxxx8例3：生產(chǎn)組織與計(jì)劃問題 設(shè)有m種資源，第i(i=1,2,m)種資源

5、的現(xiàn)存量為 ，現(xiàn)要生產(chǎn)n種產(chǎn)品，已知生產(chǎn)j(j=1,2,n)種產(chǎn)品時(shí)，每單位產(chǎn)品需要第i種資源量為 ，而每單位j種產(chǎn)品可得利潤(rùn) ，問如何組織生產(chǎn)才能使利潤(rùn)最大？ ibijajc 解：用 表示生產(chǎn)第j(j=1,2,n)種產(chǎn)品的計(jì)劃數(shù)， jx上述問題可歸結(jié)為如下的數(shù)學(xué)問題： njjjxc1maxts.mibxainjjij2 . 11njxj2 . 109 二、整數(shù)規(guī)劃模型對(duì)于線性規(guī)劃： njxmibxaxcfjnjijijnjjj2 , 102 , 1min11 決策變量是連續(xù)變量，最優(yōu)解可能是小數(shù)或分?jǐn)?shù)。 10 但是在許多實(shí)際問題中，往往要求所得的解為整數(shù)，例如投資項(xiàng)目的選擇、機(jī)器的臺(tái)數(shù)、完成

6、工作的人數(shù)、裝貨的車數(shù)等，分?jǐn)?shù)和小數(shù)的答案就沒有現(xiàn)實(shí)意義了。 在現(xiàn)性規(guī)劃中，若限制 (j=1,2,n)是非負(fù)整數(shù)，則這種線性規(guī)劃問題稱為整數(shù)規(guī)劃問題。 jx為整數(shù)為整數(shù)如如212112121,0,115851215maxxxxxxxxxxf11 例4：分配問題 假設(shè)某工廠用m臺(tái)機(jī)床加工n種零件。在一個(gè)生產(chǎn)周期內(nèi)，第i(i=1,2,m)臺(tái)機(jī)床只能工作 個(gè)機(jī)時(shí)，而第j(j=1,2,n)種零件必須完成 個(gè)，又第i臺(tái)機(jī)床加工第j種零件所需機(jī)時(shí)和成本分別為 （機(jī)時(shí)個(gè)）和 （元個(gè)）。問在這個(gè)生產(chǎn)周期內(nèi)怎樣安排各機(jī)床的生產(chǎn)任務(wù)，才能使得既完成加工任務(wù)，又使總的加工成本最少？ iajbijtijc 解：在一個(gè)

7、生產(chǎn)周期內(nèi)，假設(shè)第i臺(tái)機(jī)床加工第j種零件的個(gè)數(shù)為 。 ijx由于 是零件個(gè)數(shù)，因此 必須是非負(fù)整數(shù)， ijxijx12本問題的數(shù)學(xué)模型為： minjijijxc11mints.injijijaxt1mi2 , 1jmiijbx 1nj2 , 1 為為非非負(fù)負(fù)整整數(shù)數(shù)ijx13三、非線性規(guī)劃模型非線性規(guī)劃模型的一般形式為： )2(., 2 , 10)(.miXgtsi)3(., 2 , 10)(ljXhiDX 為為可可行行集集其其中中nTnRDxxxX,),(21 f(X)為目標(biāo)函數(shù)， (2)、(3)為約束條件， (2)為不等式約束，(3)為等式約束；若只有(1)稱為無約束問題。 ) 1 ()(

8、minXf1432321213215),(minxxxxxxxxf如如0516223121xxxxx010312221xxxx15例5：容器的設(shè)計(jì)問題 某公司專門生產(chǎn)儲(chǔ)藏用容器，定貨合同要求該公司制造一種敞口的長(zhǎng)方體容器，容積恰好為12立方米，該容器的底必須為正方形，容器總重量不超過68公斤。已知用作容器四壁的材料為每平方米10 元，重3公斤；用作容器底的材料每平方米20元，重2公斤。試問制造該容器所需的最小費(fèi)用是多少？ 模型建立 設(shè)該容器底邊長(zhǎng)和高分別為 米、 米， 1x2x則問題的數(shù)學(xué)模型為 21212040)(minxxxXf（容器的費(fèi)用） . 0, 0,68212,12. .21212

9、1221xxxxxxxts（容器重量）（容器重量）（容器體積）（容器體積）16一般來說，非線性規(guī)劃模型的求解要比線性規(guī)劃模型求解困難得多，雖然現(xiàn)在已經(jīng)發(fā)展了許多非線性規(guī)劃的算法，但到目前為止，還不象線性規(guī)劃那樣有通用的單純形算法，而是各種算法都有自己特定的適用范圍，如求解法有：最速下降法、牛頓法、可行方向法、懲罰函數(shù)法等。盡管如此，非線性規(guī)劃的實(shí)際應(yīng)用還是相當(dāng)廣泛的。17 5.2 實(shí)際問題中的優(yōu)化模型一、投資策略 某部門現(xiàn)有資金10萬元，五年內(nèi)有以下投資項(xiàng)目供選擇： 項(xiàng)目A,從第一年到第四年每年初投資，次年末收回本金且獲利15%； 項(xiàng)目B，第三年初投資，第五年末收回本金且獲利25%，最大投資額

10、為4萬元； 項(xiàng)目C，第二年初投資，第五年末收回本金且獲利40%，最大投資額為3萬元； 項(xiàng)目D，每年初投資，年末收回本金且獲利6%。問如何確定投資策略使第五年末本息總額最大。18問題的目標(biāo)函數(shù)是第五年末的本息總額， 決策變量是每年初各個(gè)項(xiàng)目的投資額， 約束條件是每年初擁有的資金。 用ijx表示第i年初（5 , , 2 , 1i）項(xiàng)目4 , 3 , 2 , 1(jj分別代表A,B,C,D)的投資額， 根據(jù)所給條件只有下表1列出的ijx才是需要求解的。 項(xiàng)目 年份 A B C D 1 2 3 4 5 11x21x31x41x32x23x14x24x34x44x54x19 因?yàn)轫?xiàng)目D 每年初可以投資，

11、且年末能收回本息，所以每年初都應(yīng)把資金全部投出去， 項(xiàng)目A,從第一年到第四年每年初投資，次年末收回本金且獲利15%； 項(xiàng)目B，第三年初投資，第五年末收回本金且獲利25%，最大投資額為4萬元； 項(xiàng)目C，第二年初投資，第五年末收回本金且獲利40%，最大投資額為3萬元； 項(xiàng)目D，每年初投資，年末收回本金且獲利6%。由此可得如下的約束條件： 第一年初： 101411 xx第二年初： 1424232106. 1xxxx第三年初 241134323106. 115. 1xxxxx第四年初： 3421444106. 115. 1xxxx第五年初： 44315406. 115. 1xxx項(xiàng)目B,C對(duì)投資額的限

12、制： 3, 42332xx20項(xiàng)目A,從第一年到第四年每年初投資，次年末收回本金且獲利15%； 項(xiàng)目B，第三年初投資，第五年末收回本金且獲利25%，最大投資額為4萬元； 項(xiàng)目C，第二年初投資，第五年末收回本金且獲利40%，最大投資額為3萬元； 項(xiàng)目D，每年初投資，年末收回本金且獲利6%。 每項(xiàng)投資應(yīng)為非負(fù)的： 0ijx第五年末本息總額為5432234106. 125. 140. 115. 1xxxxz將上條件等價(jià)變形如1424232106. 1xxxx006. 124232114xxxx21由此得投資問題的線性規(guī)劃模型如下：5432234106. 125. 140. 115. 1maxxxxx

13、zs.t. 101411 xx006. 124232114xxxx006. 115.xxxx006. 115, 144413421xxxx006. 115. 1544431xxx3, 42332xx0ijx22求解得4008. 0, 0,000. 3,5436. 3,1732. 6,8268. 3312423211411xxxxxx4609. 0, 0,0752. 4, 0,0000. 45444413432xxxxx3750.14z 即第1年項(xiàng)目A,D分別投資3.8268和6.1732(萬元)；第2年項(xiàng)目A,C分別投資3.5436和3(萬元)；第3年項(xiàng)目A,B分別投

14、資0.4008和4(萬元)；第4年項(xiàng)目A投資4.0752(萬元)；第5年項(xiàng)目D投資0.4609(萬元)；5年后總資金 14。375萬元，即盈利43.75%.23二、貨機(jī)裝運(yùn)問題 某架貨機(jī)有三個(gè)貨艙：前倉、中倉、后倉。三個(gè)貨艙所能裝載的貨物的最大重量和體積都有限制，如表3所示。并且，為了保持飛機(jī)的平衡，三個(gè)貨艙中實(shí)際裝載貨物的重量必須與其最大容許重量成比例。前倉中倉后倉重量限制（噸）10168體積限制（米3）680087005300 現(xiàn)有四類貨物供該貨機(jī)本次飛行裝運(yùn)，其有關(guān)信息如表4，最后一列指裝運(yùn)后所獲得的利潤(rùn)。24重量（噸）空間（米3/噸）利潤(rùn)（元/噸）貨物1184803100貨物21565

15、03800貨物3235803500貨物4123902850應(yīng)如何安排裝運(yùn)，使該貨機(jī)本次飛行獲利最大？模型假設(shè) 問題中沒有對(duì)貨物裝運(yùn)提出其它要求，我們可作如下假設(shè)： 1）每種貨物可以分割到任意??；2）每種貨物可以在一個(gè)或多個(gè)貨艙中任意分布；253）多種貨物可以混裝，并保證不留空隙。模型建立決策變量： ijx表示第i種貨物裝入第j個(gè)貨艙的重量（噸）， 貨艙j=1,2,3分別表示前倉、中倉、后倉。 決策目標(biāo)是最大化總利潤(rùn)，即)(3800)(3100232221131211xxxxxxZMax)(2850)(3500434241333231xxxxxx)13(約束條件包括以下4個(gè)方面：1）從裝載的四種

16、貨物的總重量約束，即)14(18131211xxx26)15(15232221xxx)16(23333231xxx)17(12434241xxx2）三個(gè)貨艙的重量限制，即)18(1041312111xxxx)19(1642322212xxxx)20(843332313xxxx3）三個(gè)貨艙的空間限制，即)21(680039058065048041312111xxxx)22(870039058065048042322212xxxx)23(530039058065048043332313xxxx274）三個(gè)貨艙裝入重量的平衡約束，即)24(81610433323134232221241312111x

17、xxxxxxxxxxx模型求解將以上模型輸入LINDO求解，可以得到：28OBJECTIVE FUNCTION VALUE1) 121515.8VARIABLE VALUE REDUCED COSTX11 0.000000 400.000000X12 0.000000 57.894737X13 0.000000 400.000000X21 10.000000 0.000000X22 0.000000 239.473679X23 5.000000 0.000000X31 0.000000 0.000000X32 12.947369 0.000000X33 3.000000 0.000000X41

18、 0.000000 650.000000X42 3.052632 0.000000X43 0.000000 650.000000實(shí)際上，不妨將所得最優(yōu)解作四舍五入， 29結(jié)果為 貨物2裝入前倉10噸、裝入后倉5噸； 貨物3裝入中倉13噸、裝入后倉3噸； 貨物4裝入中倉3噸， 最大利潤(rùn)約121516元。 評(píng)注 初步看來，本例與運(yùn)輸問題類似，似乎可以把4種貨物看成4個(gè)供應(yīng)點(diǎn)，3個(gè)貨艙看成3個(gè)需求點(diǎn)（或者反過來，把貨艙看成供應(yīng)點(diǎn)，貨物看成需求點(diǎn)）。但是，這里對(duì)供需量的限制包括兩個(gè)方面：重量限制和空間限制，且有裝載均勻要求，因此它只能看成是運(yùn)輸問題的一種變形和擴(kuò)展。 30 三、原油采購與加工 問題 某

19、公司用兩種原油（A和B）混合加工成兩種汽油（甲和乙）。甲、乙兩種汽油含原油A的最低比例分別為50%和60%，每噸售價(jià)分別為4800元和5600元。該公司現(xiàn)有原油A和B的庫存量分別為500噸和1000噸，還可以從市場(chǎng)上買到不超過1500噸的原油A。原油A的市場(chǎng)價(jià)為：購買量不超過500噸時(shí)的單價(jià)為10000元/噸；購買量超過500噸但不超過1000噸時(shí)，超過500噸的部分8000元/噸；購買量超過1000噸時(shí)，超過1000噸的部分6000元/噸。該公司應(yīng)如何安排原油的采購和加工？31問題分析 安排原油采購、加工的目標(biāo)只能是利潤(rùn)最大， 題目中給出的是兩種汽油的售價(jià)和原油A的采購價(jià)，利潤(rùn)為銷售汽油的收

20、入與購買原油A的支出之差。 這里的難點(diǎn)在于原油A的采購價(jià)與購買量的關(guān)系比較復(fù)雜，是分段函數(shù)關(guān)系，能否及如何用線性規(guī)劃、整數(shù)規(guī)劃模型加以處理是關(guān)鍵所在。模型建立 設(shè)原油A的購買量為x， 采購的支出C(x)可表為如下的分段線性函數(shù)（價(jià)格為千元/噸）：)9()15001000(63000)1000500(81000)5000(10)(xxxxxxxc32設(shè)原油A用于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為，和1211xx 設(shè)原油B用于生產(chǎn)甲、乙兩種汽油的數(shù)量分別為，和2221xx則總的收入為 )(6 . 5)(8 . 422122111xxxx于是本例的目標(biāo)函數(shù)利潤(rùn)為）（ 10)()(6 . 5)(8 . 4

21、22122111xcxxxxzMax 約束條件包括加工兩種汽油用的原油A、原油B庫存量的限制，和原油A購買量的限制，以及兩種汽油含原油A的比例限制，它們表示為）（ 115001211xxx）（ 1210002221 xx）（ 131500 x33）（ 145 . 0211111 xxx）（ 156 . 0221212 xxx）（ 160,22211211xxxxx 由于（9）式中的C(x)不是線性函數(shù)，（9）（16）給出的是一個(gè)非線性規(guī)則。而且，對(duì)于這樣用分段函數(shù)定義的C(x)，一般的非線性規(guī)劃軟件也難以輸入和求解。 能不能想辦法將該模型化簡(jiǎn)，從而用現(xiàn)成的軟件求解呢？ 34模型求解 下面介紹3

22、種解法。 第1種解法 一個(gè)自然的想法是將原油A的采購量x分解為三個(gè)量， 321,xxx 分別表示以價(jià)格10千元/噸、8千元/噸、6千元/噸采購的原油A的噸數(shù)， 總支出為 3216810)(xxxxc)17(321xxxx這時(shí)目標(biāo)函數(shù)（10）變?yōu)榫€性函數(shù)：)6810()(6 . 5)(8 . 432122122111xxxxxxxzMax)18(35應(yīng)該注意到，只有當(dāng)以10千元/噸的價(jià)格購買5001x噸時(shí)，才能以8千元/噸的價(jià)格購買)0(22xx這個(gè)條件可以表示為)19(0)500(21xx同理，只有當(dāng)以8千元/噸的價(jià)格購買5002x噸時(shí)，才能以6千元/噸的價(jià)格購買)0(33xx，于是)20(0

23、)500(32xx321,xxx的取值范圍是)21(500,0321xxx 由于有非線性約束（19），（20），（11）（21）構(gòu)成非線性規(guī)劃模型。將該模型輸入LINGO軟件如下： 36Model：Max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*02-6*x3；x11+x12x+500；x21+x220；0.4*x12-0.6*x220；x=x1+x2+x3；(x1-500)*x2=0；(x2-500)*x3=0；x1500；x2500；x30；x110；x120；x210；x220；x10；x20；x30；end37 注：程序以“Model：”開始，每

24、行最后加“；”，并以“end”結(jié)束；非負(fù)約束可以省略；乘號(hào)*不能省略，式中可有括號(hào)，右端可有數(shù)學(xué)符號(hào)。 將文件存儲(chǔ)并命名后，選擇菜單“Solve”，運(yùn)行該程序得到：Objective value: 4800.000 Variable Value Reduced Cost X11 500.0000 0.0000000E+00 X21 500.0000 0.0000000E+00 X12 0.0000000E+00 0.0000000E+00 X22 0.0000000E+00 0.0000000E+00 X1 0.1021405E-13 10.00000 X2 0.0000000E+00 8.0

25、00000 X3 0.0000000E+00 6.000000 X 0.0000000E+00 0.0000000E+0038 最優(yōu)解是用庫存的500噸原油A、500噸原油B生產(chǎn)1000噸汽油甲，不購買新的原油A，利潤(rùn)為4800000元。 但是LINGO得到的以上結(jié)果只是一個(gè)局部最優(yōu)解，還能得到更好的解嗎？第2種解法 引入0-1變量將（19）和（20）轉(zhuǎn)化為線性約束。 1, 1, 1321yyy令 分別表示以10千元/噸、8千元/噸、6千元/噸的價(jià)格采購原油A， 則約束（19）和（20） 可以替換為)19(0)500(21xx)20(0)500(32xx39）（ 22500500112yxy）

26、（ 23500500223yxy）（ 2450033yx ）（或2510,321yyy（11）（18），（21）（25）構(gòu)成整數(shù)規(guī)劃模型， 將它輸入LINGO軟件如下： 40Max 4.8x11+4.8x21+5.6x12+5.6x22-10 x1-8x2-6x3Stx-x1-x2-x3=0 x11+x12-x500 x21+x2200.4x12-0.6x220 x1-500y10 x2-500y20 x3-500y30 x2-500y30endint y1int y2int y341運(yùn)行該程序得到：OBJECTIVE FUNCTION VALUE1) 5000.000VAIABLE VALU

27、E REDUCED COST Y1 1.000000 0.000000 Y2 1.000000 2200.000000 Y3 1.000000 1200.000000 X11 0.000000 0.800000 X21 0.000000 0.800000 X12 1500.000000 0.000000 X22 1000.000000 0.000000 X1 500.000000 0.000000 X2 500.000000 0.000000 X3 0.000000 0.400000 X 1000.000000 0.00000042 最優(yōu)解是購買1000噸原油A，與庫存的500噸原油A和100

28、0噸原油B一起，共生產(chǎn)2500噸汽油乙，利潤(rùn)為5000000元，高于非線性規(guī)劃模型得到的結(jié)果。第3種解法 直接處理分段線性函數(shù)C(x)， )9()15001000(63000)1000500(81000)5000(10)(xxxxxxxc（9）式表示的C(x)如圖2。43記x軸上的分點(diǎn)為1500,1000,500, 04321bbbb。 當(dāng)x在第1個(gè)小區(qū)間,21bb 0, 1,21212211zzzzbzbzx記因?yàn)镃(x)在,21bb是線性的， 所以 )()()(2211bczbczxc44同樣，當(dāng)x在第2個(gè)小區(qū)間,32bb時(shí)， 0, 1,32323322zzzzbzbzx)()()(332

29、2bczbczxc當(dāng)x在第3個(gè)小區(qū)間,43bb時(shí)， 0, 1,43434433zzzzbzbzx)()()(4433bczbczxc為了表示x在哪個(gè)小區(qū)間，引入0-1變量)3, 2, 1( kyk， 當(dāng)x在第k個(gè)小區(qū)間時(shí)，1ky 否則，0ky。 這樣，3214321,yyyzzzz應(yīng)滿足45）（ 26,3432321211yzyyzyyzyz）（ 27)4, 3, 2, 1(0, 14321kzzzzzk）（或2810, 1321321yyyyyy此時(shí)x和C(x)可以統(tǒng)一地表示為）（ 291500100050043244332211zzzbzbzbzbzx)()()()()(44332211b

30、czbczbczbczxc）（ 301200090005000432zzz （ 10）（18），（26）（30）也構(gòu)成一個(gè)整數(shù)規(guī)劃模型， 將它輸入LINDO軟件求解，得到的結(jié)果與第2種解法相同。46評(píng)注 這個(gè)問題的關(guān)鍵是處理分段線性函數(shù)， 第3種解法更具一般性，其做法如下： 設(shè)一個(gè)n段線性函數(shù)f(x)的分點(diǎn)為11nnbbb引入kz將x和f(x)表示為11nkkkbzx11)()(nkkkbfzxfkz和0-1變量ky滿足nnnnnyzyyzyyzyz1121211,10, 121或knyyyy) 1, 2, 1(0, 1121nkzzzzkn47 生產(chǎn)中常會(huì)遇到通過切割、剪裁、沖壓等手段，將原

31、材料加工成所需尺寸這種工藝過程，稱為原料下料問題。按照進(jìn)一步的工藝要求，確定下料方案，使用料最省，或利潤(rùn)最大，是典型的優(yōu)化問題。下面通過兩個(gè)實(shí)例討論用數(shù)學(xué)規(guī)劃模型解決這類問題的方法。48四、鋼管下料問題 某鋼管零售商從鋼管廠進(jìn)貨，將鋼管按照顧客的要求切割后售出，從鋼管廠進(jìn)貨時(shí)得到的原料鋼管都是19m。（1）現(xiàn)有一客戶需要50根4 m、20根6 m和15根8 m的鋼管，應(yīng)如何下料最節(jié)?。浚?）零售商如果采用的不同切割模式太多，將會(huì)導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外，該客戶除需要（1）中的三種鋼管外，還需要10根5 m的鋼管。應(yīng)如何下

32、料最節(jié)省。問題（1）的求解問題分析 首先，應(yīng)當(dāng)確定哪些切割模式是可行的。 49 所謂一個(gè)切割模式，是指按照客戶需要在原料鋼管上安排切割的一種組合。 例如：我們可以將19 m的鋼管切割成3根4 m的鋼管，余料為7 m；或者將19 m的鋼管切割成4 m、6 m和8 m的鋼管各1根，余料為1 m。 顯然，可行的切割模式是很多的。其次，應(yīng)當(dāng)確定哪些切割模式是合理的。 通常假設(shè)一個(gè)合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸。 例如：將19 m的鋼管切割成3根4 m的鋼管，余料為7 m，可進(jìn)一步將7m的余料切割成4m 鋼管（余料為3 m），或者將7 m的余料切割成6 m鋼管（余料為1 m

33、）。 50 在這種合理性假設(shè)下，切割模式一共有7種，如表9所示。4 m鋼管根數(shù)6 m鋼管根數(shù)8 m鋼管根數(shù)余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023 問題化為在滿足客戶需要的條件下，按照哪些種合理的模式，切割多少根原料鋼管，最為節(jié)省。 而所謂節(jié)省，可以有兩種標(biāo)準(zhǔn)： 51一是切割后剩余的總余料量最小， 二是切割原料鋼管的總根數(shù)最小。 下面將對(duì)這兩個(gè)目標(biāo)分別討論。模型建立決策變量 ix表示按照第i種模式（7 , 2, 1i ）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)整數(shù)。 決策目標(biāo) 以切割后剩余的總余料量最小為目標(biāo)，則由表9可得 )

34、 1 (333376543211xxxxxxxZMin以切割原料鋼管的總根數(shù)最少為目標(biāo)，則有)2(76543212xxxxxxxZMin524 m鋼管根數(shù)6 m鋼管根數(shù)8 m鋼管根數(shù)余料（m）模式14003模式23101模式32013模式41203模式51111模式60301模式70023約束條件 為滿足客戶的需求，按照表9應(yīng)有 )3(5023454321xxxxx)4(20326542xxxx)5(152753xxx模型求解53 1將（1），（3），（4），（5）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO如下： Min 3x1+x2+3x3+3x4+x5+x6+3x7s.t. 4x

35、1+3x2+2x3+x4+x5=50 x2+2x4+x5+3x6=20 x3+x5+2x7=15endgin7求解可以得到最優(yōu)解如下：54OBJECTIVE FUNCTION VALUE1) 27.00000VARIABLE VALUE REDUCED COST X1 0.000000 3.000000 X2 12.000000 1.000000 X3 0.000000 3.000000 X4 0.000000 3.000000 X5 15.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 3.000000 即按照模式2切割12根原料鋼管，按照模

36、式5切割15根原料鋼管，共27根，總余料量為27m。 顯然，在總余料量最小的目標(biāo)下，最優(yōu)解將是使用余料盡可能小的切割模式（模式2和5的余料為1 m），這會(huì)導(dǎo)致切割原料鋼管的總根數(shù)較多。55 2將（2）（5）構(gòu)成的整數(shù)線性規(guī)劃模型（加上整數(shù)約束）輸入LINDO求解，可以得到最優(yōu)解如下： OBJECTIVE FUNCTION VALUE1） 25.00000VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 15.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 5.0000

37、00 1.000000 X6 0.000000 1.000000 X7 5.000000 1.000000 即按照模式2切割15根原料鋼管、按模式5切割5根、按模式7切割5根、共25根，可算出總余料量為35 m。 與上面得到的結(jié)果相比，總余料量增加了8 m，但是所用的原料鋼管的總根數(shù)減少了2根。 在余料沒有用途情況下，通常選擇總根數(shù)最小為目標(biāo)。 56問題（2）的求解問題（2）：零售商如果采用的不同切割模式太多，將會(huì)導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定采用的不同切割模式不能超過3種。此外，該客戶除需要（1）中的三種鋼管外，還需要10根5 m的鋼管。應(yīng)如何下料最節(jié)省。問題

38、分析 按照（1）的思路，可以通過枚舉法首先確定哪些切割模式是可行的。但由于需求的鋼管規(guī)格增加到4種，所以枚舉法的工作量較大。 下面介紹的整數(shù)非線性規(guī)劃模型，可以同時(shí)確定切割模式和切割計(jì)劃，是帶有普遍性的方法。 57 同（1）類似，一個(gè)合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸（本題中為4 m），切割計(jì)劃中只使用合理的切割模式，而由于本題中參數(shù)都是整數(shù)，所以合理的切割模式的余量不能大于3 m。 此外，這里我們僅選擇總根數(shù)最小為目標(biāo)進(jìn)行求解。模型建立決策變量 由于不同切割模式不能超過3種， 可以用ix表示按照第i種模式（3, 2, 1i ）切割的原料鋼管的根數(shù)，顯然它們應(yīng)當(dāng)是非負(fù)

39、整數(shù)。 58 設(shè)所使用的第i種切割模式下每根原料鋼管生產(chǎn)4 m，5 m，6 m和8 m的鋼管數(shù)量分別為iiiirrrr4321,（非負(fù)整數(shù)）。 決策目標(biāo) 切割原料鋼管的總根數(shù)最小，目標(biāo)為)6(321xxxMin約束條件 為滿足客戶的需求，應(yīng)有)7(50313212111xrxrxr)8(10323222121xrxrxr)9(20333232131xrxrxr)10rxrxr59 每一種切割模式必須可行、合理，所以每根原料鋼管的成品量不能超過19m，也不能少于16 m（余量不能大于3 m），于是)11(1986541641312111rrrr)12(198654164

40、2322212rrrr)13(1986541643332313rrrr模型求解 在（7）（10）式中出現(xiàn)決策變量的乘積，是一個(gè)整數(shù)非線性規(guī)劃模型，雖然用LINGO軟件可以直接求解，但我們發(fā)現(xiàn)運(yùn)行很長(zhǎng)時(shí)間也難以得到最優(yōu)解。 為了減少運(yùn)行時(shí)間，可以增加一些顯然的約束條件，從而縮小可行解的搜索范圍。 60 例如，由于3種切割模式的排列順序是無關(guān)緊要的，所以不妨增加以下約束)14(321xxx 又例如，我們注意到所需原料鋼管的總根數(shù)有著明顯的上界和下界。 首先，無論如何，原料鋼管的總根數(shù)不可能少于19158206105504根即至少需26根。 其次，考慮一種非常特殊的生產(chǎn)計(jì)劃： 第一種切割模式下只生產(chǎn)

41、4m鋼管，一根原料鋼管切割成4根4 m鋼管，為滿足50根4 m鋼管的需求，需要13根原料鋼管； 61 第二種切割模式下只生產(chǎn)5 m、6 m鋼管，一根原料鋼管切割成1根5 m鋼管和2根6 m鋼管，為滿足10根5 m和20根6 m鋼管的需求，需要10根原料鋼管； 第三種切割模式下只生產(chǎn)8 m鋼管，一根原料鋼管切割成2根8 m鋼管，為滿足15根8 m鋼管的需求，需要8根原料鋼管。 于是滿足要求的這種生產(chǎn)計(jì)劃共需13+10+8=31根原料鋼管，這就得到了最優(yōu)解的一個(gè)上界。 所以可增加以下約束)15(3126321xxx將（6）（15）構(gòu)成的模型輸入LINGO如下：62model：min=x1+x2+x

42、3；x1*r11+x2*r12+x3*r13=50；x1*r21+x2*r22+x3*r23=10；x1*r31+x2*r32+x3*r33=20；x1*r41+x2*r42+x3*r43=15；4*r11+5*r21+6*r31+8*r41=19；4*r12+5*r22+6*r32+8*r42=19；4*r13+5*r23+6*r33+8*r43=16；4*r12+5*r22+6*r32+8*r42=16；4*r13+5*r23+6*r33+8*r43=16；x1+x2+x3=26；x1+x2+x3=x2；x2=x3；gin(x1) ；gin(x2) ；gin(x3) ；gin(r11) ；

43、gin(r12) ；gin(r13) ；gin(r21) ；gin(r22) ；gin(r23) ；gin(r31) ；gin(r32) ；gin(r33) ；gin(r41) ；gin(r42) ；gin(r43) ；end63 注：LINGO軟件用于求解非線性規(guī)劃（包括含有整數(shù)變量的），輸入總是以“model：”開始，以“end”結(jié)束；中間的語句必須以“；”分開。約束中“gin(x1)”表示x1為整數(shù)，其他類似（如果要表示x1為0-1整數(shù)，應(yīng)該用“int(x1)”）。在LINGO8.0版本中，缺省設(shè)置假定所有變量非負(fù)，所以上面的輸入中沒有關(guān)于變量非負(fù)的顯式約束。經(jīng)過運(yùn)行（一般需要幾分鐘），

44、得到輸出如下：64Local optimal solution found at iteration： 12211Objective value： 28.00000 Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.00000 1.000000 R11 3.00000 0.000000 R12 2.00000 0.000000 R21 0.00000 0.000000 R22 1.00000 0.000000 R31 1.00000 0.000000 R32 1.00000 0.000000 R

45、33 0.00000 0.000000 R41 0.00000 0.000000 R42 0.00000 0.000000 R43 2.00000 0.00000065 即按照模式1，2，3分別切割10，10，8根原料鋼管，使用原料鋼管總根數(shù)為28根， 第一種切割模式下一根原料鋼管切割成3根4m鋼管和1根6 m鋼管； 第二種切割模式下一根原料鋼管切割成2根4 m鋼管、1根5 m鋼管和1根6 m鋼管； 第三種切割模式下一根原料鋼管切割成2根8 m鋼管。66五、 易拉罐下料 問題 某公司采用一套沖壓設(shè)備生產(chǎn)一種罐裝飲料的易拉罐，這種易拉罐是用鍍錫板沖壓制成的。易拉罐為圓柱形，包括罐身、上蓋和下底，

46、罐身高10cm，上蓋和下底的直徑均為5cm。該公司使用兩種不同規(guī)格的鍍錫板原料：規(guī)格1的鍍錫板為正方形，邊長(zhǎng)24cm；規(guī)格2的鍍錫板為長(zhǎng)方形，長(zhǎng)、寬分別為32cm和28cm。由于生產(chǎn)設(shè)備和生產(chǎn)工藝的限制，對(duì)于規(guī)格1的鍍錫板原料，只可以按照?qǐng)D3中的模式1、模式2或模式3進(jìn)行沖壓；對(duì)于規(guī)格2的鍍錫板原料只能按照模式4進(jìn)行沖壓。使用模式1、模式2、模式3、模式4進(jìn)行每次沖壓所需要的時(shí)間分別為1.5s、2s、1s、3s。6768 該工廠每周工作40小時(shí)，每周可供使用的規(guī)格1、規(guī)格2的鍍錫板原料分別為5萬張和2萬張。目前每只易拉罐的利潤(rùn)為0.10元，原料余料損失為0.001元/厘米2（如果周末有罐身、上

47、蓋或下底不能配套組裝成易拉罐出售，也看作是原料余料損失）。 問工廠應(yīng)如何安排每周的生產(chǎn)？問題分析 與鋼管下料問題不同的是，這里的切割模式已經(jīng)確定，只需計(jì)算各種模式下的余料損失。 已知上蓋和下底的直徑d=5cm， 可得其面積為6 .1942 dscm2， 周長(zhǎng)為7 .15dLcm； 69已知罐身高h(yuǎn)=10cm，可得其面積為 21 .157 cmLhS罐于是模式1下的余料損失為229 .2221024cmSs罐 同理計(jì)算其它模式下的余料損失，并可將4種沖壓模式的特征歸納，如表10。罐身個(gè)數(shù)底、蓋個(gè)數(shù)余料損失（cm2）沖壓時(shí)間（s）模式1110222.61.5模式224183.32模式3016261

48、.81模式445169.5370 問題的目標(biāo)顯然應(yīng)是易拉罐的利潤(rùn)扣除原料余料損失后的凈利潤(rùn)最大，約束條件除每周工作時(shí)間和原料數(shù)量外，還要考慮罐身和底、蓋的配套組裝。模型建立決策變量 ix表示按照第i種模式的沖壓次數(shù)（4, 3, 2, 1i）， 1y表示一周生產(chǎn)的易拉罐個(gè)數(shù)。 為計(jì)算不能配套組裝的罐身和底、蓋造成的原料損失， 2y表示不配套的罐身個(gè)數(shù)， 3y表示不配套的底、蓋個(gè)數(shù)。 雖然實(shí)際上這些量應(yīng)該是整數(shù)。但是由于生產(chǎn)量相當(dāng)大，可以把它們看成是實(shí)數(shù)，從而用線性規(guī)劃模型處理。 71決策目標(biāo) 假設(shè)每周生產(chǎn)的易拉罐能夠全部售出，公司每周的銷售利潤(rùn)是11 . 0 y。 原料余料損失包括兩部分： 4種

49、沖壓模式下的余料損失和不配套的罐身和底、蓋造成的原料損失。 按照前面的計(jì)算及表10的結(jié)果， 罐身個(gè)數(shù)底、蓋個(gè)數(shù)余料損失（cm2）沖壓時(shí)間（s）模式1110222.61.5模式224183.32模式3016261.81模式445169.53總損失為 72總損失為 )6 .191 .1575 .1698 .2613 .1836 .222(001. 0324321yyxxxx決策目標(biāo)為 )6 .191 .1575 .1698 .2613 .1836 .222(001. 01 . 03243211yyxxxxyMax約束條件時(shí)間約束： 每周工作時(shí)間不超過40小時(shí)=144000s，由表2最后一列得）（1

50、7144000325 . 14321xxxx原料約束： 每周可供使用的規(guī)格1、規(guī)格2的鍍錫板原料分別為50000張和20000張， ）（1673）（ 1850000321xxx）（ 19200004x配套約束： 由表2一周生產(chǎn)的罐身個(gè)數(shù)為42142xxx一周生產(chǎn)的底、蓋個(gè)數(shù)為4321516410 xxxx， 因?yàn)閼?yīng)盡可能將它們配套組裝成易拉罐銷售。 ）（202/ )516410(,42min43214211xxxxxxxy這時(shí)不配套的罐身個(gè)數(shù)，和不配套的底、蓋個(gè)數(shù)應(yīng)為）（214214212yxxxy）（222516410143213yxxxxy（16）（22）就是我們得到的模型， 74）（20

51、2/ )516410(,42min43214211xxxxxxxy 其中（20）是一個(gè)非線性關(guān)系，不易直接處理，但是它可以等價(jià)為以下兩個(gè)線性不等式）（23424211xxxy）（242)516410(43211xxxxy模型求解 將模型（16）（19）和（21）（24）輸入LINDO，求解時(shí)LINDO發(fā)出警告信息： 模型中數(shù)據(jù)之間的數(shù)量級(jí)差別太大，建議進(jìn)行預(yù)處理，縮小數(shù)據(jù)之間的差別。 實(shí)際上，約束（17）（19）中右端項(xiàng)的數(shù)值過大（與左端的系數(shù)相比較），LINDO在計(jì)算中容易中產(chǎn)生比較大的誤差，所以出現(xiàn)此警告信息。 75 為了解決這一問題，可以將所有決策變量擴(kuò)大10000倍（相當(dāng)于iiyx、以

52、萬次為單位）。 此時(shí)，目標(biāo)（16）可以保持不變（記住得到的結(jié)果單位為萬元就可以了） )6 .191 .1575 .1698 .2613 .1836 .222(001. 01 . 03243211yyxxxxyMax）（ 16而約束（17）（19）改為）（254 .14325 . 14321xxxx）（265321xxx）（2724x將模型（16）和（21）（27）輸入LINDO求解得到：76OBJECTIVE FUNCTION VALUE1) 0.4298337VARIABLE VALUE REDUCED COSTY1 16.025000 0.000000X1 0.000000 0.00005

53、0X2 4.012500 0.000000X3 0.375000 0.000000X4 2.000000 0.000000Y2 0.000000 0.223331Y3 0.000000 0.036484 即模式1不使用，模式2使用40125次，模式3使用3750次，模式4使用20000次，可生產(chǎn)易拉罐160250個(gè)，罐身和底、蓋均無剩余，凈利潤(rùn)為4298元。77 評(píng)注 下料問題的建模主要有兩部分組成，一是確定下料模式，二是構(gòu)造優(yōu)化模型。確定下料模式尚無通用的方法，對(duì)于鋼管下料這樣的一維問題，當(dāng)需要下料的規(guī)格不太多時(shí)，可以枚舉出下料模式，建立整數(shù)線必規(guī)劃模型；否則就要構(gòu)造整數(shù)非線性規(guī)劃模型，而這

54、種模型求解比較困難，本節(jié)介紹的增加約束條件的方法是將原來的可行域“割去”一部分，但要保證剩下的可行域中仍存在原問題的最優(yōu)解。而像易拉罐下料這樣的二維問題，就要復(fù)雜多了，讀者不妨試一下，看看還有沒有比圖3給出的更好的模式。至于構(gòu)造優(yōu)化模型，則要根據(jù)問題的要求和限制具體處理，其中應(yīng)特別注意配套組裝的情況。78六：平板車的優(yōu)化裝載（MCM88B) 問題：有7種規(guī)格的包裝箱要裝到兩輛平板車上去，包裝箱的寬和高是一樣的，但厚度t及重量w是不同的，下表給出了每種包裝箱的厚度、重量以及數(shù)量7654321ccccccc包包裝裝箱箱類類型型t（厘米） 48 52 61 72 48 52 64w（噸） 2 3 1

55、 0.5 4 2 1 件數(shù) 8 7 9 6 6 4 8 每輛平板車有10.2米長(zhǎng)的地方可用來裝包裝箱（象面包片那樣），載重為40噸。 79 由于當(dāng)?shù)刎涍\(yùn)的限制，對(duì), ,類的包裝箱的總數(shù)有一個(gè)特別的限制： 5c6c7c 這類箱子所占的空間（厚度）不能超過302.7厘米，試把包裝箱裝到平板車上去，使得浪費(fèi)的空間最小。 解：設(shè) 表示裝到平板車j(j=1,2)上的 型包裝箱的個(gè)數(shù)(1i7)； ijxic表示類型為 的包裝箱的件數(shù)； iNic表示類型為 的包裝箱的重量； iWic表示類型為 的包裝箱的厚度；itic S表示剩余空間。 所以使平板車上剩下的空間最小轉(zhuǎn)化為如下整數(shù)規(guī)劃模型： 80717121

56、)1020()1020(miniiiiiixtxtS7121)(2040iiiixxt為整數(shù)，為整數(shù)，ijijxxts, 0.7111020iiixt（平板車1的長(zhǎng)度限制）7121020iiixt（平板車2的長(zhǎng)度限制） 71140000iiixw（平板車1的載重量限制）8171240000iiixw（平板車2的載重量限制） iiiNxx21（ 型包裝箱的件數(shù)限制） ic7 .302)()()(727176261652515xxtxxtxxt（對(duì)三種型號(hào) 箱長(zhǎng)度的特別限制） 765,ccc思考：上面的限制是否可理解為一輛平板車的限制？目前，求解整數(shù)規(guī)劃模型常用方法有： (1)割平面法； (2)分

57、枝界限法。它們都是建立在線性規(guī)劃求解的單純形法基礎(chǔ)上的。 82 如上例，用分枝定界法即可得35個(gè)不同的最優(yōu)解，使沒有利用的空間為0.6cm。 下面給出幾組最優(yōu)解： 1 2 3 4 5 6 7 1 2 3 4 5 6 7 4 2 9 1 2 0 0 4 5 0 5 1 3 0 4 2 5 3 3 1 0 4 5 4 3 0 2 0 車1 車2 4 3 5 3 3 0 0 4 4 4 3 0 3 083七：一個(gè)飛行管理問題（95全國(guó)數(shù)學(xué)建模競(jìng)賽A題） 問題：在約10000米高空的某邊長(zhǎng)160公里的正方形區(qū)域內(nèi)，經(jīng)常有若干架飛機(jī)作水平飛行，區(qū)域內(nèi)每架飛機(jī)的位置和速度向量均由計(jì)算機(jī)記錄其數(shù)據(jù)，以便進(jìn)行

58、飛行管理。當(dāng)一架欲進(jìn)入該區(qū)域的飛機(jī)到達(dá)區(qū)域邊緣時(shí)，記錄其數(shù)據(jù)后，要立即計(jì)算并判斷是否會(huì)與區(qū)域內(nèi)的飛機(jī)發(fā)生碰撞。如果會(huì)碰撞，則應(yīng)計(jì)算如何調(diào)整各架（包括新進(jìn)入的）飛機(jī)飛行的方向角，以避免碰撞。現(xiàn)假定條件如下：1)不碰撞的標(biāo)準(zhǔn)為任意兩架飛機(jī)的距離大于8公里； 2)飛機(jī)飛行方向角調(diào)整幅度不超過30度； 3)所有飛機(jī)飛行速度均為每小時(shí)800公里； 845)最多需考慮6架飛機(jī)； 6)不必考慮飛機(jī)離開此區(qū)域后的狀況。 請(qǐng)你對(duì)這個(gè)避免碰撞的飛行管理問題建立數(shù)學(xué)模型。列出計(jì)算步驟，用以下數(shù)據(jù)進(jìn)行計(jì)算（方向角誤差不超過0.01度）。要求飛機(jī)飛行方向角調(diào)整的幅度盡量小。 設(shè)該區(qū)域4個(gè)頂點(diǎn)的坐標(biāo)為 (0,0),(16

59、0,0),(160,160),(0,160) 記錄數(shù)據(jù)為： 4)進(jìn)入該區(qū)域飛機(jī)在到達(dá)區(qū)域邊緣時(shí)，與區(qū)域內(nèi)飛機(jī)的距離應(yīng)在60公里以上； 85飛機(jī)編號(hào) 橫坐標(biāo)X 縱坐標(biāo)Y 方向角（度） 1 130 140 243 2 85 85 236 3 150 155 220.5 4 145 50 139 5 130 150 230 新進(jìn)入 0 0 52注：方向角指飛行方向與X軸正向的夾角。試根據(jù)實(shí)際應(yīng)用背景對(duì)你的模型進(jìn)行平價(jià)與推廣。本問題可歸結(jié)為非線性規(guī)劃模型求解： 86設(shè)六架飛機(jī)在調(diào)整前的方向角為 ， i 調(diào)整后的方向角為 iii (i=1,2,6) 任意兩架飛機(jī)在區(qū)域內(nèi)的最短距離為 ， ),(jiijd

60、 則問題的非線性規(guī)劃模型如下 61minii 8),(jjiiijd jiji6,1030i 注：也可用 或 作為目標(biāo) 261ii ii 61max87 5.3 動(dòng)態(tài)規(guī)劃模型例8：最短線路問題0A6A 問題：現(xiàn)選擇一條從 到 的鋪管線路，使總距離最短？ 若用窮舉法要算23222148種不同線路，比較這48種結(jié)果即可得出，但當(dāng)段數(shù)增加，且各段選擇也增加時(shí)，窮舉法將變得非常龐大，以至利用計(jì)算機(jī)都十分困難。 88下面用動(dòng)態(tài)規(guī)劃的方法計(jì)算最短線路問題的特性： 如果最短線路在第k站通過點(diǎn) ，則這一線路在由 出發(fā)到達(dá)終點(diǎn)的那一部分線路，對(duì)于從 點(diǎn)到達(dá)終點(diǎn)的所有可能選擇的不同線路來說，必定也是距離最短的。（