2019/6/20 用西北角法确定例31初始调运方案 用最小元素法确定例31初始调运方案 调、地 运 B B 产量 B B 产量 1009010-70: -00-280100 10090 79100100260100 A Xu X 80:506520075☐250200 89150第100752Q-100 A X2 100 10:200 销量 100 150 200 50 50 00 40,02 A 最优性检验 (一)闭回路法 检查当前调运方案是不是优方案的过程就是优性 什么是闭回略？ 检查的万运 导于零，则该方案就是最优调运方案，否则就应 甲实的护钠的度一条封闭查镜。且所有的边部是水 (一)阳回略法 (二)对得变量法 △世 △世 (一)闭回略法 约定作为起始顶点的非基变量为奇数点1其它 以确定了初始调运方案的作业表为基赠，以一 项点顺次排列，那度，该非基变量x的检验数： 个非基变量作为起始顶点，寻求闭回略。 0,三（闭回略上奇数次顶点运距或运价之和） 可以证明。如果对闭同路的方向不加区别，对 (闭回略上偶囊次顶点运距或运价之和) A性 A性 d2019/6/20 4 调 销地 运 量 产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450 用最小元素法确定例3-1初始调运方案 150 100 100 100 100 100 100 调 销地 运 量 产地 B1 B2 B3 产 量 A1 90 X11 70 X12 100 X13 200 A2 80 X21 65 X22 75 X23 250 销 量 100 150 200 450 用西北角法确定例3-1初始调运方案 100 100 100 50 50 200 200 得到初始调运方案为： x11=100，x12=100，x22=50，x23=200 检查当前调运方案是不是最优方案的过程就是最优性 检验。检查的方法：计算非基变量（未填上数值的格， 即空格）的检验数（也称为空格的检验数），若全部 大于等于零，则该方案就是最优调运方案，否则就应 进行调整。 （一）闭回路法 （二）对偶变量法 最优性检验 （一）闭回路法 什么是闭回路？ 图中的折线构成一条封闭曲线，且所有的边都是水 平或垂直的； （a） （b） （c） （d） 以确定了初始调运方案的作业表为基础，以一 个非基变量作为起始顶点，寻求闭回路。 该闭回路的特点是：除了起始顶点是非基变量 外，其他顶点均为基变量（对应着填上数值的格）。 可以证明，如果对闭回路的方向不加区别，对 于每一个非基变量而言，以其为起点的闭回路存在 且唯一。 （一）闭回路法 约定作为起始顶点的非基变量为奇数点1 其它 顶点顺次排列，那麽，该非基变量xij的检验数： 现在，在用最小元素法确定例3-1初始调运方案的 基础上，计算非基变量X12的检验数 ：  ij =（闭回路上奇数次顶点运距或运价之和）- （闭回路上偶数次顶点运距或运价之和） （3-1）