运筹学运输问题精品管理.ppt

运输问题的典例 运输问题的数学模型 求解方法表上作业法,第三章 运输问题,特殊的线性规划,运输问题的典例 运输问题的数学模型 求解方法表上作业法,第三章 运输问题,特殊的线性规划,运输问题的典例,例1.某食品公司经销的主要产品之一是糖果.它下面设有三个加工厂,每天的糖果产量分别为:A1-7t,A2-4t,A3-9t.该公司把这些糖果分别运往四个地区的门市销售,各地区每天的销售量分别为：B1-3t, B2-6t，B3-5t,B3-6t.已知从每个加工厂到各销售门市部每吨的运价如表所示，问该食品公司应如何调运,在满足各门市部销售需要的情况下，使得总的运费支出为最少.,运输问题的一般提法,现有一批货物, 从m个供应地运往n个销售地, Ai ( i=1, ,m )处有货物ai吨，Bj ( j= 1,n)处需货物bj吨, 已知从Ai到Bj的运价为cij 元/吨. 问如何安排，既可以满足各销地需要，又使总费用最小？,供应量,需求地,供应地,需求量,调运量xij,运输问题的框图表示,产销表,运输问题的数学模型,单位运价表,运输问题的数学模型,运输表（运价，运量）作业表,销量,产 量,销地 产地,产销平衡条件下,设xij为从产地Ai运往销地Bj的物资数量(i=1,m;j=1,n） 从Ai运出的物资总量应等于Ai的产量ai， xij应满足：,运到Bj的物资总量应该等于Bj的销量bj， xij还应满足：,运输问题的数学模型,总运费为：,运输问题的数学模型,运输问题的数学模型,1.约束条件都是等式约束,2.总产量总销量,产销平衡的运输问题的特点与性质,3.系数矩阵是一个结构特殊的稀疏矩阵,将 约 束 方 程 组 展 开,约束方程组共包含mn个变量，(m+n)个约束条件,产销平衡的运输问题的特点与性质,产销平衡的运输问题的特点与性质,系数矩阵A：, 矩阵的元素均为1或0； 每一列只有两个元素为1，其余元素均为0； 将矩阵分块,特点是:前m行构成m个mn阶矩阵,而且第k个矩阵只有第k行元素全为1,其余元素全为0（k=1,m）;后n行构成m个n阶单位阵。 A的秩一般为m+n-1,为什么？,第i行,第m+j行,运输问题的典例 运输问题的数学模型 求解方法表上作业法,第三章 运输问题,特殊的线性规划,运输问题的典例 运输问题的数学模型 求解方法表上作业法,第三章 运输问题,特殊的线性规划,表上作业法,作业表（产销平衡表）：将运输问题的有关 信息表和决策变量调运量结合在一起构成 “作业表”（产销平衡表）。,表上作业法是单纯形法求解运输问题的一种简化方法，实质是单纯形法。但是具体计算和术语有所不同。,运输问题中寻找可行解,10,2,3,20,6,5,6,3,销量,9,5,6,3,4,7,4,8,2,9,2,1,7,10,11,4,3,3,产量,销地 产地,填有数字的格:对应运输问题解中的基变量取值，这里为3+4-1=6个,空格：对应解中非基变量,表上作业法的基本思想是:先设法给出一个初始方案(如典例所示),然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案。 表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。,表上作业法,判定是否 最 优？,求解思路图,表上作业法,1.最小元素法,2.沃格尔（Vogel）法,(一) 初始方案的给定,给定初始方案的方法很多(如前例)，一 般来说，希望方法简便易行，并能给出 较好的方案。减少迭代次数。这里介绍,1.最小元素法,基本思想：就近供应，即优先考虑单位运价最小（或运距最短）的供销业务，最大限度地满足其供销量。,3,1,6,4,3,3,-3,-3,3,1,6,4,3,3,Z = 4*3+3*10+3*1+1*2+6*4+3*5 = 86,最小元素法的说明,退化现象：,部分产量和部分销量和,在迭代过程中，可能出现一行和一列同时被划去。,3,4,6,1,6,0,为使迭代过程中基变量的个数恰好为(m+n-1)个，应在同时划去的一行或一列中的某个格中填入数字0，表示这个格中的变量是取值为0的基变量。以便当做有数字的格看待。,3,4,6,1,6,0,基本思想：优选考虑最大差额（最小运价优势）方案 行（列）差额（罚数）=次小运价系数-最小运价系数,2.沃格尔（Vogel）法(差额法),0,1,1,2,5,1,3,( ),6,2,2,0,0,7,1,3,1,2,1,2,1,1,6,2,( ),3,3,( ),5,2,1,10,8,( ),6,3,3,5,2,1,沃格尔法Z = 5*3+2*10+3*1+1*8+6*4+3*5 = 85,最小元素法Z = 4*3+3*10+3*1+1*2+6*4+3*5 = 8685,29,练习.求下表给出的运输问题的初始基本可行解,(一) 初始方案的给定,30,5,10,0,15,10,10,(一) 初始方案的给定,31,5,10,0,15,10,10,(一) 初始方案的给定,判定是否 最 优？,求解思路图,表上作业法,1.最小元素法,2.沃格尔（Vogel）法,(一) 初始方案的给定,给定初始方案的方法很多(如前例)，一 般来说，希望方法简便易行，并能给出 较好的方案。减少迭代次数。这里介绍,最小元素法或Vogel法给出的是一个运输问题的基可行解，需要通过最优性检验判别该解得目标函数值是否最优，当为否时，应进行调整得到优化.,(二) 最优性检验与方案的调整,基本思想： 计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。,1.闭回路法,2.对偶变量法（位势法）,沿水平或垂直方向前，向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。,闭回路,表中闭回路的变量集合是x11,x12,x42,x 43,x 23,x 25, x 35,x 31共有8个顶点， 这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。,运输问题中的闭回路,有关闭回路的一些重要结果,定理3-设 是一个闭回路，则该闭回路中的变量所对应的系数列向量 具有下面的关系：,推论 若一组变量包含闭回路，则这组变量所对应的系数列向量线性相关。,推论 m+n-1个变量构成基变量的充要条件是该变量组不含闭回路。,判定是否 最 优？,求解思路图,表上作业法,1.最小元素法,2.沃格尔（Vogel）法,(一) 初始方案的给定,给定初始方案的方法很多(如前例)，一 般来说，希望方法简便易行，并能给出 较好的方案。减少迭代次数。这里介绍,最小元素法或Vogel法给出的是一个运输问题的基可行解，需要通过最优性检验判别该解得目标函数值是否最优，当为否时，应进行调整得到优化.,(二) 最优性检验与方案的调整,基本思想： 计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。,1.闭回路法,2.对偶变量法（位势法）,沿水平或垂直方向前，向左或右转90度（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的封闭折线叫做闭回路。,闭回路,表中闭回路的变量集合是x11,x12,x42,x 43,x 23,x 25, x 35,x 31共有8个顶点， 这8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。,运输问题中的闭回路,有关闭回路的一些重要结果,定理3-设 是一个闭回路，则该闭回路中的变量所对应的系数列向量 具有下面的关系：,推论 若一组变量包含闭回路，则这组变量所对应的系数列向量线性相关。,推论 m+n-1个变量构成基变量的充要条件是该变量组不含闭回路。,将如下表中6个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。,(A2 ,B1 ), (A3 ,B2)无法连入闭回路中,闭回路,孤立格是指在所在行或列中唯一出现的变量。 孤立格一定不会成为闭回路的顶点,最小元 素法得 初始方 案,以确定了初始调运方案的作业表为基础，以一个非基变量作为起始顶点，寻求闭回路。 该闭回路的特点是：除了起始顶点是非基变量（对应着空格）外，其他顶点均为基变量（对应着填有数字的格）。,对于每一个非基变量而言，以其为起点的闭回路存在且唯一。,运输问题中的闭回路,目 的：计算解中各非基变量(空格)的检验数 基本思路： 对于代表非基变量的空格（其调运量为零），把它的调运量调整为1（每次调整一个非基变量）； 由于产销平衡的要求我们必须对这个空格的闭回路的顶点的调运量加上或减少1 (可行条件)； 计算出由这些变化给整个运输方案的总运输费带来的变化，这里称之为检验数。,闭回路法求检验数,4.如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则进行方案调整（后续）,同理可以找出所有空格（即非基变量）的检验数。,+1,1,1,1,总运费变化,即此新可行解较原来解运费增加1元,闭回路法求检验数,闭回路法求检验数,2,3,20,6,5,6,3,销量,9,5,4,4,1,1,3,7,10,产量,销地 产地,6,4,3,3,-1,+1,-1,+1,-1,+1,总运费变化,7,约定作为起始顶点的非基变量为第一个奇数次顶点，相邻顶点为偶次顶点，其它顶点依次排列，那么，该非基变量xij的检验数：,闭回路法求检验数,当至少有一个非基变量的检验数是负值时， 说明作业表上当前的调运方案不是最优的， 应进行调整。,闭回路法求调整方案,选一个非基变量变为基变量进基 选一个基变量变为非基变量离基,反映在运输表上就是要选一个空格填上大于0的数,选择入基的原则是：,从绝对值最大的负检验数格(k,l)出发,闭回路法求调整方案,在作业表上以（A2 , B4）为起点作一条除该空格外其余顶点均为有数字格组成的闭回路,闭回路法求调整方案,+1,-1,=min3,1=1,离 基？,在作业表上以（A2 , B4）为起点作一条除该空格外其余顶点均为有数字格组成的闭回路,在这条闭回路上，在保持产销平衡的条件下对偶数顶点格子的运量做最大可能的调整,+1,-1,闭回路法求调整方案,（A2 , B4）为起点作一条出该空格外 其余顶点均为有数字各组成的闭回路,1,=min3,1=1,继续用闭回路检验 ， 直到检验数大于等于零,1.在作业表上从绝对值最大的负检验数格(k,l)出发,即xkl为起始变量作出闭回路。 2.以空格(k,l)为第一个奇数顶点，沿闭回路的顺（或逆）时针方向依次对顶点编号。 3.在闭回路上的所有偶数顶点中，找出运输量最小的格子，以该格对应的变量为离基变量。 4.调整量 5.将该闭回路上所有奇数顶点处的运输量都增加 所有偶数顶点处的运输量都减去,闭回路法求调整方案,位势法,在闭回路方法当中，要判断一个方案是否最优，需要通过每一个空格来寻找回路，以及根据闭回路求出每个空格的检验数，当一个运输问题的产地和销地很多时，用此方法工作量十分繁重.,位势法是根据对偶理论推导出来的一种求解检验数方法.运输方案的调整同前面的闭回路法.,56,位势法求检验数,原问题,对偶问题,57,记原问题基变量XB的下标集合为I，有如下式子成立：,解上面第一个方程，将ui、vj代入第二个方程求出检验数, 称ui(i=1,m),vj(j=1,n)分别成为第i行和第j列的位势,回忆：这里Pij 有如何特殊形式?,位势法求检验数,不妨令v1 =1，则,u2 =0; v3=2; u1=1; v4=9; u3=-4; v2=8.,注意：由于这些位势的数值是相互关联的，所以填写时可以先任意决定其中的一个，然后推导出其他位势的数值。,检验数表,1,2,1,-1,10,12,表 上 作 业 法,得到最优方案算出的总运价,分析实际问题 列出产销平衡表 及单位运价表,求检验数 （闭回路法或位势法）,确定初始调运方案 （最小元素法 或Vogel法）,找出绝对值最大的负的检验数用闭回路调整，得出新的调运方案,求 解 步 骤,运输问题的典例 运输问题的数学模型 求解方法表上作业法,第三章 运输问题,特殊的线性规划,产销不平衡运输问题,运输问题的典例 运输问题的数学模型 求解方法表上作业法,第三章 运输问题,特殊的线性规划,产销不平衡运输问题,产销不平衡运输问题,1产销,2销产,3.扩大的运输问题（中转站）,Min z= cij xij,n,i=1,j=1,m,Min z= cijxij+0xi,n+1,n,i=1,j=1,m,i=1,m,相当于：增加一个假想销地,产销问题,ai bj,产地,销地,A1 A2 Am,B1 B2 Bn,C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn,Bn+1, ,销量,产量,b1 b2 bn,a1 a2 am,aibj,相当于：增加一个假想销地,产销问题单位运价表,Min z= cij xij,n,i=1,j=1,m,Min z= cijxij +0xm+1,j,n,i=1,j=1,m,j=1,n,销产问题,相当于：增加一个假想产地,ai bj,产地,销地,A1 A2 Am,B1 B2 Bn,C11 C12 C1n C21 C22 C2n Cm1 Cm2 Cmn,Am+1,0 0 0,销量,产量,b1 b2 bn,a1 a2 am,bjai,销产问题单位运价表,相当于：增加一个假想产地,例一：某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂的生产能力及生产每台柴油机的成本如表示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需要存储维护费用0.15万元。要求在完成合同的情况下，做出使全年生产费用最小的决策。,季度,生产能力,(台),单位成本,(万元/台),25353010,10.811.111.011.3,运输问题案例1,数学模型：,设 xij第i季度生产，用于第j季度交货的数量。,目标函数： min z= cij xij,i=1j=1,4 4,x11+x12+x13+x1425,x22+x23+x2435,x33+x3430,x4410,x11 =10,x12+x22 =15,x13+x23+x33 =25,x14+x24+x34+x44=20,xij 0 ,(i=1,4;j=1,4),供应：,需求：,某工厂按合同规定必须于当年的每个季度末分别提供10、15、25、20台同一规格的柴油机。,合同要求,交货不得超过生产力,产销,数学模型：,每台每积压一个季度需要存储维护费用0.15万元。,当ij时，必须xij=0，令cij=M(很大的正数)，加以惩罚,产销,例二 有A、B、C三个化肥厂供应四个地区、的农用化肥，三个工厂每年各自的产量为A-50万吨，B-60万吨，C-50万吨。四个地区的需求量分别是地区最高50万吨，最低30万吨，地区为70万吨，地区为30万吨以下，地区不低于10万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。,设 xij-第i工厂调至第j需求地区的化肥数量,运输问题案例2,销产,上限50,运输问题案例2,设 xij-第i工厂调至第j需求地区的化肥数量,销产,扩大的运输问题,例：在前面的糖果例题中，若既可以从Ai运到Bj，也可以经过中间站T1、T2、T3、T4或者Ai、Bj转运，称扩大的运输问题。,几点说明： 1.所有的产地、销地、中间站均视作产地、销地； 2.所有中转站的转运量等于总的产量之和； 3.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为Cij=0； 4.实际产地产量为转运量与该产地实际产量之和，实际销地 销量为转运量与实际销量之和。,A1 A2 A3,T1 T2 T3 T4,B1 B2 B3 B4,A1 A2 A3,T1 T2 T3 T4,B1 B2 B3 B4,0 1 3 1 0 - 3 - 0,2 1 4 3 3 5 - 2 1 - 2 3,3 11 3 10 1 9 2 8 7 4 10 5,2 3 1 1 5 - 4 - 2 3 2 3,3 1 7 11 9 4 3 2 10 10 8 5,0 1 3 2 1 0 1 1 3 1 0 2 2 1 2 0,2 8 4 6 4 5 2 7 1 8 2 4 1 - 2 6,2 4 1 1 8 5 8 - 4 2 2 2 6 7 4 6,0 1 4 2 1 0 2 1 4 2 0 3 2 1 3 0,产,销,产量,销量,27 24 29,20 20 20 20,20 20 20 20,20 20 20,20 20 20 20,23 26 25 26,产销平衡表,某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要