简介与线性规划(第一至四章)打印讲义.ppt

* 练习 在下列的线性规划问题中找出满足约束条件的所有基本解.指出哪些是基本可行解,并代入目标函数,确定那一个是最优解. * 解: * 则 是基解，但不是基本可行解. 是基解，且是基本可行解. * 是基解，且是基本可行解. 是基解，且不是基本可行解. * 是基解，但不是基本可行解. * LP问题的求解：单纯形法 基本思路：从一个基可行解转换到另一个“更好”的基可行解上(“更好”：目标函数值得到改善)，直到找到最优解或者获得无最优解的信息（P67） * 例题 * * * * * 初始基可行解的确定 * * 又因bi ≥0, 所以得到一个初始基可行解 * 最优性检验与解的判别（P71） * 检验数P71 * P71 * Maxz=-x1+x23x1-2x2+x3=1 2x1-x2+x4=1 xi≥0, i=1,2,3,4 * 基变换 * * * * 迭代(旋转运算) * * * * x1 x2 5 10 0 2x1+ x2≤10 x1+x2≤8 7 8 8 x2≤7 max z=6x1+4x2 0=6x1+4x2 可行域 最优解 (X1=2， x2=6) z=36 s.t. * 线性规划的图解法2 x1 x2 目标函数等值线 可行域 最优解 6 6 -8 4 max z=x1+3x2 x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0 s.t. * 练习图解法 * Q3 4 8 4 Q4 Q1 Q2 x1 x2 C 4x2 =12 x1+ 2x2 =8 * * 无界解 4 x1 x2 * 图解法的灵敏度分析（P18） 任务：讨论模型的系数或变量发生小的变化时对解的影响（如它们在何范围内变化时可使原最优解或最优基不变？） * 灵敏度分析主要内容 1. 目标函数系数变化的灵敏度分析 2. 右边项变化的灵敏度分析 3.约束条件中的系数变化的灵敏度分析 4. 增加新变量的灵敏度分析 5. 增加约束条件的灵敏度分析 * 1. 目标函数系数变化的灵敏度分析 假定只有一个 cj 变化，假定 cj 从 cj 变到cj*=cj+Δ cj，当Δ cj在什么范围内变化时，不会影响最优解。 * 2. 右边项发生变化的灵敏度分析 假定只有一个 br 变化，假定 br 从 br 变到br*=br+Δ br，当Δ br在什么范围内变化时，不会影响最优解。 * 灵敏度分析：建立数学模型和求得最优解后，研究线性规 划的一个或多个参数（系数）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 )之间时，原最优解 x1 = 50，x2 = 100 仍是最优解。 一般情况： z = c1 x1 + c2 x2 写成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目标函数等值线的斜率为 - (c1 / c2 ) ， 当 -1 ? - (c1 / c2 ) ? 0 （*） 时，原最优解仍是最优解。 * 假设产品Ⅱ的利润100元不变，即 c2 = 100，代到式（*）并整理得 0 ? c1 ? 100 假设产品Ⅰ的利润 50 元不变，即 c1 = 50 ，代到式（*）并整理得 50 ? c2 ? + ? 假若产品Ⅰ、Ⅱ的利润均改变，则可直接用式（*）来判断。 假设产品Ⅰ、Ⅱ的利润分别为60元、55元，则 - 2 ? - (60 / 55) ? - 1 那么，最优解为 z = x1 + x2 和 z = 2 x1 + x2 的交点 x1 = 100，x2 = 200 。 * §3　图解法的灵敏度分析 3.2 约束条件中右边系数 bj 的灵敏度分析 当约束条件中右边系数 bj 变化时，线性规划的可行域发生 变化，可能引起最优解的变化。 考虑例1的情况： 假设设备台时增加10个台时，即 b1变化为310，这时可行 域扩大，最优解为 x2 = 250 和 x1 + x2 = 310 的交点 x1 =