欢迎来到淘文阁 - 分享文档赚钱的网站! | 帮助中心 好文档才是您的得力助手!
淘文阁 - 分享文档赚钱的网站
全部分类
  • 研究报告>
  • 管理文献>
  • 标准材料>
  • 技术资料>
  • 教育专区>
  • 应用文书>
  • 生活休闲>
  • 考试试题>
  • pptx模板>
  • 工商注册>
  • 期刊短文>
  • 图片设计>
  • ImageVerifierCode 换一换

    运筹学之线性规划图解法.ppt

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

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

    运筹学之线性规划图解法.ppt

    11线性规划图解法 22第2章 线性规划图解法n n2.1 2.1 线性规划问题线性规划问题n n2.2 2.2 图解法图解法n n2.3 2.3 极点和最优解极点和最优解n n2.4 2.4 计算机求解计算机求解n n2.5 2.5 最小化问题最小化问题n n2.6 2.6 特例特例 332.1 线性规划问题n n 在一定的约束条件(限制条件)下,使得某一目标函数取得最大(或最小)值,当规划问题的目标函数与约束条件都是线性函数,便称为线性规划。n n Linear programming(LP)442.1 线性规划问题产品A 产品B资源限制劳动力设备原材料9434510360工时200台时300公斤单位产品利润(元)70 120w 例1:某厂生产两种产品,需要三种资源,已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表:生产计划问题 55n n 问题:如何安排生产计划,使得获利最多?问题:如何安排生产计划,使得获利最多?n n 步骤:步骤:1 1、确定决策变量:设生产、确定决策变量:设生产A A 产品 产品x1 1kgkg,B B 产品 产品x2 2kgkg2 2、确定目标函数:确定目标函数:maxZ=70X maxZ=70X1 1+120X+120X2 23 3、确定约束条件:确定约束条件:人力约束 人力约束 9 9X X1 1+4X+4X2 2360 360 设备约束 设备约束 4 4X X1 1+5X+5X2 2 200 200 原材料约束 原材料约束3 3X X1 1+10X+10X2 2 300 300 非负性约束 非负性约束X X1 10 X 0 X2 20 0 66 线性规划示意图maxZ=70X1+120X2 9X1+4X23604X1+5X2 2003X1+10X2 300 X10 X20 77标准袋 高档袋 资源限制切割印染缝合完成检查包装7/101/211/1015/62/31/4630小时600小时708小时135小时单位产品利润(美元)9 10例例22:高尔夫球袋:高尔夫球袋2.1 线性规划问题 882.1 线性规划问题n n决策变量决策变量n n目标函数目标函数n n约束条件约束条件n n设产品标准袋、高档袋分别生产设产品标准袋、高档袋分别生产X1X1、X2X2个个 n nObj:maxZ=9XObj:maxZ=9X1 1+10X+10X2 2 n nS.t.0.7XS.t.0.7X1 1+X+X2 2 630 630 n n 0.5X 0.5X1 1+0.83333X+0.83333X2 2 600 600 n n 1X 1X1 1+0.33333X+0.33333X2 2 708 708n n 0.1X 0.1X1 1+0.25X+0.25X2 2 135 135n n X X1 10 0 n n X X2 200 992.1 线性规划问题一般形式n n 目标函数:Objective Function Max(min)z=c1 1x1 1+c2 2x2 2+cn nxn nn n 约束条件:Constraint a11 11x1 1+a12 12x2 2+a1n 1nxn n(=,)b1 1 a21 21x1 1+a22 22x2 2+a2n 2nxn n(=,)b2 2 am1 m1x1 1+am2 m2x2 2+amn mnxn n(=,)bm m x1 1,x2 2,xn n0 10102.1 线性规划问题几个概念n n 可行解:若向量X=(x1 1,x2 2,xn n)满足所有的约束条件,则称其为可行解。n n 最优解:使目标函数达到最大值(或最小值)的可行解称为最优解。n n 最优值:最优解的目标函数值称为最优值。T T 11112.2 图解法n n 唯一解n n 无穷多个最优解n n 无界解n n 无可行解 1212Example 1:A Maximization ProblemExample 1:A Maximization Problemn n LP Formulation LP Formulation Max z=5 Max z=5 x x1 1+7+7 x x2 2 s.t.s.t.x x1 1 6 6 2 2 x x1 1+3+3 x x2 2 19 19 x x1 1+x x2 2 0 0 13138 87 76 65 54 43 32 21 1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 Example 1:Graphical SolutionExample 1:Graphical Solutionn n Constraint#1 Graphed Constraint#1 Graphed x x2 2x x1 1xx1 1 6 6(6,0)(6,0)14148 87 76 65 54 43 32 21 1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 Example 1:Graphical SolutionExample 1:Graphical Solutionn n Constraint#2 Graphed Constraint#2 Graphed2x2x1 1+3x+3x2 2 19 19 x x2 2x x1 1(0,6(0,6 1/3 1/3)(9(9 1/2 1/2,0),0)1515Example 1:Graphical SolutionExample 1:Graphical Solutionn n Constraint#3 Graphed Constraint#3 Graphed8 87 76 65 54 43 32 21 1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 x x2 2x x1 1xx11+xx22 8 8(0,8)(0,8)(8,0)(8,0)1616Example 1:Graphical SolutionExample 1:Graphical Solutionn n Combined-Constraint Graph Combined-Constraint Graph8 87 76 65 54 43 32 21 1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 2x2x1 1+3x+3x2 2 19 19 x x2 2x x1 1xx11+xx22 8 8xx1 1 6 6 1717Example 1:Graphical SolutionExample 1:Graphical Solutionn n Feasible Solution Region Feasible Solution Region8 87 76 65 54 43 32 21 1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 x x1 1Feasible FeasibleRegion Region x x2 2 18188 87 76 65 54 43 32 21 1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 Example 1:Graphical SolutionExample 1:Graphical Solutionn n Objective Function Line Objective Function Linex x1 1 x x2 2(7,0)(7,0)(0,5)(0,5)Objective FunctionObjective FunctionObjective Function max Z=5 max Z=5 max Z=5xxx111+7x7x7x222555xxx111+7x7x7x2 2 2=35=35=35 19198 87 76 65 54 43 32 21 1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 Example 1:Graphical SolutionExample 1:Graphical Solutionn n Optimal Solution Optimal Solutionx x1 1 x x2 2Objective FunctionObjective FunctionObjective Function555xxx111+7x7x7x2 2 2=46=46=46Optimal SolutionOptimal SolutionOptimal Solution(xxx111=5,=5,=5,xxx222=3)=3)=3)2020nn 画图求解nn 2)Max z=7 x1+5 x2nn 3)Max z=5 x1+10 x2nn 4)Max z=5 x1+5 x2 21218 87 76 65 54 43 32 21 1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 Example 1:Graphical SolutionExample 1:Graphical Solutionn n Optimal Solution Optimal Solutionx x1 1 x x2 2Objective FunctionObjective FunctionObjective Function 5 5 5xxx111+7x7x7x222Optimal SolutionOptimal SolutionOptimal Solution(xxx111=5,=5,=5,xxx222=3)=3)=3)2222图解法求最大化问题概要n n 确定每个约束条件的可行解的图n n 确定可以满足全部约束条件的可行解的范围n n 根据特殊的目标函数的值,画两条目标函数线n n 通过平行移动目标函数线,使目标函数值增大,直到可行域全在直线的一侧n n 在目标函数线上,使目标函数的值最大的解就是最优解 2323二维线性规划的几何特征n n 若可行域非空,它是一个凸集n n 若线性规划存在最优解(最优解之一),它一定在可行域的某个(某几个)顶点(极点)得到n n 这两个特征对高维的线性规划也适用。n n 解题思路:先找出凸集的一个顶点,计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大,如果为否,则这个顶点就是最优解的点(或之一),否则转到比这个点的目标函数值更大的另一顶点,重复上述过程,一直找到使目标函数最大的顶点为止。24242.3 极点和最优解n n The Five Extreme Points The Five Extreme Points8 87 76 65 54 43 32 21 1 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 x x1 1Feasible FeasibleRegion Region1 112 223 334 445 55 x x2 2 2525 26262.4 计算机求解产品A 产品B资源限制劳动力设备原材料9434510360工时200台时300公斤单位产品利润(元)70 120w 某厂生产两种产品,需要三种资源,已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表:27272.4 计算机求解1、确定决策变量:设生产A 产品x1kg,B 产品x2kg2、Obj:maxZ=70X1 1+120X2 23、S.t.:人力约束 9X1 1+4X2 2360 设备约束 4X1 1+5X2 2 200 原材料约束 3X1 1+10X2 2 300 非负性约束 X1 10 X2 20 2828 2.4 2.4 计算机计算机求解求解线性规划示意图maxZ=70X1+120X2 9X1+4X23604X1+5X2 2003X1+10X2 300 X10 X20 29292.5 最小化问题n n Example 2:A Minimization Problem Example 2:A Minimization Problem n n LP Formulation LP Formulation Min z=5 Min z=5x x1 1+2+2x x2 2 s.t.2 s.t.2x x1 1+5+5x x2 2 10 10 4 4x x1 1-x x2 2 12 12 x x1 1+x x2 2 4 4 x x1 1,x x2 2 0 0 3030Example 2:Graphical SolutionExample 2:Graphical Solutionn n Constraints Graphed Constraints Graphed555444333222111 1 2 3 4 5 61 2 3 4 5 61 2 3 4 5 6xxx222444xxx111-xxx222 12 12 12 xxx111+xxx222 4 4 4222xxx111+5+5+5xxx222 10 10 10 xxx111Feasible Region Feasible Region 3131Example 2:Graphical SolutionExample 2:Graphical Solutionn n Objective Function Graphed Objective Function Graphed5 54 43 32 21 1 1 2 3 4 5 61 2 3 4 5 6xxx222Min Min Min zzz=5=5=5xxx111+2+2+2xxx222444xxx111-xxx222 12 12 12xxx111+xxx222 4 4 4222xxx111+5+5+5xxx222 10 10 10 xxx111 3232Example 2:Graphical SolutionExample 2:Graphical Solutionn n Optimal Solution Optimal Solution5 54 43 32 21 1 1 2 3 4 5 61 2 3 4 5 6xxx222Min Min Min zzz=5=5=5xxx111+2+2+2xxx222444xxx111-xxx222 12 12 12xxx111+xxx222 4 4 4222xxx111+5+5+5xxx222 10 10 10Optimal:Optimal:Optimal:xxx111=16/5=16/5=16/5 xxx222=4/5=4/5=4/5xxx111 33332.6 特例n n 无可行解n n 无界解n n 无穷多最优解 3434无可行解 Max z=2 Max z=2x x1 1+6+6x x2 2 s.t.4 s.t.4x x1 1+3+3x x2 2 8 8 x x1 1,x x2 2 0 0 3535无可行解x x2 2x x1 14x1+3x2 83 34 44 48 8 3636无界解 Max z=3 Max z=3x x1 1+4+4x x2 2 s.t.s.t.x x1 1+x x2 2 5 5 3 3x x1 1+x x2 2 8 8 x x1 1,x x2 2 0 0 3737无界解x x2 2x x1 13 3 x x1 1+x x2 2 8 8x x1 1+x x2 2 5 5Max z=3 Max z=3 x x1 1+4+4 x x2 25 55 58 82.67 2.67 3838无穷多最优解n n?3939问题?作 业:P53-54 1(不用化为整数,图解),2(选作),3(不用化为整数,用软件求解)

    注意事项

    本文(运筹学之线性规划图解法.ppt)为本站会员(啧***)主动上传,淘文阁 - 分享文档赚钱的网站仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知淘文阁 - 分享文档赚钱的网站(点击联系客服),我们立即给予删除!

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




    关于淘文阁 - 版权申诉 - 用户使用规则 - 积分规则 - 联系我们

    本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

    工信部备案号:黑ICP备15003705号 © 2020-2023 www.taowenge.com 淘文阁 

    收起
    展开