01《运筹学》第四版线性规划模型.ppt

* * * * * 1.2 型式转换 3）无约束的变量 设 x 为无约束变量， 实际含义： 如果变量 x 代表某产品当年计划数与上一年计划数之差， 则 x 的取值可能是正也可能是负。 令 ， 其中 。 1.2 型式转换 3．实例 将下面线性规划模型化为标准形式： 1 线性规划模型 解：令z＝－z， 按上述规则问题转化为： max z=x1－2x2－3x3＋3x3＋0x4＋0x5 x3＝x3 －x3(x3≥0，x3≥0) 1.2 型式转换 线性规划模型 三种形式 一般型 无特殊形式限制 典范型 约束为线性不等式组，决策变量非负 标准型 约束为线性方程组，决策变量非负 小结 1.2 型式转换 线性规划问题三种形式间的转换原则 典范型转化标准型 加入剩余（松弛）变量 等式可用两不等式表示 标准型转化典范型 无限制的变量可用两非负变量的差表示，或由某一等式解出该无限制的变量。 一般型转化标准/典范型 小结 1.2 型式转换 小结：线性规划型式转换步骤 步骤2 步骤3 步骤1 步骤4 若目标函数求极小，则 min z =CX —— max z′= ?CX； 若约束条件为不等式，则引入松弛变量或剩余变量 如果存在自由变量，则令我 ，若x≤0，则令x’=-x 右端项 bi ≤ 0 ，仅需等式或不等式两端同乘-1 第一章 线性规划 线性规划模型 1 线性规划解★ 2 单纯形法 3 对偶问题 4 对偶理论 5 算法复杂性 6 温 故 线性规划模型 型式转换 知 新 线性规划图解法 解的可能情况 求解 前节回顾 1.2 型式转换 小结：线性规划型式转换步骤 步骤2 步骤3 步骤1 步骤4 若目标函数求极小，则 min z =CX —— max z′= ?CX； 若约束条件为不等式，则引入松弛变量或剩余变量 如果存在自由变量，则令我 ，若x≤0，则令x’=-x 右端项 bi ≤ 0 ，仅需等式或不等式两端同乘-1 上节课内容回顾 线性规划 模型 三要素 决策变量 约束条件 目标函数 待求的未知数 操作控制的变量 受到的限制 由决策变量表示 需要优化的目标 由决策变量表示 上节课内容回顾 线性规划图解法的要点 图解法的定义、步骤 问题的图解法求解过程 解的可能情况分析 图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。 步骤1 对确定的Z，画出目标函数代表的直线 平移目标函数直线，确定最优解 画出由约束条件所确定的区域 步骤2 步骤3 线性规划图解法 定义与步骤 【例】水电厂和火电厂发电，已知生产单位电量所需各种资源消耗如下表： 每发单位电量水电厂可获利2元，每发单位电量火电厂可获利3元，问应如何安排计划使水火电总发电效益最大? 资源单耗 水电厂 火电厂 资源限量 维护成本 2 2 12元 设备折旧 1 2 8台时 水 4 0 16立方 煤 0 4 12千克 线性规划图解法 问题的提出 数学 模型 生产单位电量水火电厂分别获利2元、3元，如何安排计划使总发电效益最大? 【问题的分析】本例中的线性规划模型的三要素 线性规划图解法 问题的分析 水电厂和火电厂的产量x1, x2 决策变量 目标函数 约束条件 总发电收益z max z = 2x1+3x2 维护折旧、运行等资源限制 【问题的分析】本例中的线性规划模型的三要素 线性规划图解法 问题的分析 水电厂和火电厂的产量x1, x2 总发电收益z max z = 2x1+3x2 维护折旧、运行等资源限制 决策变量 目标函数 约束条件 开始用图解法求解 线性规划图解法 模型求解 【唯一最优解】 即当水火电厂分别发4 单位和2单位电量时， 总发电收益最大。 (0,6) (6,0) 2x1+2x2=12 (0,4) (8,0) x1+2x2=8 (4,0) 4x1=16 (0,3) 4x2=12 (0,2) (3,0) Z =6 (4,2) 将x1* =4，x2* =2 代入目标函数中 得最优值z *=14 可行域 步骤1 画出约束条件确定区域。 步骤2 画目标函数代表的直线。 步骤3 平移等值线确定最优解。 线性规划图解法 模型求解 线性规划模型是否都存在唯一最优解 线性规划图解法 模型求解 情形2：目标函数改变，约束条件不变 因其他水电欠发，火电厂单位获利提高。 max z = 2x1 ＋3x2 max z = 2x1 ＋4x2 【无穷多最优解】