线性规划

第一章线性规划与单纯形方法 内容 线性规划的数学模型 标准形式 基本概念及基本原理 线性规划的图解法 单纯形法 大M法 两阶段法 重点 1 线性规划的基本概念 2 单纯形法的基本原理与计算步骤难点 1 单纯形法的基本原理与计算步骤基本要求 1 理解线性规划的基本概念 目标函数 约束条件 可行解与可行域 基可行解 最优解及它们之间的关系 会写线性规划的标准形式 2 理解并掌握线性规划求解的基本理论 可行域 基本可行解与凸集顶点的关系 最优解 3 掌握线性规划的图解法 可行域 等值线移动方向 最优解的存在性情况 4 熟练掌握线性规划的单纯形法 单纯形法的基本原理 基本步骤 最优解的判定 5 熟练掌握大M法 两阶段法的原理和计算步骤 6 能利用线性规划的知识对一些实践问题 如 组织生产计划问题 节约下料问题等 建模求解 7 能利用当前的计算机软件求解线性规划问题 线性规划 概论 线性规划 LinearProgramming 创始人 1947年美国人G B 丹齐克 Dantzing 1951年提出单纯形算法 Simpler 1963年Dantzing写成 LinearProgrammingandExtension 1979年苏联的Khachian提出 椭球法 1984年印度的Karmarkar提出 投影梯度法 线性规划是研究线性不等式组的理论 或者说是研究 高维空间中 凸多面体的理论 是线性代数的应用和发展 1 1线性规划基本概念生产计划问题如何合理使用有限的人力 物力和资金 使得收到最好的经济效益 如何合理使用有限的人力 物力和资金 以达到最经济的方式 完成生产计划的要求 例1 1生产计划问题 资源利用问题 胜利家具厂生产桌子和椅子两种家具 桌子售价50元 个 椅子销售价格30元 个 生产桌子和椅子要求需要木工和油漆工两种工种 生产一个桌子需要木工4小时 油漆工2小时 生产一个椅子需要木工3小时 油漆工1小时 该厂每个月可用木工工时为120小时 油漆工工时为50小时 问该厂如何组织生产才能使每月的销售收入最大 解 将一个实际问题转化为线性规划模型有以下几个步骤 1 确定决策变量 x1 生产桌子的数量x2 生产椅子的数量2 确定目标函数 家具厂的目标是销售收入最大maxz 50 x1 30 x23 确定约束条件 4x1 3x2 120 木工工时限制 2x1 x2 50 油漆工工时限制 4 变量取值限制 一般情况 决策变量只取正值 非负值 x1 0 x2 0 数学模型maxS 50 x1 30 x2s t 4x1 3x2 1202x1 x2 50 x1 x2 0线性规划数学模型三要素 决策变量 约束条件 目标函数 1 2线性规划问题的数学模型例1 2营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量 55克蛋白质和800毫克的钙 如果市场上只有四种食品可供选择 它们每千克所含的热量和营养成分和市场价格见下表 问如何选择才能在满足营养的前提下使购买食品的费用最小 各种食物的营养成分表 解 设xj为第j种食品每天的购入量 则配餐问题的线性规划模型为 minS 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 其他典型问题 合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题生产工艺优化问题 用于成功决策的实例 美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资的决策Chessie道路系统关于购买和修理价值40亿美圆货运汽车决策 用于成功决策的实例 魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金 每年共计60亿美圆 来维持发展决策北美长途运输公司关于每周如何调度数千辆货车的决策埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策 线性规划问题的一般形式 Max Min S c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 线性规划问题隐含的假定 比例性假定可加性假定连续性假定确定性假定 线性规划问题隐含的假定 比例性假定 决策变量变化引起的目标函数的改变量和决策变量的改变量成比例 同样 每个决策变量的变化引起约束方程左端值的改变量和该变量的改变量成比例 可加性假定 每个决策变量对目标函数和约束方程的影响是独立于其他变量的 目标函数值是每个决策变量对目标函数贡献的总和 连续性假定 线性规划问题中的决策变量应取连续值 确定性假定 线性规划问题中的所有参数都是确定的参数 线性规划问题不包含随机因素 线性规划问题的标准形式 1 MaxS c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0其中 bi 0 i 1 2 m 线性规划问题的标准形式 2 MaxS s t xj 0 j 1 2 m 线性规划标准型的矩阵形式 3 MaxS CXs t AX bX 0 a11a12 a1nb1A a21a22 a2nb b2 am1am2 amnbn c1x10c2x20C X 0 xn0 如何将一般问题化为标准型 1 若目标函数是求最小值MinS CX令S S 则MaxS CX2 若约束条件是不等式若约束条件是 不等式 加一个松弛变量 0是非负的松驰变量 3 若约束条件是 不等式 Xi 1 0是非负的松驰变量 4 若约束条件右面的某一常数项bi 0这时只要在bi相对应的约束方程两边乘上 1 5 若变量xj无非负限制 引进两个非负变量xj xj 0令xj xj xj 可正可负 任何形式的线性规划总可以化成标准型 例1 3将下列问题化成标准型 MinS x1 2x2 3x3s t x1 x2 x3 7x1 x2 x3 2 3x1 x2 2x3 5x1 x2 0 x3无非负限制 MaxS x1 2x2 3x3 3x3 s t x1 x2 x3 x3 x4 7x1 x2 x3 x3 x5 2 3x1 x2 2x3 2x3 5x1 x2 x3 x3 x4 x5 0 对于标准型LP问题 可行解 满足约束条件 1 13 和 1 14 的解称为可行解 基 A中任何一组m个线性无关的列向量构成的子矩阵 称为该问题的一个基 basis 与中的这些列向量对应的变量称为基变量 basicvariable 1 3线性规划问题解的概念 最优解 若基本可行解又是最优解 也称基本最优解 这个基就称为最优基 optimalbasis 基本解 对于基 令非基变量为零 求得满足 1 13 的解 称为基对应的基本解 basicsolution 基本可行解 满足 1 14 的基本解称为基本可行解 basicfeasiblesolution 基本可行解所对应的基称为可行基 feasiblebasis 1 4线性规划问题的图解法 当决策变量个数n 2时 LP问题可以通过在平面上作图的方法求解 称为图解法 图解法求解的目的 1 判别线性规划问题的求解结局 2 在存在最优解的条件下 把问题的最优解找出来 图解法的步骤 1 求可行解集合 分别求出满足每个约束包括变量非负要求的区域 其交集就是可行解集合 或称为可行域 2 绘制目标函数图形 先过原点作一条矢量指向点 c1 c2 矢量的方向就是目标函数增加的方向 称为梯度方向 再作一条与矢量垂直的直线 这条直线就是目标函数图形 3 求最优解 依据目标函数求最大或最小移动目标函数直线 直线与可行域相交的点对应的坐标就是最优解 一般地 将目标函数直线放在可行域中求最大值时直线沿着矢量方向移动求最小值时沿着矢量的反方向移动 x1 x2 O 10 20 30 40 10 20 30 40 3 4 15 10 最优解X 15 10 最优值Z 85 例1 11 2 4 6 x1 x2 2 4 6 最优解X 3 1 最优值Z 5 3 1 minZ x1 2x2 例1 12 1 2 2 4 6 x1 x2 2 4 6 X 2 3 1 X 1 1 3 5 5 minZ 5x1 5x2 例1 13 有无穷多个最优解即具有多重解 通解为 0 1 当 0 5时 x1 x2 0 5 1 3 0 5 3 1 2 2 2 4 6 x1 x2 2 4 6 1 2 无界解 无最优解 maxZ x1 2x2 例1 14 x1 x2 O 10 20 30 40 10 20 30 40 50 50 无可行解即无最优解 maxZ 10 x1 4x2 例1 15 由以上例题可知 线性规划的解有4种形式 1 有唯一最优解 例1 11例1 12 2 有多重解 例1 13 3 有无界解 例1 14 产生原因 是由于在建立实际问题的数学模型中遗漏了某些必要的资源约束条件 4 无可行解 例1 15 原因是模型本身错误 约束条件之间互相矛盾 应检查修正 1 2情形为有最优解3 4情形为无最优解 图解法得到的启示 1 求解线性规划问题时 解的情况有 唯一最优解 无穷多最优解 无界解和无可行解 2 若线性规划问题的可行域存在 则可行域是一凸集 3 若线性规划问题的最优解存在 则最优解一定在某个顶点可达到 4 解题思路是 先找出凸集的任一顶点 计算Z值 比较相邻顶点Z值 如大 转到相邻顶点 一直到找出使Z值最大的顶点为止 1 通过图解法了解线性规划有几种解的形式2 作图的关键有三点 1 可行解区域要画正确 2 目标函数增加的方向不能画错 3 目标函数的直线怎样平行移动 线性规划问题解的概念线性规划标准型的矩阵形式 MaxS CX 1 9 s t AX b 1 10 X 0 1 11 a11a12 a1nb1A a21a22 a2nb b2 am1am2 amnbn c1x10c2x20C X 0 xn0 解 可行解 最优解 满足约束条件 1 10 的X 称为线性规划问题的解 满足约束条件 1 10 与 1 11 的X 称为线性规划的问题可行解 满足目标函数 1 9 的可行解X 称为线性规划的问题最优解 基 基向量 基变量 设r A m 并且B是A的m阶非奇异的子矩阵 det B 0 则称矩阵B为线性规划问题的一个基 矩阵B P1 P2 Pm 其列向量Pj称为对应基B的基向量 与基向量Pj相对应的变量xj就称为基变量 其余的就称为非基变量 基础解 基础可行解 可行基 对于某一特定的基B 非基变量取0值的解 称为基础解 满足非负约束条件的基础解 称为基础可行解 与基础可行解对应的基 称为可行基 为了理解基础解 基础可行解 最优解的概念 用下列例子说明 例1 4 maxS 2x1 3x2 1 12 s t 2x1 3x2 6 1 13 1 3x1 2x2 6 1 13 2 x1 x2 4 1 13 3 x1 x2 0 1 14 x2 4 3 2 1 1 2 3 4 x1 O 1 1 2 2 3 3 2x1 3x2 6 3x1 2x2 6 x1 x2 4 A Q1 Q2 Q3 Q4 B x2 4 3 2 1 1 2 3 4 x1 O 1 1 2 2 3 3 A B x2 4 3 2 1 1 2 3 4 x1 O 1 1 2 2 3 3 2x1 3x2 6 3x1 2x2 6 x1 x2 4 A Q1 Q2 Q3 Q4 B 满足约束条件 1 13 2x1 3x2 6 1 13 1 3x1 2x2 6 1 13 2 x1 x2 4 1 13 3 与坐标系x1 x2 0 1 14 的交点 O A B Q1 Q2 Q3 Q4 都是代表基础解 注意 点 4 0 0 4 不满足 1 13 满足约束条件 1 13 2x1 3x2 6 1 13 1 3x1 2x2 6 1 13 2 x1 x2 4 1 13 3 且满足x1 x2 0 1 14 的交点 O Q1 Q2 Q3 Q4 都是代表基础可行解 注意 点A B不满足x1 x2 0点 O Q1 Q2 Q3 Q4 刚好是可行域的顶点 x2 4 3 2 1 1 2 3 4 x1 O 1 1 2 2 3 3 2x1 3x2 6 3x1 2x2 6 x1 x2 4 A Q1 Q2 Q3 Q4 B 可行域 x2 4 3 2 1 1 2 3 4 x1 O 1 1 2 2 3 3 2x1 3x2 6 3x1 2x2 6 x1 x2 4 A Q1 Q2 Q3 Q4 B 可行域 本问题解的情况 基础解 点 O A B Q1 Q2 Q3 Q4 可行解 由点 O Q1 Q2 Q3 Q4 围成的区域 基础可行解 点 O Q1 Q2 Q3 Q4 最优解 Q3 解的集合 非可行解 可行解 解的集合 基础解 解的集合 可行解 基础解 基础可行解 解的集合 可行解 基础解 基础最优解 基础可行解 线性规划解的性质 几何意义 凸集概念 设D是n维线性空间Rn的一个点集 若D中的任意两点x 1 x 2 的连线上的一切点x仍在D中 则称D为凸集 即 若D中的任意两点x 1 x 2 D 存在0 1使得x x 1 1 x 2 D 则称D为凸集 例1 5 X1 X2 X 1 X 2 X 图 1 7 例1 5 X1 X2 X 1 X 2 X 2 X 1 X 2 图 1 7 X 例1 5 X1 X2 X 1 X 2 X X 1 X 2 y X 1 X 2 0 1 X X 2 y X 2 X 1 X 2 X 1 1 X 2 图 1 7 例1 5 X1 X2 X 1 X 2 X X 2 X 1 X 2 图 1 7 X X 2 y X 2 X 1 X 2 X 1 1 X 2 y X 1 X 2 0 1 例1 6 凸集 例1 7 非凸集 例1 8 凸集性质 二个凸集的交还是凸集 二个凸集的并不一定是凸集 两个基本概念 凸组合 设x 1 x 2 x k 是n维线性空间Rn中的k个点 若存在数u1 u2 uk且0 ui 1 i 1 2 k ui 1 使得x u1x 1 u2x 2 ukx k 成立 则称x为x 1 x 2 x k 的凸组合 两个基本概念 顶点 设D是凸集 若D中点x不能成为D中任何线段上的内点 则称x为凸集D的顶点 即 若D中的任意两点x 1 x 2 不存在数 0 1 使得x x 1 1 x 2 成立 则称x为凸集D的一个顶点 例1 9 多边形上的点是顶点 圆周上的点