资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第四章 运输问题,4,、,1,运输问题,4.2,运输问题得表上作业法,4.3,运输问题的进一步讨论,1,产销平衡问题得数学模型,表上作业法就是单纯形法在求解运输问题得一种简便方法。,单纯形法与表上作业法的关系,:,(,1,),找出初始基可行解,（2）求各非基变量的检验数,（3）判断是否最优解,计算表中空格检验数,表上给出,m+n-1,个数字格,检验是否所有检验数非负,换基,:,(,4,),确定换入变量与换出变量找出新得基可行解。,（5）重复（2）、（3）直至求出最优解。,表上调整（闭回路调整）,（运输问题必有最优解）,停止,最优解,？,是,否,举例说明表上作业法,例1、某部门三个工厂生产同一产品得产量、,四个销售点的销量及单位运价如下表,:,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,第一步,:,确定初始基可行解 最小元素法、伏格尔法,最小元素法思路,:,从单价中最小运价确定供应量,逐步次小，直至得到,m+n-1,个数字格。,最小元素法举例,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,2,0,10,10,0,6,14,8,6,8,0,0,0,0,6,0,例1用伏格尔法得到得初始基可行解,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,4,8,14,8,12,2,目标函数值,用最小元素法,求出得目标函数,z=246,一般说来,伏格尔法得出得初始解的质量最好，常用来作为运输问题最优解的近似解。,大家有疑问的，可以询问和交流,可以互相讨论下，但要小声点,第三步,:,解得调整,调整位置,(,2,4,),非空，回路角上得格至少为空，且保证数字的非负性。,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,10,14,6,8,-1,(,-2,),(,-2,),(,+2,),(,+2,),调整后得解为,:,4,12,2,8,5,4,3,9,6,11,11,10,销量,产量,销地,产地,8,2,12,14,4,8,2,2,0,9,1,12,此时的解为最优解。,有无穷多最优解,几点说明,:,当检验数为得负的变量超过两个,选择最小者对应的变量换入,;,在最优解的表中，若有检验数=0，则该运输问题有无穷多最优解；,迭代过程中，若某一格填数时需同时划去一行与一列，此时出现退化。为保证,m+n-1,个非空格，需在上述的行或列中填入数字0。,产销不平衡得运输问题,实际问题中产销往往就是不平衡的,就需要把产销不平衡的问题转化成产销平衡问题。,产大于销,销大于产,一、产销不平衡得运输问题,(,),若总产量大于总销量,即,令假象销地的销量为：,这里,松弛变量,x,i n,+1,可以视为从产地,A,i,运往销地,B,n,+1,得运输量，由于实际并不运送，它们的运费为,c,i n,+1,=0,i,=1,，,2,m,。,于就是，这个运输问题就转化成了一个产销平衡的问题。,原产大于销平衡问题得数学模型,修改后产大于销平衡问题得数学模型,决策变量 表示由 到 得物品数量。,销地,产地,销量,产量,注意,:,用最小元素法求初始调运方案时,最后一列得零运价最后考虑。,例,:,某公司从两个产地,A,1,、,A,2,将物品运往三个销地,B,1,、,B,2,、,B,3,各产地得产量、各销地的销量与各产地运往各销地每件物品的运费如下表所示，问,:,应如何调运可使总运输费用最小？,解,:,增加一个虚设得销地运输费用为,0,(,),若总产量小于总销量,即,令假象产地的销量为：,一、产销不平衡得运输问题,仿照上述类似处理。,这里,松弛变量,x,m,+1,，,j,可以视为从产地,A,m,+1,运往销地,B,j,得运输量，由于实际并不运送，它们的运费为,c,m,+1,j,=0,j,=,1,2,n,。,于就是，这个运输问题就转化成了一个产销平衡的问题。,例,:,某公司从两个产地,A,1,、,A,2,将物品运往三个销地,B,1,、,B,2,、,B,3,各产地得产量、各销地的销量与各产地运往各销地每件物品的运费如下表所示，问,:,应如何调运可使总运输费用最小？,解,:,增加一个虚设得产地运输费用为,0,产销不平衡运输问题举例,设有,A,、,B,、,C,三个化肥厂供应,1,、,2,、,3,、,4,四个地区得农用化肥。假设效果相同,有关数据如下表,举例,根据题意,作出产销平衡运价表,:,最低要求必须满足,因此把相应得虚设产地运费取,M,，而最高要求与最低要求的差允许按需要安排，因此把相应的虚设产地运费取为,0,。对应,4”,的销量,50,就是考虑问题本身适当取的数据，根据产销平衡要求确定,D,的产量为,50,。,Ex,、,2,已知运输问题由表给出,试建立运输模型,、,解,:,本题产量为,25,销量为,29,，就是销大于产问题,虚设一个产地,A,3,由于并没有生产，所以运价为零，得运输模型、,如果各销地不满足时,单位缺货费为,4,，,3,，,7,，则运输模型为,4,3,7,运输问题,讨论,29,一、概念题,(,判断,),1、运输问题就是一种,LP,问题,其求解结果有四种情况。,2、在运输问题中，只要给出一组含,(m+n-1),个非零得 ，且满足,就可以作为一个初始基可行解。,
展开阅读全文