《运筹学》课件运筹三.ppt
《《运筹学》课件运筹三.ppt》由会员分享,可在线阅读,更多相关《《运筹学》课件运筹三.ppt(22页珍藏版)》请在三一文库上搜索。
1、1第三章第三章 运输问题运输问题 顺风而呼,声非加疾也,而闻者彰。顺风而呼,声非加疾也,而闻者彰。假舆马者,非利足也,而致千里;假舟假舆马者,非利足也,而致千里;假舟楫者,非能水也,而绝江河。君子生非楫者,非能水也,而绝江河。君子生非异也,善假于物也。异也,善假于物也。荀子荀子劝学劝学23.1 运输问题的一般数学模型运输问题的一般数学模型 有有m个产地生产某种物资,有个产地生产某种物资,有n个地区需要该类物资个地区需要该类物资 令令a1,a2,am表示各产地产量,表示各产地产量,b1,b2,bn表示各销表示各销地的销量,地的销量,ai=bj 称为产销平衡称为产销平衡 设设xij表示产地表示产地
2、 i 运往销地运往销地 j 的物资量,的物资量,wij表示对应的单表示对应的单位运费,则我们有运输问题的数学模型如下:位运费,则我们有运输问题的数学模型如下:0 ,2,1 ,2,1)(min1111ijjmiijnjiijminjijijxnjbxmiaxxwxf销量约束产地约束运输问题有运输问题有m n个个决策变量,决策变量,m+n 个个约束条件。由于产约束条件。由于产销平衡条件,只有销平衡条件,只有m+n1个相互独立,个相互独立,因此,运输问题的因此,运输问题的基变量只有基变量只有m+n1 个个33.2 运输问题的求解方法运输问题的求解方法 约束条件非常有规律,技术系数非约束条件非常有规律
3、,技术系数非 0 即即 1 基变量的个数远小于决策变量的个数基变量的个数远小于决策变量的个数 采用表上作业法,称为位势法和踏石法采用表上作业法,称为位势法和踏石法 运算中涉及两个表:运费表和产销平衡表运算中涉及两个表:运费表和产销平衡表(分配表分配表)销地销地产量产量运量运量12nai产地产地1x11x12x1na12x21x22x2na2 mxm1xm2xmnam销量销量 bjb1b2bn销地销地运费运费12n产地产地1w11w12w1n2w21w22w2n mwm1wm2wmn45 3.2.1 寻找初始可行解的方法寻找初始可行解的方法 1、西北角法、西北角法 从从 x11开始分配,从西北向
4、东南方向逐个分配开始分配,从西北向东南方向逐个分配 xij 的分配公式的分配公式列待分物资量列已分配的总量行尚余物资量行已分配的总量)()(minjjbiiaxjiij例例3.2.1销地销地产量产量运费运费1234ai产地产地120113652591021031874115销量销量 bj3312126销地产量运量1234ai产地15210315销量 bj331212 例例3.2.1 西北角法西北角法销地产量运量1234ai产地13x125210315销量 bj331212销地产量运量1234ai产地13252x2210315销量 bj331212销地产量运量1234ai产地132521x231
5、0315销量 bj331212销地产量运量1234ai产地1325219103x3315销量 bj331212销地产量运量1234ai产地13252191033x3315销量 bj331212销地产量运量1234ai产地132521910331215销量 bj3312123141205)(67ijijijxwxfnm个基变量有7 2、最低费用法、最低费用法采用最小费用优先分配的原则,看一步采用最小费用优先分配的原则,看一步编号编号运费表运费表wij分配表分配表xij2011(3)6x135I5910210187411215331212编号编号运费表运费表wij分配表分配表xij20113655
6、II5910210187(4)1x331215331212编号编号运费表运费表wij分配表分配表xij20113655III59(10)2334101874131215331212f(x)=121,比,比西北角法低西北角法低848 3、运费差额法、运费差额法采用最大差额费用采用最大差额费用(即利用每行或列中最小费用与次最小之即利用每行或列中最小费用与次最小之间的差额中选最大间的差额中选最大)优先分配的原则,看两步优先分配的原则,看两步编号编号运费表运费表wij分配表分配表xij20113635I5910233101874131513211331212f(x)=98,比,比最低费用法最低费用法又
7、低了又低了23编号编号运费表运费表wij分配表分配表xij20113635II59102737101874131513211331212编号编号运费表运费表wij分配表分配表xij20113635III591027371018741351513415331212编号编号运费表运费表wij分配表分配表xij201136855IV59102737101874133751513-53312129 3.2.2 利用位势法检验分配方案是否最优利用位势法检验分配方案是否最优1、标准单纯形法(目标函数求、标准单纯形法(目标函数求Max)最优检验条件为最优检验条件为cj-zj 0,通过类比法可知,运输问题的检
8、验条件为:,通过类比法可知,运输问题的检验条件为:zij-wij 0;2、由于基变量的检验数为、由于基变量的检验数为0,所以,对于基变量,有,所以,对于基变量,有zij=wij3、一般地,令、一般地,令zij=ui+vj,且令任意一个,且令任意一个ui或或vj等于等于0(因为(因为5=5+0=4+1=3+2=2+3=1+4=0+5),4、然后利用基变量的检验数满足、然后利用基变量的检验数满足zij=wij及关系及关系zij=ui+vj求得所求得所有的有的ui、vj和和zij5、利用检验条件、利用检验条件 zij-wij 0进行最优检验。进行最优检验。10 3.2.3 踏石法踏石法1、找入变量、
9、找入变量 从从 zij wij 0 中找最大者,对应中找最大者,对应 xij 就是入变量就是入变量2、以、以 xij 为起点,寻找由原基变量构成的为起点,寻找由原基变量构成的闭合回路闭合回路 该回路只在每个拐角各有一个基变量,中间允许穿越某些基该回路只在每个拐角各有一个基变量,中间允许穿越某些基变量;因此,闭合回路中必有偶数个变量变量;因此,闭合回路中必有偶数个变量(包括包括 xij),且回路,且回路中每行每列只有两个变量中每行每列只有两个变量3、求入变量、求入变量 xij 的最大值及新基变量的解的最大值及新基变量的解 从从 xij出发,沿任一个方向对回路拐角上的基变量依此标出发,沿任一个方向
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 课件 运筹
链接地址:https://www.31doc.com/p-21713332.html