ch线性规划说课.ppt

假设这样一个规划问题：有两个决策变量X和Y 最大化：20X+10Y 约束条件 ： 1X≥2 Y≤5 X,Y≥0,如图所示 可行域 可以看出目标函数可以无限增加 解无界 本章讨论的内容对两道线性规划问题进行了阐述，展示了图解法的过程，并介绍了Management Scientist 的使用方法 介绍了线性规划问题模型的定义。 线性规划模型是一个数学模型，它的特征是： 1.存在一个目标函数，要求实现函数的最大化或最小化 2.存在一组线性的约束条件 3.有一组决策变量，这些决策变量都是非负的 线性规划问题标准化需要用到的两个变量：松弛变量－－未使用的资源；剩余变量－－超过某一最低需求的量 线性规划问题的解：有最优解（唯一、多重）；无最优解（无可行解）；无界解 主讲：程龙生 南京理工大学经济管理学院 管理科学与工程系 cheng_longsheng@163.com 025 线性规划是一种对问题进行求解的方法，可以帮助管理者制定决策。其特点： 1）在所有的使用线性规划解决的问题中，我们的目标都是实现某些量的最大化或最小化。 2）一定存在约束条件，而且这些约束条件会影响目标的实现。 建模，即将语言文字上的问题转化为数学问题。步骤如下 完整的了解问题 描述目标 描述约束条件 定义决策变量 根据决策变量写出模型目标 根据决策变量写出约束条件 这样我们就成功的将问题的目标以及约束条件转化为一组数学关系，这一过程通常称为数学模型 如果数学模型的目标和约束条件都是线性函数（函数中的每个变量都是独立的并且幂次为1），则称为线性规划模型或线性规划 某该公司是一个生产高尔夫器材的小型公司，，公司决定生产高中价位的高尔夫袋。分销商对此很感兴趣，并且同意买进该公司下3个月内的全部产品。 高尔夫袋生产步骤如下： 1.切割并印染原材料 2.缝合 3.成型（插入支撑架、球榜分离装置等） 4.检查和包装 生产每个高尔夫袋所需的时间和利润 切割 印染 缝合 完成 检查 包装 利润 （美元） 标准袋 7/10 1/2 1 1/10 10 高档袋 1 5/6 2/3 1/4 9 该公司各个部门的生产能力有限，3个月内各个部门的最大生产时间是： 高级袋和标准袋应该各生产多少才可以使公司获得，利润最大？ 建立数学模型： 定义决策变量：（1）标准袋的产量S （2）高档袋的产量D 利润 10S+9D 最大 约束条件 部门 切割印染 缝合 完成 检查包装 最大生产时间 630 600 708 135 切割印染 缝合 成型 检测包装 切割印染约束条件： 满足切割印染约束条件的可行解的范围 缝合约束条件： 满足缝合约束条件的可行解的范围 成型约束条件： 满足成型约束条件的可行解的范围 检验和包装的约束条件 满足检验包装约束条件的可行解的范围 可行域 所有的约束条件组合起来，表示出该公司的可行域 该公司的几条利润线和最优解 最大的利润线10S+9D 最优解(540,252) 步骤： 1.画出每个约束条件的可行解的图 2.确定可以满足全部约束条件的可行解的范围 3.根据特殊的目标函数的值，画出表示决策可变量的目标函数线 4.通过平行移动目标函数线，使目标函数增大，直到可行域全在直线的一侧。 5.在目标函数线上，使目标函数的值最大的解就是最优解 所有的变量非负且所有的约束条件都用等式来表达的线性规划称为标准形。 通过转换得到标准形 当决策变量小于或等于约束值时加上松弛变量。 当决策变量大于或等于约束值时减去剩余变量。 松弛变量和剩余变量代表着约束条件左侧和右侧的区别。 松弛变量和剩余变量在目标函数中的系数等于0。 前面所提到的模型的标准形式为： 可行域的顶点称为极点。 线性规划问题的最优解一定可以在可行域的一个极点上找到。