《管理定量分析》第三部分最优化.ppt

管理定量分析周立业 第三章最优化方法 第一节线性规划概述第二节线性规划问题的解法第三节线性规划问题的对偶问题第四节整数规划 运输 分配问题 第五节动态规划 案例 河流污水处理费用优化 A城市排2万立方米 天污水 到城市B前20 自然净化 问题 要求污水含量不大于0 2 如何处理污水费用最少 支流200万立方米 天 主河流500万立方米 天 B城市排1 4万立方米 天污水 处理成本 A市1000元 万立方米 B市800元 万立方米 一 线性规划问题的提出 利用有限资源 某工厂在计划期内要安排生产 两种产品 已知生产单位产品所需的设备台数及A B两种原材料的消耗量 见表1 1 该工厂每生产一件产品 可获利润2元 每生产一件产品 可获利润3元 问应如何安排生产计划使该工厂获得的利润最大 第一节线性规划概述 生产计划问题 如何制定生产计划 使两种产品总利润最大 利用有限资源 某鸡厂共饲养1万只鸡 用大豆和谷物混合喂养 已知鸡消耗饲料1kg 天 鸡至少需要蛋白质 钙分别为0 22 0 06kg 天 每公斤大豆含蛋白质 钙为50 0 2 每公斤谷物含蛋白质 钙为10 0 1 大豆和谷物售价0 4 0 2元 kg 设 每只鸡需要大豆x1公斤 谷物x2公斤 设 养鸡场每天需要大豆x1公斤 谷物x2公斤 二 线性规划的定义和数学描述 模型 1 定义 对于求取一组变量xj j 1 2 n 使之既满足线性约束条件 又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题 简称线性规划 LP 2 配比问题和生产计划问题的线性规划模型的特点 用一组未知变量表示要求的方案 这组未知变量称为决策变量 存在一定的限制条件 且为线性表达式 有一个目标要求 最大化 当然也可以是最小化 目标表示为未知变量的线性表达式 称之为目标函数 对决策变量有非负要求 3 LP的数学描述 数学模型 1 一般形式 2 紧缩形式 3 矩阵形式 其中 4 向量 矩阵形式 其中 三 LP的标准型 1 LP标准型的概念 1 什麽是LP的标准型 2 LP标准型的特点 目标函数约定是极大化Max 或Min 约束条件均用等式表示 决策变量限于取非负值 右端常数b均为非负值 3 数学表达式 有几种形式 为什麽 如何书写 2 LP问题的标准化 1 目标函数的标准化 2 约束条件的标准化 约束条件是 类型 左边加非负松弛变量 约束条件是 类型 左边减非负剩余变量 变量符号不限 引入新变量 四 在管理中一些典型的线性规划应用1 合理利用线材问题 如何在保证生产的条件下 下料最少2 配料问题 在原料供应量的限制下如何获取最大利润3 投资问题 从投资项目中选取方案 使投资回报最大4 产品生产计划 合理利用人力 物力 财力等 使获利最大5 劳动力安排 用最少的劳动力来满足工作的需要6 运输问题 如何制定调运方案 使总运费最小 线性规划总结 一 线性规划的组成 目标函数MaxF或MinF约束条件s t subjectto 满足于决策变量用符号来表示可控制的因素 二 建模过程1 理解要解决的问题 了解解题的目标和条件 2 定义决策变量 x1 x2 xn 每一组值表示一个方案 3 用决策变量的线性函数形式写出目标函数 确定最大化或最小化目标 4 用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 三 线性规划模型的一般形式目标函数 约束条件 例题分析1 生产计划问题 例1 某工厂在计划期内要安排 两种产品的生产 已知生产单位产品所需的设备台时及A B两种原材料的消耗 资源的限制 如下表 问 工厂应分别生产多少单位 产品才能使工厂获利最多 例题分析1 生产计划问题 解 工厂应分别生产 产品x1 x2单位 则所求的线性规划模型为 例题分析2 食谱问题 例1已知某人每周所需的营养成分 所食用的食品及单位食品所含营养如下表所示 问这个人每周应食用大米 白菜 鸡蛋和猪肉各多少 能使生活费用最省 例题分析2 食谱问题 解 设这个人每周应食用大米 白菜 鸡蛋 猪肉各为x1 x2 x3 x4 则所求的线性规划模型为 例题分析3 人力资源分配问题 例2 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下 设司机和乘务人员分别在各时间段一开始时上班 并连续工作八小时 问该公交线路怎样安排司机和乘务人员 既能满足工作需要 又配备最少司机和乘务人员 例题分析3 人力资源分配问题 解 设xi表示从第i班次开始上班的司机和乘务人员数 i 1 2 3 4 5 6 这样我们建立如下的数学模型 例题分析4 合理下料问题 例4假定现有一批某种型号的圆钢长8米 需要裁取长2 5米的毛坯100根 长1 3米的毛坯200根 问应该怎样选择下料方式才能既满足需要 又使总的用料最省 解 各种可能的裁剪方案如下表所示 例题分析4 合理下料问题 设x1 x2 x3 x4分别为上面4种方案下料的原材料根数 这样我们建立如下的数学模型 例题分析5 投资问题 例5某部门现有资金200万元 今后五年内考虑给以下的项目投资 已知 项目A 从第一年到第五年每年年初都可投资 当年末能收回本利110 项目B 从第一年到第四年每年年初都可投资 次年末能收回本利125 但规定每年最大投资额不能超过30万元 项目C 需在第三年年初投资 第五年末能收回本利140 但规定最大投资额不能超过80万元 项目D 需在第二年年初投资 第五年末能收回本利155 但规定最大投资额不能超过100万元 问应如何确定这些项目的每年投资额 使得第五年年末拥有资金的本利金额为最大 例题分析4 投资问题 解 设xij i 1 5 j 1 4 表示第i年初投资于A j 1 B j 2 C j 3 D j 4 项目的金额 这样我们建立如下的决策变量 12345Ax11x21x31x41x51Bx12x22x32x42Cx33Dx24 例题分析5 投资问题 投资问题 作业 某部门现有资金100万元 今后五年内考虑给以下的项目投资 已知 项目A 五年内每年初均可投资 且金额不限 投资期限1年 年回报率7 项目B 五年内每年初均可投资 且金额不限 投资期限2年 年回报率10 不计复利 项目C 五年内每年初均可投资 且金额不限 投资期限3年 年回报率12 不计复利 项目D 只在第一年初有一次投资机会 最大投资额50万元 投资期限4年 年回报率20 不计复利 项目E 在第二年和第四年初有一次投资机会 最大投资额30万元 投资期限1年 年回报率30 项目F 在第四年初有一次投资机会 金额不限 投资期限2年 年回报率25 假设当年投资金额及其收益均可用于下一年投资 问公司如何投资才能使得第五年末收回的本利金额最大 合理下料问题 作业 新华造纸厂接到三份订购卷纸的订单 其长和宽的要求如下表所示 该厂生产1米和2米两种标准宽度的卷纸 假定卷纸的长度无限制 即可以连接起来达到所需的长度 问如何切割才能使切割损失的面积最小 产品配套问题 作业 假定一个工厂的甲 乙 丙三个车间生产同一产品 每件产品包含4个A零件和3个B零件 这两种零件由两种不同的原材料制成 而这两种原材料的现有数额分别是100千克和200千克 第个生产班的原材料需要量和零件产量如下表所示 问 这三个车间各应开多少班次才能使这种产品的配套数达到最大 计划生产问题 作业 某化工厂要用三种原料混合配置三种不同规格的产品 各产品的规格单价如下表所示 问 如何安排生产利润最大 1 基本概念 凸集 设K是n维欧氏空间的一个点集 若任意两点X 1 K X 2 K的连线上的一切点 X 1 1 X 2 K 0 1 则称K为凸集 五 线性规划解的性质 凸组合设X 1 X 2 X k 是n维欧氏空间中的K个点 若存在k个数 1 2 k 满足0 i 1 i 1 2 k 且 则称X 1X 1 2X 2 kX k 为X 1 X 2 X k 的凸组合 顶点设K是凸集 X K 若X不能用X 1 K X 2 K的线性组合表示 即X X 1 1 X 2 0 1 则称X为K的一个顶点 也称极点或角点 2 线性规划问题解的性质定理 定理1 1线性规划问题的可行解集 即可行域 是凸集 定理1 2线性规划几何理论基本定理若 则X是D的一个顶点的充分必要条件是X为线性规划的基本可行解 定理1 3若可行域非空有界 则线性规划问题的目标函数一定可以在可行域的顶点上达到最优值 定理1 4若目标函数在k个点处达到最优值 k 2 则在这些顶点的凸组合上也达到最优值 上述4个定理的一些有意义的启示 LP的可行域一定是凸集 但是凸集不一定成为LP的可行域 而非凸集一定不会是LP的可行域 线性规划的基本可行解和可行域的顶点是一一对应的 在可行域中寻找LP的最优解可以转化为只在可行域的顶点中找 从而把一个无限的问题转化为一个有限的问题 若已知一个LP有两个或两个以上最优解 那麽就一定有无穷多个最优解 六 LP问题的各种解 可行解 满足约束条件和非负条件的决策变量的一组取值 可行解集 所有可行解的集合 可行域 LP问题可行解集构成n维空间的区域 可以表示为 4 最优解 使目标函数达到最优值的可行解 5 最优值 最优解对应目标函数的取值 6 求解LP问题 求出问题的最优解和最优值 7 基 设A是约束方程组m n的系数矩阵 A的秩R A m B是A中m m阶非奇异子式 即 B 0 则称B是LP问题的一个基 8 基变量 B P1 P2 Pm 称Pj j 1 2 m 为基向量 与Pj对应的变量xj j 1 2 m 称为基变量 其余的xm 1 xn为非基变量 9 基本解 令非基变量等于0 从AX b中解出的基变量所得的解称为LP关于基B的基本解 可行解与基本解的区别 基本解设AX b是含n个决策变量 m个约束条件的LP的约束方程组 若B是LP问题的一个基 若令不与B的列相应的n m个分量 非基变量 都等于零 所得方程组的解X x1 x2 xm 0 0 T称为方程组AX b关于基B的一个基本解 简称为LP的基本解 10 基本可行解 对应的基为可行基 满足非负条件的基本解 11 退化的基本可行解非零分量个数小于m 至少有一个基变量取值为0 12 最优基该基对应的基本可行解为LP的最优解 结论 13 基本最优解 对应的基为最优基 使目标函数达到最优值的基本可行解 最优解 基本最优解 1 图解法线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程 求解的思路是 先将约束条件加以图解 求得满足约束条件和非负条件的解的集合 即可行域 然后结合目标函数的要求从可行域中找出最优解 第二节线性规划问题的解法 实施图解法 以求出最优生产计划 最优解 给出最优值 例 由于线性规划模型中只有两个决策变量 因此只需建立平面直角坐标系就可以进行图解了 第一步 建立平面直角坐标系标出坐标原点 坐标轴的指向和单位长度 用x1轴表示产品A的产量 用x2轴表示产品B的产量 第二步 对约束条件加以图解 第三步 画出目标函数等值线 结合目标函数的要求求出最优解 最优生产方案 第四步 最优解带入目标函数 得出最优值 约束条件的图解 每一个约束不等式在平面直角坐标系中都代表一个半平面 只要先画出该半平面的边界 然后确定是哪个半平面 以第一个约束条件 为例 说明图解过程 代表一个半平面其边界 点A B连线AB经济含义 A0B 点A 8 0 连接AB 设备全部占用所生产 数量对应的点的集合 全部的设备都用来生产 产品而不生产 产品 那么 产品的最大可能产量为8台 计算过程为 x1 2 0 8 x1 8 0B 设备没有全部占用所生产 数量对应的点的集合 约束条件及非负条件代表的公共部分 图中阴影区 就是满足所有约束条件和非负条件的点的集合 即可行域 在这个区域中的每一个点都对应着一个可行的生产方案 另两个约束条件的边界直线CD EF 4x1 16 4x2 12 令Z 2x1 3x2 c 其中c为任选的一个常数 在图中画出直线2x1 3x2 c 即对应着一个可行的生产结果 即使两种产品的总利润达到c 这样的直线有无数条 且相互平行 称这样的直线为目标函数等值线 只要画两条目标函数等值线 如令c 0和c 6 可看出目标函数值变化的方向 即虚线l1和l2 箭头为产品的总利润递增的方向 对应坐标x1 4 x2 2是最佳的产品组合 4 2 T就是线性规划模型的最优解使产品的总利润达到最大值maxZ 2 4 3 2 14就是目标函数最优值 沿着箭头方向平移目标函数等值线 达到可行域中的最远点E E点就是最优点 尽管最优点的对应坐标可以直接从图中给出 但是在大多数情况下 对实际问题精确地看出一个解答是比较困难的 所以 通常总是用解联立方程的方法求出最优解的精确值 比如C点对应的坐标值我们可以通过求解下面的联立方程 即求直线AB和CD的交点来求得 直线AB x1 2x2 8直线CD 4x1 16 将例1 1稍作改动形成案例1 仍使用图解法来求解 案例1 某工厂生产A B C三种产品 每吨的利润分别为2000元 3000元 1000元 生产单位产品所需的工时及原材料如表1 2所示 应如何制定日生产计划 使三种产品的总利润最大 设三种产品的产量分别是x1 x2 x3吨 由于有三个决策变量 用图解法求解下面的线性规划时 必须首先建立空间直角坐标系 结果有唯一最优解可行域是一个非空有界区域 可行域有几种可能 解有几种可能 唯一最优解 例1 3将例1 1中目标要求改为极小化 目标函数和约束条件均不变 则可行域与例1 1相同 目标函数等值线也完全相同 只是在求最优解时 应沿着与箭头相反的方向平移目标函数等值线 求得的结果是有唯一最优解x1 0 x2 0 对应着图1 6中的坐标原点 无穷多个最优解 沿着箭头的方向平移目标函数等值线 发现平移的最终结果是目标函数等值线将与可行域的一条边界线段AB重合 结果表明 该线性规划有无穷多个最优解 线段AB上的所有点都是最优点 它们都使目标函数取得相同的最大值Zmax 14 无界解 如图中可行域是一个无界区域 如阴影区所示 虚线为目表函数等值线 沿着箭头指的方向平移可以使目标函数值无限制地增大 但是找不到最优解 这种情况通常称为无 有限最优解 或 最优解无界 如果一个实际问题抽象成像例1 4这样的线性规划模型 比如是一个生产计划问题 其经济含义就是某些资源是无限的 产品的产量可以无限大 此时应重新检查和修改模型 否则就没有实际意义 注意 对于无界可行域的情况 也可能有唯一最优解或无穷多个最优解 1947年G B Dantzig提出的单纯形法提供了方便 有效的通用算法求解线性规划 2单纯形法 一 单纯形法的基本思想1 顶点的逐步转移 即从可行域的一个顶点 基本可行解 开始 转移到另一个顶点 另一个基本可行解 的迭代过程 转移的条件是使目标函数值得到改善 逐步变优 当目标函数达到最优值时 问题也就得到了最优解 2 需要解决的问题 1 为了使目标函数逐步变优 怎么转移 2 目标函数何时达到最优 判断标准是什么 二 单纯形法原理 用代数方法求解LP 例 第一步 引入非负的松弛变量和剩余变量x3 x4 x5 将该LP化为标准型 第二步 寻求初始可行基 确定基变量 对应的基变量是x3x4x5 第三步 写出初始基本可行解和相应的目标函数值 两个关键的基本表达式 用非基变量表示基变量的表达式 初始基本可行解 用非基变量表示目标函数的表达式 请解释结果的经济含义 不生产任何产品 资源全部节余 x3 8x4 16 x5 12 产品的总利润为0 第四步 分析两个基本表达式 看看目标函数是否可以改善 分析用非基变量表示目标函数的表达式 非基变量前面的系数均为正数 所以任何一个非基变量进基都能使Z值增加通常把非基变量前面的系数叫 检验数 选哪一个非基变量进基 选x1为进基变量 换入变量 问题讨论 能否选其他的非基变量进基 任意一个 任意一个正检验数对应的非基变量 最大正检验数对应的非基变量 排在最前面的正检验数对应的非基变量 确定出基变量 问题讨论 x2进基意味着其取值从0变成一个正数 经济意义 生产B产品 能否无限增大 当x2增加时 x3 x4 x5如何变化 现在的非基变量是哪些 具体如何确定换出变量 由用非基变量表示基变量的表达式 当x2增加时 x3 x4 x5会减小 但有限度 必须大于等于0 以保持解的可行性 当x2的值从0增加到3时 x5首先变为0 此时x5 3 0因此选x5为出基变量 换出变量 这种用来确定出基变量的规则称为 最小比值原则 或 原则 基变换新的基变量 x2 x3 x4 新的非基变量x1 x5 写出用非基变量表示基变量的表达式 可得新的基本可行解X 1 0 3 2 16 0 T 由 写出用非基变量表示目标函数的表达式 可得相应的目标函数值为Z 1 9 检验数仍有正的返回 进行讨论 第五步 上述过程何时停止 分析用非基变量表示目标函数的表达式 如果让负检验数所对应的变量进基 目标函数值将下降 当用非基变量表示目标函数的表达式中 非基变量的系数 检验数 全部非正时 当前的基本可行解就是最优解 为什么 三 表格单纯形法 1 初始单纯形表的建立 1 表格结构 0 x38121000 x416400100 x51204001 Z023000 2 表格设计依据 将 Z看作不参与基变换的基变量 把目标函数表达式改写成方程的形式 和原有的m个约束方程组成一个具有n m 1个变量 m 1个方程的方程组 取出系数写成增广矩阵的形式 ZX1X2 XnXn 1Xn 2 Xn mb Z Xn 1 Xn m所对应的系数列向量构成一个基 用矩阵的初等行变换将该基变成单位阵 这时变成0 相应的增广矩阵变成如下形式 其中 j 1 2 n 3 检验数的两种计算方法 利用矩阵的行变换 把目标函数表达式中基变量前面的系数变为0 使用计算公式 增广矩阵的最后一行就是用非基变量表示目标函数的表达式 j 1 2 n 就是非基变量的检验数 2 例1的表格单纯形法计算过程 从最优表可知 该LP的最优解是X 4 2 0 0 4 T相应的目标函数最优值是Zmax 14 已解决的问题 1 为了使目标函数逐步变优 怎么转移 通过顶点的转移 即进基与出基达到目的 2 目标函数何时达到最优 判断标准是什么 检验数 1 若所有的检验数均 则停止计算 可找到最优解 2 若有 且的系数列向量 则该问题无界 停止计算 3 若在最终表中有非基变量的检验数为0 则该问题有无穷多最优解 一 单纯形法的矩阵描述1怎样进行矩阵描述写成分块矩阵 第三节线性规划问题的对偶问题 将分块形式代入矩阵形式标准型 得出两个基本表达式 1 由约束条件 可得用非基变量表示基变量的表达式 2 1 2 将式 2 1 代入目标函数的表达式 可得 用非基变量表示目标函数的表达式 3 借助一个恒等式推出用非基变量表示目标函数的另一个等价表达式 代入式 2 2 并令 2 4 2单纯形表格的矩阵形式 换个角度审视生产计划问题 例 要求制定一个生产计划方案 在劳动力和原材料可能供应的范围内 使得产品的总利润最大 3对偶原理 用于生产第i种产品的资源转让收益不小于生产该种产品时获得的利润 它的对偶问题就是一个价格系统 使在平衡了设备资源和原材料的直接成本后 所确定的价格系统最具有竞争力 对偶变量的经济意义可以解释为对工时及原材料的单位定价 若工厂自己不生产产品 将现有的设备及原材料转而接受外来加工时 那么上述的价格系统能保证不亏本又最富有竞争力 包工及原材料的总价格最低 当原问题和对偶问题都取得最优解时 这一对线性规划对应的目标函数值是相等的 Zmax Wmin 14 考察原问题和对偶问题的解 给作决策的管理者另一个自由度 怎样通过增加更多的资源来增加利润 怎样使用不同类型的资源来增加利润 饮食与营养问题例2 2采购甲 乙 丙 丁4种食品量分别为x1 x2 x3 x4 在保证人体所需维生素A B C前提下 使总的花费最小 构建的线性规划模型 换一个角度 生产营养药丸的制药公司力图使营养师相信 各种营养药丸勿须通过多种食品的转换就能供营养师调剂 制药公司面对的问题是为营养药丸确定单价 以获得最大的收益 同时与真正的食品竞争 于是 营养药丸的单位成本不能超过相应食品的市场平均价 由此得到下面的对偶问题 二 原问题和对偶问题的关系1 对称形式的对偶关系 1 若原问题是 这两个式子的变换关系称为 对称形式的对偶关系 2 其对偶问题为 2 对称形式的对偶关系的矩阵描述 D L 例2 3写出下面线性规划的对偶问题 1 原问题对偶问题 特点 对偶变量符号不限 系数阵转置 特点 等式约束 2 非对称形式的对偶关系 2 怎样写出非对称形式的对偶问题 把一个等式约束写成两个不等式约束 再根据对称形式的对偶关系定义写出 按照原始 对偶表直接写出 3 原始 对偶表 三 对