运筹学第3讲 线性规划2.ppt

运筹学 OperationsResearch 上海海事大学 20130925 任课教师 邓伟 邮箱 dengwei1663 线性规划问题的几何意义 凸集 设K是n维欧氏空间的一点集 若任意两点X 1 K X 2 K的连线上的所有点 X 1 1 X 2 K 0 1 则称K为凸集 注 实心圆 实心球体 实心立方体等都是凸集 圆环不是凸集 从直观上讲 凸集没有凹入部分 其内部没有空洞 图中的 a b 是凸集 c 不是凸集 任何两个凸集的交集仍为凸集 如图 d 线性规划问题的几何意义 结论 任何两个凸集的交集仍为凸集 证明 设A B为凸集 则因此同理从而所以A与B的交集为凸集 线性规划问题的几何意义 凸组合 设X 1 X 2 X k 是n维欧氏空间En中的k个点 若存在 1 2 k 且0 i 1 i 1 2 k 使X 1X 1 2X 2 kX k 则称X为X 1 X 2 X k 的凸组合 当0 i 1时 称为严格凸组合 顶点 设K是凸集 X K 若X不能用不同的两点X 1 K和X 2 K的线性组合表示为X X 1 1 X 2 0 1 则称X为K的一个顶点 或极点 注右图中0 Q1 Q2 Q3 Q4都是顶点 线性规划问题的几何意义 关于线性规划问题的几个定理 定理1 若线性规划问题存在可行解 则该问题的可行域是凸集 定理2 线性规划问题的基可行解X对应可行域 凸集 的顶点 定理3 若问题存在最优解 一定存在一个基可行解是最优解 或在某个顶点取得 以上证明过程见P16 20 单纯形法 尽管若线性规划问题有最优解 必可以在某顶点上得到 虽然顶点数目是有限的 它不大于个 若采用 枚举法 找所有基可行解 然后一一比较 最终可能找到最优解 但当n m的数较大时 这种办法是行不通的 m 20 n 40时 顶点的个数有个 如何有效地找到最优解 有多种方法 这里仅介绍单纯形法 SimplexMethod 单纯形法 单纯形 单纯形或者n 单纯形是和三角形类似的n维几何体 精确的讲 单纯形是某个n维以上的欧几里得空间中的 n 1 个仿射无关 也就是没有m维平面包含m 1个点 这样的点集被称为处于一般位置 的点的集合的凸包 0 单纯形就是点 1 单纯形就是线段 2 单纯形就是三角形 3 单纯形就是四面体 而4 单纯形是一个五胞体 每种情况都包含内部 标准n 单纯形 是Rn 1的子集 单纯形法 单纯形法的基本思路 根据前述定理 如果线性规划问题存在最优解 则可以在基本可行解中找最优解 由于基本可行解的个数是有限的 所以通过建立一种最优性判别准则 将基本可行解逐一进行检查 就可以在有限次检查后得到最优解 但是 在有些情况下 要找出所有的基本可行解是非常麻烦的 单纯形法的优越性就在于不用找出全部的基本可行解 单纯形法 单纯形法的基本思路 在得到一个基本可行解X1后 判断X1是否是最优解 或者判断此问题没有最优解 如果X1是最优解 或者此问题没有最优解 则求解到此为止 若不然 则依据这个解X1求出下一个基本可行解X2 并且X2要比X1对应的目标函数值有所改善 对X2重复刚才的判断 直到得到问题的解答为止 单纯形法 单纯形法的基本步骤 1 确定初始基本可行解X1 2 记Xk为求出的第k个基本可行解 根据建立的最优性准则 对Xk进行检验 若Xk是最优解 则计算终止 若不然 则转第 3 步 3 若根据建立的无最优解准则判断此问题没有最优解 则计算终止 若不能判定没有最优解 则转第 4 步 4 依据Xk求基本可行解Xk 1 使Z Xk 1 Z Xk 令k k 1 转回第 2 步 单纯形法 单纯形法的基本步骤 是否最优 转移到另一个基本可行解 找出更大的目标函数值 最优解 是 否 核心是 变量迭代 结束 找出一个初始可行解 循环 单纯形法 单纯形法的基本步骤 1 确定初始的基本可行解X1 假设在约束系数矩阵中含有单位阵并且bi 0 i 1 2 m 则令单位阵所在列对应的变量为基变量 其他变量为非基变量 并令非基变量取零值 可得到初始基本可行解 对于所有行约束条件为 不等式 在每行引入松弛变量化为标准形后 所有松弛变量的系数矩阵正好为单位矩阵 当化为标准形后系数矩阵中不含有单位阵时 确定初始基本可行解的方法可采用人工变量法 首先假设系数矩阵含单位阵的情况 单纯形法 单纯形法的基本步骤 2 确定最优性判别准则 设线性规划问题 LP 约束系数矩阵中的前m列为一个单位阵 其模型有如下形式 其中bi 0 i 1 2 m 目标函数 maxz c1x1 c2x2 cnxn约束条件 s t x1 a1m 1xm 1 a1nxn b1x2 a2m 1xm 1 a2nxn b2 LP xm amm 1xm 1 amnxn bmx1 x2 xn 0 单纯形法 单纯形法的基本步骤 2 确定最优性判别准则 取x1 xm为基变量 xm 1 xn为非基变量 基本解为X1 b1 b2 bm 0 0 T 将上式约束方程组变为 x1 b1 a1m 1xm 1 a1nxn x2 b2 a2m 1xm 1 a2nxn xm bm amm 1xm 1 amnxn 代入目标函数中 Z c1x1 c2x2 cnxn 单纯形法 单纯形法的基本步骤 2 确定最优性判别准则 记得到目标函数由当前解X1的非基变量的线性表示 其中Z1即为X1对应的目标函数值 单纯形法 单纯形法的基本步骤 2 确定最优性判别准则 将上面结果整理后 可得到与原线性规划等价的模型 定义 称此等价模型为基本可行解X1对应的典式 单纯形法 单纯形法的基本步骤 2 确定最优性判别准则 定理4 设X1 b1 b2 bm 0 0 T为线性规划 LP 的基本可行解 如果在其对应的典式中则X1为最优解 注 此定理就是单纯形法中的最优性判别准则 单纯形法 单纯形法的基本步骤 2 确定最优性判别准则 证明 设为任一可行解 Z0为其目标函数值 将X0代入基本可行解X1对应的典式的目标函数中 有由式 则有说明Z1为最大值 X1为最优解 定理得证 单纯形法 单纯形法的基本步骤 2 确定最优性判别准则 注 典式中的称为基本可行解的检验数 确切地说 是X1的非基变量的检验数 为了统一起见 对X1的基变量也规定检验数 显然 应有 因为典式中不含基变量 实际通过公式计算也为零 即基变量的检验数为零 单纯形法 例3 1为下面线性规划问题的一个基本可行解 试判断其是否为最优解 解 将模型化为基本可行解X1对应的典式 X1 6 2 15 0 0 T可知 x4 x5为非基变量 约束条件已具有典式形式 只需要将目标函数由非基变量x4 x5线性表示即可 Z 6 x4 6x5 2 x4 x5 2 15 6x4 2x5 2x4 x5 26 8x4 2x5由此可知 其中不满足最优性准则 因此不能判断X1为最优解 单纯形法 单纯形法的基本步骤 3 确定无最优解判别准则 定理5设X1为线性规划问题的基本可行解 如果在X1对应的典式中存在检验数 并且的约束系数皆小于等于零 则该线性规划问题的目标函数在可行域上没有上界 即没有最优解 无界解 例3 2判断下面的问题是否没有最优解 单纯形法 解 取为基本可行解 对于X1此模型已经为典式形式 其中检验数 并且皆小于等于零 由定理判断无最优解 怎么理解 分析 由约束条件可知 对于x3取任何非负值 此问题都存在可行解 目标函数值为 故而可知当M逐渐增大时 Z也相应增大 当时 因此Z为最大值 规划无最优解 单纯形法 单纯形法的基本步骤 4 基本可行解的迭代 定义 根据已有的基本可行解求新的基本可行解称为迭代 定义 将原基本可行解X1中的某个非基变量变为基变量 称为进基变量 将X1的某个基变量变为非基变量 称为出基变量 注 迭代的过程实际就是要实现进基变量和出基变量之间的转换 单纯形法 迭代方法 设为基变量 并且存在检验数 由X1的典式形式的目标函数的表达式可知其中Z1为X1对应的目标函数值 由于 故若选xk为进基变量时 一般基变量的取值大于零 可使目标函数值进一步增加 因此确定xk为进基变量 基本可行解X1的典式形式的约束方程组为 在基本可行解中 基变量的个数是固定的m个 xk进基 则必有一个基变量转换为非基变量 单纯形法 为了确定出基变量 首先在典式的约束中 令除xm以外的其余非基变量仍取零值 得到 根据这个关系式 又考虑到每个决策变量的可行性 从而选取xk 使其满足如下的关系式 单纯形法 当时 因为bi非负 故只需要即可 当时 则需 综合上面两种情况 因此 应使xk满足 注 因为最优性判别准则和无最优解判别定理不成立 故可以保证的存在性 以及 按照上面的规则确定的变量xk 当时 使得原第l个基变量的值变为 即基变量xl成为出基变量 单纯形法 可以证明 矩阵仍为可行基 因此得到新的基本可行解 其中各分量的值为 根据X1的典式的表达式中的目标函数 将X2代入计算得 新解比原解有所改善 增量为 至此 完成了基本可行解的迭代 单纯形法 定义 一般称为最小比值规则 或称为规则 其中的称为中心元素 主元 现将基本可行解的迭代过程归纳如下 设已得到基本可行解对应的典式形式 1 取对应的xk为进基变量 主要是提高收敛效率 使得每次的增量最大 2 按最小比值规则确定xk的值 并确定出基变量 3 按右式确定新的基本可行解 单纯形法 例3 3根据基本可行解X1以及典式 迭代求新的基本可行解 并指出目标函数值的增量 其典式为 X1的目标函数值为Z1 26 解 由于 所以确定x5为进基变量 按最小比值规则计算出因此 同时确定xl为出基变量 取零值 另外x4为非基变量仍取零值 单纯形法 将这些取值代入X2计算公式中 得到新的基本可行解为 其目标函数值为 目标函数值的增量为 对X2还应继续判断其是否是最优解 则问题转化为如何确定新的基本可行解X2的检验数 单纯形法 单纯形法的基本步骤 5 新的基本可行解的检验数的确定 不失一般性 考虑下面的线性规划模型 假设已得到的基本可行解不是最优解 并假设经过计算 确定x5为进基变量 x1为出基变量 a15为中心元素 得到新的基本可行解 单纯形法 单纯形法的基本步骤 5 新的基本可行解的检验数的确定 为了判断X2是否最优解 需要对约束方程组进行适当变换 找出X2对应的典式形式 为此 首先要在约束方程组中将新基变量x2 x3 x5显式表示出来 然后代入目标函数 得到目标函数由新的非基变量的线性表示 从而得到X2对应的检验数 这些变换可以经过下面的矩阵变换实现 即根据约束方程组构造矩阵式 对其进行初等行变换 变为矩阵式 单纯形法 单纯形法的基本步骤 5 新的基本可行解的检验数的确定 即 将进基变量x5对应的第5列向量化为单位向量 其中将中心元素a15化为1 由上面得到转化后的矩阵式 得到新的基本可行解X2对应的典式形式 其中即为新解X2的检验数 根据他们的正负 可以判断X2是否最优解 单纯形法 例3 4对例3 3中得到的基本可行解X2 判断其是否是最优解 由此可得到在求X2的检验数时用到的矩阵 解 是根据得到的 而X1对应的典式为 将进基变量x5对应的第5列向量化为单位向量 将中心元素a15 6化为1 得到 单纯形法 由此矩阵可知 的检验数 全部小于等于零 因此X2就是最优解 单纯形法 小结单纯形法的主要步骤 Step1确定初始的基本可行解X1 求出X1对应的典式 Step2根据最优性准则判别定理判断X1是否是最优解 若是 算法停止 X1即为最优解 否则 根据无最优解判别准则判断此线性规划是否无最优解 若是 算法停止 此规划无最优解 否则 转Step3 Step3由确定xk为进基变量 根据最小比值规则确定xk的值 确定中心元素和出基变量 Step4采用初等行变换将中心元素化为1 并将中心元素所在列化为单位列向量确定新的基本可行解X2 以及X2对应的检验数 转Step2 单纯形法 单纯形法的求解过程 实际上是在一系列表格上进行的 从这些表格上可以得到基本解 检验数等信息 这些表格称为单纯形表 每一个单纯形表相当于一个矩阵 每次迭代就是对矩阵进行初等行变换 例3 5求解下面的线性规划问题 单纯形法 解 单纯形表的主要步骤 1 构造初始单纯形表 单纯形表是根据线性规划问题的基本可行解对应的典式形式得到的 现在取X1 5 0 0 6 24 T求作为初始基本可行解 显然 模型中目标函数不是典式形式 因此需要将x4 6 x2 4x3代入目标函数Z 经整理得到Z 6 x2 2x3 单纯形法 构造初始单纯形表 CB表示基变量的系数 XB表示当前基变量 b表示当前基变量的取值 cj行为基变量的价值系数 为待填入的按最小比值规则计算的值 单纯形法 解 单纯形表的主要步骤 2 迭代求新的基本可行解及其检验数 在上面的单纯形表中 x2 x3检验数大于零 不满足最优性准则 需要进行迭代 确定中心元素以及进 出基变量 将中心元素化为1 中心元素所在列化为单位向量 单纯形法 解 单纯形表的主要步骤 2 迭代求新的基本可行解及其检验数 单纯形法 解 单纯形表的主要步骤 3 继续迭代 此表格中全部检验数均小于等于零 故得到最优解X 0 3 2 7 2 37 2 0 T 其对应的目标函数值为29 2 最优单纯形表 单纯形法 例3 5用单纯形法求解 解 初始基本可行解为X1 7 0 0 12 0 10 T 所给模型即为典式 可直接建立单纯形表进行计算 单纯形法 单纯形法 单纯形法 由上表得知 最优解为X 0 4 5 0 0 11 T 最优值为11 软件实现 例3 6求解 Max2x1 3x2St 4x1 3x2 103x1 5x2 12x1 0 x2 0 model max 2 x1 3 x2 4 x1 3 x2 10 3 x1 5 x2 12 end lingo 软件实现 软件实现 Globaloptimalsolutionfoundatiteration 2Objectivevalue 7 454545VariableValueReducedCostx11 2727270 000000 x21 6363640 000000RowSlacko