清华大学《运筹学》教材相应的授课文档.第一章.ppt

1 第一章线性规划与单纯形法 1线性规划问题及其数学模型1 1问题的提出 eg 1 生产计划问题问 产品 各生产多少件 使利润最大 2 eg 2 污水处理问题环保要求河水含污低于2 河水可自身净化20 问 化工厂1 2每天各处理多少污水 使总费用最少 分析 化工厂1处理污水x1万m3 化工厂2处理污水x2万m3 minz 1000 x1 800 x2 2 x1 500 2 1000 1 0 2 2 x1 1 4 x2 500 200 2 1000 x1 2x2 1 4x1 x2 0这里minz 表示求z的最小值 3 线性规划的数学模型 max min z c1x1 c2x2 cnxna11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 4 说明 1 决策变量 x1 x2 xn 一组决策变量表示为问题的一个方案 2 目标函数 max min zz为决策变量的线性函数 3 约束条件一组线性不等式 cj为价值系数 bi为资源 aij为技术系数 i 1 m j 1 n 5 1 2图解法 eg 3 用图解法求eg 1 maxz 2x1 3x21x1 2x2 8 4x1 16 4x2 12 x1 x2 0 解 1 建立x1 x2坐标 2 约束条件的几何表示 3 目标函数的几何表示 z 2x1 3x2 o 4 3 6 首先取z 0 然后 使z逐渐增大 直至找到最优解所对应的点 可见 在Q2点z取到最大值 因此 Q2点所对应的解为最优解 Q2点坐标为 4 2 即 x1 4 x2 2 由此求得最优解 x1 4x2 2最大值 maxz z 2x1 3x2 14 元 4 3 7 讨论 1 唯一最优解maxz z 时 解唯一 如上例 2 无穷多最优解 eg 4 对eg 1 若目标函数z 2x1 4x2 此时表示目标函数的直线与表示条件 的直线平行 最优点在线段Q3Q2上 即存在无穷多最优解 8 3 无界解 eg 5 maxz 2x1 3x24x1 16x1 x2 0则x2 z 即存在无界解 在实际问题中 可能是缺少约束条件 9 4 无可行解 eg 6 maxz 2x1 3x22x1 4x2 8x1 x2 1x1 x2 0无公共部分 无可行域 即无可行解 在实际问题中 可能是关系错 10 1 3线性规划的标准型1 标准型maxz c1x1 c2x2 cnxna11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 11 用向量表示 12 用矩阵描述为 maxz CXAX bX 0其中 X x1 x2 xn TC c1 c2 cn b b1 b2 bm T 13 2 标准型的化法 1 min max minz cx max z max z minz cx令z z则maxz cx 2 不等式 对于 情况 在 左边加上一个松弛变量 非负 变为等式 对于 情况 在 左边减去一个剩余变量 非负 变为等式 注意 松弛变量 剩余变量在目标函数中的价值系数为0 3 无约束变量令xk xk xk xk xk 0 代入即可 14 eg 7 将下述问题化为标准型minz x1 2x2 3x3x1 x2 x3 7 x1 x2 x3 2 3x1 x2 2x3 5 x1 x2 0 x3无约束 解 令x3 x3 x3 x3 x3 0 式加上一个松弛变量x4 式减去一个剩余变量x5 令z z maxz x1 2x2 3 x3 x3 0 x4 0 x5x1 x2 x3 x3 x4 7x1 x2 x3 x3 x5 2 3x1 x2 2 x3 x3 5x1 x2 x3 x3 x4 x5 0 15 1 4线性规划解的概念设线性规划为maxz CX AX b X 0 A为m n矩阵 n m RankA m A为行满秩矩阵 1 可行解 满足条件 的X 2 最优解 满足条件 的可行解 3 基 取B为A中的m m子矩阵 RankB m 则称B为线性规划问题的一个基 取B p1 p2 pm pj a1j a2j amj T则称x1 x2 xm为基变量 其它为非基变量 16 4 基解 取B p1 p2 pm a11 a1mx1a1m 1 a1nxm 1b1 am1 ammxmamm 1 amnxnbm 基基变量非基非基变量令xm 1 xn 0 非基变量为0 则BXB b 17 5 基可行解满足 式要求的基解 如右图所示 各边交点O Q1 Q2 Q3 Q4均为基可行解 而其延长线的交点Q5为基解 但不是基可行解 O 0 0 Q1 4 0 Q2 4 2 Q4 0 3 Q3 2 3 Q5 4 3 6 可行基基可行解对应的B为可行基 18 2线性规划问题的几何意义2 1基本概念1 凸集 设K为En n维欧式空间 的一点集 X 1 K X 2 K 若 X 1 1 X 2 K 则称K为凸集 0 1 19 2 顶点 X K X 1 K X 2 K 任意两点 若X不能用 X 1 1 X 2 表示 则称X为K的一个顶点 0 1 注 顶点所对应的解是基可行解 3 凸组合 设X i En 若存在0 i 1 i 1 2 k 使 则称X为X i i 1 2 k 的凸组合 2 2基本定理1 定理1若线性规划存在可行域 则 可行域D X AX b X 0 为凸集 20 证明 设X 1 x1 1 x2 1 xn 1 T D X 2 x1 2 x2 2 xn 2 T D X 1 X 2 有AX 1 b AX 2 b令X X 1 1 X 2 001 0 X 0 即D为凸集 2 定理2线性规划的基可行解对应于可行域的顶点 3 定理3若线性规划有解 则一定存在基可行解为最优解 21 3单纯形法基本思路 从可行域的一个顶点到另一个顶点迭代求最优解 3 1初始基可行解的确定1 松弛基 松弛变量对应的B eg 8 maxz x1 3x2x1 2x2 32x1 3x2 4x1 x2 0 maxz x1 3x2 0 x3 0 x4x1 2x2 x3 32x1 3x2 x4 4x1 x2 x3 x4 0 取x3 x4为基变量 令非基变量x1 x2 0 初始基可行解 X 0 0034 T 22 2 观察法 eg 9 maxz x1 3x2 2x3 x4x1 2x2 3x3 33x2 x3 x4 4x1 x2 x3 x4 0 选XB x1x4 T令x2 x3 0则初始基可行解 X 0 3004 T 23 3 人工基 eg 10 maxz x1 2x2 3x3x1 3x2 2x3 32x1 x2 x3 4x1 x2 x3 0 分析 A 132211 找不到单位矩阵基 引入人工变量为初始基变量 2个 24 3 2最优性的检验与解的判别 25 则 26 解的判别 1 若 则此时的基可行解为最优解 2 若存在某个非基变量的检验数 且 则该线性规划问题具有无界解 或称无最优解 3 若所有 又 对于某个非基变量有 则该线性规划问题具有无穷多最优解 27 3 3基变换 28 3 4旋转运算 消元运算 a1k 0 al 1k 0pk alk 1 al 1k 0 amk 0得到基可行解 重复3 2 3 4 求出最优解 29 3 5单纯形表展开如下 a11x1 a12x2 a1nxn xn 1 b1 cn 1a21x1 a22x2 a2nxn xn 2 b2 cn 2 am1x1 am2x2 amnxn xn m bm cn mc1x1 c2x2 cnxn cn 1xn 1 cn mxn m z 0 1x1 2x2 nxn 0 xn 1 0 xn m z Z0 30 建立单纯形表 eg 11 用单纯形法求解maxz x1 3x2x1 2x2 84x1 164x2 12x1 x2 0 31 解 标准化 建立单纯形表引入松弛变量x3 x4 x5为初始基变量maxz x1 3x2 0 x3 0 x4 0 x5x1 2x2 x3 84x1 x4 164x2 x5 12x1 x2 x3 x4 x5 0 此时的解 x 0 0081612 Tz 0 0 32 解的判别 1 1 2 3 0 x 0 非最优解 基变换max 1 2 3 2x2入基min 8 2 12 4 12 4x5出基 33 此时的解 x 1 032160 Tz 1 9x 1 非最优x1入基x3出基 此时的解 x 2 23080 Tz 2 11x 2 为最优解 即 最优解 x 23080 T最大值 z 11 34 X 0 0081612 TO 0 0 X 1 032160 TQ4 0 3 X 2 23080 TQ3 2 3 35 4单纯形法的进一步讨论4 1人工变量法1 大M法 M为很大的正数 法则 对于max问题 人工变量在目标函数中的价值系数为 M 对于min问题 人工变量在目标函数中的价值系数为M eg 12 minz x1 5x2 0 x3 0 x42x1 3x2 x3 62x1 x2 x4 1x1 x2 x3 x4 0解 minz x1 5x2 0 x3 0 x4 Mx5 x5为人工变量2x1 3x2 x3 62x1 x2 x4 x5 1x1 x2 x3 x4 x5 0列单纯形表求解 36 minz x1 5x2 0 x3 0 x4 Mx52x1 3x2 x3 62x1 x2 x4 x5 1x1 x2 x3 x4 x5 0对于min问题 若min j 0 k 则xk为入基变量 这里 x1为入基变量 x5为出基变量 a21 2为主元 37 进一步迭代 38 因为所有 j 0 于是得问题的最优解 最优解 X x1x2x3x4x5 T 1 20500 T目标函数最小值 Z 1 22 两阶段法由于大M不是一个确定的数 所以大M法适宜于手工计算 而不适合求解 为此 引入两阶段法 第一阶段 给线性规划加入人工变量 并构造辅助规划 辅助规划的目标函数为minw xn 1 xn m这里xn 1 xn m为人工变量 39 以人工变量为初始基变量 列表计算 若本阶段无最优解 表示原线性规划无解 停止计算 若有最优解 则转第二阶段 第二阶段 在第一阶段最优表中 去掉人工变量 换上原问题目标函数 作为本阶段初始表 以此用单纯形法进行迭代运算 求出结果 40 例13用两阶段法求解minz x1 5x22x1 3x2 62x1 x2 1x1 x2 0解 第一阶段 将问题化为等式约束引进人工变量x5得辅助规划 minz x1 5x2 0 x3 0 x4minw x52x1 3x2 x3 62x1 3x2 x3 62x1 x2 x4 12x1 x2 x4 x5 1x1 x2 x3 x4 0 x1 x2 x3 x4 x5 0 41 minw x52x1 3x2 x3 62x1 x2 x4 x5 1x1 x2 x3 x4 x5 0 42 第一阶段有最优解 第二阶段 去掉人工变量 换上原线性规划目标函数 见下表 最优解 X 1 2050