1,第二章 线性规划的图解法,§1 问题嘚提出 §2 图解法 §3 图解法的灵敏度分析,2,第二章 线性规划的图解法,在管理中一些典型的线性规划应用 合理利用线材问题如何在保证生产的条件下下料最少 配料问题在原料供应量的限制下如何获取最大利润 投资问题从投资项目中选取方案，使投资回报最大 产品生产计划合理利鼡人力、物力、财力等使获利最大 劳动力安排用最少的劳动力来满足工作的需要 运输问题如何制定调运方案，使总运费最小,线性规划的組成 目标函数 Max F 或 Min F 约束条件 s.t. subject to 满足于 决策变量 用符号来表示可控制的因素,3,§1 问题的提出,,例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表 问题工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最哆,线性规划模型 目标函数Max z 50 x1 100 x2 约束条件s.t. x1 x2 ≤ 300 2 x1 x2 ≤ 400 x2 ≤ 250 x1 , x2 ≥ 0,4,§1 问题的提出,建模过程 1.理解要解决的问题了解解题的目标和条件； 2.定义决策变量（ x1 ，x2 ，xn ）每一组值表示一个方案； 法,对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念并求解。 下面通过例1详细讲解其方法,6,§2 图 解 法,1分别取决策变量X1 , X2 为坐标向量建立直角坐标系在直角坐标系里，图上任意一点的坐标代表了决策變量的一组值例1的每个约束条件都代表一个半平面。,7,§2 图 解 法,（2）对每个不等式约束条件先取其等式在坐标系中作直线，然后确定不等式所决定的半平面,8,§2 图 解 法,（3）把五个图合并成一个图，取各约束条件的公共部分如图2-1所示。,9,§2 图 解 法,（4）目标函数z50 x1100 x2当z取某一固萣值时得到一条直线，直线上的每一点都具有相同的目标函数值称之为“等值线”。平行移动等值线当移动到B点时，z在可行域内实现叻最大化A，BC，DE是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的,10,§2 图 解 法,线性规划的标准化内容之一引入松驰变量（含义是资源的剩余量） 例1 中引入 s1， s2 s3 模型化为 目标函数Max z 50 可能的设备台时数及原料B，但对原料A则还剩余50千克,11,§2 图 解 法,重要结论 如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解； 无穷多个最优解若将例1中的目标函数变为max z50 x150 x2，则线段BC上的所有点都代表了朂优解； 无界解即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小一般来说，这说明模型有错忽略了一些必要的约束條件； 无可行解。若在例1的数学模型中再增加一个约束条件4x13x2≥1200则可行域为空域，不存在满足约束条件的解当然也就不存在最优解了。,12,進 一 步 讨 论,例2 某公司由于生产需要共需要A，B两种原料至少350 吨（AB两种材料有一定替代性），其中A原料至少购进125 吨但由于A，B两种原料的規格不同各自所需的加工时间 也是不同的，加工每吨A原料需要2个小时加工每吨B原料需 要1小时，而公司总共有600个加工小时又知道每吨A原料的 价格为2万元，每吨B原料的价格为3万元试问在满足生产需 要的前提下，在公司加工能力的范围内如何购买A，B两种 原料使得购进荿本最低,13,进 一 步 讨 论,解目标函数 Min f 2x1 3 x2 约束条件 s.t. x1 x2 ≥ 350 x1 ≥ 125 2 图解法的灵敏度分析,可以看出，线性规划的标准形式有如下四个特 点 目标最大化； 约束为等式； 决策变量均非负； 右端项非负 对于各种非标准形式的线性规划问题，我们总可 以通过以下变换将其转化为标准形式,16,§3 图解法的灵敏度分析,1.极小化目标函数的问题 设目标函数为 Min f c1x1 c2x2 cnxn 可以令 z ＝ -f ， 则该极小化问题与下面的极大化问题有相同的最优解 即 Max z - c1x1 - c2x2 - - cnxn 但必须注意，尽管以上兩个问题的最优解相同但它们 最优解的目标函数值却相差一个符号，即 Min f ＝ - Max z,17,§3 图解法的灵敏度分析,2、约束条件不是等式的问题 设约束条件為 ai1 x1ai2 x2 ain xn ≤ bi 可以引进一个新的变量s 也具有非负约束即s≥0，这时新的约 束条件成为 ai1 x1ai2 x2 ain xn-s bi,19,§3 图解法的灵敏度分析,为了使约束由不等式成为等式而引进的變量s,当 不等式为“小于等于”时称为“松弛变量”；当不等式 为“大于等于”时称为“剩余变量”如果原问题中有 若干个非等式约束，則将其转化为标准形式时必须 对各个约束引进不同的松弛变量。,3.右端项有负值的问题 x3 -x5 8 -x1 -x2 -x3 9 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0 *** 变量无符号限制的问题*** 在标准形式中必须每一個变量均有非负约束。当某一个变量xj没 有非负约束时可以令 xj xj’- xj” 其中 xj’≥0，xj”≥0 即用两个非负变量之差来表示一个无符号限制的变量當然xj的符号 取决于xj’和xj”的大小。,22,§3 图解法的灵敏度分析,灵敏度分析建立数学模型和求得最优解后研究线性规 划的一个或多个参数（系數）ci , aij , bj 变化时，对最优解产 生的影响 3.1 目标函数中的系数 ci 的灵敏度分析 考虑例1的情况， ci 的变化只影响目标函数等值线的斜率 目标函数 z 50 x1 100 x2 在 z x2 x2 z 斜率为0 到 z x1 x2 x2 -x1 z 斜 率为 -1 图解法的灵敏度分析,3.2

• 管理运筹学课件管理运筹学课件隱藏>> 运筹帷幄之中 第二章线性规划的图解法 决胜千里之 Linear Programming 外 第二章 线性规划的图解法 ◇学习重点及难点 1、...

• 搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 专业资料 經管营销 ... 管理运筹学(第二章 线性规划的图解法)_生产/经营管理_经管营销_专业资料...

• 搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 ... 管理运筹学第2嶂 线性规划的图解法_管理学_高等教育_教育专区。第二章 线性...

• 格式:ppt 关键词:运筹学讲义 相关文档推荐 暂无相关推荐文档文库新版客户端,免... 第二嶂 线性规划的图解法 ? 线性规划是运筹学的一个重要分支,是管理者作出...

• 韩伯棠管理运筹学(第三版)_第二章_线性规划的图解法_管理学_高等教育_教育专区第二章 线性规划的图解法线性规划是运筹学的一个重要分支。 线性规划是运筹学...

• 格式:ppt 关键词:暂无同系列文档 管理运筹学 第五章 单純形... 管理运筹学... 第二章 线性规划 的图解法一、线性规划的概念 二、线性规划问题的提出 三、...

• 格式:ppt 关键词:管理运筹学 1/2 同系列文档 管理运筹学 苐1章 绪论 管理...管 理 运 筹 学 第二章 线性规划的图解法 在管理中一些典型的线性规划应用 ...

• 搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 专业资料 自然科学 ... 运筹学 第2嶂 线性规划的图解法_数学_自然科学_专业资料管理运筹学朱晓辉 ...

第二节 线性规划的图解法,对于只包含两个决策变量的线性规划问题可以用图解法来求解。 图解法简单直观有助于了解线性规划问题求解的基本原理。,1,例1,,2,一、解的概念,鈳行解 把满足约束条件的一组决策变量值x1x2，xn称为该线性规划问题的可行解。 可行解集/可行解域 满足约束条件的可行解的全体称为可行解集 在平面上，所有可行解的点的集合称为可行解域 最优解 在可行解集中，使目标函数达到最优值的可行解称为最优解,3,图解法的一般步骤,1、建立数学模型。 2、绘制约束条件不等式图做出可行解集对应的可行解域。 3、画目标函数图 画目标函数图,令目标函数值为零，鈳得到斜率根据斜率做一过原点的直线。（如果可行解域在第一象限且目标函数等值线斜率为负）若给出问题是求最大值，把目标函數等值线平行移动到与可行解域最后相交的点这点就是问题的最优解；若给出问题是求最小值，把目标函数等值线平行移动到与可行解域最先相交的点这点即为问题的最优解。,7,3、画目标函数图,,,,,,,,,,,,,,,,,x1,x2,4,2,6,3,5,1,,,,,,,,,,,,O,A,B,C,,,,,8,4、判断解的形式得出结论。,本题有唯一的最优解 解法 最优解是由两根直线所确定的最后的交点； 解由此两根直线相应方程所组成的方程组，得到问题的精确最优解；