《工学运输问题》教学课件

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

2、 x12+x22+x32= 4000 x13+x23+x33= 2000 x14+x24+x34= 1500 xij0,第4页，共40页。运输问题线性规划的一般形式st. 供应：需求：第5页，共40页。供求平衡问题的特征 基变量的个数=m+n-1第6页，共40页。初始基本可行解的构造第7页，共40页。西北角方法5000100001000050004000010001000010001000015001500第8页，共40页。最小元素法4000010002500200015003500002500250040000025001000第9页，共40页。运输问题的特殊解法闭回路方法 检验数：非基变量

3、增加一个单位引起的成本变化量第10页，共40页。闭回路方法-例 第11页，共40页。初始基本可行解：基本可行解第12页，共40页。检验数的计算： 闭回路检验数第13页，共40页。初始基本可行解与检验数： 基本可行解检验数第14页，共40页。=2500基本可行解的调整： 第15页，共40页。检验数的重新计算： 检验数均大于0，得最优解：第16页，共40页。运输问题的特殊解法位势方法 检验数：目标函数的系数减去对偶变量之和第17页，共40页。st. 供应：需求：对偶变量 ui对偶变量 vj第18页，共40页。st. 对偶变量 xij第19页，共40页。原问题检验数： ij=cij-(ui+vj)i

4、=1,2,m; j=1,2,n特别对于m+n-1个基变量，有 ij=cij-(ui+vj)=0第20页，共40页。位势法-例第21页，共40页。初始基本可行解：基本可行解第22页，共40页。位势计算：第23页，共40页。检验数的计算： 第24页，共40页。退化问题的处理 保证基变量的个数为m+n-1第25页，共40页。500000第26页，共40页。非平衡问题的处理 -转换为平衡问题第27页，共40页。供过于求的处理第28页，共40页。供不应求的处理第29页，共40页。运输问题的推广转运问题第30页，共40页。转运问题-例生产厂1Denver2Atlanta6Miami5Detroit7Dal

5、las8NewOrleans零售店6004002003003501503236431162543KansasCity4Louisville64批发部第31页，共40页。MinZ=2x13+3x14+3x23+x24+2x35+6x36+3x37+6x38+4x45+4x46+6x47+5x48+4x28+x78S. t.x13+x14600 x23+x24+x28400-x13-x23+x35+x36+x37+x38=0-x14-x24+x45+x46+x47+x48=0 x35+x45=200 x36+x46=150 x37+x47-x78=350 x38+x48+x28+x78=300 x

6、ij0for all i, j供应转运需求线性规划模型第32页，共40页。转运问题分析与建模要点 纯供应节点有供应量Si，无需求量，无转运功能生产厂1Denver60032供应量第33页，共40页。纯需求节点无供应量，有需求量dj，无转运功能5Detroit零售店200需求量24第34页，共40页。供应节点有供应量，无需求量，具有转运功能生产厂1Denver60032供应量4第35页，共40页。需求节点无供应量，有需求量dj，具有转运功能7Dallas350163销售商需求量第36页，共40页。纯转运节点无供应量，无需求量，仅具有转运功能236323KansasCity6批发部第37页，共40页。一般转运节点有供应量Si，有需求量di，又具有转运功能2633KansasCity56002001需求量供应量第38页，共40页。转运问题的应用生产与库存计划第39页，共40页。