《熊伟编《运筹学》Ch5运输与指派问题》由会员分享，可在线阅读，更多相关《熊伟编《运筹学》Ch5运输与指派问题（82页珍藏版）》请在金锄头文库上搜索。
1、运筹学 Operations ResearchChapter 5 运输与指派问题Transportation and Assignment Problem5.1运输模型 Mathematical Model of Transportation Problems 5.2 运输单纯形法 Transportation Simplex Method 5.3 运输模型的应用 Aplication of Transportation Model 5.4 指派问题 Assignment problem Date5.1 运输模型Mathematical Model of Transportation Prob
2、lemsDatePage 3 Chapter 5 运输与指派问题 T&A Problem 人们在从事生产活动中，不 可避免地要进行物资调运工 作。如某时期内将生产基地 的煤、钢铁、粮食等各类物 资，分别运到需要这些物资 的地区，根据各地的生产量 和需要量及各地之间的运输 费用，如何制定一个运输方 案，使总的运输费用最小。 这样的问题称为运输问题 。5.1 运输模型 Model of Transportation Problems5.1.1 数学模型产地销地A110A28A35B43B38B27B15354 2 3 1 6 8 232 9图5.1DatePage 4 Chapter 5 运输与指
3、派问题 T&A Problem 【例5.1】现有A1，A2，A3三个产粮区，可供应 粮食分别为10， 8，5（万吨），现将粮食运往B1，B2，B3，B4四个地区，其需 要量分别为5，7，8，3（万吨）。产粮地到需求地的运价（元/ 吨）如表51所示，问如何安排一个运输计划，使总的运输费 用最少。地区 产产粮区B1B2B3B4产产量A1326310A253828A341295需要量578323运价表（元/T）表515.1 运输模型 Model of Transportation ProblemsDatePage 5 Chapter 5 运输与指派问题 T&A Problem 设xij(i=1,2,
4、3；j=1,2,3,4)为i个产粮地运往第j个需求地的运量， 这样得到下列运输问题的数学模型：运量应大于或等于零（非负要求），即 5.1 运输模型 Model of Transportation ProblemsDatePage 6 Chapter 5 运输与指派问题 T&A Problem 有些问题表面上与运输问题没有多大关系，也可以建立与 运输问题形式相同的数学模型 看一个例子：【例5.2】有三台机床加工三种零件，计划第i台的生产任务 为a i (i=1,2,3)个零件，第j种零件的需要量为bj (j=1,2,3)，第i台 机床加工第j种零件需要的时间为cij ，如表52所示。问如何安 排
5、生产任务使总的加工时间最少？ 零件 机床B1B2B3生产产任务务A152350A264160A373440需要量703050150表525.1 运输模型 Model of Transportation ProblemsDatePage 7 Chapter 5 运输与指派问题 T&A Problem 【解】 设 xi j (i=1,2,3；j=1,2,3,)为第i台机床加工第j种零件的 数量，则此问题的数学模型为5.1 运输模型 Model of Transportation ProblemsDatePage 8 Chapter 5 运输与指派问题 T&A Problem 运输问题的一般数学模型
6、设有m个产地（记作A1，A2，A3,Am），生产某种物资，其产量分别为a1,a2，am；有n个销地（记作B1，B2，Bn），其需要量分别为b1,b2，bn；且产销平衡，即 。从第i个产地到j 个销地的单位运价为cij ，在满足各地需要的前提下，求总运输费用最小的调运方案。 设xij(i=1,2,，m；j=1,2,n)为第i个产地到第j个销地的运量，则数学模型为： 5.1 运输模型 Model of Transportation ProblemsDatePage 9 Chapter 5 运输与指派问题 T&A Problem 设平衡运输问题的数学模型为：5.1.2 模型特征5.1 运输模型 Mo
7、del of Transportation Problems1.运输问题存在可行解，也一定存在最优解 2.当供应量和需求量都是整数时，则一定存在整数最优解 3.有m+n个约束，mn个变量 4.有m+n1个基变量DatePage 10 Chapter 5 运输与指派问题 T&A Problem 【证】因为产销平衡，即 ，将前m个约束方程两边相 加得再将后n个约束相加得显然前m个约束方程之和等于后n个约束方程之和，m+n个约束方 程是相关的，系数矩阵5.1 运输模型 Model of Transportation Problems【定理5.1】设有m个产地n个销地且产销平衡的运输问题，则基 变量数
8、为m+n-1。DatePage 11 Chapter 5 运输与指派问题 T&A Problem 中任意m+n阶子式等于零，取第一行到m+n1行与对应的列（共m+n-1列）组成的m+n1阶子式m 行n 行5.1 运输模型 Model of Transportation ProblemsDatePage 12 Chapter 5 运输与指派问题 T&A Problem 故r(A)=m+n1所以运输问题有m+n1个基变量。 为了在mn个变量中找出m+n1个变量作为一组基变量，就是 要在A中找出m+n-1个线性无关的列向量，下面引用闭回路的概 念寻找这些基变量。5.1 运输模型 Model of T
9、ransportation ProblemsDatePage 13 Chapter 5 运输与指派问题 T&A Problem 为一个闭回路 ，集合中的变量称为回路的顶点，相邻两个变量 的连线为闭回路的边。在表53及表54中的变量组构成两个闭 回路。x25x23B1B2B3B4B5A1 A2 A3 x35A4 x43 x11x12x31x42表53表53中闭回路的变量集合是x11,x12,x42, x 43, x 23, x 25, x 35, x 31共有8个顶点， 这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。 5.1 运输模型 Model of Transportation
10、ProblemsDatePage 14 Chapter 5 运输与指派问题 T&A Problem x11x12x32x33x41B1B2B3A1 A2 A3 A4 x43表54一条回路中的顶点数一定是偶数，回路遇到顶点必须转90度 与另一顶点连接，表53中的变 量x 32及x33不是回闭路的顶点，只是连线的交点。 表54中闭回路是例如变量组A不能组成一条闭回路，但A中包含有闭回路 B的变量数是奇数，显然不是闭回路，也不含有闭回路； 5.1 运输模型 Model of Transportation ProblemsDatePage 15 Chapter 5 运输与指派问题 T&A Proble
11、m C是一条闭回路，若把C重新写成 就不难看出C仍是一条闭回路。 【定理5.2】 若变量组B 包含有闭回路 ，则B 中的变量对应的例向量线性相关。【证】由线性代数知，向量组中部分向量组线性相关则该向量组 线性相关，显然，将C中列向量分别乘以正负号线性组合后等于零 ，即因而C中的列向量线性相关，所以B中列向量线性相关。5.1 运输模型 Model of Transportation ProblemsDatePage 16 Chapter 5 运输与指派问题 T&A Problem 由定理2可知，当一个变量组中不包含有闭回路，则这些变量对应 的系数向量线性无关。求运输问题的一组基变量，就是要找到m
12、+n1个变量，使得它们 对应的系数列向量线性无关，由定理2，找这样的一组变量是很容 易的，只要m+n1个变量中不包含闭回路，就可得到一组基变量 。因而有：【定理3】m+n1个变量组构成基变量的充要条件是它不包含任 何闭回路。定理3告诉了一个求基变量的简单方法，同时也可以判断一组变量 是否可以作为某个运输问题的基变量。这种方法是直接在运价表 中进行的，不需要在系数矩阵A中去寻找，从而给运输问题求初始 基可行解带来极大的方便。5.1 运输模型 Model of Transportation ProblemsDatePage 17 Chapter 5 运输与指派问题 T&A Problem 表5-5
13、Bj AiB1B2B3B4aiA1c11 c12c13c14 a1x11x12x13x14 A2c21c22 c23c24a2x21x22x23x24 A3c31c32c2c34a3x31x32x33x34 bjb1b2b3b45.1 运输模型 Model of Transportation Problems例如，m=3,n=4，将xij与运价Cij放在同一张表中，如表5-5所示。DatePage 18 Chapter 5 运输与指派问题 T&A Problem 这个运输问题的基变量数目是3+41=6。变量组中有7个变量，显然不能构成一组基变量，又如中有6个变量，但包含有一条闭回路故不能构成一
14、组基变量。变量组有6个变量且不含有任何闭回路，故可以构成此问题的一组基变量。5.1 运输模型 Model of Transportation ProblemsDatePage 19 Chapter 5 运输与指派问题 T&A Problem 本节介绍了具有m个产地n个销地的平衡运输问题时： 1.具有m+n1个基变量 2. 闭回路的概念 3.怎样判断m+n1个变量是否构成一组基变量5.1 运输模型 Model of Transportation Problems下一节：运输单纯形法作业：教材P124 T 5，6 建立数学模型Date5.2 运输单纯形法 Transportation Simple
15、x MethodDatePage 21 Chapter 5 运输与指派问题 T&A Problem 设平衡运输问题的数学模型为：5.2 运输单纯形法 Transportation Simplex MethodDatePage 22 Chapter 5 运输与指派问题 T&A Problem 运输单纯形法也称为表上作业法，是直接在运价表上求最优解的 一种方法，它的步骤是：第一步：求初始基行可行解（初始调运方案）。 常用的方法有 最小元素法、元素差额法（Vogel近似法）、左上角法。第二步：求检验数并判断是否得到最优解。常用求检验的方法 有闭回路法和位势法，当非基变量的检验数ij全都非负时得到最 优解，若存在检验数lk0，说明还没有达到最优，转第三步。第三步：调整运量，即换基。选一个变量出基，对原运量进行 调整得到新的基可行解，转入第二步。5.2 运输单纯形法 Transportation Simplex MethodDatePage 23 Chapter 5 运输与指派问题 T&A Problem 5.2.1初始基可行解1. 最小元素法 最小元素法的思想是就近优先运送，即
