運輸問題和指派問題

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

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

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

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

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

6、題，除采用第3章的方法外，還可以轉(zhuǎn)換為運輸問題。 由于按季度生產(chǎn)的柴油引擎不一定按季度交貨，所以將xij作為第i季度生產(chǎn)的第j季度交貨的柴油引擎數(shù)。 第i季度生產(chǎn)的第j季度交付的每臺柴油引擎的實際成本cij，將cij=第i季度的每臺生產(chǎn)成本0.15(j-i ) (儲藏、維護等費用)第i季度生產(chǎn)的柴油引擎數(shù)視為第i家生產(chǎn)廠家的產(chǎn)量。 將第j季度交付的柴油引擎數(shù)量視為第j個銷售點的銷售量生產(chǎn)成本加上存儲、維護等費用，視為運輸費。 將生產(chǎn)和儲藏問題轉(zhuǎn)換為運輸問題，相關(guān)數(shù)據(jù)如表45所示。 3.2關(guā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)比銷售還要大的運輸問題。 3.2運輸問題數(shù)學(xué)模型和電子表格模型，這個生產(chǎn)和儲藏問題(轉(zhuǎn)換為比銷售大的運輸問題)的數(shù)學(xué)模型，3.2運輸問題數(shù)學(xué)模型和電子表格模型，例子4.2運輸問題數(shù)學(xué)模型和電子表格模型，例子4.3某公司有兩個產(chǎn)地a1，a2到3個銷售點應(yīng)該如何調(diào)整運費，可以將總運費降到最低嗎？ 表46例4.3的運輸費表，3.2運輸問題數(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運輸問題數(shù)學(xué)模型和電子表格模型、例4.3的電子表格模型、3.3各種運輸問題變形的模型，在現(xiàn)實生活中很少滿足生產(chǎn)銷售平衡運輸問題的條件。 經(jīng)常出現(xiàn)一個特征近似但是其中一個或多個特征沒有滿足產(chǎn)銷平衡運輸問題的條件的運輸問題。 接下來，對(1)總供給大于市場總需求的特征進行說明。 各供給量(產(chǎn)量)表示從啟運地發(fā)送的最大數(shù)量(不是一定的數(shù)值)。 (2)總供給小于市場總需求。 每個需求(銷售量)表示目標接收的最大數(shù)量(不是固定值)。 (3)因為云同步中存在一個目的地的最小和最大需求，所以可以接受這些個兩個數(shù)值之間的所有數(shù)量(，)。 (4)配送時不能使用特定的啟運地目的地定徑套(xij=0

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

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

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

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

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

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

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

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