第三章 運(yùn)輸問題

1、運(yùn)籌學(xué)運(yùn)籌學(xué) 趙明霞趙明霞 山西大學(xué)經(jīng)濟(jì)與管理學(xué)院山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 2021-6-202 第三章第三章 運(yùn)輸問題運(yùn)輸問題 1.運(yùn)輸問題的數(shù)學(xué)模型運(yùn)輸問題的數(shù)學(xué)模型 2.表上作業(yè)法表上作業(yè)法 3.應(yīng)用應(yīng)用 2021-6-203 在經(jīng)濟(jì)建設(shè)中，經(jīng)常會(huì)遇到大宗物資中的運(yùn)輸問題如在經(jīng)濟(jì)建設(shè)中，經(jīng)常會(huì)遇到大宗物資中的運(yùn)輸問題如 煤炭、鋼鐵、木材、糧食等物資煤炭、鋼鐵、木材、糧食等物資, ,在全國(guó)有若干生在全國(guó)有若干生 產(chǎn)基地產(chǎn)基地, , 根據(jù)已有的交通網(wǎng)根據(jù)已有的交通網(wǎng), , 應(yīng)如何制定調(diào)運(yùn)方案，應(yīng)如何制定調(diào)運(yùn)方案， 將這些物資運(yùn)到各消費(fèi)地點(diǎn)，使總運(yùn)費(fèi)最小。將這些物資運(yùn)到各消費(fèi)地點(diǎn)，使總運(yùn)費(fèi)最小。

2、 2021-6-204 第一節(jié)第一節(jié) 運(yùn)輸問題運(yùn)輸問題的數(shù)的數(shù)學(xué)模型學(xué)模型 例例1 1：廣東石化公司從三個(gè)石油加工產(chǎn)地進(jìn)購(gòu)石油，銷往四廣東石化公司從三個(gè)石油加工產(chǎn)地進(jìn)購(gòu)石油，銷往四 個(gè)加油站。三個(gè)加工產(chǎn)地的產(chǎn)量分別為：個(gè)加油站。三個(gè)加工產(chǎn)地的產(chǎn)量分別為：1414千噸、千噸、2727千噸千噸 和和1919千噸，四個(gè)加油站的需求量分別為：千噸，四個(gè)加油站的需求量分別為：2222千噸、千噸、1313千噸、千噸、 1212千噸和千噸和1313千噸。已知從各加工產(chǎn)地到各加油站的單位運(yùn)千噸。已知從各加工產(chǎn)地到各加油站的單位運(yùn) 價(jià)如下網(wǎng)絡(luò)圖示（單位：千元價(jià)如下網(wǎng)絡(luò)圖示（單位：千元/ /千噸），問石化公司如何

3、安千噸），問石化公司如何安 排運(yùn)輸方案，使得總排運(yùn)輸方案，使得總？ 分析此問題：分析此問題：產(chǎn)銷平衡問題：總產(chǎn)量產(chǎn)銷平衡問題：總產(chǎn)量 = = 總銷量總銷量。設(shè)設(shè)X Xij ij為從 為從 第第i i個(gè)產(chǎn)地銷往第個(gè)產(chǎn)地銷往第j j個(gè)加油站的銷量，則此問題是一個(gè)線性個(gè)加油站的銷量，則此問題是一個(gè)線性 規(guī)劃問題，規(guī)劃問題，： 2021-6-205 2 3 2 1 3 4 1 A2=27 A3=19 B1=22 B2=13 B3=12 B4=13 A1=14 供應(yīng)量供應(yīng)量 供應(yīng)地供應(yīng)地 運(yùn)價(jià)運(yùn)價(jià) 需求量需求量 需求地需求地 6 7 5 3 8 4 2 7 5 9 10 6 2021-6-206 0 x

4、xxxxxxxxxxx 13xxx 12xxx 13xxx 22xxx 19xxxx 27xxxx 14xxxxs.t. x6x10 x9x5x7x2x4x8x3x5x7x6zmin 343332312423222114131211 342414 332313 322212 312111 34333231 24232221 14131211 343332312423222114131211 供應(yīng)地約束供應(yīng)地約束需求地約束需求地約束 x xij ij0( 0(i i=1,2=1,2，3 3；j j=1,2,3=1,2,3，4 4） 2021-6-207 數(shù)學(xué)語言數(shù)學(xué)語言來描述：來描述： 假設(shè)有假

5、設(shè)有 m m 個(gè)生產(chǎn)地點(diǎn)個(gè)生產(chǎn)地點(diǎn), ,可以供應(yīng)某種物資可以供應(yīng)某種物資( (以后稱為產(chǎn)地以后稱為產(chǎn)地) )， 用用 A Ai i 表示，表示，i i = 1,2, = 1,2, , ,m m；有；有 n n 個(gè)銷售地，個(gè)銷售地， 用用 B Bj j 表示，表示，j j = 1,2, = 1,2, , ,n n；產(chǎn)地的產(chǎn)量和銷售地的銷售量；產(chǎn)地的產(chǎn)量和銷售地的銷售量 分別為分別為 a ai i , , i i = 1,2, = 1,2, , ,m m 和和 b bj j j j = 1,2, = 1,2, , ,n n，從，從 A Ai i 到到 B Bj j 運(yùn)輸單位物資的運(yùn)價(jià)為運(yùn)輸單位物資

6、的運(yùn)價(jià)為 c cij ij ， ，問怎樣編制調(diào)運(yùn)方案才能使問怎樣編制調(diào)運(yùn)方案才能使 總運(yùn)費(fèi)最少？（注意：只研究單一品種物資運(yùn)輸問題）總運(yùn)費(fèi)最少？（注意：只研究單一品種物資運(yùn)輸問題） 為了直觀起見，運(yùn)輸問題常用表格來表示，常用有三種為了直觀起見，運(yùn)輸問題常用表格來表示，常用有三種表格表格: : 2021-6-208 1 1、產(chǎn)銷平衡表、產(chǎn)銷平衡表 產(chǎn)量ai 產(chǎn)地產(chǎn)地 銷地銷地 銷量銷量bi B1 B2 Bn A1 A2 Am b 1 b 2 b n a1 a2 am x 1 1 x 1 2 x 1 n x 2 1 x2 2 x2 n x m 1 xm 2 xm n 產(chǎn)地產(chǎn)地 銷地銷地B 1 B

7、2 B n A1 A2 Am c 1 1 c 1 2 c 1 n c 2 1 c 2 2 c 2 n c m 1 c m 2 c m n 2 2、單位運(yùn)價(jià)表、單位運(yùn)價(jià)表 2021-6-209 銷地銷地 產(chǎn)地產(chǎn)地 B B1 1 B B2 2 B Bn n產(chǎn)量產(chǎn)量 A A1 1 c c11 11 x x11 11 c c12 12 x x12 12 c c1n 1n x x1n 1n a a1 1 A A2 2 c c21 21 x x21 21 c c22 22 x x22 22 c c2n 2n x x2n 2n a a2 2 A Am m c cm m1 1 x xm m1 1 c cm m

8、2 2 x xm m2 2 c cmn mn x xmn mn a am m 銷量銷量b b1 1b b2 2b bn n 3 3、運(yùn)輸表、運(yùn)輸表 2021-6-2010 如果總產(chǎn)量如果總產(chǎn)量= =總銷量總銷量, ,= =即即 a a1 1 + a + a2 2 + + a + + am m = b = b1 1 + b + b2 2 + +b + +bn n 則稱該運(yùn)輸問題為則稱該運(yùn)輸問題為產(chǎn)銷平衡運(yùn)輸問題產(chǎn)銷平衡運(yùn)輸問題；否則，稱產(chǎn)銷不平；否則，稱產(chǎn)銷不平 衡運(yùn)輸問題。我們首先研究產(chǎn)銷平衡問題。衡運(yùn)輸問題。我們首先研究產(chǎn)銷平衡問題。 設(shè)設(shè)從從Ai Ai 到到BjBj的運(yùn)輸量為的運(yùn)輸量為x

9、xij ij, , 總運(yùn)費(fèi)為 總運(yùn)費(fèi)為Z Z。那么，。那么， 產(chǎn)銷平衡的運(yùn)輸問題的產(chǎn)銷平衡的運(yùn)輸問題的數(shù)學(xué)模型數(shù)學(xué)模型是：是： 2021-6-2011 minZ= Cij xij （總運(yùn)費(fèi)極小化）（總運(yùn)費(fèi)極小化） xij = ai i=1,2,m,（產(chǎn)量約束，某一產(chǎn)地運(yùn)（產(chǎn)量約束，某一產(chǎn)地運(yùn) 往各銷地的運(yùn)量之和等于該地產(chǎn)量）往各銷地的運(yùn)量之和等于該地產(chǎn)量） xij = bj j=1,2,n, （銷量約束，各產(chǎn)地運(yùn)往（銷量約束，各產(chǎn)地運(yùn)往 某一銷地的運(yùn)量之和等于該銷地需求量）某一銷地的運(yùn)量之和等于該銷地需求量） xij 0 非負(fù)約束非負(fù)約束 2021-6-2012 系數(shù)矩陣系數(shù)矩陣的結(jié)構(gòu)如下：的

10、結(jié)構(gòu)如下： x11x12x1nx21x22x2n xm1xm2 xmn 1 1 1 1 1 1 1 1 1 111 111 111 A m 行行 n 行行 2021-6-2013 1 1、包含、包含= = ，所以系數(shù)矩陣中線性獨(dú)立的列向量的最大個(gè)數(shù)為（，所以系數(shù)矩陣中線性獨(dú)立的列向量的最大個(gè)數(shù)為（ 該模型有該模型有m m* *n n個(gè)變量個(gè)變量，m+nm+n個(gè)約束個(gè)約束，解中，解中基變量個(gè)數(shù)為基變量個(gè)數(shù)為 （m+n-1m+n-1）個(gè)）個(gè)。（。（ 2 2、在該模型的系數(shù)矩陣中，、在該模型的系數(shù)矩陣中，每列有兩個(gè)元素是每列有兩個(gè)元素是1 1，其余為，其余為0 0。 （2mn2mn個(gè)元素不為個(gè)元素不

11、為0 0） 3 3、在目標(biāo)函數(shù)中，由于系數(shù)、在目標(biāo)函數(shù)中，由于系數(shù)0,0,且目標(biāo)為最小且目標(biāo)為最小, ,因此因此目標(biāo)函數(shù)目標(biāo)函數(shù) 有下界有下界( (不會(huì)是無界解不會(huì)是無界解),),又由于約束方程組一定有可行界（可以又由于約束方程組一定有可行界（可以 證明）證明）, ,故運(yùn)輸問題故運(yùn)輸問題一定有最優(yōu)解一定有最優(yōu)解。 運(yùn)輸模型的特點(diǎn)：運(yùn)輸模型的特點(diǎn)： 2021-6-2014 l 運(yùn)輸問題是一種特殊的線性規(guī)劃問題，理論上運(yùn)輸問題是一種特殊的線性規(guī)劃問題，理論上, ,我們可以我們可以 用單純形法來求解運(yùn)輸問題的解用單純形法來求解運(yùn)輸問題的解, , 如果用單純形法求解，先得如果用單純形法求解，先得 在各

12、約束條件上加入一個(gè)人工變量在各約束條件上加入一個(gè)人工變量( (以便求出初始基可行解以便求出初始基可行解) )。 因此，即使是因此，即使是 m = 3m = 3， n = 4 n = 4 這樣的簡(jiǎn)單問題這樣的簡(jiǎn)單問題, , 變量數(shù)就有變量數(shù)就有 1919個(gè)之多，個(gè)之多，計(jì)算起來非常復(fù)計(jì)算起來非常復(fù)雜雜。 l 由由于運(yùn)輸問題自身的特殊性于運(yùn)輸問題自身的特殊性, ,我們我們使用單純形原理使用單純形原理, ,但不用但不用 單純形單純形法。法。 l 人人們?cè)诜治鲞\(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對(duì)運(yùn)們?cè)诜治鲞\(yùn)輸規(guī)劃系數(shù)矩陣特征的基礎(chǔ)上建立了針對(duì)運(yùn) 輸問題的輸問題的表上作業(yè)法表上作業(yè)法。 2021-6-

13、2015 基本可行解基本可行解 是否最優(yōu)解是否最優(yōu)解結(jié)束結(jié)束 換基 是是 否否 運(yùn)輸問題的求解思路運(yùn)輸問題的求解思路 求解思路：求解思路：這里這里求解運(yùn)輸問題的思想和單純形法完全類求解運(yùn)輸問題的思想和單純形法完全類 似，即首先確定一個(gè)初始基本可行解，然后根據(jù)最優(yōu)性判別似，即首先確定一個(gè)初始基本可行解，然后根據(jù)最優(yōu)性判別 準(zhǔn)則來檢查這個(gè)基本可行解是不是最優(yōu)的。如果是，則計(jì)算準(zhǔn)則來檢查這個(gè)基本可行解是不是最優(yōu)的。如果是，則計(jì)算 結(jié)束；如果不是，則進(jìn)行換基，直至求出最優(yōu)解為止。結(jié)束；如果不是，則進(jìn)行換基，直至求出最優(yōu)解為止。 第二節(jié)第二節(jié) 表上作業(yè)法表上作業(yè)法 2021-6-2016 l計(jì)算步驟計(jì)算

14、步驟： 1 1、按照某種規(guī)則，找出初始基可行解。按照某種規(guī)則，找出初始基可行解。即在即在 (m(m n) n) 產(chǎn)銷平衡表產(chǎn)銷平衡表 上給出上給出m+n-1m+n-1個(gè)有數(shù)字的格個(gè)有數(shù)字的格，且，且行和等于該產(chǎn)地產(chǎn)量，列和等于行和等于該產(chǎn)地產(chǎn)量，列和等于 該銷地銷售量；（該銷地銷售量；（最小元素法、最小元素法、 2 2、檢驗(yàn)是否最優(yōu)。檢驗(yàn)是否最優(yōu)。方法：求各非基變量的檢驗(yàn)數(shù)，即在表上求空方法：求各非基變量的檢驗(yàn)數(shù)，即在表上求空 格的檢驗(yàn)數(shù)，當(dāng)所有格的檢驗(yàn)數(shù)，當(dāng)所有 ij ij 0 0，得到最優(yōu) ，得到最優(yōu)解。如果達(dá)到最優(yōu)解，則解。如果達(dá)到最優(yōu)解，則 停止計(jì)算，否則，轉(zhuǎn)入下一步；（停止計(jì)算，否則

15、，轉(zhuǎn)入下一步；（閉回路法、位勢(shì)法）閉回路法、位勢(shì)法） 3 3、 確定換入變量和換出變量，找出新的基可行解。方法：在表確定換入變量和換出變量，找出新的基可行解。方法：在表 上用閉回路法進(jìn)行調(diào)整。上用閉回路法進(jìn)行調(diào)整。( (閉回路調(diào)整法閉回路調(diào)整法) ) 4 4、重復(fù)（、重復(fù)（2 2）、（）、（3 3）步，直到求得最優(yōu)解為止。）步，直到求得最優(yōu)解為止。 注意：五個(gè)方法注意：五個(gè)方法 2021-6-2017 1 1、最小元素法。、最小元素法?；舅枷耄壕徒?yīng)，即從單位運(yùn)價(jià)表中基本思想：就近供應(yīng)，即從單位運(yùn)價(jià)表中最小最小 的運(yùn)價(jià)開始的運(yùn)價(jià)開始，盡最大可能用完一個(gè)產(chǎn)地的產(chǎn)量，或滿足一個(gè)銷，盡最大可能用

16、完一個(gè)產(chǎn)地的產(chǎn)量，或滿足一個(gè)銷 地的銷量，來確定產(chǎn)銷關(guān)系地的銷量，來確定產(chǎn)銷關(guān)系, ,得到滿足者用線劃去。逐次尋找最得到滿足者用線劃去。逐次尋找最 小元素依次類推小元素依次類推, ,直到給出初始方案為直到給出初始方案為止。止。 一、初始基可行解的確定一、初始基可行解的確定 教材例教材例1 1 2021-6-2018 注意：注意： 1 1、在調(diào)運(yùn)方案中，稱填寫數(shù)字處為、在調(diào)運(yùn)方案中，稱填寫數(shù)字處為有數(shù)字的格有數(shù)字的格，它對(duì)應(yīng)運(yùn)它對(duì)應(yīng)運(yùn) 輸問題解中的輸問題解中的基變量的取值基變量的取值（含填數(shù)字（含填數(shù)字0 0的格），為的格），為m+n-1m+n-1個(gè)個(gè)；稱；稱 不填數(shù)字處為不填數(shù)字處為空格空格，

17、它對(duì)應(yīng)解中它對(duì)應(yīng)解中非基變量非基變量。 2 2、當(dāng)在、當(dāng)在中間中間步驟步驟的未劃去的單位運(yùn)價(jià)表中尋找最小元素時(shí)，的未劃去的單位運(yùn)價(jià)表中尋找最小元素時(shí)， 發(fā)現(xiàn)該元素所在行的剩余產(chǎn)量等于該元素所在列的剩余銷售量。發(fā)現(xiàn)該元素所在行的剩余產(chǎn)量等于該元素所在列的剩余銷售量。 這時(shí)在產(chǎn)銷平衡表相應(yīng)的位置填上一個(gè)數(shù)，而在單位運(yùn)價(jià)表中就這時(shí)在產(chǎn)銷平衡表相應(yīng)的位置填上一個(gè)數(shù)，而在單位運(yùn)價(jià)表中就 要要同時(shí)劃去一行和一列同時(shí)劃去一行和一列。為了使調(diào)運(yùn)方案中有數(shù)字的格仍為。為了使調(diào)運(yùn)方案中有數(shù)字的格仍為（m m + n 1+ n 1）個(gè)，需要在個(gè)，需要在同時(shí)劃去的行或列的任一空格位置添上一同時(shí)劃去的行或列的任一空格位

18、置添上一 個(gè)個(gè)“0”0”，這個(gè)，這個(gè)“0”0”表示該變量是基變量，只不過它取值為表示該變量是基變量，只不過它取值為0 0， 即此時(shí)的調(diào)運(yùn)方案是一個(gè)退化的基可行解。如下例。即此時(shí)的調(diào)運(yùn)方案是一個(gè)退化的基可行解。如下例。 3 3、同時(shí)存在兩個(gè)或兩個(gè)以上相等的最小運(yùn)價(jià)時(shí)，任選其一。、同時(shí)存在兩個(gè)或兩個(gè)以上相等的最小運(yùn)價(jià)時(shí)，任選其一。 2021-6-2019 B1B2B3B4 A153104 A21696 A3201057 銷地銷地 產(chǎn)地產(chǎn)地 B1B2B3B4產(chǎn)量產(chǎn)量 A15049 A2314 A377 銷量銷量3584 2021-6-2020 在這個(gè)例子中，當(dāng)在填入第三數(shù)字的格在這個(gè)例子中，當(dāng)在填入

19、第三數(shù)字的格 ( ( A A1 1, , B B4 4 ) ) 時(shí)時(shí), , 在填入在填入 4 4 之后，恰好之后，恰好產(chǎn)銷平衡產(chǎn)銷平衡，就必須在單位運(yùn)價(jià)表中同時(shí)，就必須在單位運(yùn)價(jià)表中同時(shí) 劃去第一行和第四列。為了使有數(shù)字的格不減少，劃去第一行和第四列。為了使有數(shù)字的格不減少，( ( 有數(shù)字的有數(shù)字的 格的總數(shù)應(yīng)為格的總數(shù)應(yīng)為m + n m + n 1 1個(gè)個(gè) ) )可以在空格可以在空格( ( A A1 1, , B B1 1 ) ) 、 ( ( A A1 1, , B B3 3 ) ) 、 ( ( A A2 2, , B B4 4 ) ) 、( ( A A3 3, , B B4 4 ) )中任

20、選一個(gè)格添加一個(gè)中任選一個(gè)格添加一個(gè) “0”0”；同樣，這個(gè)；同樣，這個(gè)添加的添加的“0”0”格格當(dāng)作當(dāng)作基變量基變量，取值為，取值為0 0。我。我 們這里是在們這里是在 ( ( A A1 1, , B B3 3 ) ) 處填處填0 0（即初始調(diào)運(yùn)方案是一個(gè)（即初始調(diào)運(yùn)方案是一個(gè)退化退化 的基可行解）。的基可行解）。 2021-6-2021 思路：思路： 最小元素法的缺點(diǎn)是，為了節(jié)省一處最小元素法的缺點(diǎn)是，為了節(jié)省一處 的費(fèi)用，有時(shí)造成在其它地方要花多幾倍的運(yùn)費(fèi)。的費(fèi)用，有時(shí)造成在其它地方要花多幾倍的運(yùn)費(fèi)。 伏格爾法考慮到，一產(chǎn)地的產(chǎn)品，假如不能按最小伏格爾法考慮到，一產(chǎn)地的產(chǎn)品，假如不能按最

21、小 運(yùn)費(fèi)就近供應(yīng)，就考慮運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)次小運(yùn)費(fèi)。這就有一個(gè)差額，。這就有一個(gè)差額， 差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加差額越大，說明不能按最小運(yùn)費(fèi)調(diào)運(yùn)時(shí)，運(yùn)費(fèi)增加 就越多。因此，就越多。因此，對(duì)于差額最大處對(duì)于差額最大處 ，就優(yōu)先采用最小，就優(yōu)先采用最小 運(yùn)費(fèi)調(diào)運(yùn)費(fèi)調(diào)運(yùn)。運(yùn)。 2021-6-2022 2021-6-2023 方法特點(diǎn)：解的質(zhì)量比較好，常用作求運(yùn)輸問題的近方法特點(diǎn)：解的質(zhì)量比較好，常用作求運(yùn)輸問題的近 似最優(yōu)解。似最優(yōu)解。一般來說，比用最小元素法所求出的初始解更一般來說，比用最小元素法所求出的初始解更 接近于最優(yōu)解。在產(chǎn)地和銷地?cái)?shù)量不多時(shí)，此法給出的初接近

22、于最優(yōu)解。在產(chǎn)地和銷地?cái)?shù)量不多時(shí)，此法給出的初 始方案有時(shí)就是最優(yōu)方案。始方案有時(shí)就是最優(yōu)方案。 2021-6-2024 按照上述兩種方法按照上述兩種方法所產(chǎn)生的一組變量的取值將滿足下所產(chǎn)生的一組變量的取值將滿足下 面面條件條件： (1)(1)所得的變量均為非負(fù)，且變量總數(shù)恰好為所得的變量均為非負(fù)，且變量總數(shù)恰好為 （m + n m + n 1 1） 個(gè)；個(gè)； (2)(2)所有的約束條件均得到滿足；所有的約束條件均得到滿足； (3) (m + n 1 )(3) (m + n 1 )個(gè)基變量對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立個(gè)基變量對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立 的。（所得的變量不構(gòu)成閉回路）的。（所得的變

23、量不構(gòu)成閉回路） 2021-6-2025 最優(yōu)性檢驗(yàn)就是檢查所得到的方案是不是最優(yōu)方案。檢查最優(yōu)性檢驗(yàn)就是檢查所得到的方案是不是最優(yōu)方案。檢查 的方法與單純形方法中的原理相同，即計(jì)算檢驗(yàn)數(shù)。由于目的方法與單純形方法中的原理相同，即計(jì)算檢驗(yàn)數(shù)。由于目 標(biāo)要求極小，因此，當(dāng)標(biāo)要求極小，因此，當(dāng)所有的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào)所有的檢驗(yàn)數(shù)都大于或等于零時(shí)該調(diào) 運(yùn)方案就是最優(yōu)方案運(yùn)方案就是最優(yōu)方案；否則就不是最優(yōu)，需要進(jìn)行；否則就不是最優(yōu)，需要進(jìn)行調(diào)整。調(diào)整。 1 1、閉回路法、閉回路法 2 2、對(duì)偶變量法、對(duì)偶變量法( (位勢(shì)法位勢(shì)法) ) 二、基可行解的最優(yōu)性檢驗(yàn)二、基可行解的最優(yōu)性檢驗(yàn) 2021

24、-6-2026 1 1）某）某空格空格的閉回路：的閉回路：在調(diào)運(yùn)在調(diào)運(yùn)方案表中，從任一方案表中，從任一空格空格出發(fā)，沿著水出發(fā)，沿著水 平或垂直方向前進(jìn)，遇到平或垂直方向前進(jìn)，遇到適當(dāng)填有數(shù)字的方格適當(dāng)填有數(shù)字的方格才沿前進(jìn)方向才沿前進(jìn)方向9090度度 轉(zhuǎn)彎（轉(zhuǎn)彎（遇到數(shù)字格才允許轉(zhuǎn)，但不是每一數(shù)字格就能轉(zhuǎn)遇到數(shù)字格才允許轉(zhuǎn)，但不是每一數(shù)字格就能轉(zhuǎn)），繼續(xù)），繼續(xù) 行進(jìn)行進(jìn)( (試探法），總能回到原來試探法），總能回到原來空格空格。這個(gè)封閉的曲線稱為閉回路。這個(gè)封閉的曲線稱為閉回路。 頂點(diǎn)由一個(gè)空格與其余為填數(shù)字的格組成。可以證明：頂點(diǎn)由一個(gè)空格與其余為填數(shù)字的格組成?？梢宰C明：每個(gè)空格每個(gè)空

25、格 都唯一存在這樣一條閉回路。都唯一存在這樣一條閉回路。 2 2）若把閉回路的各變量格看作節(jié)點(diǎn)，在表中可以畫出如下形式的）若把閉回路的各變量格看作節(jié)點(diǎn)，在表中可以畫出如下形式的 閉回路：閉回路： （幾種常見形式）（幾種常見形式） 閉回路示意圖閉回路示意圖 1 1、閉回路法（、閉回路法（cycle methodcycle method） 2021-6-2027 3)3)閉回路上一組變量對(duì)應(yīng)約束條件的系數(shù)列向量線性相關(guān)。閉回路上一組變量對(duì)應(yīng)約束條件的系數(shù)列向量線性相關(guān)。 因此，在運(yùn)輸問題的基可行解迭代過程中，不允許出現(xiàn)因此，在運(yùn)輸問題的基可行解迭代過程中，不允許出現(xiàn)全部全部 頂點(diǎn)由填數(shù)字格構(gòu)成的閉

26、回路頂點(diǎn)由填數(shù)字格構(gòu)成的閉回路。 推論：推論：產(chǎn)銷平衡運(yùn)輸問題的產(chǎn)銷平衡運(yùn)輸問題的 m + n -1 m + n -1 個(gè)變量構(gòu)成基變量個(gè)變量構(gòu)成基變量 的充分必要條件是它不含閉的充分必要條件是它不含閉回路。回路。 這個(gè)推論給出了運(yùn)輸問題基本解的重要性質(zhì)，因?yàn)槔盟@個(gè)推論給出了運(yùn)輸問題基本解的重要性質(zhì)，因?yàn)槔盟?來判斷來判斷 m+n-m+n-1 1個(gè)變量是否構(gòu)成基變量比直接判斷這些變量所個(gè)變量是否構(gòu)成基變量比直接判斷這些變量所 對(duì)應(yīng)的系數(shù)列向量組是否線性無關(guān)要簡(jiǎn)單和對(duì)應(yīng)的系數(shù)列向量組是否線性無關(guān)要簡(jiǎn)單和直觀。直觀。 教材例教材例1 1 2021-6-2028 4 4）閉回路計(jì)算檢驗(yàn)數(shù)的方法

27、及經(jīng)濟(jì)解釋）閉回路計(jì)算檢驗(yàn)數(shù)的方法及經(jīng)濟(jì)解釋 如：根據(jù)如：根據(jù)初始方案，產(chǎn)地初始方案，產(chǎn)地 A A2 2 的產(chǎn)品是不運(yùn)往銷地 的產(chǎn)品是不運(yùn)往銷地 B B4 4 的。如 的。如 果現(xiàn)在改變初始方案，把果現(xiàn)在改變初始方案，把 A A2 2 的產(chǎn)品運(yùn)送 的產(chǎn)品運(yùn)送1 1 個(gè)單位給個(gè)單位給 B B4 4 ，那，那 么為了保持產(chǎn)銷平衡，就必須使么為了保持產(chǎn)銷平衡，就必須使 x x14 14 或 或 x x34 34 減少 減少 1 1 個(gè)單位；個(gè)單位； 而如果而如果 x x14 14 減少 減少 1 1 個(gè)單位，第個(gè)單位，第 1 1 行的運(yùn)輸量就必須增加行的運(yùn)輸量就必須增加 1 1 個(gè)單位，例如個(gè)單位，

28、例如 x x13 13 增加 增加 1 1 個(gè)單位，那么為了保持產(chǎn)銷平衡，個(gè)單位，那么為了保持產(chǎn)銷平衡， 就必須使就必須使 x x23 23 減少 減少 1 1 個(gè)個(gè)單位。單位。 這個(gè)過程就是尋找一個(gè)以非基變量這個(gè)過程就是尋找一個(gè)以非基變量 x24 x24 為起始頂點(diǎn)的閉為起始頂點(diǎn)的閉 回路回路 x24 x24 ，x14 x14 ，x13 x13 ，x23 x23 ，這個(gè)閉回路的其他頂，這個(gè)閉回路的其他頂 點(diǎn)均為基變量點(diǎn)均為基變量( (對(duì)應(yīng)著填上數(shù)字的格對(duì)應(yīng)著填上數(shù)字的格) )。容易計(jì)算出上述調(diào)整使。容易計(jì)算出上述調(diào)整使 總的運(yùn)輸費(fèi)用發(fā)生的變化為總的運(yùn)輸費(fèi)用發(fā)生的變化為 8 10 + 3 2

29、8 10 + 3 2 -1 -1 ，即，即總總 的運(yùn)費(fèi)減少的運(yùn)費(fèi)減少 1 1 個(gè)單位，這就說明原始方案不是最優(yōu)方案，可個(gè)單位，這就說明原始方案不是最優(yōu)方案，可 以進(jìn)行調(diào)整以得到更好的方案。以進(jìn)行調(diào)整以得到更好的方案。 2021-6-2029 顯然，當(dāng)顯然，當(dāng)所有非基變量的檢驗(yàn)數(shù)均大于或等于零所有非基變量的檢驗(yàn)數(shù)均大于或等于零時(shí)，調(diào)時(shí)，調(diào) 運(yùn)方案就是最優(yōu)方案，因?yàn)榇藭r(shí)對(duì)現(xiàn)行方案作任何調(diào)整都將運(yùn)方案就是最優(yōu)方案，因?yàn)榇藭r(shí)對(duì)現(xiàn)行方案作任何調(diào)整都將 導(dǎo)致總的運(yùn)輸費(fèi)用增加。導(dǎo)致總的運(yùn)輸費(fèi)用增加。 閉回路法的閉回路法的主要缺點(diǎn)主要缺點(diǎn)是是：用閉回路法求檢驗(yàn)數(shù)時(shí)，需要：用閉回路法求檢驗(yàn)數(shù)時(shí)，需要 給每一空格

30、找一條閉回路。當(dāng)產(chǎn)銷點(diǎn)很多時(shí)，尋找閉回路以給每一空格找一條閉回路。當(dāng)產(chǎn)銷點(diǎn)很多時(shí)，尋找閉回路以 及計(jì)算兩方面都會(huì)產(chǎn)生困難。及計(jì)算兩方面都會(huì)產(chǎn)生困難。 2021-6-2030 2.2.位勢(shì)法（位勢(shì)法（dual variable method,dual variable method,對(duì)偶變量法）對(duì)偶變量法） 2021-6-2031 2021-6-2032 2021-6-2033 2021-6-2034 2021-6-2035 步驟步驟如下如下： step1 step1 從任意從任意基變量（填數(shù)字格）基變量（填數(shù)字格）對(duì)應(yīng)的對(duì)應(yīng)的 c cij ij開始 開始, ,利用公式利用公式 c cij ij

31、=u =ui i+v+vj j 依次找出依次找出(m+n-1)(m+n-1)個(gè)個(gè)u ui i,v,vj j；任意給出一個(gè)；任意給出一個(gè)u ui i或或v vj j 值，值， 推算出其它位勢(shì)值。稱這些推算出其它位勢(shì)值。稱這些u ui i,v,vj j為該基本可行解對(duì)應(yīng)的位勢(shì)；為該基本可行解對(duì)應(yīng)的位勢(shì)； （填數(shù)字格中按填數(shù)字格中按c cij ij=u =ui i+v+vj j確立確立u ui i,v,vj j ，方程組的解稱為位勢(shì)，方程組的解稱為位勢(shì)） step2step2 計(jì)算計(jì)算非基變量（空格）非基變量（空格）的檢驗(yàn)數(shù)的檢驗(yàn)數(shù)： ij ij=c =cij ij- -（ （u ui i+v+vj

32、 j），）， 填入括號(hào)內(nèi)填入括號(hào)內(nèi) 教材例教材例1 2021-6-2036 l 當(dāng)當(dāng)非基變量的非基變量的檢驗(yàn)數(shù)出現(xiàn)負(fù)值檢驗(yàn)數(shù)出現(xiàn)負(fù)值時(shí)，則表明當(dāng)前的基本時(shí)，則表明當(dāng)前的基本 可行解不是最優(yōu)解。在這種情況下，應(yīng)該對(duì)基本可行解可行解不是最優(yōu)解。在這種情況下，應(yīng)該對(duì)基本可行解 進(jìn)行調(diào)整，即找到一個(gè)新的基本可行解使目標(biāo)函數(shù)值下進(jìn)行調(diào)整，即找到一個(gè)新的基本可行解使目標(biāo)函數(shù)值下 降，這一過程通常稱為降，這一過程通常稱為換基過程換基過程。 方法：閉回路調(diào)整法方法：閉回路調(diào)整法 三、求新的基可行解三、求新的基可行解-基可行解的改進(jìn)基可行解的改進(jìn) 2021-6-2037 步驟：步驟： 1 1、取取0 總銷總銷

33、量，還是總銷量量，還是總銷量 總產(chǎn)量，然后虛擬銷地或產(chǎn)地；總產(chǎn)量，然后虛擬銷地或產(chǎn)地； B B、有最高與最低情況的按照、有最高與最低情況的按照兩個(gè)地區(qū)看待兩個(gè)地區(qū)看待；（注意各；（注意各 地區(qū)產(chǎn)量和需求量如何確定）地區(qū)產(chǎn)量和需求量如何確定） C C、注意、注意運(yùn)價(jià)運(yùn)價(jià)確定方法：一般情況下虛擬的為確定方法：一般情況下虛擬的為零零，不讓，不讓 運(yùn)輸?shù)倪\(yùn)價(jià)運(yùn)輸?shù)倪\(yùn)價(jià)為為M M。 2021-6-2054 在原運(yùn)輸問題上增加若干轉(zhuǎn)運(yùn)站。運(yùn)輸方式有：產(chǎn)地在原運(yùn)輸問題上增加若干轉(zhuǎn)運(yùn)站。運(yùn)輸方式有：產(chǎn)地 轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)站轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)站 銷地、產(chǎn)地銷地、產(chǎn)地 產(chǎn)地、產(chǎn)地產(chǎn)地、產(chǎn)地 銷地、銷地銷地、銷地 轉(zhuǎn)運(yùn)站、銷

34、地轉(zhuǎn)運(yùn)站、銷地 產(chǎn)地等產(chǎn)地等。 例例6、騰飛電子儀器公司在大連和廣州有兩個(gè)分廠生產(chǎn)同一種儀器，大連分廠每騰飛電子儀器公司在大連和廣州有兩個(gè)分廠生產(chǎn)同一種儀器，大連分廠每 月生產(chǎn)月生產(chǎn)400臺(tái)，廣州分廠每月生產(chǎn)臺(tái)，廣州分廠每月生產(chǎn)600臺(tái)。臺(tái)。 該公司在上海和天津有兩個(gè)銷售公司負(fù)該公司在上海和天津有兩個(gè)銷售公司負(fù) 責(zé)對(duì)南京、濟(jì)南、南昌、青島四個(gè)城市責(zé)對(duì)南京、濟(jì)南、南昌、青島四個(gè)城市 的儀器供應(yīng)。另外因?yàn)榇筮B距離青島較的儀器供應(yīng)。另外因?yàn)榇筮B距離青島較 近，公司同意大連分廠向青島直接供貨，近，公司同意大連分廠向青島直接供貨， 運(yùn)輸費(fèi)用如圖，單位是百元。運(yùn)輸費(fèi)用如圖，單位是百元。 問應(yīng)該如何調(diào)運(yùn)儀器

35、，可使總運(yùn)輸費(fèi)用最低？問應(yīng)該如何調(diào)運(yùn)儀器，可使總運(yùn)輸費(fèi)用最低？ 圖中圖中: 1- 廣州、廣州、2 - 大連、大連、3 - 上海、上海、4 - 天津、天津、5 - 南京、南京、6 - 濟(jì)南、濟(jì)南、7 - 南昌、南昌、8 - 青島青島 二、轉(zhuǎn)運(yùn)問題二、轉(zhuǎn)運(yùn)問題 2021-6-2055 解：解：設(shè)設(shè) xij 為從為從 i 到到 j 的運(yùn)輸量，可得到有下列特點(diǎn)的線性規(guī)的運(yùn)輸量，可得到有下列特點(diǎn)的線性規(guī) 劃模型：劃模型： 目標(biāo)函數(shù)：目標(biāo)函數(shù)：Min f = Min f = 所有可能的運(yùn)輸費(fèi)用（運(yùn)輸單價(jià)與運(yùn)所有可能的運(yùn)輸費(fèi)用（運(yùn)輸單價(jià)與運(yùn) 輸量乘積之和）輸量乘積之和） 約束條件：約束條件： 對(duì)產(chǎn)地（發(fā)點(diǎn)）

36、對(duì)產(chǎn)地（發(fā)點(diǎn)） i i ：輸出量：輸出量 - - 輸入量輸入量 = = 產(chǎn)量產(chǎn)量 對(duì)轉(zhuǎn)運(yùn)站（中轉(zhuǎn)點(diǎn)）：輸入量對(duì)轉(zhuǎn)運(yùn)站（中轉(zhuǎn)點(diǎn)）：輸入量 - - 輸出量輸出量 = 0= 0 對(duì)銷地（收點(diǎn)）對(duì)銷地（收點(diǎn)） j j ：輸入量：輸入量 - - 輸出量輸出量 = = 銷量銷量 2021-6-2056 目標(biāo)函數(shù)：目標(biāo)函數(shù)： Min f = 2Min f = 2x x13 13+ 3 + 3x x14 14+ 3 + 3x x23 23+ + x x24 24+ 4 + 4x x28 28 + 2 + 2x x35 35+ 6 + 6x x36 36+ 3 + 3x x37 37+ + 6 6x x38 3

37、8+ 4 + 4x x45 45+ 4 + 4x x46 46+ 6 + 6x x47 47+ 5 + 5x x48 48 約束條件：約束條件： s.ts.t. . x x13 13+ + x x14 14 600 ( 600 (廣州分廠供應(yīng)量限制）廣州分廠供應(yīng)量限制） x x23 23+ + x x24 24+ + x x28 28 400 ( 400 (大連分廠供應(yīng)量限制）大連分廠供應(yīng)量限制） - -x x13 13- - x x23 23 + + x x35 35 + + x x36 36+ + x x37 37 + + x x38 38 = 0 = 0 （上海銷售公司，轉(zhuǎn)運(yùn)站）（上海銷

38、售公司，轉(zhuǎn)運(yùn)站） - -x x14 14- - x x24 24 + + x x45 45 + + x x46 46+ + x x47 47 + + x x48 48 = 0 = 0 （天津銷售公司，轉(zhuǎn)運(yùn)站）（天津銷售公司，轉(zhuǎn)運(yùn)站） x x35 35+ + x x45 45 = 200 = 200 （南京的銷量）（南京的銷量） x x36 36+ + x x46 46 = 150 = 150 （濟(jì)南的銷量）（濟(jì)南的銷量） x x37 37+ + x x47 47 = 350 = 350 （南昌的銷量）（南昌的銷量） x x38 38+ + x x48 48 + + x x28 28 = 300

39、 = 300 （青島的銷量）（青島的銷量） x xij ij 0 , 0 , i,ji,j = 1,2,3,4,5,6,7,8 = 1,2,3,4,5,6,7,8 2021-6-2057 345678 123MMMM600 231MMM4400 30M26361000 4M044651000 1000 1000200150350300 2021-6-2058 例例7、某公司有、某公司有A1、 A2、 A3三個(gè)分廠生產(chǎn)某種物資，分別供應(yīng)三個(gè)分廠生產(chǎn)某種物資，分別供應(yīng)B1、 B2、 B3、 B4四個(gè)地區(qū)的銷售公司銷售。假設(shè)質(zhì)量相同，有關(guān)數(shù)據(jù)如下表：四個(gè)地區(qū)的銷售公司銷售。假設(shè)質(zhì)量相同，有關(guān)數(shù)據(jù)如下

40、表： 試求總費(fèi)用為最少的調(diào)運(yùn)方案。試求總費(fèi)用為最少的調(diào)運(yùn)方案。 假設(shè)：假設(shè)： 1.每個(gè)分廠的物資不一定直接發(fā)運(yùn)到銷地，可以從其中幾個(gè)產(chǎn)地集中一起運(yùn)；每個(gè)分廠的物資不一定直接發(fā)運(yùn)到銷地，可以從其中幾個(gè)產(chǎn)地集中一起運(yùn)； 2.運(yùn)往各銷地的物資可以先運(yùn)給其中幾個(gè)銷地，再轉(zhuǎn)運(yùn)給其他銷地；運(yùn)往各銷地的物資可以先運(yùn)給其中幾個(gè)銷地，再轉(zhuǎn)運(yùn)給其他銷地； 3.除產(chǎn)銷地之外，還有幾個(gè)中轉(zhuǎn)站，在產(chǎn)地之間、銷地之間或在產(chǎn)地與銷地之除產(chǎn)銷地之外，還有幾個(gè)中轉(zhuǎn)站，在產(chǎn)地之間、銷地之間或在產(chǎn)地與銷地之 間轉(zhuǎn)運(yùn)。間轉(zhuǎn)運(yùn)。 2021-6-2059 運(yùn)價(jià)如下表：運(yùn)價(jià)如下表： 2021-6-2060 解：把此轉(zhuǎn)運(yùn)問題轉(zhuǎn)化為一般運(yùn)輸問

41、題：解：把此轉(zhuǎn)運(yùn)問題轉(zhuǎn)化為一般運(yùn)輸問題： 1 1、把所有產(chǎn)地、銷地、轉(zhuǎn)運(yùn)站都同時(shí)看作產(chǎn)地和銷地；、把所有產(chǎn)地、銷地、轉(zhuǎn)運(yùn)站都同時(shí)看作產(chǎn)地和銷地； 2 2、運(yùn)輸表中不可能方案的運(yùn)費(fèi)取作、運(yùn)輸表中不可能方案的運(yùn)費(fèi)取作M M，自身對(duì)自身的運(yùn)費(fèi)為，自身對(duì)自身的運(yùn)費(fèi)為0 0； 3 3、A Ai i： 產(chǎn)量為產(chǎn)量為 20+20+原產(chǎn)量，原產(chǎn)量， 銷量為銷量為 2020； T Ti i： 產(chǎn)量、銷量均為產(chǎn)量、銷量均為 2020； B Bi i： 產(chǎn)量為產(chǎn)量為 2020，銷量為，銷量為 20 +20 +原銷量，其中原銷量，其中2020為各點(diǎn)可能變化為各點(diǎn)可能變化 的最大流量；的最大流量； 4 4、對(duì)于最優(yōu)方案

42、，其中、對(duì)于最優(yōu)方案，其中 x xi i i i 為自身對(duì)自身的運(yùn)量，實(shí)際上不進(jìn)行 為自身對(duì)自身的運(yùn)量，實(shí)際上不進(jìn)行 運(yùn)作。運(yùn)作。 2021-6-2061 擴(kuò)大的運(yùn)輸問題產(chǎn)銷平衡與運(yùn)價(jià)表：擴(kuò)大的運(yùn)輸問題產(chǎn)銷平衡與運(yùn)價(jià)表： 2021-6-2062 教材例教材例5 2021-6-2063 例例8、光明儀器廠生產(chǎn)電腦繡花機(jī)是以產(chǎn)定銷的。已知、光明儀器廠生產(chǎn)電腦繡花機(jī)是以產(chǎn)定銷的。已知1至至6月份各月的生產(chǎn)月份各月的生產(chǎn) 能力、合同銷量和單臺(tái)電腦繡花機(jī)平均生產(chǎn)費(fèi)用見下表：能力、合同銷量和單臺(tái)電腦繡花機(jī)平均生產(chǎn)費(fèi)用見下表： 已知上年末庫存已知上年末庫存103臺(tái)繡花機(jī)，如果當(dāng)月生產(chǎn)出來的機(jī)器當(dāng)月不交貨，臺(tái)

43、繡花機(jī)，如果當(dāng)月生產(chǎn)出來的機(jī)器當(dāng)月不交貨， 則需要運(yùn)到分廠庫房，每臺(tái)增加運(yùn)輸成本則需要運(yùn)到分廠庫房，每臺(tái)增加運(yùn)輸成本0.1萬元萬元,每臺(tái)機(jī)器每月的平均倉每臺(tái)機(jī)器每月的平均倉 儲(chǔ)費(fèi)、維護(hù)費(fèi)為儲(chǔ)費(fèi)、維護(hù)費(fèi)為0.2萬元。在萬元。在7-8月份銷售淡季，全廠停產(chǎn)月份銷售淡季，全廠停產(chǎn)1個(gè)月，因此在個(gè)月，因此在 6月份完成銷售合同后還要留出庫存月份完成銷售合同后還要留出庫存80臺(tái)。加班生產(chǎn)機(jī)器每臺(tái)增加成本臺(tái)。加班生產(chǎn)機(jī)器每臺(tái)增加成本1 萬元。問應(yīng)如何安排萬元。問應(yīng)如何安排1-6月份的生產(chǎn)，可使總的生產(chǎn)費(fèi)用（包括運(yùn)輸、倉月份的生產(chǎn)，可使總的生產(chǎn)費(fèi)用（包括運(yùn)輸、倉 儲(chǔ)、維護(hù)）最少？?jī)?chǔ)、維護(hù)）最少？ 三、生產(chǎn)與

44、儲(chǔ)存問題三、生產(chǎn)與儲(chǔ)存問題 2021-6-2064 解：解： 這個(gè)生產(chǎn)存儲(chǔ)問題可化為運(yùn)輸問題來做。考慮：各月生產(chǎn)與交貨分這個(gè)生產(chǎn)存儲(chǔ)問題可化為運(yùn)輸問題來做?？紤]：各月生產(chǎn)與交貨分 別視為產(chǎn)地和銷地別視為產(chǎn)地和銷地 1）1-6月份合計(jì)生產(chǎn)能力（包括上年末儲(chǔ)存量）為月份合計(jì)生產(chǎn)能力（包括上年末儲(chǔ)存量）為743臺(tái)，銷量為臺(tái)，銷量為 707臺(tái)。設(shè)一假想銷地銷量為臺(tái)。設(shè)一假想銷地銷量為36； 2）上年末庫存）上年末庫存103臺(tái)，只有倉儲(chǔ)費(fèi)和運(yùn)輸費(fèi)，把它列為第臺(tái)，只有倉儲(chǔ)費(fèi)和運(yùn)輸費(fèi)，把它列為第0行；行； 3）6月份的需求除月份的需求除70臺(tái)銷量外，還要臺(tái)銷量外，還要80臺(tái)庫存，其需求應(yīng)為臺(tái)庫存，其需求應(yīng)為

45、 70+80=150臺(tái)；臺(tái)； 4）1-6表示表示1-6月份正常生產(chǎn)情況，月份正常生產(chǎn)情況， 1-6表示表示1-6月份加班生產(chǎn)月份加班生產(chǎn) 情況。情況。 產(chǎn)銷平衡與運(yùn)價(jià)表：產(chǎn)銷平衡與運(yùn)價(jià)表： 2021-6-2065 2021-6-2066 四、航運(yùn)四、航運(yùn)調(diào)度問題調(diào)度問題 某航運(yùn)公司承擔(dān)六個(gè)城市某航運(yùn)公司承擔(dān)六個(gè)城市A A、B B、C C、D D、E E、F F之間的四條航線，之間的四條航線， 已知各航線的起點(diǎn)、終點(diǎn)及每天所需的航班數(shù)如下表。又知已知各航線的起點(diǎn)、終點(diǎn)及每天所需的航班數(shù)如下表。又知 各城市之間的航行天數(shù)，假定船只型號(hào)相同，裝卸貨時(shí)間各各城市之間的航行天數(shù)，假定船只型號(hào)相同，裝卸貨時(shí)間各 一天，問該公司至少要配備多少條船才能滿足需要？一天，問該公司至少要配備多少條船才能滿足需要？ 航線航線起點(diǎn)起點(diǎn)終點(diǎn)終點(diǎn)每天