運(yùn)輸問(wèn)題和指派問(wèn)題

1、實(shí)用運(yùn)籌學(xué)運(yùn)用excel建模與解決、運(yùn)輸問(wèn)題與分配問(wèn)題、本章內(nèi)容要點(diǎn)、運(yùn)輸問(wèn)題的基本概念及其各種變形的建模與應(yīng)用問(wèn)題的基本概念及其各種變形的建模與應(yīng)用， 本章內(nèi)容3.1運(yùn)輸問(wèn)題基本概念3.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型3.3各種運(yùn)輸問(wèn)題變形的建模3.4運(yùn)輸問(wèn)題應(yīng)用實(shí)例3.5分配問(wèn)題3.6隨著各種分配問(wèn)題變形的建模經(jīng)濟(jì)的發(fā)展，現(xiàn)代物流業(yè)蓬勃發(fā)展，利用了時(shí)間、信息、倉(cāng)庫(kù)、配送和協(xié)作系統(tǒng)創(chuàng)造了更多價(jià)值，也為運(yùn)籌學(xué)提供了便利科學(xué)組織來(lái)源、運(yùn)輸、配送要求運(yùn)輸問(wèn)題越來(lái)越復(fù)雜，但其基本思想依然是實(shí)現(xiàn)現(xiàn)有資源的優(yōu)化配置。 3.1運(yùn)輸問(wèn)題的基本概念，一般的運(yùn)輸問(wèn)題是解決將某產(chǎn)品從幾個(gè)產(chǎn)地運(yùn)送到幾個(gè)銷售地的方法

2、，知道每個(gè)產(chǎn)地的供給量和每個(gè)銷售地的需求量，在知道各地間的運(yùn)送單價(jià)的基礎(chǔ)上，決定總運(yùn)送費(fèi)用最小化的方法。 平衡運(yùn)輸問(wèn)題的條件：1.明確啟運(yùn)地(產(chǎn)地)、目的地(銷售地)、供給量(產(chǎn)量)、需求量(銷售量)和單位成本。 2 .需求假設(shè)：每個(gè)啟運(yùn)地有一定的供應(yīng)量，所有供應(yīng)量必須送達(dá)目的地。 同樣，每個(gè)目的地都有一定的需求量，整個(gè)需求量必須滿足啟運(yùn)地。 總供給需求修訂。 3 .成本假設(shè)：從任何一個(gè)啟運(yùn)地到任何一個(gè)目的地的貨物配送成本與配送的數(shù)量呈線性比例關(guān)系，因此成本等于配送的單位成本乘以配送的數(shù)量(目的函數(shù)為線性)。 3.1運(yùn)輸問(wèn)題的基本概念，例4.1某公司生產(chǎn)有三個(gè)加工廠a1、a2、a3的產(chǎn)品，每日

3、產(chǎn)量分別為7噸、4噸、9噸該公司將這些個(gè)產(chǎn)品分別商品發(fā)貨到四個(gè)銷售點(diǎn)b1、b2、b3、b4，各銷售點(diǎn)的每日銷售量分別為從各工廠到各銷售小賣店的單位產(chǎn)品運(yùn)費(fèi)如表41所示。 詢問(wèn)該公司如何運(yùn)輸這些個(gè)產(chǎn)品，在滿足各銷售點(diǎn)需求量的基礎(chǔ)上，使總運(yùn)輸費(fèi)最小化表41從各工廠到各銷售點(diǎn)的單位產(chǎn)品運(yùn)輸價(jià)格(元/噸)，3.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型，(1)生產(chǎn)銷售平衡運(yùn)輸問(wèn)題數(shù)學(xué)模型是m個(gè)產(chǎn)地ai (元/噸) 具有m )和n個(gè)銷售地bj (j 1，2，)的4個(gè)大頭針地b1，b2，b3，b4的總銷售量為365620。 由于總生產(chǎn)率等于總銷售量，這個(gè)問(wèn)題是生產(chǎn)銷售平衡的運(yùn)輸問(wèn)題。 (1)將決策變量xij從產(chǎn)地a

4、i向銷售地bj的運(yùn)輸量(i1，2，3； j=1，2，3，4 ) (2)目標(biāo)函數(shù)本題的目的是使總運(yùn)費(fèi)最小化。 3.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型，(3)限制條件滿足產(chǎn)地產(chǎn)量(3個(gè)產(chǎn)地產(chǎn)品全部配送)銷售量(4個(gè)產(chǎn)地產(chǎn)品全部配送)并不負(fù)，3.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型，運(yùn)輸問(wèn)題是一個(gè)特殊的線性規(guī)劃問(wèn)題， 一般來(lái)說(shuō)，采用“表作業(yè)法”的例子4.1的電子表格模型、3.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型，運(yùn)輸問(wèn)題都有這樣的性質(zhì)(整數(shù)解性質(zhì))，如果其供給量和需求量都是整數(shù)，則任何可行解的運(yùn)輸問(wèn)題都必定有所有決策變量為整數(shù)的最佳解。 因此，沒(méi)有必要施加所有變量都是整數(shù)的制約。因?yàn)檫\(yùn)輸量多以卡車和擠壓筒等為

5、單位，卡車沒(méi)有裝滿的話就不經(jīng)濟(jì)。 整數(shù)解的性質(zhì)是運(yùn)輸量(運(yùn)輸方案)避免小數(shù)的麻煩。3.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型、(2)比運(yùn)輸問(wèn)題數(shù)學(xué)模型生產(chǎn)大(以銷售量小為基準(zhǔn))、3.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型、(3)比運(yùn)輸問(wèn)題數(shù)學(xué)模型生產(chǎn)大(滿足銷售量小)。 我們知道該工廠的每季度生產(chǎn)能力和每臺(tái)柴油引擎的生產(chǎn)成本如表44所示。 如果生產(chǎn)的柴油引擎不按季度交貨的話，每臺(tái)需要按季度儲(chǔ)藏、維護(hù)等費(fèi)用1500元。 在完成合同的情況下，要求作出該工廠年生產(chǎn)(包括儲(chǔ)存、維護(hù))費(fèi)用最少的決定。 表44各季度的生產(chǎn)能力和每臺(tái)柴油引擎的生產(chǎn)成本，3.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型，解：這是生產(chǎn)和儲(chǔ)存(庫(kù)存)問(wèn)

6、題，除采用第3章的方法外，還可以轉(zhuǎn)換為運(yùn)輸問(wèn)題。 由于按季度生產(chǎn)的柴油引擎不一定按季度交貨，所以將xij作為第i季度生產(chǎn)的第j季度交貨的柴油引擎數(shù)。 第i季度生產(chǎn)的第j季度交付的每臺(tái)柴油引擎的實(shí)際成本cij，將cij=第i季度的每臺(tái)生產(chǎn)成本0.15(j-i ) (儲(chǔ)藏、維護(hù)等費(fèi)用)第i季度生產(chǎn)的柴油引擎數(shù)視為第i家生產(chǎn)廠家的產(chǎn)量。 將第j季度交付的柴油引擎數(shù)量視為第j個(gè)銷售點(diǎn)的銷售量生產(chǎn)成本加上存儲(chǔ)、維護(hù)等費(fèi)用，視為運(yùn)輸費(fèi)。 將生產(chǎn)和儲(chǔ)藏問(wèn)題轉(zhuǎn)換為運(yùn)輸問(wèn)題，相關(guān)數(shù)據(jù)如表45所示。 3.2關(guān)于運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型、表45柴油引擎生產(chǎn)的數(shù)據(jù)，從表45可以看出，由于總生產(chǎn)率(生產(chǎn)能力)為2

7、5-35-30-10=100，總銷售量(需求量)為10-15-25-20=70，所以是生產(chǎn)比銷售還要大的運(yùn)輸問(wèn)題。 3.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型，這個(gè)生產(chǎn)和儲(chǔ)藏問(wèn)題(轉(zhuǎn)換為比銷售大的運(yùn)輸問(wèn)題)的數(shù)學(xué)模型，3.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型，例子4.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型，例子4.3某公司有兩個(gè)產(chǎn)地a1，a2到3個(gè)銷售點(diǎn)應(yīng)該如何調(diào)整運(yùn)費(fèi)，可以將總運(yùn)費(fèi)降到最低嗎？ 表46例4.3的運(yùn)輸費(fèi)表，3.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型，解：由表46可知，總生產(chǎn)率為78 45=123，總銷售額為53 36 65=154，銷售額大于生產(chǎn)。 數(shù)學(xué)模型是以xij為產(chǎn)地ai商品發(fā)貨給銷售地bj的

8、物品數(shù)量、3.2運(yùn)輸問(wèn)題數(shù)學(xué)模型和電子表格模型、例4.3的電子表格模型、3.3各種運(yùn)輸問(wèn)題變形的模型，在現(xiàn)實(shí)生活中很少滿足生產(chǎn)銷售平衡運(yùn)輸問(wèn)題的條件。 經(jīng)常出現(xiàn)一個(gè)特征近似但是其中一個(gè)或多個(gè)特征沒(méi)有滿足產(chǎn)銷平衡運(yùn)輸問(wèn)題的條件的運(yùn)輸問(wèn)題。 接下來(lái)，對(duì)(1)總供給大于市場(chǎng)總需求的特征進(jìn)行說(shuō)明。 各供給量(產(chǎn)量)表示從啟運(yùn)地發(fā)送的最大數(shù)量(不是一定的數(shù)值)。 (2)總供給小于市場(chǎng)總需求。 每個(gè)需求(銷售量)表示目標(biāo)接收的最大數(shù)量(不是固定值)。 (3)因?yàn)樵仆街写嬖谝粋€(gè)目的地的最小和最大需求，所以可以接受這些個(gè)兩個(gè)數(shù)值之間的所有數(shù)量(，)。 (4)配送時(shí)不能使用特定的啟運(yùn)地目的地定徑套(xij=0

9、)，(5)不是使總成本最小化，而是以配送數(shù)的總利益最大化為目標(biāo)。 (min max )，3.3各種運(yùn)輸問(wèn)題變形的建模，例4.4某公司決定使用3個(gè)有生產(chǎn)能力的工廠進(jìn)行4種全新產(chǎn)品的生產(chǎn)。由于每單位產(chǎn)品需要同等量的工作，所以工廠的有效生產(chǎn)能力按每天生產(chǎn)的任意產(chǎn)品數(shù)量進(jìn)行測(cè)量(參照表47的右端列)。 每個(gè)產(chǎn)品每天都有一定的需求量(見表47的最后一行)。 任何工廠都可以制造這些個(gè)產(chǎn)品，但工廠2不能生產(chǎn)產(chǎn)品3。 但是，如表47所示，每個(gè)產(chǎn)品的單位成本不同。 現(xiàn)在需要決定在哪個(gè)工廠生產(chǎn)什么樣的產(chǎn)品，能夠?qū)⒖偝杀究刂圃谧钚∠薅取?表47關(guān)于產(chǎn)品生產(chǎn)的數(shù)據(jù)，3.3各種運(yùn)輸問(wèn)題變形的建模、解：指定工廠生產(chǎn)的產(chǎn)品

10、可以視為運(yùn)輸問(wèn)題來(lái)解決。 在本問(wèn)題中，工廠2不能生產(chǎn)產(chǎn)品3，可以增加限制條件x230，并且是總供給(75 75 45=195 )市場(chǎng)總需求(20 30 30 40=120 )。 其數(shù)學(xué)模型，以xij為工廠i生產(chǎn)產(chǎn)品j的數(shù)量，3.3各種運(yùn)輸問(wèn)題變形的建模，例4.4的電子表格模型，產(chǎn)品4點(diǎn)在2個(gè)工廠生產(chǎn)，3.3各種運(yùn)輸問(wèn)題變形的建模，例4.5某公司在3個(gè)工廠專門生產(chǎn)1個(gè)產(chǎn)品。 今后4個(gè)月中，國(guó)內(nèi)不同地區(qū)的4名潛在客戶(批發(fā)商)大量訂貨的可能性很高。 因?yàn)轭櫩?是公司最好的顧客，他的全部訂單量應(yīng)該滿腳丫子的顧客2和顧客3也是公司的重要顧客，所以營(yíng)銷學(xué)經(jīng)理認(rèn)為至少要滿足他們的訂單的1/3。對(duì)于顧客4，

11、銷售經(jīng)理認(rèn)為不需要特別的照顧。 由于運(yùn)輸成本的不同，銷售一個(gè)產(chǎn)品得到的凈收益也不同，在很大程度上取決于哪個(gè)工廠提供哪個(gè)顧客(參照表48 )。 表48關(guān)于工廠供應(yīng)客戶的數(shù)據(jù)，3.3各種運(yùn)輸問(wèn)題變形的建模，解決方案：此問(wèn)題要求滿足不同客戶的需求(采購(gòu)量)，解決方案：實(shí)際供應(yīng)量最小，實(shí)際供應(yīng)量最大，目標(biāo)為利潤(rùn)最大，成本最小其數(shù)學(xué)模型以xij為工廠i提供給顧客j的產(chǎn)品數(shù)量，3.3各種運(yùn)輸問(wèn)題變形的模型化，例4.5的電子表格模型，3.4運(yùn)輸問(wèn)題的應(yīng)用例，例4.6某工廠的技術(shù)裝備通過(guò)銷售生產(chǎn)。 如表49所示，已知16月各月的生產(chǎn)能力、合同銷售量、單一設(shè)備的平均生產(chǎn)費(fèi)用。 據(jù)悉上年末有103臺(tái)庫(kù)存。 當(dāng)月生

12、產(chǎn)的設(shè)備如不當(dāng)月交貨，需運(yùn)往分廠倉(cāng)庫(kù)，每臺(tái)運(yùn)費(fèi)0.1萬(wàn)元，每臺(tái)月平均倉(cāng)庫(kù)費(fèi)、維護(hù)費(fèi)0.2萬(wàn)元。 因?yàn)?8月份的銷售額很淡薄，工廠全體停止了1個(gè)月的生產(chǎn)，所以在6月份完成銷售合同后，留下80臺(tái)庫(kù)存。 加班技術(shù)裝備每臺(tái)增加1萬(wàn)元。 如何安排16月份的生產(chǎn)，最大限度地減少生產(chǎn)總值(包括運(yùn)輸、倉(cāng)庫(kù)、維護(hù))的費(fèi)用，3.4運(yùn)輸問(wèn)題的應(yīng)用實(shí)例，例4.7華中金剛石鋸片工廠有兩個(gè)生產(chǎn)流水線，分別為直徑900-1800mm的大鋸片基體20000片，直徑350-800mm 公司全國(guó)共有25個(gè)售樓處，主要銷售區(qū)域集中在福建、廣東、廣西、四川、山東5個(gè)石材主產(chǎn)區(qū)。 為了完成總廠的要求，公司決定10%的產(chǎn)量與前期各客戶保

13、持聯(lián)系穩(wěn)定，保證將來(lái)的市場(chǎng)份額，而剩下的90%的產(chǎn)量合理分配給5個(gè)石材主產(chǎn)區(qū)和其他省區(qū)，面臨最大的利益。 各銷售區(qū)的最低需求、銷售固定費(fèi)、每張的平均運(yùn)輸費(fèi)、每張從總公司工廠倉(cāng)庫(kù)購(gòu)買的價(jià)格和當(dāng)?shù)劁N售價(jià)格差的貢獻(xiàn)等自然情況如表412所示。 為了實(shí)現(xiàn)毛利的最大化，應(yīng)如何分配給各銷售區(qū)域？ 表412的大鋸片和小鋸片相關(guān)數(shù)據(jù)，3.5分配問(wèn)題，在現(xiàn)實(shí)生活中，分配人多做某些工作(任務(wù))。 分配問(wèn)題的許多應(yīng)用程序用于鼎力相助管理員可以解決如何分配人員到以后的工作中去。 有些其他應(yīng)用程序?qū)C(jī)械、設(shè)備、工廠等分配給工作。分配問(wèn)題也稱為分配問(wèn)題，研究主要研究者和工作(塔斯克)之間如何一致，所有工作完成的效率優(yōu)化。

14、從形式上講，分配問(wèn)題給予一系列完成的工作和一系列完成的人員，需要解決的問(wèn)題是決定分配誰(shuí)來(lái)完成哪項(xiàng)工作。 3.5分配問(wèn)題、分配問(wèn)題的假設(shè)： (1)人數(shù)和工作數(shù)相等(2)每個(gè)人只能做一項(xiàng)工作(3)每項(xiàng)工作只能做一個(gè)人(4)有關(guān)每個(gè)人和每項(xiàng)工作組合的成本(單位成本) (5)將總成本降到最低分配3.5個(gè)問(wèn)題，將決策變量xij設(shè)為第i個(gè)人第j個(gè)辦事兒，并且將目標(biāo)函數(shù)系數(shù)cij設(shè)為第i個(gè)人完成第j個(gè)工作所需的單位成本。 平衡分配問(wèn)題的數(shù)學(xué)模型是3.5分配問(wèn)題，需要說(shuō)明分配問(wèn)題實(shí)際上是特殊的運(yùn)輸問(wèn)題。 其中啟運(yùn)地是人，目的地是工作。 但是，各啟運(yùn)地的供給量為1 (各人完成一項(xiàng)工作)，各目的地的需求量為1 (

15、各工作完成)。 由于運(yùn)輸問(wèn)題具有“整數(shù)解的性質(zhì)”，所以沒(méi)有必要施加所有決策變量都是0-1變量的制約。 指派問(wèn)題是一個(gè)特殊的線性修訂問(wèn)題，有匈牙利方法，但excel的“修訂解決”用“簡(jiǎn)單形法”解決。3.5分配問(wèn)題，例4.8某公司營(yíng)銷學(xué)經(jīng)理主辦一年一度的營(yíng)銷學(xué)區(qū)域經(jīng)理和銷售員參加的銷售協(xié)議會(huì)。 為了更好地安排這次會(huì)議，他安排了老張、王老板、小李、老劉四個(gè)人，每人負(fù)責(zé)以下工作： a、b、c和d。 因?yàn)槊總€(gè)人完成各塔斯克的時(shí)間和工資不同(如表414所示)。 如果詢問(wèn)分配方法，可以將總成本降到最低。 3.5分配問(wèn)題，解：這個(gè)問(wèn)題是典型的分配問(wèn)題。 單位成本是每個(gè)人工作的總工資薪金目標(biāo)是確定哪個(gè)人是哪個(gè)辦

16、事兒，總成本的最小供給量為1，每個(gè)人工作的需求量為1，每個(gè)人達(dá)到總?cè)藬?shù)(4人)和總塔斯克數(shù)(4個(gè)項(xiàng)目)，分配3.5分配問(wèn)題，數(shù)學(xué)模型： xij 3.5分配問(wèn)題、電子表格模型和3.6各種分配問(wèn)題的變形建模經(jīng)常遇到分配問(wèn)題的變形。 之所以將該這些個(gè)稱為形變是因?yàn)樗粷M足平衡的分配問(wèn)題的所有假設(shè)中的一個(gè)或多個(gè)。 一般來(lái)說(shuō)，(1)有的人不會(huì)辦事兒(對(duì)應(yīng)的xij0) (2)每個(gè)人完成一個(gè)任務(wù)，但任務(wù)比別人多(人少)。 (3)一個(gè)一個(gè)的任務(wù)只有一個(gè)人完成，但人比任務(wù)多(人少) (4)某人可以給云同步分配多個(gè)塔斯克(一個(gè)人可以做某事) (5)某人可以由多人共同完成(某人可以完成某事)。 (6)不是使總成本最小化，而是以分配相關(guān)的總利益最大化為目標(biāo)；(7)實(shí)際需要完成的塔斯克數(shù)不超過(guò)總?cè)藬?shù)，不超過(guò)總塔斯克數(shù)。 3.6各種分配問(wèn)題的變形建模，示例4.9主題見示例4.4。 也就是說(shuō)，某公司為了生產(chǎn)4種全新產(chǎn)品需要安排3個(gè)工廠。 相關(guān)數(shù)據(jù)已在表47中列出。 在示例4.4中，行政許可了產(chǎn)品的生產(chǎn)分解，這將產(chǎn)生與產(chǎn)品生產(chǎn)分解相關(guān)的隱性成本，包括額外的安裝、運(yùn)輸、管理成本等。 因此，管理者決定在禁止產(chǎn)品生產(chǎn)分解的同時(shí)對(duì)問(wèn)題進(jìn)行分析。 新問(wèn)題是，了解表47所示