《《精编》线性规划问题及单纯形法概述》由会员分享，可在线阅读，更多相关《《精编》线性规划问题及单纯形法概述（66页珍藏版）》请在金锄头文库上搜索。
1、运筹学 OperationsResearch 第一章线性规划及单纯形法 第一章线性规划及单纯形法 线性规划 LinearProgramming 简称LP 运筹学的一个重要分支 是运筹学中研究较早 发展较快 理论上较成熟和应用上极为广泛的一个分支 1947年G B Dantying提出了一般线性规划问题求解的方法 单纯形法之后 线性规划的理论与应用都得到了极大的发展 60年来 随着计算机的发展 线性规划已广泛应用于工业 农业 商业 交通运输 经济管理和国防等各个领域 成为现代化管理的有力工具之一 1线性规划问题及其数学模型 e g 1资源的合理利用问题 问 如何安排生产计划 使得既能充分利用现有
2、资源又使总利润最大 表1产品资源甲乙库存量A1360B1140单件利润1525 某工厂在下一个生产周期内生产甲 乙两种产品 要消耗A B两种资源 已知每件产品对这两种资源的消耗 这两种资源的现有数量和每件产品可获得的利润如表1 第一章线性规划及单纯形法 maxz 15x1 25x2s t x1 3x2 60 x1 x2 40 x1 x2 0 解 设x1 x2为下一个生产周期产品甲和乙的产量 约束条件 Subjectto x1 3x2 60 x1 x2 40 x1 x2 0 目标函数 z 15x1 25x2 表1产品资源甲乙库存量A1360B1140单件利润1525 决策变量 1线性规划问题及其
3、数学模型 e g 2营养问题 假定在市场上可买到B1 B2 Bnn种食品 第i种食品的单价是ci 另外有m种营养A1 A2 Am 设Bj内含有Ai种营养数量为aij i 1 m j 1 n 又知人们每天对Ai营养的最少需要量为bi 见表2 表2食品最少营养B1B2 Bn需要量A1a11a12 a1nb1A2a21a22 a2nb2 Amam1am2 amnbm单价c1c2 cn 试在满足营养要求的前提下 确定食品的购买量 使食品的总价格最低 第一章线性规划及单纯形法 表2食品最少营养B1B2 Bn需要量A1a11a12 a1nb1A2a21a22 a2nb2 Amam1am2 amnbm单价c
4、1c2 cn 解 设xj为购买食品Bj的数量 j 1 2 n i 1 2 m xj 0 j 1 2 n 0 xj lj 1线性规划问题及其数学模型 三个基本要素 Note 1 善于抓住关键因素 忽略对系统影响不大的因素 2 可以把一个大系统合理地分解成n个子系统处理 1 决策变量xj 0 2 约束条件 一组决策变量的线性等式或不等式 3 目标函数 决策变量的线性函数 第一章线性规划及单纯形法 max min z c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn 或 b1a21x1 a22x2 a2nxn 或 b2 am1x1 am2x2 amnxn 或 bmxj 0 j
5、1 2 n 其中aij bi cj i 1 2 m j 1 2 n 为已知常数 1线性规划问题及其数学模型 线性规划问题的标准形式 maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmxj 0 j 1 2 n bi 0 i 1 2 m 特点 1 目标函数为极大化 2 除决策变量的非负约束外 所有的约束条件都是等式 且右端常数均为非负 3 所有决策变量均非负 第一章线性规划及单纯形法 如何转化为标准形式 1 目标函数为求极小值 即为 因为求minz等价于求max z 令z z 即化
6、为 2 约束条件为不等式 xn 1 0松弛变量 如何处理 1线性规划问题及其数学模型 右端项bi 0时 只需将等式两端同乘 1 则右端项必大于零 4 决策变量无非负约束 设xj没有非负约束 若xj 0 可令xj xj 则xj 0 又若xj为自由变量 即xj可为任意实数 可令xj xj xj 且xj xj 0 第一章线性规划及单纯形法 e g 3 试将LP问题 minz x1 2x2 3x3s t x1 x2 x3 7x1 x2 x3 2 3x1 x2 2x3 5x1 x2 0化为标准形式 解 令x3 x4 x5其中x4 x5 0 对第一个约束条件加上松弛变量x6 对第二个约束条件减去松弛变量x
7、7 对第三个约束条件两边乘以 1 令z z把求minz改为求maxz maxz x1 2x2 3x4 3x5s t x1 x2 x4 x5 x6 7x1 x2 x4 x5 x7 23x1 x2 2x4 2x5 5x1 x2 x4 x5 x6 x7 0 1线性规划问题及其数学模型 LP的几种表示形式 2线性规划问题的图解法 定义1在LP问题中 凡满足约束条件 2 3 的解x x1 x2 xn T称为LP问题的可行解 所有可行解的集合称为可行解集 或可行域 记作D x Ax b x 0 定义2设LP问题的可行域为D 若存在x D 使得对任意的x D都有cx cx 则称x 为LP问题的最优解 相应的
8、目标函数值称为最优值 记作z cx 2线性规划问题的图解法 maxz 15x1 25x2s t x1 3x2 60 x1 x2 40 x1 x2 0 40 0 0 0 B C 30 10 O L1 L2 Z 250 目标函数变形 x2 3 5x1 z 25 x2 x1 最优解 x1 30 x2 10最优值 zmax 700 B点是使z达到最大的唯一可行点 第一章线性规划及单纯形法 LP问题图解法的基本步骤 1 在平面上建立直角坐标系 2 图示约束条件 确定可行域和顶点坐标 3 图示目标函数 等值线 和移动方向 4 寻找最优解 2线性规划问题的图解法 maxz 3x1 5 7x2s t x1 1
9、 9x2 3 8x1 1 9x2 3 8x1 1 9x2 11 4x1 1 9x2 3 8x1 x2 0 x1 x2 o x1 1 9x2 3 8 x1 1 9x2 3 8 x1 1 9x2 11 4 7 6 2 D 0 3x1 5 7x2 maxZ minZ 3 8 4 34 2 3x1 5 7x2 可行域 x1 1 9x2 3 8 0 2 3 8 0 绿色线段上的所有点都是最优解 即有无穷多最优解 Zman 34 2 第一章线性规划及单纯形法 maxz 2x1 2x2s t 2x1 x2 2 x1 4x2 4x1 x2 0 O x1 x2 Note 可行域为无界区域 目标函数值可无限增大
10、即解无界 称为无最优解 可行域为无界区域一定无最优解吗 2线性规划问题的图解法 由以上两例分析可得如下重要结论 1 LP问题从解的角度可分为 有可行解 无可行解 有唯一最优解b 有无穷多最优解C 无最优解 2 LP问题若有最优解 必在可行域的某个顶点上取到 若有两个顶点上同时取到 则这两点的连线上任一点都是最优解 2线性规划问题的图解法 图解法优点 直观 易掌握 有助于了解解的结构 图解法缺点 只能解决低维问题 对高维无能为力 3线性规划问题解的基本性质 讨论如下LP问题 其中 系数矩阵 决策向量 假设A的秩为m 且只讨论m n的情形 什么意思 为什么 第一章线性规划及单纯形法 定义3在上述L
11、P问题中 约束方程组 2 的系数矩阵A的任意一个m m阶的非奇异的子方阵B 即 B 0 称为LP问题的一个基阵或基 称pi i 1 2 m 为基向量 xi i 1 2 m 为基变量 xj j m 1 n 为非基变量 pj j m 1 n 为非基向量 记 则A B N 3线性规划问题解的基本性质 A B N xB x1 xm T xN xm 1 xn T 则 代入约束方程 2 得 自由变量 独立变量 令 称 4 为相应于基B的基本解 第一章线性规划及单纯形法 是可行解吗 maxz x1 2x2 3x4 3x5s t x1 x2 x4 x5 x6 7x1 x2 x4 x5 x7 23x1 x2 2
12、x4 2x5 5x1 x2 x4 x5 x6 x7 0 令x1 x2 x4 0 如果B 1b 0 则称 4 为相应于基B的基可行解 此时的基B称为可行基 3线性规划问题解的基本性质 基本解唯一吗 最多有多少 称它是非退化的解 反之 如果有一个基变量也取零值 则称它是退化的解 一个LP问题 如果它的所有基可行解都是非退化的就称该是非退化的 否则就称它是退化的 第一章线性规划及单纯形法 LP问题解的基本性质 Ax 0 定理2 定理3称为LP问题的基本定理 定理2证明 向前 定理3证明 LP问题是一个组合优化问题 3线性规划问题解的基本性质 定理2证明 设x x1 x2 xn T是LP问题的一个可行
13、解 如果x 0 则由定理1知 它是LP问题的一个基可行解 定理成立 如果x 0 不妨设x的前k个分量为非零分量 则有x1p1 x2p2 xkpk b 及x1 0 x2 0 xk 0 分两种情况讨论 如果p1 p2 pk线性无关 即x的非零分量对应的列向量线性无关 则由定理1知 它是LP的一个基本可行解 定理成立 2 如果p1 p2 pk线性相关 则必存在一组不全为零的数 1 2 k使得 第一章线性规划及单纯形法 假定有 i 0 取 作 其中 由 6 式知 必有 即 又因为由 5 式知 故有 即 也是LP的两个可行解 3线性规划问题解的基本性质 再由的取法知 在式 7 的诸式中 至少有一个等于零
14、 于是所作的可行解中 它的非零分量的个数至少比x的减少1 如果这些非零分量所对应的列向量线性无关 则为基可行解 定理成立 否则 可以从出发 重复上述步骤 再构造一个新的可行解 使它的非零分量的个数继续减少 这样经过有限次重复之后 必可找到一个可行解使它的非零分量对应的列向量线性无关 故可行解必为基可行解 证毕 返回 3线性规划问题解的基本性质 定理3证明 设 是LP的一个最优解 如果x 是基本解 则定理成立 如果x 不是基本解 则由定理2的证明过程可构造两个可行解 它的非零分量的个数比x 的减少 且有 又因为x 是最优解 故有 由式 8 和 9 知 必有 即x 1 x 2 仍为最优解 如果x
15、1 或x 2 是基可行解 则定理成立 否则 按定理2证明过程 可得基可行解x s 或x s 1 使得 即得基可行解x s 或x s 1 为最优解 返回 第一章线性规划及单纯形法 LP问题解的几何意义 定义5设集合是n维欧氏空间中的一个点集 如果及实数 则称S是一个凸集 几何意义 如果集合中任意两点连线上的一切点都在该集合中 则称该集合为凸集 Note 空集和单点集也是凸集 3线性规划问题解的基本性质 定义6设则称 为点的一个凸组合 第一章线性规划及单纯形法 定理5设D为LP问题的可行解集 则x是D的极点的充分必要条件是x为LP问题的基可行解 prove 此时 该LP问题有无穷多最优解 3线性规
16、划问题解的基本性质 Note 1 如何判断LP问题有最优解 2 计算复杂性问题 设有一个50个变量 20个约束等式的LP问题 则最多可能有个基 即约150万年 4单纯形法的基本原理 单纯形法 SimplexMethod 是1947年由G B Dantzig提出 是解LP问题最有效的算法之一 且已成为整数规划和非线性规划某些算法的基础 基本思路 基于LP问题的标准形式 先设法找到一个基可行解 判断它是否是最优解 如果是则停止计算 否则 则转换到相邻的目标函数值不减的一个基可行解 两个基可行解相邻是指它们之间仅有一个基变量不相同 第一章线性规划及单纯形法 单纯形法引例 首先 化原问题为标准形式 x3 x4是基变量 基变量用非基变量表示 x3 60 x1 3x2x4 40 x1 x2 代入目标函数 z 15x1 25x2 令非基变量x1 x2 0 z 0基可行解x 0 0 0 60 40 T 是最优解吗 maxz 15x1 25x2s t x1 3x2 60 x1 x2 40 x1 x2 0 maxz 15x1 25x2 0 x3 0 x4s t x1 3x2 x3 60 x1 x2 x4
