运筹学 线性规划 单纯形法
更新时间:2023-08-17 20:50:01 阅读量: 资格考试认证 文档下载
- 运筹学推荐度:
- 相关推荐
运筹学 线性规划 单纯形法
第一章 线性规划问题及单纯形法线性规划问题及其数学模型 图解法 单纯形法原理 单纯形法计算步骤 单纯形法的进一步讨论
运筹学 线性规划 单纯形法
第五节
单纯形法的进一步讨论
本节重点: 本节重点:● 大 M法 ●两阶段法 ●解的存在情况判别
运筹学 线性规划 单纯形法
一, 人工变量的引入及其解法当约束条件为" 1. 当约束条件为"≥"型,引入剩余变量和人工变 量 由于所添加的剩余变量的技术系数为 由于所添加的剩余变量的技术系数为1,不能作 为初始可行基变量,为此引入一个人为的变量(注意, 为初始可行基变量,为此引入一个人为的变量(注意, 此时约束条件已为" ),以便取得初始基变量 以便取得初始基变量, 此时约束条件已为"="型),以便取得初始基变量, 故称为人工变量. 故称为人工变量. 人工变量 由于人工变量在原问题的解中是不能存在的, 由于人工变量在原问题的解中是不能存在的,应 尽快被迭代出去, 尽快被迭代出去,因此人工变量在目标函数中对应的 价值系数应具有惩罚性,称为罚系数 罚系数. 价值系数应具有惩罚性,称为罚系数.罚系数的取值 视解法而定 两种方法: 两种方法:大M法和二阶段法.
运筹学 线性规划 单纯形法
2. 大M法的求解过程 法的求解过程例1
人工变量添加前已为等式, 人工变量添加前已为等式, 其取值必须为0; 称为 其取值必须为 ;-M称为 惩罚因子" "惩罚因子"
运筹学 线性规划 单纯形法
例1的单纯型表迭代过程 的单纯型表迭代过程Cj CB X B b M x6 6 7 x3 4 10 x1 (2) 1 8 x2 1 1 7 x3 0 10
0 x4 1 0M
c j z j→
2M3 M1
0 x5 0 17
M x6 1 00
θ (3) 4
10 x1 7 x3
3 1
1 00
1/2 (1/2)1/2
0 10
c j z j →
1/2 0 1/2 13/2
1/2 1/2
6 (2)
7 M+3/2
10 x1 8 x2
2 2
1 00
0 10
c j z j→
1 2 1
1 12
1 26
M+2
1 1
答:最优解为 x1=2, x2=2, x3=0, OBJ=36
运筹学 线性规划 单纯形法
3.大 法的一些说明 3.大M法的一些说明(1)人工变量被迭代出去后一般就不会再成为基变量 法实质上与原单纯形法一样, (2)大M法实质上与原单纯形法一样,M 可看成一个 很大的常数 当检验数都满足最优条件, (3)当检验数都满足最优条件,但基变量中仍有人工 变量, 变量,说明原线性规划问题无可行解 法手算不会遇到麻烦, (4)大M法手算不会遇到麻烦,但计算机计算很容易产 生误差,因此提出了二阶段法. 生误差,因此提出了二阶段法.
运筹学 线性规划 单纯形法
4.二阶段法的求解过程 4.二阶段法的求解过程(1)第一阶段的任务是将人工变量尽快迭代出去,从而找 )第一阶段的任务是将人工变量尽快迭代出去, 到一个没有人工变量的基础可行解 (2)若第一阶段结束时,人工变量仍在基变量中,则原问 )若第一阶段结束时,人工变量仍在基变量中, 题无解( ) 题无解(3)第二阶段以第一阶段得到的基础可行解为初始 解,采用原单纯形法求解 (4)为了简化计算,在第一阶段重新定义价值系数
如下: )为了简化计算,在第一阶段重新定义价值系数如下:
运筹学 线性规划 单纯形法
用二阶段法求解例1的 用二阶段法求解例 的第一阶段
运筹学 线性规划 单纯形法
人工变量x 不在基变量中, 人工变量 6不在基变量中,从最终单纯形表中去除人工 变量,更换目标函数为原问题的目标函数, 变量,更换目标函数为原问题的目标函数,继续用单纯 形表计算. 形表计算.
运筹学 线性规划 单纯形法
用二阶段法求解例1的 用二阶段法求解例 的第二阶段
运筹学 线性规划 单纯形法
LP解的进一步讨论 二,LP解的进一步讨论 1.关于退化问题 1.关于退化问题当按照最小比值θ确定换出基变量时, 当按照最小比值θ确定换出基变量时,存在多个相同的最 最小比值 小比值, 小比值,从而使下一个表的基可行解中出现一个或多个基 变量等于零的退化解. 变量等于零的退化解. 退化的严重性在于可能导致死循环,克服死循环的方法有 退化的严重性在于可能导致死循环, 字典序" Bland规则:(1 规则:( "字典序"法,即Bland规则:(1)当按照最大检验数 确定换入变量时,存在多个相同的最大检验数, σj≥0确定换入变量时,存在多个相同的最大检验数,始终 选取下标值为最小的变量作为换入变量;( ;(2 当按照最 选取下标值为最小的变量作为换入变量;(2)当按照最 小比值θ确定换出基变量时,存在多个相同的最小比值, 小比值θ确定换出基变量时,存在多个相同的最小比值, 始终选取下标值为最小的变量作为换出变量. 始终选取下标值为最小的变量作为换出变量.
运筹学 线性规划 单纯形法
例2 m Z = 3x1 + 4x2 ax x1 + x2 ≤ 40 2x + x ≤ 60 1 2 s.t. x1 x2 = 0 x1, x2 ≥ 0
运筹学 线性规划 单纯形法
.关于多重解问题 2 .关于多重解问题最优单纯形表中有非基变量的检验数为0 最优单纯形表中有非基变量的检验数为0 非基变量的检验数为
运筹学 线性规划 单纯形法
例3 的单纯型表及其迭代过程
运筹学 线性规划 单纯形法
4 .关于无可行解问题 关于无可行解问题单纯形表达到最优解检验条件时, 单纯形表达到最优解检验条件时,人工变量仍在基 变量中
运筹学 线性规划 单纯形法
例4第一阶段的单纯型表 第一阶段的单纯型表
运筹学 线性规划 单纯形法
三,单纯形法小结 如下所示: 如下所示:
运筹学 线性规划 单纯形法
1. 线性规划模型及其变换, , 根据实际问题给出数学模型,进行标准化,列出初始单纯型表, 根据实际问题给出数学模型,进行标准化,列出初始单纯型表,见表 xj ≥ 0 不需要处理 变 xj ≤ 0 令 xj′ =-xj; x j ′≥ 0 量 xj 无约束 令 xj=xj′ -xj〃 ; xj′ , xj〃≥ 0 b>0 约 不需要处理 b<0 约束条件两端同乘-1 束 约束条件两端同乘 = 条 加人工变量 ≥ 减去剩余, 件 减去剩余,加人工变量 ≤ 加松弛变量 Max z 目 不需要处理 Min z 标 令 z′=-z 求 Max z′ 0 函 加入变量 松弛变量 人工变量 -M 数 的系数 分别以每一个约束条件中松弛变量或人工变量为基变量, 分别以每一个约束条件中松弛变量或人工变量为基变量, 列出初始单纯型
表
运筹学 线性规划 单纯形法
2.线性规划解的情况 线性规划解的情况解除有唯一最优解的情况外,还有如下几种情况: 解除有唯一最优解的情况外,还有如下几种情况: 唯一最优解的情况外无界解:(1) 可行区域不闭合 约束条件有问题 :(1 可行区域不闭合(约束条件有问题 约束条件有问题) 无界解:( 对应的列中所有a (2)单纯形中存在某入基变量 xk 对应的列中所有 ik≤0 ) 退化解: 退化问题的原因很复杂, 退化解:(1) 退化问题的原因很复杂,当原问题存在平衡约束时 (2)当单纯型表中同时有多个基变量可选作出变量时 ) (3)退化的严重性在于可能导致死循环 ) 无穷多解: (1)多个基础可行解都是最优解,这些解在同一个超平面上, 多个基础可行解都是最优解,这些解在同一个超平面上, 无穷多解: 且该平面与目标函数等值面平行 (2)最优单纯形表中有非基变量的检验数为0 最优单纯形表中有非基变量的检验数为 (3)最优解的线性组合仍是最优解,即 X=aX1+bX2,a+b=1 最优解的线性组合仍是最优解, 无可行解: (1) 约束条件互相矛盾,无可行域 约束条件互相矛盾, 无可行解: (2)单纯型表达到最优解检验条件时,人工变量仍在基 单纯型表达到最优解检验条件时, 变量中
运筹学 线性规划 单纯形法
添加松弛变量, 添加松弛变量 , 人工变 量 列出初始单纯形表 计算各列检验数б 计算各列检验数бj
3.对目标函数求极大值标准型线性规 对目标函数求极大值标准型线性规 划问题, 划问题,单纯形法计算步骤的框图否 唯一最优解
所有б 所有бj≤0 否 对任一б 对任一бj≥0 有aik≤0 否 令бk=max{бj} б
是
基变量中 有非零的 人工变量是
否
某非基变 量检验数 为零 无穷多最优解
无可行解 是 无界解
xk为换入变量
1.xk替换 l . 替换x 2.列出新的单纯形表 . 对主元素行( 行 ① 对主元素行(第l行)
对 所 有 aik>0 计 算 θi=bi/aik 令θl=min{θi} 个基变量为换出变 第 l 个基变量 为换出变 量,alk为主元素
′ bl′ = bl / a lk , a lj = a lj / a lk②其它行i(i≠l) 其它行 ( )
′ bi′ = bi aik bl / alk , aij = aij aik alj / alk
运筹学 线性规划 单纯形法
例1:某糖果厂用原材料A,B,C加工成三种不同牌号的糖 :某糖果厂用原材料 , , 加工成三种不同牌号的糖 果甲, 已知各种牌号的糖果中A, , 含量 含量, 果甲,乙,丙.已知各种牌号的糖果中 ,B,C含量,原 料成本,各种原料每月限制用量, 料成本,各种原料每月限制用量,三种牌号糖果的单位加 工费及售价如下表所示. 工费及售价如下表所示.问该厂每月生产这三种牌号糖果 多少kg,使该厂获利最大.试建立该问题的LP的数学模型 的数学模型. 多少 ,使该厂获利最大.试建立该问题的 的数学模型.甲 A B C 加工费 元/kg 售价 元/kg ≤20% 0.5 3.4 ≤50% 0.4 2.85 ≤60% 0.3 2.25 ≥60% 乙 ≥30% 丙 原料
售价 元/kg 2 1.5 1 每月限量 kg 2000 2500 1200
正在阅读:
运筹学 线性规划 单纯形法08-17
中考英语真题分类汇编:题型7书面表达专项训练五事物介绍类(含解析)12-28
2018年婴儿餐椅市场现状与发展趋势预测 (目录)_ss04-29
建筑工程工程量清单计价(A.B.C)06-15
Photoshop超强抠图合成创意实例07-20
医疗队员抗疫个人先进事迹心得体会范文五篇03-24
恽代英110-01
演马庄矿井下钻场视频监控系统 技术要求05-21
党支部工作基本知识测试题04-14
大学生创业导论 姚凯版 课后习题答案07-28
- 梳理《史记》素材,为作文添彩
- 2012呼和浩特驾照模拟考试B2车型试题
- 关于全面推进施工现场标准化管理实施的通知(红头文件)
- 江西省房屋建筑和市政基础设施工程施工招标文件范本
- 律师与公证制度第2阶段练习题
- 2019-2020年最新人教版PEP初三英语九年级上册精编单元练习unit6训练测试卷内含听力文件及听力原文
- 小升初数学模拟试卷(十四) 北京版 Word版,含答案
- 认识创新思维特点 探讨创新教育方法-精选教育文档
- 00266 自考 社会心理学一(复习题大全)
- 多媒体在语文教学中的运用效果
- 派出所派出所教导员述职报告
- 低压电工作业考试B
- 18秋福建师范大学《管理心理学》在线作业一4
- 中国铝业公司职工违规违纪处分暂行规定
- 13建筑力学复习题(答案)
- 2008年新密市师德征文获奖名单 - 图文
- 保安员培训考试题库(附答案)
- 银川市贺兰一中一模试卷
- 2011—2017年新课标全国卷2文科数学试题分类汇编 - 1.集合
- 湖北省襄阳市第五中学届高三生物五月模拟考试试题一
- 线性规划
- 运筹学
- 单纯
- 过程质量提升新闻稿
- 霍尔效应测磁感应强度
- 2015江西银行校园招聘银行校园招聘考试用书详解
- 《后砌墙与剪力墙接缝处抹灰开裂修复方案1》
- 结合自身工作和生活实际,谈谈如何让把握好情绪
- 初二上册历史导言课
- 武大分子生物学考研历年真题
- ATA100 中英文对照版
- 浅谈提高钢板桩围堰合拢精度
- 济南电子路考完整版
- 安全隐患整改通知书
- “十三五”重点项目-木制楼梯生产建设项目可行性研究报告
- 熊彼特的创新理论
- 特色学校古诗文诵读
- 平年闰年
- 六艺贯通:“互联网”视角下的民族技艺传承与创新——刘正宏(北京电子科技职业技术学
- 广东省药品交易中心药品合同管理操作指引-配送方
- 五六年级体育_ABC教育网
- 《关于当前干熄焦技术推广难的症结问题及改进措施的探讨》
- 《中学教育心理学》第十一章__心理健康教育