运筹学概论第3章运输问题.ppt

第三章 运输问题,运输问题及其数学模型 用表上作业法求解运输问题 运输问题的进一步讨论,某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的产量，各销地的销量以及各工厂到各销地的单位运价示于下表中，要求研究产品如何调运才能使总运费最小？,第一节 运输问题及其数学模型,解： 设xij表示由第i个产地运往第j个销地的产品数量，数学模型如下：,有m个产地生产某种物资，有n个地区需要该类物资 令a1, a2, , am表示各产地产量， b1, b2, , bn表示各销地的销量，ai=bj 称为产销平衡 设xij表示产地 i 运往销地 j 的物资量，cij表示对应的单位运费。,一、运输问题的一般数学模型,Bn,B2,B1,销地 产地,Am,A2,A1,如何建立供需搭配，使总的运输费用最小？,供需平衡表,设从Ai到Bj的物资运量为xij ，,产销平衡运输问题的数学模型：,Ai的产品全 部供应出去,Bj的需求全部得到满足,二、运输问题数学模型的特点,1运输问题有有限最优解,其中,（1）,则(1)就是运输问题的一个可行解；另一方面，运输问题的目标函数有下界，目标函数值不会趋于-，由此可知，运输问题必存在有限最优解。,若令变量,2.运输问题约束条件的系数矩阵,系数列向量的结构,m行,n行,产销平衡问题的所有约束条件都是等式约束。 各产地产量之和等于各销地销量之和。,3.运输问题的解,根据运输问题的数学模型求出的运输问题的解 X=(xij)，代表着一个运输方案，其中每一个变量xij的值表示由Ai调运数量为xij的物品给Bj。,运输问题是一种线性规划问题，可设想用迭代法进行求解，即先找出它的某一个基可行解，再进行解的最优性检验，若它不是最优解，就进行迭代调整，以得到一个新的更好的解，继续检验和调整改进，直至得到最优解为止。,为了保证运输问题的每步得到的解xij都是基可行解，要求: (1) 解X必须满足模型中的所有约束条件； (2) 基变量对应的约束方程组的系数列向量线性无关； (3) 解中非零变量的个数不能大于(+-1)个，原因是运输问题中虽有(m+)个约束条件，但由于总产量等于总销量，故只有(+-1)个结构约束条件是线性独立的； (4) 为使迭代顺利进行，基变量的个数在迭代过程中保持为(+-1)个。,平衡表、运价表合二为一,第三章 运输问题,运输问题及其数学模型 用表上作业法求解运输问题 运输问题的进一步讨论,一、计算步骤：,(1)按某种规则(最小元素法、西北角法)找出一个初始解（初始调运方案）。即在(mn)产销平衡表上给出m+n-1个数字格。,(2)对现行解作最优性判别，即求检验数(闭回路法)。如是最优解，则停止计算，否则转到下一步。,(3)对方案进行改善，找出新的调运方案(表上闭回路法调整) 。,(4) 重复(2)、(3)，直到求得最优调运方案。,第二节 用表上作业法求解运输问题,例 1 运输问题供需平衡表和运价表如下，求最优调运方案。,二、举例,（1） 最小元素法,该方案总运费： Z=43+310+31+12+64+35=86,找出初始调运方案,6,2,3,2,4,3,（2） 西北角法,优先满足运输表中西北角(即左上角)上空格的供销需求,该方案总运费： Z=33+411+29+22+310+65=132,2.最优解的判别 （位势法）,标准型运输问题的对偶问题是：,由原问题与对偶问题解的相互关系知，变量xij的检验数为：,位势法,令v1=0, 由c21=1= u2 +v1，得 u2=1,0,1,1,2,0,1,1,2,8,-3,7,位势表,2,9,8,9,-3,-2,检验数,(空格中数字为ui+vj ),0,1,1,2,8,-3,7,检验数表,1,2,1,-1,10,12,24=-10，当前方案 不是最优方案。,3.闭回路调整法改进方案,从(p,q)空格开始画闭回路，其它转角点都是填有运量的方格，并从(p,q)空格为第一个奇数顶点，开始给闭回路上的点按顺时针或逆时针依次编号。运输量最小的偶数格为换出变量,最小运量为调整量。,新的调运方案为：,7,1,3,4,9,11,10,2,3,10,8,5,4.表上作业法计算中的问题,(1)若运输问题的某一基可行解有几个非基变量的检验数均为负，在继续进行迭代时，取它们中的任一变量为换入变量均可使目标函数值得到改善，但通常取ij中最小者对应的变量为换入变量。 (2)有无穷多最优解。最终解中有非基变量检验数为零时，以此非基变量为换入变量，可求得另一基最优解。基最优解的任一凸组合都是最优解。,(3) 退化 当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中有可能在某一格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。在运输问题中，退化解是时常发生的。为了使表上作业法的迭代工作进行下去，退化时应在同时划去的一行或一列中的某个格中填入数字0，表示这个格中的变量是取值为0的变量，使迭代过程中基可行解的分量恰好为（m+n-1）个。,例2 某地区有三个化肥厂和四个产粮区。单位运价、供应量、需求量如表所示。确定最小运费方案。,4,6,2,3,0,3,课堂作业,（1）试用最小元素法列出初始基可行解。 （2）采用位势法作最优性检验。 （3）运用闭回路法进行解的调整。,第三章 运输问题,运输问题及其数学模型 用表上作业法求解运输问题 运输问题的进一步讨论,在很多运输问题中，总产量不等于总销量。这时，为了使用前述表上作业法求解，就需将产销不平衡运输问题化为产销平衡运输问题。,第三节 运输问题的进一步讨论,这时的数学模型是 ：,如果总产量大于总销量，即,若令假想销地的销量为 ，且,为借助于产销平衡时的表上作业法求解，可增加一个假想的销地 Bn+1，由于实际上它不存在，因而由产地 调运到这个假想销地的物品数量 (相当于松弛变量)，实际上是就地存贮在 的物品数量。就地存贮的物品不经运输，故其单位运价 。,则模型变为：,总销量大于总产量的情形可仿照上述类似处理，即增加一个假想的产地 ，它的产量等于：,由于这个假想的产地并不存在，求出的由它发往各个销地的物品数量