运筹学课件第三运输问题(浙江).pptVIP

运筹学 第三章 运输问题 3.1 运输问题的表示 3.2 初始基础可行解 3.3 非基变量的检验数 3.4 基解的调整 3.5 运输问题的进一步讨论 运输问题的一般提法：假设有m个生产地点，可以供应某种物资（以后称为产地），用Ai来表示，i=1,…,m,有n个销地，用Bj来表示，j=1,…,n，产地的产量和销地的销量分别为ai,bj，从产地Ai到销地Bj运输一个单位物资的运价为Cij，这些数据可汇总于下表，在假设产销平衡的条件下，即∑ai= ∑bj，问该如何调运物品使总运费最小？ 建模：设xij表示从Ai到Bj的运量，则所求的数学模型为： 2.运输问题线性规划模型 3.运输问题的表格表示 2.初始基础可行解—西北角法 单纯形法与表上作业法比较 解：计算∑ai=140，∑bj =110，∑ai∑bj所以要虚构一销地B4，其销量b5=30，而ci5 =0，这样，就转化成了一个产销平衡问题。 例：某建筑公司有A1、 A2、 A3三个水泥库，其水泥贮存量分别为30吨、 50吨、 60吨，四个工地B1、 B2、 B3 、 B4需要水泥的数量依次为15吨、 10吨、 40吨、 45吨，已知从各库到各工地运送每吨水泥的费用如下表，求使运费最少的调运方案？ 2）产小于销，即∑ai＜∑bj 方法：虚购一产地Am+1，其产量Am+1= ∑bj -∑ai Am+1运往Bj物资的数量xm+1j，就是各销地缺货的物资量，因此，虚产地到各销地的单位运价均为0，即cm+1j=0，这样，就转化成了一个产销平衡问题。 例如： 二、一些变形和推广 1、最大化问题 作法：1）找出单位物资效益表（cij）中的最大元素M，即M=max{cij} 2)令bij =M-cij，并视为运价。 3）由bij构成单位运价表，按通常的表上作业法求解，求得最优解后还要把所得结果转换为原问题的答案。 2、销量不确定（有最高需求和最低需求） 设销地Bk的最低需求为bk’，最高需求为bk’’ ，这时可把看作Bk’和Bk’’两个销地， Bk’需求量bk’ ， Bk’’的需求量bk’’ - bk’ 解释c34 =M（M是一个无穷大的正数），这意味着不允许从A3运货至B4，或者因为交通不方便等原因，使从A3到B4不可能送货。 例：设某种材料有A1、 A2、 A3三个生产厂家，其产品供应B1、 B2、 B3 、 B4四个城市，假定等量的材料在这些城市的使用效果相同，已知各建材厂的年产量、各城市的年需求量以及各厂到各城市运送单位建材的运价如表所示，求使运费最少的调运方案？ 3、指定销售问题 如规定销地1的需求量必须由产地4供应，如何处理？ 1）直接令x41=b1 2)令c41=-M，或者c11=c21=c31=M这样销地1的需求量肯定是由产地1供应了。 4、缺货损失问题如下表，设销地1不允许缺货；销地2缺货，单位损失费3元；销地3缺货，单位损失费2元，问如何处理？ 三、生产与存储问题 例：某厂按合同须于当年每个季度末分别提供10、15、25、20台同一规格的起重机，已知该厂各季度的生产能力及生产每台起重机的成本如表所示，若生产出来的起重机当季不交货，每台每积压一个季度工厂需支付保管及维护费0.15元，试问在按合同完成任务的情况下，工厂应如何安排生产计划才能使全年消耗的生产与存贮费用的总和最少？ 发货点：生产起重机的四个季度发货量：生产能力收货点：按合同交付起重机的四个季度收货量：按合同提供起重机的数量cij=第i季度每台起重机的生产成本+（j-i）个季度每台起重机的存贮费（ji） 四、有转运的运输问题 1、运输表的构成 1）产地：原产地、中间转运站、转运物资的销地 2）销地：原销地、中间转运站、转运物资的产地 3）设各转运站转运物资的数量均为∑ ai 这样专职转运站的产量和销量均为∑ ai 而原产地Ai的产量均为（ai+∑ ai） 原销地Bj的销量均为（ bj+∑ ai） 4)将各条线路实际的运输单位列成单位运价表，其中不可能的运输其单位运价用M表示。 2、举例： A、B两个化肥厂每年各生产磷肥900、600万吨，这些化肥要通过公路运到三个港口，然后再装船运往其他各地，已知三个港口C、D、E每年能承担的船运量分别为700、400、300万吨，两个工厂及三个港口之间均有公路相通，且已知单位运价如表所示，为按需要把磷肥运到各港口，怎样安排运输才能使运费最少？ 确定初始基础可行解 西北角法 沃格尔法 求非基变量的检验数 闭回路法 对偶变量法 确定进基变量 确定离基变量 得到新的基础可行解 表上作业法总结 沿闭回路调整运量 最小元素法 表上作业法 单纯形法（Min） 确定初始基变量XB +松驰变量+（人工变量） XB——系数矩阵为I，m个 其余XN 最小元素法、沃格尔法 XB