线性规划模型ppt课件.ppt

1 第1节线性规划问题与模型 一 线性规划模型从招聘总经理谈起 2 泰山工厂生产状况 泰山工厂可以生产两种产品出售 需要三种资源 已知各产品的利润 各资源的限量和各产品的资源消耗系数如下表 目前生产现状 不生产产品A 生产产品B每天30 获利3600 3 招聘总经理 约翰 我应聘 在现有资源状况下 我可以使利润达到4280 方案是 生产A产品20 生产B产品24可行性 9 20 4 24 276 3604 20 5 24 2003 20 10 24 300 4 怎么达到的 约翰使用了运筹学中的线性规划模型问题 如何安排生产计划 使得获利最多 步骤 1 确定决策变量 设生产A产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 设备约束9X1 4X2 360人力约束4X1 5X2 200原材料约束3X1 10X2 300非负性约束X1 0X2 0 5 线性规划图解法 由数学知识可知 y ax b是一条直线 同理 Z 70 x1 120 x2 x2 70 120 x1 Z 120也是一条直线 以Z为参数的一族等值线 9x1 4x2 360 x1 360 9 4 9x2是直线x1 360 9 4 9x2下方的半平面 所有半平面的交集称之为可行域 可行域内的任意一点 就是满足所有约束条件的解 称之为可行解 6 例1图示 9080604020 020406080100 x1 x2 9x1 4x2 360 4x1 5x2 200 3x1 10 x2 300 A B C D E F G H I Z 70 x1 120 x2 7 最优解 X1 20 x2 24对应的生产方案 生产A产品20生产B产品24获利 70 20 120 24 4280 8 约翰就任泰山工厂总经理 9 二 线性规划图解法 例2 某工厂在计划期内要安排 两种产品的生产 已知生产单位产品所需的设备台时及A B两种原材料的消耗 资源的限制 如下表 问题 工厂应分别生产多少单位 产品才能使工厂获利最多 线性规划模型 目标函数 Maxz 50 x1 100 x2约束条件 s t x1 x2 3002x1 x2 400 x2 250 x1 x2 0 10 例1 目标函数 Maxz 50 x1 100 x2约束条件 s t x1 x2 300 A 2x1 x2 400 B x2 250 C x1 0 D x2 0 E 得到最优解 x1 50 x2 250最优目标值z 27500 图解法 对于只有两个决策变量的线性规划问题 可以在平面直角坐标系上作图表示线性规划问题的有关概念 并求解 下面通过例1详细讲解其方法 11 线性规划图解法 续 1 分别取决策变量X1 X2为坐标向量建立直角坐标系 在直角坐标系里 图上任意一点的坐标代表了决策变量的一组值 例1的每个约束条件都代表一个半平面 12 线性规划图解法 续 2 对每个不等式 约束条件 先取其等式在坐标系中作直线 然后确定不等式所决定的半平面 13 线性规划图解法 续 3 把五个图合并成一个图 取各约束条件的公共部分 如图2 1所示 14 线性规划图解法 续 4 目标函数z 50 x1 100 x2 当z取某一固定值时得到一条直线 直线上的每一点都具有相同的目标函数值 称之为 等值线 平行移动等值线 当移动到B点时 z在可行域内实现了最大化 A B C D E是可行域的顶点 对有限个约束条件则其可行域的顶点也是有限的 15 线性规划图解法 续 重要结论 如果线性规划有最优解 则一定有一个可行域的顶点对应一个最优解 无穷多个最优解 若将例1中的目标函数变为maxz 50 x1 50 x2 则线段BC上的所有点都代表了最优解 无界解 即可行域的范围延伸到无穷远 目标函数值可以无穷大或无穷小 一般来说 这说明模型有错 忽略了一些必要的约束条件 无可行解 若在例1的数学模型中再增加一个约束条件4x1 3x2 1200 则可行域为空域 不存在满足约束条件的解 当然也就不存在最优解了 16 线性规划图解法 续 例2某公司由于生产需要 共需要A B两种原料至少350吨 A B两种材料有一定替代性 其中A原料至少购进125吨 但由于A B两种原料的规格不同 各自所需的加工时间也是不同的 加工每吨A原料需要2个小时 加工每吨B原料需要1小时 而公司总共有600个加工小时 又知道每吨A原料的价格为2万元 每吨B原料的价格为3万元 试问在满足生产需要的前提下 在公司加工能力的范围内 如何购买A B两种原料 使得购进成本最低 17 线性规划图解法 续 解 目标函数 Minf 2x1 3x2约束条件 s t x1 x2 350 x1 1252x1 x2 600 x1 x2 0采用图解法 如下图 得Q点坐标 250 100 为最优解 18 三 线性规划一般形式 企业管理的重点内容之一就是在各种生产因素和产品的调配问题上 一方面 在一固定阶段 企业管理者所能 投入 的生产因素 原料 人力 设备时间是由一定限量的 在一固定期间 任何一工厂的厂房 工场 机器 一切固定资本是不会变动的 再雄厚的资本 也还是有它的限度 再从流动资本来看 原料的来源和存量 各种技工的人数和时间 在一相当的短期中也是有一定的限度 19 线性规划一般形式 另一方面 企业管理者 投入 生产因素时 一定有一完整的目标 在商言商 企业管理者的目标当然是求最高的利润和最低的成本 如何将受时间 空间 数量限制的 投入 生产因素调配 得当 达到最佳的境界而获得最佳的 产出 量 因而获得最大的收益 以上就是企业管理者须面对的一个问题的两个方面 企业管理者不仅要知道如何调配手头上有限的生产因素 同时要从不同的调配中 找出最佳的调配 来达到他的企业经营目标 最低成本 最高利润 20 线性规划一般形式 事实上 用最低的代价去追求最高的收获 原是一种理性的要求 因此在任何理性活动中 都有一求 最佳 问题的存在 21 例题3 配方问题 养海狸鼠饲料中营养要求 VA每天至少700克 VB每天至少30克 VC每天刚好200克 现有五种饲料 搭配使用 饲料成分如下表 22 例题3建模 设抓取饲料Ix1kg 饲料IIx2kg 饲料IIIx3kg 目标函数 最省钱minZ 2x1 7x2 4x3 9x4 5x5约束条件 3x2 2x2 x3 6x4 18x5 700营养要求 x1 0 5x2 0 2x3 2x4 0 5x5 300 5x1 x2 0 2x3 2x4 0 8x5 200用量要求 x1 50 x2 60 x3 50 x4 70 x5 40非负性要求 x1 0 x2 0 x3 0 x4 0 x5 0 23 例题4 人员安排问题 医院护士24小时值班 每次值班8小时 不同时段需要的护士人数不等 据统计 24 例题4建模 目标函数 minZ x1 x2 x3 x4 x5 x6约束条件 x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30非负性约束 xj 0 j 1 2 6 25 归纳 线性规划的一般模式 目标函数 max min Z c1x1 c2x2 c3x3 cnxn约束条件 a11x1 a12x2 a13x3 a1nxn b1a21x1 a22x2 a23x3 a2nxn b2 am1x1 am2x2 am3x3 amnxn bn非负性约束 x1 0 x2 0 xn 0 26 四 线性规划的标准型 一般形式目标函数 Max Min z c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0标准形式目标函数 Maxz c1x1 c2x2 cnxn约束条件 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 bi 0 27 线性规划的标准型 可以看出 线性规划的标准形式有如下四个特点 目标最大化 约束为等式 决策变量均非负 右端项非负 对于各种非标准形式的线性规划问题 我们总可以通过以下变换 将其转化为标准形式 28 线性规划的标准型 1 极小化目标函数的问题 设目标函数为Minf c1x1 c2x2 cnxn 可以 令z f 则该极小化问题与下面的极大化问题有相同的最优解 即Maxz c1x1 c2x2 cnxn但必须注意 尽管以上两个问题的最优解相同 但它们最优解的目标函数值却相差一个符号 即Minf Maxz 29 线性规划的标准型 2 约束条件不是等式的问题 设约束条件为ai1x1 ai2x2 ainxn bi可以引进一个新的变量s 使它等于约束右边与左边之差s bi ai1x1 ai2x2 ainxn 显然 s也具有非负约束 即s 0 这时新的约束条件成为ai1x1 ai2x2 ainxn s bi 30 线性规划的标准型 当约束条件为ai1x1 ai2x2 ainxn bi时 类似地令s ai1x1 ai2x2 ainxn bi显然 s也具有非负约束 即s 0 这时新的约束条件成为ai1x1 ai2x2 ainxn s bi 31 线性规划的标准型 为了使约束由不等式成为等式而引进的变量s 当不等式为 小于等于 时称为 松弛变量 当不等式为 大于等于 时称为 剩余变量 如果原问题中有若干个非等式约束 则将其转化为标准形式时 必须对各个约束引进不同的松弛变量 3 右端项有负值的问题 在标准形式中 要求右端项必须每一个分量非负 当某一个右端项系数为负时 如bi 0 则把该等式约束两端同时乘以 1 得到 ai1x1 ai2x2 ainxn bi 32 线性规划的标准型 例 将以下线性规划问题转化为标准形式Minf 2x1 3x2 4x3s t 3x1 4x2 5x3 62x1 x3 8x1 x2 x3 9x1 x2 x3 0解 首先 将目标函数转换成极大化 令z f 2x1 3x2 4x3其次考虑约束 有2个不等式约束 引进松弛变量x4 x5 0 第三个约束条件的右端值为负 在等式两边同时乘 1 33 线性规划的标准型 通过以上变换 可以得到以下标准形式的线性规划问题 Maxz 2x1 3x2 4x3s t 3x1 4x2 5x3 x4 62x1 x3 x5 8 x1 x2 x3 9x1 x2 x3 x4 x5 0 变量无符号限制的问题 在标准形式中 必须每一个变量均有非负约束 当某一个变量xj没有非负约束时 可以令xj xj xj 其中xj 0 xj 0即用两个非负变量之差来表示一个无符号限制的变量 当然xj的符号取决于xj 和xj 的大小 34 五 计算机求解算法 单纯形算法基本思想 从可行域中的一个基本可行解出发 判断它是否已是最优解 若不是 寻找下一个基本可行解 并使目标函数得到改进 如此迭代下去 直到找出最优解或判定问题无界为止 从另一个角度说 就是从可行域的某一个极点出发 迭代到另一个极点 并使目标函数的值有所改善 直到找出有无最优解时为止 35 求解线型规划的算法单纯形算法且听下回分解 36 37 第三章运筹学优化模型 大连海事大学刘巍 38 第2节线性规划求解 单纯性算法求解线性规划的最常用算法 39 单纯形算法 基本思想 从可行域中的一个基本可行解出发 判断它是否已是最优解 若不是 寻找下一个基本可行解 并使目标函数得到改进 如此迭代下去 直到找出最优解或判定问题无界为止 从另一个角度说 就是从可行域的某一个极点出发 迭代到另一个极点 并使目标函数的值有所改善 直到找出有无最优解时为止 40 单纯形法 引例 41 解 1 确定初始可行解 B P3P4P5 I 令X1 X2 0 X 1 0 0 30 60 24 TZ 1 0 42 2 判定解是否最优 Z 0 40X1 50X2当X1从0 或X2从0 Z从0 X 1 不是最优解 43 3 由一个基可行解 另一个基可行解 50 40选X2从0 X1 0 X2 min 30 2 60 2 24 2 12X2进基变量 X5出基变量 44 B2 P3P4P2 45 1 2 代入 式 令X1 X5 0X 2 0 12 6 36 0 TZ 2 600 46 2 判断 40 0 X 2 不是 3 选X1从0 X5 0 X1 min 6 1 36 3 1 6X1进基 X3出基 47 B3 P1P4P2 令X3 X5 0X 3 6 12 0 18 0 TZ 3 840 48 2 15 0 X 3 不是 3 选X5从0 X3 0 X5 min 18 2 12 1 2 9X5进基 X4出基 49 B4 P1P5P2 令X3 X4 0X 4 15 15 2 0 0 9 TZ 4 975 50 0 0 0 X2 X1 51 两个重要公式 52 当LP的数学模型为一般型时 两个重要公式形如 53 B P1P2 Pm I 54 当Xj 0 j m 1 n 时 55 1 5 2单纯形法原理 56 此时 B P1P2 Pm 对应的基本可行解为 57 定理1 对解X 1 若检验数 j j m 1 n 全部 0 则X 1 为最优解 定理2 对X 1 若有某个非基变量Xm k m k 0且相应的Pm k a1m k amm k T 0 则原问题无有限最优解 58 定理2证明 X 2 b1 a1m k bm amm k 0 0 T AX 2 bX 2 0 Z Z0 m k 当 时Z 59 初始基B1 P3P4 X 1 0 0 10 15 TZ 1 0 60 选中X1从0 X2 0 求X1 X1 Z 61 换基迭代公式 1 决定换入变量 2 决定换出变量 bi aim kXm k 0 i 1 2 m 62 则Xr为换出变量 63 定理3 经单纯形法得到的 64 若否 因为P1 Pm线性无关 65 X 2 是基本解 且是可行解 66 单纯形法基本步骤 1 定初始基 初始基本可行解 3 若有 k 0 Pk全 0 停 没有有限最优解 否则转 4 2 对应于非基变量检验数 j全 0 若是 停 得到最优解 若否 转 3 67 定Xr为换出变量 arm k为主元 由最小 比值法求 68 转 2 5 以arm k为中心 换基迭代 69 证明可用归纳法 略 X在边界上 X在内部 0 1 70 证明 设X 1 X k 为可行域顶点 若X 不是顶点 但maxZ CX X 定理2 可行域有界 最优值必可在顶点得到 iX i i 1 0 i 1 CX iCX i iCX m CX m 设CX m Max CX i 1 i k 71 Z 2 Z 1 Cm k Zm k m k 0 72 1 5 3单纯形表 73 74 本问题的最优解X 15 15 2 0 0 9 TZ 975 75 几点说明 1 例maxZ X1 2X2 76 77 78 X 1 2 3 Z 1 8 X 2 4 2 Z 2 8 无穷多解 79 80 81 判定定理1 基本可行解X 当全部 j 0时 X为最优解 判定定理2 对可行基B 当某 k 0 且Pk a1k amk T 0 则原问题无有限最优解 82 83 84 退化解 X 0 3 2 0 1 2 0 T Zmax 18 85 P1P2P3 P4P2P3 P4P5P3 P6P5P3 P6P7P3 P1P7P3 P1P2P3 86 4 例 87 88 89 本问题无界 90 1 5 4初始基本可行解的求法 一 大M法 判定无解条件 当进行到最优表时 仍有人工变量在基中 且 0 则说明原问题无可行解 91 例1 92 93 94 95 96 97 解题过程 98 两阶段法原理 1 辅助问题的基本可行解X 0 为最优解 对应最小值 0则X 0 的前n个分量是原问题的基本可行解 99 证明 100 2 原问题有可行解时 辅助问题最优值 0 101 maxZ X1 2X2 X1 X2 2 X1 X2 1X2 3X1X2 0 例2 102 第 1 阶段 103 104 105 例3 106 第 1 阶段 107 108 109 第1阶段最优基B min 1 0 110 1 arj全 0 式多余方程 2 arj有 0元 设为ars 0 以ars为主元 换基迭代 最后得到 111 例4 求 112 一 二 113 CBXB000005 205 40X21011 4 2 31 20 1 21y200000 3 21 1 40X12101 20101 6 第一阶段 三 40 30X1X2X3X4CBXB 800 100X21011 4 2 3 4X42101 20 第二阶段 114 的特殊情况 第1阶段结束时 有人工变量在基中取0 但Xi系数全为0 此方程为多余方程 115 例5 求 116 一 二 117 118 40 30X1X2X3X4CBXB 800000X21010 2 3 3X300010 4X121000 第二阶段 的特殊情况 可将人工变量换出 119 单纯形法小结 1 标准型中有单位基 120 建模有问题 5 退化解问题 121 122 第三章运筹学优化模型 大连海事大学刘巍 123 第3节对偶线性规划与影子价格 一 对偶问题再谈招聘总经理 124 泰山工厂生产状况 泰山工厂可以生产两种产品出售 需要三种资源 已知各产品的利润 各资源的限量和各产品的资源消耗系数如下表 目前生产现状 不生产产品A 生产产品B每天30 获利3600 125 招聘总经理 约翰 我应聘 在现有资源状况下 我可以使利润达到4280 方案是 生产A产品20 生产B产品24可行性 9 20 4 24 276 3604 20 5 24 2003 20 10 24 300 126 怎么达到的 约翰使用了运筹学中的线性规划模型问题 如何安排生产计划 使得获利最多 步骤 1 确定决策变量 设生产A产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 设备约束9X1 4X2 360人力约束4X1 5X2 200原材料约束3X1 10X2 300非负性约束X1 0X2 0 127 例1图示 9080604020 020406080100 x1 x2 9x1 4x2 360 4x1 5x2 200 3x1 10 x2 300 A B C D E F G H I Z 70 x1 120 x2 128 X1 20 x2 24对应的生产方案 生产A产品20生产B产品24获利 70 20 120 24 4280 129 问题的最优解 最优解如下 目标函数最优值为 4280变量最优解相差值 x1200 x2240约束松弛 剩余变量对偶价格 18402013 6305 2目标函数系数范围 变量下限当前值上限 x1367096x287 5120233 333常数项数范围 约束下限当前值上限 1276360无上限2150200226 9233227 586300400 130 再谈招聘总经理 约翰作为总经理将泰山工厂经营的很好了 汤姆来竞争了 竞争口号 不裁员 不减薪 不加班 提高利润5 131 可能吗 目前约翰的经营已经是资源的最佳利用了 汤姆还有什么绝招增加利润呢 132 这个问题涉及到 1 线性规划的对偶问题 2 影子价格概念 133 原来问题的最优解 最优解如下 目标函数最优值为 4280变量最优解相差值 x1200 x2240约束松弛 剩余变量对偶价格 18402013 6305 2目标函数系数范围 变量下限当前值上限 x1367096x287 5120233 333常数项数范围 约束下限当前值上限 1276360无上限2150200226 9233227 586300400 134 对偶性是线性规划问题的最重要的内容之一 每一个线性规划 LP 必然有与之相伴而生的另一个线性规划问题 即任何一个求maxZ的LP都有一个求minZ的LP 其中的一个问题叫 原问题 记为 P 另一个称为 对偶问题 记为 D 例 资源的合理利用问题已知资料如表所示 问应如何安排生产计划使得既能充分利用现有资源有使总利润最大 对偶问题的提出 135 下面从另一个角度来讨论这个问题 假定 该厂的决策者不是考虑自己生产甲 乙两种产品 而是将厂里的现有资源用于接受外来加工任务 只收取加工费 试问该决策者应制定怎样的收费标准 合理的 136 分析问题 1 每种资源收回的费用不能低于自己生产时的可获利润 2 定价又不能太高 要使对方能够接受 137 一般而言 W越大越好 但因需双方满意 故 为最好 该问题的数学模型为 138 模型对比 139 对称形式 互为对偶 LP Maxz cTx DP Minf bTys t Ax bs t ATy cx 0y 0 Max Min 一般形式 若一个问题的某约束为等式 那么对应的对偶问题的相应变量无非负限制 反之 若一个问题的某变量无非负限制 那么对应的对偶问题的相应约束为等式 对偶定义 140 对偶问题 令y1 y1 y1 141 解 142 3 原问题第k个约束为等式 对偶问题第k个变量是自由变量 原问题第k个变量是自由变量 则对偶问题第k个约束为等式约束 143 对偶关系对应表 144 例2 写对偶规划 minZ 4X1 2X2 3X3 X1 2X2 62X1 3X3 9X1 5X2 2X3 4X2 X3 0 145 maxW 6y1 9y2 4y3 y1 2y2 y3 42y1 5y3 23y2 2y3 3y1 0 y2 0 y3自由 146 minZ 4X1 2X2 3X3 X1 2X2 62X1 3X3 9X1 5X2 2X3 4X2 X3 0 或将原问题变形为 147 maxW 6y1 9y2 4y3 y1 2y2 y3 4 2y1 5y3 23y2 2y3 3y1 y2 0 y3自由 对偶规划 148 产品A B产量X1 X2 Z为利润 例1 149 X 8 24 TZ 184 150 151 y 2 9 13 9 Z 184 152 观察结论 一对对偶问题都有最优解 且目标函数值相等 最优表中有两个问题的最优解 153 1 7 2对偶问题解的性质 154 定理1 弱对偶定理 155 推论2 P 有可行解 但无有限最优解 则 D 无可行解 推论1 P D 都有可行解 则必都有最优解 156 157 158 159 定理4 松紧定理 互补松弛性 原问题 160 对偶问题 161 162 163 164 165 例 min 5y1 y2 166 P 最优解 0 9 0 4 64 9 167 168 169 解 D 为 170 将y1 y2 代入 知 为严格不等式 x2 x3 x4 0 x 1 0 0 0 1 TZ 5 171 小结 原问题与对偶问题的关系 互为对偶最优解的存在性相同 目标函数值相等 解互为影子价格 172 影子价格在管理决策中的作用 173 原来问题的最优解 最优解如下 目标函数最优值为 4280变量最优解相差值 x1200 x2240约束松弛 剩余变量对偶价格 18402013 6305 2目标函数系数范围 变量下限当前值上限 x1367096x287 5120233 333常数项数范围 约束下限当前值上限 1276360无上限2150200226 9233227 586300400 174 4 影子价格可以告诉决策者 用多大的代价增加资源才是合算的 如 第二种资源增加1单位能使收益增加13 6 如果增加这种资源的代价大于13 6就不划算了 3 影子价格可以告诉决策者 增加哪一种资源对增加经济效益最有利 如 本例中三种资源的价格为0 13 6 5 2 说明首先应增加第二种资源 因为相比之下 它能使收益增加得更多 175 5 影子价格可以告诉决策者应如何考虑新产品的价格 如 企业要生产一种新产品时 如果每件新产品耗用的这三种资源数量是1 2 3单位 则新产品的定价一定要大于才能增加公司的收益 如售价低于42 8的话 生产是不划算的 176 汤姆的决策 设备资源的影子价格为0 不需要添加 人力资源的影子价格为13 6 而在市场上人力资源的价格是5 因此 招聘人力26人 原材料的影子价格为5 2 可是市场上这种材料价格是5 9 买入不上算 不增加 177 新的线型规划模型 1 确定决策变量 设生产A产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 设备约束9X1 4X2 360人力约束4X1 5X2 226原材料约束3X1 10X2 300非负性约束X1 0X2 0 178 最优解如下 目标函数最优值为 4633 6变量最优解相差值 x130 40 x220 880约束松弛 剩余变量对偶价格 12 8802013 6305 2目标函数系数范围 变量下限当前值上限 x1367096x287 5120233 333常数项数范围 约束下限当前值上限 1357 12360无上限2150226226 9233297 517300452 179 新的生产计划 生产A产品30 4生产B产品20 88获利4633 6相比约翰的经营增加纯利润353 6 130 223 提高5 2 180 热烈祝贺汤姆竞聘泰山工厂总经理成功 181 问题 可不可以再进一步增加人力资源 从而能否用这种方式使利润进一步提高 182 将人力资源增加到250人 1 确定决策变量 设生产A产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 设备约束9X1 4X2 360人力约束4X1 5X2 250原材料约束3X1 10X2 300非负性约束X1 0X2 0 183 计算结果 最优解如下 目标函数最优值为 4646 11变量最优解相差值 x130 7690 x220 7690约束松弛 剩余变量对偶价格 104 359223 07703010 256目标函数系数范围 变量下限当前值上限 x13670270 x231 111120233 333常数项数范围 约束下限当前值上限 11203604322226 923250无上限3120300362 069 184 效益分析 利润4646 11增加4646 11 5 50 4391 11相比人力资源为226时的利润4391 11 4633 6 142 49 185 注意 将人力资源增加到227人时 1 确定决策变量 设生产A产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 设备约束9X1 4X2 360人力约束4X1 5X2 227原材料约束3X1 10X2 300非负性约束X1 0X2 0 186 人力资源为227时最优解 最优解如下 目标函数最优值为 4646 11变量最优解相差值 x130 7690 x220 7690约束松弛 剩余变量对偶价格 104 3592 07703010 256目标函数系数范围 变量下限当前值上限 x13670270 x231 111120233 333常数项数范围 约束下限当前值上限 1120360360 242226 923227无上限3120300300 207 187 原来是这样啊 此时人力资源的影子价格为0 再增加也不会带来新的利润 188 新的问题 灵敏度分析且听下回分解 189 190 第三章运筹学优化模型 大连海事大学刘巍 191 第3节对偶线性规划与影子价格 续 灵敏度分析汤姆总经理的失误 192 泰山工厂生产状况 泰山工厂可以生产两种产品出售 需要三种资源 已知各产品的利润 各资源的限量和各产品的资源消耗系数如下表 目前生产现状 不生产产品A 生产产品B每天30 获利3600 193 招聘总经理 约翰 我应聘 在现有资源状况下 我可以使利润达到4280 方案是 生产A产品20 生产B产品24可行性 9 20 4 24 276 3604 20 5 24 2003 20 10 24 300 194 怎么达到的 约翰使用了运筹学中的线性规划模型问题 如何安排生产计划 使得获利最多 步骤 1 确定决策变量 设生产A产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 设备约束9X1 4X2 360人力约束4X1 5X2 200原材料约束3X1 10X2 300非负性约束X1 0X2 0 195 最优解 X1 20 x2 24对应的生产方案 生产A产品20生产B产品24获利 70 20 120 24 4280 196 再谈招聘总经理 约翰作为总经理将泰山工厂经营的很好了 汤姆来竞争了 竞争口号 不裁员 不减薪 不加班 提高利润5 197 原来问题的最优解 最优解如下 目标函数最优值为 4280变量最优解相差值 x1200 x2240约束松弛 剩余变量对偶价格 18402013 6305 2目标函数系数范围 变量下限当前值上限 x1367096x287 5120233 333常数项数范围 约束下限当前值上限 1276360无上限2150200226 9233227 586300400 198 汤姆的决策 设备资源的影子价格为0 不需要添加 人力资源的影子价格为13 6 而在市场上人力资源的价格是5 因此 招聘人力26人 原材料的影子价格为5 2 可是市场上这种材料价格是5 9 买入不上算 不增加 199 新的线型规划模型 1 确定决策变量 设生产A产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 设备约束9X1 4X2 360人力约束4X1 5X2 226原材料约束3X1 10X2 300非负性约束X1 0X2 0 200 最优解如下 目标函数最优值为 4633 6变量最优解相差值 x130 40 x220 880约束松弛 剩余变量对偶价格 12 8802013 6305 2目标函数系数范围 变量下限当前值上限 x1367096x287 5120233 333常数项数范围 约束下限当前值上限 1357 12360无上限2150226226 9233297 517300452 201 新的生产计划 生产A产品30 4生产B产品20 88获利4633 6相比约翰的经营增加纯利润353 6 130 223 提高5 2 202 热烈祝贺汤姆竞聘泰山工厂总经理成功 203 汤姆总经理的失误 在成绩面前和赞誉声中汤姆总经理头脑有些发热 汤姆决定 再进一步增加人力资源 将人力资源达到250人 204 将人力资源增加到250人 1 确定决策变量 设生产A产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 设备约束9X1 4X2 360人力约束4X1 5X2 250原材料约束3X1 10X2 300非负性约束X1 0X2 0 205 计算结果 最优解如下 目标函数最优值为 4646 11变量最优解相差值 x130 7690 x220 7690约束松弛 剩余变量对偶价格 104 359223 07703010 256目标函数系数范围 变量下限当前值上限 x13670270 x231 111120233 333常数项数范围 约束下限当前值上限 11203604322226 923250无上限3120300362 069 206 效益分析 利润4646 11增加4646 11 5 50 4391 11相比人力资源为226时的利润4391 11 4633 6 142 49 207 注意 将人力资源增加到227人时 1 确定决策变量 设生产A产品x1kg B产品x2kg2 确定目标函数 maxZ 70X1 120X23 确定约束条件 设备约束9X1 4X2 360人力约束4X1 5X2 227原材料约束3X1 10X2 300非负性约束X1 0X2 0 208 人力资源为227时最优解 最优解如下 目标函数最优值为 4646 11变量最优解相差值 x130 7690 x220 7690约束松弛 剩余变量对偶价格 104 3592 07703010 256目标函数系数范围 变量下限当前值上限 x13670270 x231 111120233 333常数项数范围 约束下限当前值上限 1120360360 242226 923227无上限3120300300 207 209 原来是这样啊 此时人力资源的影子价格为0 再增加也不会带来新的利润 210 新的问题 灵敏度分析 211 戴维来竞争了 戴维 男 25岁 大连海事大学管理科学与工程硕士研究生毕业 在校学习期间认真刻苦 善于思考 从不缺课 注 约翰 汤姆都是戴维的同班同学 但是约翰在学习 运筹与优化模型 课时因故缺课 没听到影子价格一节内容 而汤姆虽然听了影子价格一节内容 但是也因故在讲 灵敏度分析 一节内容时缺课了 212 2 3灵敏度分析进一步理解最优单纯形表中各元素的含义考虑问题Maxz c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0引入m个松弛变量后 通过计算得到最优单纯形表 应 1 1能够找到最优基B的逆矩阵B 以及BN 检验数等 灵敏度分析 213 灵敏度分析 续 在生产计划问题的一般形式中 A代表企业的技术状况 b代表企业的资源状况 而C代表企业产品的市场状况 在这些因素不变的情况下企业的最优生产计划和最大利润由线性规划的最优解和最优值决定 在实际生产过程中 上述三类因素均是在不断变化的 如果按照初始的状况制订了最佳的生产计划 而在计划实施前或实施中上述状况发生了改变 则决策者所关心的是目前所执行的计划还是不是最优 如果不是应该如何修订原来的最优计划 更进一步 为了防止在各类状况发生时 来不及随时对其变化作出反应 即所谓 计划不如变化快 企业应当预先了解 当各项因素变化时 应当作出什么样的反应 214 灵敏度分析 续 当系数A b C发生改变时 目前最优基是否还最优 为保持目前最优基还是最优 系数A b C的允许变化范围是什么 假设每次只有一种系数变化 目标系数C变化基变量系数发生变化 非基变量系数发生变化 右端常数b变化 增加一个变量 增加一个约束 技术系数A发生变化 215 灵敏度分析 续 若B是最优基 则最优表形式如下 216 灵敏度分析 续 最优单纯形表 B 1 BT 1cB I O 217 价值系数C发生变化 m考虑检验数 j cj criarijj 1 2 ni 11 若ck是非基变量的系数 设ck变化为ck ck k ck ck criarik k ck只要 k 0 即 ck k 则最优解不变 否则 将最优单纯形表中的检验数 k用 k 取代 继续单纯形法的表格计算 例 MaxZ 2x1 3x2 4x3S t x1 2x2 x3 x4 3 2x1 x2 3x3 x5 4x1 x2 x3 x4 x5 0 灵敏度分析 续 218 例 最优单纯形表从表中看到 3 C3 C3 C2 a13 C1 a23 可得到 C3 9 5时 原最优解不变 灵敏度分析 续 219 2 若cs是基变量的系数 设cs变化为cs cs 那么 j cj criarij cs cs asj j csasj 对所有非基变量i s只要对所有非基变量 j 0 即 j csasj 则最优解不变 否则 将最优单纯形表中的检验数 j用 j 取代 继续单纯形法的表格计算 Max j asj asj 0 cs Min j asj asj 0 例 MaxZ 2x1 3x2 0 x3 0 x4 0 x5S t x1 2x2 x3 84x1 x4 164x2 x5 12x1 x2 x3 x4 x5 0 灵敏度分析 续 220 例 下表为最优单纯形表 考虑基变量系数c2发生变化从表中看到 j Cj C1 a1j C5 a5j C2 C2 a2j j 3 4可得到 3 C2 1时 原最优解不变 灵敏度分析 续 221 右端项b发生变化设分量br变化为br br 根据第1章的讨论 最优解的基变量xB B 1b 那么只要保持B 1 b b 0 则最优基不变 即基变量保持 只有值的变化 否则 需要利用对偶单纯形法继续计算 对于问题 LP Maxz cTxs t Ax bx 0最优单纯形表中含有B 1 aij i 1 m j n 1 n m那么 新的xi B 1b i brairi 1 m 由此可得 最优基不变的条件是Max bi air air 0 br Min bi air air 0 灵敏度分析 续 222 例 上例最优单纯形表如下 00 250 这里B 1 20 51 各列分别对应b1 b2 b3的单一 0 5 0 1250 变化 因此 设b1增加4 则x1 x5 x2分别变为 4 0 4 4 4 2 4 4 0 2 0 5 4 4用对偶单纯形法进一步求解 可得 x 4 3 2 0 0 Tf 17 灵敏度分析 续 223 增加一个变量增加变量xn 1则有相应的pn 1 cn 1 那么 计算出B 1pn 1 n 1 cn 1 criarin 1填入最优单纯形表 若 n 1 0则最优解不变 否则 进一步用单纯形法求解 例 前例增加x6 p6 2 6 3 T c6 5 计算得到 灵敏度分析 续 用单纯形法进一步求解 可得 x 1 1 5 0 0 0 2 Tf 16 5 224 增加一个约束增加约束一个之后 应把最优解带入新的约束 若满足则最优解不变 否则填入最优单纯形表作为新的一行 引入1个新的非负变量 原约束若是小于等于形式可引入非负松弛变量 否则引入非负人工变量 并通过矩阵行变换把对应基变量的元素变为0 进一步用单纯形法或对偶单纯形法求解 例 前例增加3x1 2x2 15 原最优解不满足这个约束 于是 灵敏度分析 续 225 A中元素发生变化 只讨论N中某一列变化情况 与增加变量xn 1的情况类似 假设pj变化 那么 重新计算出B 1pj j cj criarij填入最优单纯形表 若 j 0则最优解不变 否则 进一步用单纯形法求解 灵敏度分析 续 可得最优解 x 3 2 0 8 0 0 2 4 Tf 15 2 226 灵敏度分析 续 灵敏度分析小结 1Ci发生变化2Bj发生变化3增加一个变量4增加一个约束5A中元素发生变化 返回目录 227 228 第三章运筹学优化模型 大连海事大学刘巍 229 第4节线性规划应用 学以致用 培养学生 用数学的意识是本节的重要目的学习线性规划的有关知识其最终目的就是运用它们去解决一些生产 生活中问题 230 线性规划的应用 1人力资源分配的问题2生产计划的问题3套裁下料问题4配料问题5投资问题 231 人力资源分配的问题 例1 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下 设司机和乘务人员分别在各时间段一开始时上班 并连续工作八小时 问该公交线路怎样安排司机和乘务人员 既能满足工作需要 又配备最少司机和乘务人员 232 人力资源分配的问题 解 设xi表示第i班次时开始上班的司机和乘务人员数 这样我们建立如下的数学模型 目标函数 Minx1 x2 x3 x4 x5 x6约束条件 s t x1 x6 60 x1 x2 70 x2 x3 60 x3 x4 50 x4 x5 20 x5 x6 30 x1 x2 x3 x4 x5 x6 0 233 人力资源分配的问题 例2 一家中型的百货商场 它对售货员的需求经过统计分析如下表所示 为了保证售货人员充分休息 售货人员每周工作5天 休息两天 并要求休息的两天是连续的 问应该如何安排售货人员的作息 既满足工作需要 又使配备的售货人员的人数最少 234 人力资源分配的问题 解 设xi i 1 2 7 表示星期一至日开始休息的人数 这样我们建立如下的数学模型 目标函数 Minx1 x2 x3 x4 x5 x6 x7约束条件 s t x1 x2 x3 x4 x5 28x2 x3 x4 x5 x6 15x3 x4 x5 x6 x7 24x4 x5 x6 x7 x1 25x5 x6 x7 x1 x2 19x6 x7 x1 x2 x3 31x7 x1 x2 x3 x4 28x1 x2 x3 x4 x5 x6 x7 0 235 2生产计划的问题 例3 某公司面临一个是外包协作还是自行生产的问题 该公司生产甲 乙 丙三种产品 都需要经过铸造 机加工和装配三个车间 甲 乙两种产品的铸件可以外包协作 亦可以自行生产 但产品丙必须本厂铸造才能保证质量 数据如表 问 公司为了获得最大利润 甲 乙 丙三种产品各生产多少件 甲 乙两种产品的铸造中 由本公司铸造和由外包协作各应多少件 236 生产计划的问题 解 设x1 x2 x3分别为三道工序都由本公司加工的甲 乙 丙三种产品的件数 x4 x5分别为由外协铸造再由本公司加工和装配的甲 乙两种产品的件数 求xi的利润 利润 售价 各成本之和产品甲全部自制的利润 23 3 2 3 15产品甲铸造外协 其余自制的利润 23 5 2 3 13产品乙全部自制的利润 18 5 1 2 10产品乙铸造外协 其余自制的利润 18 6 1 2 9产品丙的利润 16 4 3 2 7可得到xi i 1 2 3 4 5 的利润分别为15 10 7 13 9元 237 生产计划的问题 通过以上分析 可建立如下的数学模型 目标函数 Max15x1 10 x2 7x3 13x4 9x5约束条件 5x1 10 x2 7x3 80006x1 4x2 8x3 6x4 4x5 120003x1 2x2 2x3 3x4 2x5 10000 x1 x2 x3 x4 x5 0 238 生产计划的问题 例4 永久机械厂生产 三种产品 均要经过A B两道工序加工 设有两种规格的设备A1 A2能完成A工序 有三种规格的设备B1 B2 B3能完成B工序 可在A B的任何规格的设备上加工 可在任意规格的A设备上加工 但对B工序 只能在B1设备上加工 只能在A2与B2设备上加工 数据如表 问 为使该厂获得最大利润 应如何制定产品加工方案 239 生产计划的问题 解 设xijk表示第i种产品 在第j种工序上的第k种设备上加工的数量 建立如下的数学模型 s t 5x111 10 x211 6000 设备A1 7x112 9x212 12x312 10000 设备A2 6x121 8x221 4000 设备B1 4x122 11x322 7000 设备B2 7x123 4000 设备B3 x111 x112 x121 x122 x123 0 产品在A B工序加工的数量相等 x211 x212 x221 0 产品在A B工序加工的数量相等 x312 x322 0 产品在A B工序加工的数量相等 xijk 0 i 1 2 3 j 1 2 k 1 2 3 240 生产计划的问题 目标函数为计算利润最大化 利润的计算公式为 利润 销售单价 原料单价 产品件数 之和 每台时的设备费用 设备实际使用的总台时数 之和 这样得到目标函数 Max 1 25 0 25 x111 x112 2 0 35 x221 2 80 0 5 x312 300 6000 5x111 10 x211 321 10000 7x112 9x212 1