1、运筹学Operations ResearchChapter 5 运输与指派问题Transportation and Assignment Problem5.1运输模型 Mathematical Model of Transportation Problems5.2 运输单纯形法 Transportation Simplex Method5.3 运输模型的应用 Aplication of Transportation Model5.4 指派问题 Assignment problem Date5.1 运输模型Mathematical Model of Transportation Problems
2、Date制作与教学武汉 理工大学 管理学院 熊伟 Page 3 Chapter 5 运输与指派问题T&A Problem 人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的 生产量和 需要量 及各地之间的 运输费用 ，如何制定一个运输方案，使总的运输费用最小。这样的问题称为 运输问题。5.1 运输模型 Model of Transportation Problems5.1.1 数学模型 产地 销地A110A28A35B43B38B27B1535 4231682329图 5.1Date制作与教学武汉 理工大学
3、 管理学院 熊伟 Page 4 Chapter 5 运输与指派问题T&A Problem 【 例 5-1】 现有 A1， A2， A3三个产粮区，可供应 粮食分别为 10，8， 5（万吨），现将粮食运往 B1， B2， B3， B4四个地区，其需要量分别为 5， 7， 8， 3（万吨）。产粮地到需求地的运价（元 /吨）如表 5-1所示，问如何安排一个运输计划，使总的运输费用最少。地区产 粮区 B1 B2 B3 B4 产 量A1 3 2 6 3 10A2 5 3 8 2 8A3 4 1 2 9 5需要量 5 7 8 3 23运价表（元 /T）表 5-15.1 运输模型 Model of Tran
4、sportation Problems Date制作与教学武汉 理工大学 管理学院 熊伟 Page 5 Chapter 5 运输与指派问题T&A Problem 设 xij(i=1,2,3； j=1,2,3,4)为 i个产粮地运往第 j个需求地的运量（万吨），得到下列运输问题的数学模型：运量应大于或等于零（非负要求），即 5.1 运输模型 Model of Transportation Problems Date制作与教学武汉 理工大学 管理学院 熊伟 Page 6 Chapter 5 运输与指派问题T&A Problem 有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数
5、学模型看一个例子：【 例 5-2】 有三台机床加工三种零件，计划第 i台的生产任务为 a i (i=1,2,3)个零件，第 j种零件的需要量为 bj (j=1,2,3)，第 i台机床加工第 j种零件需要的时间为 cij ， 如表 5 2所示。问如何安排生产任务使总的加工时间最少？ 零件机床 B1 B2 B3 生 产 任 务A1 5 2 3 50A2 6 4 1 60A3 7 3 4 40需要量 70 30 50 150表 5 25.1 运输模型 Model of Transportation Problems Date制作与教学武汉 理工大学 管理学院 熊伟 Page 7 Chapter 5
6、运输与指派问题T&A Problem 【 解 】 设 xi j (i=1,2,3； j=1,2,3,)为第 i台机床加工第 j种零件的数量，则此问题的数学模型为5.1 运输模型 Model of Transportation Problems Date制作与教学武汉 理工大学 管理学院 熊伟 Page 8 Chapter 5 运输与指派问题T&A Problem 运输问题的一般数学模型设有 m个产地（记作 A1， A2， A3, Am）， 生产某种物资，其产量分别为 a1,a2， ， am；有 n个销地（记作 B1， B2， ， Bn），其需要量分别为 b1,b2， ， bn； 且产销平衡，即
7、 。从第 i个产地到 j 个销地的单位运价为 cij ， 在满足各地需要的前提下，求总运输费用最小的调运方案。 设 xij(i=1,2, ， m；j=1,2, n)为第 i个产地到第 j个销地的运量，则数学模型为： 5.1 运输模型 Model of Transportation Problems Date制作与教学武汉 理工大学 管理学院 熊伟 Page 9 Chapter 5 运输与指派问题T&A Problem 设 平衡运输问题的数学模型为：5.1.2 模型特征5.1 运输模型 Model of Transportation Problems1.运输问题存在可行解，也一定存在最优解 2.当供应量和需求量都是整数时，则一定存在整数最优解3.有 m+n个约束， mn个变量4.有 m+n 1个基变量Date制作与教学武汉 理工大学 管理学院 熊伟 Page 10 Chapter 5 运输与指派问题T&A Problem 【 证 】 因为产销平衡，即 ，将前 m个约束方程两边相加得再将后 n个约束相加得显然前 m个约束方程之和等于后 n个约束方程之和， m+n个约束方程是相关的，系数矩阵5.1 运输模型 Model of Transportation Problems【 定理 5.1】 设有 m个产地 n个销地且产销平衡的运输问题，则基变量数为 m+n-1。Date
