机械优化设计课件 第5章 线性规划
36页1、开放 包容 求实 创新机械优化设计第五章 线性规划第五章 线性规划一.线性规划的基本概念二.求解线性规划的单纯形法三三. .初始基本可行解初始基本可行解第五章 线性规划 某厂生产甲、乙两种产品,已知:两种产品分别由两条生产线生产。第一条生产甲,每天最多生产9件,第二条生产乙,每天最多生产7件;该厂仅有工人24名,生产甲每件用2工日,生产乙每件用3工日;产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润?一)应用实例5-1 线性规划的基本概念日利润最大生产能力限制劳动力限制变量非负解: 设甲、乙两种产品的日产件数分别为s.t.第五章 线性规划5-1 线性规划的基本概念二)线性规划的一般形式s.t.特点: 1)为极小化问题; 2)约束取等号;3)限定系数非负; 4)变量非负.式中, 价值系数; 结构系数 限定系数第五章 线性规划5-1 线性规划的基本概念将数学模型化为标准型的方法1)将极大化问题化为极小化问题松弛变量(开关变量)(两边乘-1)4)将负的限定系数化为正值3)将任意变量化为非负变量2)将不等式约束变为等式约束:目标函数变号;第五章 线性规划5-1 线性
2、规划的基本概念s.t.化为标准型:第五章 线性规划5-1 线性规划的基本概念三)线性规划的基本概念s.t.1.线性规划的图解x2x10F=0F*=620(1.5,7)第五章 线性规划5-1 线性规划的基本概念2. 线性规划的基本概念1)可行解满足约束条件及非负条件的解。 (D内及其边界上的解) 2)基本解 使n-m个变量等于0,解约束方程 组(共有m个约束方程)所得的解。 基本解对应于约束边界的交点.x2x10F=0F*=-620(1.5,7)第五章 线性规划5-1 线性规划的基本概念3)基本可行解可行域中的基本解(即D的顶点)。 4)基本变量与非基本变量基本可行解中取零值的n-m个变量为非基本变量,取正 值为基本变量。s.t.第五章 线性规划5-1 线性规划的基本概念四)线性规划的基本性质1)可行域D为凸集,每个基本可行解对应于D上的一个顶点 ;2)只要可行域存在且封闭,则起码有一个基本可行解为最 优点;*)若最优点所在的边界线与等值线平行,则该边界线上 的点均为最优点;)若可行域不封闭,则可能有无界解。3)最优点可在D的顶点中寻找。第五章 线性规划5-1 线性规划的基本概念5-2
3、求解线性规划的单纯形法一.基本思路先取D的一个顶点作为初始点,由此出发朝 可使目标函数降低最快的方向依次经过一系 列的基本可行解,直至达到最优解.*1)需获得一个初始基本可行解;2)每次只更换一个非基本变量;3)保证下降性和可行性.第五章 线性规划二.计算实例s.t.1.初始基本可行解取x5,x6 为基本变量, 则有:0 0 0 0 4 5T5-2 求解线性规划的单纯形法第五章 线性规划2.第一次变换顶点(1)选取进基变量原则: 考虑下降性,且下降得最快判别数:假定x2进基, 则有 取相应的目标函数变化量:即5-2 求解线性规划的单纯形法第五章 线性规划写成一般形式 :最小,x3 应为进基变量 推论: 若线性规划的一个基本可行解的所有进基判别数均为非负,则该解为最优解.5-2 求解线性规划的单纯形法第五章 线性规划(2)确定离基变量原则:考虑可行性(该变量离基后,能使余下的基本变量为非负)判别数:由于)若取 (离基),则有 应取 为正且其值为最小者对应的基本变量离基.(可行)(不可行)若取 (离基),则有 5-2 求解线性规划的单纯形法第五章 线性规划)推论:若线性规划的所有离基判别数
4、均为负数时,则问题有无界解.最小,x6 应为离基变量 0 0 5/3 0 2/3 0T)因为 ,故 也必须大于0, 否则不满足可行性要求;5-2 求解线性规划的单纯形法第五章 线性规划进基3.第二次变换顶点去掉了(1)(2)1)确定进基变量(3 )(4 )5-2 求解线性规划的单纯形法第五章 线性规划2)确定离基变量离基(1 ) (2 )0 0 8/5 1/5 0 0T(3)(4)5-2 求解线性规划的单纯形法第五章 线性规划4. 第三次变换顶点1) 确定进基变量故 为最优点, 为最优值:0 0 8/5 1/5 0 0T5-2 求解线性规划的单纯形法第五章 线性规划三.用单纯形表求解线性规划例.用初等变换法求解解:增广矩阵:5-2 求解线性规划的单纯形法第五章 线性规划s.t.离基判别数进基判别数单纯形法实际上是解 一系列的线性方程组,也 可用初等变换方法列表求 解.但需加入判别数的计 算.4 42 21 12 23 35 5基变量基变量x x1 1x x2 2x x3 3x x4 4x x5 5x x6 63 3x x5 51 11 12 24 41 10 04 42 25 5x x
《机械优化设计课件 第5章 线性规划》由会员杨****分享,可在线阅读,更多相关《机械优化设计课件 第5章 线性规划》请在金锄头文库上搜索。
金属材料与热处理课程总复习课件(ppt)
金属切削原理课件 第8章 工件材料切削加工性
Java EE 课程ppt课件 第13章 Spring基础
Java EE 课程ppt课件 第6章 Struts 2的其他应用
Java EE 课程ppt课件 第2章 Struts 2基础
制作精良优美的高质量PPT模版 紫色主色调简洁风
制作精良优美的高质量PPT模版 数码风格论文答辩模版
制作精良优美的高质量PPT模版 蓝白主色调简洁风
制作精良优美的高质量PPT模版 答辩报告毕业设计 蓝色主色调
弹性力学与有限元教学课件第6.2章 ANSYS软件的应用
机械优化设计课件 绪论第1章 优化设计概述
金属切削原理课件 第9章 切削液
制作精良优美的高质量PPT模版 枣红色 毕业答辩论文模版
制作精良优美的高质量PPT模版 论文答辩 星空背景简洁风
制作精良优美的高质量PPT模版 毕业实习答辩 灰色风格
制作精良的论文答辩PPT模版 橙色主色调
艺术花色文艺风ppt模板
数值分析 第八章 常微分方程数值解法
郑州大学概率论与数理统计课程 第8章 假设检验part2
郑州大学概率论与数理统计课程 第4.4章 大数定律
2022-11-24 46页
2022-11-24 39页
2021-09-18 51页
2021-09-18 72页
2021-09-18 69页
2021-09-18 136页
2021-09-18 56页
2021-09-18 50页
2021-09-18 88页
2021-09-18 59页