文档介绍：回顾
运输问题的数学模型及其特点;
运输问题解法—表上作业法;
(两个表格:产销平衡表,单位运价表)
表上作业法中初始基可行解的确定方法:最小元素法;Vogel法(最大差额法)
闭回路的建立与闭回路法求解检验数
1
1、运输问题的数学模型
2
2、最小元素法确定初始基可行解的步骤
步骤一:确定第一个基变量
方法:(1)从单位运价表中,找出最小运价;(2)对于最小运价处,用所在行的产量最大限度满足销售量(所在列)的需求。将满足之数填入产销平衡表中相应的位置处;(3)观察产和销的关系:1)如果产量用完,则划去所在行的单位运价信息<表示此产地不能再供应其他地方>;如果销量得到满足,则划去所在列的单位运价信息<表示此销售地不再有需求>。(注意产量和销量的变化)
步骤二:确定第二个基变量
方法:在剩下的单位运价信息中,寻找最小值。按照上述方法进行操作。
3
3、伏格尔方法(Vogel)确定初始基可行解主旨:最大差额处,优先按最小运价进行调运。
第一步:计算单位运价表中同行、同列的最小运费与次小运费之差,分别列在单位运价表的最右列和最下行(行差和列差)。
第二步:对行差和列差进行对比,找出最大差额。以与最大差额值同行(或同列)的最小运价为准,倾所在行的产量,最大限度地满足所在列的需求;一旦需求(或库存)被彻底满足(或库存调光),则随即划去该列(或行)的所有运价信息。(注意产量和销量的变化)
第三步:重新计算同行同列的最小运费与次小运费之差,并对其它未被确定调拨值的行列,重复第二步的处理,直至构造出某初始调拨方案(初始解)。
4
4、最优性检验的核心思想
1、最优检验判断思路:确定初始基可行解后,调查非基变量取值变化对总运费的影响。
2、实现方法:在确定的初始基可行解基础上,当非基变量有取值时,考虑总的运费的变化情况? (1)如果所有情况下总费用均增加,证明初始方案为最优; (2)一旦出现了总费用降低,代表给该非基变量安排运量可更优,说明最初方案需要优化。
3、需要解决的问题:当非基变量取值时,为保证产销平衡表上的产销平衡,会引起已确定的基变量的连锁变化,导致相应的行或列基变量的波动。→需要靠闭回路法来确定基变量的变动情况。
5
5、闭回路法的构造
(1)闭回路:调运方案中由一个空格(非基变量)和若干个有数字格(基变量)的水平和垂直连线所组成的回路。
(3)闭回路的构造方法:从选中的空格(非基变量)出发,沿水平或铅垂方向前进,确保只以途中的有数字格(基变量)为拐点实施转向,直到返回出发的空格(非基变量) 。
6
闭回路形式
7
6、利用闭回路法计算非基变量检验数方法
1)参考产销平衡表,建立非基变量检验数表,用于填写各非基变量的检验数;
2)以确定的初始(或前一可行)调运方案表为准,寻找每个非基变量的闭回路;
3)在每个非基变量的闭回路上,计算当非基变量由“0”变为“+1”时,基变量的取值变化规律(+1,还是-1);
4)利用单位运价表中与闭回路相对应的运价信息,计算运费的变化情况(非基变量单位运价-∑处于奇数位置的基变量的单位运价+ ∑处于偶数位置的基变量的单位运价),即为非基变量检验数;
5)将非基变量检验数填入检验数表中相应位置。
8
销地
产地
B1
B2
B3
B4
产量
A1
非基变量1
(3)
非基变量2
(11)
4
(3)
3
(10)
7
A2
3
(1)
非基变量3 (9)
1
(2)
非基变量4 (8)
4
A3
非基变量5
(7)
6
(4)
非基变量6
(10)
3
(5)
9
销量
3
6
5
6
利用闭回路法计算非基变量检验数方法
A1B1非基变量:A1B1+1,A1B3-1,A2B3+1,A2B1-1.
运费影响:3-3+2-1=1>0(即为此非基变量的检验数)。
A2B2非基变量:A2B2+1,A2B3-1,A1B3+1,A1B4-1,A3B4+1,A3B2-1.
运费影响:9-2+3-10+5-4=1>0。
非基变量4:A2B4-1,A1B4+1, A1B3-1,A2B3+1。运费影响:8-10+3-2=-1<0。
9
销地
产地
B1
B2
B3
B4
A1
1
2
A2
1
-1
A3
10
12
非基变量检验数表
非基变量A2B4的检验数小于0,表明在A2B4处安排运量可以带来更低的运费→如何调整?
10