工学运输问题ppt课件.ppt

《工学运输问题ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、经典运输问题网络表示供应商1Cleveland2Bedford3York2Chicago1Boston3St.Louis4Lexington销售商5,0002,5006,0006,0001,5002,0004,000327627534255线性规划模型MinZ=3x11+2x12+7x13+6x14+7x21+5x22+2x23+3x24+2x31+5x32+4x33+5x34S.t.x11+x12+x13+x14≤5000x21+x22+x23+x24≤6000x31+x32+x33+x34≤2500x11+x21+x31=6000x12+x22+x32=4000x13+x23+x33

2、=2000x14+x24+x34=1500xij³0,运输问题线性规划的一般形式st.供应：需求：供求平衡问题的特征基变量的个数=m+n-1初始基本可行解的构造西北角方法5000100001000050004000010001000010001000015001500最小元素法4000010002500200015003500002500250040000025001000运输问题的特殊解法——闭回路方法检验数：非基变量增加一个单位引起的成本变化量闭回路方法---例初始基本可行解：基本可行解检验数的计算：闭回路检验数初始基本可行解与检验数：基本可行解检验数θ=2500基本可行解的调整：检

3、验数的重新计算：检验数均大于0，得最优解：运输问题的特殊解法——位势方法检验数：目标函数的系数减去对偶变量之和st.供应：需求：对偶变量ui对偶变量vjst.对偶变量xij原问题检验数：λij=cij-(ui+vj)i=1,2,……m;j=1,2,……n特别对于m+n-1个基变量，有λij=cij-(ui+vj)=0位势法---例初始基本可行解：基本可行解位势计算：检验数的计算：退化问题的处理保证基变量的个数为m+n-1500000非平衡问题的处理----转换为平衡问题供过于求的处理供不应求的处理运输问题的推广——转运问题转运问题---例生产厂1Denver2Atlanta6Miami5

4、Detroit7Dallas8NewOrleans零售店6004002003003501503236431162543KansasCity4Louisville64批发部MinZ=2x13+3x14+3x23+x24+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48+4x28+x78S.t.x13+x14≤600{x23+x24+x28≤400-x13-x23+x35+x36+x37+x38=0{-x14-x24+x45+x46+x47+x48=0x35+x45=200x36+x46=150x37+x47-x78=350{x38+x48+x28+x78=30

5、0xij³0foralli,j供应转运需求线性规划模型转运问题分析与建模要点纯供应节点——有供应量Si，无需求量，无转运功能生产厂1Denver60032供应量纯需求节点——无供应量，有需求量dj，无转运功能5Detroit零售店200需求量24供应节点——有供应量，无需求量，具有转运功能生产厂1Denver60032供应量4需求节点——无供应量，有需求量dj，具有转运功能7Dallas350163销售商需求量纯转运节点——无供应量，无需求量，仅具有转运功能236323KansasCity6批发部一般转运节点——有供应量Si，有需求量di，又具有转运功能2633KansasCity560

6、02001需求量供应量转运问题的应用——生产与库存计划网络模型生产第一季度第二季度600300235第四季度第三季度500400需求第一季度第二季度400500第四季度第三季度40040030.250.250.25生产能力生产需求量