(例题)运筹学 运输问题课件.ppt

《(例题)运筹学 运输问题课件.ppt》由会员分享，可在线阅读，更多相关《(例题)运筹学 运输问题课件.ppt（40页珍藏版）》请在三一办公上搜索。

1、经典运输问题,网络表示,线性规划模型,运输问题线性规划的一般形式,st.供应：,需求：,供求平衡问题的特征,基变量的个数=m+n-1,初始基本可行解的构造,西北角方法,5000,1000,4000,1000,1000,1500,最小元素法,4000,2500,2000,1500,2500,1000,运输问题的特殊解法闭回路方法,检验数：非基变量增加一个单位引起的成本变化量,闭回路方法-例,初始基本可行解：,基本可行解,检验数的计算：,闭回路,检验数,初始基本可行解与检验数：,基本可行解,检验数,=2500,基本可行解的调整：,检验数的重新计算：,检验数均大于0，得最优解：,运输问题的特殊解法位

2、势方法,检验数：目标函数的系数减去对偶变量之和,st.,对偶变量 xij,原问题检验数：ij=cij-(ui+vj),i=1,2,m;j=1,2,n,特别对于m+n-1个基变量，有 ij=cij-(ui+vj)=0,位势法-例,初始基本可行解：,基本可行解,位势计算：,检验数的计算：,退化问题的处理,保证基变量的个数为m+n-1,5000,非平衡问题的处理,-转换为平衡问题,供过于求的处理,供不应求的处理,运输问题的推广转运问题,转运问题-例,线性规划模型,转运问题分析与建模要点,纯供应节点有供应量Si，无需求量，无转运功能,纯需求节点无供应量，有需求量dj，无转运功能,5,Detroit,零售店,200,需求量,2,4,供应节点有供应量，无需求量，具有转运功能,需求节点无供应量，有需求量dj，具有转运功能,纯转运节点无供应量，无需求量，仅具有转运功能,一般转运节点有供应量Si，有需求量di，又具有转运功能,转运问题的应用生产与库存计划,网络模型,