运筹学运输问题管理.pptx

运输问题的典例运输问题的典例运输问题的数学模型运输问题的数学模型求解方法求解方法表上作业法表上作业法第三章第三章 运输问题运输问题特殊的线性规划第1页/共77页运输问题的典例运输问题的典例例例1.1.某食品公司经销的主要产品之一是糖果某食品公司经销的主要产品之一是糖果.它下面设有三个加工厂它下面设有三个加工厂,每天的糖果每天的糖果产量分别为产量分别为:A:A1 1-7t,A-7t,A2 2-4t,A-4t,A3 3-9t-9t.该公司把这些糖果分该公司把这些糖果分别运往四个地区的门市销售别运往四个地区的门市销售,各地区每天的各地区每天的销售量分别为：销售量分别为：B B1 1-3t,-3t,B B2 2-6t-6t，B B3 3-5t,B-5t,B3 3-6t-6t.已知从每个加工厂到各销售门市部每吨的运已知从每个加工厂到各销售门市部每吨的运价如表所示，价如表所示，问该食品公司应如何调运问该食品公司应如何调运,在满足各门市部销售需要在满足各门市部销售需要的情况下，使得总的运费支出为最少的情况下，使得总的运费支出为最少.8291A251047A3103113A1B4B3B2B1门市部门市部加工厂加工厂表表 3-1 单位：元单位：元/t第2页/共77页 运输问题的一般提法运输问题的一般提法 现有一批货物,从m个供应地运往n个销售地,Ai(i=1,m)处有货物ai吨，Bj(j=1,n)处需货物bj吨,已知从Ai到Bj的运价为cij 元/吨.问如何安排，既可以满足各销地需要，又使总费用最小？A1A2AmB1B2Bna1a2amb1b2bm供应量需求地供应地需求量调运量xij运输问题的框图表示第3页/共77页产销表运输问题的数学模型第4页/共77页单位运价表运输问题的数学模型运输问题的数学模型第5页/共77页运输表（运价，运量）运输表（运价，运量）作业表作业表销量销量销量销量产产产产量量量量 销地销地销地销地产地产地产地产地产销平衡产销平衡条件下条件下第6页/共77页设设xij为为 从从 产产 地地 A Ai运运 往往 销销 地地 B Bj的的 物物 资资 数数 量量(i=1,i=1,m;j=1,m;j=1,n n）从从Ai运出的物资总量运出的物资总量应等于应等于Ai的产量的产量ai，xij应满足：应满足：运到Bj的物资总量应该等于Bj的销量bj，xij还应满足：运输问题的数学模型运输问题的数学模型第7页/共77页总运费为：运输问题的数学模型运输问题的数学模型第8页/共77页运输问题的数学模型运输问题的数学模型第9页/共77页1.1.约束条件都是等式约束约束条件都是等式约束约束条件都是等式约束约束条件都是等式约束2.2.总产量总销量总产量总销量总产量总销量总产量总销量产销平衡的运输问题的特点与性质第10页/共77页3.3.系数矩阵是一个结构特殊的稀疏矩阵系数矩阵是一个结构特殊的稀疏矩阵系数矩阵是一个结构特殊的稀疏矩阵系数矩阵是一个结构特殊的稀疏矩阵将约束方程组展开约束方程组共包含mn个变量，(m+n)个约束条件产销平衡的运输问题的特点与性质第11页/共77页产销平衡的运输问题的特点与性质系数矩阵系数矩阵A：m行行n行行第12页/共77页 矩阵的元素均为1 1或0 0；每一列只有两个元素为1 1，其余元素均为0 0；v将矩阵分块,特点是:前m m行构成m m个mnmn阶矩阵,而且第k k个矩阵只有第k k行元素全为1,1,其余元素全为0 0（k=1,k=1,m,m）;后n n行构成m m个n n阶单位阵。vvA A的秩一般为的秩一般为m+n-1m+n-1 m行 n行为什么？第i行第m+j行 第13页/共77页运输问题的典例运输问题的典例运输问题的数学模型运输问题的数学模型求解方法求解方法表上作业法表上作业法第三章第三章 运输问题运输问题特殊的线性规划第14页/共77页运输问题的典例运输问题的典例运输问题的数学模型运输问题的数学模型求解方法求解方法表上作业法表上作业法第三章第三章 运输问题运输问题特殊的线性规划第15页/共77页表上作业法表上作业法作业表（产销平衡表）：将运输问题的有关信息表和决策变量调运量结合在一起构成“作业表”（产销平衡表）。表上作业法是单纯形法求解运输问题的一种简化方法，实质是单纯形法。但是具体计算和术语有所不同。销量销量销量销量产产产产量量量量 销地销地销地销地产地产地产地产地第16页/共77页运输问题中寻找可行解运输问题中寻找可行解10102 23 320206 65 56 63 3销量销量销量销量9 95 56 63 34 47 74 48 82 29 92 21 17 71 10 011114 43 3 3 3产量产量产量产量 销地销地销地销地产地产地产地产地填有数字的格:对应运输问题解中的基变量取值，这里为3+4-1=63+4-1=6个空格：对应解中非基变量第17页/共77页表上作业法的基本思想是:先设法给出一个初始方案(如典例所示),),然后根据确定的判别准则对初始方案进行检查、调整、改进，直至求出最优方案。表上作业法和单纯形法的求解思想完全一致，但是具体作法更加简捷。表上作业法表上作业法第18页/共77页 确定初始确定初始方案方案(初始基可行解初始基可行解)改进调整改进调整（换基迭代）（换基迭代）否否 判定是否判定是否 最最 优？优？是是结结 束束最优方案最优方案求解思路图表上作业法表上作业法第19页/共77页1.1.最小元素法最小元素法最小元素法最小元素法2.2.沃格尔（沃格尔（沃格尔（沃格尔（VogelVogel）法）法）法）法(一)初始方案的给定给定初始方案的方法很多(如前例)，一般来说，希望方法简便易行，并能给出较好的方案。减少迭代次数。这里介绍第20页/共77页1.1.最小元素法最小元素法最小元素法最小元素法基本思想：基本思想：基本思想：基本思想：就近供应就近供应，即即优先考虑单位运价最小（或优先考虑单位运价最小（或优先考虑单位运价最小（或优先考虑单位运价最小（或运距最短）的供销业务，最大限度地满足其供销量。运距最短）的供销业务，最大限度地满足其供销量。运距最短）的供销业务，最大限度地满足其供销量。运距最短）的供销业务，最大限度地满足其供销量。销地销地销地销地产地产地产地产地产量产量产量产量3 311113 3101071 19 92 28 847 74 410105 59销量销量销量销量3656203 33 33 31 11 11 14 44 4-6 66 66 64 43 33 33 33 3-3-3第21页/共77页 销地销地销地销地产地产地产地产地产量产量产量产量3 311113 3101071 19 92 28 847 74 410105 59销量销量销量销量3656203 31 16 64 43 33 3Z=4*3+3*10+3*1+1*2+6*4+3*5=86Z=4*3+3*10+3*1+1*2+6*4+3*5=86第22页/共77页最小元素法的说明退化现象退化现象：部分产量和部分销量和在迭代在迭代过程中过程中，可能出现一行和一列，可能出现一行和一列同时被划去同时被划去。第23页/共77页 销地销地销地销地产地产地产地产地产量产量产量产量3 311114 45 577 77 73 38 841 12 210106 69销量销量销量销量3656203 34 44 44 41 11 1-6 66 66 61 16 63 33 36 6-60为使迭代过程中基变量的个数恰好为(m+n-1)(m+n-1)个，应在同时划去的一行或一列中的某个格中填入数字0 0，表示这个格中的变量是取值为0 0的基变量。以便当做有数字的格看待。第24页/共77页 销地销地销地销地产地产地产地产地产量产量产量产量3 311114 45 577 77 73 38 841 12 210106 69销量销量销量销量3656203 34 46 61 16 60第25页/共77页基本思想：基本思想：基本思想：基本思想：优选考虑优选考虑最大差额（最小运价优势）最大差额（最小运价优势）方案方案行（列）差额（行（列）差额（行（列）差额（行（列）差额（罚数罚数）=次小次小运价系数运价系数-最小最小运价系数运价系数2 2.沃格尔（沃格尔（沃格尔（沃格尔（VogelVogelVogelVogel）法）法）法）法(差额法差额法差额法差额法)行行行行 罚罚罚罚 数数数数列列列列罚罚罚罚数数数数10102 23 320206 65 56 63 3销量销量销量销量9 95 54 47 74 48 89 91 17 7101011113 3产量产量 销地销地产地产地0112513()6220 0 71312121 1 62()33()521108()第26页/共77页10102 23 320206 65 56 63 3销量销量销量销量9 95 54 47 74 48 89 91 17 7101011113 3产量产量 销地销地产地产地633521一般当产销地数量不多时，(Vogel)法给出的初始方案有时就是最优方案。沃格尔法沃格尔法Z=5*3+2*10+3*1+1*8+6*4+3*5=85Z=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=8685Z=4*3+3*10+3*1+1*2+6*4+3*5=8685第27页/共77页28练习.求下表给出的运输问题的初始基本可行解 B1B2B3B4产量产量A14104420A2773815A31210615销量销量510251050(一)初始方案的给定第28页/共77页29 销地销地产地产地B1B2B3B4aiA14104420A2773815A31210615销量销量5102510505100151010(一)初始方案的给定第29页/共77页30 BjAiB1B2B3B4aiA14104420A2773815A31210615bj5102510505100151010(一)初始方案的给定第30页/共77页 确定初始确定初始方案方案(初始基可行解初始基可行解)改进调整改进调整（换基迭代）（换基迭代）否否 判定是否判定是否 最最 优？优？是是结结 束束最优方案最优方案求解思路图表上作业法表上作业法第31页/共77页1.1.最小元素法最小元素法最小元素法最小元素法2.2.沃格尔（沃格尔（沃格尔（沃格尔（VogelVogel）法）法）法）法(一)初始方案的给定给定初始方案的方法很多(如前例)，一般来说，希望方法简便易行，并能给出较好的方案。减少迭代次数。这里介绍第32页/共77页 最小元素法或VogelVogel法给出的是一个运输问题的基可行解，需要通过最优性检验判别该解得目标函数值是否最优，当为否时，应进行调整得到优化.(二)最优性检验与方案的调整基本思想：计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。1.闭回路法闭回路法2 2.对偶变量法（对偶变量法（位势法位势法）第33页/共77页 沿沿水平或垂直水平或垂直方向前，方向前，向左或右转向左或右转9090度度（当然也可以不改变方向）继续前进，（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的这样继续下去，直至回到出发的那个空格，由此形成的封闭折线封闭折线叫做闭回路。叫做闭回路。闭回路第34页/共77页x25x23B1B2B3B4B5A1A2A3x35A4 x43x11x12x31x42表中闭回路的变量集合是 x x1111,x x1212,x x4242,x x 43 43,x x 23 23,x x 2525,x x 35 35,x x 31 31 共有8 8个顶点，这8 8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。运输问题中的闭回路第35页/共77页有关闭回路的一些重要结果有关闭回路的一些重要结果有关闭回路的一些重要结果有关闭回路的一些重要结果定定理理3-设设 是是一一个个闭闭回回路路，则则该该闭闭回回路路中中的的变变量量所所对对应应的的系系数数列列向向量量 具具有有下下面面的关系：的关系：推推推推论论论论 若若若若一一一一组组组组变变变变量量量量包包包包含含含含闭闭闭闭回回回回路路路路，则则则则这这这这组组组组变变变变量量量量所所所所对对对对应应应应的系数列向量的系数列向量的系数列向量的系数列向量线性相关线性相关线性相关线性相关。推推推推论论论论 m+n-1个个变变量量构构成成基基变变量量的的充充要要条条件件是是该该变变量组量组不含闭回路不含闭回路。第36页/共77页 确定初始确定初始方案方案(初始基可行解初始基可行解)改进调整改进调整（换基迭代）（换基迭代）否否 判定是否判定是否 最最 优？优？是是结结 束束最优方案最优方案求解思路图表上作业法表上作业法第37页/共77页1.1.最小元素法最小元素法最小元素法最小元素法2.2.沃格尔（沃格尔（沃格尔（沃格尔（VogelVogel）法）法）法）法(一)初始方案的给定给定初始方案的方法很多(如前例)，一般来说，希望方法简便易行，并能给出较好的方案。减少迭代次数。这里介绍第38页/共77页 最小元素法或VogelVogel法给出的是一个运输问题的基可行解，需要通过最优性检验判别该解得目标函数值是否最优，当为否时，应进行调整得到优化.(二)最优性检验与方案的调整基本思想：计算非基变量（未填上数值的格，即空格）的检验数（也称为空格的检验数），若全部大于等于零，则该方案就是最优调运方案，否则就应进行调整。1.闭回路法闭回路法2 2.对偶变量法（对偶变量法（位势法位势法）第39页/共77页 沿沿水平或垂直水平或垂直方向前，方向前，向左或右转向左或右转9090度度（当然也可以不改变方向）继续前进，（当然也可以不改变方向）继续前进，这样继续下去，直至回到出发的那个空格，由此形成的这样继续下去，直至回到出发的那个空格，由此形成的封闭折线封闭折线叫做闭回路。叫做闭回路。闭回路第40页/共77页x25x23B1B2B3B4B5A1A2A3x35A4 x43x11x12x31x42表中闭回路的变量集合是 x x1111,x x1212,x x4242,x x 43 43,x x 23 23,x x 2525,x x 35 35,x x 31 31 共有8 8个顶点，这8 8个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。运输问题中的闭回路第41页/共77页有关闭回路的一些重要结果有关闭回路的一些重要结果有关闭回路的一些重要结果有关闭回路的一些重要结果定定理理3-设设 是是一一个个闭闭回回路路，则则该该闭闭回回路路中中的的变变量量所所对对应应的的系系数数列列向向量量 具具有有下下面面的关系：的关系：推推推推论论论论 若若若若一一一一组组组组变变变变量量量量包包包包含含含含闭闭闭闭回回回回路路路路，则则则则这这这这组组组组变变变变量量量量所所所所对对对对应应应应的系数列向量的系数列向量的系数列向量的系数列向量线性相关线性相关线性相关线性相关。推推推推论论论论 m+n-1个个变变量量构构成成基基变变量量的的充充要要条条件件是是该该变变量组量组不含闭回路不含闭回路。第42页/共77页 将如下表中6 6个顶点间用水平或垂直线段连接起来，组成一条封闭的回路。10102 23 320206 65 56 63 3销量销量9 95 53 34 46 67 74 48 81 19 91 13 37 710103 34 411113 3产产量量 销地销地产地产地(A2,B1),(A3,B2)无法连入闭回路中无法连入闭回路中闭回路孤 立 格 是 指 在 所 在 行 或 列 中 唯 一 出 现 的 变 量。孤立格一定不会成为闭回路的顶点最小元素法得初始方案第43页/共77页 以以确确定定了了初初始始调调运运方方案案的的作作业业表表为为基基础础，以以一一个个非非基基变变量量作作为起始顶点为起始顶点，寻求，寻求闭回路闭回路。该该闭闭回回路路的的特特点点是是：除除了了起起始始顶顶点点是是非非基基变变量量（对对应应着着空空格格）外，其他顶点均为基变量（对应着）外，其他顶点均为基变量（对应着填有数字的格填有数字的格）。）。对于每一个非基变量而言，以其为起点的对于每一个非基变量而言，以其为起点的闭回路存在且唯一。闭回路存在且唯一。运输问题中的闭回路第44页/共77页目目 的：的：计算解中各非基变量计算解中各非基变量(空格空格)的检验数的检验数基本思路：基本思路：1.1.对于代表对于代表非基变量非基变量的空格（其调运量为零），把它的空格（其调运量为零），把它的的调运量调整为调运量调整为1 1（每次调整一个非基变量每次调整一个非基变量）；2.2.由于产销平衡的要求我们必须对这个空格的闭回路由于产销平衡的要求我们必须对这个空格的闭回路的的顶点的调运量加上或减少顶点的调运量加上或减少1 1(可行条件可行条件)；3.3.计算出由这些变化给整个运输方案的总运输费带来计算出由这些变化给整个运输方案的总运输费带来的变化，这里称之为的变化，这里称之为检验数检验数。闭回路法求检验数闭回路法求检验数4.4.如果所有代表非基变量的空格的检验数也即非基变量的检验数都大于等于零，则已求得最优解，否则进行方案调整（后续）第45页/共77页2 23 320206 65 56 63 3销量销量销量销量9 95 54 44 4 1 11 1 3 37 71 10 0 产量产量产量产量 销销销销地地地地产地产地产地产地 6 6 4 4 3 3 3 33 3同理可以找出所有空格（即非基变量）的检验数。+1+11 11 11 1总运费变化总运费变化即此新可行解较原来解运费增加1元闭回路法求检验数闭回路法求检验数第46页/共77页闭回路法求检验数2 23 320206 65 56 63 3销量销量销量销量9 95 54 44 4 1 11 1 3 37 71 10 0 产量产量产量产量 销销销销地地地地产地产地产地产地 6 6 4 4 3 3 3 3-1 1+1+1-1 1+1+1-1 1+1 1总运费变化总运费变化总运费变化总运费变化7 7 约定作作为为起起始始顶顶点点的的非非基基变变量量为为第第一一个个奇数次顶点，相相邻邻顶顶点点为为偶偶次次顶顶点点，其其它它顶顶点点依依次次排排列列，那那么么，该该非非基基变变量量x x x xijijijij的检验数：的检验数：=（闭回路上（闭回路上（闭回路上（闭回路上奇数次顶点奇数次顶点奇数次顶点奇数次顶点运价之和）运价之和）运价之和）运价之和）（闭回路上（闭回路上（闭回路上（闭回路上偶数次顶点偶数次顶点偶数次顶点偶数次顶点运价之和）运价之和）运价之和）运价之和）第47页/共77页-11A21210A321A1B4B3B2B1销地销地产地产地检验数表检验数表闭回路法求检验数闭回路法求检验数 当至少有一个当至少有一个非基变量的检验数非基变量的检验数是是负值负值时，时，说明作业表上当前的调运方案不是最优的，说明作业表上当前的调运方案不是最优的，应进行调整。应进行调整。第48页/共77页闭回路法求调整方案选一个非基变量变为基变量进基选一个基变量变为非基变量离基反映在运输表上就是要选一个空格填上大于0 0的数选择选择选择选择入基入基入基入基的原则是：的原则是：的原则是：的原则是：从绝对值最大的负检验数格(k,l)出发第49页/共77页闭回路法求调整方案-11A21210A321A1B4B3B2B1销地销地产地产地检验数表检验数表在作业表上以（A A2 2,B,B4 4）为起点作一条除该空格外其余顶点均为有数字格组成的闭回路第50页/共77页闭回路法求调整方案206563销量销量销量销量94 1 374 产量产量产量产量 销地销地销地销地产地产地产地产地 6 33 调运方案（最小元素法得到）+1-1=min3,1=1离 基？在作业表上以（A A2 2,B,B4 4）为起点作一条除该空格外其余顶点均为有数字格组成的闭回路 在这条闭回路上，在保持产销平衡的条件下对偶数顶点格子的运量做最大可能的调整+1-1第51页/共77页闭回路法求调整方案（A A2 2,B,B4 4）为起点作一条出该空格外其余顶点均为有数字各组成的闭回路206563销量销量销量销量94 375 产量产量产量产量 销地销地销地销地产地产地产地产地 6 32 调运方案（最小元素法得到）1=min3,1=1继续用闭回路检验，直到检验数大于等于零第52页/共77页1.1.1.1.在作业表上从绝对值最大的负检验数格(k,l)出发,即x xklkl为起始变量作出闭回路。2.2.以空格(k,l)(k,l)为第一个奇数顶点，沿闭回路的顺（或逆）时针方向依次对顶点编号。3.3.在闭回路上的所有偶数顶点中，找出运输量最小的格子，以该格对应的变量为离基变量。4.4.调整量5.5.将该闭回路上所有奇数顶点处的运输量都增加 所有偶数顶点处的运输量都减去ij =minmin该该该该闭闭闭闭回回回回路路路路中中中中偶偶偶偶数数数数次次次次顶顶顶顶点点点点运运运运输输输输量量量量x xij ij 闭回路法求调整方案第53页/共77页位势法位势法 在闭回路方法当中，要判断一个方案是否在闭回路方法当中，要判断一个方案是否最优，需要通过每一个空格来寻找回路，以及最优，需要通过每一个空格来寻找回路，以及根据闭回路求出每个空格的检验数，当一个运根据闭回路求出每个空格的检验数，当一个运输问题的产地和销地很多时，用此方法工作量输问题的产地和销地很多时，用此方法工作量十分繁重十分繁重.位势法是根据对偶理论推导出来的一种求解检验数方法.运输方案的调整同前面的闭回路法.第54页/共77页55位势法求检验数原问题对偶问题第55页/共77页56记原问题基变量X XB B的下标集合为I I，有如下式子成立：解上面第一个方程，将解上面第一个方程，将u ui i、v vj j代入第二个方程代入第二个方程求出检验数求出检验数,称称u ui i(i=1,(i=1,m),m),v vj j(j=1,(j=1,n),n)分别成为第分别成为第i i行和第行和第j j列的列的位势位势回忆：这里Pij 有如何特殊形式?位势法求检验数第56页/共77页uiu1u2u3v vj jv v1 1v v2 2v v3 3v v4 4不妨令不妨令不妨令不妨令v v1 1=1=1，则则则则u u2 2=0;v=0;v3 3=2;=2;u u1 1=1;=1;v v4 4=9;u=9;u3 3=-4;v4;v2 2=8.=8.(1)(1)(0)(0)(-4)4)(1)(1)(8)(8)(2)(2)(9)(9)102320206 65 56 63 3销量销量销量销量9 9534674 4819137 71034113产量产量 销地销地产地产地注意：由于这些位势的数值是相互关联的，所以填写时可以先任意决定其中的一个，然后推导出其他位势的数值。第57页/共77页A2A3A1B4B3B2B1销地销地产地产地检检验验数数表表121-11012uiu1u2u3v vj jv v1 1v v2 2v v3 3v v4 4(1)(1)(0)(0)(-4)4)(1)(1)(8)(8)(2)(2)(9)(9)102320206 65 56 63 3销量销量销量销量9 9534674 4819137 71034113产量产量 销地销地产地产地第58页/共77页表表上上作作业业法法得到最优方案得到最优方案算出的总运价算出的总运价分析实际问题分析实际问题列出产销平衡表列出产销平衡表及单位运价表及单位运价表求检验数求检验数（闭回路法或位势法闭回路法或位势法）是是确定初始调运方案确定初始调运方案（最小元素法最小元素法或或Vogel法法）找出绝对值最大的负找出绝对值最大的负的检验数用的检验数用闭回路闭回路调整，调整，得出新的调运方案得出新的调运方案否否循循环环所有检验数所有检验数0 0求解步骤第59页/共77页运输问题的典例运输问题的典例运输问题的数学模型运输问题的数学模型求解方法求解方法表上作业法表上作业法第三章第三章 运输问题运输问题特殊的线性规划 产销不平衡运输问题产销不平衡运输问题第60页/共77页运输问题的典例运输问题的典例运输问题的数学模型运输问题的数学模型求解方法求解方法表上作业法表上作业法第三章第三章 运输问题运输问题特殊的线性规划 产销不平衡运输问题产销不平衡运输问题第61页/共77页产销不平衡运输问题产销不平衡运输问题1 1 产 销2 2 销 产3.3.扩大的运输问题（中转站）第62页/共77页Min z=cij xijni=1j=1mMin z=cijxij+0 0 x xi i,n+1n+1ni=1 j=1mi=1i=1m m相当于：增加一个假想销地产 销问题 a ai i b bj j第63页/共77页产地销地A1 A2 AmB1B2BnC11C12C1n C21C22C2n Cm1Cm2CmnBn+1 销量产量b1b2bna1 a2 amaibj相当于：增加一个假想销地产 销问题单位运价表第64页/共77页Min z=cij xijni=1j=1mMin z=cijxij+0 0 x xm+1m+1,j jni=1 j=1mj=1j=1n n销 产问题相当于：增加一个假想产地 a ai i 销第68页/共77页数学模型：数学模型：季季度度生产能力生产能力(台台)单位成本单位成本(万元万元/台台)252535353030101010.810.811.111.111.011.011.311.3 每台每积压一个季度需要存储维护费用0.15万元。单位运价表：销量 D 产量10.810.95 11.10 11.25 0 25 M 11.10 11.25 11.40 0 35 MM11.00 11.15 0 30单位：万元供应需求10 15 2520 30MM M11.30 0 10当ij时，必须xij=0，令cij=M(很大的正数)，加以惩罚产销第69页/共77页 例二 有A A、B B、C C三个化肥厂供应四个地区、的农用化肥，三个工厂每年各自的产量为A-50A-50万吨，B-B-60-60万吨，C-50C-50万吨。四个地区的需求量分别是地区最高5050万吨，最低3030万吨，地区为7070万吨，地区为3030万吨以下，地区不低于1010万吨。问：如何调运，可使总的调运费用最小？单位调运费用如下表所示。产地销地A1A1A2A2A3A3B1 B2 B3 B4B1 B2 B3 B4 产量销量16 13 22 17 16 13 22 17 14 13 19 15 14 13 19 15 19 20 23 19 20 23 单位运价表50 50 60 60 505030-50 70 0-30 10-30-50 70 0-30 10-单位：万元/万吨设 x xijij-第i i工厂调至第j j需求地区的化肥数量运输问题案例2 2销 产上限50第70页/共77页运输问题案例2 2A B C D 161613221717 14141319151519192023 M MM0M0M0供应需求产量销 量50 50 60 60 50 50 5050 303020207070303010105050修正运价表产地销地A1A1A2A2A3A3B1 B2 B3 B4B1 B2 B3 B4 产量销量16 13 22 17 16 13 22 17 14 13 19 15 14 13 19 15 19 20 23 19 20 23 单位运价表50 50 60 60 505030-50 70 0-30 10-30-50 70 0-30 10-单位：万元/万吨设 x xijij-第i i工厂调至第j j需求地区的化肥数量销 产第71页/共77页扩大的运输问题扩大的运输问题例：在前面的糖果例题中，若既可以从AiAi运到BjBj，也可以经过中间站T1T1、T2T2、T3T3、T4T4或者AiAi、BjBj转运，称扩大的运输问题。几点说明：1.1.所有的产地、销地、中间站均视作产地、销地；2.2.所有中转站的转运量等于总的产量之和；3.3.不能出现循环倒运现象，允许自身往自身最多调运一次，运价为C Cijij=0=0；4.4.实际产地产量为转运量与该产地实际产量之和，实际销地 销量为转运量与实际销量之和。第72页/共77页A1 A2 A3A1 A2 A3T1 T2 T3 T4T1 T2 T3 T4B1 B2 B3 B4B1 B2 B3 B4A1 A1 A2 A2 A3A3T1 T1 T2 T2 T3 T3 T4T4B1 B1 B2 B2 B3 B3 B4B40 1 3 0 1 3 1 0 -1 0 -3 -03 -02 1 4 3 2 1 4 3 3 5 -2 3 5 -2 1 -2 31 -2 33 11 3 10 3 11 3 10 1 9 2 8 1 9 2 8 7 4 10 57 4 10 52 3 1 2 3 1 1 5 -1 5 -4 -2 4 -2 3 2 33 2 33 1 7 3 1 7 11 9 4 11 9 4 3 2 10 3 2 10 10 8 510 8 50 1 3 2 0 1 3 2 1 0 1 1 1 0 1 1 3 1 0 2 3 1 0 2 2 1 2 0 2 1 2 0 2 8 4 6 2 8 4 6 4 5 2 7 4 5 2 7 1 8 2 4 1 8 2 4 1 -2 6 1 -2 6 2 4 1 1 2 4 1 1 8 5 8 -8 5 8 -4 2 2 2 4 2 2 2 6 7 4 66 7 4 60 1 4 2 0 1 4 2 1 0 2 1 1 0 2 1 4 2 0 3 4 2 0 3 2 1 3 02 1 3 0产产销销产量产量销量销量27 27 24 24 292920 20 20 20 20 20 202020 20 20 20 20 20 202020 20 2020 20 2020 20 20 2020 20 20 2023 26 25 2623 26 25 26产销平衡表产销平衡表第73页/共77页 某餐馆承办宴会，每晚连续举行，共举行五次。宴会上需用特殊的餐巾，根据参加的人数，预计每晚的需要量为：第一天10001000条，第二天700700条，第三天800800条，第四天12001200条，第五天15001500条，五天之后，所有的餐巾作废。宴会中用过的餐巾经过洗涤处理后可以重复使用，这样可以降低使用成本。已知每条新餐巾需要1 1元的费用，送洗时可选择两种方式：快洗仅需要一天时间，每条洗涤费用为0.20.2元，慢洗需要两天时间，每条洗涤费用0.10.1元。问：如何安排，可使总费用最低？运输问题案例3 3第74页/共77页设x xj j第j j天使用新毛巾的数量；y yijij第i i天送第j j天使用快洗餐巾的数量；z zijij第i i天送第j j天使用慢洗餐巾的数量；第一天：第一天：x x1 1=1000=1000第二天：第二天：x x2 2+y+y1212=700=700第三天：第三天：x x3 3+z+z1313+y+y2323=800=800第四天：第四天：x x4 4+z+z1414+z+z2424+y+y3434=1200=1200第五天：第五天：x x5 5+z+z1515+z+z2525+z+z3535+y+y4545=1500=1500需需求求约约束束供供应应约约束束新购餐巾：新购餐巾：x x1 1+x+x2 2+x+x3 3+x+x4 4+x+x5 5 52005200第一天送洗：第一天送洗：y y1212+z+z1313+z+z1414+z+z1515 10001000第二天送洗：第二天送洗：y y2323+z+z2424+z+z2525 700700第三天送洗：第三天送洗：y y3434+z+z3535 800800第四天送洗：第四天送洗：y y4545 12001200 x xj j 0 0，y yijij 0 0，z zijij 0 0，（，（i=1,4i=1,4；j=1,5j=1,5）Min z=Min z=x xj j+0.2y0.2yijij+0.1z0.1zijij数学模型：第75页/共77页新新 购购 第一天第一天第二天第二天第三天第三天第四天第四天111110 M0.20.10.10.10MM0.20.10.10MMM0.20.10供应需求产量销 量5200 5200 1000 1000 700 700 800 800 12001200MMM0.20.1010001000700700800800120012001500150037003700单位费用表第一天：第一天：x x1 1=1000=1000第二天：第二天：x x2 2+y+y1212=700=700第三天：第三天：x x3 3+z+z1313+y+y2323=800=800第四天：第四天：x x4 4+z+z1414+z+z2424+y+y3434=1200=1200第五天：第五天：x x5 5+z+z1515+z+z2525+z+z3535+y+y4545=1500=1500需需求求约约束束供供应应约约束束新购餐巾：新购餐巾：x x1 1+x+x2 2+x+x3 3+x+x4 4+x+x5 5 52005200第一天送洗：第一天送洗：y y1212+z+z1313+z+z1414+z+z1515 10001000第二天送洗：第二天送洗：y y2323+z+z2424+z+z2525 700700第三天送洗：第三天送洗：y y3434+z+z3535 800800第四天送洗：第四天送洗：y y4545 12001200 x xj j 0 0，y yijij 0 0，z zijij 0 0，（，（i=1,4i=1,4；j=1,5j=1,5）Min z=Min z=x xj j+0.2y0.2yijij+0.1z0.1zijij第76页/共77页感谢您的观看！第77页/共77页