线性规划问题.ppt

第1章线性规划与单纯形法 本章要点 1 线性规划问题的数学模型 2 线性规划问题的基本理论 3 线性规划问题的求解 例1 1 美佳公司计划制造I II两种家电产品 已知各制造一件时分别占用的设备A B的台时 调试时间 调试工序及每天可用于这两种家电的能力 各售出一件时的获得情况 如表所示 问该公司应制造两种家电各多少件 使获取的利润为最大 一 问题的提出 1 1线性规划问题与及其数学模型 Max 解 设x1和x2分别表示美佳公司制造家电I和II的数量 则该问题可用线性规划模型表示如下 1 1线性规划问题与及其数学模型 1 1线性规划问题与及其数学模型 例1 2某工厂计划生产A B C三种产品 每吨利润分别为2万元 3万元 1万元 生产单位产品所需的工时及原材料如表所示 如果供应的原材料每天不超过3吨 每天所能利用的劳动力总工时是固定的 问如何制定日生产计划 使三种产品总利润最大 设每天生产A产品X1吨 B产品X2吨 C产品X3吨 则用数学语言可描述为 Max 1 1线性规划问题与及其数学模型 例1 3某工地租赁机械甲和乙来安装A B C三种构件 已知这两种机械每天的安装能力如表所示 而工程任务要求共安装250根A构件 300根B构件和700根C构件 又知机械甲每天租赁费为250元 机械乙每天租赁费为350元 试决定租赁机械甲和乙各多少天 才能使总租赁费最少 1 1线性规划问题与及其数学模型 设租赁甲X1天 机械乙X2天 为满足A B C的安装要求 则用数学语言可描述为 Min 1 1线性规划问题与及其数学模型 二 线性规划的数学模型共同特征 1 决策变量 向量 X2 约束条件 向量 AX b3 线性目标函数Z CX 其中 C为价值系数 向量 A为约束条件系数矩阵 1 1线性规划问题与及其数学模型 用数学语言可描述为 Max Min 1 1线性规划问题与及其数学模型 线性规划模型的结构目标函数 max min约束条件 变量符号 0 unr 0 用矩阵描述为 1 1线性规划问题与及其数学模型 1 2线性规划问题的求解 图解法 适用于 个决策变量 鞍面法 1992年中国沈阳化工学院尚毅教授发明 内点法 1984年美国籍印度数学家Karmarker 卡玛卡 发明 椭球法 1979年苏联数学家Khachiyan 哈奇扬 发明 单纯形法 1952年美国斯坦福大学教授Dantzig 丹茨格 发明 可以解决1 5万至2万个决策变量 1 2线性规划的求解 一 图解法maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优解 6 4 8 6 0 x1 x2 1 2线性规划的求解 图解法求解步骤1 建立直角坐标系 2 根据线性规划问题的约束条件和非负条件画出可行域 3 作出目标函数等值线Z c c为一常数 并使其平移求得最优解 1 2线性规划的求解 线性规划的解的特殊情况唯一解 无界解 少了约束条件 例Maxz x1 2x2stx1 1x2 2 无穷解 头与身平行 例Maxz x1 x2st2x1 2x2 0 x2 0 1 2线性规划的求解 无可行解 有矛盾约束 例MinZ x1 x2stx1 2x1 1 1 2线性规划的求解 二 线性规划问题的标准型1 线性规划问题的标准型统一规定 1 目标函数取极大化类型 也可以是极小化类型 2 所有约束条件用等式来表示 3 所有决策变量取非负值 4 每一约束条件的右端常数为非负值 1 2线性规划的求解 2 线性规划问题的标准型为 Max 1 2线性规划的求解 标准型缩写式为 Max i 1 2 m 1 2线性规划的求解 向量形式为 MaxZ CX j 1 2 n 线性规划的标准形式矩阵形式为 目标函数 max约束条件 变量符号 0 1 2线性规划的求解 1 2线性规划的求解 线性规划问题的标准化1 目标函数的标准化 对于最小化问题MINZ 化为最大化问题为 MAXZ Z CX 如不等号为 则左边减去一非负变量变为等式 如不等号为 则左边加上一非负变量变为等式 若右端为负 则左右两同乘 1 即可 若某个变量无约束 则引入两个非负变量 可令 2 约束条件的标准化 1 2线性规划的求解 例1 4 Max Max 1 2线性规划的求解 例1 5将下面的线性规划问题化成标准型 Min Min 1 2线性规划的求解 Min Max 1 2线性规划的求解三 线性规划的解 Max i 1 2 m 1 2 3 1 可行解 满足上面模型中的 2 和 3 式的解X 最优解 满足上面模型中的 1 的可行解X 基 矩阵 若B是A中的m m阶非奇异子式 即 B 0 则B是线性规划问题的一个基 矩阵 可设B P1 P2 Pm 则Pj为基向量 与Pj对应的变量xj为基 本 变量 1 2线性规划的求解三 线性规划的解 Max i 1 2 m 1 2 3 1 非基 本 变量 X中除基 本 变量外的变量 在方程AX b中 令非基变量的值为0 求得基本变量的值 这样得到的一组解X0称为方程AX b关于基B的基本解 一般m n 故基本解的个数 基本可行解 满足模型中 3 式的基本解 1 2线性规划的求解三 线性规划的解 例1 6设线性规划问题的约束条件如下 试求其基本可行解 可知 m 1 n 3 故基本解的个数应 3 试理解各解之间的关系 1 2线性规划的求解三 线性规划的解 例1 7设线性规划问题的约束条件如下 试求其基本可行解 1 2线性规划的求解三 线性规划的解 解间的关系如下图所示 基本可行解 基本解 可行解 非可行解 最优解 基本可行解 1 基本概念凸集 设K是n维欧氏空间的一个点集 若任意两点X 1 K X 2 K的连线上的一切点满足下式 1 2线性规划的求解四 线性规划问题解的几何意义 则称K为凸集 顶点 设K为凸集 X K 若不能用两点X 1 K X 2 K组合表示为 则X为K的一个顶点 或极点 1 2线性规划的求解四 线性规划问题解的几何意义 2 基本定理 定理1 线性规划问题的可行解集是一个凸集 即 定理2 设线性规划问题的可行解集为D 则X是D的一个顶点的充要条件是X是线性规划问题的基本可行解 定理3 若可行域非空有界 则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值 1 2线性规划的求解四 线性规划问题解的几何意义 基本结论 线性规划问题的所有可行解构成的集合是凸集 线性规划问题的每一个基本可行解都有对应可行域的一个顶点 若线性规划问题有最优解 必定在可行域的某个顶点上达到 1 2线性规划的求解五 单纯形法 1 单纯形法的基本思想单纯形法的基本思路 根据线性规划问题的标准型 从可行域的一个基本可行解 即某个顶点 开始 转移到另一个基本可行解 顶点 并且使目标函数值逐步变优 当目标函数达到极大值时 就得到了最优解 例1 8 Max 1 2线性规划的求解五 单纯形法 化为标准形式为 可知 可得基本解 X 0 0 0 1 3 T 也即基本可行解 Max 1 2线性规划的求解五 单纯形法 观察目标函数 若要使目标函数增加 可知如果x1和x2能变为基变量的话 会使目标函数值增加快 我们可以通过模型系数矩阵初等变化解方程组得到同解的原理 可以实现上述步骤 也即原约束方程组可化为 可得到解 X 1 2 0 0 0 T 1 2线性规划的求解五 单纯形法 变化过程 可得Z 2x1 3x2 x3 0 0 1 2线性规划的求解五 单纯形法 2 单纯形法的求解步骤1 确定初始基本可行解2 最优性检验如果判别行 j 0 则已得到最优解 否则继续转下一步 3 迭代变化 确定换入基变量 Max j j 0 k确定换出基变量 4 继续迭代 旋转变换 1 2线性规划的求解五 单纯形法 3 表格单纯法 单纯形表 例1 9 Max j j 0 k 1 2线性规划的求解五 单纯形法 j 0 无界解判定 若非基变量 k 0 且 则该线性规划问题的解无界 1 2线性规划的求解五 单纯形法 一般线性规划问题的处理没有立即出现初始基本可行解 人工加入变量 即人工变量 后 变换后的问题有初始基本可行解 但两方程组不等价 当且仅当加入的变量可以优化为0时 变换前后方程组才等价 例1 9用单纯形法解线性规划问题 Max 加入人工变量 化标准形式如下 1 大M法 M为足够大的数 目标函数中处理 把要优化为0的人工变量在目标函数中减去M乘以人工变量 再用单纯形法求解 可知人工变量会很快优化为0 否则目标函数无法增加 甚至无法达到目标最优解 即目标值最大 当人工变量为0时 加入人工变量的前后方程是等价的 也即找到原问题的初始基本可行解 然后继续用单纯法迭代即对原问题完成求解 如果得不到初始基本可行解 则原问题无解 1 大M法 Max 1 大M法 660403 31 1 21 10 110 330211 10 x4x2x7 00 M Z0 6M 3 0 4M 1 0 3M 4M 0 1 1 xBbx1x2x3x4x5x6x7 CB Cj 30100 M M 411110001 21 10 11090310001 x4x6x7 0 M M Z 2M 3 4M 1 0 M 0 0 4 1 3 1 大M法 续 xBbx1x2x3x4x5x6x7 CB Cj 30100 M M x4x2x1 00 3 Z 3 2 9 2 00001 1 21 2 1 2 1102 301 2 1 21 6 3011 30001 3 3 0 0 3 0 3 2 M 3 2 M 1 2 i 93 2 3 23 20103 4 3 41 4 5 2 1 2100 1 41 41 4 00001 1 21 2 1 2 x4x2x3 001 Z 0 0 0 3 4 M 3 4 M 1 4 2 二阶段法 第一阶段 目标函数处理成人工变量求和的最小化 Min 用单纯形法求解 直至优化到目标函数值为 即得到初始基本可行解 第二阶段 利用上阶段的初始基本可行解 目标函数换回原来的目标函数 再继续求解直至完成 如果得不到初始基本可行解 则原问题无解 例1 9用两阶段法求解 Max 加入人工变量 例1 9用两阶段法求解 第一阶段目标函数为 Min 标准化为 Max 第二阶段目标函数为 Max 例1 9用两阶段法求解 第一阶段 xBbx1x2x3x4x5x6 CB i Cj0000 1 1 1051181010243201 x5x6 1 1 W 20 7 541000 10 8 10 2 5 45 81 81 811 80 15 23 415 411 40 1 41 x4x6 0 1