运筹学-运输与指派问题

《运筹学-运输与指派问题》由会员分享，可在线阅读，更多相关《运筹学-运输与指派问题（101页珍藏版）》请在金锄头文库上搜索。

1、运筹学运筹学 OperationsResearch Chapter5运输与指派问题运输与指派问题 TransportationandAssignmentProblem 5.1运输问题的数学模型运输问题的数学模型及其特征及其特征 5.2运输单纯形法运输单纯形法 5.3运输模型的应用运输模型的应用 5.4指派问题指派问题 5.1运输问题的数学模型及其特征运输问题的数学模型及其特征 MathematicalModelofTransportationProblems 人们在从事生产活动中，不人们在从事生产活动中，不 可避免地要进行物资调运工可避免地要进行物资调运工 作。如某时期内将生产基地作。如某时期

2、内将生产基地 的煤、钢铁、粮食等各类物的煤、钢铁、粮食等各类物 资，分别运到需要这些物资资，分别运到需要这些物资 的地区，根据各地的的地区，根据各地的生产量生产量 和和需要量需要量及各地之间的及各地之间的运输运输 费用费用，如何制定一个运输方，如何制定一个运输方 案，使总的运输费用最小。案，使总的运输费用最小。 这样的问题称为这样的问题称为运输问题运输问题。 5.1运输模型运输模型 ModelofTransportationProblems 5.1.1数学模型数学模型 产地 销地 A1 10 A2 8 A3 5 B4 3 B3 8 B2 7 B1 5 3 5 4 2 3 1 6 8 2 3 2

3、 9 图图5.1 【例例5-1】现有现有A1，A2，A3三个产粮区，可供应三个产粮区，可供应粮食分别为粮食分别为10， 8，5（万吨），现将粮食运往（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需四个地区，其需 要量分别为要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元（万吨）。产粮地到需求地的运价（元/ 吨）如表吨）如表5-1所示，问如何安排一个运输计划，使总的运输费用所示，问如何安排一个运输计划，使总的运输费用 最少。最少。 需求地需求地 产粮地产粮地 B1B2B3B4供给量供给量 A1326310 A253828 A341295 需求量需求量578323 运价表（元运

4、价表（元/吨）吨）表表5-1 5.1运输模型运输模型 ModelofTransportationProblems 设设xij(i=1,2,3；j=1,2,3,4)为为i个产粮地运往第个产粮地运往第j个需求地的运量，个需求地的运量， 这样得到下列运输问题的数学模型：这样得到下列运输问题的数学模型： 运量应大于或等于零（非负要求），即运量应大于或等于零（非负要求），即 5.1运输模型运输模型 ModelofTransportationProblems 有些问题表面上与运输问题没有多大关系，也可以建立与有些问题表面上与运输问题没有多大关系，也可以建立与 运输问题形式相同的数学模型运输问题形式相同的数

5、学模型 看一个例子：看一个例子： 【例例5-2】有三台机床加工三种零件，计划第有三台机床加工三种零件，计划第i台的生产任务台的生产任务 为为a i (i=1,2,3)个零件，第个零件，第j种零件的需要量为种零件的需要量为bj (j=1,2,3)，第，第i台台 机床加工第机床加工第j种零件需要的时间为种零件需要的时间为cij ，如表，如表52所示。问如何安所示。问如何安 排生产任务使总的加工时间最少？排生产任务使总的加工时间最少？ 零件零件 机床机床 B1B2B3生产任务生产任务 A152350 A264160 A373440 需要量需要量703050150 表表52 5.1运输模型运输模型 M

6、odelofTransportationProblems 【解解】设设xi j (i=1,2,3；j=1,2,3,)为第为第i台机床加工第台机床加工第j种零件的种零件的 数量，则此问题的数学模型为数量，则此问题的数学模型为 5.1运输模型运输模型 ModelofTransportationProblems 5.1.2模型特征模型特征 运输问题的一般数学模型运输问题的一般数学模型 设有设有m个产地（记作个产地（记作A1，A2，A3,Am），生产某种物资，其产），生产某种物资，其产 量分别为量分别为a1,a2，am；有；有n个销地（记作个销地（记作B1，B2，Bn），）， 其需要量分别为其需要量分

7、别为b1,b2，bn；且产销平衡，即；且产销平衡，即。 从第从第i个产地到个产地到j 个销地的单位运价为个销地的单位运价为cij ，在满足各地需要的前提，在满足各地需要的前提 下，求总运输费用最小的调运方案。下，求总运输费用最小的调运方案。 5.1运输模型运输模型 ModelofTransportationProblems 销地 产地 产量 销量 设设xij(i=1,2,，m；j=1,2,n)为第为第i个产地到第个产地到第j个销地的运量，个销地的运量， 则数学模型为：则数学模型为： 5.1运输模型运输模型 ModelofTransportationProblems m 行行 n 行行 5.1运

8、输模型运输模型 ModelofTransportationProblems 运输问题具有如下特点运输问题具有如下特点: 1.运输问题存在可行解，也一定存在最优解运输问题存在可行解，也一定存在最优解 2.当供应量和需求量都是整数时，则一定存在整数最优解当供应量和需求量都是整数时，则一定存在整数最优解 3.有有m+n个约束，个约束，mn个变量个变量 4.约束条件系数矩阵的元素等于约束条件系数矩阵的元素等于0或或1 5.约束条件系数矩阵的每一列有两个非零元素约束条件系数矩阵的每一列有两个非零元素,这对应于每一个变量在前这对应于每一个变量在前 m个约束方程中出现一次个约束方程中出现一次,在后在后n个约

9、束方程中也出现一次个约束方程中也出现一次 6.所有约束方程都是等式方程所有约束方程都是等式方程 7.各产地产量之和等于各销地销量之和各产地产量之和等于各销地销量之和 8.有有m+n1个基变量个基变量,因为产销平衡因为产销平衡,所以模型最多只有所以模型最多只有m+n-1个独立约个独立约 束方程束方程,即系数矩阵的秩最多为即系数矩阵的秩最多为m+n-1. 5.2运输单纯形法运输单纯形法 TransportationSimplexMethod 设平衡运输问题的数学模型为：设平衡运输问题的数学模型为： 5.2运输单纯形法运输单纯形法 TransportationSimplexMethod 运运输输单单

10、纯纯形形法法也也称称为为表表上上作作业业法法，是是直直接接在在运运价价表表上上求求最最优优解解的的 一种方法，它的步骤是：一种方法，它的步骤是： 第第一一步步：求求初初始始基基本本可可行行解解（初初始始调调运运方方案案）。常常用用的的方方法法有有 最小元素法、元素差额法（最小元素法、元素差额法（Vogel近似法）、左上角法。近似法）、左上角法。 第第二二步步：求求检检验验数数并并判判断断是是否否得得到到最最优优解解。常常用用求求检检验验的的方方法法 有有闭闭回回路路法法和和位位势势法法，当当非非基基变变量量的的检检验验数数ij全全都都非非负负时时得得到到最最 优解，若存在检验数优解，若存在检验

11、数lk0，说明还没有达到最优，转第三步。，说明还没有达到最优，转第三步。 第第三三步步：调调整整运运量量，即即换换基基。选选一一个个变变量量出出基基，对对原原运运量量进进行行 调整得到新的基可行解，转入第二步。调整得到新的基可行解，转入第二步。 5.2运输单纯形法运输单纯形法 TransportationSimplexMethod 5.2.1初始基可行解初始基可行解 1.最最小小元元素素法法最最小小元元素素法法的的思思想想是是就就近近优优先先运运送送，即即最最小小运运价价Cij 对应的变量对应的变量xij优先赋值优先赋值 然然后后再再在在剩剩下下的的运运价价中中取取最最小小运运价价对对应应的的

12、变变量量赋赋值值并并满满足足约约束束， 依次下去，直到最后得到一个初始基可行解。依次下去，直到最后得到一个初始基可行解。 5.2运输单纯形法运输单纯形法 TransportationSimplexMethod 【例例5-3】求表求表56所示的运输问题的初始基可行解。所示的运输问题的初始基可行解。 表表56 销销地地 产地产地B1B2B3B4产量产量 A1 A2 A3 9 7 2 3 6 10 8 5 9 4 1 2 70 50 20 销销量量10604030140 5.2运输单纯形法运输单纯形法 TransportationSimplexMethod Bj Ai B1B2B3B4产产量量 A1

13、938 4 70 A27651 50 A321092 20 销销量量10604030140 表表5759 【解解】 30 10 1060 5.2运输单纯形法运输单纯形法 TransportationSimplexMethod 20 10 到一组基可行解可用矩阵到一组基可行解可用矩阵 表示，矩阵表示，矩阵X 中空白处对应的变量是非基变量，运量等于零，中空白处对应的变量是非基变量，运量等于零， 这组解就是初始调运方案总运费这组解就是初始调运方案总运费 Z=360+810+520+130+210+910=500 【例例5-4】求表求表5-10给出的运输问题的初始基本可行解给出的运输问题的初始基本可行

14、解 B1B2B3B4ai A14104420 A2773815 A31210615 bj510251050 表表5-10 5.2运输单纯形法运输单纯形法 TransportationSimplexMethod 表表5-11 Bj Ai B1B2B3B4ai A1 41044 20 A2 7738 15 A3 12106 15 bj510251050 【解解】 5 10 0 15 1010 5.2运输单纯形法运输单纯形法 TransportationSimplexMethod 初始基本可行解可用下列矩阵表示初始基本可行解可用下列矩阵表示 5.2运输单纯形法运输单纯形法 Transportatio

15、nSimplexMethod 2元元素素差差额额法法（Vogel近近似似法法）最最小小元元素素法法只只考考虑虑了了局局部部运运输输费费 用用最最小小。有有时时为为了了节节省省某某一一处处的的运运费费，而而在在其其它它处处可可能能运运费费很很大大。 元元素素差差额额法法对对最最小小元元素素法法进进行行了了改改进进，考考虑虑到到产产地地到到销销地地的的最最小小 运运价价和和次次小小运运价价之之间间的的差差额额，如如果果差差额额很很大大，就就选选最最小小运运价价先先调调 运，否则会增加总运费。例如下面两种运输方案运，否则会增加总运费。例如下面两种运输方案 前一种按最小元素法求得，总运费是前一种按最小

16、元素法求得，总运费是 Z1=108+52+151=105 后后一一种种方方案案考考虑虑到到C11与与C21之之间间的的差差额额是是82=6，先先调调运运x21， 再是再是x22，其次是，其次是x12这时总运费这时总运费 Z2=105+152+51=85Z1。 5.2运输单纯形法运输单纯形法 TransportationSimplexMethod 基于以上思路，元素差额法求初始基本可行解的步骤是：基于以上思路，元素差额法求初始基本可行解的步骤是： 第第一一步步：求求出出每每行行次次小小运运价价与与最最小小运运价价之之差差，记记为为ui，i=1,2,m ； 同时求出每列次小运价与最小运价之差，记为同时求出每列次小运价与最小运价之差，记为vj，j=1，2，n ； 第第二二步步：找找出出所所有有行行、列列差差额额的的最