第二章__运输问题.ppt

Chapter 1 第二章 运输问题 一、运输模型（产销平衡） 例1．某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示： 问：应如何调运，使得总运输费最小？ 产销平衡表 满足产地产量的约束条件为： X11+X12+X13=200 X21+X22+X23=300 满足销地销量的约束条件为： X11+X21＝150 X12+X22＝150 X13+X23＝200 使运输费最小的目标函数为： minz＝6X11+4X12+6X13+6X21+5X22+5X23 Xij=0 一般运输问题的线性规划的模型： 有m个产地生产某种物资，有n个地区需要该类物资。Al，A2，…，Am表示某种物资的m个产地；Bl，B2，…，Bn表示某种物资的n个销地； 令a1, a2, …, am表示各产地产量， b1, b2, …, bn表示各销地的销量，?ai=?bj 称为产销平衡。 Cij表示把物资从产地Ai运到销地Bj的单位运价。 同样设Xij表示从产地Ai运到销地Bj的运输量。 则产销平衡的运输问题的线性规划模型如下所示： 共有2个产地和3个销地，产销平衡。 各产地产量a=(200,300) 各销地销量b=(150,150,200) 各点之间的运价c= 二、表上作业法 表上作业法是单纯形法在求解运输问题时的一种简化方法，其实质是单纯形法。 (1)给出初始调运方案。——初始基可行解：即在(m×n)产销平衡表上给出m+n-1个数字格。 (2)检验方案是否最优，若是最优解，则停止计算；否则转下一步。 求各非基变量的检验数，即在表上计算空格的检验数。 (3)调整调运方案，得新的方案。——确定入基和出基变量，找出新的基可行解。在表上用闭环回路法或乘数法。 (4)重复(2),(3)直到求出最优方案。 【定理】：产销平衡的运输问题一定有可行解，且一定有最优解。 证：记∑ai= ∑bj=Q Xij=aibj/Q就是一个可行解，因为Xij≥0，且满足 ∑Xij=ai, ∑Xij=bj 又因为Cij≥0,Xij≥0,所以目标函数有下界零。 因而运输问题一定有最优解。 1、确定初始基可行解 最常用的方法是最小元素法。——既简便，又尽可能接近最优解。 最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定供销关系，同时兼顾各产销地的需求，然后次小，一直到给出初始基可行解为止。 例1：某公司经销甲产品，它下设三个加工厂，每日的产量分别为A1－7吨，A2－4吨，A3－9吨。该公司把这些产品分别运往四个销售点。各销售点每日销量为B1－3吨，B2－6吨，B3－5吨，B4－6吨。已知从各工厂到各销售点的单位产品的运价如下表所示。 产销平衡表 1）找出最小运价为1，先将A2的产品供应给B1，因a2b1，A2除满足B1的全部需要外，还可多余1吨产品。在(A2,B1)的交叉格处填上3。并将B1列运价划去。 2）在未划去的元素中再找出最小运价2，确定A2多余的1吨供应B3。在(A2,B3)的交叉格处填上1。并将A2行运价划去 3）在未划去的元素中再找出最小的运价3，这样一步步进行下去，直到运价表上的所有元素划去为止。 最后在(A1,B4)的交叉格处填上3，将A1行和B4列运价同时划去，得到一个初始调运方案。这方案的总运费为86元。 最小元素法中的退化情况 第一次划去第1列B1，第二次最小运价为2，对应的销地B2销量和产地A3的产量未分配量皆为6，故同时划去B2列和A3行。非零的数字格小于(m+n-1)个。 出现退化时，要在同时被划去的行列中选一个空格填0，此格作为有数字格。。 伏格尔法(Vogel)——差额法： 最小元素法的缺点是：为了节省一处的费用，有时会造成在其他处要多花几倍的运费。 伏格尔法考虑到：一产地的产品假如不能按最小运费就近供应，就应考虑次小运费。这就有一个差额，差额越大，说明不能按最小运费调运时，运费增加越多。因而对差额最大处，就应当采用最小运费调运。 1）分别计算出各行和各列的最小运费和次最小运费的差额，填入表格的最右列和最下行。 2）从行或列差额中选出最大者，选择它所在行或列中的最小元素。B2列中的最小元素是4，可确定A3的产品先满足B2的需要，同时将B2列运价划去。 3）对未划去的元素再分别计算出各行、各列的最小运费和次最小运费的差额，重新填入表格的最右列和最下行。重复1）2），直到找到初始调运方案。总运费为85元。 伏格尔法给出的初始解比用最小元素法给出的更接近最优解。本例用伏格尔法给出的初始解就是最优解。 2、调运方案的检验 判别的方