第1章 线性规划.ppt

第二部分 规划论 第1章 线性规划与单纯形法第2章 对偶理论和灵敏度分析第3章 运输问题第4章 目标规划 第1章线性规划与单纯形法 基本概念 图解法及单纯形解法 一般线性规划问题的数学模型线性规划问题的图解法线性规划问题的单纯形解法 知识点要求 了解线性规划的涵义 能根据实际问题列出线性规划的数学模型 掌握线性规划图解法及其几何意义 理解线性规划的标准型和规范型 掌握单纯形法原理 了解并掌握运用单纯形表计算线性规划问题的步骤及解法 掌握任何基可行解原表及单纯形表的对应关系 能运用大M法或两阶段法求解线性规划问题 能运用人工变量法求解非规范型的线性规划问题 1 1线性规划问题及其数学模型 规划问题 简单地说 就是指如何最合理地利用有限的资源 以便使产出的消耗最小 同时实现利润最大 丹捷格 1947年 首次提出 线性规划问题 LP LinearProgramming 线性规划问题的提出 解决有限资源的最佳分配问题 即如何对有限的资源作出最佳方式的调配和最有利的使用 以便最充分地发挥资源的效能去获取最佳的经济效益 例 某工厂在计划期内要安排生产I II两种产品 已知生产单位产品所需的设备台时及A B两种原材料的消耗 如下表所示 又设工厂每生产一件产品I可获利2元 每生产一件产品II可获利3元 问应如何安排计划使该工厂获利最多 模型 目标函数约束条件 例 靠近某河流有两个化工厂 流经第一化工厂的河流流量为每天500万立方米 在两个工厂之间有一条流量为每天200万立方米的支流 第一化工厂每天排放含有某种有毒物质的工业污水2万立方米 第二化工厂每天排放这种工业污水1 4立方米 从第一化工厂排出的工业污水流到第二化工厂之前 有20 可自然净化 根据环保要求 河流中工业污水的含量应不大于0 2 这两个工厂都需要种处理一部分工业污水 续上 第一化工厂处理工业污水的成本是1000元 万立方米 第二化工厂的成本为800元 万立方米 现在要问在满足环保要求的条件下 每厂各应处理多少工业污水 使这两个工厂总的处理工业污水费用最小 例 产品生产决策问题 某汽车工厂生产大轿车和载重汽车两种型号的汽车 已知生产每辆汽车所用的钢材都是2吨 辆 该工厂每年供应的钢材为1600吨 工厂的生产能力是每2 5小时可生产一辆载重汽车 每5小时可生产一辆大轿车 工厂全年的有效工时为2500小时 已知供应给该厂大轿车用的座椅每年可装配400辆 据市场调查 出售一辆大轿车可获利4千元 出售一辆载重汽车可获利3千元 问在这些条件下 工厂应如何安排生产 以使工厂获利最大 解决问题的步骤 1 确定决策变量 设生产大轿车x1辆 载重汽车x2辆2 确定目标函数 maxZ 4x1 3x23 确定约束条件 原材料约束2x1 2x2 1600工时约束5x1 2 5x2 2500大轿车座椅约束x1 400非负性约束x1 0 x2 0 可控因素 目标 约束条件 问题 如何安排生产 以实现利润最大化 数学模型表达 目标函数 maxZ 4x1 3x2约束条件 2x1 2x2 16005x1 2 5x2 2500 x1 400 x1 0 x2 0 小结 线性规划 LP 问题包含下列要素 变量 决策要控制的因素目标函数 决策目标 最优 的数学描述约束条件 实现目标的一组限制条件求LP问题 在约束条件下使目标最优的一组变量的取值解决环节 确定问题 建立模型 问题求解 经济分析 敏感性分析 模型构建的一般思路总结 1 确定该LP问题的目标是什么 2 实现目标取决于什么因素和条件 3 确定哪几个因素为决策变量 4 目标如何用决策变量来加以描述 5 约束条件如何表达 6 决策变量本身是否有限制条件 例 广告方法的选择问题 某公司要求销售部经济制定一个广告计划 计划用经费10000元 要求尽量多的人能看到广告 该经理选择了三种广告方法 电视 电台和报纸 据调查各种广告的费用如下 在地方电视台下午播放0 5分钟要1000元 晚上要2000元 在广播电台上作广告的价格是 白天每半分钟600元 晚上每半分钟400元 在地方报纸上作半页广告费用是300元 一页要1000元 经理决定在电视上作广告至少两次 但不多于四次 同时 公司限制用电台作广告的次数 白天最多不超过5次 晚上不超过3次 另外 根据有关资料估计 在下午观看电视广告节目的大约有4万人 晚上有9万人 广播电台的听众白天有4万人 晚上有3万人 看日报的大约有6万人 并估计其中1 2的人看整页的广告 1 3的人看半页的广告 要求设定一种广告方案 使尽量多的人能受到广告的宣传 广告问题 例 配料问题 某奶牛场面临着选择两种饲料问题 每种饲料所含的营养成分及价格如下表 已知每头奶牛每天需要三种营养的最低数量是A 20单位 B 14单位 C 16单位 问如何找一个最经济的配方 以满足奶牛每天的最低营养量 如果在每种饲料中都含有一种有害的成分D 甲饲料每斤含D成分0 1个单位 乙饲料每斤含D成分0 05个单位 而奶牛每日食有D成分不得大于1个单位 问如何求最优配方 例 下料问题 某工厂要做100套钢架 每套由长2 9米 2 1米和1 5米的圆钢各一根组成 已知原料长7 4米 问应如何下料使需用的原材料最省 构件数 根 例 某工厂拥有A B C三种类型的设备 生产甲 乙 丙 丁四种产品 每件产品在生产中需要占用的设备机时数 每件产品可以获得的利润以及三种设备可利用的时数如下表所示 用线性规划制订使总利润最大的生产计划 建立的模型如下 设变量xi为第i种产品的生产件数 i 1 2 3 4 目标函数Z为相应的生产计划可以获得的总利润 在加工时间以及利润与产品产量成线性关系的假设下 可以建立如下的线性规划模型 求解这个线性规划 可以得到最优解为 x1 294 12x2 1500 x3 0 x4 58 82最大利润为 z 12737 06 元 请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产 说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性 尤其当产品品种很多 设备类型很多的情况下 用手工方法安排生产计划很难获得满意的结果 另外 变量是否需要取整也是需要考虑的问题 线性规划的定义 求一组变量的值 使之满足关于这组变量的若干个线性等式或不等式的约束条件 而且使这组变量的一个线性函数取到最优 最大值或极小值 这些变量称为决策变量 所要优化的函数称为目标函数 决策变量是取实数值的连续变量 这样的问题称为线性规划 总结 线性规划问题的典型特征 可用一些变量表示这类问题的待定方案 这些变量 决策变量 的一组值代表一个具体方案 存在一定的约束条件 这些约束条件都能用关于决策变量的线性不等式或等式来表示 有一个期望达到的目标 这个目标能以某种确定的数量指标刻划出来 而这种数量指标可表示为关于决策变量的线性函数 按所考虑的问题的不同 要求该函数值最大化或最小值 线性规划问题的一般形式 目标函数 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其中 cj称为价值系数 aij称为技术系数 bi称为限定系数 线性规划问题的标准形式 目标函数 maxZ c1x1 c2x2 c3x3 cnxn约束条件 a11x1 a12x2 a13x3 a1nxn b1a21x1 a22x2 a23x3 a2nxn b2 am1x1 am2x2 am3x3 amnxn bmx1 0 x2 0 xn 0 标准型的好处 其它各种形式的线性规划问题可以化为标准型后 用标准型的求解方法求解 一般形式向标准形式的转化 目标函数极小化转为极大化 minZ max Z 即 一个变量的极小化等价于其相反数的极大化 不等式约束的转化 aijxj bi加入松弛变量 aijxj bi减去剩余变量非正变量 即xk 0则令x k xk自由变量 即xk无约束 令xk x k x k 例 MaxZ 4x1 3x2MaxZ 4x1 3x22x1 2X2 16002x1 2x2 x3 16005x1 2 5x2 25005x1 2 5x2 x4 2500 x1 300 x1 x5 300 x1 0 x2 0 xj 0j 1 2 5 例 MinZ x1 2x2 3x3MaxZ x 1 2x2 3 x 3 x 3 x1 x2 x3 9 x 1 x2 x 3 x 3 x4 9 x1 2x2 x3 2x 1 2x2 x 3 x 3 x5 23x1 x2 3x3 5 3x 1 x2 3 x 3 x 3 5x1 0 x2 0 x3无约束x 1 0 x2 0 x 3 0 x 3 0 x4 0 x5 0 标准型的和式 线性规划的标准型的向量表示 其中 X x1 x2 x3 xn TC c1 c2 c3 cn Tpj a1j a2j amj Tb b1 b2 b3 bn T0 0 0 0 0 T 线性规划的标准型的矩阵式 MaxZ CTXs t AX bX 0其中 b b1 b2 bm Ta11a12 a1nA a21a22 a2n am1am2 amn 二 线性规划问题的图解法 考虑前述的例1 目标函数 maxZ 4x1 3x2约束条件 2x1 2x2 16005x1 2 5x2 2500 x1 400 x1 0 x2 0二元线性方程在二维平面坐标上的图示 二元线性不等式在二维平面坐标上的图示 我们知道 y ax b是一条直线 同理 Z 4x1 3x2 x2 4 3 x1 Z 3也是一条直线 以Z为参数的一族等值线 2x1 2x2 1600 x2 800 x1是直线x2 800 x1下方的半平面 所有半平面的交集称之为可行域 可行域内的任意一点 就是满足所有约束条件的解 称之为可行解 2x1 2x2 1600 E F G H 可以看到 这些等值线互相平行 Z的值越大 离原点越远 因此 问题可化为 在上列平行线中 找出一条与五边形OABCD有共同点 又离原点最远的直线 该直线与五边形OABCD的公共点即为所求的点 从上图可以看到 B点符合要求 从图中读出B的坐标为 200 600 即最优解为 x1 200 x2 600 此时 目标函数的最大值为 Zmax 4 200 3 600 2600 用图解法解线性规划的一般步骤 选择适当的比例 绘出由约束条件所确定的可行解集 绘出目标函数的等值线 平行线簇 在各等值线中选取一条与原点距离最大 如果求目标函数的最小值 则选与原点距离最小的 而与可行解集有公共点的直线 该公共点 一个或多个 的坐标就是最优解 该等值线所代表的值就是目标函数在约束条件下能取到的最大值 或最小值 例 利用图解法解下面的线性规划问题 MinS 2x1 3x2S t x1 x2 54x1 x2 8x1 2x2 6x1 0 x2 0 x1 x2 图解法的局限性 只适用于两维的情形 只有两个变量 线性规划问题解的概念 基本概念如前所述线性规划问题的标准型为MaxZ CTXs t AX bX 0满足约束条件的解X称为线性规划问题的可行解 而使目标函数达到最大值的可行解称为最优解 约束方程组的系数矩阵A的秩为m 且m n 设A B R B是A中m m阶非奇异子矩阵 则称B是LP的一个基 即 B是A中m个线性无关向量组 记A的列向量顺序为P1 P2 Pn 那么约束条件Ax b可写为 x1P1 x2P2 xnPn b 因而基是由m个线形无关的列向量Pj所组成 设B 则把称为基向量 其余列向量称为为非基向量 与之相应的称为基变量 其余变量称为非基变量 令非基变量取值为0 求出基变量的值 这样的解称为相应于基B的基解 基本解 不妨设B P1 P2 Pm 是一个极大无关组 则AX b P1 P2 Pm Pm 1 Pn X bx1P1 x2P2 xmPm xm 1Pm 1 xnpn b即 P1 P2 Pm Pm 1 Pn b 此时A可写成分块矩阵A B R 相应地将基变量组成的向量记为xB 非基变量组成的向量记为xR 与xB和xR相对应的目标函数的系数向量分别记为CB和CR 从而AX b可以写成 B R XB XR T bBXB RXR bXB B 1b B 1RXR此时 Z CBT CRT XB XR T CBTXB CRTXR CBT B 1b B 1RXR CRTXR CBTB 1b CBTB 1R CRT XR 从而 对应于基B的基本解是 XR 0 XB B 1b 此时 Z CBTB 1b 如果B 1b 0 则称基B是可行基 所对应的基解称为基可行解 如果基可行解是最优解 那么基B称为最优基 求解线性规划的过程就是寻找最优解的过程 现在可化为寻找最优基的过程 首先提出的问题是 什么样的基是最优基 对此 我们有如下判定定理 定理 对于基B 若B 1b 0 且CBTB 1R CRT 0 则B是最优基 证明 由B 1b 0可知B是可行基 由CBTB 1R CRT 0可知 Z CBTB 1b因此 XR 0 XB B 1b是最优解 故B是最优基 基解 令非基变量xm 1 xn 0 再用高斯消去法求解方程组AX b 就可以求出一个解 XB x1 x2 xm 0 0 T这个解称为基本解 所以有一个基就有一个解 在n个变量 m个约束条件的情况下 共有Cm nn个基本解 基可行解 满足非负条件的基本解称为基本可行解 否则 称为基本不可行解 可行基 对应于基本可行解的基称为可行基 例 找出如下线性规划问题的所有的基解 指出哪些是基可行解 MinZ 5x1 2x2 3x3 2x4S t x1 2x2 3x3 4x4 72x1 2x2 x3 2x4 3xj 0 j 1 2 3 4 解答见DOC文档 考虑前面提到的例1 maxZ 4x1 3x2s t 2x1 2x2 16005x1 2 5x2 2500 x1 400 x1 0 x2 0 maxZ 4x1 3x2 0 x3 0 x4 0 x5s t 2x1 2x2 x3 16005x1 2 5x2 x4 2500 x1 x5 400 xj 0 j 1 5 22100A 52 501010001 找出关于例1的线性规划问题的基解 MaxZ 4x1 3x2s t 2x1 2x2 x3 16005x1 2 5x2 x4 2500 x1 x5 300 xj 0j 1 2 5 本部分小结 可行解 最优解 基 基解 基可行解 可行基 最优基 不可行解 可行解 基可行解 基解 1 2线性规划问题的几何意义 凸集 如果在形体中任意两点连接一根直线 若线段上所有的点都在这个形体中 则称该形体为凸集 凸集的数学语言表述 设K是n维欧氏空间中的一个点集 任取两点x1 K x2 K 若它们连线上的一切点均有 x1 1 x2 K 0 1 则称K为凸集 a 凸集 b 凸集 c 凸集 a 非凸集 b 非凸集 c 非凸集 凸组合 设x1 x2 xk是n维欧式空间En中的k个点 若存在 1 2 k 且0 i 1 i 1 使得 x 1x1 2x2 kxk则称x为x1 x2 xk的凸组合 顶点 设K是凸集 x K 若x不能表示为K中两个不同的两点x1 K x2 K 的线性组合 x x1 1 x2 0 1 则称x是K的一个顶点 顶点也称为极点或角顶 定理 有限个凸集的交集是凸集 线性规划问题的解的特点 定理 定理1 若线性规划问题存在可行域 则其可行域D X AX b X 0 是凸集 引理1 线性规划问题的可行解为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的 定理2 线性规划问题的基可行解对应于可行域的顶点 引理2 若K是有界凸集 则其内任何一点都可表示为K的顶点的凸组合 定理3 若可行域有界 线性规划问题的目标函数一定可以在其可行域的顶点上达到最优 其它 如果一个线性规划问题存在唯一的最优解 那么它必定是一个顶点可行解 如果线性规划问题存在多个最优解 那么至少有两个相邻的顶点可行解 只存在有限个顶点可行解如果一个顶点可行解的目标函数比其相邻的极点可行解的目标函数值要好的话 那么它就比其他所有顶点可行解的目标函数都要好 或者说它就是一个最优解 对于凸集来说 局部极点就是全局顶点 线性规划的可行域及最优解的可能结果可行域为封闭的有界区域 唯一 多个最优解可行域为非封闭的无界区域 唯一 多个最优解对于目标函数无界 无最优解可行域为空集 没有可行解 更无最优解 a 可行域封闭 唯一最优解 b 可行域封闭 多个最优解 d 可行域开放 多个最优解 e 可行域开放 目标函数无界 f 可行域为空集 c 可行域开放 唯一最优解 线性规划的可行域及最优解的可能结果图示 1 3单纯形法 单纯形法的基本思路是 先从可行域中某个基可行解 一个极点 开始 判断该解是否最优 如不是 则实施基变换 转换到另一个基可行解 极点 使新的基可行解比原来的要好 这样迭代下去 直至找到最优解为止 现以例1中的线性规划问题为例进行说明 见DOC文档 1 建立初始基本可行解 2 最优解检验规则 3 第一次迭代 确定换入变量 选取相对收益系数最大者确定换出变量 极小比值法则 资源限制 4 第二次 第三次迭代 解的最优性检验 从前面的例子可以看到 迭代的每一步都要对解的最优性进行检验 方法是把每次迭代得到的基本可行解代入目标函数 然后检查目标函数中非基变量的系数是否大于0 如果有大于0的系数 说明目前的解不是最优解 如果无大于0的系数 说明该解就是最优解 下面来推导目标函数中非基变量系数的一般表达式 由 x1 b1 a14 x4 a15 x5 x2 b2 a24 x4 a25 x5 x3 b3 a34 x4 a35 x5 代入目标函数Z c1 x1 c2 x2 c3 x3 c4 x4 c5 x5 得 由 x1 b1 a14x4 a15x5x2 b2 a24x4 a25x5x3 b3 a34x4 a35x5代入目标函数Z c1x1 c2x2 c3x3 c4x4 c5x5 得 显然 如果某一非基变量的 j值大于0 说明该非基变量xj 换成基变量时可以使目标值增加 因此该解还不是最优解 如果非基变量的 j都不大于0 说明该解就是最优解 1 4单纯形法的表格化计算步骤 单纯形表 1 4单纯形法的表格化计算步骤 第一步 引进松驰变量 化不等式为等式 例线性规划标准化 MaxZ 4x1 3x2s t 2x1 2x2 x3 16005x1 2 5x2 x4 2500 x1 x5 300 xj 0j 1 2 5第二步 建立初始单纯形表 第三步 判定所求得的解是否是优 如果检验数 j zj cj 0 则已得到最优解 停止计算 否则转入第四步 第四步 换基迭代 迭代完毕转入第三步 迭代法则如下 确定枢轴元素 在对应负检验数的各向量中 选取绝对值最大的一个 记为Pj 作为进入新表的基向量 如果不止一个 则可任意选一个 j 列称为枢轴列 本例P1进入新表基向量 P1所在的列为枢轴列 选定枢轴列后 用枢轴列中的各正元素去除b列的对应各元素 所得的数记为 i 即 i bi aij aij 0 设 i 是 i中最小的一个 则把向量P从原基向量中搞出 如果不止一个 则可取下标较小者 P所在的行称为枢轴行 在枢轴行与枢轴列的交点上的元素叫做枢轴元素 本例中 1 800 2 500 3 400 从而取第3行为枢轴行 第三行第一列元素为枢轴元素 2 换基即首先把原基底中的Pi 取出 用Pj 代替它 3 计算新表元素我们用 ij表示原表中第i行 第j列元素 用 ij表示新表中第i行 第j列元素 按如下法则填写新表中的各单元格 把原表枢轴行上的元素 i j除以枢轴元素 i j 后填在新表上相应位置上 即 i j i j i j 本例中 30 400 1 400 31 1 1 1 原表枢轴列上的元素 除了枢轴元素在新表相应的位置填上1之外 其余元素在新表相应位置都填上0 2 换基即首先把原基底中的Pi 取出 用Pj 代替它 原表中不在枢轴行和枢轴列上的元素 在新表的相应位置填上新数 ij ij i j ij i j i i j j 该规则对于zj cj行同样适用 在实际运算中 我们可以用如下矩形记住这个法则 本例中 10 1600 400 2 1 800 12 2 2 0 1 2 1 5单纯形法的进一步讨论 一 目标函数求极小值问题解决方法 1 将目标函数极小问题改为等价的求极大问题 即由目标函数 MinZ cjxj变成目标函数 Max Z cjxj 2 改变最优解的检验规则 例 求LP问题 Minz x2 2x3x1 2x2 x3 2x2 3x3 x4 1x2 x3 x5 2xj 0 j 1 2 5 二 等式约束 人工变量法1 人工变量的引入判断准则 若在最终表中当所有zj cj非负 而在其中还有某个非零人工变量 则表示无可行解 2 大M法3 两阶段法 三 大于等于约束条件思路 先减去一个松驰变量 再加入一个人工变量 来产生初始基本可行基 然后用大M法进行单纯形的迭代计算 四 常数项为负值的情况五 允许变量为负值的情况 关于解的退化问题 若存在两个以上相同的最小比值 这样在下一次迭代中就有一个或几个基变量等于零 就出现退化解解决办法 勃兰特规则 选取zj cj 0中下标最小的非基变量xk为换入变量 即 k min j zj cj 0 当按 规则计算存在两个及以上最小比值时 选取下标最小的基变量为换出变量 单纯形法的解的判定 1 无可行解 最优解中包括有正的人工变量 因为正的人工变量表示等式约束不能被满足 2 无界解 有负检验数的非基变量对应的列向量其分量a ij均非正数 负数或零 3 无穷最优解 存在非基变量的检验数为0时 4 退化解 出现某一基解为0 单纯形法小结 单纯形法基本过程 开始 选择一个起始基础可行解 编初始单纯形表 Yes OK No 施以初等变换 换基 zj cj 0 根据max zj cj 确定入基向量Pj 根据min bi0 bij bij 0 确定出基向量Pi 更详细的过程见P37 1 6线性规划应用举例 例1 合理利用线材问题 现要做100套钢架 每套用长为2 9米 2 1米和1 5米的元钢各一根 已经原料长7 4米 问应如何下料 使用的原材料最省 例2 配料问题 某工厂要用三种原材料C P H混合调配出三种不同规格的产品A B D 简单混合 没有发生化学反应 已知产品的规格要求 产品单价 每天能供应的原材料数量及原材料单价 分别见表1 13和1 14 问该厂应如何安排生产 使利润收入为最大 表1 13 表1 14 例3 连续投资问题 某部门在今后五年内考虑给下列项目投资 已知 项目A 从第一年到第四年年初需要投资 并于次年末回收本利115 项目B 第三年初需要投资 到第五年末能回收本利125 但规定最大投资额不超过4万元 项目C 第二年初需要投资 到第五年末能回收本利125 但规定最大投资额不超过3万元 项目D 五年内每年年初可购买公债 于当年末归还 并加利息6 该部门现有资金10万元 应如何确定这些项目每年的投资额 使到第五年末拥有的资金的本利总额最大 解 确定决策变量 设xiA xiB xiC xiD i 1 5 分别表示第i年年初给项目A B C D的投资额建立目标函数 Maxz 1 15x4A 0 25x3B 1 40 x2C 1 06x5D 确定约束条件 第一年 x1A x1D 10000第二年 x2A x2C x2D 1 06x1D第三年 x3A x3B x3D 1 151A 1 06x2D第四年 x4A x