运筹学运输问题-2.ppt

1、1、回顾、运输问题数学模型及其特征运输问题解法表操作法(两个表：产销平衡表、单位运输价格表)表操作法中初始化学基可行解的确定方法：最小元素法Vogel法(最大差额法)闭合回路的建立和闭合回路法检验数，2，1，运输问题数学模型，3，2， 用最小元素法确定初始化学基可行解的步骤，步骤1 :确定第一个化学基变量法的方法： (1)从单位价目表中找到最小运费价；(2)在最小运费价中，用所在行的生产量最大限度地满足销售量(所在列)的需求。 (3)观察生产和销售的关系：1)如果生产量没有了，删除该行的单位运价信息如果销售量达到满脚丫子，就删除该列的单位运价信息。 (注意产量和销售量的变化)步骤2 :确定第二

2、个基本变量的方法：在剩馀的单位运价信息中找到最小值。 用上述方法操作。4、3、博尔格尔法(Vogel )确定了初期化学基可行解的主旨：以最大差额，优先以最小运费价运送。 第一步：与单位价目表同行，计算同列的最小运输费和子运输费的差，分别列在单位价目表的最右列和最下行(行差和列差)。 步骤2 :比较行差和列差，找出最大的差。 如果相对于与最大差额值相同的列中的最小运费价格倾斜所属行的产量，并且完全满足所属列的需求(或库存) (或调整库存)，则系统将清除该列(或行)中的所有运费价格信息。 (注意产量和销售量的变化)第三步：重新计算同行的最小运输费和子运输费的差，对其他拨号值未确定的矩阵，重复第二步

3、的处理，直到构成某个初始拨号计划(初始解)。 5，4，最优性检验的核心思想，1，最优性检验判断思路：在确定初始化学基可行解后，考察非化学基变量数值变化对总运输费的影响。 2、实现方法：根据确定的初始化学基的可行解，当非化学基变量取值时，考虑总运输费的变化情况；(1)证明所有情况下总费用都增加，则最合适；(2)当总费用出现减少时，代表对该非基本变量安排运输量更好，第一个方案是3、需要解决的问题：当非基变量取值时，为了保证生产销售平衡表的生产销售平衡，会引起确定的基变量的连锁变化，导致相应行和列的基变量的变动。 有必要用闭环法确定基变量的变动情况。 (1)闭合电路：调音方案中，由具有一个空格(非基

4、本变量)和几个数字格(基本变量)的水平和垂直线构成的电路。 (3)闭合回路的构造方法：从选择的空间(非基底变量)向水平或铅直方向前进，仅以途中的有数字格(基底变量)为拐点，确实转向直到返回到出发的空间(非基底变量)。 7、闭路形式、8、6、利用闭路法计算非化学基变量检验常数的方法，1 )参考产销平衡表，制作非化学基变量检验常数表，填写各非化学基变量检验常数2 )根据确定的初始(或之前可能的)运转计划表，查找各非基底变量的闭环3 )各非基底变量4 )利用单位运费表中与闭路对应的运费信息，计算运费的变化状况(非基底变量的单位运费-奇数位置的基底变量的单位运费在双位数位置的基底变量的单位运费)是非基

5、底变量检常数5 )将非基底变量检常数记入检常数表的相应位置。 9、闭环法的非基底变量检测数的计算方法、A1B1非基底变量： A1B1、A1B3-1、A2B3 1、A2B1-1 .运输费的影响：3-3 2-1=10 (即该非基底变量的检测数)。、A2B2非化学基变量： A2B2 1、A2B3-1、A1B3 1、A1B4-1、A3B4 1、A3B2-1.运输费的影响：9-2 3-10 5-4=10。 非化学基变量4:A2B4-1、a1b4-1、A1B3-1、A2B3 1。 受运输费的影响：8-10 3-2=-10。 10、非化学基变量检测常数表、非化学基变量A2B4的检测常数小于0，表示通过对A2

6、B4安排运输量，如何调整更低的运输费，11、7、问题是对各个非基本变量反复搜索闭环，计算“非基本变量1”时的总运输费检查数为0时，原初期方案和改善方案如何证明调用基变量不是最合适的？ 用电位法一次计算所有的检查数，分配给检查数为0的非基底变量，越大越好。 但是，必须考虑生产销售平衡的问题。 利用12、8、运输问题的鉴定法2位电势法、行电势和列电势2种数据，将检验数和单位运输价格结合起来，得到13、检验数方程式、ij=cijavj、ui、vj行电势列电势、单位运输价格、m产地、n据点时为m n个列电位，14，一般基变量的ij=0因此确定ui和vj可以由基变量的电位方程确定，ui vj=cij (

7、与基变量对应的单位运费)包括总共m n-1个方程，确定m n个未知数，通常是某个、15、a、用位势法求检验数的步骤，第一步骤：根据用最小元素法或Vogel法决定的初期运输量表，将化学基变量(或运输量)数据置换为与之对应的单位运价表(或修正单位价目表，求出与基本变量对应的价格信息的右侧表示行电位ui (I=1，2.m )，下侧表示列电位VJ (j=1，2.n )的步骤3 :在与基本变量对应的单位运输价格中，ui vj=cij。 步骤4 :在与非基变量对应的空间内计算检索常数ij=cij-(ui vj )，其中，若自由决定任意一个电位，则可以求出所有行和列的电位。 将检查数记入检查表的步骤5 :判

8、断检查数ij是否大于0，表示如果是那样就好。 否则，必须调整基本变量。 步骤6 :基本变量的调整用闭回路法进行。16、初始运费表、化学基变量的单位运费价目表、步骤1 :化学基变量的单位运费价目表、单位运费价目表、b，例如p88、17、步骤2 :行电势和列电势的值、化学基变量的单位运费价目表、1 )关于化学基变量cij=ui vj； 2 )任意决定一个电位即可。 0，10，3，- 1，2，- 5，9，18，步骤3 :根据行二进制位电势和列二进制位电势计算非基底变量检测常数，使用0，10，3，- 1，2，- 5，9，1 )非基底变量检测常数为cij-(ui vj )； 2 )通过结合与非基底变量对

9、应的单位运费，能够计算所有非基底变量的检验常数。1、2、1、10、12、-1、19、初始调整表、7、9、2、1、1、5、0、9、2、5、1、4、11、例2、20、利用所确定的ui和vj值，将非基本变量的检测常数与cij值一起进行计算，ij=cij (ui vj 2、1、1、5、14、-1、5、3、-4、22、确定1 )出现多个非基底变量检测常数0时，选择哪个非基底变量作为置换基底变量2 )如何决定变换基底变量？ 23、建构闭合电路，如何调整7、9、2、1、1、5、14、-1、5、5、3、-4、特异点、特异点、双位数点、基变量、非基变量、7、2、7、2、24、1、7、2、0、基变量？ 初始化学基

10、变量2、初始化学基变量3、初始化学基变量1、检测常数0的非化学基变量，一般必须在闭合电路中进行调整。25、8、化学基变量的调整方法采用闭环法调整输入化学基和输出化学基变量，(生产销售平衡时的运输问题)、26、化学基变量的调整方法，1 )选择负检验数中绝对值最大的空格(非化学基变量)，将其作为输入化学基变量2 )从该空格中该闭回路是唯一的3 )在闭回路中，在该空间调整闭回路中的最小基础变量的取值，以使所选空间中的运输量尽可能地增加，并且将该非基础变量变为基础变量(被基础变量替换)。原始的最小基础变量成为非基础变量，在新的运输计划中被清除(替换基础变量)。 4 )闭路上的其他基变量进行相应的调整，

11、保证产销平衡，获得新的运输计划；5 )继续用位势法进行检验，观察检验数是否全部大于零。 出现负数时，用1)4)的方法进行基底变量的调整，直到所有的检验常数都为正。 27、化学基变量的调整例1、1、2、1、10、12、-1、检查数、初始调整方案、28、化学基变量的调整方法、查找以检查数为负的非化学基变量为起点的闭环的基底变量，将非基底变量作为基底变量：将闭环电路中最小的基底变量的运输量调整为该非基底变量，调整量为mm 在使调整后的基变量成为非基变量的闭回路中，调整其他基变量，保证生产销售的平衡。 获得新的运输计划。1、0、2、5、29、初始调整方案(初始化学基可行解)、调整后的调整方案(优化后的

12、化学基可行解)、运输费： 86、运输费： 85、30、检验常数表、优化调整方案、31、双位数点减少、特异点加算、7、9、2、1、1、5、14、-1、5、3、-4、特异点、特异点、双位数点、0、6、3、1、32 8，运输问题表作业法程序，33、9，生产大头针不平衡问题，核心方法：将生产大头针不平衡转换为生产大头针平衡情况，用表作业法求解。 (1)关于“生产销售”的状况，生产量溢出，可以将一个销售地(库存)虚拟化，将多馀的生产量运送到该销售地，如果其销售量是“生产-销售”，则可以云同步，使该虚拟销售地的单位运价为零(虚拟的生产量=“销售-生产”作为虚拟产地的同时，该虚拟产地的单位运输价格为0.34

13、，例1生产超过销售量，35，解法：虚拟销售地，销售量作为生产销售量的差。 b4=ai-bj=4该列单位的运费价格为0，成为生产销售平衡的问题，36、例2的生产比大头针小，37，解法：在虚拟的销售地，如果将其销售量的差b4=bj -ai=1，则该列的运费价格为0，这是生产销售、38、39、10、运输问题应用、资源不足分配问题、40、必须满足、最高和最低差额未必完全满足。问题分析、一、产销量问题。 产量160，最低需求110，最高需求是无限的，但根据现状，最高市场总需求是210 (因为销售地最多可以获得60 )，是生产销售的不平衡问题，2，如何转换为生产销售平衡的问题？ 增加虚拟产地。 3、将需求量化为两个，一部分满足最低需求，一部分满足差额。 41、步骤1 :转换生产销售平衡问题，解：增设产地丁，其供给量为最大需求量供给量50，虚拟产地的运价如何确定，最小需求、最高需求与最低需求之差，42，m表示无限大的正数，最低需求表示无法从d产地供给。 第二步：确定虚拟产地的单位运价，原则：销售点的最小需求必须得到满足，但最高需求未必得到满足。 最小销量的满脚丫子表示没有来自虚拟产地。 m，m，m，