《运筹学课件第三章运输问题(浙江)》课件.ppt

* * * * * * * 运筹学 * 确定初始基础可行解 西北角法 沃格尔法 求非基变量的检验数 闭回路法 对偶变量法 确定进基变量 确定离基变量 得到新的基础可行解 表上作业法总结 沿闭回路调整运量 最小元素法 * 运筹学 * 单纯形法与表上作业法比较 单纯形法（Min） 表上作业法 确定初始基变量XB +松驰变量+（人工变量） XB——系数矩阵为I，m个 其余XN 最小元素法、沃格尔法 XB——数字格，m+n-1个 XN ——空格 检验数 基变量?j =0 非基变量?j =cj-cBB-1pj 基变量?ij=0 非基变量?ij =cij-Ui-Vj 调整 进基：min{?j∣ ?j 0} 出基： θ＝min{bi/aik，aik＞0} 进基：min{?ij∣ ?ij0} 出基： θ＝min{闭回路上偶数点xij} * 运筹学 * 3.5 运输问题的进一步讨论 一、产销不平衡的运输问题 1）产大于销，即∑ai∑bj 方法：虚购一销地Bn+1，其销量bn+1= ∑ai-∑bj Ai运往Bn+1物资的数量xin+1，就是产地就地贮存的物资量，因此，产地到虚销地的单位运价均为0，即cin+1 =0，这样，就转化成了一个产销平衡问题。 * 运筹学 * 例：某建筑公司有A1、 A2、 A3三个水泥库，其水泥贮存量分别为30吨、 50吨、 60吨，四个工地B1、 B2、 B3 、 B4需要水泥的数量依次为15吨、 10吨、 40吨、 45吨，已知从各库到各工地运送每吨水泥的费用如下表，求使运费最少的调运方案？ B1 B2 B3 B4 产量 A1 30 50 80 40 30 A2 70 40 80 60 50 A3 100 30 50 20 60 销量 15 10 40 45 解：计算∑ai=140，∑bj =110，∑ai∑bj所以要虚构一销地B4，其销量b5=30，而ci5 =0，这样，就转化成了一个产销平衡问题。 * 运筹学 * 2）产小于销，即∑ai＜∑bj 方法：虚购一产地Am+1，其产量Am+1= ∑bj -∑ai Am+1运往Bj物资的数量xm+1j，就是各销地缺货的物资量，因此，虚产地到各销地的单位运价均为0，即cm+1j=0，这样，就转化成了一个产销平衡问题。 例如： B1 B2 B3 B4 产量 A1 3 11 3 10 9 A2 1 9 2 8 4 A3 7 4 10 5 7 销量 13 6 15 6 * 运筹学 * 二、一些变形和推广 1、最大化问题 作法：1）找出单位物资效益表（cij）中的最大元素M，即M=max{cij} 2)令bij =M-cij，并视为运价。 3）由bij构成单位运价表，按通常的表上作业法求解，求得最优解后还要把所得结果转换为原问题的答案。 2、销量不确定（有最高需求和最低需求） 设销地Bk的最低需求为bk’，最高需求为bk’’ ，这时可把看作Bk’和Bk’’两个销地， Bk’需求量bk’ ， Bk’’的需求量bk’’ - bk’ * 运筹学 * 例：设某种材料有A1、 A2、 A3三个生产厂家，其产品供应B1、 B2、 B3 、 B4四个城市，假定等量的材料在这些城市的使用效果相同，已知各建材厂的年产量、各城市的年需求量以及各厂到各城市运送单位建材的运价如表所示，求使运费最少的调运方案？ B1 B2 B3 B4 产量 A1 16 13 22 17 50 A2 14 13 19 15 60 A3 19 20 23 M 50 最低需求 30 70 0 10 最低需求 50 70 30 不限 解释c34 =M（M是一个无穷大的正数），这意味着不允许从A3运货至B4，或者因为交通不方便等原因，使从A3到B4不可能送货。 * 运筹学 * B1 B2 B3 B4 产量 A1 16 13 22 17 50 A2 14 13 19 15 60 A3 19 20 23 M 50 最低需求 30 70 0 10 最低需求 50 70 30 不限 B1’ B1’’ B2 B3 B4’ B4’’ 销量 30 20 70 30 10 50 A1 A2 A3 A4 产量 50 60 50 50 16 14 19 M 16 14 19 0 13 13 20 M 22 19 23 0 17 15 M M 17 15 M 0 * 运筹学 * 3、指定销售问题 如规定销地1的需求量必须由产地4供应，如何处理？ 1）直接令x41=b1 2)令c41=-M，或者c11=c21=c31=M这样销地1的需求量肯定是由产地1供应了。 * 运筹学 * 4、缺货损失问题如下表，设销地1不允许缺货；销地2缺货，单位损失费3元；销地3缺货，单位损失费2元，问如何处理？ B1 B2 B3 产量 A1 5 1 7 10 A2