運(yùn)籌學(xué)運(yùn)輸問題

1、Chapter4 運(yùn)輸問題運(yùn)輸問題運(yùn)輸模型運(yùn)輸模型運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法 運(yùn)輸問題的應(yīng)用運(yùn)輸問題的應(yīng)用 中華圖書進(jìn)出口總公司的主營業(yè)務(wù)之一是中文書刊對國外出口業(yè)務(wù)，每年中華圖書進(jìn)出口總公司的主營業(yè)務(wù)之一是中文書刊對國外出口業(yè)務(wù)，每年10月月-12月為下一年度報刊訂閱的征訂期。在此期間，為鞏固老訂戶，發(fā)展新訂戶，要向月為下一年度報刊訂閱的征訂期。在此期間，為鞏固老訂戶，發(fā)展新訂戶，要向國外個人、大學(xué)圖書館、科研機(jī)構(gòu)等無償寄發(fā)小禮品和征訂宣傳推廣材料。國外個人、大學(xué)圖書館、科研機(jī)構(gòu)等無償寄發(fā)小禮品和征訂宣傳推廣材料。 中華圖書進(jìn)出口總公司在深圳、上海的分公司也部分經(jīng)營中文報刊的出

2、口業(yè)務(wù)。中華圖書進(jìn)出口總公司在深圳、上海的分公司也部分經(jīng)營中文報刊的出口業(yè)務(wù)。為維護(hù)公司整體利益，公司對征訂期間三個部門寄發(fā)征訂材料的工作做了整體安排。為維護(hù)公司整體利益，公司對征訂期間三個部門寄發(fā)征訂材料的工作做了整體安排。部部 門門份數(shù)份數(shù)/冊冊中文書刊出口部15000深圳分公司7500上海分公司7500總 計30000 日本、韓國以及中國香港地區(qū)集中了該公司的絕大部分中文報刊訂戶，根據(jù)訂日本、韓國以及中國香港地區(qū)集中了該公司的絕大部分中文報刊訂戶，根據(jù)訂戶數(shù)分布數(shù)量不同，寄發(fā)征訂材料的數(shù)量也不同，對此公司也做了安排。戶數(shù)分布數(shù)量不同，寄發(fā)征訂材料的數(shù)量也不同，對此公司也做了安排。國家和地

3、區(qū)國家和地區(qū)份數(shù)份數(shù)/冊冊日 本15000中國香港特別行政區(qū)10000韓 國5000總 計30000 這些材料無論由三家中哪個部門寄出，征收訂戶的效果大致相同；同時，無論這些材料無論由三家中哪個部門寄出，征收訂戶的效果大致相同；同時，無論讀者向哪個部門訂閱，為總公司創(chuàng)造的利益均是大致一樣的。讀者向哪個部門訂閱，為總公司創(chuàng)造的利益均是大致一樣的。 但由于各部門郵途距離不同，郵寄方式及人工費(fèi)用不同，導(dǎo)致從各部門寄往各但由于各部門郵途距離不同，郵寄方式及人工費(fèi)用不同，導(dǎo)致從各部門寄往各地的費(fèi)用也不同。地的費(fèi)用也不同。日日 本本中國香港特別行政區(qū)中國香港特別行政區(qū)韓韓 國國中文書刊出口部中文書刊出口部

4、10.2079深圳分公司深圳分公司12.50414上海分公司上海分公司687.50 要求：在服從公司總體安排的前提下，作出一個公司整體的中文書刊征訂材料要求：在服從公司總體安排的前提下，作出一個公司整體的中文書刊征訂材料的郵運(yùn)方案，使得公司總的郵運(yùn)費(fèi)用最小。的郵運(yùn)方案，使得公司總的郵運(yùn)費(fèi)用最小。5運(yùn)輸問題：解決把某種產(chǎn)品從若干個產(chǎn)地調(diào)運(yùn)到若干個銷地，在每個產(chǎn)運(yùn)輸問題：解決把某種產(chǎn)品從若干個產(chǎn)地調(diào)運(yùn)到若干個銷地，在每個產(chǎn)地的供應(yīng)量與每個銷地的需求量已知，各地之間的運(yùn)輸單價已知的前提地的供應(yīng)量與每個銷地的需求量已知，各地之間的運(yùn)輸單價已知的前提下，如何確定一個使得總的運(yùn)輸費(fèi)用最小的方案的問題。下，

5、如何確定一個使得總的運(yùn)輸費(fèi)用最小的方案的問題。1 1運(yùn)運(yùn) 輸輸 模模 型型例例 某公司從兩個產(chǎn)地某公司從兩個產(chǎn)地A1、A2將物品運(yùn)往三個銷地將物品運(yùn)往三個銷地B1、B2、B3，各產(chǎn)地，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如下表所示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最小？示，問：應(yīng)如何調(diào)運(yùn)可使總運(yùn)輸費(fèi)用最??？B1B2B3產(chǎn)量A1646200A2655300銷量1501502006解：解： 產(chǎn)銷平衡問題：產(chǎn)銷平衡問題： 總產(chǎn)量總產(chǎn)量 = 總銷量總銷量 設(shè)設(shè) xij 為從產(chǎn)地為從產(chǎn)地Ai運(yùn)往銷地運(yùn)往銷地Bj的運(yùn)輸量，得到下

6、列運(yùn)輸量表：的運(yùn)輸量，得到下列運(yùn)輸量表： 滿足產(chǎn)地產(chǎn)量的約束條件：滿足銷地銷量的約束條件：使運(yùn)費(fèi)最小，即 1 1運(yùn)運(yùn) 輸輸 模模 型型B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量150150200111213212223200300 xxxxxx112112221323150150200 xxxxxx111213212223min 646655fxxxxxxB1B2B3產(chǎn) 量A1646200A2655300銷 量1501502007所以此線性規(guī)劃問題的線性規(guī)劃模型如下： 1 1運(yùn)運(yùn) 輸輸 模模 型型11121321222311121321222311211222

7、1323min 646655200300150s.t. 15020001,2;1,2,3ijfxxxxxxxxxxxxxxxxxxxij81 1運(yùn)運(yùn) 輸輸 模模 型型產(chǎn)銷平衡運(yùn)輸問題的一般模型：產(chǎn)銷平衡運(yùn)輸問題的一般模型： A1、 A2、 Am 表示某物資的表示某物資的m個產(chǎn)地；個產(chǎn)地；B1、B2、Bn 表示某物質(zhì)的表示某物質(zhì)的n個銷地；個銷地；si 表示產(chǎn)地表示產(chǎn)地Ai的產(chǎn)量；的產(chǎn)量；dj 表示銷地表示銷地Bj 的銷量；的銷量； cij 表示把物資從產(chǎn)地表示把物資從產(chǎn)地Ai運(yùn)往銷地運(yùn)往銷地Bj的單位運(yùn)價。的單位運(yùn)價。 設(shè)設(shè) xij 為從產(chǎn)地為從產(chǎn)地Ai運(yùn)往銷地運(yùn)往銷地Bj的運(yùn)輸量，得到下列一

8、般運(yùn)輸問題的模型：的運(yùn)輸量，得到下列一般運(yùn)輸問題的模型： 1111min ,i=1,2,ms.t. ,j=1,2,n0,ij.mnijijijnijijmijjiijfc xxsxdxLL對所有的 和91 1運(yùn)運(yùn) 輸輸 模模 型型上述運(yùn)輸問題一般模型的變體：上述運(yùn)輸問題一般模型的變體： 求目標(biāo)函數(shù)的最大值，如求利潤最大或營業(yè)額最大等；求目標(biāo)函數(shù)的最大值，如求利潤最大或營業(yè)額最大等； 當(dāng)某些運(yùn)輸線路上的能力有限制時，在模型中要加入運(yùn)輸能力限制的當(dāng)某些運(yùn)輸線路上的能力有限制時，在模型中要加入運(yùn)輸能力限制的約束條件；約束條件； 產(chǎn)銷不平衡時，可加入假想的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷產(chǎn)銷不平衡時

9、，可加入假想的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷時）。時）。B1B2B3產(chǎn)量A1x11x12x13200A2x21x22x23300銷量15015020013100 x102 2運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法表上作業(yè)法：是求解運(yùn)輸問題的方法，其實(shí)質(zhì)是單純形法。表上作業(yè)法：是求解運(yùn)輸問題的方法，其實(shí)質(zhì)是單純形法。表上作業(yè)法的計算過程：表上作業(yè)法的計算過程：找出初始基本可行解：由于產(chǎn)銷平衡，運(yùn)輸問題有找出初始基本可行解：由于產(chǎn)銷平衡，運(yùn)輸問題有m+n-1個基個基變量。在變量。在mn的產(chǎn)銷平衡表上給出的產(chǎn)銷平衡表上給出m+n-1個數(shù)字格，其相對個數(shù)字格，其相對應(yīng)的調(diào)運(yùn)量的值即為基變量的值；

10、應(yīng)的調(diào)運(yùn)量的值即為基變量的值；求各非基變量的檢驗數(shù)：檢驗除了上述求各非基變量的檢驗數(shù)：檢驗除了上述m+n-1個基變量以外的個基變量以外的空格的檢驗數(shù)，判別是否達(dá)到最優(yōu)解，如果已是最優(yōu)，停止空格的檢驗數(shù)，判別是否達(dá)到最優(yōu)解，如果已是最優(yōu)，停止計算，否則轉(zhuǎn)到下一步；計算，否則轉(zhuǎn)到下一步；確定入基變量和出基變量：在表上用閉回路法找出新的基本確定入基變量和出基變量：在表上用閉回路法找出新的基本可行解；可行解；重復(fù)重復(fù)2、3直到得到最優(yōu)解。直到得到最優(yōu)解。112 2運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法例例 喜慶食品公司有三個生產(chǎn)面包的分廠喜慶食品公司有三個生產(chǎn)面包的分廠A1，A2，A3，有四個銷售公

11、司，有四個銷售公司B1，B2，B3，B4，其各分廠每日的產(chǎn)量、各銷售公司每日的銷量以及各，其各分廠每日的產(chǎn)量、各銷售公司每日的銷量以及各分廠到各銷售公司的單位運(yùn)價如表所示，在表中產(chǎn)量與銷量的單位為噸，分廠到各銷售公司的單位運(yùn)價如表所示，在表中產(chǎn)量與銷量的單位為噸，運(yùn)價的單位為百元運(yùn)價的單位為百元/噸。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品在滿足各銷點(diǎn)的需求量噸。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品在滿足各銷點(diǎn)的需求量的前提下總運(yùn)費(fèi)最少？的前提下總運(yùn)費(fèi)最少？ 銷地產(chǎn)地B1B2B3B4產(chǎn)量A13113107A219284A3741059銷量3656 2020122 2運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法一、確定初始基本可行

12、解一、確定初始基本可行解 為了把初始基本可行解與運(yùn)價區(qū)分開，我們把運(yùn)價放在每一欄的右上為了把初始基本可行解與運(yùn)價區(qū)分開，我們把運(yùn)價放在每一欄的右上角，每角，每一欄的中間寫上初始基本可行解（調(diào)運(yùn)量）。一欄的中間寫上初始基本可行解（調(diào)運(yùn)量）。 1.西北角法西北角法 銷地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 7 A2 4 A3 9 銷量 3 6 5 6 2020311310851029471304420202203306600初始基本可行解：初始基本可行解：總運(yùn)輸費(fèi)用為：總運(yùn)輸費(fèi)用為：135（百元）（百元）1112222333343,4,2,2,3,6xxxxxx132 2運(yùn)輸問題的表上作業(yè)法運(yùn)

13、輸問題的表上作業(yè)法2.最小元素法最小元素法 最小元素法是就近供應(yīng)，即對單位運(yùn)價最小的變量分配運(yùn)輸量。最小元素法是就近供應(yīng)，即對單位運(yùn)價最小的變量分配運(yùn)輸量。 銷地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 7 A2 4 A3 9 銷量 3 6 5 6 2020311310851029471301104430603303300初始基本可行解：初始基本可行解：總運(yùn)輸費(fèi)用為：總運(yùn)輸費(fèi)用為：86（百元）（百元）1314212332344,3,3,1,6,3xxxxxx通過西北角法求得的初始基本可行解對應(yīng)的總運(yùn)輸費(fèi)用為：通過西北角法求得的初始基本可行解對應(yīng)的總運(yùn)輸費(fèi)用為：135（百元）（百元）142 2運(yùn)

14、輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法 注意：注意：當(dāng)取定當(dāng)取定xij的值之后，會出現(xiàn)的值之后，會出現(xiàn)Ai的產(chǎn)量與的產(chǎn)量與Bj的銷量都的銷量都改為零的情況，這時只能劃去改為零的情況，這時只能劃去Ai行或行或Bj列，但不列，但不能同時劃去能同時劃去Ai行與行與Bj列。列。用最小元素法時，可能會出現(xiàn)只剩下一行或一列的用最小元素法時，可能會出現(xiàn)只剩下一行或一列的所有格均未填數(shù)或未被劃掉的情況，此時在這一所有格均未填數(shù)或未被劃掉的情況，此時在這一行或者一列中除去已填上的數(shù)外均填上零，不能行或者一列中除去已填上的數(shù)外均填上零，不能按空格劃掉。這樣可以保證填過數(shù)或零的格為按空格劃掉。這樣可以保證填過數(shù)或零

15、的格為m+n-1個，即保證基變量的個數(shù)為個，即保證基變量的個數(shù)為m+n-1個。個。152 2運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法二、最優(yōu)解的判別二、最優(yōu)解的判別 1.閉回路法：在已給出的調(diào)運(yùn)方案的運(yùn)輸表上從一個代閉回路法：在已給出的調(diào)運(yùn)方案的運(yùn)輸表上從一個代表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)，只有表非基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)，只有遇到代表基變量的填入數(shù)字的格才能向左或右轉(zhuǎn)遇到代表基變量的填入數(shù)字的格才能向左或右轉(zhuǎn)90度繼度繼續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個空格，由續(xù)前進(jìn)，這樣繼續(xù)下去，直至回到出發(fā)的那個空格，由此形成的封閉折線叫做閉回路。一個空格存在唯一的閉此

16、形成的封閉折線叫做閉回路。一個空格存在唯一的閉回路?；芈?。 銷地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 43 7 A2 3 1 4 A363 9 銷量 3 6 5 6 2020311310851029471x11x11162 2運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法 閉回路法：是對于代表非基變量的空格（其調(diào)運(yùn)量為零），把它的閉回路法：是對于代表非基變量的空格（其調(diào)運(yùn)量為零），把它的調(diào)運(yùn)量調(diào)整為調(diào)運(yùn)量調(diào)整為1，由于產(chǎn)銷平衡的要求，由于產(chǎn)銷平衡的要求,我們必須對這個空格的閉回路的我們必須對這個空格的閉回路的頂點(diǎn)的調(diào)運(yùn)量加上或減少頂點(diǎn)的調(diào)運(yùn)量加上或減少1。最后計算出由這些變化給整個運(yùn)輸方案的。最

17、后計算出由這些變化給整個運(yùn)輸方案的總運(yùn)輸費(fèi)帶來的變化，即這個空格代表的非基變量的檢驗數(shù)。如果所有總運(yùn)輸費(fèi)帶來的變化，即這個空格代表的非基變量的檢驗數(shù)。如果所有代表非基變量的空格的檢驗數(shù)都大于等于零，則已求得最優(yōu)解，否則繼代表非基變量的空格的檢驗數(shù)都大于等于零，則已求得最優(yōu)解，否則繼續(xù)迭代找出最優(yōu)解。續(xù)迭代找出最優(yōu)解。 銷地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 43 7 A2 3 1 4 A363 9 銷量 3 6 5 6 2020311310851029471運(yùn)費(fèi)的變化：運(yùn)費(fèi)的變化：33-32+22-1=1172 2運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法空空 格格閉閉 回回 路路檢檢 驗

18、驗 數(shù)數(shù)121-1101211x12x22x24x31x33x1113232111xxxxx1214343212xxxxx22231314343222xxxxxxx2423131424xxxxx31341413232131xxxxxxx3334141333xxxxx182 2運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法2.位勢法：對運(yùn)輸表上的每一行賦予一個數(shù)值位勢法：對運(yùn)輸表上的每一行賦予一個數(shù)值ui，對每一列賦予一個數(shù)值，對每一列賦予一個數(shù)值vj，它們的數(shù)值是由基變量，它們的數(shù)值是由基變量xij的檢驗數(shù)的檢驗數(shù) 所決定的，則非所決定的，則非基變量基變量xij的檢驗數(shù)就可以用公式的檢驗數(shù)就可以用公

19、式 求出。求出。 銷地產(chǎn)地 B1 B2 B3 B4 ui A1 4 3 A2 3 1 A3 6 3 vj 3113108510294710jiijijvucjiijijvuc0310-1-529-192 2運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法三、改進(jìn)運(yùn)輸方案的辦法三、改進(jìn)運(yùn)輸方案的辦法閉回路調(diào)整法閉回路調(diào)整法 方法是：選取所有負(fù)檢驗數(shù)最小的非基變量作為入基變量，以求盡快實(shí)方法是：選取所有負(fù)檢驗數(shù)最小的非基變量作為入基變量，以求盡快實(shí)現(xiàn)最優(yōu)?，F(xiàn)最優(yōu)。 銷地產(chǎn)地 B1 B2 B3 B4 ui A1 4(+1) 3(-1) 0 A2 3 1 (-1) +1 -1 A3 6 3 -5 vj 2 9

20、 3 10 2020311310851029471202 2運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法 銷地產(chǎn)地 B1 B2 B3 B4 產(chǎn)量 A1 5 2 7 A2 3 1 4 A3 6 3 9 銷量 3 6 5 6 2020 銷地產(chǎn)地 B1 B2 B3 B4 ui A1 0 2 5 2 0 A2 3 2 1 1 -1 A3 9 6 12 3 -5 vj 2 9 3 10 2020311310851029471上表給出的運(yùn)輸方案對應(yīng)的檢驗數(shù)如下表所示：上表給出的運(yùn)輸方案對應(yīng)的檢驗數(shù)如下表所示：212 2運(yùn)輸問題的表上作業(yè)法運(yùn)輸問題的表上作業(yè)法四、如何找多個最優(yōu)方案四、如何找多個最優(yōu)方案 識別是

21、否有多個最優(yōu)解的方法和單純形表法一樣，只需看最優(yōu)方案中是否識別是否有多個最優(yōu)解的方法和單純形表法一樣，只需看最優(yōu)方案中是否存在非基變量的檢驗數(shù)為零。如在本題中給出的最優(yōu)運(yùn)輸方案中存在非基變量的檢驗數(shù)為零。如在本題中給出的最優(yōu)運(yùn)輸方案中x11的檢驗數(shù)為的檢驗數(shù)為0，可知此運(yùn)輸問題有多個最優(yōu)解。只要把，可知此運(yùn)輸問題有多個最優(yōu)解。只要把x11作為入基變量，調(diào)整運(yùn)輸方案，就可作為入基變量，調(diào)整運(yùn)輸方案，就可得到另一個最優(yōu)方案。得到另一個最優(yōu)方案。 銷地產(chǎn)地 B1 B2 B3 B4A1 (+2) 5 2(-2)A2 3(-2) 1(+2)A3 6 3 銷地產(chǎn)地 B1 B2 B3 B4A1 2 5 A2

22、 1 3A3 6 322課堂作業(yè)課堂作業(yè)有個玩具制造商在不同的地方開設(shè)了三個工廠，從這些長將有個玩具制造商在不同的地方開設(shè)了三個工廠，從這些長將汽車零件運(yùn)至設(shè)在全國各地的四個倉庫，并希望運(yùn)費(fèi)最小，汽車零件運(yùn)至設(shè)在全國各地的四個倉庫，并希望運(yùn)費(fèi)最小，下表列出了運(yùn)價及三個廠的供應(yīng)量和四個倉庫的需求量，請下表列出了運(yùn)價及三個廠的供應(yīng)量和四個倉庫的需求量，請求出運(yùn)費(fèi)最小的方案。求出運(yùn)費(fèi)最小的方案。 倉庫工廠1234供應(yīng)量121355022241303143270銷量40502535 150150233 3運(yùn)輸問題的應(yīng)用運(yùn)輸問題的應(yīng)用一、產(chǎn)銷不平衡的運(yùn)輸問題一、產(chǎn)銷不平衡的運(yùn)輸問題例例 石家莊北方研究院

23、有一、二、三三個區(qū)。每年分別需要用煤石家莊北方研究院有一、二、三三個區(qū)。每年分別需要用煤3000、1000、2000噸，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價格、質(zhì)量相同。供噸，由河北臨城、山西盂縣兩處煤礦負(fù)責(zé)供應(yīng)，價格、質(zhì)量相同。供應(yīng)能力分別為應(yīng)能力分別為1500、4000噸，運(yùn)價為：噸，運(yùn)價為： 由于需大于供，經(jīng)院研究決定一區(qū)供應(yīng)量可減少由于需大于供，經(jīng)院研究決定一區(qū)供應(yīng)量可減少0-300噸，二區(qū)必須滿噸，二區(qū)必須滿足需求量，三區(qū)供應(yīng)量不少于足需求量，三區(qū)供應(yīng)量不少于1500噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。噸，試求總費(fèi)用為最低的調(diào)運(yùn)方案。解：解： 根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價表：根據(jù)題意

24、，作出產(chǎn)銷平衡與運(yùn)價表：解：解： 根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價表：根據(jù)題意，作出產(chǎn)銷平衡與運(yùn)價表： 最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為最低要求必須滿足，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為 M ，而最高要求與最低要，而最高要求與最低要求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為求的差允許按需要安排，因此把相應(yīng)的虛設(shè)產(chǎn)地運(yùn)費(fèi)取為 0 。對應(yīng)。對應(yīng) 4”的銷量的銷量 50 是考慮問題本身適當(dāng)取的數(shù)據(jù)，根據(jù)產(chǎn)銷平衡要求確定是考慮問題本身適當(dāng)取的數(shù)據(jù)，根據(jù)產(chǎn)銷平衡要求確定 D的產(chǎn)量為的產(chǎn)量為 50。243 3運(yùn)輸問題的應(yīng)用運(yùn)輸問題的應(yīng)用例例 設(shè)有設(shè)有A、B、C三個化肥廠供應(yīng)三個化肥廠供應(yīng)1、

25、2、3、4四個地區(qū)的農(nóng)用化肥。假設(shè)效果相四個地區(qū)的農(nóng)用化肥。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表，試求總費(fèi)用為最低的化肥調(diào)撥方案。同，有關(guān)數(shù)據(jù)如下表，試求總費(fèi)用為最低的化肥調(diào)撥方案。1234產(chǎn)量A1613221750B1413191560C192023-50最低需要量3070010最高需要量507030不限 1 1” 2 3 4 4” 產(chǎn)量 A 16 16 13 22 17 17 50 B 14 14 13 19 15 15 60 C 19 19 20 23 M M 50 D M 0 M 0 M 0 50 銷量 30 20 70 30 10 50 210 210 253 3運(yùn)輸問題的應(yīng)用運(yùn)輸問題的應(yīng)用

26、二、生產(chǎn)與儲存問題二、生產(chǎn)與儲存問題例例 某廠按合同規(guī)定須于當(dāng)年每個季度末分別提供某廠按合同規(guī)定須于當(dāng)年每個季度末分別提供10、15、25、20臺同臺同一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的一規(guī)格的柴油機(jī)。已知該廠各季度的生產(chǎn)能力及生產(chǎn)每臺柴油機(jī)的成本如右表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺每積壓一個成本如右表。如果生產(chǎn)出來的柴油機(jī)當(dāng)季不交貨，每臺每積壓一個季度需儲存、維護(hù)等費(fèi)用季度需儲存、維護(hù)等費(fèi)用0.15萬元。試求在完成合同的情況下，使該萬元。試求在完成合同的情況下，使該廠全年生產(chǎn)總費(fèi)用為最小的決策方案。廠全年生產(chǎn)總費(fèi)用為最小的決策方案。生產(chǎn)能力（臺） 單位成本（萬

27、元）一季度2510.8二季度3511.1三季度3011.0四季度1011.3263 3運(yùn)輸問題的應(yīng)用運(yùn)輸問題的應(yīng)用解：解： 設(shè)設(shè) xij為第為第 i 季度生產(chǎn)的第季度生產(chǎn)的第 j 季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足：季度交貨的柴油機(jī)數(shù)目，那么應(yīng)滿足： 交貨：交貨：x11 = 10 生產(chǎn)：生產(chǎn)：x11 + x12 + x13 + x14 25 x12 + x22 = 15 x22 + x23 + x24 35 x13 + x23 + x33 = 25 x33 + x34 30 x14 + x24 + x34 + x44 = 20 x44 10 把第把第 i 季度生產(chǎn)的柴油機(jī)數(shù)目看作第季度生產(chǎn)的柴油

28、機(jī)數(shù)目看作第 i 個生產(chǎn)廠的產(chǎn)量；把第個生產(chǎn)廠的產(chǎn)量；把第 j 季度季度交貨的柴油機(jī)數(shù)目看作第交貨的柴油機(jī)數(shù)目看作第 j 個銷售點(diǎn)的銷量；成本加儲存、維護(hù)等費(fèi)個銷售點(diǎn)的銷量；成本加儲存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)。用看作運(yùn)費(fèi)。 可構(gòu)造下列產(chǎn)銷平衡問題：可構(gòu)造下列產(chǎn)銷平衡問題：目標(biāo)函數(shù)：目標(biāo)函數(shù)：Min f = 10.8 x11 +10.95 x12 +11.1 x13 +11.25 x14 +11.1 x22 +11.25 x23 +11.4 x24 +11.0 x33 +11.15 x34 +11.3 x44 第一季度 第二季度 第三季度 第四季度 D 產(chǎn)量 第一季度 10.80 10.95 11.

29、10 11.25 0 25 第二季度 M 11.10 11.25 11.40 0 35 第三季度 M M 11.00 11.15 0 30 第四季度 M M M 11.30 0 10 銷量 10 15 25 20 30 100 100 273 3運(yùn)輸問題的應(yīng)用運(yùn)輸問題的應(yīng)用例例 光明儀器廠生產(chǎn)電腦繡花機(jī)是以產(chǎn)定銷的。已知光明儀器廠生產(chǎn)電腦繡花機(jī)是以產(chǎn)定銷的。已知1至至6月份各月的生月份各月的生產(chǎn)能力、合同銷量和單臺電腦繡花機(jī)平均生產(chǎn)費(fèi)用見下表：產(chǎn)能力、合同銷量和單臺電腦繡花機(jī)平均生產(chǎn)費(fèi)用見下表： 已知上年末庫存已知上年末庫存103臺繡花機(jī)，如果當(dāng)月生產(chǎn)出來的機(jī)器當(dāng)月不交貨臺繡花機(jī)，如果當(dāng)月生產(chǎn)

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

31、銷量（臺）單臺費(fèi)用（萬元）1 月份6010104152 月份501075143 月份902011513.54 月份10040160135 月份10040103136 月份80407013.5283 3運(yùn)輸問題的應(yīng)用運(yùn)輸問題的應(yīng)用解：解： 這個生產(chǎn)存儲問題可化為運(yùn)輸問題來做。這個生產(chǎn)存儲問題可化為運(yùn)輸問題來做。 考慮：各月生產(chǎn)與交貨分別視為產(chǎn)地和銷地考慮：各月生產(chǎn)與交貨分別視為產(chǎn)地和銷地 1）1-6月份合計生產(chǎn)能力（包括上年末儲存量）為月份合計生產(chǎn)能力（包括上年末儲存量）為743臺，銷量為臺，銷量為707臺。臺。 設(shè)一假想銷地銷量為設(shè)一假想銷地銷量為36； 2）上年末庫存）上年末庫存103臺，只

32、有倉儲費(fèi)和運(yùn)輸費(fèi)，把它列為第臺，只有倉儲費(fèi)和運(yùn)輸費(fèi)，把它列為第0行；行； 3）6月份的需求除月份的需求除70臺銷量外，還要臺銷量外，還要80臺庫存，其需求應(yīng)為臺庫存，其需求應(yīng)為70+80=150臺；臺； 4）1-6表示表示1-6月份正常生產(chǎn)情況，月份正常生產(chǎn)情況， 1-6表示表示1-6月份加班生產(chǎn)情況。月份加班生產(chǎn)情況。產(chǎn)銷平衡與運(yùn)價表：產(chǎn)銷平衡與運(yùn)價表： 1 月 2 月 3 月 4 月 5 月 6 月 虛銷地 正常產(chǎn)量 加班產(chǎn)量 0 0.3 0.5 0.7 0.9 1.1 1.3 0 103 1 15 15.3 15.5 15.7 15.9 16.1 0 60 1 16 16.3 16.5

33、16.7 6.9 17.1 0 10 2 M 14 14.3 14.5 14.7 14.9 0 50 2 M 15 15.3 15.5 15.7 15.9 0 10 3 M M 13.5 13.8 14.0 14.2 0 90 3 M M 14.5 14.8 15.0 15.2 0 20 4 M M M 13.0 13.3 13.5 0 100 4 M M M 14.0 14.3 14.5 0 40 5 M M M M 13.0 13.3 0 100 5 M M M M 14.0 14.3 0 40 6 M M M M M 13.5 0 80 6 M M M M M 14.5 0 40 銷量

34、104 75 115 160 103 150 36 743 743 29三、轉(zhuǎn)運(yùn)問題三、轉(zhuǎn)運(yùn)問題 在原運(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)轉(zhuǎn)運(yùn)站、轉(zhuǎn)運(yùn)站運(yùn)站 銷地、產(chǎn)地銷地、產(chǎn)地 產(chǎn)地、產(chǎn)地產(chǎn)地、產(chǎn)地 銷地、銷地銷地、銷地 轉(zhuǎn)運(yùn)站、銷地轉(zhuǎn)運(yùn)站、銷地 產(chǎn)地等產(chǎn)地等例例 騰飛電子儀器公司在大連和廣州有兩個分廠騰飛電子儀器公司在大連和廣州有兩個分廠生產(chǎn)同一種儀器，大連分廠每月生產(chǎn)生產(chǎn)同一種儀器，大連分廠每月生產(chǎn)400臺，廣臺，廣州分廠每月生產(chǎn)州分廠每月生產(chǎn)600臺。該公司在上海和天津有臺。該公司在上海和天津有兩個銷售公司負(fù)責(zé)對南京、濟(jì)南

35、、南昌、青島兩個銷售公司負(fù)責(zé)對南京、濟(jì)南、南昌、青島四個城市的儀器供應(yīng)。另外因為大連距離青島四個城市的儀器供應(yīng)。另外因為大連距離青島較近，公司同意大連分廠向青島直接供貨，運(yùn)較近，公司同意大連分廠向青島直接供貨，運(yùn)輸費(fèi)用如圖，單位是百元。問應(yīng)該如何調(diào)運(yùn)儀輸費(fèi)用如圖，單位是百元。問應(yīng)該如何調(diào)運(yùn)儀器，可使總運(yùn)輸費(fèi)用最低？器，可使總運(yùn)輸費(fèi)用最低？1 - 廣州廣州 2 - 大連大連 3 - 上海上海 4 - 天津天津5 - 南京南京 6 - 濟(jì)南濟(jì)南 7 - 南昌南昌 8 - 青島青島30解：設(shè)解：設(shè) xij xij 為從為從 i i 到到 j 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)輸單價與運(yùn)輸量乘積之和）所有可能的運(yùn)輸費(fèi)用（運(yùn)輸單價與運(yùn)輸量乘積之和）約束條件：約束條件： 對產(chǎn)地（發(fā)點(diǎn)）對產(chǎn)地（發(fā)點(diǎn)） i i ：輸出量：輸出量 - - 輸入量輸入量 = = 產(chǎn)量產(chǎn)量 對轉(zhuǎn)運(yùn)站（中轉(zhuǎn)點(diǎn)）：輸入量對轉(zhuǎn)運(yùn)站（中轉(zhuǎn)點(diǎn)）：輸入量 - - 輸出