(例题)运筹学-运输问题

经典运输问题网络表示供应商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=6000x11+x21+x31=4000x11+x21+x31=2000x11+x21+x31=1500xij³0,运输问题线性规划的一般形式st.供应：需求：供求平衡问题的特征

基变量的个数=m+n-1初始基本可行解的构造西北角方法5000100001000050004000010001000010001000015001500最小元素法4000010002500200015003500002500250040000025001000运输问题的特殊解法

——闭回路方法检验数：非基变量增加一个单位引起的成本变化量闭回路方法---例

初始基本可行解：基本可行解检验数的计算：

闭回路检验数初始基本可行解与检验数：

基本可行解检验数θ=2500基本可行解的调整：

检验数的重新计算：

检验数均大于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非平衡问题的处理

----转换为平衡问题供过于求的处理供不应求的处理运输问题的推广

——转运问题转运问题---例生产厂1Denver2Atlanta6Miami5Detroit7Dallas8NewOrleans零售店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=300xij³0foralli,j供应转运需求线性规划模型转运问题分析与建模要点

纯供应节点——有供应量Si，无需求量，无转运功能生产厂1Denver60032供应量纯需求节点——无供应量，有需求量dj，无转运功能5Detroit零售店200需求量24供应节点——有供应量，无需求量，具有转运功能生产厂1Denver60032供应量4需求节点——无供应量，有需求量dj，具有转运功能7Dallas350163销售商需求量纯转运节点——无供应量，无需求量，仅具有转运功能236323KansasCity6批发部一般转运节点——有供应量Si，有需求量di，又具有转运功能2633KansasCity56002001需求量供应量转运问题的应用——生产与库存计划网络模型生产第一