线性规划与单纯形法.ppt

第二章线性规划与单纯形法 第二章线性规划与单纯形法 第1节线性规划问题及其数学模型第2节图解法第3节解第4节单纯形法原理及其计算步骤第5节人工变量法第6节小结 第1节线性规划问题及其数学模型 一 规划如何合理地利用有限的人力 物力 财力等资源 以便得到最好的经济效果 第1节线性规划问题及其数学模型 例1 用一块边长为a的正方形铁皮做一个容器 应该如何裁剪 使做成的容器的容积最大 如下图所示 第1节线性规划问题及其数学模型 例1 解 设在铁皮四个角上剪去四个边长各为x的正方形V a 2x a 2x x max满足x a 2x 0 第1节线性规划问题及其数学模型 例2 某企业计划生产 两种产品 都要分别在A B C D四种不同设备上加工 按工艺资料规定 生产每件产品 需占用各设备分别为2 1 4 0 小时 生产每件产品 需占用各设备分别为2 2 0 4 小时 已知各设备计划期内用于生产这两种产品的能力分别为12 8 16 12 小时 又知每生产一件产品 企业能获利2元 每生产一件产品 企业能获利3元 问 该企业应如何安排生产两种产品各多少件 使企业的利润收入最大 第1节线性规划问题及其数学模型 例2 解 设 两种产品在计划期内的产量分别为x1 x2z 2x1 3x2 max2x1 2x2 12x1 2x2 8满足4x1 164x2 12x1 x2 0 表示形式 第1节线性规划问题及其数学模型 二 数学规划研究在一些给定的条件下 求所考察函数在某种意义下的极值问题 第1节线性规划问题及其数学模型 特征 1 决策变量 2 约束条件 3 目标函数 第1节线性规划问题及其数学模型 三 线性规划问题特征 三要素 1 决策变量 问题中的未知量 2 目标函数 问题要达到的目标 最大或最小 表示为决策变量的线性函数 3 约束条件 表示为含决策变量的一组互不矛盾的线性等式或线性不等式的函数约束和决策变量的非负约束 第1节线性规划问题及其数学模型 V a 2x a 2x x maxx a 2x 0z 2x1 3x2 max2x1 2x2 12x1 2x2 84x1 164x2 12x1 x2 0 第1节线性规划问题及其数学模型 线性规划问题数学模型的形式 1 一般形式 第1节线性规划问题及其数学模型 2 简写形式 3 向量形式 4 矩阵形式 第1节线性规划问题及其数学模型 例3 写出例2数学模型的一般形式和矩阵形式 一般形式矩阵形式maxz 2x1 3x22x1 2x2 12x1 2x2 84x1 164x2 12x1 x2 0 解 第1节线性规划问题及其数学模型 四 线性规划数学模型的标准形式 标准型 目标函数求最大值函数约束条件全为等式决策变量全为非负函数约束条件右端项全为非负 第1节线性规划问题及其数学模型 五 线性规划的非标准型如何转化为标准型目标函数求最小值 令z z函数约束条件为不等式 在函数约束条件左端加非负的松弛变量 在函数约束条件左端减非负的松弛变量松弛变量在目标函数中的系数全为 0 决策变量为负值 令xj xj xj 0决策变量取值无约束 令xj xj xj xj 0 xj 0函数约束条件右端项 bi 为负值 函数约束条件两端同乘 1 第1节线性规划问题及其数学模型 要求 将下列线性规划问题转化为标准型 例4 minz x1 2x2 3x3 2x1 x2 x3 9 3x1 x2 2x3 43x1 2x2 3x3 6x1 0 x2 0 x3取值无约束 第1节线性规划问题及其数学模型 例4 解 令maxz x1 2x2 3x3 3x3 0 x4 0 x52x1 x2 x3 x3 x4 93x1 x2 2x3 2x3 x5 43x1 2x2 3x3 3x3 6x1 x2 x3 x3 x4 x5 0 第1节线性规划问题及其数学模型 例5 minz x1 2x2 3x3x1 x2 x3 7x1 x2 x3 2 3x1 x2 2x3 5x1 x2 0 x3无约束 第1节线性规划问题及其数学模型 例5 解 令maxz x1 2x2 3x3 3x3 x1 x2 x3 x3 x4 7x1 x2 x3 x3 x5 2 3x1 x2 2x3 2x3 5x1 x2 x3 x3 x4 x5 0 第1节线性规划问题及其数学模型 例6 maxz 2x1 3x2 5x3x1 x2 x3 5 6x1 7x2 9x3 16 19x1 7x2 5x3 13x1 x2 0 x3无约束 第1节线性规划问题及其数学模型 例6 解 令maxz 2x1 3x2 5x3 5x3 x1 x2 x3 x3 x4 5 6x1 7x2 9x3 9x3 1619x1 7x2 5x3 5x3 x5 13 19x1 7x2 5x3 5x3 x6 13x1 x2 x3 x3 x4 x5 x6 0 作业2 1 作业2 1 将下列线性规划问题化为标准型 1 minz 5x1 2x2 4x3 3x4 x1 2x2 x3 4x4 2 x1 3x2 x3 x4 142x1 x2 3x3 x4 2x1无约束 x2 0 x3 x4 02 minz x1 2x2 4x32x1 x2 3x3 20 3x1 x2 4x3 25x1 x2 0 x3 0 第2节解 线性规划问题数学模型的标准型 以 一般形式 表示 第2节解 一 线性规划问题解的概念可行解 满足函数约束条件和非负约束条件的解 全部可行解的集合称为可行域最优解 使目标函数达到最大值的可行解 对应的目标函数值称为最优值 第2节解 基 设A是约束方程组的m n阶系数矩阵 B是矩阵A中m m阶非奇异子矩阵 称B是线性规划问题的一个基基向量 基B中每一个列向量Pj非基向量 A中其余列向量Pj 不在B中 基变量 与基向量Pj对应的决策变量xj非基变量 与非基向量对应的决策变量基解基可行解 满足非负约束条件的基解可行基 对应于基可行解的基 克莱姆法则 非奇异矩阵 解的关系 第2节解 非奇异矩阵 行列式不等于0的矩阵 克莱姆法则 如果线性方程组a11x1 a12x2 a1mxm b1a21x1 a22x2 a2mxm b2 am1x1 am2x2 ammxm bm的系数行列式不等于0 则方程组有唯一解 第2节解 二 线性规划问题解的关系 第2节解 例7 写出例2的标准型 并指出基 基变量 基解 基可行解和可行基 第2节解 例7 标准型maxz 2x1 3x22x1 2x2 12x1 2x2 84x1 164x2 12x1 x2 0 maxz 2x1 3x22x1 2x2 x3 12x1 2x2 x4 84x1 x5 164x2 x6 12x1 6 0 图解法 第2节解 例8 求下述线性规划的所有基解 基可行解及最优解 maxz 3x1 x2 3x3x1 x2 x3 2x1 2x2 4x3 6x1 x2 x3 0 作业2 2 作业2 2 求下列线性规划的所有基解 基可行解及最优解 1 maxz 2x1 3x2 4x3 7x42x1 3x2 x3 4x4 8 x1 2x2 6x3 7x4 3x1 x2 x3 x4 02 maxz 5x1 2x2 3x3 6x4x1 2x2 3x3 4x4 72x1 x2 x3 2x4 3x1 x2 x3 x4 0 第3节图解法 一 图解法适用条件 适用于求解只有两个决策变量的线性规划问题特点 1 不必将线性规划问题转化为标准型 2 直观性强 计算方便 第3节图解法 例9 用图解法求解下述线性规划问题 maxz 2x1 3x2x1 2x2 84x1 164x2 12x1 x2 0 第3节图解法 例9 标出约束条件 第3节图解法 例9 标出目标函数 唯一最优解 第3节图解法 二 图解法的求解步骤建立二维坐标系将约束条件表示在坐标系中 以确立可行域 画出每个函数约束的约束边界 用原点判断直线的哪一边是约束条件所允许的 找出所有约束条件都同时满足的区域 即可行域将目标函数绘制在坐标系中 并标出变化的方向 给定目标函数一个特定的值k 画出目标函数特定线 当k变化时 目标函数特定线将平行移动 对于目标函数最大 小 化的问题 找出目标函数增加 减少 的方向 目标函数最后离开可行域的点是最优解确定最优解 第3节图解法 三 图解法解的类型唯一最优解 仅有一点使目标函数值取得最大 小 值无穷多 多重 最优解 线段 射线 上任意一点都使目标函数值取得相同的最大 小 值无界解 可行域无界 目标函数值可以增大到无穷大无可行解 可行域为空集无界解和无可行解统称为无最优解 第3节图解法 要求 用图解法求解下列线性规划问题 例10 maxz 2x1 4x2x1 2x2 84x1 164x2 12x1 x2 0 第3节图解法 例10 多重最优解 第3节图解法 例11 maxz 2x1 3x24x1 16x1 x2 0 无界解 第3节图解法 例12 maxz 2x1 3x22x1 2x2 12x1 2x2 14x1 x2 0 无可行解 第3节图解法 四 图解法解的特点当可行域非空集时 可行域必是有界或无界凸多边形 凸集 集合C中任意两个点a和b 其连线上所有点也必为集合C中的点 若可行域有界 则目标函数一定可以在可行域的顶点上达到最优 若可行域无界 则可能无最优解 也可能有最优解 若有也必定在某顶点上达到 第3节图解法 线性规划问题的每个基可行解对应可行域的一个顶点 线性规划问题的最优解在顶点上达到 则一定存在一个基可行解是最优解 若有唯一最优解 则一定在可行域的某个顶点处得到 若有两个顶点同时达到最优解 则两个顶点之间线段上的任意一点都是最优解 既有无穷多最优解 线性规划问题有最优解 则解题思路 找出可行域的顶点 计算顶点处的目标函数值 比较各顶点的目标函数值 值最大 小 的顶点为最优解的点或最优解的点之一 第3节图解法 例13 下列哪一个图是凸集 ABCD 凸多边形 第3节图解法 例9图解 z 第3节图解法 例10图解 顶点最优 第3节图解法 要求 用图解法求解下列线性规划问题 例14 minz 2x1 x2 2x1 x2 2x1 2x2 1x1 x2 0 无界可行域 第3节图解法 例15 1 maxz x1 x2 2x1 x2 4x1 x2 2x1 x2 02 maxz x1 2x2x1 2x2 84x1 164x2 12x1 x2 0 第3节图解法 例15 2 作业2 3 作业2 3 用图解法求解下列线性规划问题 1 maxz 50 x1 100 x2x1 x2 3002x1 x2 400 x2 250 x1 x2 02 maxz 4x1 8x22x1 2x2 10 x1 x2 8x1 x2 0 3 maxz 3x1 9x2x1 3x2 22 x1 x2 4x2 62x1 5x2 0 x1 x2 04 maxz 2x1 2x2x1 x2 1 0 5x1 x2 2x1 x2 0 第4节单纯形法原理及其计算步骤 例16 求解下述线性规划问题 maxz 2x1 3x2x1 2x2 84x1 164x2 12x1 x2 0 第4节单纯形法原理及其计算步骤 例16 解 方法一 图解法 第4节单纯形法原理及其计算步骤 例16 解 方法二 确定所有基解 基可行解及最优解转化为标准型maxz 2x1 3x2x1 2x2 x3 84x1 x4 164x2 x5 12x1 5 0 第4节单纯形法原理及其计算步骤 例16 解 方法三 确定部分基可行解及最优解转化为标准型maxz 2x1 3x2x1 2x2 x3 84x1 x4 164x2 x5 12x1 5 0 第4节单纯形法原理及其计算步骤 一 单纯形法的解题思路从某一基可行解开始 转化到另一个相邻的基可行解 并且使相应的目标函数值有改进 即从可行域的一个顶点沿约束边界转换到可行域的另一个相邻的且使目标函数值有改进的顶点 直到目标函数值到达最优时的顶点为止 第4节单纯形法原理及其计算步骤 两个基可行解相邻 在基变量集合中 除了一个基变量以外 其他基变量全是相同的 只是数值可能不相同而已 第4节单纯形法原理及其计算步骤 二 单纯形法的含义单纯形法是一种迭代算法 首先找到一个初始基可行解 然后判断它是否为最优解 如果是就停止迭代 否则 按照一定的法则 再找到一个更好且与当前基可行解相邻的基可行解 再进行判断 直到找不到更好的基可行解或判断问题无解为止 第4节单纯形法原理及其计算步骤 三 单纯形法的解题步骤1 找出初始可行基 确定初始基可行解 建立初始单纯形表 第4节单纯形法原理及其计算步骤 例 线性规划问题数学模型的某种标准形式 第4节单纯形法原理及其计算步骤 初始单纯形表 第4节单纯形法原理及其计算步骤 2 检验各非基变量xj j m 1 m 2 n 的检验数 j 若 j 0 则已得最优解 停止计算 否则转入3 3 在 j 0 j m 1 m 2 n 中 若有某个 k对应的xk的系数列向量Pk 0 则此线性规划问题存在无界解 停止计算 否则转入4 4 根据 确定xk为换入变量 通过 计算确定xl为换出变量 转入5 第4节单纯形法原理及其计算步骤 5 以alk为主元素进行迭代 高斯消去法 把xk所对应的列向量将xB列中xl的换为xk 得到新的单纯形表 重复2 5 直至终止 单纯形法求解例16 第4节单纯形法原理及其计算步骤 高斯消去法的基本代数运算 一行乘以一个数一行乘上一个数加到另外一行中去 第4节单纯形法原理及其计算步骤 例16 解 方法四 单纯形法转化为标准型maxz 2x1 3x2x1 2x2 x3 84x1 x4 164x2 x5 12x1 5 0 第4节单纯形法原理及其计算步骤 例17 用单纯形法求解下述线性规划问题 maxz 2x1 x25x2 156x1 2x2 24x1 x2 5x1 x2 0 第4节单纯形法原理及其计算步骤 例17 解 转化为标准型maxz 2x1 x25x2 x3 156x1 2x2 x4 24x1 x2 x5 5x1 x2 x3 x4 x5 0 作业2 4 作业2 4 用单纯形法求解下列线性规划问题 1 maxz 5x1 2x2 3x3 x4 x5x1 2x2 2x3 x4 83x1 4x2 x3 x5 7x1 x2 x3 x4 x5 02 minz 5x1 4x2x1 2x2 62x1 x2 45x1 3x2 15x1 x2 0 第5节人工变量法 例18 求解下述线性规划问题 maxz 3x1 x3x1 x2 x3 4 2x1 x2 x3 13x2 x3 9x1 x2 x3 0 第5节人工变量法 例18 解 标准型 第5节人工变量法 第5节人工变量法 例18 线性规划问题的最后形式 第5节人工变量法 一 人工变量法的解题思路线性规划问题中不存在现成的可行基 为了求一个初始可行基和初始基可行解 在每个约束方程中人为地加上一个变量 人工变量 使约束方程组的系数矩阵中产生初始基 第5节人工变量法 二 人工变量法的含义为了确保引入人工变量以后新的线性规划问题与原线性规划问题求解的一致性 在最优解中人工变量取值必须为零 令人工变量的系数为 M M 0 表示充分大的数 M 称为 罚因子 表示只要人工变量取值大于零 目标函数就不可能达到最大值 第5节人工变量法 三 人工变量法的解题步骤将原问题转化为标准型对 或 的约束条件添加人工变量 直至构造出单位矩阵 且人工变量在目标函数中的系数为 M 建立初始单纯形表按照 单纯形法 的解题步骤2 5求解 人工变量法求解例18 第5节人工变量法 例18 解 第5节人工变量法 例19 用人工变量法求解下述线性规划问题 maxz 2x1 x2x1 x2 22x1 2x2 6x1 x2 0 第5节人工变量法 例19 解 标准型并添加人工变量maxz 2x1 x2 Mx5x1 x2 x3 22x1 2x2 x4 x5 6x1 x2 x3 x4 x5 0 第5节人工变量法 小结 1 将线性规划化为标准型后 对 或 的约束条件添加人工变量 若约束条件系数矩阵A中已有k个单位列向量 只要引入m k个人工变量 使它们与原来的k个单位列向量合成单位矩阵 2 在最优解中 若人工变量大于0 则原问题无可行解 作业2 5 作业2 5 用人工变量法求解下列线性规划问题 1 maxz 3x1 x2 x3x1 2x2 x3 11 4x1 x2 2x3 32x1 x3 1x1 x2 x3 0 2 minz x1 3x2 x3x1 x2 2x3 x4 4 x1 x3 x5 4x3 x6 3x1 x2 x3 x4 x5 x6 0 第6节小结 第6节小结 二 单纯形表中解的表示形式1 唯一最优解 最终单纯形表中 所有非基变量检验数 j 02 无穷多最优解 最终单纯形表中 某非基变量检验数 j 03 无界解 某检验数 j 0对应变量的系数列向量Pk 04 无可行解 线性规划问题中添加人工变量后 最终单纯形表中 基变量中含有非零的人工变量 0 第6节小结 5 退化现象 用 规则确定换出变量时 出现两个以上相同的最小比值 使下一个单纯形表中出现一个或多个基变量等于零 退化基可行解 一个或几个基变量取值 0 的基可行解退化基可行解出现的原因 模型中存在多余的约束 使多个基可行解对应同一顶点 第6节小结 退化基可行解的处理规则 出现退化基可行解 可能导致从某个基开始 经过若干次迭代后又回到原来的基 即单纯形法出现了循环 永远达不到最优解 导致计算失败 为避免出现死循环 法则如下 选择换入变量时 若有几个正的检验数具有相同的最大值 则选择下标最小的对应的非基变量作为换入变量选择换出变量时 若按 规则计算 有几个比值同时达到最小 则选择下标最小的对应的基变量作为换出变量 第6节小结 例20 下列表格是求线性规划问题的单纯形表 试说明解的情况 1 最终表 第6节小结 2 最终表 第6节小结 3 中间表 最终表 第6节小结 4 中间表 最终表 第6节小结 5 最初表 第6节小结 6 中间表 第6节小结 三 单纯形法对给定的线性规划问题 首先化为标准型 选取或构造一个单位矩阵作为基矩阵 求出初始基可行解并列出初始单纯形表 若线性规划问题的标准型为目标函数最小化 则最优解判别规则为 所有检验数 j 0 单纯形法计算步骤框图 第6节小结 例21 用单纯形法求解下述线性规划问题