运筹学线性规划与单纯形法ppt课件.ppt

第一章线性规划及单纯形法 LinearProgramming 简称LP 线性规划的发展1947年 丹 捷格提出求解线性规划的单纯形法 SimpleMethod 1950 1956年 主要研究线性规划的对偶理论1958年 发表整数规划的割平面法1960年 Dantzig和Wolfe研究成功分解算法 奠定了大规模线性规划问题理论和算法的基础 1979年 Khachiyan 1984年 Karmarkaa研究成功线性规划的多项式算法 理论上日益成熟 计算技术简单 应用广泛 现代管理科学的重要基础和手段之一 1 1一般线性规划问题的数学模型一 问题的提出1 规划问题 在有限资源的条件下 合理分配和利用资源 以期取得最佳的经济效益的优化方法 例1 用一块边长为a的正方形铁皮做一个容器 应如何裁剪 使做成的容器的容积为最大 V a 2x 2 x用微积分中求极值的古典方法解决 古典方法不是规划问题 只处理简单的表达式和简单的约束条件 2 例2 某厂生产两种产品 下表给出了单位产品所需资源及单位产品利润 问 应如何安排生产计划 才能使总利润最大 3 解 用数学的语言进行描述 1 决策变量 设产品I II的产量分别为x1 x22 目标函数 问题要求获取利润最大 该公司获取利润为2x1 3x2 令z 2x1 3x2 则maxz 2x1 3x2 maxz是该公司获取利润的目标值 它是变量x1 x2的函数 称为目标函数 3 约束条件 两种产品受设备制造能力的限制 可用不等式表示为 4 综合例2的数学模型可表示为 maxz 2x1 3x2这是一个典型的利润最大化的生产计划问题 其中 Max 是英文单词 Maximize 的缩写 含义为 最大化 s t 是 subjectto 的缩写 表示 满足于 因此 上述模型的含义是 在给定条件限制下 求使目标函数z达到最大的x1 x2的取值 5 2 线性规划研究的主要问题 可以归纳为两类 一类是已有一定数量的资源 人力 物质 时间等 研究如何充分合理地使用它们 才能使完成的任务量为最大 另一类是当一项任务确定以后 研究如何统筹安排 才能使完成任务所耗费的资源量为最少 实际上 上述两类问题是一个问题的两个不同的方面 都是求问题的最优解 max或min 6 例3 某厂生产三种药物 这些药物可以从四种不同的原料中提取 下表给出了单位原料可提取的药物量 要求 生产A种药物至少160单位 B种药物恰好200单位 C种药物不超过180单位 且使原料总成本最小 解 1 决策变量 设四种原料的使用量分别为 x1 x2 x3 x42 目标函数 设总成本为z 则有 minz 5x1 6x2 7x3 8x43 约束条件 7 二 线性规划问题的数学模型 一 LP问题数学模型由三个要素组成1 变量 或称为决策变量 是问题中要确定的未知量 表示规划中要采取的方案 措施 可由决策者决定和控制 2 目标函数 实现的目标 是决策变量的函数 按照优化目标加上最大或者最小 3 约束条件 是变量取值时受到的各种资源条件的限制 通常表达为含决策变量的线性等式或线性不等式 所谓线性的是指 目标函数与约束条件均为一次的 8 二 LP的条件或LP数学模型的特点1 数学模型由变量 目标函数和约束条件三部分组成 2 决策变量为可控的连续变量 3 目标函数和约束条件都是线性的 满足以上三个条件的数学模型称为线性规划 9 三 线性规划数学模型的几种形式n个变量xj j 1 2 3 n xj一般非负 从数学意义上可以有xj 0 这时xj的取值为 称xj取值不受约束或无约束 价值系数cj 资源系数bi i 1 2 3 m 资源拥有量 xj受m项资源的限制 工艺系数 约束系数 aij表示xj取值一个单位时消耗的或所含有的第j种资源的数量 由技术条件决定 10 1 一般形式目标函数 max min Z c1x1 c2x2 c3x3 cnxn约束条件 a11x1 a12x2 a13x3 a1nxn b1a21x1 a22x2 a23x3 a2nxn b2 am1x1 am2x2 am3x3 amnxn bmx1 0 x2 0 xn 0 11 2 简写形式3 向量形式4 矩阵形式 系数矩阵 工艺系数 决策变量 价值系数 常数项 资源系数 12 三 线性规划的标准形式maxZ cjxj aijxj bii 1 2 mxj 0j 1 2 n可以看出 线性规划的标准形式有如下四个特点 目标最大化 约束条件全为等式 决策变量均非负 右端项非负 对于各种非标准形式的线性规划问题 我们总可以通过以下变换 将其转化为标准形式 13 1 目标函数极小化转为极大化 minZ max Z 一个数的极小化等价于其相反数的极大化 令Z Z 则Z cjxj于是转化为 maxZ cjxj 约束条件不变 2 约束为不等式 可利用添加松弛变量 变为等式 不等式约束的转化 aijxj bi加入非负的松弛变量 aijxj bi减去非负的剩余变量松弛变量和剩余变量在目标函数中的系数均为0 3 取值无约束的变量 即x无约束 变为两个变量的差即令x x x 其中x 0 x 0 4 变量xj 0 令xj xj 则xj xj 代入即可 5 bi 0 该约束条件两边同乘以 1 14 练习题 将下列问题化成标准型 1 minZ x1 2x2 3x3x1 x2 x3 9 x1 2x2 x3 23x1 x2 3x3 5x1 0 x2 0 x3无约束 2 MinZ x1 2x2 3x3x1 x2 x3 7x1 x2 x3 2 3x1 x2 2x3 5x1 x2 0 x3无非负限制 15 解 maxZ x1 2x2 3 x3 x3 0 x4 0 x5 x1 x2 x3 x3 x4 9x1 2x2 x3 x3 x5 23x1 x2 3 x3 x3 5x1 0 x2 0 x3 0 x3 0 x4 0 x5 0 16 MaxZ x1 2x2 3x3 3x3 0 x4 0 x5s t x1 x2 x3 x3 x4 7x1 x2 x3 x3 x5 2 3x1 x2 2x3 2x3 5x1 x2 x3 x3 x4 x5 0第一节小结 建立模型 三个组成要素 四种形式 化为标准形 4个条件5点 17 2线性规划图解法 图解法简单 直观 有利于理解LP求解的基本原理 基本思路 缺点 只适合两个变量 一 图解法的步骤1 画出坐标系 以x1为横轴 x2为纵轴2 图示约束条件 找出可行域 所有约束条件的公共部分 3 图示目标函数的直线 标出目标函数值增加 或减小 的方向 4 确定最优解 若求最大 小 值 则令目标函数等值线沿 逆 目标函数值增加的方向平行移动 找与可行域最后相交或相切的点 该点就是最优解 5 将最优解代入目标函数 求出最优值 18 求解书上例题 x2 x1 最优解 X 4 2 T最优值 Z 14 O Q1 Q2 Q3 Q4 19 maxZ 50 x1 30 x2s t 4x1 3x2 1202x1 x2 50 x1 x2 0 线性规划的图解法 例4 LP模型 20 x2 50 40 30 20 10 10 20 30 40 x1 4x1 3x2 120 由4x1 3x2 120 x1 0 x2 0围成的区域 21 x2 50 40 30 10 10 20 30 40 x1 2x1 x2 50 由2x1 x2 50 x1 0 x2 0围成的区域 20 22 x2 50 40 30 20 10 10 20 30 40 x1 2x1 x2 50 4x1 3x2 120 可行域 同时满足 2x1 x2 504x1 3x2 120 x1 0 x2 0的区域 可行域 23 x2 50 40 30 20 10 10 20 30 40 x1 可行域 O 0 0 Q1 25 0 Q2 15 20 Q3 0 40 可行域是由约束条件围成的区域 该区域内的每一点都是可行解 它的全体组成问题的解集合 该问题的可行域是由O Q1 Q2 Q3作为顶点的凸多边形 24 x2 50 40 30 20 10 10 20 30 40 x1 可行域 目标函数是以Z作为参数的一组平行线x2 Z 30 5 3 x1 25 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当Z值不断增加时 该直线x2 Z 30 5 3 x1沿着其法线方向向右上方移动 26 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当该直线移到Q2点时 Z 目标函数 值达到最大 MaxZ 50 15 30 20 1350此时最优解 15 20 Q2 15 20 27 线性规划的图解法 Maxz x1 3x2s t x1 x2 6 x1 2x2 8x1 0 x2 0 可行域 目标函数等值线 最优解 6 4 8 6 0 x1 x2 例5 28 maxZ 70X1 120X29X1 4X2 3604X1 5X2 2003X1 10X2 300X1 0 X2 0 线性规划的图解法 例6 29 9080604020 020406080100 x1 x2 9x1 4x2 360 4x1 5x2 200 3x1 10 x2 300 A B C D E F G H I Z 70 x1 120 x2 maxZ 70X1 120X29X1 4X2 3604X1 5X2 2003X1 10X2 300X1 0 X2 0 30 二 解的几种可能情况1 唯一最优解 目标函数直线与凸多边形只有一个切点 2 无穷多最优解 目标函数图形与某个约束条件平行 3 无界解 无最优解 可行域无界 一般是漏了一些约束条件 4 无可行解 可行域为空 31 解的讨论 无穷多组最优解 例7 目标函数由maxZ 50 x1 30 x2变成 maxX 40 x1 30 x2s t 4x1 3x2 1202x1 x2 50 x1 x2 0 32 x2 50 40 30 20 10 10 20 30 40 x1 可行域 目标函数是同约束条件 4x1 3x2 120平行的直线x2 Z 30 4 3 x1 33 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当Z的值增加时 目标函数同约束条件 4x1 3x2 120重合 Q1与Q2之间都是最优解 Q1 25 0 Q2 15 20 34 解的讨论 无界解 例8 maxZ x1 x2s t 2x1 x2 40 x1 x2 20 x1 x2 0 35 x2 50 40 30 20 10 10 20 30 40 x1 该可行域无界 目标函数值可增加到无穷大 称这种情况为无界解或无最优解 36 解的讨论 无可行解 例9 maxZ 2x1 3x2s t x1 2x2 8x1 4x2 3 2x1 x2 4x1 x2 0 该问题可行域为空集 即无可行解 也不存在最优解 37 解的情况 有最优解 有唯一最优解 有无穷最优解无最优解 无界解 无可行解 38 解的情况 有可行解 有唯一最优解 有无穷最优解 无界解无可行解 39 三 图解法的启示1 LP解有四种情况 2 若可行域存在 则可行域是一个凸集 这一事实可以推广到更多变量的场合 3 最优解存在于可行域 凸集 的某个顶点 4 解题思路 40 课后习题1 4a1 c d 0时 此时点O A B C都是最优解 2 1 c 0 d 0时 目标函数等值线x2 z d 点C为最优解 2 c 0 d 0时 目标函数等值线x2 z d 点O A为最优解 3 1 d 0 c 0时 目标函数等值线x1 z c 点A为最优解 2 d 0 c 0时 目标函数等值线x1 z c 点O C为最优解 4 1 c 0 d 0时 x2 cx1 d z d c d 5 2时 点A为最优解 c d 5 2时 点A B为最优解 3 4 c d 5 2时 点B为最优解 c d 3 4时 点B C为最优解 c d 3 4时 点C为最优解 2 c 0 d 0时 x2 cx1 d z d 点A为最优解 3 c 0 d 0时 x2 cx1 d z d 点O为最优解 4 c 0 d 0时 x2 cx1 d z d 点C为最优解 41 3单纯形法原理 1 可行解 feasiblesolution 满足LP约束条件的解称为可行解 一 线性规划问题解的几个概念 针对标准形 2 最优解 optimalsolution 使线性规划目标函数达到最优的可行解称为最优解 4 基解 basicsolution 以线性规划约束等式的系数矩阵A中任意m行m列组成的m m满秩子矩阵为基矩阵 与基矩阵相对应的变量称为基变量 basicvariable 其余变量称为非基变量 令非基变量为零 可求得基变量的值 这样求出的解称为基解 基本解 5 基可行解 basicfeasiblesolution 满足非负约束的基解称为基可行解 若约束等式中有n个变量 m个约束 则基本解的个数 3 基 radix 设约束方程组的系数矩阵A的秩为m 且m n 设A B N B是A中m m阶满秩子矩阵 非奇异子矩阵 B 0 则称B是LP的一个基 即 B是A中m个线性无关向量组 6 可行基 feasiblebasis 对应于基可行解的基 42 线性规划的基本概念 线性规划的基矩阵 基变量 非基变量 目标函数 约束条件 行列式 0基矩阵 右边常数 43 解的集合 可行解 基解 基最优解 基可行解 44 线性规划解之间的关系可行解与最优解 最优解一定是可行解 但可行解不一定是最优解 2 可行解与基解 基解不一定是可行解 可行解也不一定是基解 3 可行解与基可行解 基可行解一定是可行解 但可行解不一定是基解 4 基解与基可行解 基可行解一定是基解 但基解不一定是基可行解 5 最优解与基本解 最优解一定是基解 基解不一定是最优解 45 例10 基解Maxz 1500 x1 2500 x2s t 3x1 2x2 x3 652x1 x2 x4 403x2 x5 75x1 x2 x3 x4 x5 0注意 线性规划的基本解 基本可行解 极点 和可行基只与线性规划问题标准形式的约束条件有关 46 32100A P1 P2 P3 P4 P5 2101003001A矩阵包含以下10个3 3的子矩阵 B1 p1 p2 p3 B2 p1 p2 p4 B3 p1 p2 p5 B4 p1 p3 p4 B5 p1 p3 p5 B6 p1 p4 p5 B7 p2 p3 p4 B8 p2 p3 p5 B9 p2 p4 p5 B10 p3 p4 p5 47 其中 B4 0 因而B4不是该线性规划问题的基 其余均为非奇异方阵 因此该问题共有9个基 对于基B3 p1 p2 p5 令非基变量x3 0 x4 0 在等式约束中令x3 0 x4 0 解线性方程组 3x1 2x2 0 x5 652x1 x2 0 x5 400 x1 3x2 x5 75得到x1 15 x2 10 x5 45 对应的基本可行解 x x1 x2 x3 x4 x5 T 15 10 0 0 45 T 于是对应的基B3是一个可行基 48 类似可得到x 2 5 25 0 5 0 T 对应B2 x 7 20 0 5 0 75 T 对应B5 x 8 0 25 15 15 0 T 对应B7 x 9 0 0 65 40 75 T 对应B10 是基本可行解 而x 3 0 32 5 0 7 5 22 5 T 对应B9 x 4 65 3 0 0 10 3 75 T 对应B6 x 5 7 5 25 7 5 0 0 T 对应B1 x 6 0 40 15 0 45 T 对应B8 是基本解 49 例11 基解 参考 50 基变量x1 x2 x3 非基变量x4 x5 x6 基解为 x1 x2 x3 x4 x5 x6 5 3 1 0 0 0 是基可行解 表示可行域的一个极点 目标函数值为 z 20 51 基变量x1 x2 x4 非基变量x3 x5 x6 基解为 x1 x2 x3 x4 x5 x6 27 5 12 5 0 2 5 0 0 是基可行解 表示可行域的一个极点 目标函数值为 z 18 52 基变量x1 x2 x5 非基变量x3 x4 x6 基本解为 x1 x2 x3 x4 x5 x6 6 3 0 0 3 0 是基本解 但不是可行解 不是一个极点 53 基变量x1 x2 x6 非基变量x3 x4 x5 基本解为 x1 x2 x3 x4 x5 x6 3 4 0 0 0 4 是基本可行解 表示可行域的一个极点 目标函数值为 z 18 54 基变量x2 x3 x4 非基变量x1 x5 x6 基本解为 x1 x2 x3 x4 x5 x6 0 21 2 27 2 30 0 0 是基本解 但不是可行解 55 基变量x1 x2 x3 非基变量x4 x5 x6 基本解为 x1 x2 x3 x4 x5 x6 0 3 6 0 15 0 是基本可行解 表示可行域的一个极点 目标函数值为 z 15 56 基变量x1 x2 x3 非基变量x4 x5 x6 基本解为 x1 x2 x3 x4 x5 x6 0 11 2 3 2 0 0 10 是基本解但不是可行解 57 例12 找出下述线性规划问题的全部基解 指出其中的基可行解 并确定最优解 maxZ 2X1 3X2 X3X1 X3 5X1 2X2 X4 10X2 X5 4Xj 0 j 1 2 3 4 5 58 解 该LP的全部基解见下表 打 者为基可行解 注 者为最优解 59 例13 已知线性规划问题maxZ X1 3X2X1 X3 5 X1 2X2 X4 10 X2 X5 4 Xj 0 j 1 2 3 4 5 下表中所列的解 a f 均满足约束条件 试指出表中哪些解是可行解 哪些是基解 哪些是基可行解 60 二 凸集和顶点1 凸集 设C是一个集合 X1与X2是C中任意两点 如果X X1 1 X2 0 1 也是C中的点 称C是一个凸集 几何意义 任意两点连线上的点都是C的点 为什么X1 X2连线上的点可以如此表示 n维欧氏空间 线性空间 令 X X2 X1 X2 0时 X X2 右端点 1时 X X1 左端点0 1时 X1与X2之间任一点 X2 X X1 61 例 凸集 62 例 非凸集 63 例 凸集性质 二个凸集的交还是凸集 二个凸集的并不一定是凸集 64 2 顶点 设d是C中的点 但d不在C中任何两点的连线上 则称d是C的一个顶点 例 多边形上的点是顶点 圆周上的点都是顶点 65 可行域的性质 线性规划的可行域是凸集线性规划的最优解在顶点上 凸集 凸集 不是凸集 顶点 66 三 几个基本定理 一般形式 标准形式均适用 定理一 若线性规划问题存在可行解 则可行域是凸集 可行域的几何特征 图解法直观印象的一个推广 理论上加以肯定 证明思路 按照凸集的定义 可行域内任意两点的连线仍在可行域内 引理 LP的可行解X x1 xn T为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的 必要性 基可行解 线性独立充分性 线性独立 基可行解 67 定理二 LP问题的基可行解对应线性规划问题可行域 凸集 的顶点 证明思路 可行域顶点基可行解 1 X不是基可行解X不是可行域顶点 2 X不是可行域顶点X不是基可行解定理三 若LP问题有最优解 一定存在一个基可行解是最优解 前三个定理的递进关系 1 可行解 2 基可行解 3 最优解意义 线性规划的最优解 在可行域的顶点上找 理论上 只要找出可行域的所有顶点 然后比较目标值 即可找到最优解 但要找顶点 则需要找到基 问题是在技术上如何去实现 68 定理四 若LP在可行域的两个顶点上达到最优 则在两个顶点的连线上也达到最优 定理五 LP问题的一般形式与标准形式等价 即二者解的情形是完全对应相同的 学习几个定理的思考 学习关于LP的几个基本定理 目的也让我们想一下 LP问题看上去似乎简单 可是为什么一直到20世纪中期才得以解决 在解决的过程中遇到了哪些问题 他们是如何一步一步解决的 了解这一发展过程 也使我们想一下以前的人们分析问题 处理问题的方法 这种方法和思路对我们自己今后工作和学习是有帮助的 69 四 单纯形法迭代原理思路 从一个基可行解出发 如何去找一个基可行解 判断其是否为最优解 如何判断 若不是 则转换到相邻的基可行解 如何转换 并使目标函数值不断增大 一直找到最优解为止 70 步骤 一 确定初始基可行解问题是如何找到满秩的单位矩阵 1 当所有约束是 时 可通过加一些松弛变量来实现 2 当约束是 或 时 化为标准形后 一般约束条件的系数矩阵中不含单位矩阵 这时可以添加人工变量 构造人工基 人为产生一个单位矩阵 具体方法在后面介绍 结论 不管在什么情况下 初始基可行解总可以找到 71 二 基可行解的改进 从一个基可行解转换为另一 相邻的 基可行解 如何转换 定义 两个基可行解是相邻的 如果他们之间变换且仅变换一个基变量 设初始基可行解的前m个为基变量 即X X1 X2 Xm 0 0 T 记 Pj a1j a2j amj T j 1 2 n 为约束系数矩阵的列向量 则P1 P2 Pm为单位向量 设Pi是第i个分量 P1 P2 Pm构成单位矩阵 又记b b1 b2 bm T为常数向量 于是有 72 P1X1 P2X2 PmXm b1 又因P1 P2 Pm是一个基 其它向量Pj可用这个基的线性组合来表示 有 Pj a1jP1 a2jP2 amjPm或Pj a1jP1 a2jP2 amjPm 02 将2 乘一个正数 0得 Pj a1jP1 a2jP2 amjPm 03 3 1 整理后得 X1 a1j P1 X2 a2j P2 Xm amj Pm Pj b4 73 于是得到满足等式约束条件的另一个解Y 有 Y X1 a1j X2 a2j Xm amj 0 0 现在我们把此解转换为基可行解 需要两个条件 所有分量 0 在前m个分量中至少某一个为0 1 若aij 0 则对应的分量 0 因此只需要使aij 0对应的分量 0即可 只要取 min Xi aij aij 0 i 1 m Xl alj2 此时 Xl alj Xl Xl alj alj 0 且其他分量 0从而Y是一个基可行解 且X与Y是相邻的 对约束方程的增广矩阵 Ab 进行初等变换 使Pj成为单位向量 变换后第l列出基 第j列入基 然后再检验Y是否最优解 从上述过程 我们可以得到单纯形法解的转换的一般步骤 74 三 最优性检验和解的判别 已经得到一个基可行解 判断其是否最优解 设X是任意一个基可行解 P P1 P2 Pm 是X对应的单位基矩阵 记A PD X XPXD C CPCD 于是由AX b可得到 PXP DXD b XP b DXD 给XD不同的值 就会得到不同的解 其式表示约束方程的所有解 令XD 0 则得到一个基可行解 b0 现在我们检验其是否为最优解 CX CPXP CDXD CP b DXD CDXD CPb CD CPD XD显然 只要CD CPD中有一个分量 0 则X就不是最优解 下面我们写出CD CPD的各个分量 n m 个 第j个为 cj c1a1j c2a2j cmamj j m 1 m 2 n 记 j cj zj cj ciaij cj c1a1j c2a2j cmamj 称为最优性检验数 75 z 1 z 0 cj ciaij 检验数 j cj c1a1j c2a2j cmamj cj ciaij cj zj结论 适用于无人工变量的问题 1 若所有 j 0 表明现有顶点 基可行解 为最优解 2 若所有 j 0 且有某个非基变量的 j 0 则有无穷多个解当所有非基变量 j0 则不是最优解 可以改进 若同时又有该正的检验数相应变量的系数Pj 0 即没有正数 则线性规划有无界解 4 无可行解的判别后面第5节讲 76 单纯形法原理总结 我们知道在标准形中 找一个单位基矩阵并求出该基对应的基可行解 检验该基可行解是否最优 通过非基变量的检验数 若不是最优 则旋转找另一个基可行解 直到最优 对此原理 我们可以通过单纯形表来实现 77 单纯形法的基本过程 78 单纯形表的格式 4单纯形法的计算步骤 79 教材上例5之初始单纯形表 80 例14 下表中给出一个求最大化问题的单纯形表 问表中字母取何值时有 a 表中解为最优解 b 表中解为唯一最优解 c 表中解无穷多最优解之一 d 该LP具有无界解 e 该LP不是最优解 a a 0 b 0 b a0 c 0 e a b中至少一个大于0 81 单纯形法的计算步骤一 求一初始基可行解 列出初始单纯形表 二 最优性检验 1 如果所有检验数 0 则所得基可行解即为最优解 2 如果存在检验数 0 则该可行解不是最优解 转下一步 表示解可以改进 三 换基迭代 转换基可行解 从一基可行解转换到相邻的目标函数值更大的基可行解 列出新的单纯形表 1 取 j 0最大者 k 对应的变量Xk为进基变量 换入变量 2 用Xk所在列中正系数去除相应b列中数 选取比值最小者对应的基变量 Xl 作为出基变量 换出变量 3 以alk为主元素做初等行变换 把主元素alk化为1 所在列其他元素 包括检验数 化为0 得到新的基可行解和新基 并相应画出一张新的单纯形表 四 重复二 三步骤 直到计算结束 82 进基 出基 教材上例5之初始单纯形表 83 目标函数 约束条件 基矩阵 右边常数 进基变量 离基变量 基变换 基变量 84 进基变量 离基变量 目标函数 约束条件 右边常数 85 目标函数 约束条件 新的基矩阵 右边常数 86 进基变量 离基变量 目标函数 约束条件 基矩阵 87 目标函数 约束条件 新的基矩阵 右边常数 88 例5各基可行解和图解法中可行域的顶点的一一对应关系X1 0 0 12 8 16 12 TZ1 0X2 0 3 6 2 16 0 TZ2 9X3 2 3 2 0 8 0 TZ3 13X4 4 2 0 0 0 4 TZ1 14P11图 X1 O X2 Q4 X3 Q3 X4 Q2 89 例15 求解线性规划问题 可以参考叙述方式 解 化为标准形式 MAXZ 2X1 X2MAXZ 2X1 X2 0X3 0X4 0X55X2 155X2 X3 15st 6X1 2X2 24st 6X1 2X2 X4 24X1 X2 5X1 X2 X5 5X1 0 X2 0Xi 0 i 1 2 3 4 5 90 于是 得到一个基可行解X 0 0 15 24 5 T此时 基变量为 X3 X4 X5 非基变量为 X1 X2 非基变量的检验数为 2 1 不是最优解我们可以列初始单纯形表如下 91 进基 出基 X1 0 0 15 24 5 TZ1 0X4换出 X1换入 得到一组新的基变量X3 X1 X5 对此表做初等行变换 画出新的单纯形表 92 X2 4 0 15 0 1 TZ2 8仍非最优解 X2换入 X5换出 画出新的单纯形表 93 此时 非基变量检验数全部 0 于是得到最优解为 X 7 2 3 2 15 2 0 0 T 最优值为 Z 17 2 94 注意 单纯形法中 1 每一步运算只能用矩阵初等行变换 2 表中第3列 b列 的数总应保持非负 0 3 当所有检验数均非正 0 时 得到最优单纯形表 4 基变量下面对应单位向量 5 基变量检验数为0 6 检验数用定义和初等行变换两种方法求都可以 7 基解和图解法凸集的顶点一一对应 8 解的退化 当选择换出变量求比值时 有两个相同的最小比值 任选一个基变量作为换出变量 则下面表中另一基变量的值将等于0 这种现象成为退化 含一个或多个基变量为0的基可行解为退化的基可行解 出现退化解时 可以随意决定哪一个变量为换出变量 不必考虑理论上可能出现的循环的后果 95 maxZ 70X1 120X2P1P2P3P4P59X1 4X2 X3 360941004X1 5X2 x4 200A 450103X1 10X2 x5 300310001Xj 0j 1 2 5 例16 此例可以作为课外参考 96 97 例17 下表为用单纯形法计算时某一步的表格 已知该线性规划的目标函数为maxZ 5X1 3X2 约束形式都为 X3 X4为松弛变量 表中解代入目标函数后得Z l0 a 求a一g的值 b 表中给出的解是否为最优解 用到三点 1 把解代入目标函数 2 基变量下面对应单位向量 而且基变量检验数为0 3 用定义求非基变量的检验数 98 a 求a一g的值 b 表中给出的解是否为最优解 a 7 b 6 c 0 d 1 e 0 f 1 3 g 0 例18 下表中给出某线性规划问题计算过程中的一个单纯形表 目标函数为maxZ 28X4 X5 2X6 约束条件都为 表中X1 X2 X3为松弛变量 表中解的目标函值为Z 14 99 一 人工变量法 大M法 在前面我们假设标准形中存在一个单位矩阵 但在实际问题中往往不存在 我们是否有办法解决 当LP化为标准形后 约束方程的系数矩阵中不存在M阶单位矩阵作为初始基 引入适当的人工变量 使得系数矩阵中含有单位矩阵 此时规定人工变量在目标函数中的系数为 M M为无穷大的正数 然后可用单纯形法求得其最优解 maxZ cjxj Mxn i方法两句话 约束条件引入人工变量 目标函数中人工变量系数为 M 5单纯形法的进一步探讨 100 注意三点 1 最优解中人工变量必须为零 因此Z要实现最优解 必须把人工变量从基变量中换出 否则不能使Z值实现最优 2 M作为一个数学符号一起参加运算 3 变化后的问题的最优解中含有非零的人工变量 则原问题无可行解 101 例19 求下列线性规划问题 参考叙述方式 MAXZ 3X1 X2 X3X1 2X2 X3 11st 4X1 X2 2X3 3 2X1 X3 1X1 0 X2 0 X3 0 102 解 约束条件中引入松弛变量 剩余变量和人工变量 得到MAXZ 3X1 X2 X3 MX6 MX7X1 2X2 X3 X4 11 4X1 X2 2X3 X5 X6 3st 2X1 X3 X7 1XI 0 I 1 7X4 X6 X7为基变量 令非基变量X1 X2 X3 X5 0 得初始基可行解X 0 0 0 0 4 0 1 9 T列出初始单纯形表 单纯形法求解过程如下 103 104 105 106 最优解为X 4 1 9 0 0 0 0 T 最优值为 Z 2 107 例20 大M法Maxz 5x1 2x2 3x3 x4 Mx5 Mx6s t x1 2x2 3x3 x5 152x1 x2 5x3 x6 20 x1 2x2 4x3 x4 26x1 x6 0 108 大M法 了解一下其它形式 得到最优解 25 3 10 3 0 11 T最优目标值 112 3 109 二 两阶段法原因 克服计算机求解时的麻烦 引进两阶段法方法 构造目标函数 分两个阶段求解第一阶段 判别有无可行解 不考虑原LP是否存在基可行解 给其加入人工变量并构造仅含人工变量的目标函数 人工变量系数为1 和要求实现最小化 即引入人工变量xn i 0 i 1 m 构造 MinW xn 1 xn 2 xn m两句话 约束条件与大M方法相同 目标函数实现最小化 为人工变量相加 用单纯形法求解如果W 0 这时候的最优解就是原线性规划的一个可行解 说明原问题存在基可行解 这时 可以进行第二阶段的运算 否则原问题无可行解 停止计算 110 第二阶段 在第一阶段的最优表中去掉人工变量列 目标函数换成原来的目标函数再进行换基迭代 直到求出最优解 思考 为什么可以在原来的表上继续往下计算 而不用从头算 从头算行吗 点评 两阶段法十分巧妙 第一阶段判断LP有无可行解 第二阶段利用第一阶段计算的单纯形表继续往下计算 111 第一阶段问题MaxW x5 x6s t x1 2x2 3x3 x5 152x1 x2 5x3 x6 20 x1 2x2 4x3 x4 26x1 x2 x3 x4 x5 x6 0 例21 两阶段法 112 第一阶段 得到最优解为 0 15 7 25 7 52 7 0 0 T最优目标值 0 113 第二阶段 得到原问题的最优解 25 3 10 3 0 11 T最优目标值 112 3 114 例22 已知线性规划问题minz 5x1 6x2 7x3 x1 5x2 3x3 15 5x1 6x2 10 x3 20 x1 x2 x3 5x1 0 x2 0 x3无约束要求 1 化为标准形式 2 分别列出用大M法求解时的初始单纯形表和两阶段法求解时第一阶段的初始单纯形表 115 解 令x1 x1 x3 x3 x3 x3 x3 0 z z 则maxz 5x1 6x2 7 x3 x3 0 x4 0 x5 Mx6 Mx7 x1 5x2 3x3 3x3 x4 x6 15x1 6x2 10 x3 10 x3 x5 20 x1 x2 x3 x3 x7 5x1 x2 x3 x3 x4 x5 x6 x7 0 116 三 关于解的判别1 无穷多最优解 若所有 j 0 且有某个非基变量的 j 0 则有无穷多个解 当所有非基变量 j0 若同时又有该正的检验数相应变量的系数Pj 0 即没有正数 则线性规划有无界解 3 无可行解 当添加人工变量求解时 如果出现所有 j 0 其基变量中仍含有非零的人工变量 或两阶段法求解时候第一阶段W O 表明问题无可行解 117 例23 下表中给出一个求最大化LP问题的单纯形表 x5为人工变量 问表中d a1 a2 c1 c2分别为何值时 a 表中解为唯一最优解 b 表中解无穷多最优解之一 c 表中解为退化的可行解 d 下一步将以x1替换基变量x5 e 该LP具有无界解 f 该LP无可行解 a d 0 c10 c1 0 d 4 3 a2 d c1 0 3 a20 d 0 e c2 0 a1 0 f x5为人工变量 c1 0 c2 0 118 a 表中解为唯一最优解 d 0 c10 c1 0 d 4 3 a2 d 下一步将以x1替换基变量x5 c1 0 3 a20 d 0 e 该LP具有无界解 c2 0 a1 0 f 该LP无可行解 x5为人工变量 c1 0 c2 0 119 四 单纯形法小结1 对给定的LP首先化为标准形 选取或构造一个单位矩阵作为基 找初始可行基 松弛变量法或人工变量法 2 求初始检验数 列单纯形表 1 确定进基变量 最大检验数对应的列 2 确定出基变量 min bi aik aik 0 做初等行变换 说明 如果 有些书中 求MinW 所有 j 0 求得最优解 120 1 6单纯形法计算的矩阵描述 假定LP问题 maxZ cjxj aijxj bii 1 2 mxj 0j 1 2 n用矩阵形式加上松弛变量为 maxZ CX 0XsAX IXs bX 0 Xs 0其中Xs为松弛变量Xs xn 1 xn 2 xn m T I为m m单位矩阵 单纯形法计算时 总选取I为初始基 对应基变量为Xs 设迭代若干步后 基变量为XB XB在初始表中系数矩阵为B 将B在初始单纯形表中单独列出 而A中去掉B的若干列后 剩下的列组成矩阵N 这样其初始单纯形表可以表示为如下形式 121 当迭代后基变量为XB时 其在初始单纯形表中系数矩阵为B 则有 1 单位矩阵 B 12 基变量XS b XB B 1b3 约束系数矩阵 B N B 1N B 1 4 如果原表中变量的系数为向量Pj 迭代后为Pj B 1Pj5 检验数变为 CN CBB 1N和 CBB 1 也可根据定义得出 当迭代若干步后 基变量为XB时 则该步的单纯形表中由XB系数组成的矩阵I Xs的系数矩阵为B 1 因为单纯形法的迭代是对约束增广矩阵进行的初等行变换 故当基变量为XB时 新的单纯形表为 122 例24 已知下表是某求极大化LP的初始单纯形表和迭代计算中某一步的单纯形表 求出表中a l的值 123 1 7应用举例 线性规划数学模型的建立建立模型是运筹学方法的核心和精髓 一 建模条件 1 优化条件 问题所要达到的目标能用线型函数描述 且能够用极值 max或min 来表示 2 限定条件 达到目标受到一定的限制 且这些限制能够用决策变量的线性等式或线性不等式表示 3 选择条件 有多种可选择的方案供决策者选择 以便找出最优方案 124 二 建模步骤 1 确定决策变量 即需要我们作出决策或选择的量 一般情况下 题目问什么就设什么为决策变量 2 写出目标函数 即问题所要达到的目标 并明确是max还是min 3 找出所有限定条件 即决策变量受到的所有的约束 125 三 建模案例线性规划的应用 一 合理利用线材问题 如何下料使用材最少 二 方案选择问题 三 配料问题 在原料供应量的限制下如何获取最大利润 四 劳动力安排 用最少的劳动力来满足工作的需要 五 产品生产计划 合理利用人力 物力 财力等 使获利最大 六 投资问题 从投资项目中选取方案 使投资回报最大 七 运输问题 如何制定调运方案 使总运费最小 126 例25 某工厂要做100套钢架 每套有长为2 9m 2 1m 1 5m的圆钢各一根 已知原料每根长7 4m 问 应如何下料 可使所用原料最省 一 合理利用线材问题 套裁下料问题 解 考虑下列各种下料方案 按一种逻辑顺序给出 把各种下料方案按剩余料头从小到大顺序列出 127 假设x1 x2 x3 x4 x5分别为上面前5种方案下料的原材料根数 我们建立如下的数学模型 目标函数 MinZ 0 x1 0 1x2 0 2x3 0 3x4 0 8x5约束条件 s t x1 2x2 x4 1002x3 2x4 x5 1003x1 x2 2x3 3x5 100 x1 x2 x3 x4 x5 0 128 二 方案选择问题 例26 j个阶段 rj个专用工具慢修b元p个阶段快修c元 c b q阶段 qc 求总费用最小 解 设xjyjzj 1 rj yj zj sj sj 1 2 3个式子 3 2个式子 4 总费用 129 例27 解 如何设变量maxZ 毛收入 原料成本X11 x21 x31 甲糖果的重量 甲糖果仅由此三种原料构成X12 x22 x32 乙糖果的重量X13 x23 x33 丙糖果的重量X11 x12 x13 A原料的重量X21 x22 x23 B原料的重量X31 x32 x33 C原料的重量在糖果甲中原材料A 60 在糖果甲中原材料C 20 x11 0 6 X11 x21 x31 x31 0 2 X11 x21 x31 三 配料问题 130 例28 某工厂要用三种原料1 2 3混合调配出三种不同规格的产品甲 乙 丙 数据如下表 问 该厂应如何安排生产 使利润收入为最大 131 解 设xij表示第i种 甲 乙 丙 产品中原料j的含量 这样我们建立数学模型时 要考虑 对于甲 x11 x12 x13 对于乙 x21 x22 x23 对于丙 x31 x32 x33 对于原料1 x11 x21 x31 对于原料2 x12 x22 x32 对于原料3 x13 x23 x33 目标函数 利润最大 利润 收入 原料支出约束条件 规格要求4个 供应量限制3个 Maxz 15x11 25x12 15x13 30 x21 10 x22 40 x31 10 x33 132 x11 0 5 x11 x12 x13 原材料1不少于50 x12 0 25 x11 x12 x13 原材料2不超过25 x21 0 25 x21 x22 x23 0 原材料1不少于25 x22 0 5 x21 x22 x23 0 原材料2不超过50 x11 x21 x31 100 供应量限制 x12 x22 x32 100 供应量限制 x13 x23 x33 60 供应量限制 xij 0 i 1 2 3 j 1 2 3 133 0 5x11 0 5x12 0 5x13 0 原材料1不少于50 0 25x11 0 75x12 0 25x13 0 原材料2不超过25 0 75x21 0 25x22 0 25x23 0 原材料1不少于25 0 5x21 0 5x22 0 5x23 0 原材料2不超过50 x11 x21 x31 100 供应量限制 x12 x22 x32 100 供应量限制 x13 x23 x33 60 供应量限制 xij 0 i 1 2 3 j 1 2 3 134 营养配餐问题 例29 假定一个成年人每天需要从食物中获得3000千卡的热量 55克蛋白质和800毫克的钙 如果市场上只有四种食品可供选择 它们每千克所含的热量和营养成分和市场价格见下表 问如何选择才能在满足营养的前提下使购买食品的费用最小 135 解 设xj为第j种食品每天的购入量 则配餐问题的线性规划模型为 minZ 14x1 6x2 3x3 2x4s t 1000 x1 800 x2 900 x3 200 x4 300050 x1 60 x2 20 x3 10 x4 55400 x1 200 x2 300 x3 500 x4 800 x1 x2 x3 x4 0 136 配方问题 例30 养海狸鼠饲料中营养要求 VA每天至少700克 VB每天至少30克 VC每天刚好200克 I II III IV V五种饲料用量分别不超过50 60 50 70 40KG 现有五种饲料 搭配使用 使费用最小 饲料成分如下表 137 设抓取饲料Ix1kg 饲料IIx2kg 饲料IIIx3kg 目标函数 最省钱minZ 2x1 7x2 4x3 9x4 5x5约束条件 营养要求 3x1 2x2 x3 6x4 18x5 700 x1 0 5x2 0 2x3 2x4 0 5x5 300 5x1 x2 0 2x3 2x4 0 8x5 200用量要求 x1 50 x2 60 x3 50 x4 70 x5 40非负性要求 x1 0 x2 0 x3 0 x4 0 x5 0 138 例31 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下 四 人力资源分配的问题 设司机和乘务人员分别在各时间段一开始时上班 并连续工作8h 问该公交线路怎样安排机和乘务人员 既能满足工作需要 又配备最少司机和乘务人员 139 解 设xi表示第i班次时开始上班的司机和乘务人员数 这样我们建立如下的数学模型 目标函数 minZ x1 x2 x3 x4 x5 x6约束条件 s t x1 x6 60 x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30 x1 x2 x3 x4 x5 x6 0 140 例32 某厂生产 三种产品 均要经过A B两道工序加工 假设有两种规格的设备A1 A2都能完成A工序 有三种规格的设备B1 B2 B3能完成B工序 可在A B的任何规格的设备上加工 可在任意规格的A设备上加工 但对B工序 只能在B1设备上加工 只能在A2与B2设备上加工 数据如下表 问 为使该厂获得最大利润 应如何制定产品加工方案 五 生产计划的问题 141 解 设xij表示在AiBj两台设备上加工的产品 的数量 i 1 2 j 1 2 3 又设y1为在A1B1上加工的产品 的数量 y2为在A2B1上加工的产品 的数量 x为产品 的数量 利润 销售单价 原料单价 产品件数 之和 每台时的设备费用 设备实际使用的总台时数 之和 142 这样我们建立如下的数学模型 MaxZ 1 25 0 25 x11 x12 x13 x21 x22 x23 2 0 35 y1 y2 2 80 0 50 x 0 05 5 x