![第5章线性规划_第1页](http://file.renrendoc.com/FileRoot1/2018-8/3/c0b731fd-0804-4620-a257-34d114e71541/c0b731fd-0804-4620-a257-34d114e715411.gif)
![第5章线性规划_第2页](http://file.renrendoc.com/FileRoot1/2018-8/3/c0b731fd-0804-4620-a257-34d114e71541/c0b731fd-0804-4620-a257-34d114e715412.gif)
![第5章线性规划_第3页](http://file.renrendoc.com/FileRoot1/2018-8/3/c0b731fd-0804-4620-a257-34d114e71541/c0b731fd-0804-4620-a257-34d114e715413.gif)
![第5章线性规划_第4页](http://file.renrendoc.com/FileRoot1/2018-8/3/c0b731fd-0804-4620-a257-34d114e71541/c0b731fd-0804-4620-a257-34d114e715414.gif)
![第5章线性规划_第5页](http://file.renrendoc.com/FileRoot1/2018-8/3/c0b731fd-0804-4620-a257-34d114e71541/c0b731fd-0804-4620-a257-34d114e715415.gif)
已阅读5页,还剩52页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第五章 线性规划一 .线性规划的基本概念二 .基本可行解的转换三 .求解线性规划的单纯形法Date 1某厂生产甲、乙两种产品,已知: 两种产品分别由两条生产线生产。第一条生产甲,每天最多生产 9件,第二条生产乙,每天最多生产 7件; 该厂仅有工人 24名,生产甲每件用 2工日,生产乙每件用 3工日; 产品甲、乙的单件利润分别为40元和 80元。问工厂如何组织生产才能获得最大利润?一)应用实例5-1 线性规划的基本概念* 2日 利润最大生产能力限制劳动力限制变量非负解 : 设甲、乙两种产品的日产件数分别为s.t.Date 3二 )线性规划的一般形式s.t.特点 : 1)为极小化问题 ; 2)约束取等号 ;3)限定系数非负 ; 4)变量非负 .式 中, 价值系数; 结构系数 限定系数Date 4 将数学模型化为标准型的方法1)将极大化问题化为极小化问题 松弛变量(开关变量)(两边乘 -1)4)将负的限定系数化为正值3)将任意变量化为非负变量2)将不等式约束变为等式约束: 目标函数变号;Date 5s.t.化为标准型 :Date 6三)线性规划的基本概念s.t.1.线性规划的图解 x2x10F=0F*=620(1.5,7)Date 72. 线性规划的基本概念1)可行解 满足约束条件及非负条件的解。( D内及其边界上的解)2)基本解 使 n-m个变量等于 0,解约束方程组 (共有 m个约束方程 )所得的解。基本解对应于约束边界的交点 .3)基本可行解 可行域中的基本解 (即 D的顶点)。4)基本变量与非基本变量预先取为零值的 n-m个变量为非基本变量,其余 m个为基本变量。x2x10F=0F*=-620(1.5,7)s.t.Date 8举例Date 9四)线性规划的基本性质1)可行域 D为凸集,每个基本可行解对应于 D上的一个顶点;2)只要可行域存在且封闭,则起码有一个基本可行解为最优点;* )若最优点所在的边界线与等值线平行,则该边界线上的点均为最优点; )若可行域不封闭,则可能有无界解。3)最优点可在 D的顶点中寻找。Date 105-2 基本可行解的转换Date 11Date 12Date 13Date 14Date 15Date 16Date 17Date 18Date 19Date 205-3 求解线性规划的单纯形法一 .基本思路先 取 D的一个顶点作为初始点 ,由此出发朝可使目标函数降低最快的方向依次经过一系列的基本可行解 ,直至达到最优解 .*1)需获得一个初始基本可行解 ;2)每次只更换一个非基本变量 ;3)保证下降性和可行性 .Date 21二 .计算实例s.t.1.初始基本可行解取 x5,x6 为 基本变量 , 则有 :0 0 0 0 4 5TDate 222.第一次变换顶点(1)选取进基变量 原则 : 考虑下降性 ,且下降得最快 判别数 : 假定 x2进基 , 则有取相应的目标函数变化量 :即Date 23写成 一般形式:最小 ,x3 应为进基变量推论 : 若线性规划的一个基本可行解的所有进基判别数均为非负 ,则该解为最优解 .Date 24(2)确定离基变量 原则 :考虑可行性 (该变量离基后 ,能使余下的基本变量为非负 ) 判别数 :由于) 若取 (离基 ),则有 应 取 为正且其值为最小者对应的基本变量离基 .(可行 )(不可行) 若取 (离基 ),则有 Date 25) 推论 :若线性规划的的所有离基判别数均为负数时 ,则问题有无界解.最小 ,x6 应为离基变量0 0 5/3 0 2/3 0T* ) 因为 ,故 也必须大于 0, 否则不满足可行性要求 ;Date 26进基3.第二次变换顶点去掉了(1)(2)1)确定进基变量(3)(4)Date 272)确定离基变量离基(1)(2)0 0 8/5 1/5 0 0T(3)(4)Date 284. 第三次变换顶点1)
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 完整美容院入股协议书共
- 水果农产品购销合同模板
- 养殖牛场出租转让合同范本
- 种苗购买协议
- 企业贷款合同
- 传媒公司劳动合同
- 员工车辆私车公用协议书
- 茶楼茶宴餐厅租赁合同
- 全新厂房装修合同简单合同
- 商铺合同补充协议书范本
- 2024年重庆市中考数学试卷真题B卷(含答案逐题解析)
- 广西壮族自治区南宁市西乡塘区2022-2023学年二年级下学期期末语文试卷
- 湖南省岳阳县一中、汨罗市一中2025届物理高一下期末学业水平测试试题含解析
- 2024年度全国社会工作者《社会工作实务》备考真题带答案
- 浙江省杭州市2022-2023学年一年级下学期语文期末试卷(含答案)3
- 燃烧学智慧树知到期末考试答案章节答案2024年长安大学
- 2024年杭州市上城区部分事业单位公开招聘19名工作人员历年高频考题难、易错点模拟试题(共500题)附带答案详解
- 软件测试师考试题库三
- 文献学概论智慧树知到期末考试答案章节答案2024年湖北师范大学
- 江西省宜春实验中学2024届中考生物对点突破模拟试卷含解析
- 三年级下数学计算比赛
评论
0/150
提交评论