欢迎来到三一文库! | 帮助中心 三一文库31doc.com 一个上传文档投稿赚钱的网站
三一文库
全部分类
  • 研究报告>
  • 工作总结>
  • 合同范本>
  • 心得体会>
  • 工作报告>
  • 党团相关>
  • 幼儿/小学教育>
  • 高等教育>
  • 经济/贸易/财会>
  • 建筑/环境>
  • 金融/证券>
  • 医学/心理学>
  • ImageVerifierCode 换一换
    首页 三一文库 > 资源分类 > PPT文档下载
     

    第二章线性规划.ppt

    • 资源ID:3119967       资源大小:648.52KB        全文页数:41页
    • 资源格式: PPT        下载积分:6
    快捷下载 游客一键下载
    会员登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录 QQ登录   微博登录  
    二维码
    微信扫一扫登录
    下载资源需要6
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    第二章线性规划.ppt

    第二章 线性规划,第一节 线性规划问题及其数学模型 第二节 线性规划问题的图解法 第三节 单纯形法 第四节 线性规划的对偶问题 第五节 线性规划在卫生管理中的应用,第一节 线性规划问题及其数学模型,一、线性规划问题的特征和建模的步骤,二、线性规划问题的数学模型及一般形式,三、线性规划问题的标准形式,(一)线性规划问题的标准形式,(二)书写形式,(三)标准形式的转化,2、任务给定,如何合理地计划、统筹安排 以最少的资源完成它,1、资源给定,如何合理地计划、统筹安排 才能发挥最大的效益;,一、线性规划问题的特征和建模的步骤,(一) 线性规划研究的内容,(三)都有一个目标要求,并且这个目标可以表示为决策变量的线性函数(称为目标函数)。,(一)可用一组变量(x1,x2 , xn)(称之为决策变量)来表示问题的方案,正常要求这组变量的取值是非负的,称为非负约束;,(二)存在某种限制条件,这些限制条件都可以用线性等式或不等式来表示。(这些等式或不等式称之为规划问题的约束条件方程式),(二) 线性规划问题的共同特征,(三) 建立模型的三个步骤, 确定一组变量(决策变量); 表示出一定的限制条件; 写出目标函数。,Max ( Min ) Z = c1 x1 + c2 x2 + + cn xn,约束条件:,目标函数:,二、线性规划问题的数学模型及一般形式,第二节 线性规划问题的图解法,一 、图解法解极大化问题 二、 图解法求解极小化问题 三、 线性规划模型的解的各种情况 四、 解法的优点及局限性,一 、用图解法解极大化问题,例1MaxZ 60x 50y 2x 4y 80 3x 2y 60 x, y 0,(1) 以 x、y 作为坐标轴,建立平面直角坐标系,根据 x、y 非负的约束,可行解区域位于坐标图的第一象限(见图(a),1图示全部约束条件, 确定可行解区域,(2)用等式约束代替非等 式约束,画出直线 2x4y80 3x2y60 (见图(b),(3)根据不等式约束 2x4y 80 3x2y 60 确定可行解区域 (见图(c),( 1)等直线法:把目标函数 Z60x50y 看成是随着Z的取值不同而产生的一族直线。令目标函数值分别为0、600、1200作平行线族(图(2),从图中可见,Z值越高,目标函数直线离原点越远。所以,寻找最优解问题可归结为:找出离原点最远的一条直线与可行解集的交点。,2从可行解中找出最优解,(1)等直线法 (2)试算法,(2)试算法:,(a)线性规划的可行域是凸多边形或凸集; (b)线性规划的最优解如果存在,必然在 可行解集的某个顶点上达到。,* 试算法是根据下面线性规划解的性质而得出的一种算法:,* 根据线性规划解的性质,先求出可行解集各顶点的坐标,然后试算目标函数之值,使目标函数达到极值的解,即为最优解,(见下面表13),表13 例1试算结果,最优解为(x,y)(10,15) 最优值为 ZMax 1350,二、 图解法求解极小化问题,例 MinZ 50x 80y 4x + 10y 40 10x 5y 50 35x + 35y 245 x, y 0,解: 1、图示全部约束条件, 确定可行解区域,2可行解中找出最优解 (1)用等直线法求最优解。本例是极小值问题,因此目标函数值取离原点尽可能近的等直线的值(见图(4)。通过 p2 点的等直线离原点最近, p2 点的坐标既满足全部约束条件又能使目标函数取得最小值, 故为最优解。,(2)用试算法求最优解(见表14),表1-4 例2试算结果,最优解为(x,y)(5,2) 最优值为 ZMin 410,三、线性规划模型的解的各种情况,例3,解:在本例中,由于目标函数(Z2x4y)的等直线与约束条件(x2y 8)的直线相平行,故最优解同时在两个顶点上达到。则在此两顶点连线上的任何一点都是最优解,即有无限多个最优解。,从图(6)可见,本 例的可行域无上界,目 标函数的值可趋于无穷 大。在这种情况下无法 确定最优解。,解:,例4,从图(7)可以看出, 本题的可行域是一个空集,因此无可行解。这是由于本题中包括了相互矛盾的约束条件的缘故。,解:,例5,线性规划问题解的几种情况,(1)有唯一的最优解。这时最优解一定在可行域的 某个顶点达到; (2)有最优解,但不唯一。这时最优解一定充满一个线段,此线段是可行域的一条边; (3)有可行解,但没有最优解。这时可行域上的点能使目标函数趋向无穷大; (4)没有可行解(空集)。即线性规划问题是不可行的。,图解法的优点及局限性,图解法的局限性: 一般仅适用于只有两个变量的。对于三维以上的模型,约束条件表现为平面,这就难用图解法去求解了。,图解法的优点: 直观、形象,它容易使人具体地认识线性规划模型的求解过程。,线性规划的标准形有如下四个特点: 目标最大化、 约束为等式、 变量均非负、 右端项非负。,三、线性规划问题的标准形式,(一)线性规划问题的标准形式,(二)书写形式,1.简缩形式,2.矩阵形式 见教材 P12,二、线性规划模型的解,我们把满足约束条件(1-3)、(1-4)的解称为线性规划模型的可行解。当mn时,约束方程组(1-3)可以有无穷多个解。全部可行解的集合,称为可行域。 线性规划模型的最优解,就是指能满足(1-2),即能使目标函数达到最大值的可行解。,1线性规划的解,对应于最优解的目标函数之值,称为最优值。,三、单纯形法的基本原理 (一)典型方程组 见规划教材第二章把后面的片子都改成新的内容,第三节 单纯形法,一、线性规划问题的标准型 二、线性规划模型的解 (性质略,见P15),2线性规划标准形式的基、 基本解、基本可行解,我们称这个解为基本解,若这个解能同时满足线性规划模型的非负约束条件,则把这个基本解称为基本可行解。,基,基变量,非基变量,称变量 在约束方程组对应的系数列向量为线性规划模型的一个基。基对应的变量称为基变量,其它变量称为非基变量。即:,任取A中的3个线性无关列向量构成矩阵B,那么B为线性规划的一个基。如果B为单位矩阵,则称B为一个单位基。线性规划 的任一个基,总可以 通过线性方程组的变 换化成单位基。,一般形式:,对于线性规划的约束条件系数矩阵A,设B是A矩阵中的一 个非奇异(可逆)的子矩阵,则称B为线性规划的一个基。 任取A中的m个线性无关列向量构成矩阵B,那么B为线性规 划的一个基。如果B为单位矩阵,则称B为一个单位基。 称对应于基B的变量为基变量,而其它变量称为非基变量。,(1) 线性规划的基、基变量,(2) 基本解、基本可行解和可行基,对于线性规划问题,设矩阵B为一个基,令所有非基变量为零,可以得到m个关于基变量的线性方程,解这个线性方程组得到基变量的值。我们称这个解为一个基本解。若得到的基变量的值均非负,则称为基本可行解,同时称这个基B为可行基。,返回,第一步 建立平面直角坐标系 第二步 求满足约束条件的可行解区域 第三步 作目标函数的等值线簇,确定 目标函数值增加方向(或用等 值线法)。 第四步 从可行解区内找满足目标函数 的最优解。,1.两个变量的线性规划问题的图解法步骤,本次课小结,第二节 线性规划问题的图解法,2. 图解法的优点及局限性,线性规划问题解的几种情况,图解法的局限性:一般仅适用于只有两个变量的。对于三维以上的模型,约束条件表现为平面,这就难用图解法去求解了。,本次课小结,(1)有唯一的最优解; (2)有最优解,但不唯一; (3)有可行解,但没有最优解; (4)没有可行解(空集)。,图解法的优点:直观、形象,它容易使人具体地认识线性规划模型的求解过程。,一、线性规划问题的标准型(四个特点) 二、线性规划模型的解及有关概念,第三节 线性规划模型的解及有关概念,线性规划模型的解的概念: 可行解、可行域、最优解、 基本解、基本可行解。,2线性规划标准形式的基的概念: 基、单位基、可行基、 基变量、非基变量。,本次课小结,练 习,1思考题 (1)建立线性规划模型的三个步骤是什么? (2)两个变量的线性规划问题的图解法的一般步骤是什么? (3)求解线性规划问题时可能出现几种结果? (4)什么是线性规划的标准型?如何把一个非标准形式的线性规划问题转化成标准形式? (5)理解线性规划问题的可行解、基本解、基本可行解、最优解的概念。,练 习,2判断下列说法是否正确 (1)线性规划问题的最优解一定在可行域的顶点达到。 (2)线性规划的可行解集是凸集。 (3)如果一个线性规划问题有两个不同的最优解,则它有无穷多个最优解。 (4)如果一个线性规划问题有可行解,那么它必有最优解。,作 业,求解线性规划问题 (1)Max Z = 10 x1 +5 x2 3x1 +4x29 5x1+2x28 x1, x2 0 (2)Max Z = 2x1 +x2 3x1 +5x215 6x1+2x224 x1, x2 0,

    注意事项

    本文(第二章线性规划.ppt)为本站会员(本田雅阁)主动上传,三一文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一文库(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    经营许可证编号:宁ICP备18001539号-1

    三一文库
    收起
    展开