线性规划(01).ppt

第一讲线性规划与单纯形方法 第一节线性规划问题及数学模型线性规划 LinearProgramming 创始人 1947年美国人G B 丹齐克 Dantzing 线性规划 概论 线性规划 LinearProgramming 创始人 1947年美国人G B 丹齐克 Dantzing 1951年提出单纯形算法 Simpler 线性规划 概论 线性规划 LinearProgramming 创始人 1947年美国人G B 丹齐克 Dantzing 1951年提出单纯形算法 Simpler 1963年Dantzing写成 LinearProgrammingandExtension 线性规划 概论 线性规划 LinearProgramming 创始人 1947年美国人G B 丹齐克 Dantzing 1951年提出单纯形算法 Simpler 1963年Dantzing写成 LinearProgrammingandExtension 1979年苏联的Khachian提出 椭球法 线性规划 概论 线性规划 LinearProgramming 创始人 1947年美国人G B 丹齐克 Dantzing 1951年提出单纯形算法 Simpler 1963年Dantzing写成 LinearProgrammingandExtension 1979年苏联的Khachian提出 椭球法 1984年印度的Karmarkar提出 投影梯度法 线性规划 概论 线性规划 LinearProgramming 创始人 1947年美国人G B 丹齐克 Dantzing 1951年提出单纯形算法 Simpler 1963年Dantzing写成 LinearProgrammingandExtension 1979年苏联的Khachian提出 椭球法 1984年印度的Karmarkar提出 投影梯度法 线性规划是研究线性不等式组的理论 或者说是研究 高维空间中 凸多面体的理论 是线性代数的应用和发展 1线性规划发展史线性规划 LinearProgramming 创始人 1947年美国人G B 丹齐克 Dantzing 1951年提出单纯形算法 Simpler 1963年Dantzing写成 LinearProgrammingandExtension 1979年苏联的Khachian提出 椭球法 1984年印度的Karmarkar提出 投影梯度法 线性规划是研究线性不等式组的理论 或者说是研究 高维空间中 凸多面体的理论 是线性代数的应用和发展 2线性规划基本概念生产计划问题如何合理使用有限的人力 物力和资金 使得收到最好的经济效益 如何合理使用有限的人力 物力和资金 以达到最经济的方式 完成生产计划的要求 例1生产计划问题 资源利用问题 某家具厂生产桌子和椅子两种家具 桌子售价50元 个 椅子销售价格30元 个 生产桌子和椅子要求需要木工和油漆工两种工种 生产一个桌子需要木工4小时 油漆工2小时 生产一个椅子需要木工3小时 油漆工1小时 该厂每个月可用木工工时为120小时 油漆工工时为50小时 问该厂如何组织生产才能使每月的销售收入最大 解 将此问题列成图表如下 将一个实际问题转化为线性规划模型有以下几个步骤 将一个实际问题转化为线性规划模型有以下几个步骤 1 确定决策变量 x1 生产桌子的数量x2 生产椅子的数量 解 将一个实际问题转化为线性规划模型有以下几个步骤 1 确定决策变量 x1 生产桌子的数量x2 生产椅子的数量2 确定目标函数 家具厂的目标是销售收入最大maxz 50 x1 30 x2 解 将一个实际问题转化为线性规划模型有以下几个步骤 1 确定决策变量 x1 生产桌子的数量x2 生产椅子的数量2 确定目标函数 家具厂的目标是销售收入最大maxz 50 x1 30 x23 确定约束条件 4x1 3x2 120 木工工时限制 2x1 x2 50 油漆工工时限制 解 将一个实际问题转化为线性规划模型有以下几个步骤 1 确定决策变量 x1 生产桌子的数量x2 生产椅子的数量2 确定目标函数 家具厂的目标是销售收入最大maxz 50 x1 30 x23 确定约束条件 4x1 3x2 120 木工工时限制 2x1 x2 50 油漆工工时限制 4 变量取值限制 一般情况 决策变量只取正值 非负值 x1 0 x2 0 解 将一个实际问题转化为线性规划模型有以下几个步骤 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 决策变量 设产品I II的产量分别为x1 x2 2 目标函数 设总运费为z 则有 maxz 2x1 3x2 3 约束条件 3线性规划问题的数学模型 例3营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量 55克蛋白质和800毫克的钙 如果市场上只有四种食品可供选择 它们每千克所含的热量和营养成分和市场价格见下表 问如何选择才能在满足营养的前提下使购买食品的费用最小 各种食物的营养成分表 每天需要300055800 各种食物的营养成分表 每天需要300055800 X1X2x3x4 解 设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 例4合理下料问题现做100套钢架 每套用长为2 9m 2 1m和1 5m的原钢各一根 已知原料长为7 4m 问应如何下料 使用的原料最省 解 最简单的方法是在每根原料上截取2 9m 2 1m 1 5m的元钢各一根组成一套 需100根 每根省下料头0 9m 就浪费了 若改为套裁 可以节约原料 几种套裁方案如下表 线性规划模型 不同方法截得每种根长的总数至少100 此例的变量xi只取正整数 故建立的模型也称整数规划 0 1规划是整数规划的特殊情形 例5运输问题设有两砖厂A1 A2分别供应三个工地B1 B2 B3 运价表如下 问如何调运使总运费最省 列出数学模型 解设Ai调运给Bj的调运量为xij i 1 2 j 1 2 3其数学模型为 minS 50 x11 60 x12 70 x13 60 x21 110 x22 160 x23s t x11 x12 x13 23x21 x22 x23 27x11 x21 17x12 x22 18x13 x23 15xij 0 i 1 2 j 1 2 3 其他典型问题 运输问题 其他典型问题 合理下料问题运输问题生产的组织与计划问题 其他典型问题 合理下料问题运输问题生产的组织与计划问题投资证券组合问题 其他典型问题 合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题 其他典型问题 合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题生产工艺优化问题 用于成功决策的实例 美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策 用于成功决策的实例 美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资的决策 用于成功决策的实例 美国航空公司关于哪架飞机用于哪一航班和哪些机组人员被安排于哪架飞机的决策美国国防部关于如何从现有的一些基地向海湾运送海湾战争所需要的人员和物资的决策Chessie道路系统关于购买和修理价值40亿美圆货运汽车决策 用于成功决策的实例 魁北克水利部门关于用哪几个水库来满足每天电力需求决策 用于成功决策的实例 魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金 每年共计60亿美圆 来维持发展决策 用于成功决策的实例 魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金 每年共计60亿美圆 来维持发展决策北美长途运输公司关于每周如何调度数千辆货车的决策 用于成功决策的实例 魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金 每年共计60亿美圆 来维持发展决策北美长途运输公司关于每周如何调度数千辆货车的决策埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策 用于成功决策的实例 魁北克水利部门关于用哪几个水库来满足每天电力需求决策农场信贷系统联邦土地银行关于如何支付到期债券和应发售多少新债券以获取资金 每年共计60亿美圆 来维持发展决策北美长途运输公司关于每周如何调度数千辆货车的决策埃克森炼油厂关于调节冶炼能力去适应关于无铅燃料生产的法律更改的决策 4线性规划问题的一般形式 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 向量形式 3 线性规划标准型的矩阵形式 3 x10 x20C c1 c2 cn X 0 xn0 a11a12 a1nb1A a21a22 a2nb b2 am1am2 amnbn 如何将一般问题化为标准型 若目标函数是求最小值MinS CX令S S 则MaxS CX 如何将一般问题化为标准型 若目标函数是求最小值MinS CX令S S 则MaxS CX若约束条件是不等式 如何将一般问题化为标准型 若目标函数是求最小值MinS CX令S S 则MaxS CX若约束条件是不等式若约束条件是 不等式n aijxj yi bij 1yi 0是非负的松驰变量 如何将一般问题化为标准型 若约束条件是 不等式n aijxj zi bij 1zi 0是非负的松驰变量 如何将一般问题化为标准型 若约束条件右面的某一常数项bi 0这时只要在bi相对应的约束方程两边乘上 1 如何将一般问题化为标准型 若约束条件右面的某一常数项bi 0这时只要在bi相对应的约束方程两边乘上 1 若变量xj无非负限制引进两个非负变量xj xj 0令xj xj xj 如何将一般问题化为标准型 若约束条件右面的某一常数项bi 0令xj xj xj 可正可负 任何形式的线性规划总可以化成标准型 例6将下列问题化成标准型 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 例6将下列问题化成标准型 MinS x1 2x2 3x3s t x1 x2 x3 7x1 x2 x3 2 3x1 x2 2x3 5x1 x2 0 x3无非负限制 二维 线性规划问题图解法 1 满足约束条件的变量的值 称为可行解 二维 线性规划问题图解法 1 满足约束条件的变量的值 称为可行解 2 使目标函数取得最优值的可行解 称为最优解 二维 线性规划问题图解法 1 满足约束条件的变量的值 称为可行解 2 使目标函数取得最优值的可行解 称为最优解 例1的数学模型maxS 50 x1 30 x2s t 4x1 3x2 1202x1 x2 50 x1 x2 0 x2 50 40 30 20 10 10 20 30 40 x1 4x1 3x2 120 由4x1 3x2 120 x1 0 x2 0围成的区域 x2 50 40 30 20 10 10 20 30 40 x1 2x1 x2 50 由2x1 x2 50 x1 0 x2 0围成的区域 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的区域 可行域 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作为顶点的凸多边形 x2 50 40 30 20 10 10 20 30 40 x1 可行域 目标函数是以S作为参数的一组平行线S 50 x1 30 x2x2 S 30 5 3 x1 2 5 3 4 3 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当S值不断增加时 该直线x2 S 30 5 3 x1沿着其法线方向向右上方移动 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当该直线移到Q2点时 S 目标函数 值达到最大 MaxS 50 15 30 20 1350此时最优解 15 20 Q2 15 20 二个重要结论 满足约束条件的可行域一般都构成凸多边形 这一事实可以推广到更多变量的场合 二个重要结论 满足约束条件的可行域一般都构成凸多边形 这一事实可以推广到更多变量的场合 最优解必定能在凸多边形的某一个顶点上取得 这一事实也可以推广到更多变量的场合 解的讨论 最优解是唯一解 解的讨论 最优解是唯一解 无穷多组最优解 例1的目标函数由maxS 50 x1 30 x2变成 maxS 40 x1 30 x2s t 4x1 3x2 1202x1 x2 50 x1 x2 0 例1maxS 50 x1 30 x2s t 4x1 3x2 1202x1 x2 50 x1 x2 0 x2 50 40 30 20 10 10 20 30 40 x1 可行域 目标函数是同约束条件 4x1 3x2 120平行的直线x2 S 30 4 3 x1 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当S的值增加时 目标函数同约束条件 4x1 3x2 120重合 Q1与Q2之间都是最优解 Q1 0 40 Q2 15 20 解的讨论 无界解 例 maxS x1 x2s t 2x1 x2 40 x1 x2 20 x1 x2 0 x2 50 40 30 20 10 10 20 30 40 x1 该可行域无界 目标函数值可增加到无穷大 称这种情况为无界解或无最优解 2x1 x2 40 x1 x2 20 解的讨论 无可行解 例 maxS 2x1 3x2s t x1 2x2 8x1 4x2 3 2x1 x2 4x1 x2 0 该问题可行域为空集 即无可行解 也不存在最优解 解的情况 有可行解 有唯一最优解 有无穷最优解 无界解 无最优解 无可行解 线性规划问题解的概念线性规划标准型的矩阵形式 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 线性规划问题的数学模型 一般式 标准型 线性规划问题的图解法 二维 线性规划标准型的矩阵形式 MaxS CXs t AX bX 0 线性规划问题的解解 可行解 最优解 满足约束条件 1 10 的X 称为线性规划问题的解 MaxS CX 1 9 s t AX b 1 10 X 0 1 11 解 可行解 最优解 满足约束条件 1 10 的X 称为线性规划问题的解 满足约束条件 1 10 与 1 11 的X 称为线性规划的问题可行解 解 可行解 最优解 满足约束条件 1 10 的X 称为线性规划问题的解 满足约束条件 1 10 与 1 11 的X 称为线性规划的问题可行解 满足目标函数 1 9 的可行解X 称为线性规划的问题最优解 基 基向量 基变量 设r A m 并且B是A的m阶非奇异的子矩阵 det B 0 则称矩阵B为线性规划问题的一个基 基 基向量 基变量 设r A m 并且B是A的m阶非奇异的子矩阵 det B 0 则称矩阵B为线性规划问题的一个基 矩阵B P1 P2 Pm 其列向量Pj称为对应基B的基向量 基 基向量 基变量 设r A m 并且B是A的m阶非奇异的子矩阵 det B 0 则称矩阵B为线性规划问题的一个基 矩阵B P1 P2 Pm 其列向量Pj称为对应基B的基向量 与基向量Pj相对应的变量xj就称为基变量 其余的就称为非基变量 基础解 基础可行解 可行基 对于某一特定的基B 非基变量取0值的解 称为基础解 基解 基础解 基础可行解 可行基 对于某一特定的基B 非基变量取0值的解 称为基础解 满足非负约束条件的基础解 称为基础可行解 基可行解 基础解 基础可行解 可行基 对于某一特定的基B 非基变量取0值的解 称为基础解 满足非负约束条件的基础解 称为基础可行解 与基础可行解对应的基 称为可行基 矩阵A P1 P2 Pn B P1 P2 Pm 基的个数 基可行解的个数 a11a12 a1mb1B a21a22 a2mb b2 am1am2 ammbn a11a12a1mb1a1m 1a1na21x1 a22x2 a2mxm b2 a2m 1xm 1 a2nxn am1am2ammbnamm 1amn 或 令 XB是对应这个基的基变量XB 为基解 基解中非零分量的个数小于m个时 该基解是退化解 为了理解基础解 基础可行解 最优解的概念 用下列例子说明 标准型为 maxz 2x1 3x2 0 x3 0 x4 0 x5 例maxz 2x1 3x2 基 基为 基变量为 x3 x4 x5 非基变量为x1 x2 令非基变量x1 0 x2 0 基变量x3 8 x4 16 x5 12 X 0 0 8 16 12 T为基解 且为基可行解 解的集合 非可行解 可行解 解的集合 基础解 解的集合 可行解 基础解 基础可行解 解的集合 可行解 基础解 基础最优解 基础可行解 第二节 线性规划解的性质 几何意义 凸集 Convexset 概念 设D是n维欧氏空间的一个点集 若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 6 凸集 例 非凸集 例 X X 1 1 X 2 为什么 X1 X2 X 1 X 2 X 图 1 7 例 X1 X2 X 1 X 2 X 2 X 1 X 2 图 1 7 X 例 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 例 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 两个基本概念 凸组合 Convexcombination 设x 1 x 2 x k 是n维欧氏空间中的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 的凸组合 两个基本概念 顶点 Extremeopint 设D是凸集 若D中的点x不能成为D中任何线段上的内点 则称x为凸集D的顶点 即 若D中的任意两点x 1 x 2 不存在数 0 1 使得x x 1 1 x 2 成立 则称x为凸集D的一个顶点 例 多边形上的点是顶点 圆周上的点都是顶点 线性规划的基本定理 定理1 1线性规划问题的可行解集是凸集 即连接线性规划问题任意两个可行解的线段上的点仍然是可行解 证明线性规划问题的可行解的集合为D X AX b X 0 任意X1 X2 D 有AX1 b X1 0 AX2 b X2 0 令X X1 1 X2 则AX A X1 1 X2 AX1 1 AX2 b 1 b b 且 X1 1 X2 0 故X D 线性规划的基本定理 定理1 2线性规划问题的可行解x x1 x2 xn T为基础可