线性规划问题的图解法.pptx

《线性规划问题的图解法.pptx》由会员分享，可在线阅读，更多相关《线性规划问题的图解法.pptx（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学 1线性规划问题的图解法图解法的一般步骤：图解法的一般步骤：先 先 将 将 约 约 束 束 条 条 件 件 和 和 非 非 负 负 条 条 件 件 加 加 以 以 图 图 解 解，画出可行域；画出可行域；再 再 画 画 目 目 标 标 函 函 数 数 等 等 值 值 线 线（令 令Z Z 为 为 某 某 一 一 常 常数 数c c）；）；最 最 后 后，结 结 合 合 目 目 标 标 函 函 数 数 的 的 要 要 求 求，平 平 移 移 目 目标 标 函 函 数 数 的 的 等 等 值 值 线 线，从 从 可 可 行 行 域 域 中 中 找 找 出 出 最 最 优 优解。解。第2 页/

2、共20 页 第1 页/共20 页图解法举例 图解法举例 例1-1第3 页/共20 页 第2 页/共20 页9 8 7 6 5 4 3 2 1 0|1 2 3 4 5 6 7 8 9x1x2x1+2x2 8(0,4)(8,0)目标函数 目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件 约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 04x1 164 x2 12v v 图解法 图解法第4 页/共20 页 第3 页/共20 页9 8 7 6 5 4 3 2 1 0 x

3、2 目标函数 目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件 约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0|1 2 3 4 5 6 7 8 9x1x1+2x2 84x1 164 x2 16可行域v v 图解法 图解法第5 页/共20 页 第4 页/共20 页9 8 7 6 5 4 3 2 1 0|1 2 3 4 5 6 7 8 9x1x2 目标函数 目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件 约束条件 x x1 1

4、+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 x1+2x2 84x1 164 x2 16可行域BCDEAv v 图解法 图解法第6 页/共20 页 第5 页/共20 页9 8 7 6 5 4 3 2 1 0 x2 目标函数 目标函数 Max Max Z Z=2=2x x1 1+3+3x x2 2 约束条件 约束条件 x x1 1+2+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0|1 2 3 4 5 6 7 8 9x1x1+2x2 84

5、x1 164 x2 16BCDEAx1+2x2=8 4x1=16最优解 最优解(4,2)(4,2)v v 图解法 图解法第7 页/共20 页 第6 页/共20 页 对应坐标 对应坐标x x1 1=4,x=4,x2 2=2=2 是最佳的产品组合 是最佳的产品组合,4,2,4,2T T就是线性规划模型的 就是线性规划模型的 最优解；最优解；使产品的总利润达到最大值 使产品的总利润达到最大值maxZ=2 maxZ=2 4+3 4+3 2=14 2=14 就是目标函数 就是目标函数 最优值 最优值。解联立方程求出最优解的精确值。解联立方程求出最优解的精确值。x1+2x2=8 4x1=16第8 页/共2

6、0 页 第7 页/共20 页总结线性规划问题的有关概念（1）可行解：满足约束条件与非负限制的变量的值，称为可行解。（2）可行域：全部可行解的集合称 为可行域。（3）最优解：使目标函数取得 最优值的可行解，称为最优解。第9 页/共20 页 第8 页/共20 页练习：某公司由于生产需要，共需要A，B 两种原料至少350 吨（A，B 两种材料有一定替代性），其中A 原料至少购进125吨。但由于A，B 两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A 原料需要2 个小时，加工每吨B 原料需要1 小时，而公司总共有600 个加工小时。又知道每吨A 原料的价格为2 万元，每吨B原料的价格为3

7、万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B 两种原料，使得购进成本最低？第10 页/共20 页 第9 页/共20 页解：目标函数：解：目标函数：Min f=2x Min f=2x1 1+3 x+3 x2 2 约束条件：约束条件：s.t.x s.t.x1 1+x+x2 2 350 350 x x1 1 125 125 2 x 2 x1 1+x+x2 2 600 600 x x1 1,x,x2 2 0 0 采用图解法。如下图：得 采用图解法。如下图：得Q Q 点坐标（点坐标（250 250，100 100）为最优解。）为最优解。100 200 300 400 500

8、600100200300400600500 x 1=125x 1+x 2=3502x 1+x 2=600 x 1 x 2 2x 1+3x 2=1200第1 1 页/共20 页 第10 页/共20 页100 200 300 400 500 600100200300400600500 x 1=125x 1+x 2=3502x 1+x 2=600 x 1 x 2 Q2x 1+3x 2=12002x 1+3x 2=9002x 1+3x 2=800第12 页/共20 页 第1 1 页/共20 页讨论：用图解法求解线性规划的各种可能 的结果。可行域有几种可能可行域有几种可能?解有几种可能解有几种可能?第1

9、3 页/共20 页 第12 页/共20 页线性规划问题求解的 线性规划问题求解的 几种可能结果 几种可能结果(1)唯一最优解 目标函数 目标函数 Max Max Z Z=2=2x x1+1+3 3x x2 2约束条件 约束条件 x x1+2 1+2x x2 2 8 8 4 4x x1 1 16 16 4 4x x2 2 12 12 x x1 1、x x2 2 0 0 x26 5 4 3 2 1 0|1 2 3 4 5 6 7 8 9x1第14 页/共20 页 第13 页/共20 页(2)无穷多最优解6 5 4 3 2 1 0 x2|1 2 3 4 5 6 7 8 9x1目标函数 目标函数 Ma

10、x Max Z Z=X X1 1+2X 2X2 2约束条件 约束条件 X X1 1+2X 2X2 2 8 8 4 4X X1 1 16 16 4 4X X2 2 12 12 X X1 1、X X 2 20 0第15 页/共20 页 第14 页/共20 页 目 标 函 数 等 值 线 与 可 行 域 的 一 条 边 界线 段 重 合，说 明 该 线 性 规 划 问 题 有无 无 穷 穷 多 多 个 个 最 最 优 优 解 解 线 段 上 的 所 有点 都 使 目 标 函 数 取 得 相 同 的 最 大 值Zmax=14。第16 页/共20 页 第15 页/共20 页(3)无界解 Max Max

11、Z Z=x x1 1+x x2 2s.t.s.t.-2-2x x1 1+x x2 2 4 4 x x1 1-x x2 2 2 2 x x1 1、x x2 2 0 0 x2x1该可行域无 该可行域无界，目标函 界，目标函数值可增加 数值可增加到无穷大 到无穷大42第17 页/共20 页 第16 页/共20 页 如 如 图 图 中 中 可 可 行 行 域 域 是 是 一 一 个 个 无 无 界 界 区 区 域 域，如 如 阴 阴影 影 区 区 所 所 示 示。虚 虚 线 线 为 为 目 目 标 标 函 函 数 数 等 等 值 值 线 线，沿 沿 着 着箭 箭 头 头 指 指 的 的 方 方 向 向

12、 平 平 移 移 可 可 以 以 使 使 目 目 标 标 函 函 数 数 值 值 无 无 限 限制地增大，但是找不到最优解。制地增大，但是找不到最优解。如 果 一 个 实 际 问 题 抽 象 成 像 上 面 这 样 的 线性 规 划 模 型，比 如 是 一 个 生 产 计 划 问 题，其经 济 含 义 就 是 某 些 资 源 是 无 限 的，产 品 的 产量 可 以 无 限 大，这 说 明 模 型 忽 略 了 一 些 必 要的 约 束 条 件。此 时 应 重 新 检 查 和 修 改 模 型，否则就没有实际意义。第18 页/共20 页 第17 页/共20 页(4)无可行解Max Max Z Z=

13、2=2x x1 1+3+3x x2 2s.t.x s.t.x1 1+2+2 x x2 2 8 8 4 4 x x1 1 16 16 4 4x x2 2 12 12-2-2x x1 1+x x2 2 4 4 x x1 1、x x2 2 0 0线性规划问题求解的线性规划问题求解的 几种可能结果几种可能结果该问题可行域 该问题可行域为空集，即无 为空集，即无可行解，也不 可行解，也不存在最优解。存在最优解。8 5 6 7x 13x 241 23102第19 页/共20 页 第18 页/共20 页由图解法得到的启示：由图解法得到的启示：n n可行域是有界或无界的凸多可行域是有界或无界的凸多边形。边形。n n若线性规划问题存在最优解，若线性规划问题存在最优解，它一定可以在可行域的顶点它一定可以在可行域的顶点得到。得到。n n若两个顶点同时得到最优解，若两个顶点同时得到最优解，则其连线上的所有点都是最则其连线上的所有点都是最优解。优解。第20 页/共20 页 第19 页/共20 页