管理运筹与学 运输问题 .pptVIP

管理运筹学运输问题 第五章 运输问题 运输问题是线性规划问题的特例。 产地：货物发出的地点。 销地：货物接收的地点。 产量：各产地的可供货量。 销量：各销地的需求数量。 运输问题就是研究如何组织调运，既满足各销地的需求，又使总运费最小。 第一节 运输模型 某饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。 第一节 运输模型 (1)决策变量。设从Ai到Bj的运输量为xij， (2)目标函数 minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 (3)约束条件。产量之和等于销量之和,故要满足： 供应平衡条件 第一节 运输模型 二、表式运输模型 第一节 运输模型 产销平衡 第一节 运输模型 产大于销 第一节 运输模型 产小于销 第一节 运输模型 系数矩阵的结构如下：（决策变量m?n，约束方程m+n个） 第二节 表上作业法 表上作业法适合于产销平衡的运输问题 求解步骤： 找出初始方案（初始基可行解）：在m?n维产销平衡表上给出m+n-1个数字。 最优性检验：计算各非基变量的检验数，当?ij?0最优。 方案调整与改进：确定进基变量和离基变量，找出新的基可行解。 第二节 表上作业法 最小元素法 “就近运给”， 从单位运价表中最小运价开始确定供销关系， 逐次挑选最小元素，安排运量min{ai , bj}。 最大差额法 不能按最小运费就近供应，就考虑次小运费。 各行(各列)的最小运费与次小运费之差称为行差(列查)。 差额越大，说明不能按最小运费调运时，运费增加最多。 对最大差额处就采用最小运费调运。 第二节 表上作业法 从单位运价表中逐次挑选最小元素，安排运量 min{ai,bj}。 然后，划去该元素所在行或列： 当产大于销，划去该元素所在列； 当产小于销，划去该元素所在行。 第二节 表上作业法 判别方法是计算非基变量的检验数： ?ij= cij – CBPij’= cij – CBB-1Pij 运输问题的目标函数要求为最小，即当?ij?0视为最优。 位势法计算检验数(原理不做要求) ?ij= cij – CBPij’= cij – CBB-1Pij ?ij = cij –(ui+vj ) ui代表产地Ai的位势量，vj代表销地Bj的位势量。 基变量的检验数为0，即?ij= cij –ui – vj =0， 并令u1 =0，计算各行各列的位势量。 第二节 表上作业法 基变量的检验数?ij= cij –ui – vj =0， 即cij =ui +vj ， 且令u1 =0，计算位势量ui和vj 第二节 表上作业法 计算非基变量的检验数?ij= cij –ui – vj 第二节 表上作业法 确定进基变量 检查非基变量xij的检验数?ij ，按 min{?ij| ?ij 0}= ?lk 确定xlk进基。 确定离基变量 非基变量xlk进基之后，能让它的运量增加多少呢？ 就要求它所在行和列的运量保持产销平衡。 保持产销平衡的方法是闭回路法。 闭回路法：以进基变量xlk所在格为始点和终点，其余顶点均为基变量的封闭回路。 闭回路的画法：从进基变量xlk所在格开始，用水平或垂直线向前划，每碰到一个基变量格转90o，继续前进，直到返回始点。 奇偶点： 始点是偶点，依次奇偶相间标注；偶点标“+” ，表示运量增加量；奇点标“-” ，表示运量减少量。 调整量：最小可减少的运量，即奇点运量的最小值。 奇点运量的最小值所在格的基变量离基。 第二节 表上作业法 x12 进基 最小调整量为2， x11 离基 第二节 表上作业法 非最优方案的调整 所有偶点的值都加上调整量； 所有奇点的值都减去调整量； 获得一个新的运输方案。 第二节 表上作业法 基变量的检验数?ij= cij –ui – vj =0，且令u1 =0，计算位势量ui和vj 第三节 产销不平衡问题 产销平衡的运输问题采取表上作业法求解。 产销不平衡的运输问题需划成产销平衡问题再求解。 产大于销：