第1章 线性规划及单纯型法.ppt

第1章线性规划及单纯型法 1 1线性规划问题及其模型1 2 1线性规划图解法1 2 2线性规划解的性质1 3单纯形法原理1 4单纯形法计算步骤1 5 1单纯形法的进一步讨论1 5 2单纯形法的矩阵描述1 6 1线性规划应用举例1 6 2线性规划模型 电子表格 1 7习题课 线性规划问题的提出线性规划的基本概念线性规划的数学模型线性规划问题的标准形式 1 1线性规划问题及其数学模型 问题的提出 例 生产计划问题 决策变量 Decisionvariables 目标函数 Objectivefunction 约束条件 Constraintconditions 可行域 Feasibleregion 最优解 Optimalsolution 基本概念 问题中要确定的未知量 表明规划中的用数量表示的方案 措施 可由决策者决定和控制 它是决策变量的函数 指决策变量取值时受到的各种资源条件的限制 通常表达为含决策变量的等式或不等式 满足约束条件的决策变量的取值范围 可行域中使目标函数达到最优的决策变量的值 是问题中要确定的未知量 表明规划中的用数量表示的方案 措施 可由决策者决定和控制 第1步 确定决策变量 设 I的产量 II的产量 利润 第2步 定义目标函数 MaxZ x1 x2 MaxZ 2x1 3x2 第2步 定义目标函数 第3步 表示约束条件 x1 2x2 84x1 164x2 12x1 x2 0 该计划的数学模型 目标函数MaxZ 2x1 3x2约束条件x1 2x2 84x1 164x2 12x1 x2 0 x1 x2 线性规划问题的共同特征 一组决策变量X表示一个方案 一般X大于等于零 约束条件是线性等式或不等式 目标函数是线性的 求目标函数最大化或最小化 线性规划模型的一般形式 线性规划问题的标准形式 标准形式为 目标函数最大约束条件等式决策变量非负 简写为 用向量表示 用矩阵表示 C 价值向量b 资源向量X 决策变量向量 minZ CX等价于maxZ CX 约束 加入非负松驰变量 一般线性规划问题的标准形化 例 目标函数MaxZ 2x1 3x2约束条件x1 2x2 84x1 164x2 12x1 x2 0 minZ CX等价于maxZ CX 约束 加入非负松驰变量 一般线性规划问题的标准形化 例 约束 减去非负剩余变量 Max 例 可正可负 即无约束 解 标准形为 练习建立LP数学模型一 有两个煤厂A B 每月分别供应三个居民区X Y Z 求运费最少的方案 供需平衡 线性规划模型举例 一 运输问题 二 布局问题 三 分派问题 四 生产计划问题 五 合理下料问题 线性规划模型的条件 1 要求解问题的目标函数能用数值指标来反映 且为线性函数 2 存在着多种方案 3 要求达到的目标是在一定约束条件下实现的 这些约束条件可用线性等式或不等式来描述 一 运输问题 设某种物资有m个产地 A1 A2 Am 联合供应n个销地 B1 B2 Bn 各产地产量 单位 吨 各销地销量 单位 吨 各产地至各销地单位运价 单位 元 吨 如下表所示 应如何调运 才使总运费最少 表中 ai表示产地Ai的产量 i 1 2 m bj表示产地Bj的产量 j 1 2 n cij表示AiBj间的单位运价 元 吨 i 1 2 m j 1 2 n 设xij表示由产地Ai运往销地Bj的物资数 i 1 2 m j 1 2 n 那么 上述运输问题的数学模型为 求一组变量xij i 1 2 m j 1 2 n 的值 使它满足 即 一 运输问题 产销平衡 约束条件 产地Ai发到各销地的发量总和应等于Ai的产量 各产地发到销地Bj的发量总和应等于Bj的销量 调运量不能为负数0 产销平衡的模型 约束条件 产地Ai发到各销地的发量总和应等于Ai的产量 各产地发到销地Bj的发量总和应等于Bj的销量 调运量不能为负数0 产销平衡的模型 约束条件 产销平衡的模型 产销不平衡 产大于销 一 运输问题 约束条件 产地Ai发到各销地的发量总和不超过Ai的产量 各产地发到销地Bj的发量总和应等于Bi的销量 调运量不能为负数 产销不平衡 产大于销的模型 二 布局问题 作物布局在n块地上种植m种作物 已知各块土地亩数 各种作物计划播种面积及各种作物在各块的单产 每亩的产量 如表 与运输问题相似 问 如何合理安排种植计划 才使总产量最多 二 布局问题 n块土地 每亩的产量 m种农作物 总产量最多 方法与运输问题类似 三 分派问题 解 设为Bj分派给人Ai情况 Bj分派给Ai时 不分派给Ai时 那末这一问题的数学模型为 求一组变量的值 使目标函数的值最小 完成全部工作的总工时最少 三 分派问题 约束条件 每件工作只分派一人去做 每人只做一件工作 每人对每件工作只有做与不做两种情况 分派问题的模型 目标函数 设用某原材料 条材或板材 下零件的毛坯 根据过去经验在一件原材料上有种不同的下料方式 每种下料方式可得各种毛坯个数及每种零件需要量如下表所示 问 应怎样安排下料方式 使得既能满足需要 用的原材料又最少 四 合理下料问题 五 合理下料问题 解 设用种方式下料的原材料数为 j 1 2 n 则这一问题的数学模型为 五 合理下料问题 所用原材料数量最少 所下的Ai零件总数不能少于 各种方式下料的原材料数不能是负数 分数 五 合理下料问题的模型 约束条件 目标函数 结束 线性规划模型 图解法线性规划问题求解的几种可能结果由图解法得到的启示 1 2 1线性规划的图解法 例1的数学模型 目标函数MaxZ 2x1 3x2约束条件x1 2x2 84x1 164x2 12x1 x2 0 x1 x2 9 8 7 6 5 4 3 2 1 0 123456789 x1 x2 x1 2x2 8 目标函数MaxZ 2x1 3x2约束条件x1 2x2 84x1 164x2 12x1 x2 0 4x1 16 4x2 12 图解法 9 8 7 6 5 4 3 2 1 0 x2 目标函数MaxZ 2x1 3x2约束条件x1 2x2 84x1 164x2 12x1 x2 0 可行域 图解法 9 8 7 6 5 4 3 2 1 0 123456789 x1 x2 目标函数MaxZ 2x1 3x2约束条件x1 2x2 84x1 164x2 12x1 x2 0 可行域 图解法 9 8 7 6 5 4 3 2 1 0 x2 目标函数MaxZ 2x1 3x2约束条件x1 2x2 84x1 164x2 12x1 x2 0 2x1 3x2 6 图解法 9 8 7 6 5 4 3 2 1 0 x2 目标函数MaxZ 2x1 3x2约束条件x1 2x2 84x1 164x2 12x1 x2 0 x1 2x2 84x1 16 图解法 图解法求解步骤 由全部约束条件作图求出可行域 作目标函数等值线 确定使目标函数最优的移动方向 平移目标函数的等值线 找出最优点 算出最优值 线性规划问题求解的几种可能结果 a 唯一最优解 b 无穷多最优解 线性规划问题求解的几种可能结果 c 无界解MaxZ x1 x2 2x1 x2 4x1 x2 2x1 x2 0 x1 线性规划问题求解的几种可能结果 d 无可行解MaxZ 2x1 3x2x1 2x2 84x1 164x2 12 2x1 x2 4x1 x2 0可行域为空集 线性规划问题求解的几种可能结果 图解法的几点结论 由图解法得到的启示 可行域是有界或无界的凸多边形 若线性规划问题存在最优解 它一定可以在可行域的顶点得到 若两个顶点同时得到最优解 则其连线上的所有点都是最优解 解题思路 找出凸集的顶点 计算其目标函数值 比较即得 练习 用图解法求解LP问题 图解法 练习 18 16 14 12 10 8 6 4 2 0 24681012141618 x1 x2 4x1 6x2 48 2x1 2x2 18 2x1 x2 16 图解法 练习 18 16 14 12 10 8 6 4 2 0 24681012141618 x1 x2 4x1 6x2 48 2x1 2x2 18 2x1 x2 16 可行域 A B C D E 图解法 练习 18 16 14 12 10 8 6 4 2 0 24681012141618 x1 x2 4x1 6x2 48 2x1 2x2 18 2x1 x2 16 A B C D E 8 0 0 6 8 34x1 40 x2 272 图解法 练习 18 16 14 12 10 8 6 4 2 0 24681012141618 x1 x2 4x1 6x2 48 2x1 2x2 18 2x1 x2 16 A B C D E 8 0 0 6 8 图解法 练习 x2 18 16 14 12 10 8 6 4 2 0 24681012141618 x1 4x1 6x2 48 2x1 2x2 18 2x1 x2 16 A B C D E 8 0 0 6 8 最优解 3 6 4x1 6x2 482x1 2x2 18 1 2 1线性规划的图解法 结束 1 2 2线性规划解的性质 线性规划解的概念线性规划问题的几何意义 单纯形法原理 线性规划问题解的概念 标准型可行解 满足AX b X 0的解X称为线性规划问题的可行解 最优解 使Z CX达到最大值的可行解称为最优解 基 若B是矩阵A中m m阶非奇异子矩阵 B 0 则B是线性规划问题的一个基 不妨设 j 1 2 m 基向量 j 1 2 m 基变量 j m 1 n 非基变量 线性规划问题解的概念 求解 线性规划问题解的概念 基本解 称上面求出的X解为基本解 基本可行解 非负的基本解X称为基本可行解可行基 对应基本可行解的基称为可行基 线性规划问题解的概念 线性规划解的关系图 非可行解 可行解 基本可行解 基本解 线性规划问题解的概念 最优解 例 求基本解 基本可行解 最优解 线性规划问题解的概念 最优解 线性规划问题解的概念 解 求基本解 基本可行解 最优解 练习 线性规划问题解的概念 3 线性规划问题的几何意义 基本概念凸集 线性规划问题的几何意义 顶点 若K是凸集 X K 若X不能用不同的两点的线性组合表示为 则X为顶点 凸集 线性规划问题的几何意义 凸组合 n 2 k 3 线性规划问题的几何意义 定理1 若线性规划问题存在可行域 则其可行域 D X AX b X 0 是凸集 基本定理 证明 线性规划问题的几何意义 只要验证X在D中即可 引理 可行解X为基本可行解X的正分量对应的列向量线性无关 定理3 若可行域有界 线性规划问题的目标函数一定可以在其可行域的顶点上达到最优 定理2 线性规划问题的基本可行解X对应于可行域D的顶点 几点结论 线性规划问题的可行域是凸集 基可行解与可行域的顶点一一对应 可行域有有限多个顶点 最优解必在顶点上得到 图解法 9 8 7 6 5 4 3 2 1 0 x2 可行域为凸集目标函数不同时等值线的斜率不同最优解在顶点产生 目标函数等值线的斜率 最优解 图解法 9 8 7 6 5 4 3 2 1 0 x2 可行域为凸集目标函数不同时等值线的斜率不同最优解在顶点产生 目标函数等值线的斜率 最优解 图解法 9 8 7 6 5 4 3 2 1 0 x2 可行域为凸集目标函数不同时等值线的斜率不同最优解在顶点产生 目标函数等值线的斜率 最优解 求解LP的基本思路 1 构造初始可行基 2 求出一个基可行解 顶点 3 最优性检验 判断是否最优解 4 基变化 转2 要保证目标函数值比原来更优 1 2 2线性规划解的性质 结束 1 3单纯形法原理 本节通过一个引例 可以了解利用单纯形法求解线性规划问题的思路 并将每一次的结果与图解法作一对比 其几何意义更为清楚 引例 上一章例 求解线性规划问题的基本思路 1 构造初始可行基 2 求出一个基可行解 顶点 3 最优性检验 判断是否最优解 4 基变化 转2 要保证目标函数值比原来更优 从线性规划解的性质可知求解线性规划问题的基本思路 第1步确定初始基可行解 根据 显然 可构成初等可行基B 为基变量 第2步求出基可行解 基变量用非基变量表示 并令非基变量为0时对应的解 是否是最优解 第3步最优性检验 分析目标函数 检验数 0时 无解换基 继续 只要取或的值可能增大 换入 基变量换出 基变量 考虑将或换入为基变量 第4步基变换 换入基变量 换入变量 均可换入 换出变量 使换入的变量越大越好同时 新的解要可行 选非负的最小者对应的变量换出 为换入变量 应换出 变量 思考 当时会怎样 因此 基由变为 为换入变量 应换出变量 转第2步 继续迭代 可得到 最优值 最优解 结合图形法分析 单纯形法的几何意义 A 0 3 B 2 3 C 4 2 D 4 0 单纯形法迭代原理 从引例中了解了线性规划的求解过程 将按上述思路介绍一般的线性规划模型的求解方法 单纯形法迭代原理 观察法 直接观察得到初始可行基 约束条件 加入松弛变量即形成可行基 下页 约束条件 加入非负人工变量 以后讨论 1 初始基可行解的确定 1 初始基可行解的确定 不妨设为松弛变量 则约束方程组可表示为 1 初始基可行解的确定 2 最优性检验与解的判别 2 最优性检验与解的判别 2 最优性检验与解的判别 1 最优解判别定理 若 为基可行解 且全部则为最优解 2 唯一最优解判别定理 若所有则存在唯一最有解 2 最优性检验与解的判别 3 无穷多最优解判定定理 若 且存在某一个非基变量则存在无穷多最优解 4 无界解判定定理 若有某一个非基变量并且对应的非基变量的系数则具有无界解 2 最优性检验与解的判别 4 之证明 2 最优性检验与解的判别 最优解判断小结 用非基变量的检验数 以后讨论 3 基变换 换入变量确定对应的为换入变量 一般 注意 只要对应的变量均可作为换入变量 此时 目标函数 换出变量确定 3 基变换 则对应的为换出变量 4 迭代运算 写成增广矩阵的形式 进行迭代 例 4 迭代运算 非基变量 基变量 001 通过初等行变换化主列为 主元 4 迭代运算 每次迭代的信息都在增广矩阵及目标函数中 检验数 1 3单纯形法迭代原理 结束 1 4单纯形法的计算步骤 为书写规范和便于计算 对单纯形法的计算设计了单纯形表 每一次迭代对应一张单纯形表 含初始基可行解的单纯形表称为初始单纯形表 含最优解的单纯形表称为最终单纯形表 本节介绍用单纯形表计算线性规划问题的步骤 在上一节单纯形法迭代原理中可知 每一次迭代计算只要表示出当前的约束方程组及目标函数即可 单纯形表 E单位阵 N非基阵 基变量XB 非基变量XN 0 单纯形表 21000 检验数 单纯形表结构 单纯形表 C 已知 21000 24 65 1 C 检验数 单纯形表结构 单纯形表 基可行解 单纯形表结构 单纯形表 有时不写此项 求 单纯形表结构 单纯形表 求 单纯形表结构 单纯形表 求 不妨设此为主列 主行 单纯形表结构 单纯形表 主元 用单纯形表求解LP问题 例 用单纯形表求解LP问题 解 化标准型 210000150510002462010051100121000 主元化为1主列单位向量换出换入 表1 列初始单纯形表 单位矩阵对应的变量为基变量 正检验数中最大者对应的列为主列 最小的值对应的行为主行 21000015051002412 601 600104 60 1 6101 30 1 30 表2 换基 初等行变换 主列化为单位向量 主元为1 检验数 0确定主列 最小确定主列 主元 检验数 0 最优解为X 7 2 3 2 15 2 0 0 目标函数值Z 8 5 表3 换基 初等行变换 主列化为单位向量 主元为1 210000150510002462010051100121000 练习 一般主列选择正检验数中最大者对应的列 也可选择其它正检验数的列 以第2列为主列 用单纯形法求解 正检验数对应的列为主列 结束 1 4单纯形法的计算步骤 1 5 1单纯形法的进一步讨论 一 大M法二 两阶段法 人工变量法 人工变量法 问题 线性规划问题化为标准形时 若约束条件的系数矩阵中不存在单位矩阵 如何构造初始可行基 人工变量法 加入人工变量 设线性规划问题的标准型为 加入人工变量 构造初始可行基 人工变量法 系数矩阵为单位矩阵 可构成初始可行基 约束条件已改变 目标函数如何调整 人工变量法 惩罚 人工变量 1 大M法 2 两阶段法 一 大M法 人工变量在目标函数中的系数为 M 其中 M为任意大的正数 目标函数中添加 罚因子 M M是任意大的正数 为人工变量系数 只要人工变量 0 则目标函数不可能实现最优 例 求解线性规划问题 一 大M法 一 大M法 解 加入松弛变量和剩余变量进行标准化 加入人工变量构造初始可行基 求解结果出现检验数非正若基变量中含非零的人工变量 则无可行解 否则 有最优解 一 大M法 用单纯形法求解 见下页 目标函数中添加 罚因子 M为人工变量系数 只要人工变量 0 则目标函数不可能实现最优 表1 初始单纯形表 一 大M法 单纯形法求解 一 大M法 单纯形法求解 表2 表3 一 大M法 单纯形法求解 表4 一 大M法 单纯形法求解 最优解为目标函数值z 2 检验数均非正 此为最终单纯形表 M在计算机上处理困难 分阶段处理 先求初始基 再求解 二 两阶段法 二 两阶段法 第一阶段 构造如下的线性规划问题 人工变量的系数矩阵为单位矩阵 可构成初始可行基 目标函数仅含人工变量 并要求实现最小化 若其最优解的目标函数值不为0 也即最优解的基变量中含有非零的人工变量 则原线性规划问题无可行解 用单纯形法求解上述问题 若 0 进入第二阶段 否则 原问题无可行解 第二阶段 去掉人工变量 还原目标函数系数 做出初始单纯形表 用单纯形法求解即可 二 两阶段法 下面举例说明 仍用大M法的例 例 二 两阶段法 二 两阶段法 构造第一阶段问题并求解 解 用单纯形法求解 二 两阶段法 第一阶段 求min 表1 1000 11000 0 10 00 1 x4x5x6 二 两阶段法 第一阶段 求min 表2 1 220 11000 00 1 00 1 x4x5x6 二 两阶段法 第一阶段 求min 表3 最终单纯形表 第二阶段 不含人工变量且 0 二 两阶段法 第二阶段 将去掉人工变量 还原目标函数系数 做出初始单纯形表 1000 1 二 两阶段法 1 3 2 30 12 3 4 3 00 x4x5 第二阶段 000 1 3 1 3 最优解为目标函数值z 2 单纯形法计算中的几个问题 1 目标函数极小化时解的最优性判断只需用检验数作为最优性的标志 2 无可行解的判断当求解结果出现所有时 如基变量仍含有非零的人工变量 两阶段法求解时第一阶段目标函数值不等于0 则问题无可行解 退化基可行解中存在基变量 0的解 退化解 换入变量和换出变量的Bland规则选择中下标最小的非基变量为换入变量 这里 当按规则计算存在两个和两个以上最小比值时 选下标最小的基变量为换出变量 单纯形法计算中的几个问题 1 5 1单纯形法的进一步讨论 结束 返回 继续 1 5 2单纯形法的进一步讨论 单纯形法的矩阵描述及改进单纯形法介绍 单纯形法的矩阵描述 不妨设基为 基变量 非基变量 设线性规划问题 则 单纯形法的矩阵描述 其中 令得当前的基解为 当前基解 约束方程组 当前目标值 目标函数 令得当前的目标函数值为 单纯形法的矩阵描述 当前检验数 单纯形法的矩阵描述 检验数 其中 当前对应的系数列 矩阵单纯形法计算的描述 线性规划问题 化为标准型 引入松弛变量 初始单纯形表 初始基变量 矩阵单纯形法计算的描述 当基变量为时 新的单纯形表 矩阵单纯形法计算的描述 当前检验数 当前基解 结束 线性规划模型 单纯形法习题课 继续 返回 基本概念 线性规划模型三个要素 决策变量 目标函数 约束条件线性性线性规划解的性质线性规划问题的可行域是凸集 最优解必在顶点上得到 线性规划求解方法图解法单纯形法 本次习题课内容 单纯形法小结 一般线性规划问题的标准化及初始单纯形法表 变量 约