数学软件MATLAB课件第三章运输问题.ppt

1、运筹学OPERATIONAL RESEARCH，第三章运输问题，第一节运输问题和数学模型，1，运输问题的典型形式和数学模型，1。实例，查找最低运费成本的发运方法，minZ=6x11 4x12 5x13 6x21 5x22 5x23，x11x 12x 13=300 x21x 22x 23=200 x11x 21=150 x12x 22=150 x13x 23典型运输问题：C11，C12，CM1，C21，C22，C2n，C1n，CMN，CM2，C11 x112 x13=300 x23运输问题的数学模型，I=1，2，j=运输问题约束条件的系数矩阵：x11x 12x 13=300 x21x 22x 2

2、3=200 x11x 21=150 x12x 22=150 x13x 23=200 xij 0，2(3)产销平衡问题是同等限制。(4)在生产销售平衡问题上，各产地产量之和等于各产地销售量之和。3 .运输问题的基本变量数：m n-1，2节表工作法，1，表工作法的基本思想和步骤：1。基本思想：单纯形法的基本思想，2 .表工作法的步骤(1)找到初始基本可行的解决方案。最小元素方法、西北角方法、沃格尔方法(2)求出非本变量检查数(空格检查数)，以确定是否为最佳解决方案。闭合电路法，电位法(3)交换器改进，新的基础可行闭环调整法(4)迭代(2)(3)，2，初始基础可行性解决方法(1)最小元素方法：寻找运

3、费最低的运输方案。范例(P82范例1)，0，0，6，0，0，(2)西北角法，(2)西北角法差异越大，以最小运费运送因此，在差额最大的地方，您必须分别计算最小运费、补偿数=用于辅助冲减的-最小成本、1、价目表中每行、列的行补偿数和列补偿数，然后填写表中最右边的列和最下面的行。2、选择行或列差异中最大的一个，然后选择行或列中最小的一个。以类似于最小值的方法优先供应，搅拌相应的行或列。(威廉莎士比亚，范本，望) (威廉莎士比亚，歌剧，望)3，在表格中重复步骤1，2，直到所有行和列都被清除为止。(阿尔伯特爱因斯坦，Northern Exposure(美国电视电视剧)，沃格尔法基本步骤：，)，注：min

4、z=c11x 11 c12x 12 C1 nx1 n cm1xm 1 cm2xm 2 cmnxmn，(2)双变量方法(位方法)，1 .基本原理，将双变量矢量设置为y=(u1，U2)J=c J-c B- 1 pj=CJ-y pj ij=c ij-c B- 1 pij=cij-y pij=cij-y pij=cijVn) Pij=Cij-(ui VJ) xij是主变量时，ij=Cij-(ui VJ )=0到总计m n-1个双变量，因此，如果选择其中一个双变量为0，那么就可以找到其馀所有的ij=Cij-=Cij-。，11=4-(3 0)=1 12=12-(10 0 0)=2 22=10-(10-1)=1 A2，B4=9-(11-1)使用常规ij0中最小的相应变量作为替换变量。(2)在最优解中，非基本变量的检验数为零，则运输问题存在无穷多个解。(3)如果在重复过程中需要逐格填写，需要同时划行和列，就会发生退化。为了确保M n-1郑智薰空格，上述行或列中包含数字0(其位置为该行或该列的所有空格中相应单位运费牙齿最小的空格)，练习：最低运费的运输方案，第3节运输问题的进一步讨论1，生产销售不平衡的运输问题示例1:大于生产牙齿销售的运费0，I=1，2， 添加销售j的虚拟销售地Bn 1(虚拟仓库):M，m1，j=1，2，n，xi