已阅读5页,还剩6页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
p11-1,2.1 单纯形法原理,一、构造初始可行基, 1947年, 美国数学家丹捷格提出了求解线性规划的单纯形法.,1. 引入附加变量, 化数学模型为标准型; 2. 若A中含有m阶单位阵, 则该单位阵即为一个初始可行基; 否则, 须引入人工变量, 以构成初始可行基; 3. 目标函数中, 附加变量的系数为0, 人工变量的系数为M (很大的正数, 称为罚因子)大M法或罚函数法., 以求解下述线性规划 问题为例,p11-2,2.1 单纯形法原理,一、构造初始可行基,1. 引入附加变量, 化数学模型为标准型; 2. 若A中含有m阶单位阵, 则该单位阵即为一个初始可行基; 否则, 须引入人工变量, 以构成初始可行基; 3. 目标函数中, 附加变量的系数为0, 人工变量的系数为M (很大的正数, 称为罚因子)大M法或罚函数法.,二、求出一个基本可行解,1. 用非基变量表示基变量和目标函数; 2. 求出一个基本可行解和相应的函数值;,p11-3,2.1 单纯形法原理,一、构造初始可行基,二、求出一个基本可行解,1. 用非基变量表示基变量和目标函数; 2. 求出一个基本可行解和相应的函数值;,三、最优性检验判断基本可行解是否为最优解,1. 最优性检验的依据检验数 用非基变量表示目标函数之后, 目标函数中各非基变量 的系数即为非基变量的检验数. 基变量的检验数为0.,2. 最优解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 且人工变量=0, 则该基本可行解为最优解.,p11-4,2.1 单纯形法原理,一、构造初始可行基,二、求出一个基本可行解,三、最优性检验判断基本可行解是否为最优解,1. 最优性检验的依据检验数,2. 最优解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 且人工变量=0, 则该基本可行解为最优解.,3. 无穷多最优解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 又存在某个非基变量的检验数=0, 且人工变量=0, 则该线性 规划问题有无穷多最优解.,p11-5,2.1 单纯形法原理,一、构造初始可行基,二、求出一个基本可行解,三、最优性检验判断基本可行解是否为最优解,2. 最优解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 且人工变量=0, 则该基本可行解为最优解.,3. 无穷多最优解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 又存在某个非基变量的检验数=0, 且人工变量=0, 则该线性 规划问题有无穷多最优解.,4. 无可行解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 但某个人工变量0, 则该线性规划问题无可行解.,p11-6,2.1 单纯形法原理,三、最优性检验判断基本可行解是否为最优解,3. 无穷多最优解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 又存在某个非基变量的检验数=0, 且人工变量=0, 则该线性 规划问题有无穷多最优解.,4. 无可行解判别定理 在极小化问题中, 对于某个基本可行解, 若所有检验数0, 但某个人工变量0, 则该线性规划问题无可行解.,5. 无有限最优解(无界解)判别定理 在极小化问题中, 对于某个基本可行解, 若存在某个非基变 量的检验数0, 但相应的列中没有正元素, 且人工变量=0, 则该线性规划问题无有限最优解(具有无界解).,p11-7,2.1 单纯形法原理,一、构造初始可行基,二、求出一个基本可行解,三、最优性检验判断基本可行解是否为最优解,2. 最优解判别定理,3. 无穷多最优解判别定理,4. 无可行解判别定理,四、基变换,1. 换入变量的确定 负检验数中的小者所对应的非基变量为换入变量. 2. 换出变量的确定 按最小非负比值原则确定换出变量.,p11-8,2.2 单纯形法的表格形式,四、基变换,1. 换入变量的确定 负检验数中的小者所对应的非基变量为换入变量. 2. 换出变量的确定 按最小非负比值原则确定换出变量.,例 用大M法求解下述线性规划问题.,最优解为X*=(1, 2)T , 最优值为z*= -1,p11-9,2.3 大M法和两阶段法,一、两阶段法,1. 第一阶段: 判断原线性规划问题是否有可行解. 目标函数取全部人工变量之和. 若最小值为0, 则转入第二 阶段. 否则, 原线性规划问题无可行解. 2. 第二阶段: 求解原线性规划问题的最优解.,例 用两阶段法求解下述线性规划问题.,最优解为X*=(1, 2)T , 最优值为z*= 7,p11-10,2.4 退化问题,一、何谓退化,对
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 物流运作方案设计(2篇)
- 2023年温度校准仪表资金需求报告
- 过程控制及仪表-知到答案、智慧树答案
- 机关先进工作者个人事迹-总结报告模板
- 2024年汽缸垫项目投资申请报告代可行性研究报告
- 2024年软泡聚醚项目投资申请报告代可行性研究报告
- 2023年指示灯具:设备指示灯资金申请报告
- 2024年大型袋式除尘器项目资金需求报告代可行性研究报告
- 2023年医用超声仪器资金筹措计划书
- 2023年转子式海流计资金需求报告
- 夏季混凝土养护通知
- 紧急情况停产撤人措施
- 电气防火安全检测技术导则
- 物资消耗控制及节超奖惩办法
- GB∕T 40920-2021 皮革 色牢度试验 往复式摩擦色牢度
- CNC操作员培训内容
- 第二章----曲柄压力机ppt-2
- 临床科室绩效奖金二次分配办法
- 《红楼梦》71-75回阅读指导讲义.ppt
- 浅谈古典舞美学之形、神、气、韵
- (完整版)钢结构工程施工质量验收规范
评论
0/150
提交评论