第4章-运输问题和指派问题

第4章运输问题和指派问题东北财经大学工商管理学院3.3网络配送问题通过配送网络能以最小的成本完成货物的配送，称之为网络配送问题。在网络配送问题中，必须确定需求以及相应地确定需求的约束条件。确定需求约束的形式如下：提供的数量＝需求的数量第4章运输问题和指派问题东北财经大学工商管理学院3.3网络配送问题C2F2C1F1C3900元/个10个8个9个12个15个第4章运输问题和指派问题东北财经大学工商管理学院实用运筹学－运用Excel建模和求解第4章运输问题和指派问题第4章运输问题和指派问题东北财经大学工商管理学院本章内容要点运输问题的基本概念及其各种变形的建模与应用指派问题的基本概念及其各种变形的建模与应用第4章运输问题和指派问题东北财经大学工商管理学院本章节内容4.1运输问题基本概念4.2运输问题数学模型和电子表格模型4.3各种运输问题变形的建模4.4运输问题应用举例4.5指派问题4.6各种指派问题变形的建模第4章运输问题和指派问题东北财经大学工商管理学院本章主要内容框架图产销平衡（总产量等于总销量）产大于销（总产量大于总销量）销大于产（总产量小于总销量）运输问题数学模型和电子表格模型运输问题和指派问题各种变形的建模应用举例平衡指派问题（总人数等于总任务数）指派问题数学模型和电子表格模型各种变形的建模第4章运输问题和指派问题东北财经大学工商管理学院4.1运输问题基本概念运输问题最初起源于人们在日常生活中把某些物品或人们自身从一些地方转移到另一些地方，要求所采用的运输路线或运输方案是最经济或成本最低的，这就成为了一个运筹学问题。随着经济的不断发展，现代物流业蓬勃发展，如何充分利用时间、信息、仓储、配送和联运体系创造更多的价值，向运筹学提出了更高的挑战。要求科学地组织货源、运输和配送使得运输问题变得日益复杂，但是其基本思想仍然是实现现有资源的最优化配置。第4章运输问题和指派问题东北财经大学工商管理学院4.1运输问题基本概念一般的运输问题就是解决如何把某种产品从若干个产地调运到若干个销地，在每个产地的供应量和每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。平衡运输问题的条件：1.明确出发地（产地）、目的地（销地）、供应量（产量）、需求量（销量）和单位成本。2.需求假设：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足。即“总供应＝总需求”。3.成本假设：从任何一个出发地到任何一个目的地的货物配送成本与所配送的数量成线性比例关系，因此成本就等于配送的单位成本乘以所配送的数量（目标函数是线性的）。第4章运输问题和指派问题东北财经大学工商管理学院4.1运输问题基本概念例4.1某公司有三个加工厂A1、A2、A3生产某产品，每日的产量分别为：7吨、4吨、9吨；该公司把这些产品分别运往四个销售点B1、B2、B3、B4，各销售点每日销量分别为：3吨、6吨、5吨、6吨；从各工厂到各销售点的单位产品运价如表4-1所示。问该公司应如何调运这些产品，在满足各销售点的需要量的前提下，使总运费最少？表4-1各工厂到各销售点的单位产品运价（元/吨）B1B2B3B4产量（吨）A13113107A219284A3741059销量（吨）3656第4章运输问题和指派问题东北财经大学工商管理学院B2A2B1A1B3806585A3B475125100704.1运输问题基本概念第4章运输问题和指派问题东北财经大学工商管理学院4.2运输问题数学模型和电子表格模型销售点销售点加工厂A1A2┆AmB1B2…Bn产量a1a2┆am销量b1b2…bnc11c12…c1nc21c22…c2n┆┆cij┆cm1cm2…cmn第4章运输问题和指派问题东北财经大学工商管理学院4.2运输问题数学模型和电子表格模型（1）产销平衡运输问题的数学模型1111()()Min(1,2,,)s.t.(1,2,,)0(1,2,,;1,2,,)mnijijijnijijmijjiijzcxxaimxbjnximjn产量约束销量约束LLLL11mnijijab第4章运输问题和指派问题东北财经大学工商管理学院4.2运输问题数学模型和电子表格模型对于例4.1，其数学模型如下：首先，三个产地A1、A2、A3的总产量为7＋4＋9＝20；四个销地B1、B2、B3、B4的总销量为3＋6＋5＋6＝20。由于总产量等于总销量，故该问题是一个产销平衡的运输问题。(1)决策变量设xij为从产地Ai运往销地Bj的运输量(i＝1,2,3;j=1,2,3,4)（2）目标函数本问题的目标是使得总运输费最小111213142122232431323334Minz31131092874105xxxxxxxxxxxx第4章运输问题和指派问题东北财经大学工商管理学院4.2运输问题数学模型和电子表格模型（3）约束条件①满足产地产量（3个产地的产品都要全部配送出去）②满足销地销量（4个销地的产品都要全部得到满足）③非负111213142122232431323334111213142122232431323334112131122232Minz311310928741057493s.t.6xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx132333142434560(1,2,3;1,2,3,4)ijxxxxxxxij第4章运输问题和指派问题东北财经大学工商管理学院4.2运输问题数学模型和电子表格模型运输问题是一种特殊的线性规划问题，一般采用“表上作业法”求解运输问题，但Excel的“规划求解”还是采用“单纯形法”来求解。例4.1的电子表格模型第4章运输问题和指派问题东北财经大学工商管理学院4.2运输问题数学模型和电子表格模型需要注意的是：运输问题有这样一个性质（整数解性质），只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件。由于运输量经常以卡车、集装箱等为单位，如果卡车不能装满的话，就很不经济了。整数解性质就避免了运输量（运输方案）为小数的麻烦。第4章运输问题和指派问题东北财经大学工商管理学院4.2运输问题数学模型和电子表格模型（2）产大于销（供过于求）运输问题的数学模型（以满足小的销量为准）1111()()Minz(1,2,,)s.t.(1,2,,)0(1,2,,;1,2,,)mnijijijnijijmijjiijcxxaimxbjnximjn产量约束销量约束LLLL11mnijijab第4章运输问题和指派问题东北财经大学工商管理学院4.2运输问题数学模型和电子表格模型（3）销大于产（供不应求）运输问题的数学模型（以满足小的产量为准）1111()()Min(1,2,,)s.t.(1,2,,)0(1,2,,;1,2,,)mnijijijnijijmijjiijzcxxaimxbjnximjn产量约束销量约束LLLL11mnijijab第4章运输问题和指派问题东北财经大学工商管理学院4.2运输问题数学模型和电子表格模型例4.2某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表4－4所示。如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用1500元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最小的决策。表4－4各季度的生产能力及生产每台柴油机的成本季度生产能力（台）需求量（台）单位成本（万元）1251010.82351511.13302511.04102011.3第4章运输问题和指派问题东北财经大学工商管理学院例3.7某公司根据订单进行生产。已知半年内对某产品的需求量、单位生产费用和单位存储费用,还已知公司每月的生产能力为100，每月仓库容量为50。问：如何确定产品未来半年内每月最佳生产量和存储量，以使总费用最少。表3-10生产与库存的有关数据月份123456需求量504050455530单位生产费用825775850850775825单位存储费用4030352040404.2运输问题数学模型和电子表格模型第4章运输问题和指派问题东北财经大学工商管理学院解：(1)决策变量设每月生产量为xi(i=1,2,,6)，每月月末库存量为si(i=1,2,,6)。上月库存量（si-1）＋本月生产量（xi）-市场需求＝本月月末库存量（si）4.2运输问题数学模型和电子表格模型第4章运输问题和指派问题东北财经大学工商管理学院数学模型（线性规划模型）12345612345611122233344455566Minz82577585085077582540303520404050405045s.t.5530100(1,2,,6)50(1,2iixxxxxxssssssxssxssxssxssxssxsxisiL,,6),0(1,2,,6)iixsiLL4.2运输问题数学模型和电子表格模型第4章运输问题和指派问题东北财经大学工商管理学院例3.7的电子表格模型4.2运输问题数学模型和电子表格模型第4章运输问题和指派问题东北财经大学工商管理学院4.2运输问题数学模型和电子表格模型解：这是一个生产与储存（库存）问题，除了采用第3章的方法外，还可以转化为运输问题来做。由于每个季度生产出来的柴油机不一定当季交货，所以设xij为第i季度生产的第j季度交货的柴油机数。则第i季度生产的第j季度交货的每台柴油机的实际成本cij为：cij=第i季度每台的生产成本+0.15(j-i)（储存、维护等费用）把第i季度生产的柴油机数看作第i个生产厂商的产量；把第j季度交货的柴油机数看作第j个销售点的销量；生产成本加储存、维护等费用看作运费。将生产与储存问题转化为运输问题，相关数据见表4－5。第4章运输问题和指派问题东北财经大学工商管理学院4.2运输问题数学模型和电子表格模型1234生产能力110.810.9511.1011.2525211.1011.2511.4035311.0011.1530411.3010需求量10152520由表4－5可知，总产量（生产能力）为25+35+30+10=100，总销量（需求量）为10+15+25+20=70，因此是产大于销的运输问题季度生产能力（台）需求量（台）单位成本（万元）1251010.82351511.13302511.04102011.3第4章运输问题和指派问题东北财经大学工商管理学院4.2运输问题数学模型和电子表格模型该生产与储存问题（转化为产大于销的运输问题）的数学模型为111213142223243334Minz10.8010.9511.1011.2511.1011.2511.4011.0011.15xxxxxxxxx441112131422232433344411122213233311.3025353010s.t.1015xxxxxxxxxxxxxxxxx1424344425200(,1,2,3,4;)ijxxxxxijij第4章运输问题和指派问题东北财经大学工商管理学院4.2运输问题数学模型和电子表格模型例4.2的电子表格模型第4章运输问题和指派问题东北财经大学工商管理学院4.2运输问题数学模