第二章线性规划模型和图解法全PPT课件

Chapter2线性规划模型和图解法 LinearProgramming LP LP方法应用的典型情况LP的数学模型LP模型的图解法LP问题的计算机求解 本章主要内容 Chapter2线性规划模型和图解法 本章教学目的 重点 难点 掌握线性规划问题数学模型建立和线性规划模型的特征 线性规划模型的一般形式及标准形式 解的相关概念 掌握两个变量线性规划问题的几何作图求解方法 掌握两个变量线性规划模型可行域的特点及最优解存在的位置 熟悉计算机QM软件求解线性规划问题的步骤 1 规划问题阐述 生产和经营管理中经常提出如何合理安排 使人力 物力等各种资源得到充分利用 获得最大的效益 这就是规划问题 线性规划通常解决下列两类问题 1 当任务或目标确定后 如何统筹兼顾 合理安排 用最少的资源 如资金 设备 原标材料 人工 时间等 去完成确定的任务或目标 2 在一定的资源条件限制下 如何组织安排生产获得最好的经济效益 如产品量最多 利润最大 LP方法应用的典型情况 2在管理中一些典型的线性规划应用 LP方法应用的典型情况 1 生产的组织与计划问题 合理利用现有的人力 物力 财力做出最优产品生产计划 2 运输问题 根据生产单位的产量和销售单位的销量 制订产品调运方案 使得总运费最小 3 合理下料问题 如何裁截下料 既满足生产需要 又使得所用的材料数量最少 4 配料问题 在原料供应量限制和保证产品成分含量的前提下 获取最优配料方案 2在管理中一些典型的线性规划应用 LP方法应用的典型情况 5 营销管理问题 要从几种媒体中选择一种组合 使其在广告费用预算条件下广告效益最好 6 投资组合问题 选择一组股票或证券进行投资 使得有最大的回报率 7 人力资源管理问题 在不同的时间段需要不同数量的劳动力 如何安排劳动力才能用最少的劳动力来满足工作的需要 线性规划问题的数学模型 线性规划问题的数学模型 易拉罐的设计理念 具体下料 模型的建立 线性规划问题的数学模型 例1 2某企业计划生产甲 乙两种产品 这些产品分别要在A B C D 四种不同的设备上加工 按工艺资料规定 单件产品在不同设备上加工所需要的台时如下表所示 企业决策者应如何安排生产计划 使企业总的利润最大 2线性规划模型的建立 线性规划问题的数学模型 解 设x1 x2分别为甲 乙两种产品的产量 则数学模型为 线性规划问题的数学模型 3 线性规划的数学模型由三个要素构成 决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints 其特征是 1 问题的目标函数是多个决策变量的线性函数 通常是求最大值或最小值 2 问题的约束条件是一组多个决策变量的线性不等式或等式 怎样辨别一个模型是线性规划模型 模型建立练习 P13 线性规划问题的数学模型 4 线性规划数学模型的一般形式 简写为 线性规划问题的数学模型 向量形式 其中 线性规划问题的数学模型 矩阵形式 其中 线性规划问题的数学模型 5 线性规划问题的标准形式 特点 1 目标函数求最大值 有时求最小值 2 约束条件都为等式方程 且右端常数项bi都大于或等于零 3 决策变量xj为非负 线性规划问题的数学模型 6如何化标准形式 目标函数的转换 若存在取值无约束的变量 可令其中 变量的变换 线性规划问题的数学模型 约束方程的转换 由不等式转换为等式 称为松弛变量 称为剩余变量 变量的变换 可令 显然 线性规划问题的数学模型 例1 3将下列线性规划问题化为标准形式 线性规划问题的数学模型 2 第一个约束条件是 号 在 左端加入松驰变量x4 x4 0 化为等式 3 第二个约束条件是 号 在 左端减去剩余变量x5 x5 0 4 第3个约束方程右端常数项为 5 方程两边同乘以 1 将右端常数项化为正数 5 目标函数是最小值 为了化为求最大值 令z z 得到maxz z 即当z达到最小值时z 达到最大值 反之亦然 线性规划问题的数学模型 标准形式如下 学习要点小结 1 线性规划模型在管理中的应用 生产组织 下料问题等2 线性规划模型的构成 目标函数 约束条件 3 将一般形式转化标准形式 目标函数求最大 最小时 约束条件变为不等号时 常数项为负时 决策变量无约束时 小结 作业 作业 课堂出题练习思考 建立模型后怎样进行求解 线性规划模型的图解法 1 基本概念 线性规划问题 求解线性规划问题 就是从满足约束条件 2 3 的方程组中找出一个解 使目标函数 1 达到最大值 可行解 满足约束条件 2 3 的解为可行解 所有可行解的集合为可行域 最优解 使目标函数达到最大值的可行解 最优值 最优解带入目标函数所得的值称为线性规划的最优值 凸集 如果集合C中任何两点连线上所有的点都是集合C中的点 则称该集合为凸集 线性规划模型的图解法 线性规划模型的图解法 凸集 如果集合C中任意两个点X1 X2 其连线上的所有点也都是集合C中的点 称C为凸集 线性规划问题的求解方法 一般有两种方法 图解法单纯形法 两个变量 直角坐标 适用于任意变量 但必需将一般形式变成标准形式 下面我们分析一下简单的情况 只有两个决策变量的线性规划问题 这时可以通过图解的方法来求解 图解法具有简单 直观 便于初学者窥探线性规划基本原理和几何意义等优点 线性规划模型的图解法 线性规划模型图解法基本步骤 Step1 建立坐标系 Step2 图示约束条件 Step3 图示目标函数 Step4 确定最优解 图解法简单直观 有助于领会线性规划的基本性质及一般求解方法的基本思想 线性规划模型的图解法 maxZ 2X1 X2X1 1 9X2 3 8X1 1 9X2 3 8s t X1 1 9X2 10 2X1 1 9X2 3 8X1 X2 0 例1 4用图解法求解线性规划问题 线性规划模型的图解法 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 4 2X1 X2 20 2X1 X2 17 2 2X1 X2 11 2X1 X2 Lo 0 2X1 X2 7 6 2 D maxZ minZ 此点是唯一最优解 且最优目标函数值maxZ 17 2 可行域 maxZ 2X1 X2 线性规划模型的图解法 maxZ 3X1 5 7X2 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 7 6 2 D L0 0 3X1 5 7X2 maxZ 34 2 3X1 5 7X2 蓝色线段上的所有点都是最优解这种情形为有无穷多最优解 但是最优目标函数值maxZ 34 2是唯一的 可行域 线性规划模型的图解法 minZ 5X1 4X2 x1 x2 o X1 1 9X2 3 8 X1 1 9X2 3 8 X1 1 9X2 10 2 D L0 0 5X1 4X2 maxZ minZ 8 5X1 4X2 43 5X1 4X2 0 2 可行域 此点是唯一最优解 线性规划模型的图解法 2 4 6 x1 x2 2 4 6 无界解 无最优解 maxZ x1 2x2 例1 5 x1 x2 4 x1 3x2 6 3x1 x2 6 maxZ minZ 线性规划模型的图解法 x1 x2 O 10 20 30 40 10 20 30 40 50 50 无可行解 即无最优解 maxZ 3x1 4x2 例1 6 线性规划模型的图解法 练习 用图解法求解下面线性规划模型 线性规划模型的图解法 分析 用图解法求解下面线性规划模型 图1最大化线性规划模型的图解法 线性规划模型的图解法 分析 用图解法求解下面线性规划模型 线性规划模型的图解法 分析 用图解法求解下面线性规划模型 可得C点坐标X1 4 X2 2 对应的目标函数值为 线性规划模型有以下4种情况 唯一最优解 凸多边形的某个顶点 无穷多最优解 目标函数直线和可行域边界一条边重合 无界解 如果线性规划模型的解无限的变大 变小 却不违反任何约束条件 无可行解 不存在在满足全部约束条件的解 线性规划模型的图解法 计算机求解线性规规划问题 下面介绍QM软件的使用方法 Step1 双击QM软件图标 运行该软件 Step2 选择 Module 按回车键 选择 LinearProgramming 按回车键 选择 New 按回车键 Step3 在出现的窗口中确定约束方程个数 变量个数 选择最大值 最小值 并按 OK 确认 Step4 输入数据 Step5 选择 Solve 按回车键运行 Step6 在 Windows 窗口中查看结果 最优解 最优值 迭代过程 影子价格 线性规划模型的图解法 线性规划模型的图解法 2 使用QM软件求解线性规划模型 选择线性规划模块 P12例题 输入目标函数系数和约束条件如图1所示 图1 线性规划模型的图解法 点击 SLOVE 按钮 进行求解 结果如图2所示 图2 学习要点小结 1 线性规划模型的构成 将一般形式转化标准形式2 通过图解法了解线性规划有几种解的形