运筹学中的运输问题演示文稿

运筹学中的运输问题演示文稿当前1页，总共46页。本章内容要点运输问题的基本概念及其各种变形的建模与应用指派问题的基本概念及其各种变形的建模与应用当前2页，总共46页。本章节内容1运输问题基本概念2运输问题数学模型和电子表格模型3各种变形的运输问题建模4运输问题应用举例5指派问题6各种变形的指派问题建模当前3页，总共46页。产大于销（总产量大于总销量）运输问题数学模型和电子表格模型各种变形的建模应用举例指派问题数学模型和电子表格模型本章主要内容框架图产销平衡（总产量等于总销量）销大于产（总产量小于总销量）运输问题和指派问题平衡指派问题（总人数等于总任务数）各种变形的建模当前4页，总共46页。1运输问题运输问题最初起源于人们在日常生活中把某些物品或人们自身从一些地方转移到另一些地方，要求所采用的运输路线或运输方案是最经济或成本最低的，这就成为了一个运筹学问题。随着经济的不断发展，现代物流业蓬勃发展，如何充分利用时间、信息、仓储、配送和联运体系创造更多的价值，向运筹学提出了更高的挑战。要求科学地组织货源、运输和配送使得运输问题变得日益复杂，但是其基本思想仍然是实现现有资源的最优化配置。当前5页，总共46页。1运输问题基本概念一般的运输问题就是解决如何把某种产品从若干个产地调运到若干个销地，在每个产地的供应量和每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案。平衡运输问题的条件：

1.明确出发地（产地）、目的地（销地）、供应量（产量）、需求 量（销量）和单位成本。

2.需求假设：每一个出发地都有一个固定的供应量，所有的供应量 都必须配送到目的地。与之类似，每一个目的地都有一个固定的 需求量，整个需求量都必须由出发地满足。即“总供应＝总需 求”。

3.成本假设：从任何一个出发地到任何一个目的地的货物配送成本 与所配送的数量成线性比例关系，因此成本就等于配送的单位成 本乘以所配送的数量（目标函数是线性的）。当前6页，总共46页。1运输问题基本概念例1某公司有三个加工厂A1、A2、A3生产某产品，每日的产量分别为：7吨、4吨、9吨；该公司把这些产品分别运往四个销售点B1、B2、B3、B4，各销售点每日销量分别为：3吨、6吨、5吨、6吨；从各工厂到各销售点的单位产品运价如表1所示。问该公司应如何调运这些产品，在满足各销售点的需要量的前提下，使总运费最少？

表1各工厂到各销售点的单位产品运价（元/吨）B1B2B3B4产量（吨）749A1A2A3销量（吨）3173119463210510856当前7页，总共46页。对于例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）目标函数本问题的目标是使得总运输费最小Minz=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24+7x31+4x32+10x33+5x34当前8页，总共46页。（3）约束条件①满足产地产量 （3个产地的产 品都要全部配 送出去）②满足销地销量 （4个销地的产 品都要全部得 到满足）③非负当前9页，总共46页。2运输问题数学模型和电子表格模型运输问题是一种特殊的线性规划问题，一般采用“表上作业法”求解运输问题，但Excel的“规划求解”工具还是采用“单纯形法”来求解。例1的电子表格模型当前10页，总共46页。2运输问题数学模型和电子表格模型（1）产销平衡运输问题的数学模型 具有m个产地Ai（i＝1,2,…,m）和n个销地

Bj（j＝1,2,…,n）的运输问题的数学模型为当前11页，总共46页。2运输问题数学模型和电子表格模型需要注意的是：运输问题有这样一个性质（整数解性质），只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件。由于运输量经常以卡车、集装箱等为单位，如果卡车不能装满的话，就很不经济了。整数解性质就避免了运输量（运输方案）为小数的麻烦。当前12页，总共46页。当前13页，总共46页。（以满足小的产量为准）ij=（3）销大于产（供不应求）运输问题当前14页，总共46页。

2运输问题数学模型和电子表格模型例2某厂按合同规定须于当年每个季度末分别提供10，15，25，20台同一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如表所示。如果生产出来的柴油机当季不交货的，每台每积压一个季度需储存、维护等费用1500元。要求在完成合同的情况下，做出使该厂全年生产（包括储存、维护）费用最小的决策。

各季度的生产能力及生产每台柴油机的成本季度生产能力（台）单位成本（万元）12342535301010.811.111.011.3当前15页，总共46页。2运输问题数学模型和电子表格模型解：这是一个生产与储存（库存）问题，可以转化为运输问题来做。由于每个季度生产出来的柴油机不一定当季交货，所以设xij为第i季度生产的第j季度交货的柴油机数。则第i季度生产的第j季度交货的每台柴油机的实际成本cij为：

cij=第i季度每台的生产成本+0.15(j-i)（储存、维护等费用）

把第i季度生产的柴油机数看作第i个生产厂商的产量；把第j季度交货的柴油机数看作第j个销售点的销量；生产成本加储存、维护等费用看作运费。将生产与储存问题转化为运输问题，相关数据见表。当前16页，总共46页。2运输问题数学模型和电子表格模型

柴油机生产的相关数据

由表可知，总产量（生产能力）为

25+35+30+10=100，总销量（需求量）为10+15+25+20=70，因此是产大于销的运输问题。1234生产能力10.810.9511.1012311.1011.2511.0011.2511.40113010需求量10152520当前17页，总共46页。该生产与储存问题（转化为产大于销的运输问题）的数学模型为2运输问题数学模型和电子表格模型

Minz=10.80x11+10.95x12+11.10x13+11.25x14

+11.10x22+11.25x23+11.40x24

+11.00x33+11.15x34+11.30x44当前18页，总共46页。2运输问题数学模型和电子表格模型例2的电子表格模型当前19页，总共46页。

2运输问题数学模型和电子表格模型例3某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示。问应如何调运，可使得总运输费最小？

例3运输费用表B1B2B3产量A1A2销量1311531529361222657845（销大于产）当前20页，总共46页。2运输问题数学模型和电子表格模型解：由表知，总产量为78+45=123，总销量为53+36+65=154，销大于产(供不应求)。数学模型如下：设xij为产地Ai运往销地Bj的物品数量当前21页，总共46页。2运输问题数学模型和电子表格模型例3的电子表格模型当前22页，总共46页。3各种变形的运输问题建模现实生活中符合产销平衡运输问题每一个条件的情况很少。一个特征近似但其中的一个或者几个特征却并不符合产销平衡运输问题条件的运输问题却经常出现。下面是要讨论的一些特征：（1）总供应大于总需求。每一个供应量（产量）代表了从其出发地中配送出去的最大数量（而不是一个固定的数值,≤）。（2）总供应小于总需求。每一个需求量（销量）代表了在其目的地中所接收到的最大数量（而不是一个固定的数值,≤）。（3）一个目的地同时存在着最小需求和最大需求，于是所有在这两个数值之间的数量都是可以接收的（≥,≤）。（4）在配送中不能使用特定的出发地—目的地组合（xij=0）。（5）目标是使与配送数量有关的总利润最大而不是使总成本最小。（Min－>Max）当前23页，总共46页。

3各种变形的运输问题建模例4某公司决定使用三个有生产余力的工厂进行四种新产品的生产。每单位产品需要等量的工作，所以工厂的有效生产能力以每天生产的任意种产品的数量来衡量（见表的最右列）。而每种产品每天有一定的需求量（见表的最后一行）。每家工厂都可以制造这些产品，除了工厂2不能生产产品3以外。然而，每种产品在不同工厂中的单位成本是有差异的（如表所示）。 现在需要决定的是在哪个工厂生产哪种产品，可使总成本最小。

表产品生产的有关数据

单位成本（元） 生产能力产品1产品2产品3产品4757545工厂1工厂2工厂3需求量414037202729303028－273024232140当前24页，总共46页。解：指定工厂生产产品可以看作运输问题来求解。本题中，工厂2不能生产产品3，这样可以增加约束条件；并且，总供应x23＝0（75+75+45=195）>总需求（20+30+30+40=120）。其数学模型如下： 设xij为工厂i生产产品j的数量3各种变形的运输问题建模当前25页，总共46页。3各种变形的运输问题建模例4的电子表格模型产品4分在2个工厂生产当前26页，总共46页。

3各种变形的运输问题建模例5某公司在3个工厂中专门生产一种产品。在未来的4个月中，有四个处于国内不同区域的潜在顾客（批发商）很可能大量订购。顾客1是公司最好的顾客，所以他的全部订购量都应该满足；顾客2和顾客3也是公司很重要的顾客，所以营销经理认为作为最低限度至少要满足他们订单的1/3；对于顾客4，销售经理认为并不需要进行特殊考虑。由于运输成本上的差异，销售一个产品得到的净利润也不同，很大程度上取决于哪个工厂供应哪个顾客（见表）。问应向每一个顾客供应多少货物，以使公司总利润最大？ 表4-8工厂供应顾客的相关数据产量单位利润（元）顾客1顾客2顾客3顾客4800050007000工厂1工厂2工厂3最小采购量最大采购量55372970007000421859300090004632512000600053483508000当前27页，总共46页。3各种变形的运输问题建模解：该问题要求满足不同顾客的需求（采购量），解决办法：实际供给量≥最小采购量实际供给量≤最大采购量 目标是利润最大，而不是成本最小。其数学模型如下： 设xij为工厂i供应给顾客j的产品数量当前28页，总共46页。3各种变形的运输问题建模例5的电子表格模型当前29页，总共46页。4运输问题应用举例

例6某厂生产设备是以销定产的。已知1～6月份各月的生产能力、合 同销量和单台设备平均生产费用，如表所示。 已知上年末库存103台。如果当月生产出来的设备当月不交货，则 需要运到分厂库房，每台增加运输成本0.1万元，每台设备每月的平均 仓储费、维护费为0.2万元。7～8月份为销售淡季，全厂停产1个月， 因此在6月份完成销售合同后还要留出库存80台。加班生产设备每台增 加成本1万元。问应如何安排1～6月份的生产，使总的生产（包括运输、 仓储、维护）费用最少？月份1月2月3月4月5月6月正常生产能力（台）60509010010080加班生产能力（台）101020404040合同销量（台）1047511516010370单台费用（万元）151413.5131313.5当前30页，总共46页。4运输问题应用举例例7华中金刚石锯片厂有两条生产线，分别生产直径900-1800mm大锯片基体20000片，直径350-800mm中小锯片基体40000片。公司在全国有25个销售网点，主要销售区域集中在福建、广东、广西、四川、山东5个石材主产区。为完成总厂的要求，公司决定一方面拿出10%的产量稳定与前期各个客户的联系以保证将来的市场区域份额，另一方面，面临如何将剩余的90%的产量合理分配给五个石材主产区和其他省区，以获取最大的利润。各个销售区的最低需求、销售固定费用、每片平均运费、每片从总厂库房的购进价与当地的销售价差贡献等自然情况见表。问应如何分配给各个销售区，才能使得总利润为最大？当前31页，总共46页。4运输问题应用举例当前32页，总共46页。5指派问题在现实生活中，经常会遇到指派人员做某项工作（任务）的情况。指派问题的许多应用是用来帮助管理人员解决如何为一项即将开展的工作指派人员的问题。其他的一些应用如为工作指派机器、设备或工厂等。指派问题也称分配问题，主要研究人和工作（任务）间如何匹配，以使所有工作完成的效率实现最优化。形式上，指派问题给定了一系列所要完成的工作以及一系列完成工作的人员，所需要解决的问题就是要确定出指派哪个人去完成哪项工作。当前33页，总共46页。5指派问题指派问题的假设：

（1）人的数量和工作的数量相等； （2）每个人只能完成一项工作； （3）每项工作只能由一个人来完成； （4）每个人和每项工作的组合都会有一 个相关的成本（单位成本）； （5）目标是要确定如何指派才能使总成 本最小。当前34页，总共46页。设决策变量xij为第i个人做第j项工作，而已知5指派问题目标函数系数cij为第i个人完成第j项工作所需要的单位成本。平衡指派问题的数学模型为当前35页，总共46页。5指派问题需要说明的是：指派问题实际上是一种特殊的运输问题。其中出发地是人，目的地是工作。只不过，每一个出发地的供应量都为1（因为每个人都要完成一项工作），每一个目的地的需求量都为1（因为每项工作都要完成）。由于运输问题有“整数解性质”，因此，没有必要加上所有决策变量都是0-1变量的约束。指派问题是一种特殊的线性规划问题，有一种快捷的求解方法：匈牙利方法（HungarianMethod），但Excel的“规划求解”工具还是采用“单纯形法”来求解。当前36页，总共46页。5指派问题

例8某公司的营销经理将要主持召开一年一度的由 营销区域经理以及销售人员参加的销售协商会议。 为了更好地安排这次会议，他安排小张、小王、小 李、小刘等四个人，每个人负责完成下面的一项工 作：A、B、C和D。 由于每个人完成每项任务的时间和工资不同（如 表所示）。问如何指派，可使总成本最小。人员每小时工资 （元）每一项工作所需要的时间（小时） 工作A工作B工作C工作D小张小王小李小刘3547393241455651273236254051434614121315当前37页，总共46页。5指派问题解：该问题是一个典型的指派问题。单位成本为每个人做每项工作的总工资目标是要确定哪个人做哪一项工作，使总成本最小供应量为1代表每个人都只能完成一项工作需求量为1代表每项工作也只能有一个人来完成总人数（4人）和总任务数（4项）相等当前38页，总共46页。5指派问题数学模型： 设xij为指派人员i去做工作j（i，j＝1,2,3,4)当前39页，总共46页。5指派问题电子表格模型当前40页，总共46页。6各种变形的指派问题建模经常会遇到指派问题的变形，之所以称它们为变形，是因为它们都不满足平衡指派问题所有假设之中的一个或者多个。一般考虑下面的一些特征：（1）有些人并不能进行某项工作（相应的xij＝0）;（2）虽然每个人完成一项任务，但是任务比人多(人少事多);（3）虽然每一项任务只由一个人完成，但是人比任务多（人多事少）；（4）某人可以同时被指派给多个任务（一人可做几件事）；（5）某事可以由多人共同完成（一事可由多人完成）；（6）目标是与