运筹学运输问题.ppt

回 顾 运输问题的数学模型及其特点； 运输问题解法—表上作业法； （两个表格：产销平衡表，单位运价表） 表上作业法中初始基可行解的确定方法：最小元素法；Vogel法（最大差额法） 闭回路的建立与闭回路法求解检验数 2、最小元素法确定初始基可行解的步骤 步骤一：确定第一个基变量 方法：（1）从单位运价表中，找出最小运价；（2）对于最小运价处，用所在行的产量最大限度满足销售量（所在列）的需求。将满足之数填入产销平衡表中相应的位置处；（3）观察产和销的关系：1）如果产量用完，则划去所在行的单位运价信息表示此产地不能再供应其他地方；如果销量得到满足，则划去所在列的单位运价信息表示此销售地不再有需求。（注意产量和销量的变化） 步骤二：确定第二个基变量 方法：在剩下的单位运价信息中，寻找最小值。按照上述方法进行操作。 3、伏格尔方法（Vogel）确定初始基可行解主旨：最大差额处，优先按最小运价进行调运。 闭回路形式 7、问 题 对于每一个非基变量，需要重复寻找闭回路，并计算“非基变量+1” 时对总运费的影响→繁琐。 当出现检验数0，证明原初始方案或改进方案还不是最优→如何进行基变量的调入调出？ 检 验 数 方 程 一般令基变量的λ ij= 0，故确定ui与vj可借助基变量的位势方程组来确定 A、位势法求检验数的步骤 第一步：根据最小元素法或Vogel法确定的初始运量表做一表格，将基变量（或运量）数据替换成与之对应的单位运价；（或对单位运价表进行修改，只保留与基变量对应的运价信息） 第二步：在右侧增加一列，下侧增加一行，用于填写位势数据。右侧表示行位势ui（i=1，2...m），下侧表示列位势vj（j=1，2...n）； 第三步：对于基变量对应的单位运价处，ui+vj=cij。随便确定任一个位势，即可求解全部行和列位势； 第四步：在非基变量对应的空格处，计算检验数λij=cij-（ui+vj）。并将检验数填入检验数表中； 第五步：判断检验数λij是否大于0，如是，则表示较优。如不是，则需要调整基变量。 第六步：基变量的调整采用闭回路法进行。 利用已确定好的ui与vj值，再结合cij值计算非基变量的检验数 8、基变量的调整方法—用闭回路法调整进基和出基变量 （产销平衡时的运输问题） 9、产销不平衡的问题 核心方法：将产销不平衡转换为产销平衡的情形，然后由表上作业法进行求解。 （1）对于“产销”情形：产量盈余，可虚拟一个销售地（库存），让多余的产量均运抵此销售地，则其销售量=“产-销”，同时令该虚拟的销售地的单位运价为0；（虚拟的销地） （2）对于“销产”，可虚拟一个产地，让其产量=“销-产”，同时令该虚拟的产地的单位运价为0. 例 1 产大于销 例 2 产小于销 10、运输问题的应用 短缺资源的分配问题 偶点基变量x31的取值 1 最小 ：θ= 1 Σa =Σb 5 7 9 4 收量 6 x34 16 2 12 x31 14 A3 5 10 18 8 x22 6 x21 11 A2 2 9 10 x13 1 18 x11 9 A1 0 发量 B4 11 B3 1 B2 4 B1 9 收点 发点 偶点减θ，奇点加θ 7 9 2 1 1 5 14 -1 5 5 3 -4 奇点① ③奇点 ②偶点 偶点④ 0 6 3 1 8、运输问题表上作业法的步骤 Σ50 ≠Σ46 18 12 16 销量 15 18 17 产量 5 9 2 3 1 7 6 2 8 B1 B2 B3 A1 A2 A3 销地 产地 解法：虚设一销地，令其销量为产销量之差。 b4=∑ai-∑bj=4 该列单位运价为0，即可化为产销平衡问题 Σ50 =Σ50 18 12 16 4 销量 15 18 17 产量 5 9 2 0 3 1 7 0 6 2 8 0 B1 B2 B3 B4 A1 A2 A3 销地 产地 22 23 5 10 8 bj 12 3 4 3 A2 10