线性函数极值.pdf

1 实验八实验八 线性函数极值求解线性函数极值求解 西安交通大学数学与统计学院 刘康民 办公地点 理科楼214 电子邮箱 liukm 2 实验目的实验目的 本实验通过具体问题介绍线性规划的一本实验通过具体问题介绍线性规划的一 些基本概念和性质 掌握线性规划问题的图解些基本概念和性质 掌握线性规划问题的图解 法法 软件解法以及当线性规划问题规模较小软件解法以及当线性规划问题规模较小 并且存在最优解时的理论解法并且存在最优解时的理论解法 3 实验内容实验内容 本实验主要介绍线性函数的极值求解方法本实验主要介绍线性函数的极值求解方法 即线性即线性 规划问题规划问题 它是运筹学的一个重要分支它是运筹学的一个重要分支 在科学实践在科学实践 中有着广泛的应用中有着广泛的应用 不仅许多实际课题属于线性规划不仅许多实际课题属于线性规划 问题问题 而且运筹学其它分支中的一些问题也可转化为而且运筹学其它分支中的一些问题也可转化为 线性规划问题来计算线性规划问题来计算 因此因此 线性规划在最优化学科线性规划在最优化学科 中占有重要地位中占有重要地位 本实验通过具体问题介绍线性规划本实验通过具体问题介绍线性规划 的一些基本概念和性质的一些基本概念和性质 给出求解线性规划问题的图给出求解线性规划问题的图 解法和软件解法以及当线性规划问题规模较小解法和软件解法以及当线性规划问题规模较小 并且并且 存在最优解时的理论解法存在最优解时的理论解法 4 美国空军为了保证士兵的营养 规定每餐的食品中 美国空军为了保证士兵的营养 规定每餐的食品中 要保证一定的营养成份 例如蛋白质 脂肪 维生要保证一定的营养成份 例如蛋白质 脂肪 维生 素等等 都有定量的规定 当然这些营养成份可以素等等 都有定量的规定 当然这些营养成份可以 由各种不同的食物来提供 例如牛奶提供蛋白质和由各种不同的食物来提供 例如牛奶提供蛋白质和 维生素 黄油提供蛋白质和脂肪 胡萝卜提供维生维生素 黄油提供蛋白质和脂肪 胡萝卜提供维生 素 等等 由於战争条件的限制 食品种类有限 素 等等 由於战争条件的限制 食品种类有限 又要尽量降低成本 於是在一盒套餐中 如何决定又要尽量降低成本 於是在一盒套餐中 如何决定 各种食品的数量 使得既能满足营养成份的需要 各种食品的数量 使得既能满足营养成份的需要 又可以降低成本 又可以降低成本 现代管理问题虽然千变万化 但大致上总是要利用现代管理问题虽然千变万化 但大致上总是要利用 有限的资源 去追求最大的利润或最小的成本 如有限的资源 去追求最大的利润或最小的成本 如 何解决这些问题 何解决这些问题 解决问题的方法解决问题的方法 各种各种规划规划 5 在波斯湾战争期间在波斯湾战争期间 美国军方利用线性规划美国军方利用线性规划 有效地解决了部队给养和武器调运问题有效地解决了部队给养和武器调运问题 对促对促 进战争的胜利进战争的胜利 起了关键的作用起了关键的作用 甚至有这样甚至有这样 的说法 因为使用炸药的说法 因为使用炸药 第一次世界大战可说第一次世界大战可说 是是 化学的战争化学的战争 因为使用原子弹 因为使用原子弹 第二次第二次 世界大战可说是世界大战可说是 物理的战争物理的战争 因为使用线 因为使用线 性规划性规划 波斯湾战争可称为波斯湾战争可称为 数学的战争数学的战争 在历史上在历史上 没有哪种数学方法没有哪种数学方法 可以像线性规可以像线性规 划那样划那样 直接为人类创造如此巨额的财富直接为人类创造如此巨额的财富 并并 对历史的进程发生如此直接的影响对历史的进程发生如此直接的影响 6 例例1 生产计划问题 生产计划问题 问 问 A B各生产多少各生产多少 可获最大利润可获最大利润 A B 备用资源备用资源 煤煤 1 2 30 劳动日劳动日 3 2 60 仓库仓库 0 2 24 利润利润 40 50 一 引例 某企业生产某企业生产A B两两 种产品 成本和利润指标如下 种产品 成本和利润指标如下 7 x1 2x2 30 3x1 2x2 60 2x2 24 x1 x2 0 max Z 40 x1 50 x2 解解 设产品设产品A B的产量分别为变量的产量分别为变量x1 x2 则 则 s t A B 备用资源备用资源 煤煤 1 2 30 劳动日劳动日 3 2 60 仓库仓库 0 2 24 利润利润 40 50 8 例2 资源配置问题 现有四种原料 其单位成本 和所含维生素A B C成分如下 求 最低成本的原料混合方案 A B 每单位成本 原料1 4 1 0 2 原料2 6 1 2 5 原料3 1 7 1 6 原料4 2 5 3 8 每单位添加剂中 维生素最低含量 12 14 8 9 解 解 minZ 2x1 5x2 6x3 8x4 4x1 6x2 x3 2x4 12 x1 x2 7x3 5x4 14 2x2 x3 3x4 8 xi 0 i 1 4 设每单位添加剂中原料设每单位添加剂中原料i的用量为的用量为xi i 1 2 3 4 则 则 s t A B 每单位成本每单位成本 原料原料1 4 1 0 2 原料原料2 6 1 2 5 原料原料3 1 7 1 6 原料原料4 2 5 3 8 每单位添加剂中每单位添加剂中 维生素最低含量维生素最低含量 12 14 8 10 有一批长度为有一批长度为7 4m的钢筋若干根 现有的钢筋若干根 现有5种下料方种下料方 案 分别作成案 分别作成2 9m 2 1m 1 5m的钢筋架子各的钢筋架子各100 根 每种下料方案及剩余料头如下表所示 根 每种下料方案及剩余料头如下表所示 例例3 合理下料合理下料问题问题 问 如何下料使得剩余料头最少 问 如何下料使得剩余料头最少 2 9m 1 2 0 1 02 9m 1 2 0 1 0 2 1m 0 0 2 2 12 1m 0 0 2 2 1 1 5m 3 1 2 0 31 5m 3 1 2 0 3 合计合计 7 4 7 3 7 2 7 1 6 67 4 7 3 7 2 7 1 6 6 料头料头 0 0 1 0 2 0 3 0 80 0 1 0 2 0 3 0 8 11 解 解 设按第设按第i种方案下料的原材料为种方案下料的原材料为xi根 则 根 则 minZ 0 1x2 0 2x3 0 3x4 0 8x5 x1 2x2 x4 100 2x3 2x4 x5 100 3x1 x2 2x3 3x5 100 xi 0 i 1 5 且为整数 且为整数 s t 2 9m 1 2 0 1 02 9m 1 2 0 1 0 2 1m 0 0 2 2 12 1m 0 0 2 2 1 1 5m 3 1 2 0 31 5m 3 1 2 0 3 合计合计 7 4 7 3 7 2 7 1 6 67 4 7 3 7 2 7 1 6 6 料头料头 0 0 1 0 2 0 3 0 80 0 1 0 2 0 3 0 8 12 例4 运输问题 1 2 3 库存容量 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10 需求 40 15 35 仓库 车间 某棉纺厂的原棉需从仓库运送到各车间 各车间原 棉需求量 单位产品从各仓库运往各车间的运输费 以及各仓库的库存容量如下表所列 问 如何安排运输任务使得总运费最小 13 设设xij为为i 仓库运到仓库运到 j车间的原棉数量车间的原棉数量 i 1 2 3 j 1 2 3 则 则 minZ 2x11 x12 3x13 2x21 2x22 4x23 3x31 4x32 2x33 解 解 x11 x12 x13 50 x21 x22 x23 30 x31 x32 x33 10 x11 x21 x31 40 x12 x22 x32 15 x13 x23 x33 35 xij 0 i 1 2 3 j 1 2 3 s t 1 2 3 库存容量库存容量 1 2 1 3 50 2 2 2 4 30 3 3 4 2 10 需求需求 40 15 35 仓库仓库 车间车间 14 例5 连续投资10万元于4个项目 各项目投资时间 和本利情况如下 项目A 从第1年 到第4年每年初要投资 次年末 回收本利1 15倍 项目B 第3年初投资 到第5年末回收本利1 25倍 最大投资4万元 项目C 第2年初投资 到第5年末回收本利1 40倍 最大投资3万元 项目D 每年初投资 每年末回收本利1 11倍 求 如何分配投资资金使得5年末总资本最大 15 以上问题的特点 2 某项任务确定后 如何安排人力 财力 物力 使之最省 1 在人力 财力 资源给定条件下 如何 合理安排任务 使得效益最高 即以上问题都是在一定条件下 求目标函数 的最大值或最小值问题 而且目标函数和约 束条件都是线性函数 这类问题称为线性规 划LP Linear Programming LP 问题 16 二二 线性规划问题的一般形式线性规划问题的一般形式 max min Z c1x1 c2x2 cnxn a11x1 a12x2 a1nxn b b1 1 a21x1 a22x2 a2nxn b b2 2 am1x1 am2x2 amnxn b bm m xj j 0 0 j 1 n s t T i zfx s tAxbxin min max 0 1 2 或或 或或或或 或或 17 三 线性规划问题的求解方法 2 二元线性规划问题的图解法 3 线性规划问题的理论解法 1 线性规划问题的MATLAB软件解法 18 x linprog f A b 求解 min z f x A x b 1 1 求解线性规划的求解线性规划的MATLABMATLAB命令命令 若没有不等式约束 可用 替代A和b 若没有等式约束 可用 替代Aeq和beq 若某个xi下无界或上无界 可设定 inf或 inf 用 x Fval 代替上述命令行中的x 可得最优解处的函 数值Fval x linprog f A b Aeq beq 求解 min z f x A x b Aeq x beq x linprog f A b Aeq beq lb ub 指定lb x ub 19 x fval exitflag output linprog f A b Aeq beq lb ub X为最优解向量 为最优解向量 fval为最优值 为最优值 exitflag描述描述 linprog的终止条件 若为正值 表示目标函数的终止条件 若为正值 表示目标函数 收敛于解收敛于解x 若为负值 表示目标函数不收敛 若为负值 表示目标函数不收敛 若为零值 表示已经达到函数评价或迭代的最若为零值 表示已经达到函数评价或迭代的最 大次数 大次数 output为返回优化算法信息的一个数为返回优化算法信息的一个数 据结构 据结构 output iteration表示迭代次数 表示迭代次数 output algorithm表示所采用的算法 表示所采用的算法 output funcCount表示函数评价次数 表示函数评价次数 20 x1 2x2 30 3x1 2x2 60 2x2 24 min Z 40 x1 50 x2 s t 例例1 解 程序如下解 程序如下 sy0601 c c 40 40 50 50 a 1 2 3 2 0 2 a 1 2 3 2 0 2 b 30 60 24 b 30 60 24 x x linprog c a b c a b z c xz c x 21 x1 x2 5 6 x1 10 1 x2 4 4 例例2 min Z 4x1 3x2 s t 解 解 sy0602sy0602 m m c 4 3 a 1 1 b 5 c 4 3 a 1 1 b 5 vlb vlb 6 6 1 1 lower bound of vector x vub 10 4 vub 10 4 upper bound of vector x x linprog c a b vlb vub x linprog c a b vlb vub z c xz c x 22 x1 x2 x3 7 x1 x2 x3 2 2 x1 x2 x3 0 0 例例3 min Z x1 2x2 3x3 s t 解 解 sy060sy0603 3 m m c c 1 2 1 2 3 a 1 1 1 3 a 1 1 1 1 1 1 1 1 1 b 7 b 7 2 2 vlb 0 0 0 vlb 0 0 0 lower bound of vector x vub vub upper bound of vector x x linprog c a b vlb vub x linprog c a b vlb vub z c xz c x 23 minZ 2x1 x2 3x3 2x4 2x5 4x6 3x7 4x8 2x9 x1 x4 x7 40 x2 x5 x8 15 x3 x6 x9 35 x1 x2 x3 50 x4 x5 x6 30 x7 x8 x9 10 xi 0 i 1 2 9 s t 例例4 24 sy060 sy0604 4 m m c 2 1 3 2 2 4 3 4 2 c 2 1 3 2 2 4 3 4 2 beq 40 15 35 b 50 30 10 beq 40 15 35 b 50 30 10 a 1 1 1 0 0 0 0 0 0 a 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 aeq 1 0 0 1 0 0 1 0 0 aeq 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 vlb zeros 9 1 vlb zeros 9 1 lower bound of vector x vub vub upper bound of vector x x linprog c a b aeq beq vlb vub x linprog c a b aeq beq vlb vub z c xz c x 解 解 25 2 2 线性规划问题的图解法线性规划问题的图解法 Ax b 1 x 0 2 max Z cx 3 定义1 满足约束满足约束 1 2 的的x x1 xn T称为称为 LP问题的可行解 全部可行解的集合称为问题的可行解 全部可行解的集合称为可行可行 域 域 定义2 满足满足 3 的可行解称为的可行解称为LP问题的问题的最优解最优解 26 图解法步骤图解法步骤 1 1 作出可行域的图形 作出可行域的图形 2 2 作出目标函数等值线 作出目标函数等值线 3 3 将目标函数等值线自坐标原点开始向 将目标函数等值线自坐标原点开始向 上 下 平移 与可行域的最后一个交点就是上 下 平移 与可行域的最后一个交点就是 最优解 最优解 4 4 求最优解坐标和最优值 求最优解坐标和最优值 27 x1 2x2 30 3x1 2x2 60 2x2 24 x1 x2 0 max Z 40 x1 50 x2 例例1 s t 二元二元线性规划问题的图解法线性规划问题的图解法 A B 备用资源备用资源 煤煤 1 2 30 劳动日劳动日 3 2 60 仓库仓库 0 2 24 利润利润 40 50 28 x2 0 0 纵纵 0 30 20 0 2x2 24 1 确定可行域 确定可行域 解 解 x1 0 0 x1 0 0 横横 x2 0 0 x1 2x2 30 x1 2x2 30 0 15 30 0 与坐标轴交点与坐标轴交点 3x1 2x2 60 2x2 24 3x1 2x2 60 0 x2 10 20 30 D A B C 3x1 2x2 60 x1 2x2 30 2x2 24 30 10 x1 20 29 2 求最优解 求最优解 x 15 7 5 Z 40 x1 50 x2 0 40 x1 50 x2 x1 2x2 30 3x1 2x2 60 C点点 0 10 20 30 x2 D A B C 3x1 2x2 60 x1 2x2 30 2x2 24 20 30 10 x1 Z 975 Z 0 Zmax 975 30 0 1 maxZ 40 x1 80 x2 x1 2x2 30 3x1 2x2 60 2x2 24 x1 x2 0 0 例例2 求解求解 s t 最优解 最优解 BC线段线段 B点点 x 1 6 12 C点点 x 2 15 7 5 BC线段线段 21 2 1 1xx x x x maxZ 1200 0 10 20 30 x2 D A B C 3x1 2x2 60 x1 2x2 30 2x2 24 20 30 10 x1 Z 1200 Z 0 31 例 例 max Z 3x1 2x2 x1 x2 1 1 x1 x2 0 0 即无可行解即无可行解 x2 x1 1 1 0 s t 可行域可行域为空集为空集 x1 x2 1 1 32 nnx cxcxcZ 2211 max 3 3 线性规划问题的理论解法线性规划问题的理论解法 11112211 1122 0 1 2 nn mmmnnm i a xa xa xb s t axaxaxb xin 线性规划问题的标准形式 33 特点 特点 1 所有约束条件是等式 2 约束条件右端常数项为非负 3 所有变量是非负 xCZ T max 0 x bAx ts A称为约束矩阵 量 量 称为价值向量或赋权向称为价值向量或赋权向 T C 34 化一般线性规划问题为标准形 化一般线性规划问题为标准形 1 iij n j ij bbxa 约束条件的转换 约束条件的转换 0 11 in iinj n j ijiinj n j ij x bxxabxxa或或 in x 称为称为剩余变量剩余变量或或松弛变量松弛变量 35 x1 2x2 x3 30 3x1 2x2 x4 60 2x2 x5 24 x1 x5 0 0 maxZ 40 x1 50 x2 0 x3 0 x4 0 x5 x1 2x2 30 3x1 2x2 60 2x2 24 x1 x2 0 max Z 40 x1 50 x2 例例1 s t 其中其中x3 x4 x5 为松弛变量为松弛变量 s t 36 minZ 2x1 5x2 6x3 8x4 4x1 6x2 x3 2x4 12 x1 x2 7x3 5x4 14 2x2 x3 3x4 8 xi 0 i 1 4 例例2 minZ 2x1 5x2 6x3 8x4 0 x5 0 x6 0 x7 4x1 6x2 x3 2x4 x5 12 x1 x2 7x3 5x4 x6 14 2x2 x3 3x4 x7 8 xi 0 i 1 2 7 其中其中x5 x6 x7 为剩余变量为剩余变量 s t s t 37 变量的转换变量的转换 例例3 令令 x1 x1 x1 3x1 2x2 8 x1 4x2 14 x2 0 0 x1 为自由变量为自由变量 1 1 3 x1 3 x1 2x2 8 x1 x1 4x2 14 x1 x1 x2 0 0 2 38 0 jj jjj j xx xxx x 则可令则可令 由变量 由变量 无非负限制 称为自无非负限制 称为自如果某个变量如果某个变量 jj lx 0 jjj lxy jj lx 0 jjj xly 39 令令 x1 x1 6 则则 0 x1 16 x1 x2 5 6 x1 10 x2 0 0 3 6 6 x1 6 10 6 易知易知 例例4 3 x1 x2 11 x1 16 x1 x2 0 0 4 40 目标函数的转换目标函数的转换 Z Z n j jj xcZ 1 min n j jjc cZ 1 max 令令Z Z x o Z 41 将以下线性规划问题将以下线性规划问题 x1 x2 x3 7 x1 x2 x3 2 2 x1 x2 0 0 x3为自由变量为自由变量 化为标准型 化为标准型 例例5 min Z x1 2x2 3x3 s t 42 令令x3 x4 x5 加松弛变量加松弛变量x6 加剩余变量加剩余变量x7 令令 Z Z max Z x1 2x2 3x4 3x5 解解 min Z x1 2x2 3x3 x1 x2 x3 7 x1 x2 x3 2 2 x1 x2 0 0 s t x1 x2 x4 x5 x6 7 x1 x2 x4 x5 x7 2 x1 x2 x4 x5 x6 x7 0 0 s t 43 线性规划问题的理论解法 线性规划问题的理论解法 凸集凸集 定义定义1 Ax b 1 x 0 2 maxZ cx 3 设设D是是n维欧氏空间的一个集合维欧氏空间的一个集合 任意点任意点x 1 x 2 D D 若任一满足若任一满足 x x 1 1 x 2 0 1 的点的点x D D 则则D称为称为凸集凸集 x 2 x 1 x 设线性规划的标准型 44 B P1 Pm N Pm 1 Pn a11 a1m a21 a2m am1 amm P1 Pm a1m 1 a1n a2m 1 a2n amm 1 amn Pm 1 Pn A 定义定义2 基基 基阵基阵 若若A中一个子矩阵方阵中一个子矩阵方阵B可逆 可逆 则矩阵则矩阵B称为称为LP问题的一个问题的一个基基 基阵基阵 基向量基向量 P1 Pm 非基向量非基向量 Pm 1 Pn 基变量基变量 x1 xm xB 非基变量非基变量 xN xm 1 xn 设设 x x1 xm xm 1 xn xB xN 45 xB B 1 b B 1N xN A B N x xB xN Ax b 记记 BxB NxN b BxB b NxN bAx x NxbB x x x N N N B 的一个解的一个解为为 则则 1 46 简称可行解 这时的基简称可行解 这时的基B B称为称为可行基 可行基 称为称为Ax b的一个的一个基本基本可行可行解 解 B 1 b 0 x 若若B 1 b 0 0 1 0 0 N B b xxAxb 令令则则称称为为的的一一个个基基本本解解 个基本可行解个基本可行解最多有最多有 mn n m c m n 47 x1 2x2 x3 30 30 3x1 2x2 x4 60 2x2 x5 24 x1 x5 0 0 例例1 b 30 60 24 取取B P3 P4 P5 I 可逆可逆 基阵基阵 1 2 1 0 0 3 2 0 1 0 0 2 0 0 1 P1 P2 P3 P4 P5 A N P1 P2 非基阵非基阵 非基向量非基向量 xN x1 x2 xB x3 x4 x5 基向量基向量 x xN xB 解向量解向量 48 xB B 1 b B 1N xN Ax b 令令 0 0 xN x1 x2 则基本解则基本解 0 0 30 60 24 x xN xB 因为因为x 0 0 是是基本基本可行解 可行解 49 又又 由由det B1 6 0 知知B1可逆可逆 可以充当基矩阵可以充当基矩阵 1 2 1 3 2 0 0 2 0 若取若取B1 P1 P2 P3 相应的非基阵相应的非基阵 N1 P4 P5 xB1 x1 x2 x3 基变量基变量 x4 x5 xN1 非基变量非基变量 得基本解得基本解 令令 12 12 6 0 0 xB1 xN1 x B1 1 b 0 x4 x5 xN1 0 0 非非基本基本可行解可行解 50 x3 x4 0 0