《运筹学课件ch3运输问题.ppt》由会员分享，可在线阅读，更多相关《运筹学课件ch3运输问题.ppt（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、pp运输问题的表示pp网络图、线性规划模型、运输表pp初始基础可行解pp西北角法、最小元素法pp非基变量的检验数pp闭回路法、位势法pp确定进基变量，调整运量，确定离基变量第三章第三章 运输问题运输问题TransportationProblem12/27/202212/27/2022运筹学课件运筹学课件一.运输问题的一般提法人们在从事生产活动中，不可避免地要进行物资调运工作。如人们在从事生产活动中，不可避免地要进行物资调运工作。如某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到某时期内将生产基地的煤、钢铁、粮食等各类物资，分别运到需要这些物资的地区，根据各地的需要这些物资的地区，根据各地
2、的生产量生产量和和需要量需要量及各地之间及各地之间的的运输费用运输费用，如何制定一个运输方案，使总的运输费用最小。，如何制定一个运输方案，使总的运输费用最小。这样的问题称为这样的问题称为运输问题运输问题。12/27/202212/27/2022运筹学课件运筹学课件n n典型典型范范例例 各工各工厂应厂应分別分別运运送多少送多少数数量至各配量至各配送送中心，才能中心，才能使使总总的的运输成本运输成本最低？最低？n n供供给及需求单位给及需求单位：1 1卡车的量卡车的量n n单位运输成本单位运输成本：千元：千元工厂配送中心供给W1W2W3W4P1675314P2842727P35910619需求2
3、21312136060运价表运价表12/27/202212/27/2022运筹学课件运筹学课件2321341运输问题网络图运输问题网络图s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地675384275910612/27/202212/27/2022运筹学课件运筹学课件运输问题线性规划模型运输问题线性规划模型供应地约束需求地约束设设xij(i=1,2,3；j=1,2,3,4)为为i个工厂运往第个工厂运往第j个配送中心的运量，个配送中心的运量，这样得到下列运输问题的数学模型：这样得到下列运输问题的数学模型：12/27/202212/27/2022
4、运筹学课件运筹学课件运输问题的表格表示运输问题的表格表示12/27/202212/27/2022运筹学课件运筹学课件运输问题的一般提法是：运输问题的一般提法是：1.1.产销平衡问题产销平衡问题产销平衡问题产销平衡问题已知：已知：m个产地（记作个产地（记作A1，A2，A3,Am），其产量分别为），其产量分别为a1,a2，am；n个销地（记作个销地（记作B1，B2，Bn），），其需要量分别为其需要量分别为b1,b2，bn；且产销平衡，即且产销平衡，即。从第从第i个产地到个产地到j 个销地的单位运价为个销地的单位运价为cij，问：在满足各地需要的前提下，求总运输费用最小的调运方问：在满足各地需要的前
5、提下，求总运输费用最小的调运方案。案。即即AiBj的运量的运量xij使使12/27/202212/27/2022运筹学课件运筹学课件2.2.产销不平衡问题产销不平衡问题此时分为两种情形来考虑：此时分为两种情形来考虑：供不应求：即产量小于销量时有：即产量小于销量时有 供过于求供过于求：即产量大于销量时有即产量大于销量时有 12/27/202212/27/2022运筹学课件运筹学课件二二.运输问题的模型运输问题的模型产销平衡问题模型12/27/202212/27/2022运筹学课件运筹学课件将约束方程式展开可得将约束方程式展开可得约束方程式中共mn个变量，m+n个约束。12/27/202212/2
6、7/2022运筹学课件运筹学课件上述模型是一个线性规划问题。但是其结构很特殊，特点如下：1.变量多（mn个），但结构简单。技术系数矩阵12/27/202212/27/2022运筹学课件运筹学课件系数矩阵的特点:(1)约束条件的系数矩阵的元素只有两个:0,1.(2)元素 xij 对应于每一个变量在前m个约束方程中(第i个方程中)出现一次,在后n个约束方程中(第m+j 个方程中)也出现一次.(3)产销平衡问题为等式约束.(4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等.12/27/202212/27/2022运筹学课件运筹学课件2.m+n个约束中有一个是多余的（因为其间含个约束中有一个
7、是多余的（因为其间含有一个平衡关系式有一个平衡关系式）所以所以R(A)=m+n-1，即解的即解的mn个变量中基变量个变量中基变量为为m+n-1个。个。3.m+n1个变量组构成基变量的充要条件是它不个变量组构成基变量的充要条件是它不包含任何闭回路。包含任何闭回路。一条回路中的顶点数一定是偶数。一条回路中的顶点数一定是偶数。12/27/202212/27/2022运筹学课件运筹学课件【证证】因因为为产产销销平平衡衡，即即，将将前前m个个约约束束方方程程两两边边相相加得加得再将后再将后n个约束相加得个约束相加得显显然然前前m个个约约束束方方程程之之和和等等于于后后n个个约约束束方方程程之之和和，m+
8、n个个约约束束方方程是相关的，系数矩阵程是相关的，系数矩阵【定理定理1】设有设有m个产地个产地n个销地且产销平衡的运输问题，则基变个销地且产销平衡的运输问题，则基变量数为量数为m+n-1。12/27/202212/27/2022运筹学课件运筹学课件中任意中任意m+n阶子式等于零，取第一行到阶子式等于零，取第一行到m+n1行与行与对应的列（共对应的列（共m+n-1列）组成的列）组成的m+n1阶子式阶子式m 行行n 行行12/27/202212/27/2022运筹学课件运筹学课件故故r(A)=m+n1所以运输问题有所以运输问题有m+n1个基变量。个基变量。为为了了在在mn个个变变量量中中找找出出m
9、+n1个个变变量量作作为为一一组组基基变变量量，就就是是要要在在A中中找找出出m+n-1个个线线性性无无关关的的列列向向量量，通通常常引引用用闭闭回回路路的的概概念寻找这些基变量。念寻找这些基变量。12/27/202212/27/2022运筹学课件运筹学课件三三.运输问题的解法运输问题的解法 运输问题仍然是线性规划问题，可以用线性规划法中的单纯形法来解决。但是：1.运输问题所涉及的变量多，造成单纯 形表太大；2.若把技术系数矩阵A中的0迭代成非0，会使问题更加复杂。以上两个原因使得我们不得不利用运输问题的特点设计出它的特殊解法表上作业法。12/27/202212/27/2022运筹学课件运筹学
10、课件运运输输单单纯纯形形法法也也称称为为表表上上作作业业法法，是是直直接接在在运运价价表表上上求求最最优优解解的的一种方法，它的步骤是：一种方法，它的步骤是：第第一一步步：求求初初始始基基行行可可行行解解（初初始始调调运运方方案案）。常常用用的的方方法法有有最小元素法、元素差额法（最小元素法、元素差额法（Vogel近似法）、左上角法。近似法）、左上角法。第第二二步步：求求检检验验数数并并判判断断是是否否得得到到最最优优解解。常常用用求求检检验验的的方方法法有有闭闭回回路路法法和和位位势势法法，当当非非基基变变量量的的检检验验数数ij全全都都非非负负时时得得到到最最优解，若存在检验数优解，若存在
11、检验数lk0，说明还没有达到最优，转第三步。说明还没有达到最优，转第三步。第第三三步步：调调整整运运量量，即即换换基基。选选一一个个变变量量出出基基，对对原原运运量量进进行行调整得到新的基可行解，转入第二步。调整得到新的基可行解，转入第二步。表表上上作作业业法法12/27/202212/27/2022运筹学课件运筹学课件左上角法左上角法(亦称西北角法亦称西北角法)是优先从运价表的左上角的变量赋值，当行或列分是优先从运价表的左上角的变量赋值，当行或列分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕后，再在表中余下部分的左上角赋值，依次类推，直到右下角元素分配完毕当出现同
12、时分配完一行和一列时，仍然应在打配完毕当出现同时分配完一行和一列时，仍然应在打“”的位置上选一的位置上选一个变量作基变量，以保证最后的基变量数等于个变量作基变量，以保证最后的基变量数等于m+n1初始基础可行解初始基础可行解西北角法西北角法81313146612/27/202212/27/2022运筹学课件运筹学课件最小元素法的思想是优先满足单位运价最小的业务，即最最小元素法的思想是优先满足单位运价最小的业务，即最小运价小运价Cij 对应的变量对应的变量xij优先赋值，优先赋值，然后再在剩下的运价中取最小运价对应的变量赋值并满足然后再在剩下的运价中取最小运价对应的变量赋值并满足约束，依次下去，直
13、到最后得到一个初始基可行解。约束，依次下去，直到最后得到一个初始基可行解。初始基础可行解最小元素法12/27/202212/27/2022运筹学课件运筹学课件初始基础可行解最小元素法（1）12/27/202212/27/2022运筹学课件运筹学课件最小元素法（2）12/27/202212/27/2022运筹学课件运筹学课件最小元素法（3）12/27/202212/27/2022运筹学课件运筹学课件最小元素法（4）12/27/202212/27/2022运筹学课件运筹学课件最小元素法（5）12/27/202212/27/2022运筹学课件运筹学课件最小元素法（6）12/27/202212/27/
14、2022运筹学课件运筹学课件初始基础可行解元素差额法（Vogel近似法）求初始基本可行解的步骤是：求初始基本可行解的步骤是：第第一一步步：求求出出每每行行次次小小运运价价与与最最小小运运价价之之差差，记记为为ui，i=1,2,m；同同时时求求出出每每列列次次小小运运价价与与最最小小运运价价之之差差，记记为为vj，j=1，2，n；第第二二步步：找找出出所所有有行行、列列差差额额的的最最大大值值，即即L=maxui，vi，差差额额L对应行或列的最小运价处优先调运；对应行或列的最小运价处优先调运；第第三三步步：这这时时必必有有一一列列或或一一行行调调运运完完毕毕，在在剩剩下下的的运运价价中中再再求求
15、最最大大差差额额，进进行行第第二二次次调调运运，依依次次进进行行下下去去，直直到到最最后后全全部部调调运运完毕，就得到一个初始调运方案。完毕，就得到一个初始调运方案。用用元元素素差差额额法法求求得得的的基基本本可可行行解解更更接接近近最最优优解解，所所以以也也称称为为近近似方案。似方案。12/27/202212/27/2022运筹学课件运筹学课件B B1 1B B2 2B B3 3B B4 4a ai iA A1 15 58 89 912121515A A2 21 17 72 24 42525A A3 36 6101013138 82020b bj j202010105 525256060【例
16、例】用元素差额法求下表运输问题的初始基本可行解。用元素差额法求下表运输问题的初始基本可行解。【解解】求行差额求行差额ui,i=1,2,3及列差额及列差额vj,j=1,2,3,4.计算公式为计算公式为ui=i行次小运价行次小运价i行最小运价行最小运价vj=j列次小运价列次小运价j例最小运价例最小运价12/27/202212/27/2022运筹学课件运筹学课件 BjAiB1B2B3B4aiuiA158912153A21724251A3610138202bj201052560vj4174【】512/27/202212/27/2022运筹学课件运筹学课件 BjAiB1B2B3B4aiuiA158912
17、153A217242535A3610138202bj201052560vj41420【】0除去除去B3列，重新计算差额列，重新计算差额12/27/202212/27/2022运筹学课件运筹学课件 B Bj jA Ai iB B1 1B B2 2B B3 3B B4 4a ai iu ui iA A1 15 58 89 9121215154 4A A2 21 17 72 24 425255 5A A3 36 6101013138 820202 2b bj j202010105 525256060v vj j2 24 4200【】1020512/27/202212/27/2022运筹学课件运筹学课
18、件求求出出一一组组基基可可行行解解后后，判判断断是是否否为为最最优优解解，仍仍然然是是用用检检验验数数来来判判断断，记记xij的的检检验验数数为为ij由由第第一一章章知知，求求最最小小值值的的运运输输问问题题的的最最优优判别准则是：判别准则是：所有非基变量的检验数都非负，则运输方案最优（即为最优解）。所有非基变量的检验数都非负，则运输方案最优（即为最优解）。求检验数的方法有两种，闭回路法和位势法。求检验数的方法有两种，闭回路法和位势法。1闭闭回回路路法法求求检检验验数数求求某某一一非非基基变变量量的的检检验验数数的的方方法法是是：在在基基本本可可行行解解矩矩阵阵中中，以以该该非非基基变变量量为
19、为起起点点，以以基基变变量量为为其其它它顶顶点点，找找一一条条闭闭回回路路，由由起起点点开开始始，分分别别在在顶顶点点上上交交替替标标上上代代数数符符号号+、-、+、-、，以以这这些些符符号号分分别别乘乘以以相相应应的的运运价价，其其代代数数和和就就是是这个非基变量的检验数。这个非基变量的检验数。第二步，求检验数，判优第二步，求检验数，判优12/27/202212/27/2022运筹学课件运筹学课件5非基变量xij的检验数cij-zij闭回路法(1)12=c12-z12=c12-(c11-c21+c22)=7-6+8-4=512/27/202212/27/2022运筹学课件运筹学课件5闭回路法
20、(2)13=c13-z13=c13-c11+c21-c23)=5-6+8-2=5512/27/202212/27/2022运筹学课件运筹学课件5闭回路法(3)14=c14-z14=c14-(c11-c21+c21-c23+c33-c34)-=3-(6-8+2-10+6)=77512/27/202212/27/2022运筹学课件运筹学课件5闭回路法(4)c24-z24=c24-(c23-c33+c34)=7-(2-10+6)=995712/27/202212/27/2022运筹学课件运筹学课件5闭回路法(5)c31-z31=c31-(c21-c23+c33)=5-(8-2+10)=-11-115
21、7912/27/202212/27/2022运筹学课件运筹学课件5闭回路法(6)c32-z32=c32-(c22-c23+c33)=9-(4-2+10)=-3-3579-11这里31和 320,得到最优解。Min z=61+3 13+8 2+4 13+2 12+5 19=142115548212/27/202212/27/2022运筹学课件运筹学课件小结：运输问题的常用解法：最小元素法（确定初始方案）闭回路法（检验当前方案）闭回路法（方案调整）12/27/202212/27/2022运筹学课件运筹学课件例：某食品公司下设3个加工厂A1，A2，A3，和4个门市部B1，B2，B3，B4。各加工厂每
22、天的产量、各门市部每天的销售量以及从各加工厂到各门市部的运价如下表所示。问：该公司应如何调运，在满足各门市部销售需要的情况下，使得运费支出为最少？12/27/202212/27/2022运筹学课件运筹学课件 门市部门市部加工厂加工厂B B1 1 B B2 2 B B3 3 B B4 4产产 量量A A1 1A A2 2A A3 37 74 49 9销销 量量3 6 5 63 6 5 62020 门市部门市部加工厂加工厂B B1 1 B B2 2 B B3 3 B B4 4A A1 1A A2 2A A3 3 3 11 3 103 11 3 10 1 9 2 8 1 9 2 8 7 4 10 5
23、 7 4 10 5 产销平衡表 单位：吨 单位运价表 单位：元/吨12/27/202212/27/2022运筹学课件运筹学课件解：1.确定初始方案确定初始方案:(最小元素法基本思想：就近供应，即从单位运价表上最小的运价开始确定产销关系，以此类推，直到给出初始方案为止)从运价表上找出最小运价C2121=1，A2 2 先保证供应B1 1 ，X2121=3，划去运价表上B B1 1 列；再从运价表上其余元素中找到最小的运价C2323=2，加工厂A2 2 应供给B3 3，X2323=1，划去A2 2行；再从运价表上其余元素中找到最小的运价C1313=3，所以A1先保证供应B3 3，B3 3 尚缺4单位
24、，因此X1313=4，划去B3 3 列。12/27/202212/27/2022运筹学课件运筹学课件以此类推，得到一初始方案（如下图）：X21=3，X32=6，X13=4，X23=1，X14=3，X34=3（有数格）X11=X31=X12=X22=X33=X24=0（空格）B B1 1B B2 2B B3 3B B4 4A A1 14 43 3A A2 23 31 1A A3 36 63 3注：（）有数格是基变量，共m+n-1=3+4-1=6个。空格是非基变量，共划去m+n=7条线；（）如果填上一个运量之后能同时划去两条线（一行与一列），就须在所划去的该行或该列填一个0，此0格当有数个对待。初
25、始方案运费Z0=31+64+43+12+310+35=86(元)12/27/202212/27/2022运筹学课件运筹学课件2.2.检验检验检验检验（闭回路法（闭回路法（闭回路法（闭回路法:计算空格的检验数）计算空格的检验数）计算空格的检验数）计算空格的检验数）找出任意空格的闭回路找出任意空格的闭回路除此空格外，其余顶点均为有数格。除此空格外，其余顶点均为有数格。如从如从a11a11出发可找出发可找（A1A1 B1B1 ）（A1A1 B3B3 ）（A2A2 B3B3 ）（A2A2 B1B1 ）；）；计算出空格的检验数计算出空格的检验数等于闭回路上由此空格起奇数顶点运等于闭回路上由此空格起奇数顶
26、点运价与偶数顶点运价的价与偶数顶点运价的代数和代数和。如如 1111c11-c13+c13-c21=3-3+2-1=1c11-c13+c13-c21=3-3+2-1=1计算出此空格的检验数计算出此空格的检验数 ij ij,若若 ij ij，则该方案为最优方，则该方案为最优方案，否则转；案，否则转；每一个空格的检验数每一个空格的检验数=奇顶点运费之和奇顶点运费之和偶顶点运费之和。偶顶点运费之和。12/27/202212/27/2022运筹学课件运筹学课件B B1 1B B2 2B B3 3B B4 4A A1 11 12 24 43 3A A2 23 31 11 1-1-1A A3 310106
27、 612123 3注：检验数的经济意义，以注：检验数的经济意义，以 1111为例，空格表示原方案中为例，空格表示原方案中X11=0,即A1A1 B1B1 的运输量为的运输量为0 0。若试着运。若试着运1 1单位，则这样单位，则这样所引起的总费用的变化恰是所引起的总费用的变化恰是 1111，可见检验数，可见检验数 ij ij的意义是：的意义是：AiAi BjBj增运单位所引起的总费用的增量。增运单位所引起的总费用的增量。ij ij，说，说明若增运一单位则在总运输量不变情况下，总运费会增加。明若增运一单位则在总运输量不变情况下，总运费会增加。此时不应在此时不应在 AiAi BjBj上增运。上增运。
28、(+1)*3+(-1)*3+(+1)*2+(-1)*1=1空格检验数空格检验数 3 11 3 10 3 11 3 10 1 9 2 8 1 9 2 8 7 4 10 5 7 4 10 512/27/202212/27/2022运筹学课件运筹学课件B B1 1B B2 2B B3 3B B4 4A A1 11 12 24 43 3A A2 23 31 11 1-1-1A A3 310106 612123 324=(+1)*8+(-1)*2+(+1)*3+(-1)*10=-1表示原方案中表示原方案中X24=0,即A1A1 B1B1 的运输量为的运输量为0 0。若试。若试着运着运1 1单位，单位，引
29、起的总费用减少引起的总费用减少.+-3 11 3 10 3 11 3 10 1 9 2 8 1 9 2 8 7 4 10 5 7 4 10 512/27/202212/27/2022运筹学课件运筹学课件从 ij ij 为最小负值的空格出发.对其闭回路上的奇数顶点运量增加,偶数顶点的运量减少(这才能保证新的平衡)，其中为该空格闭回路中偶数顶点的最小值。242400，从（从（从（从（A A2 2 B B4 4）出发其闭回路上=1，调整后得到一个新方案（如下表），运量为=1的（A A2 2 B B3 3）变）变空空格，得到新方案后再转格，得到新方案后再转 2。经再计算新方案的检验数全部大于0。所以，
30、该新方案为最优方案，可计算得总运费为85元。注：若闭回路的偶数顶点中同时有两个格以上运量为，则调整后其中一个变空格，其余填0。（保证基变量个数不变）3 3 6 6 1 1 3 3 2 2 5 53.调整调整:129211212/27/202212/27/2022运筹学课件运筹学课件4）表上作业法须注意的问题：）表上作业法须注意的问题：i)在最终调运表中，若有某个空格（非基变量）的检验数为0时，则表明该运输问题有多重调运方案；ii)在确定初始方案时，若某一行的产量与某一列的需求量同时满足，这时也只能划去一行或一列（绝对不能同时把行、列划去，否则就不满足圈格=m+n1个的要求，即基变量的个数永远要
31、保持为m+n1个）；iii)在用闭回路法调整时，当闭回路上奇顶点有几个相同的最小值时，调整后只能有一个空格，其余均要保留数“0”，以保证圈格=m+n1个的需要。iv)用最小元素法所得到的初始方案可以不唯一。12/27/202212/27/2022运筹学课件运筹学课件（）产销不平衡的运输问题）产销不平衡的运输问题1.1.产大于销的情况：产大于销的情况：添加松弛变量xin+1xin+1的定义：由Ai向Bn+1的运量，而Bn+1并不存在，相当于增加了一个虚设的销地Ai自己的仓库里，自己往自己的地方运，运费运费cin+1显然为显然为0。实际上xin+1即剩余量就地库存12/27/202212/27/2
32、022运筹学课件运筹学课件产大于销的产销量表A1Ama1amB1Bnb1bnBn+1A1AmB1BnC1100C1nCm1Cmn产大于销的单位运价表Bn+112/27/202212/27/2022运筹学课件运筹学课件2.销大于产的情况：销大于产的情况：添加松弛变量xm+1j同理，此时xm+1j的意义为销售短缺的量，同样，Am+1不存在，cm+1j为0。12/27/202212/27/2022运筹学课件运筹学课件销大于产的产销量表A1Ama1amB1Bnb1bnAm+1A1AmB1BnC1100C1nCm1Cmn销大于产的单位运价表Am+112/27/202212/27/2022运筹学课件运筹学
33、课件B1B1B2B2B3B3B4B4a ai iA1A15 59 92 23 36060A2A2-4 47 78 84040A3A33 36 64 42 23030A4A44 48 8101011115050b bj j2020606035354545180180160160因为有因为有：【例例】求下列表中极小化运输问题的最优解。求下列表中极小化运输问题的最优解。所以是一个产大于销的运输问题。所以是一个产大于销的运输问题。12/27/202212/27/2022运筹学课件运筹学课件表中表中A2不可达不可达B1，用一个很大的正数用一个很大的正数M表示运价表示运价C21。虚设一虚设一个销量为个销量
34、为b5=180160=20的销地的销地B5，Ci5=0，i=1，2，3，4。表的右边增添一列表的右边增添一列这样可得新的运价表：这样可得新的运价表：B1B1B2B2B3B3B4B4B5B5a ai iA1A15 59 92 23 30 06060A2A2MM4 47 78 80 04040A3A33 36 64 42 20 03030A4A44 48 8101011110 05050b bj j2020606035354545202018018012/27/202212/27/2022运筹学课件运筹学课件B1B1B2B2B3B3B4B4B5B5AiAiA1A1353525256060A2A24
35、0404040A3A3101020203030A4A42020101020205050BjBj20206060353545452020180180下表为计算结果。可看出：产地下表为计算结果。可看出：产地A4还有还有20个单位没个单位没有运出。有运出。12/27/202212/27/2022运筹学课件运筹学课件上例中，假定上例中，假定B1的需要量是的需要量是20到到60之间，之间，B2的需要量是的需要量是50到到70，试求极小化问题的最优解。，试求极小化问题的最优解。B1B1B2B2B3B3B4B4a ai iA1A15 59 92 23 36060A2A2-4 47 78 84040A3A33
36、 36 64 42 23030A4A44 48 8101011115050b bj j202060605050707035354545180180150150210210需求量不确定的运输问题需求量不确定的运输问题12/27/202212/27/2022运筹学课件运筹学课件（1）总产量为）总产量为180，B1，B4的最低需求量的最低需求量20+50+35+45=150，这时属产大于销；，这时属产大于销；（2）B1，B4的最高需求是的最高需求是60+70+35+45=210，这时属销大于产，这时属销大于产（3）虚设一个产地）虚设一个产地A5，产量是产量是210180=30，A5的产量只能供的产量
37、只能供应应B1或或B2。（4）将）将B1与与B2各分成两部分各分成两部分的需求量是的需求量是20，的需求量是的需求量是40，的需求量分别是的需求量分别是50与与20，因此，因此必须由必须由A1，A4供应，供应，可由可由A1、A5供应。供应。（5）上述）上述A5不能供应某需求地的运价用大不能供应某需求地的运价用大M表示，表示，A5到到、的的运价为零。得到下表的产销平衡表。运价为零。得到下表的产销平衡表。先作如下分析：先作如下分析：12/27/202212/27/2022运筹学课件运筹学课件B B3 3B B4 4a ai iA1A15 55 59 99 92 23 36060A2A2MMMM4
38、44 47 78 84040A3A33 33 36 66 64 42 23030A4A44 44 48 88 8101011115050A5A5MM0 0MM0 0MMMM3030b bj j202040405050202035354545210210得到这样的平衡表后，计算得到最优方案表得到这样的平衡表后，计算得到最优方案表5-29。产销平衡表产销平衡表12/27/202212/27/2022运筹学课件运筹学课件B3B4aiA1352560A24040A30102030A4203050A5102030bj204050203545210表表中中：x131=0是是基基变变量量,说说明明这这组组解
39、解是是退退化化基基本本可可行行解解,空空格格处处的的变变量量是是非非基基变变量量。B1，B2，B3，B4实实际际收收到到产产品品数数量量分分别别是是50，50，35和和45个单位。个单位。12/27/202212/27/2022运筹学课件运筹学课件有些问题表面上与运输问题没有多大关系，也可以建立与有些问题表面上与运输问题没有多大关系，也可以建立与运输问题形式相同的数学模型运输问题形式相同的数学模型看一个例子：看一个例子：【例例】有三台机床加工三种零件，计划第有三台机床加工三种零件，计划第i台的生产任务为台的生产任务为a i(i=1,2,3)个零件，第个零件，第j 种零件的需要量为种零件的需要量
40、为bj (j=1,2,3)，第第i 台台机床加工第机床加工第j 种零件需要的时间为种零件需要的时间为cij，如表如表32所示。问如何安所示。问如何安排生产任务使总的加工时间最少？排生产任务使总的加工时间最少？零件零件零件零件机床机床机床机床B1B1B2B2B3B3生产任务生产任务生产任务生产任务A1A15 52 23 35050A2A26 64 41 16060A3A37 73 34 44040需要量需要量需要量需要量707030305050150150表表3212/27/202212/27/2022运筹学课件运筹学课件5 52 23 350506 64 41 160607 73 34 440
41、407070303050501501505030201040确定初始基可行解确定初始基可行解12/27/202212/27/2022运筹学课件运筹学课件5 52 23 350506 64 41 160607 73 34 440407070303050501501505030201040312-1计算空格的检验数320初始基可行解非优.X32进基,min(30,40)=30,x12出基12/27/202212/27/2022运筹学课件运筹学课件5 52 23 350506 64 41 160607 73 34 4404070703030505015015050305010103221调整量=30
42、,调整x32,x31,x11,x12计算新的可行解的空格检验数,全大于零,为最优12/27/202212/27/2022运筹学课件运筹学课件DF公司在接下来的三个月内每月都要按照销售合同生产出两种公司在接下来的三个月内每月都要按照销售合同生产出两种产品。产品。表表中给出了在正常时间（中给出了在正常时间（RegularTime，缩写为，缩写为RT）和）和加班时间（加班时间（OverTime，缩写为，缩写为OT）内能够生产这两种产品的）内能够生产这两种产品的总数。总数。月月最大生最大生产总产总量量产产品品1/产产品品2销销售售产产品品1/产产品品2单单位生位生产产成本成本(1000元元/件件)单单位位储储存成存成本（本（1000元元/件）件）RTOTRTOT123108103235/33/54/415/1617/1519/1718/2020/1822/221/22/1（1）对这个问题进行分析，描述成一个运输问题的产销平衡表，）对这个问题进行分析，描述成一个运输问题的产销平衡表，使之可用运输单纯形法求解使之可用运输单纯形法求解（2）建立总成本最小的数学模型并求出最优解）建立总成本最小的数学模型并求出最优解作作 业业12/27/202212/27/2022运筹学课件运筹学课件