版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
关于运输问题表上作业法
确定初始方案(初始基本可行解)
改进调整(换基迭代)否
判定是否最优?是结束最优方案图1运输问题求解思路图第2页,共35页,2024年2月25日,星期天
二、初始基本可行解的确定
例2:甲、乙两个煤矿供应A、B、C三个城市用煤,各煤矿产量及各城市需煤量、各煤矿到各城市的运输单价见表所示,求使总运输费用最少的调运方案。第3页,共35页,2024年2月25日,星期天例题有关信息表450200150100
日销量(需求量)250756580
乙200100
7090
甲
日产量(供应量)CBA运距城市煤矿第4页,共35页,2024年2月25日,星期天例题数学模型第5页,共35页,2024年2月25日,星期天
(1)最小元素法:从运价最小的格开始,在格内的标上允许取得的最大数。然后按运价从小到大顺序填数。若某行(列)的产量(销量)已满足,则把该行(列)的其他格划去。如此进行下去,直至得到一个基本可行解。第6页,共35页,2024年2月25日,星期天调销地运量产地
B1B2B3
产量A190
X1170
X12
100
X13200
A280
X2165
X2275
X23250
销量
100
150
200
450
用最小元素法确定初始调运方案
150100100100100100100第7页,共35页,2024年2月25日,星期天
得到初始调运方案为:
x11=100,x13=100,x22=150,x23=100
第8页,共35页,2024年2月25日,星期天(2)西北角法不是优先考虑具有最小单位运价的供销业务,而是优先满足运输表中西北角(左上角)上空格的供销要求第9页,共35页,2024年2月25日,星期天调销地运量产地
B1B2B3
产量A190
X1170
X12
100
X13200
A280
X21
65
X2275
X23250
销量
100
150
200
450
用西北角法确定初始调运方案
100100100
5050200200第10页,共35页,2024年2月25日,星期天
得到初始调运方案为:
x11=100,x12=100,x22=50,x23=200
第11页,共35页,2024年2月25日,星期天三、最优性检验根据最小元素法或西北角法求得运输问题的初始基可行解之后,按照表上作业法的第二步,下面需对这个解进行最优性判别,看它是否为本运输问题的最优解.第12页,共35页,2024年2月25日,星期天1、闭回路法思路:要判定运输问题的初始基可行解是否为最优解,可仿照一般单纯形法,检验这个解的各非基变量(对应于运输表中的空格)的检验数。检验数:运输问题中非基变量(对应于空格)的检验数定义为给某空格增加单位运量导致总费用的增加量。如果有某空格(Ai、Bj)的检验数为负,说明将Xij变为基变量将使运输费用减少,故当前这个解不是最优解。若所有空格的检验数全为非负,则不管怎样变换,均不能使运输费用降低,即目标函数值已无法改进,这个解就是最优解。第13页,共35页,2024年2月25日,星期天闭回路:在给出的调运方案的运输表上,从一个空格(非基变量)出发,沿水平或垂直方向前进,只有碰到代表基变量的数字格才能向左或向右转90°继续前进,直至最终回到初始空格而形成的一条回路。从每一空格出发,一定可以找到一条且只存在唯一一条闭回路。第14页,共35页,2024年2月25日,星期天以xij空格为第一个奇数顶点,沿闭回路的顺(或逆)时针方向前进,对闭回路上的每个折点依次编号;非基变量xij的检验数:现在,在用最小元素法确定例2初始调运方案的基础上,计算非基变量X12的检验数:=(闭回路上奇数次顶点运距或运价之和)-(闭回路上偶数次顶点运距或运价之和)第15页,共35页,2024年2月25日,星期天调销地运量产地
B1B2B3
产量A190
X1170
X12
100
X13200
A280
X2165
X2275
X23250
销量
100
150
200
450100100100150初始调运方案中以X12(X21)为起点的闭回路第16页,共35页,2024年2月25日,星期天非基变量X12的检验数:非基变量X21的检验数:
=(c12+c23)-(c13+c22)
=70+75-(100+65)=-20,=(c21+c13)-(c11+c23)=80+100-(90+75)=15。经济含义:在保持产销平衡的条件下,该非基变量增加一个单位运量而成为基变量时目标函数值的变化量。第17页,共35页,2024年2月25日,星期天2、对偶变量法(位势法)检验数公式:
分别表示前m个约束等式对应的对偶变量;分别表示后n个约束等式对应的对偶变量。第18页,共35页,2024年2月25日,星期天初始调运方案对偶变量对应表
调销地运量产地
B1B2B3产量A190
X1170
X12
100
X13200
A280
X2165
X2275
X23250
销量
100
150
200
450对偶变量vjv1v2v3100100100150对偶变量
uiu1u2第19页,共35页,2024年2月25日,星期天
以初始调运方案为例,设置对偶变量和,然后构造下面的方程组:第20页,共35页,2024年2月25日,星期天
在式中,令u1=0,则可解得v1=90,v3=100,u2=-25,v2=90,于是σ12=c12-(u1+v2)=70-(0+90)=-20σ21=c21-(u2+v1)=80-(-25+90)=15与前面用闭回路法求得的结果相同。第21页,共35页,2024年2月25日,星期天方程组的特点:
方程个数是m+n-1=2+3-1=4个,对偶变量共有m+n=2+3=5。
初始方案的每一个基变量xij对应一个方程——-—所在行和列对应的对偶变量之和等于该基变量对应的运距(或运价):ui+vj=cij;
方程组恰有一个自由变量,可以证明方程组中任意一个变量均可取作自由变量。这个时候方程的解可以称为位势。第22页,共35页,2024年2月25日,星期天
在式中,令u1=0,则可解得v1=90,v3=100,u2=-25,v2=90,于是σ12=c12-(u1+v2)=70-(0+90)=-20σ21=c21-(u2+v1)=80-(-25+90)=15与前面用闭回路法求得的结果相同。第23页,共35页,2024年2月25日,星期天位势法计算非基变量xij检验数的公式σij=cij-(ui+vj)=(闭回路上奇数次顶点运距或运价之和)-(闭回路上偶数次顶点运距或运价之和)闭回路法计算非基变量xij检验数的公式:复习比较检验数计算的两种方法思考:试解释位势变量的含义(提示:写出运输问题的对偶问题)第24页,共35页,2024年2月25日,星期天四、解的改进如检验出初始解不是最优解,即某非基变量检验数为负,说明将这个非基变量变为基变量时运费会下降。根据表上作业法的第三步,需对初始方案进行改进。第25页,共35页,2024年2月25日,星期天(一)解改进的步骤为:1.(如存在多个非基变量的检验数为负时,以最小负检验数所在空格对应的变量)为换入变量,找出它在运输表中的闭回路;2.以这个空格为第一个奇数顶点,沿闭回路的顺(或逆)时针方向前进,对闭回路上的每个折点依次编号;第26页,共35页,2024年2月25日,星期天解的改进步骤续:3.在闭回路的所有偶数折点中,找出运输量最小的一个折点,以该格中的变量为换出变量;4.将闭回路上所有奇数折点的运输量都增加这一换出变量值,所有偶数折点处的运输量都减去这一数值,最终得出一个新的运输方案。对得出的新方案再进行最优性检验,如不是最优解,就重复以上步骤继续进行调整,一直到得出最优解为止。第27页,共35页,2024年2月25日,星期天调销地运量产地
B1B2B3
产量A190
X1170
X12
100
X13200
A280
X2165
X2275
X23250
销量
100
150
200
450100100100150++--因σ12=-20,画出以x12为起始变量的闭回路020050100第28页,共35页,2024年2月25日,星期天
计算调整量:ε=Min(100,150)=100。
按照下面的方法调整调运量:闭回路上,奇数次顶点的调运量加上ε,偶数次顶点的调运量减去ε;闭回路之外的变量调运量不变。
得到新的调运方案:第29页,共35页,2024年2月25日,星期天调销地运量产地
B1B2B3
产量A190
X1170
X12
100
X13200
A280
X2165
X2275
X23250
销量
100
150
200
45034250100100200
50重复上面的步骤,直至求出最优调运方案:第30页,共35页,2024年2月25日,星期天调销地运量产地
B1B2B3
产量A190
X1170
X12
100
X13200
A280
X2165
X2275
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 加油站一线三排全套资料
- 医疗机构改革方案
- 降钙素在感染病治疗中的应用
- 如何有效控制继发性高血压
- 医疗行业监管政策临床路径季度分析
- GLP在肿瘤治疗中的临床应用
- 环境卫生与寄生虫病:防治措施
- 2024年跨境电商行业现状及发展趋势研究
- 传染病防控健康行为知识竞赛
- 针灸治疗高血压的研究进展
- 苏教版四年级数学下册六 运算律第4课时 乘法的分配律(课件)
- 河南烟草公司招聘笔试题目
- 天津交通职业学院招聘考试题库2024
- 太平洋保险公司招聘线上测评题库
- 机场碳排放控制与减缓
- 银行柜员柜面营销案例分析报告
- 知识产权运用能力
- 伍德灯在细菌检测中的应用
- 应急疏散避难场所选址方法
- 建筑工程质量验收标准化培训课程
- 口腔种植护理病例汇报课件
评论
0/150
提交评论