三章運输问题.pptVIP

第三章 运输问题 －特殊的线性规划 第一节 运输问题及其数学模型 2、运输问题的数学模型 设xij为从产地Ai运往销地Bj的物资数量（i=1，…m；j=1，…n）。 从Ai运出的物资总量应等于Ai的产量ai， xij应满足： 运输问题的数学模型 第二节 表上作业法 作 业 P104 3.7（表3－29） 用三种方法分别求出初始调运方案，比较哪种方案更好。 * * 模型及其特点 求解思路及相关理论 求解方法——表上作业法 运输问题的推广 产销不平衡的运输问题 转运问题 一、运输问题的数学模型 1、 运输问题的一般提法： 某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？ 销量 产量 销地 产地 运输表（运价，运量） 运到Bj的物资总量应该等于Bj的销量bj， xij还应满足： 总运费为： 1.约束条件都是等式约束 2.总产量＝总销量 二、产销平衡的运输问题的特点与性质 3.必有最优基本可行解 证明思路 非空有界 非空 有界 4．系数矩阵是一个结构特殊的稀疏矩阵。 系数矩阵A： m行 n行 ? 矩阵的元素均为1或0； 每一列只有两个元素为1，其余元素均为0； ? 列向量Pij =(0,…，0，1，0，…,0,1,0,…0)T，其中两个元素1分别处于第i行和第m+j行。 将该矩阵分块，特点是： 前m行构成m个m×n阶矩阵，而且第k个矩阵只有第k行元素全为1，其余元素全为0（k=1，…，m）； 后n行构成m个n阶单位阵。 运输问题的基变量总数是m + n -1 A的秩为m+n-1 例．三个产地，四个销地问题运输表如表 运输表（运价，运量） 11 3 4 48 14 12 14 8 销量 22 6 8 5 14 8 10 9 10 10 2 16 11 6 2 12 4 8 产量 销地 产地 填有数字的格 空格 11 3 4 48 14 12 14 8 销量 22 6 5 8 10 9 10 2 16 11 12 4 产量 销地 产地 一、表上作业法的基本思想: 先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案。 作业表（产销平衡表）：将运输问题的有关 信息表和决策变量——调运量结合在一起构成 “作业表”（产销平衡表）。 确定初始方案 (初始基本可行解) 改进调整 （换基迭代） 否 判定是否 最 优？ 是 结 束 最优方案 图3-1 运输问题求解思路图 1.最小元素法 2.西北角法 (左上角法) 3.沃格尔（Vogel）法(差额法) 初始基本可行解 1.最小元素法 优先考虑单位运价最小（或运距最短）的供销业务，最大限度地满足其供销量。 11 3 4 48 14 12 14 8 销量 22 6 5 8 10 9 10 2 16 11 12 4 产量 销地 产地 8 －8 －8 2 －2 －2 －10 －10 －14 －14 14 10 8 6 －8 －8 z=10*4+6*11+8*2+2*3+14*5+8*6 =246 2.西北角法 (左上角法) 优先满足运输表中西北角（即左上角）上空格的供销需求 11 3 4 48 14 12 14 8 销量 22 6 5 8 10 9 10 2 16 11 12 4 产量 销地 产地 8 －8 －8 ——优先考虑最大差额（最小运价优势）方案 3.沃格尔（Vogel）法(差额法) 行（列）差额（罚数）=次小运价系数-最小运价系数 11 3 4 48 14 12 14 8 销量 22 6 5 8 10 9 10 2 16 11 12 4 产量 销地 产地 1 1 0 行罚数 3 1 5 2 列罚数 得到初始调运方案为： x13=12，x14=4，x21=8， x24=2 , x32=14，x34=8 z=12*4+4*11+8*2+2*9+14*5+8*6 =244 z(最小元素法）=246 z（西北角法）=372 二、确定初始方案的步骤 初始方案就是初始基本可行解。 （1）选择一个xij，令xij= min{ai，bj}= 将具体数值填入xij在表中的位置； （2）调整产销剩余数量： 从ai和bj中分别减去xij的值， 若ai-xij=0，则划去产地Ai所在的行，即该产地产量已全部运出无剩余，而销地Bj尚有需求缺口bj-ai； 若bj-x