CH3交通问题.ppt

;一般描述 ;产 地;数学模型 ; 运输问题模型是线性规划模型，当然可以用单纯形法求解，但由于其系数矩阵具有特殊形式，可以使单纯形法的操作更为简便，这就是表上作业法（其实质是单纯形法）。 ;表上作业法 ;2) m+n-1个数字格不构成闭回路。; 产地 销地; 产地 销地;伏格尔法步骤 ;闭回路法 画法：从某一空格出发，横向或纵向画直线，在适当的数字格转向以回到出发的空格。 ; 产地 销地; 产地 销地; 产地 销地; 产地 销地; 产地 销地; 产地 销地;位势法理论依据; 位势法求检验数： 原理：利用基变量检验数为0，求非基变量检验数;第三章：运输问题（1）;第三章：运输问题（1）;XB;基变量X24检验数满足： C24-(u2+v4)=0 ----------------------------（1） 基变量X34检验数满足： C34-(u3+v4)=0 ----------------------------（2） 基变量X21检验数满足： C21-(u2+v1)=0 ----------------------------（3） 基变量X32检验数满足： C32-(u3+v2)=0 ----------------------------（4） 基变量X13检验数满足： C13-(u1+v3)=0 ----------------------------（5） 基变量X14检验数满足： C14-(u1+v4)=0 ----------------------------（6）;表上作业法 ;用位势法求检验数;3 方案的改进——闭回路调整法 ;4 表上作业法的说明 ; 产地 销地; 表上作业法出现的几种情况： 1.无穷最优解—非基变量检验数为0 (类似一般单纯形法) 2.退化 3.不可能有无界最优解，因 运量有限;退化情况;产销平衡问题是运输问题中的特例，而不平衡问题才具有普遍意义。 数学模型表述: 在产销不平衡运输问题中，可分“产大于销”和“销大于产”两类。 设有m个产地，n个销地，其中第i个产地（i=1,2,…,m）的产量为ai， 第j个销地（j=1,2,…,n）的销量为bj 若， 则称该问题为产大于销的运输问题； 若， 则称该问题为销大于产的运输问题。 ;产销不平衡运输问题及求解 总思路：产销不平衡 产销平衡 1.若 产销 销+存贮=产 2.若产销 产+虚产地=销 难点：造假， ???假求真（非以假乱真）;第三章：运输问题（2）; 产大于销时，假想一销地（即储存地），将运输表增加一列。由于是储存，无实际运量，其单位运价为0，其销量为产大于销的部分。这样不平衡问题就转化为平衡问题了。;3 2 4;15;15; 销大于产时，假想一产地，将运输表增加一行。由于是脱销，无实际运量，其单位运价为0，其销量为销大于产的部分。这样，不平衡问题就转化为平衡问题了。 因A3行无实际运输量，为使所得初始解尽量好，用最小元素法或伏格尔法求初始调运方案时，可先不考虑A3行。 ; ;这是一个产销不平衡的运输问题，总产量为160万吨，四个地区最低需求为110万吨，最高需求为无限。根据现有产量，第四个地区每年最多能分配到60万吨（当每个地区按最低需求为110万吨时），这样最高需求为210万吨，大于产量。为了求的平衡，在产销平衡表中增加一个假想的农药厂D其产量为50万吨。由于各地区的需要量包含两部分，如地区一其中30万是最低需求，故不能由假想农药厂D供给，令相应的运价为M，而另一部分20万吨满足不满足均可，因此可以由D厂供给令运价为0。对凡是需求分两种的地区实际上可按照两个地区看待。则可写出这个问题： 产销平衡表 ;产地 ;产地 ;产地 ;; 运输问题应用举例： 把线性规划问题转化为运输问题？？ 已知运价表 Cij Cij：已知