物流运输方案的选择.pptx

1、物流运输方案优化,制作人：李媛媛,运输规划的数学模型,一,产销平衡的运输问题,二,产销不平衡的运输问题.,三,运输问题 ( Transportation Problem),第一节 运输问题的数学模型,一、问题的提出,例1,产销平衡表,二、运输问题的一般数学模型,有m个产地生产某种物资，有n个地区需要该类物资；,设xij表示产地 Ai 运往销地B j 的物资量，cij表示对应的单位运费，则我们有运输问题的数学模型如下：,令a1, a2, , am表示各产地产量， b1, b2, , bn表示各销地的销量；,一般满足产销平衡：ai=bj,当产大于销时，其模型是：,当产小于销时，其模型是：, 运输问

2、题是特殊的线性规划问题。, 普通运输问题是追求运费最少问题。,例1、 某部门有3个同类型的工厂（产地），生产的产品由4个销售点出售，各工厂的生产量、各销售点的销售量（假定单位为t）以及各工厂到销售点的单位运价（元/t）示于下表，问如何调运才能使总运费最小？,第一节 产销平衡的运输问题,该运输问题的数学模型为：,1.最小元素法,基本思想:,就“近”供应，从运输表中最小运价所在格开始确定供销关系。,缺点:,为节省一处费用，会使别处费用增加很多，因此，其初始基可行解往往离最优解甚远，需要较多的迭代过程。,此时得到一个初始调运方案（初始可行解）：,其余变量全等于零。,总运费为（目标函数值）,此解满足所

3、有约束条件，且基变量（非零变量）的个数为6 （等于m+n-1=3+4-1=6).,2.伏格尔法（Vogel）,基本思想:,同时考虑每一产地（销地）与每一销地（产地）之间的最小运价和次小运价，若两者差额大，说明若不能按最小运价供应，就有可能按次小运价供应，从而运费很高。因此，应先对最大差额所在的行或列，按最小元素确定供销关系。,优点:,按此法所得基可行解较最小元素法所得可行解更接近最优解。,此时得到一个初始调运方案（初始可行解）：,其余变量全等于零。,总运费为（目标函数值）,此解满足所有约束条件，且基变量（非零变量）的个数为6 （等于m+n-1=3+4-1=6).,三、求检验数并进行最优解的判定

4、,1. 闭回路法,检验数即调运方案中空格的检验数ij，当所有ij 0，则得最优解。,对于运输表中的任意一个空格（Ai，Bj）,以该空格为出发点，沿水平方向或垂直方向前进，遇到一个适当的数字格，转90度后继续前进，前进过程中可以穿过数字格或空格，经过若干次转向后又回到空格，这样经过的路径称为从Xij格出发的闭回路。,定理：非基变量闭回路存在且唯一性定理,用LP的对偶理论可以证明，检验数的公式为：,其中 分别称为行位势、列位势。,有基变量所对应的检验数为零，可从m+n-1个等式,解出所有的行位势、列位势。,可以证明，不论令 为何值， 始终不变。,2.位势法（对偶变量法）,即 将不会随 的取值而改变

5、。,为此，在求解时，为计算简便，可指定一个位势等于一个较小的整数或零。,行位势,列位势,四、解的改进（用闭回路法调整）,从最小负检验数所对应的空格进行调整,例3 对由最小元素法得出的初始解进行调整,调整方法：,1）找出闭回路,2）确定调整量 使最小负检验数所对应的空格达到最大的调整量，即 =min(1,3)=1,再按调整后的解由位势法计算空格的检验数,3,1,6,3,3,1,2,1,-1,10,12,(+),(-),(+),(-),4,1,5,2,续例2，继续迭代,此时得到一个最优解：,其余变量全等于零。,总运费为（目标函数值）,一、产销不平衡运输问题,第三节 产销不平衡的运输问题,对产销不平

6、衡问题，可转化为平衡问题，然后按表上作业 法求解。转换办法：, 若产大于销，增加一个假想的销地（可视为库存地）其销 量设定为余量，相应的运价设为0。, 若销大于产，增加一个虚拟的产地，其产量设定为不足 量，相应的运价也设为0。,例6 某市有3个造纸厂 ， 和 ，有4个集中用户 和 ，各工厂的生产量、各用户的需用量以及各 工厂到用户的单位运价（元/t）示于下表中，问如何调运 才能使总运费最小？,22,18,可增加一个假想的销地,3.在产销不平衡问题时，出现最低需求的情况,在产销不平衡时，某销地存在最低需求量（为必须提供量），则将该销地拆分为两个销地： 必须提供量 可调整提供量,对于增加的虚拟的产地，对这个销地的成本分别为： M 0 其他成本不变,推广：所有不可能的成本为M,例7 在产销不平衡问题时，出现最低需求的情况,如果从最高需求量与产量的关系来看,是需求量大于产量,因此需要虚设一个产地A3,其产量a3=7+4+5-5-8=3；但从最低需求量与产量的关系来看，产量大于需求量，且最低需求量必须获得满足，故不能从虚设的产地A3调运物品来满足销地的最低需求量。为此，将B1、B3分成最低需求量和可调控需求量，分别用B1、B1、B3、B3来表示，为了保证B1、B3的需求量是由产量产地A1、A2提供的，设B1、B3到产地A3的单位物品的运价为M，这里M为一个很大的