运筹运输问题.pptVIP

第四章 特殊的线性规划——运输问题 模型及其特点 求解思路及相关理论 求解方法——表上作业法 运输问题的推广 产销不平衡的运输问题 转运问题 4.1 运输问题模型与性质 一、运输问题的数学模型 1、 运输问题的一般提法： 某种物资有若干产地和销地，现在需要把这种物资从各个产地运到各个销地，产量总数等于销量总数。已知各产地的产量和各销地的销量以及各产地到各销地的单位运价（或运距），问应如何组织调运，才能使总运费（或总运输量）最省？ 2、运输问题的数学模型 设xij为从产地Ai运往销地Bj的物资数量（i=1，…m；j=1，…n），由于从Ai运出的物资总量应等于Ai的产量ai，因此xij应满足： 同理，运到Bj的物资总量应该等于Bj的销量bj，所以xij还应满足：  总运费为： 矩阵的元素均为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阶单位阵。 三.运输问题求解 —表上作业法 一、表上作业法的基本思想是:先设法给出一个初始方案,然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案，如图4-1所示。 表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。 1、初始基本可行解的确定 找到 m + n – 1 个不构成闭回路的基变量。 较常用的方法有西北角法、最小元素法和伏格尔法。 —西北角法 甲、乙两个煤矿供应A、B、C三个城市用煤，各煤矿产量及各城市需煤量、各煤矿到各城市的运输距离见表3-4，求使总运输量最少的调运方案。 得到初始调运方案为： x11=100，x12=100，x22=50，x23=200 运输费用为34250 2、最优性检验 检查当前调运方案是不是最优方案的过程就是最优性检验。检查的方法：计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。 ——闭回路法 以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。 该闭回路的特点是：除了起始顶点是非基变量外，其他顶点均为基变量（对应着填上数值的格）。 可以证明，如果对闭回路的方向不加区别，对于每一个非基变量而言，以其为起点的闭回路存在且唯一。 方程组的特点： ? 方程个数是m+n-1=2+3-1=4个，位势变量共有m+n=2+3=5个，通常称ui为第i行的位势，称vj为第j列的位势； 初始方案的每一个基变量xij对应一个方程——-—所在行和列对应的位势变量之和等于该基变量对应的运距（或运价）：ui+vj=cij； 方程组恰有一个自由变量，可以证明方程组中任意一个变量均可取作自由变量。 σ12=c12-（u1+v2）=70-（0+90）=-20 σ21=c21-（u2+v1）=80-（-25+90）=15 与前面用闭回路法求得的结果相同。 3、方案调整 当至少有一个非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调整。 若检验数σij小于零，则首先在作业表上以xij为起始变量作出闭回路，并求出调整量ε： ε=min{该闭回路中奇数次顶点调运量xij} ij 计算调整量：ε=Min（100，150）=100。 按照下面的方法调整调运量： 闭回路上，奇数次顶点的调运量减去ε，偶数次顶点（包括起始顶点）的调运量加上ε；闭回路之外的变量调运量不变。 得到新的调运方案： 1、产量大于销量 增加虚拟销地 虚拟销地的销量？运价？ 运价见下表，产地产量分别为7、5、7t，销地销量分别为2、3、4、6t，试决定总运费最少的调运方案。 2、产量小于销量 增加虚拟产地 虚拟产地的产量？运价？ 运价见下表，产地产量分别为7、5、2t，销地销量分别为2、3、4、6t，试决定总运费最少的调运方案。 3、销量非固定值 数据见下表，决定运费最少的调拨方案。 4、转运问题 数据见下表， 三个产地的产量分别为7、4、9t，四个销地的销量分别为3、6、5、6t，试决定运费最少的调拨方案。 例4-2初始调运方案位势变量对应表 450 200 150 100