运筹学3运输问题 ppt课件

Chapter 3 运输问题Transportation Problem 运输问题是一种特殊的线性规划问题 ,用一种特殊的方法 (表上作业法 )求解更为简单运筹学Operations Research1.运输模型 Mathematical Model of Transportation Problems2.基变量与闭回路 Basis Variable and Closed path 3.表上作业法 Transportation Simplex Method 4.运输问题的变体 Variants of Transportation Problems Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 2 of 11运输问题人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的 生产量 和 需要量 及各地之间的 运输费用 ，如何制定一个运输方案，使总的运输费用最小。这样的问题称为 运输问题 。 Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 3 of 11运输问题的特征Characteristics of Transportation Problems每一个 出发地 都有一定的 供应量 （ supply） 配送到目的地，每一个 目的地 都有需要从一定的 需求量 （demand） ， 接收从出发地发出的产品。需求假设 （ The Requirements Assumption） 可行解特性 （ The Feasible Solutions Property） 成本假设（ The Cost Assumption）整数解性质（ Integer Solutions Property）Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 4 of 11需求假设 （ The Requirements Assumption）：每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之相类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足， 即总供应量 总需求量 可行解特性（ The Feasible Solutions Property）：当且仅当供应量的总和等于需求量的总和时，运输问题才有可行解 Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 5 of 11成本假设（ The Cost Assumption）：从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系，因此这个成本就等于配送的单位成本乘以所配送的数量 整数解性质（ Integer Solutions Property） ：只要它的供应量和需求量都是整数，任何有可行解的运输问题必然有所有决策变量都是整数的最优解。因此，没有必要加上所有变量都是整数的约束条件 Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 6 of 11【 例 1】 现有 A1， A2， A3三个产粮区，可供应 粮食分别为 10， 8， 5（万吨），现将粮食运往 B1， B2， B3， B4四个地区，其需要量分别为 5， 7， 8， 3（万吨）。产粮地到需求地的运价（ 10万元 /万吨）如表 3 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运价表（元 /吨）表 3 1Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 7 of 11设 xij ( i =1,2,3； j =1,2,3,4)为 i个产粮地运往第 j个需求地的运量，这样得到下列运输问题的数学模型：运量应大于或等于零（非负要求），即 Min z = 3x11+ 2x12+ 6x13+ 3x14+ 5x21+ 3x22+ 8x23+ 2x24+ 4x31+ x32+ 2x33+ 9x34xij 0, i =1, 2, 3; j =1, 2, 3, 4Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 8 of 11有些问题表面上与运输问题没有多大关系，但经过转换，也可以建立与运输问题形式相同的数学模型看一个例子：【 例 2】 有三台机床加工三种零件，计划第 i台的生产任务为 a i (i=1,2,3)个零件，第 j种零件的需要量为 bj (j=1,2,3)，第 i台机床加工第 j种零件需要的时间为 cij ， 如表 3 2所示。问如何安排生产任务使总的加工时间最少？ 零件机床 B1 B2 B3 生 产 任 务A1 5 2 3 50A2 6 4 1 60A3 7 3 4 40需要量 70 30 50 150表 3 2Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 9 of 11【 解 】 设 xi j (i=1,2,3； j=1,2,3,)为第 i台机床加工第 j种零件的数量，则此问题的数学模型为Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 10 of 11运输问题的数学模型设有 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个销地的运量，则数学模型为： Date3.1 运输问题的数学模型Mathematical Model of T P Ch3 Transportation Problem Page 11 of 11基变量与闭回路 ExitDate3.2 基变量与闭回路Basis Variable and Closed PathCh3 Transportation Problem Page 12 of 11设 平衡运输问题的数学模型为：Date3.2 基变量与闭回路Basis Variable and Closed PathCh3 Transportation Problem Page 13 of 11【 定理 1】 设有 m个产地 n个销地且产销平衡的运输问题，则基变量数为 m+n-1。【 证 】 因为产销平衡 ，即 ，将前 m个约束方程两边相加得再将后 n个约束相加得显然前 m个约束方程之和等于后 n个约束方程之和， m+n个约束方程是相关的，系数矩阵Date3.2 基变量与闭回路Basis Variable and Closed PathCh3 Transportation Problem Page 14 of 11中任意 m+n阶子式等于零，取第一行到 m+n 1行与对应的列（共 m+n-1列）组成的 m+n 1阶子式Date3.2 基变量与闭回路Basis Variable and Closed PathCh3 Transportation Problem Page 15 of 11故 r(A)=m+n 1所以运输问题有 m+n 1个基变量。为了在 mn个变量中找出 m+n 1个变量作为一组基变量，就是要在 A中找出 m+n-1个线性无关的列向量，下面引用闭回路的概念寻找这些基变量。Date3.2 基变量与闭回路Basis Variable and Closed PathCh3 Transportation Problem Page 16 of 11为一个闭回路 ，集合中的变量称为回路的顶点，相邻两个变量的连线为闭回路的边。在表 3 3及表 3 4中的变量组构成两个闭回路。x23B1 B2 B3 B4 B5A1 A2 A3 x35A4 x43 x11 x12x25x31x42表 3 3表 3 3中闭回路的变量集合是 x11,x12,x42, x 43, x 23, x 25, x 35, x 31共有 8个顶点， 这 8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。 Date3.2 基变量与闭回路Basis Variable and Closed PathCh3 Transportation Problem Page 17 of 11x11 x12x32 x33x41B1 B2 B3A1 A2 A3 A4 x43表 3 4 一条回路中的顶点数一定是偶数，回路遇到顶点必须转 90度与另一顶点连接，表 3 3中的变量 x 32及 x33不是回闭路的顶点，只是连线的交点。 表 3 4中闭回路是例如变量组A不能组成一条闭回路，但 A中包含有闭回路 B的变量数是奇数，显然不是闭回路，也不含有闭回路； Date3.2 基变量与闭回路Basis Variable and Closed PathCh3 Transportation Problem Page 18 of 11C是一条闭回路，若把 C重新写成 就不难看出 C仍是一条闭回路。 【 定理 2】 若变量组 B 包含有闭回路 ，则 B中的变量对应的例向量线性相关。【 证 】 由线性代数知，向量组中部分向量组线性相关则该向量组线性相关，显然，将 C中列向量分别乘以正负号线性组合后等于零，即因而 C中的列向量线性相关，所以 B中列向量线性相关。Date3.2 基变量与闭回路Basis Variable and Closed PathCh3 Transportation Problem Page 19 of 11由定理 2可知，当一个变量组中不包含有闭回路，则这些变量对应的系数向量线性无关。求运输问题的一组基变量，就是要找到 m+n 1个变量，使得它们对应的系数列向量线性无关，由定理 2，找这样的一组变量是很容易的，只要 m+n 1个变量中不包含闭回路，就可得到一组基变量。因而有：【 定理 3】 m+n 1个变量组构成基变量的充要条件是它不包含任何闭回路。定理 3告诉了一个求基变量的简单方法，同时也可以判断一组变量是否可以作为某个运输问题的基变量。这种方法是直接在运价表中进行的，不需要在系数矩阵 A中去寻找，从而给运输问题求初始基可行解带来极大的方便。Date3.2 基变量与闭回路Basis Variable and Closed PathCh3 Transportation Problem Page 20 of 11例如， m=3,n=4， 在运价表 Cij的格子的右上方填上相应的 xij， 如表 3-5所示。表 3 5BjAi B1 B2 B3 B4 aiA1x11 x12x13 x14 a1C11 C12 C13 C14A2x21 x22 x23 x24a2C21 C22 C23 C24A3x31 x32 x2 x34a3C31 C32 C33 C34bj b1 b2 b3 b4 Date3.2 基变量与闭回路Basis Variable and Closed PathCh3 Transportation Problem Page 21 of 11这个运输问题的基变量数目是 3+4 1=6。变量组中有 7个变量，显然不能构成一组基变量，又如中有 6个变量，但包含有一条闭回路故不能构成一组基变量。变量组有 6个变量且不含有任何闭回路，故可以构成此问题的一组基变量。Date3.2 基变量与闭回路Basis Variable and Closed PathCh3 Transportation Problem Page 22 of 11表上作业法作业： P98 T3.1 本节介绍了具有 m个产地 n个销地的平衡运输问题时：1.具有 m+n 1个基变量2. 闭回路的概念3.怎样判断 m+n 1个变量是否构成一组基变量ExitDate3.3 表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 23 of 36设 平衡运输问题的数学模型为：Date3.3 表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 24 of 36表上作业法也称为运输单纯形法，是直接在运价表上求最优解的一种方法，它的步骤是：第一步：求初始基行可行解（初始调运方案），常用的方法有最小元素法、元素差额法（ Vogel近似法）、左上角法。第二步：求检验数并判断是否得到最优解，常用求检验的方法有闭回路法和位势法，当非基变量的检验数 ij全都非负时得到最优解，若存在检验数 lk0， 说明还没有达到最优，转第三步。第三步：调整运量，即换基，选一个变量出基，对原运量进行调整得到新的基可行解，转入第二步。Date3.3 表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 25 of 363.3.1初始基可行解1.最小元素法 最小元素法的思想是就近优先运送，即最小运价 Cij对应的变量 xij优先赋值然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直到最后一个初始基可行解。Date3.3 表上作业法Transportation Simplex MethodCh3 Transportation Problem Page 26 of 36【 例 3】 求表 3 6所示的运输问题的初始基可行解。表 3 6销 地产地 B1 B2 B3 产量A18 6 730A24 3 545A37 4 825销 量 60 30 10 100Date3.3 表上作业法Transportation Simp