运筹学运输问题表上作业法.ppt

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

1、运筹学李细霞2013物流工程1班2014~2015学年第二学期课程主要内容绪论线性规划及单纯形法对偶理论与灵敏度分析运输问题整数规划目标规划动态规划图与网络Transportationproblem3第三章运输问题学习目标什么是运输问题？如何解决运输问题？复杂运输问题主要内容问题描述（模型）问题解决(表上作业法)复杂运输问题（应用）思考运输问题要解决什么？什么叫一个运输方案？什么叫一个最优的运输方案？若用xij表示从Si到Dj的运量，那么在产销平衡的条件下，求总运费最小的方案。问题描述7表格模型8生产量：A1-7吨，A2-4吨，A3-9吨销售量：B1-3吨，B2-6吨，B

2、3-5吨，B4-6吨产地单位运价销地B1B2B3B4A1A2A3311310192874105举例产销平衡？9A1A2A3B1B2B3B47吨4吨9吨3吨6吨5吨6吨x11x12x13x14x21x22x23x24x31x32x33x34产地销地调运示意图10此问题是线性规划问题吗？请建立此问题的模型目标？约束条件？思考11二、建立模型设：xij——第i产地到第j销地之间的调运量，则有Minz=cij·xij34i=1j=1x11+x12+x13+x14=7x11+x21+x31=3xij0,(i=1,2,┄,3；j=1,2,┄,4)产量限制销量限制x21+x22+

3、x23+x24=4x31+x32+x33+x34=9x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6可否用单纯形法求解？12ai=bj产销平衡运输问题的一般表示13调运模型为：m×n个变量m个约束n个约束共有m+n个约束条件？14约束条件展开15约束条件的系数矩阵有何特点？161.变量数：mn个2.约束方程数：m+n个最大独立方程数：m+n-13.系数列向量结构：Pij=——第i个分量——第m+j个分量产销平衡运输问题模型的特点Why?0…1.1.017定理平衡条件下的运输问题一定有最优解证：若设åå====njjmiibaQ11，并

4、令Qbaxjiij=，则][ijx显然是一组可行解，又因为总费用不会为负值，这说明，运输问题既有可行解，又必然有下界存在，因此一定有最优解存在。显然，由于运输问题属线性规划问题，因此无疑可以用单纯形方法求解，但由于其数学模型自身结构的特殊性，也可以利用更简便的方法来求解。这与运输问题的特点有关。唯一最优解？无穷多最优解？18初始解最优性检验调整基本可行解检验数基变换用单纯形法求解线性规划问题的步骤表上作业法19单纯形法在求解运输问题时的一种简化方法20初始方案最优性检验方案调整1.西北角法2.最小元素法3.伏格尔法1.闭回路法2.位势法闭回路法表上作业法步骤举例产量产地销

5、地A1A2A3B1B2B3B4销量4131025365674931198710运价总产=总销22初始方案的确定西北角法最小元素法伏格尔法23西北角法产量产地销地A1A2A3B1B2B3B4销量3656749342236有何疑问？24西北角法的优劣？太简单咯！最优解有点望尘莫及呢25几点疑问为什么要从西北角开始？为什么每次填数一定要填最大允许量，然后划掉一行（或一列）？为什么有数格只有6个？（总共有12个格）26基本可行解一个基本可行解：有m+n-1个基变量（有数格），其余为非基变量（空格）m+n-1个变量不能构成闭回路充要条件运输问题的m+n个约束方程中，有且只有m+n-

6、1个有效方程举例1234123123412312341231234123下面这些有数格组成了闭回路（不能作为基本可行解）什么是闭回路？123412312341231234123123412312341231234123下面这些有数格没有组成闭回路（可以作为基本可行解）29几点疑问的解答为什么要从西北角开始？为什么每次填数一定要填最大允许量，然后划掉一行（或一列）为什么有数格只有6个？（总共有12个格）m+n-1个变量不能构成闭回路只有6个有数格基变量的个数为m+n-1（3+4-1）30所有问题答案归结一句话：保证初始方案是运输问题（线性规划问题）的基本可行解Why？随便一

7、个可行解不行么？31最小元素法产量产地销地A1A2A3B1B2B3B4销量365674931131019287410531463332最小元素法的优劣？也很简单哦最优解可望，但还是有一定距离的33伏格尔法产量产地销地A1A2A3B1B2B3B4销量365674931131019287410534产地销地A1A2A3B1B2B3B4行差额列差额31131019287410501125130122-1301-2-1276---12Vogel法:产地销地A1A2A3B1B2B3B4749产量销量3656635213产销平衡表单位运价