线性规划的图解法和标准化.ppt

1 例1 目标函数 Maxz 50 x1 100 x2约束条件 s t x1 x2 300 A 2x1 x2 400 B x2 250 C x1 0 D x2 0 E 得到最优解 x1 50 x2 250最优目标值z 27500 1图解法 对于只有两个决策变量的线性规划问题 可以在平面直角坐标系上作图表示线性规划问题的有关概念 并求解 下面通过例1详细讲解其方法 2 几何概念 代数概念 直线 满足一个等式约束的解 半平面 满足一个不等式约束的解 半平面的交集 凸多边形 满足一组不等式约束的解 目标函数等值线 一组平行线 目标函数值等于一个常数的解 1图解法 注 当目标函数求极大时 等值线向右移 当目标函数求极小时 等值线向左移 3 1图解法 1 分别取决策变量X1和X2为横轴和纵轴 建立直角坐标系 在直角坐标系中 图上任意一点的坐标代表了决策变量的一组取值 例1的每个约束条件都代表一个半平面 4 1图解法 2 对每个不等式 约束条件 先取其等式在坐标系中作直线 然后确定不等式所决定的半平面 5 1图解法 3 把五个图合并成一个图 取各约束条件的公共部分 如图3 1所示 6 1图解法 4 目标函数Z 50 x1 100 x2 当Z取某一固定值时得到一条直线 直线上的每一点都具有相同的目标函数值 称之为 等值线 平行移动等值线 当移动到B点时 Z在可行域内实现了最大化 A B C D E是可行域的顶点 对有限个约束条件 则其可行域的顶点也是有限的 7 例2maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优解 6 4 8 6 0 x1 x2 1图解法 8 进一步讨论 例3某公司由于生产需要 共需要A B两种原料至少350吨 A B两种材料有一定替代性 其中A原料至少购进125吨 但由于A B两种原料的规格不同 各自所需的加工时间也是不同的 加工每吨A原料需要2个小时 加工每吨B原料需要1小时 而公司总共有600个加工小时 又知道每吨A原料的价格为2万元 每吨B原料的价格为3万元 试问在满足生产需要的前提下 在公司加工能力的范围内 如何购买A B两种原料 使得购进成本最低 9 进一步讨论 解 目标函数 MinZ 2x1 3x2约束条件 s t x1 x2 350 x1 1252x1 x2 600 x1 x2 0采用图解法 如左图 得Q点坐标 250 100 为最优解 10 重要结论1 线性规划的可行域是凸集可行域的顶点为有限个线性规划的最优解一定可以在某个顶点上实现 凸集 凸集 不是凸集 顶点 1图解法 11 1图解法 重要结论2 如果线性规划有唯一最优解 例1 2 3 则一定有一个可行域的顶点对应最优解 无穷多个最优解 若将例1中的目标函数变为maxz 50 x1 50 x2 则线段BC上的所有点都代表最优解 无界解 即可行域的范围延伸到无穷远 目标函数值可以无穷大或无穷小 一般来说 这说明模型有错 忽略了一些必要的约束条件 无可行解 若在例1的数学模型中再增加一个约束条件4x1 3x2 1200 则可行域为空域 不存在满足约束条件的解 当然也就不存在最优解 12 2线性规划的标准化 一般形式目标函数 Max Min Z c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0标准形式目标函数 MaxZ c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 bi 0注 只能使用一个脚码 变量连续编号 不能使用多重脚码 13 2线性规划的标准化 可以看出 线性规划的标准形式有如下四个特点 目标极大化 约束条件为等式 决策变量均非负 约束条件右端常数项非负 对于各种非标准形式的线性规划问题 我们总可以通过以下变换 将其转化为标准形式 14 2线性规划的标准化 1 变量不是大于等于0的问题 1 若xj 0 令xj xj 则xj 0 2 若变量为无约束在标准形式中 必须每一个变量均有非负约束 当某一个变量xj没有非负约束时 可以令 xj xj xj 其中xj 0 xj 0即用两个非负变量之差来表示一个无符号限制的变量 当然xj的符号取决于xj 和xj 的大小 15 2线性规划的标准化 2 目标函数为极小化的问题 设目标函数为 MinZ c1x1 c2x2 cnxn 可以 令Z Z 则该极小化问题与下面的极大化问题有相同的最优解 即 MaxZ c1x1 c2x2 cnxn但必须注意 尽管以上两个问题的最优解相同 但它们最优解的目标函数值却相差一个符号 即 MinZ MaxZ 3 右端常数项为负数的问题 在标准形式中 要求约束条件右端常数项必须全部是非负的 当某个右端常数项为负时 如bi 0 则把该约束条件两端同时乘以 1 得到 ai1x1 ai2x2 ainxn bi 16 2线性规划的标准化 4 约束条件不是等式的问题 设约束条件为ai1x1 ai2x2 ainxn bi可以引进一个新的变量s 使它等于约束右边与左边之差s bi ai1x1 ai2x2 ainxn 显然 s也具有非负约束 即 s 0 这时新的约束条件成为ai1x1 ai2x2 ainxn s bi 17 2线性规划的标准化 当约束条件为ai1x1 ai2x2 ainxn bi时 类似地令s ai1x1 ai2x2 ainxn bi显然 s也具有非负约束 即s 0 这时新的约束条件成为ai1x1 ai2x2 ainxn s bi 18 2线性规划的标准化 为了使约束由不等式成为等式而引进的变量s 当不等式为 小于等于 时称为 松弛变量 当不等式为 大于等于 时称为 剩余变量 如果原问题中有若干个非等式约束条件 则将其转化为标准形式时 必须对各个约束条件引进不同的松弛变量或剩余变量 结论 当约束条件为 在约束条件的左端加入非负的松弛变量 在约束条件的左端减去非负的剩余变量注 松弛变量和剩余变量在目标函数中的系数为0 19 例4 将下列线性规划模型标准化 2线性规划的标准化 20 2线性规划的标准化 21 2线性规划的标准化 例5 将以下线性规划问题转化为标准形式Minf 2x1 3x2 4x3s t 3x1 4x2 5x3 62x1 x3 8x1 x2 x3 9x1 x2 x3 0解 首先 将目标函数转换成极大化 令z f 2x1 3x2 4x3其次考虑约束条件 有2个不等式约束 引进松弛变量X4和