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

实用运筹学

－运用Excel建模和求解第4章运输问题和指派问题本章内容要点运输问题的根本概念及其各种变形的建模与应用指派问题的根本概念及其各种变形的建模与应用本章节内容4.1运输问题根本概念4.2运输问题数学模型和电子表格模型4.3各种运输问题变形的建模4.4运输问题应用举例4.5指派问题4.6各种指派问题变形的建模本章主要内容框架图4.1运输问题根本概念运输问题最初起源于人们在日常生活中把某些物品或人们自身从一些地方转移到另一些地方，要求所采用的运输路线或运输方案是最经济或本钱最低的，这就成为了一个运筹学问题。随着经济的不断开展，现代物流业蓬勃开展，如何充分利用时间、信息、仓储、配送和联运体系创造更多的价值，向运筹学提出了更高的挑战。要求科学地组织货源、运输和配送使得运输问题变得日益复杂，但是其根本思想仍然是实现现有资源的最优化配置。4.1运输问题根本概念一般的运输问题就是解决如何把某种产品从假设干个产地调运到假设干个销地，在每个产地的供给量和每个销地的需求量，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。平衡运输问题的条件：1. 明确出发地〔产地〕、目的地〔销地〕、供给量〔产量〕、需求量〔销量〕和单位本钱。2. 需求假设：每一个出发地都有一个固定的供给量，所有的供给量都必须配送到目的地。与之类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足。即“总供给＝总需求〞。3. 本钱假设：从任何一个出发地到任何一个目的地的货物配送本钱与所配送的数量成线性比例关系，因此本钱就等于配送的单位本钱乘以所配送的数量〔目标函数是线性的〕。4.1运输问题根本概念例4.1某公司有三个加工厂A1、A2、A3生产某产品，每日的产量分别为：7吨、4吨、9吨；该公司把这些产品分别运往四个销售点B1、B2、B3、B4，各销售点每日销量分别为：3吨、6吨、5吨、6吨；从各工厂到各销售点的单位产品运价如表4－1所示。问该公司应如何调运这些产品，在满足各销售点的需要量的前提下，使总运费最少？表4－1各工厂到各销售点的单位产品运价〔元/吨〕B1B2B3B4产量（吨）A13113107A219284A3741059销量（吨）36564.2运输问题数学模型和电子表格模型〔1〕产销平衡运输问题的数学模型具有m个产地Ai〔i＝1,2,,m〕和n个销地Bj〔j＝1,2,,n〕的运输问题的数学模型为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〕目标函数本问题的目标是使得总运输费最小。4.2运输问题数学模型和电子表格模型〔3〕约束条件①满足产地产量〔3个产地的产品都要全部配送出去〕②满足销地销量〔4个销地的产品都要全部得到满足〕③非负4.2运输问题数学模型和电子表格模型运输问题是一种特殊的线性规划问题，一般采用“表上作业法〞求解运输问题，但Excel的“规划求解〞还是采用“单纯形法〞来求解。例4.1的电子表格模型4.2运输问题数学模型和电子表格模型需要注意的是：运输问题有这样一个性质〔整数解性质〕，只要它的供给量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件。由于运输量经常以卡车、集装箱等为单位，如果卡车不能装满的话，就很不经济了。整数解性质就防止了运输量〔运输方案〕为小数的麻烦。4.2运输问题数学模型和电子表格模型〔2〕产大于销〔供过于求〕运输问题的数学模型〔以满足小的销量为准〕4.2运输问题数学模型和电子表格模型〔3〕销大于产〔供不应求〕运输问题的数学模型〔以满足小的产量为准〕4.2运输问题数学模型和电子表格模型例4.2某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。该厂各季度的生产能力及生产每台柴油机的本钱如表4－4所示。如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用1500元。要求在完成合同的情况下，做出使该厂全年生产〔包括储存、维护〕费用最小的决策。表4－4各季度的生产能力及生产每台柴油机的本钱季度生产能力（台）单位成本（万元）12510.823511.133011.041011.34.2运输问题数学模型和电子表格模型解：这是一个生产与储存〔库存〕问题，除了采用第3章的方法外，还可以转化为运输问题来做。由于每个季度生产出来的柴油机不一定当季交货，所以设xij为第i季度生产的第j季度交货的柴油机数。那么第i季度生产的第j季度交货的每台柴油机的实际本钱cij为：cij=第i季度每台的生产本钱+0.15(j-i)〔储存、维护等费用〕把第i季度生产的柴油机数看作第i个生产厂商的产量；把第j季度交货的柴油机数看作第j个销售点的销量；生产本钱加储存、维护等费用看作运费。将生产与储存问题转化为运输问题，相关数据见表4－5。4.2运输问题数学模型和电子表格模型表4－5柴油机生产的相关数据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，因此是产大于销的运输问题。4.2运输问题数学模型和电子表格模型该生产与储存问题〔转化为产大于销的运输问题〕的数学模型为4.2运输问题数学模型和电子表格模型例4.2的电子表格模型4.2运输问题数学模型和电子表格模型例4.3某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表4－6所示。问应如何调运，可使得总运输费最小？表4－6例4.3的运输费用表

B1B2B3产量A113151278A211292245销量533665（销大于产）4.2运输问题数学模型和电子表格模型解：由表4－6知，总产量为78+45=123，总销量为53+36+65=154，销大于产(供不应求)。数学模型如下：设xij为产地Ai运往销地Bj的物品数量4.2运输问题数学模型和电子表格模型例4.3的电子表格模型4.3各种运输问题变形的建模现实生活中符合产销平衡运输问题每一个条件的情况很少。一个特征近似但其中的一个或者几个特征却并不符合产销平衡运输问题条件的运输问题却经常出现。下面是要讨论的一些特征：〔1〕总供给大于总需求。每一个供给量〔产量〕代表了从其出发地中配送出去的最大数量〔而不是一个固定的数值,≤〕。〔2〕总供给小于总需求。每一个需求量〔销量〕代表了在其目的地中所接收到的最大数量〔而不是一个固定的数值,≤〕。〔3〕一个目的地同时存在着最小需求和最大需求，于是所有在这两个数值之间的数量都是可以接收的〔≥,≤〕。〔4〕在配送中不能使用特定的出发地—目的地组合〔xij=0〕。〔5〕目标是使与配送数量有关的总利润最大而不是使总本钱最小。〔Min－>Max〕4.3各种运输问题变形的建模例4.4某公司决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量〔见表4－7的最右列〕。而每种产品每天有一定的需求量〔见表4－7的最后一行〕。每家工厂都可以制造这些产品，除了工厂2不能生产产品3以外。然而，每种产品在不同工厂中的单位本钱是有差异的〔如表4－7所示〕。现在需要决定的是在哪个工厂生产哪种产品，可使总本钱最小。表4－7产品生产的有关数据单位成本（元）生产能力产品1产品2产品3产品4工厂24029－2375工厂33730272145需求量203030404.3各种运输问题变形的建模解：指定工厂生产产品可以看作运输问题来求解。此题中，工厂2不能生产产品3，这样可以增加约束条件x23＝0；并且，总供给〔75+75+45=195〕>总需求〔20+30+30+40=120〕。其数学模型如下：设xij为工厂i生产产品j的数量4.3各种运输问题变形的建模例4.4的电子表格模型产品4分在2个工厂生产4.3各种运输问题变形的建模例4.5某公司在3个工厂中专门生产一种产品。在未来的4个月中，有四个处于国内不同区域的潜在顾客〔批发商〕很可能大量订购。顾客1是公司最好的顾客，所以他的全部订购量都应该满足；顾客2和顾客3也是公司很重要的顾客，所以营销经理认为作为最低限度至少要满足他们订单的1/3；对于顾客4，销售经理认为并不需要进行特殊考虑。由于运输本钱上的差异，销售一个产品得到的净利润也不同，很大程度上取决于哪个工厂供给哪个顾客〔见表4－8〕。问应向每一个顾客供给多少货物，以使公司总利润最大？表4－8工厂供给顾客的相关数据单位利润（元）产量顾客1顾客2顾客3顾客4工厂1554246538000工厂2371832485000工厂3295951357000最小采购量7000300020000最大采购量70009000600080004.3各种运输问题变形的建模解：该问题要求满足不同顾客的需求〔采购量〕，解决方法：实际供给量最小采购量实际供给量最大采购量

目标是利润最大，而不是本钱最小。其数学模型如下：设xij为工厂i供给给顾客j的产品数量4.3各种运输问题变形的建模例4.5的电子表格模型4.4运输问题应用举例例4.6某厂生产设备是以销定产的。1～6月份各月的生产能力、合同销量和单台设备平均生产费用，如表4－9所示。上年末库存103台。如果当月生产出来的设备当月不交货，那么需要运到分厂库房，每台增加运输本钱0.1万元，每台设备每月的平均仓储费、维护费为0.2万元。7～8月份为销售淡季，全厂停产1个月，因此在6月份完成销售合同后还要留出库存80台。加班生产设备每台增加本钱1万元。问应如何安排1～6月份的生产，使总的生产〔包括运输、仓储、维护〕费用最少？月份正常生产能力（台）加班生产能力（台）合同销量（台）单台费用（万元）1月6010104152月501075143月902011513.54月10040160135月10040103136月80407013.54.4运输问题应用举例解：这是一个生产与储存问题，但可以转化为运输问题来做。〔是否可以采用第3章的方法做？同学们可以试试，然后进行比较〕生产方案不变，但总费用为：8329.7万元根据条件可以列出生产能力〔正常生产能力和加班生产能力〕和销量以及运价表〔P120〕数学模型P120－121电子表格模型P122求解结果P1234.4运输问题应用举例例4.7华中金刚石锯片厂有两条生产线，分别生产直径900-1800mm大锯片基体20000片，直径350-800mm中小锯片基体40000片。公司在全国有25个销售网点，主要销售区域集中在福建、广东、广西、四川、山东5个石材主产区。为完成总厂的要求，公司决定一方面拿出10%的产量稳定与前期各个客户的联系以保证将来的市场区域份额，另一方面，面临如何将剩余的90%的产量合理分配给五个石材主产区和其他省区，以获取最大的利润。各个销售区的最低需求、销售固定费用、每片平均运费、每片从总厂库房的购进价与当地的销售价差奉献等自然情况见表4－12。问应如何分配给各个销售区，才能使得总利润为最大？4.4运输问题应用举例解：该问题数据较多，但是经过分析，其产量在最低需求和最高需求之间，并且目标函数是最大利润，可以化简为表4－13〔P124〕数学模型P124电子表格模型P125求解结果P1264.5指派问题在现实生活中，经常会遇到指派人员做某项工作〔任务〕的情况。指派问题的许多应用是用来帮助管理人员解决如何为一项即将开展的工作指派人员的问题。其他的一些应用如为工作指派机器、设备或工厂等。指派问题也称分配问题，主要研究人和工作〔任务〕间如何匹配，以使所有工作完成的效率实现最优化。形式上，指派问题给定了一系列所要完成的工作以及一系列完成工作的人员，所需要解决的问题就是要确定出指派哪个人去完成哪项工作。4.5指派问题指派问题的假设：〔1〕人的数量和工作的数量相等；〔2〕每个人只能完成一项工作；〔3〕每项工作只能由一个人来完成；〔4〕每个人和每项工作的组合都会有一个相关的本钱〔单位本钱〕；〔5〕目标是要确定如何指派才能使总本钱最小。4.5指派问题设决策变量xij为第i个人做第j项工作，而目标函数系数cij为第i个人完成第j项工作所需要的单位本钱。平衡指派问题的数学模型为4.5指派问题需要说明的是：指派问题实际上是一种特殊的运输问题。其中出发地是人，目的地是工作。只不过，每一个出发地的供给量都为1〔因为每个人都要完成一项工作〕，每一个目的地的需求量都为1〔因为每项工作都要完成〕。由于运输问题有“整数解性质〞，因此，没有必要加上所有决策变量都是0-1变量的约束。指派问题是一种特殊的线性规划问题，有一种快捷的求解方法：匈牙利方法〔HungarianMethod〕，但Excel的“规划求解〞还是采用“单纯形法〞来求解。4.5指派问题例4.8某公司的营销经理将要主持召开一年一度的由营销区域经理以及销售人员参加的销售协商会议。为了更好地安排这次会议，他安排小张、小王、小李、小刘等四个人，每个人负责完成下面的一项工作：A、B、C和D。由于每个人完成每项任务的时间和工资不同〔如表4－14所示〕。问如何指派，可使总本钱最小。人员每一项工作所需要的时间（小时）每小时工资（元）工作A工作B工作C工作D小张3541274014小王4745325112小李3956364313小刘32512546154.5指派问题解：该问题是一个典型的指派问题。单位本钱为每个人做每项工作的总工资目标是要确定哪个人做哪一项工作，使总本钱最小供给量为1代表每个人都只能完成一项工作需求量为1代表每项工作也只能有一个人来完成总人数〔4人〕和总任务数〔4项〕相等4.5指派问题数学模型：设xij为指派人员i去做工作j〔i，j＝1,2,3,4)4.5指派问题电子表格模型4.6各种指派问题变形的建模经常会遇到指派问题的变形，之所以称它们为变形，是因为它们都不满足平衡指派问题所有假设之中的一个或者多个。一般考虑下面的一些特征：〔1〕有些人并不能进行某项工作〔相应的xij＝0〕;〔2〕虽然每个人完成一项任务，但是任务比人多(人少事多);〔3〕虽然每一项任务只由一个人完成，但是人比任务多〔人多事少〕；〔4〕某人可以同时被指派给多个任务〔一人可做几件事〕；〔5〕某事可以由多人共同完成〔一事可由多人完成〕；〔6〕目标是与指派有关的总利润最大而不是使总本钱最小；〔7〕实际需要完成任务数不超过总人数也不超过总任务数。4.6各种指派问题变形的建模例4.9题目见例4.4，即某公司需要安排三个工厂来生产四种新产品，相关的数据在表4－7中已经给出。在例4.4中，允许产品生产分解，但这将产生与产品生产分解相关的隐性本钱〔包括额外的设置、配送和管理本钱等〕。因此，管理人员决定在禁止产品生产分解发生的情况下对问题进行分析。 新问题描述为：如表4－7所示的数据，问如何把每一个工厂指派给至少一个新产品〔每一种产品只能在一个工厂生产〕，使总本钱到达最小？4.6各种指派问题变形的建模解：该问题可视为指派工厂生产产品问题，工厂可以看作指派问题中的人，产品那么可以看作需要完成的工作〔任务〕。由于有四种产品和三个工厂，所以就有两个工厂各只能生产一种新产品，第三个工厂生产两种新产品。只有工厂1和工厂2有生产两种产品的能力。这里涉及如何把运输问题转换为指派问题，关键所在是数据转换。4.6各种指派问题变形的建模数据转换：〔1〕单位指派本钱:原来的单位本钱转换成整批本钱〔＝单位本钱×需求量〕，即单位指派本钱为每个工厂生产每种产品的本钱。〔2〕供给量和需求量的转换问题：三个工厂生产四种产品，但一种产品只能在一个工厂生产，根据生产能力，工厂3只能生产一种产品〔供给量为1〕，而工厂1和工厂2可以生产2种产品〔供给量为2〕，而产品的需求量为1。还有“总供给〔2+2+1=5〕>总需求〔1+1+1+1=4〕〞,为人多事少的指派问题。4.6各种指派问题变形的建模数学模型：设xij为指派工厂i生产产品j〔i=1,2,3;j=1,2,3,4)4.6各种指派问题变形的建模电子表格模型4.6各种指派问题变形的建模例4.10一家制药公司，为了提升企业的竞争力，决定加大科研力度。在研究了市场的需要，分析了当前药物的缺乏并且拜会了大量对有良好前景的医药领域进行研究的科学家之后，决定由五位科学家开发五个工程。为了保证这些科学家都能够到他们感兴趣的工程中去，为此建立了一个投标系统。这五位科学家每个人都有1000点的投标点。他们向每一个工程投标，并且把较多的投标点投向自己最感兴趣的工程中。表4－15显示了这5位科学家进行投标的情况。4.6各种指派问题变形的建模表4－15科学家工程投标表投标点a项目b项目c项目d项目e项目李尔博士100400200200100朱诺博士020080000刘哲博士100100100100600王凯博士2671539945130罗林博士1003333348004.6各种指派问题变形的建模分析：决定要对一些可能发生的情况进行评估。〔1〕根据所给出的投标情况，需要为每一个工程指派一位资深的科学家并且使得科学家的总满意度最高。那么应当怎样进行指派？〔人数与工程数相等〕P133－134〔2〕罗林博士接到了北大医学院的邀请去完成一个教学任务，而公司却非常想把她留下来。但是北大的声望会使她离开公司。如果这种情况真的发生的话，公司就只有放弃那个最缺乏热情的工程。公司应当放弃那一个工程？〔人少工程多〕P134－1354.6各种指派问题变形的建模〔3〕当然公司并不愿意放弃任何一个工程。公司决定让朱诺博士或者王凯博士同时领导两个工程。在只有4位科学家的情况下，让哪一位科学家领导哪一个工程才能使得对工程的热情最大？〔有人可以同时领导两个工程〕P134，136〔4〕还是来分析拥有5位科学家的情况，但由于各方面的原因，有三位科学家不能领导几个特定的工程，具体如表4－16〔P137〕所示。由于不能领导，需重新调整这三位科学家的投标点，使其总投标点还是1000点，具体的调整方法是将不能领导的投标点全部投到他自己最感兴趣的工程上。在这种情况下，让哪个科学家领导哪个工程才能使得对工程的总热情最大？〔有人不能领导几个特