线性规划问题的基本理论.ppt

第二章第2节线性规划问题的基本理论 一 线性规划问题的标准化二 线性规划问题的解三 线性规划问题的几何意义 一 线性规划问题的标准化 一般形式目标函数 Max Min z c1x1 c2x2 cnxn约束条件 a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bm决策变量 x1 x2 xn 0 标准形式目标函数 Maxz c1x1 c2x2 cnxn约束条件 a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bm决策变量 bi 0 x1 x2 xn 0 一般型和标准型的区别 可以看出 线性规划的标准形式有如下四个特点 目标最大化 约束为等式 决策变量均非负 右端项非负 对于各种非标准形式的线性规划问题 我们总可以通过以下变换 将其转化为标准形式 1 极小化目标函数的问题 设目标函数为Minf c1x1 c2x2 cnxn 可以 令z f 则该极小化问题与下面的极大化问题有相同的最优解 即Maxz c1x1 c2x2 cnxn但必须注意 尽管以上两个问题的最优解相同 但它们最优解的目标函数值却相差一个符号 即Minf Maxz 2 约束条件不是等式的问题 设约束条件为ai1x1 ai2x2 ainxn bi可以引进一个新的变量s 使它等于约束右边与左边之差 一般称S为松弛变量 s bi ai1x1 ai2x2 ainxn 显然 s也具有非负约束 即s 0 这时新的约束条件成为ai1x1 ai2x2 ainxn s bi 当约束条件为ai1x1 ai2x2 ainxn bi时 类似地令s ai1x1 ai2x2 ainxn bi显然 s也具有非负约束 即s 0 这时新的约束条件成为ai1x1 ai2x2 ainxn s bi称S为剩余变量 不等式情况下 当 引入松弛变量s当 引入剩余变量s松弛变量 需要补充的资源剩余变量 没有使用的资源如果原问题中有若干个非等式约束 则将其转化为标准形式时 必须对各个约束引进不同的松弛变量 3 右端项有负值的问题 在标准形式中 要求右端项必须每一个分量非负 当某一个右端项系数为负时 如bi 0 则把该等式约束两端同时乘以 1 得到 ai1x1 ai2x2 ainxn bi 4 决策变量不定 当Xio当某一个变量xj没有非负约束时 可以令xj xj xj 其中xj 0 xj 0即用两个非负变量之差来表示一个无符号限制的变量 当然xj的符号取决于xj 和xj 的大小 例 将以下线性规划问题转化为标准形式Minf 2x1 3x2 4x3s t 3x1 4x2 5x3 62x1 x3 8x1 x2 x3 9x1 x2 x3 0 解 首先 将目标函数转换成极大化 令z f 2x1 3x2 4x3其次考虑约束 有2个不等式约束 引进松弛变量x4 和剩余变量x5 0 第三个约束条件的右端值为负 在等式两边同时乘 1 通过以上变换 可以得到以下标准形式的线性规划问题 Maxz 2x1 3x2 4x3s t 3x1 4x2 5x3 x4 62x1 x3 x5 8 x1 x2 x3 9x1 x2 x3 x4 x5 0 练习 P24习题3 1 和 2 作业 P24习题3 3 二 线性规划问题的解 1 解的情况2 几个重要的解概念 1 解的情况 1 存在有限最优解 a 唯一最优解b 无穷多个最优解 2 不存在最优解a 无有限最优解 无界解 b 无可行解 可行域空 判断题 线性规划问题无有限最优解的充要条件是可行域为空 2 几个重要的解概念 1 可行解 可行域 最优解 最优值 2 基 基本解 3 基本可行解 基可行解 4 可行基 1 可行解 可行域 最优解 最优值 满足约束条件 1 2 1 3 式的解X x1 x2 xn T 称为线性规划问题的可行解 其中使目标函数达到最大值的可行解称为最优解 由可行解组成的集合就是可行域 满足约束条件不等式所有点组成的集合 将最优解代目标函数得到的函数值就是最优值 例 Maxz 1500 x1 2500 x2s t 3x1 2x2 652x1 x2 403x2 75x1 x2 0 2 基 基本解 设B为A中的一个基 令Ax b 中所有的非基变量 n m个 为0 得出的解x 称为是B的基本解 x1x2x3x4x5bi321006521010400300175P1P2P3P4P5A P1 P2 P3 P4 P5 B P1 P2 P3 基变量 x3x4x5 非基变量 x1x2 B的基本解是 0 0 65 40 70 3 基本可行解 1 满足非负的基本解 为基本可行解 2 可行解满足的条件是 Ax b和x 0 而基本解必然满足Ax b 只需满足X 0 4 可行基 对应于基可行解的基 称为可行基 基本解数目最多是Cnm个 一般基可行解的数目要小于基本解的数目 当基本解中的非零分量的个数小于m时 该基本解是退化解 练习 P96例题1作业 P96例题2 1 找出所有基本解 并指出哪些是基本可行解 1 基本概念2 基本定理3 几何意义 三 线性规划问题的几何意义 三 线性规划问题的几何意义 1 基本概念 1 凸集 2 顶点 1 凸集定义 设K是n维欧氏空间的一点集 若任意两点X 1 K X 2 K的连线上的所有点 X 1 1 X 2 K 0 1 则称K为凸集 任何两个凸集的交集是凸集 2 顶点设K是凸集 X K 若X不能用不同的两点X 1 K和X 2 K的线性组合表示为X X 1 1 X 2 0 1 则称X为K的一个顶点 或极点 2 基本定理定理1 若线性规划问题有可行域 则可行域必为凸集 定理2 线性规划问题的基可行解X对应于可行域D的顶点 定理3 若可行域有界 则最优解一定在顶点上达到 定理的意义 定理1 可行域是凸集 定理2 基本可行解对应顶点 定理3 最优解在顶点上找 几何意义的作用 线性规划问题的所有可行解构成的集合是凸集 也可能为无界域 它们有有限个顶点 线性规划问题的每个基可行解对应可行域的一个顶点 若线性规划问题有最优解 必在某顶点上