运筹学运输问题表上作业法讲述.ppt

运 筹 学 李细霞 2013物流工程1班 2014~2015学年第二学期 课程主要内容 Transportation problem 3 第三章 运输问题 学习目标 主要内容 思考 问题描述 7 表格 模型 8 生产量：A1-7吨， A2-4吨， A3-9吨 销售量：B1-3吨，B2-6吨，B3-5吨，B4-6吨 9 10 11 二、建立模型 设：xij——第i产地到第j销地之间的调运量，则有 Min z = ? ? cij· xij 3 4 i=1 j=1 x11+x12+x13+x14=7 x11+x21+x31=3 xij?0,(i=1,2,┄,3；j=1,2,┄,4) 产量限制 销量限制 x21+x22+x23+x24=4 x31+x32+x33+x34=9 x12+x22+x32=6 x13+x23+x33=5 x14+x24+x34=6 12 ??ai=?bj 13 调运模型为： 14 15 有何特点？ 16 1.变量数：m?n个 2.约束方程数：m+n个 最大独立方程数：m+n-1 3.系数列向量结构： 17 唯一最优解？无穷多最优解？ 18 基本可行解 检验数 基变换 表上作业法 19 单纯形法在求解运输问题时的一种简化方法 20 表上作业法步骤 产量 产地 销地 A1 A2 A3 B1 B2 B3 B4 销量 4 1 3 10 2 5 3 6 5 6 7 4 9 3 11 9 8 7 10 运价 总产=总销 22 23 西北角法 3 4 2 2 3 6 有何疑问？ 24 25 26 充要条件 举例 1 2 3 4 1 2 3 1 2 3 4 1 2 3 1 2 3 4 1 2 3 1 2 3 4 1 2 3 下面这些有数格组成了闭回路（不能作为基本可行解） 1 2 3 4 1 2 3 1 2 3 4 1 2 3 1 2 3 4 1 2 3 1 2 3 4 1 2 3 1 2 3 4 1 2 3 1 2 3 4 1 2 3 下面这些有数格没有组成闭回路（可以作为基本可行解） 29 30 31 最小元素法 3 11 3 10 1 9 2 8 7 4 10 5 3 1 4 6 3 3 32 33 伏格尔法 34 产地 销地 A1 A2 A3 B1 B2 B3 B4 行差额 列差额 3 11 3 10 1 9 2 8 7 4 10 5 0 1 1 2 5 1 3 0 1 2 2 - 1 3 0 1 - 2 - 1 2 7 6 - - - 1 2 Vogel法: 产地 销地 A1 A2 A3 B1 B2 B3 B4 7 4 9 产量 销量 3 6 5 6 6 3 5 2 1 3 产销平衡表 单位运价表 伏格尔法（差额法） 对最小元素法的改进 35 36 课堂练习：用最小元素法求初始解 37 5 3 4 1 7 38 销地 利润 产地 A B C D 产量 Ⅰ 10 5 6 7 250 Ⅱ 8 2 7 6 250 Ⅲ 9 3 4 8 500 销量 150 200 300 350 39 最优性检验——闭回路法 表示什么？ 每个空格都能找到闭回路吗？有的话，是否唯一？ 46 若存在某些检验数小于0，则说明调整后运价将减少。（不是最优解） 若存在某些检验数等于0，则说明调整后运价将不发生改变。（多个最优解） 若所有检验数大于0，说明调整后运价将增加。（唯一最优解） 注意是目标最小化的问题 48 最优性检验——位势法（对偶变量法） 49 2. 令u1=0，则依cij=ui+vj 计算各ui和vj 3.计算空格处位势；?ij=cij-（ui+vj） 1.在表中增加一行一列,填上行位势ui,列位势vj, 在对应初始方案有数格处写0（基变量检验数为0）； 位势法的图表形式: ui 产地 销地 A1 A2 A3 B1 B2 B3 B4 vj u3=-5 3 11 3 10 1 9 2 8 7 4 10 5 B1 B2 B3 B4 A1 4 3 A2 3 1 A3 6 3 0 0 0 0 0 0 v3=3 v4=10 u1=0 u2=-1 v1=2 v2=9 1 2 1 -1 10 12 50 位势法计算非基变量xij检验数的公式 σij=cij-（ui+vj） 比较检验数计算的两种方法 51 52 三、方案改进（闭回路法） 当至少有一个非基变量的检验数是负值时，说明作业表上当前的调运方案不是最优的，应进行调