第四章 数学规划模型.pdf

z y x z yx 数 学 模 型数 学 模 型 数学与应用数学 第四章数学规划模型第四章数学规划模型 4 1 奶制品的生产与销售奶制品的生产与销售 4 2汽车生产与原油采购汽车生产与原油采购 4 3接力队选拔和选课策略接力队选拔和选课策略 4 4饮料厂的生产与检修饮料厂的生产与检修 4 5 钢管和易拉罐下料钢管和易拉罐下料 y 数学规划模型数学规划模型 实际问题中 的优化模型 实际问题中 的优化模型 mixgts xxxxfzMaxMin i T n 2 1 0 1 或 x 决策变量决策变量f x 目标函数目标函数 gi x 0 约束条件约束条件 多元函数 条件极值 多元函数 条件极值 决策变量个数决策变量个数n和和 约束条件个数约束条件个数m较大较大 最优解在可行域最优解在可行域 的边界上取得的边界上取得 数 学 规 划 数 学 规 划 线性规划线性规划 非线性规划非线性规划 整数规划整数规划 重点在模型的建立和结果的分析重点在模型的建立和结果的分析 企业生产计划企业生产计划 4 1 奶制品的生产与销售奶制品的生产与销售 空间层次空间层次 工厂级 根据外部需求和内部设备 人力 原料等 条件 以最大利润为目标制订产品生产计划 工厂级 根据外部需求和内部设备 人力 原料等 条件 以最大利润为目标制订产品生产计划 车间级 根据生产计划 工艺流程 资源约束及费 用参数等 以最小成本为目标制订生产批量计划 车间级 根据生产计划 工艺流程 资源约束及费 用参数等 以最小成本为目标制订生产批量计划 时间层次时间层次 若短时间内外部需求和内部资源等不随时间变化 可 制订 若短时间内外部需求和内部资源等不随时间变化 可 制订单阶段生产计划单阶段生产计划 否则应制订多阶段生产计划 否则应制订多阶段生产计划 本节课题本节课题 例例1 加工奶制品的生产计划加工奶制品的生产计划 1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元 公斤 获利16元 公斤 50桶牛奶桶牛奶时间时间480小时小时至多加工至多加工100公斤公斤A1 制订生产计划 使每天获利最大制订生产计划 使每天获利最大 35元可买到元可买到1桶牛奶 买吗 若买 每天最多买多少桶牛奶 买吗 若买 每天最多买多少 可聘用临时工人 付出的工资最多是每小时几元可聘用临时工人 付出的工资最多是每小时几元 A1的获利增加到的获利增加到 30元元 公斤 应否改变生产计划 公斤 应否改变生产计划 每天 每天 1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元 公斤 获利16元 公斤 x1桶牛奶生产桶牛奶生产A1x2桶牛奶生产桶牛奶生产A2 获利获利 24 3x1获利获利 16 4 x2 原料供应原料供应 50 21 xx 劳动时间劳动时间 480812 21 xx 加工能力加工能力 1003 1 x 决策变量决策变量 目标函数目标函数 21 6472xxzMax 每天获利每天获利 约束条件约束条件 非负约束非负约束 0 21 xx 线性 规划 模型 线性 规划 模型 LP 时间时间480小时小时50桶牛奶每天桶牛奶每天至多加工至多加工100公斤公斤A1 模型分析与假设模型分析与假设 比 例 性 比 例 性 可 加 性 可 加 性 连续性连续性 xi对目标函数的对目标函数的 贡 献 贡 献 与与xi取值成正比取值成正比 xi对约束条件的对约束条件的 贡 献 贡 献 与与xi取值成正比取值成正比 xi对目标函数的对目标函数的 贡 献 贡 献 与与xj取值无关取值无关 xi对约束条件的对约束条件的 贡 献 贡 献 与与xj取值无关取值无关 xi取值连续取值连续 A1 A2每公斤的获利是与各 自产量无关的常数 每公斤的获利是与各 自产量无关的常数 每桶牛奶加工出每桶牛奶加工出A1 A2的数量和 时间是与各自产量无关的常数 的数量和 时间是与各自产量无关的常数 A1 A2每公斤的获利是与相 互产量无关的常数 每公斤的获利是与相 互产量无关的常数 每桶牛奶加工出每桶牛奶加工出A1 A2的数量和 时间是与相互产量无关的常数 的数量和 时间是与相互产量无关的常数 加工加工A1 A2的牛奶桶数是实数的牛奶桶数是实数 线性规划模型线性规划模型 模型求解模型求解图解法图解法 x1 x2 0 A B C D l2 l3 l4 l5 50 21 xx 480812 21 xx 1003 1 x 0 21 xx 约 束 条 件 约 束 条 件 50 211 xxl 480812 212 xxl 1003 13 xl 0 0 2514 xlxl 21 6472xxzMax 目标 函数 目标 函数 Z 0 Z 2400 Z 3600 z c 常数常数 等值线等值线 c 在在B 20 30 点得到最优解点得到最优解 目标函数和约束条件是线性函数目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形可行域为直线段围成的凸多边形 目标函数的等值线为直线目标函数的等值线为直线 最优解一定在凸多边 形的某个顶点取得 最优解一定在凸多边 形的某个顶点取得 l1 模型求解模型求解软件实现软件实现 LINDO 6 1 max 72x1 64x2 st 2 x1 x2 50 3 12x1 8x2 480 4 3x1 100 end OBJECTIVE FUNCTION VALUE 1 3360 000 VARIABLE VALUEREDUCED COST X1 20 0000000 000000 X2 30 0000000 000000 ROW SLACK OR SURPLUS DUAL PRICES 2 0 000000 48 000000 3 0 000000 2 000000 4 40 000000 0 000000 NO ITERATIONS 2 DO RANGE SENSITIVITY ANALYSIS No 20桶牛奶生产桶牛奶生产A1 30桶生产桶生产A2 利润 利润3360元 元 结果解释结果解释 OBJECTIVE FUNCTION VALUE 1 3360 000 VARIABLE VALUE REDUCED COST X1 20 000000 0 000000 X2 30 000000 0 000000 ROWSLACK OR SURPLUSDUAL PRICES 2 0 00000048 000000 3 0 0000002 000000 4 40 0000000 000000 NO ITERATIONS 2 原料无剩余原料无剩余 时间无剩余时间无剩余 加工能力剩余加工能力剩余40 max 72x1 64x2 st 2 x1 x2 50 3 12x1 8x2 480 4 3x1 100 end 三 种 资 源 三 种 资 源 资源资源 剩余为零的约束为紧约束 有效约束 剩余为零的约束为紧约束 有效约束 结果解释结果解释 OBJECTIVE FUNCTION VALUE 1 3360 000 VARIABLE VALUE REDUCED COST X1 20 000000 0 000000 X2 30 000000 0 000000 ROW SLACK OR SURPLUS DUAL PRICES 2 0 000000 48 000000 3 0 000000 2 000000 4 40 000000 0 000000 NO ITERATIONS 2 最优解下最优解下 资源资源 增加增加1 单位时单位时 效益效益 的增量的增量 原料增加原料增加1单位单位 利润增长利润增长48 时间增加时间增加1单位单位 利润增长利润增长2 加工能力增长不影响利润加工能力增长不影响利润 影子价格影子价格 35元可买到元可买到1桶牛奶 要买吗 桶牛奶 要买吗 35 48 应该买 应该买 聘用临时工人付出的工资最多每小时几 元 聘用临时工人付出的工资最多每小时几 元 2元 元 RANGES IN WHICH THE BASIS IS UNCHANGED OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72 000000 24 000000 8 000000 X2 64 000000 8 000000 16 000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50 000000 10 000000 6 666667 3 480 000000 53 333332 80 000000 4 100 000000 INFINITY 40 000000 最优解不变时目标函 数系数允许变化范围 最优解不变时目标函 数系数允许变化范围 DO RANGE SENSITIVITY ANALYSIS Yes x1系数范围系数范围 64 96 x2系数范围系数范围 48 72 A1获利增加到获利增加到 30元元 千克 应否改变生产计划千克 应否改变生产计划 x1系数由系数由24 3 72 增加为增加为30 3 90 在允许范围内 在允许范围内 不变 不变 约束条件不变约束条件不变 结果解释结果解释 RANGES IN WHICH THE BASIS IS UNCHANGED OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72 000000 24 000000 8 000000 X2 64 000000 8 000000 16 000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50 000000 10 000000 6 666667 3 480 000000 53 333332 80 000000 4 100 000000 INFINITY 40 000000 影子价格有意义时约束右端的允许变化范围影子价格有意义时约束右端的允许变化范围 原料最多增加原料最多增加10 时间最多增加时间最多增加53 35元可买到元可买到1桶牛奶 每天最多买多桶牛奶 每天最多买多 少少 最多买最多买10桶桶 目标函数不变目标函数不变 例例2 奶制品的生产销售计划奶制品的生产销售计划在例在例1基础上深加工基础上深加工 1桶 牛奶 桶 牛奶 3千克千克A1 12小时小时 8小时小时 4公斤公斤A2 或 获利 或 获利24元元 公斤公斤 获利获利16元元 公斤公斤 0 8千克千克B1 2小时小时 3元元 1千克 获利 千克 获利44元元 千克千克 0 75千克千克B2 2小时小时 3元元 1千克 获利 千克 获利32元元 千克千克 制订生产计划 使每天净利润最大制订生产计划 使每天净利润最大 30元可增加元可增加1桶牛奶 桶牛奶 3元可增加元可增加1小时时间 应否投 资 现投资 小时时间 应否投 资 现投资150元 可赚回多少 元 可赚回多少 50桶牛奶桶牛奶 480小时小时 至多至多100公斤公斤A1 B1 B2的获利经常有的获利经常有10 的波动 对计划有无影响 的波动 对计划有无影响 1桶 牛奶 桶 牛奶 3千克千克 A1 12小时小时 8小时小时 4千克千克 A2 或 获利 或 获利24元元 千克千克 获利获利16元元 kg 0 8千克千克 B1 2小时小时 3元元 1千克千克 获利获利44元元 千克千克 0 75千克千克 B2 2小时小时 3元元 1千克千克 获利获利32元元 千克千克 出售出售x1 千克千克 A1 x2 千克千克 A2 X3千克千克 B1 x4千克千克 B2 原料 供应 原料 供应 劳动 时间 劳动 时间 加工能力加工能力 决策 变量 决策 变量 目标 函数 目标 函数 利润利润 约束 条件 约束 条件 非负约束非负约束0 61 xx 654321 3332441624xxxxxxzMax x5千克千克 A1加工加工B1 x6千克千克 A2加工加工B2 50 43 6251 xxxx 48022 2 4 65 6251 xx xxxx 100 51 xx 附加约束附加约束 53 80 x x 64 750 x x 模型求解模型求解 软件实现软件实现LINDO 6 1 50 43 2 6251 xxxx 48022 2 4 3 65 6251 xx xxxx OBJECTIVE FUNCTION VALUE 1 3460 800 VARIABLE VALUE REDUCED COST X1 0 000000 1 680000 X2 168 000000 0 000000 X3 19 200001 0 000000 X4 0 000000 0 000000 X5 24 000000 0 000000 X6 0 000000 1 520000 ROW SLACK OR SURPLUS DUAL PRICES 2 0 000000 3 160000 3 0 000000 3 260000 4 76 000000 0 000000 5 0 000000 44 000000 6 0 000000 32 000000 NO ITERATIONS 2 600334 2 6521 xxxx4 4804624 3 6521 xxxx DO RANGE SENSITIVITY ANALYSIS No OBJECTIVE FUNCTION VALUE 1 3460 800 VARIABLE VALUEREDUCED COST X1 0 0000001 680000 X2 168 0000000 000000 X3 19 2000010 000000 X4 0 0000000 000000 X5 24 0000000 000000 X6 0 0000001 520000 ROW SLACK OR SURPLUS DUAL PRICES 2 0 000000 3 160000 3 0 000000 3 260000 4 76 000000 0 000000 5 0 000000 44 000000 6 0 000000 32 000000 NO ITERATIONS 2 结果解释结果解释 每天销售每天销售168 千克千克A2 和和19 2 千克千克B1 利润 利润3460 8 元 元 8桶牛奶加工成桶牛奶加工成A1 42桶 牛奶加工成 桶 牛奶加工成A2 将得到的 将得到的24千克千克A1全部 加工成 全部 加工成B1 除加工能力外均 为紧约束 除加工能力外均 为紧约束 结果解释结果解释 OBJECTIVE FUNCTION VALUE 1 3460 800 VARIABLE VALUE REDUCED COST X1 0 000000 1 680000 X2 168 000000 0 000000 X3 19 200001 0 000000 X4 0 000000 0 000000 X5 24 000000 0 000000 X6 0 000000 1 520000 ROW SLACK OR SURPLUS DUAL PRICES 2 0 000000 3 160000 3 0 000000 3 260000 4 76 000000 0 000000 5 0 000000 44 000000 6 0 000000 32 000000 增加增加1桶牛奶使利润增 长 桶牛奶使利润增 长3 16 12 37 92 50 43 2 6251 xxxx 600334 2 6521 xxxx4 增加增加1小时时间使利 润增长 小时时间使利 润增长3 26 30元可增加元可增加1桶牛奶 桶牛奶 3元可增加元可增加1小时时间 应否投资 现投资 小时时间 应否投资 现投资150元 可赚回多少 元 可赚回多少 投资投资150元增加元增加5桶牛奶 可赚回 桶牛奶 可赚回189 6元 大于 增加时间的利润增长 元 大于 增加时间的利润增长 结果解释结果解释B1 B2的获利有的获利有10 的波动 对计划有无影响的波动 对计划有无影响 RANGES IN WHICH THE BASIS IS UNCHANGED OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24 000000 1 680000 INFINITY X2 16 000000 8 150000 2 100000 X3 44 000000 19 750002 3 166667 X4 32 000000 2 026667 INFINITY X5 3 000000 15 800000 2 533334 X6 3 000000 1 520000 INFINITY DO RANGE SENSITIVITY ANALYSIS Yes B1获利下降获利下降10 超 出 超 出X3 系数允许范围系数允许范围 B2获利上升获利上升10 超 出 超 出X4 系数允许范围系数允许范围 波动对计划有影响波动对计划有影响 生产计划应重新制订 如将生产计划应重新制订 如将x3的系数改为的系数改为39 6 计算 会发现结果有很大变化 计算 会发现结果有很大变化 如果生产某一类型汽车 则至少要生产如果生产某一类型汽车 则至少要生产8080辆 那么 最优的生产计划应作何改变 辆 那么 最优的生产计划应作何改变 例例4 2 1 汽车厂生产计划汽车厂生产计划 汽车厂生产三种类型的汽车 已知各类型每辆车对钢 材 劳动时间的需求 利润及工厂每月的现有量 汽车厂生产三种类型的汽车 已知各类型每辆车对钢 材 劳动时间的需求 利润及工厂每月的现有量 小型中型大型现有量 钢材 吨 小型中型大型现有量 钢材 吨 1 5 3 5 600 劳动时间 小时 劳动时间 小时 280 250 400 60000 利润 万元 利润 万元 2 3 4 制订月生产计划 使工厂的利润最大 制订月生产计划 使工厂的利润最大 4 2汽车生产与原油采购汽车生产与原油采购 设每月生产小 中 大型 汽车的数量分别为 设每月生产小 中 大型 汽车的数量分别为x1 x2 x3 321 432xxxzMax 600535 1 321 xxxts 60000400250280 321 xxx 0 321 xxx 汽车厂生产计划汽车厂生产计划 模型建立模型建立 线性线性 规划规划 模型模型 LP 小型中型大型现有量 钢材 小型中型大型现有量 钢材1 5 3 5 600 时间时间280 250 400 60000 利润利润2 3 4 模型 求解 模型 求解 3 模型中增加条件 模型中增加条件 x1 x2 x3 均为整数 重新求解 均为整数 重新求解 OBJECTIVE FUNCTION VALUE 1 632 2581 VARIABLE VALUE REDUCED COST X1 64 5161290 000000 X2 167 7419280 000000 X3 0 000000 0 946237 ROW SLACK OR SURPLUS DUAL PRICES 2 0 000000 0 731183 3 0 000000 0 003226 结果为小数 怎么办 结果为小数 怎么办 1 舍去小数 取 舍去小数 取x1 64 x2 167 算出目标函数值 算出目标函数值z 629 与 与 LP最优值最优值632 2581相差不大 相差不大 2 试探 如取 试探 如取x1 65 x2 167 x1 64 x2 168等 计算函数 值 等 计算函数 值z 通过比较可能得到更优的解 通过比较可能得到更优的解 但必须检验它们是否满足约束条件 为什么 但必须检验它们是否满足约束条件 为什么 IP可用可用LINDO直接求解直接求解 整数规划 整数规划 Integer Programming 简记 简记IP gin 3 表示表示 前前3个变量为 整数 个变量为 整数 等价于 等价于 gin x1 gin x2 gin x3 IP 的最优解的最优解x1 64 x2 168 x3 0 最优值 最优值z 632 max 2x1 3x2 4x3 st 1 5x1 3x2 5x3 600 280 x1 250 x2 400 x3 60000 end gin 3 OBJECTIVE FUNCTION VALUE 1 632 0000 VARIABLE VALUE REDUCED COST X1 64 000000 2 000000 X2 168 000000 3 000000 X3 0 000000 4 000000 321 432xxxzMax 600535 1 321 xxxts 60000400250280 321 xxx 为非负整数 321 xxx 模型求解模型求解 IP 结果输出结果输出 其中其中3个子模型应去掉 然后 逐一求解 比较目标函数值 再加上整数约束 得最优解 个子模型应去掉 然后 逐一求解 比较目标函数值 再加上整数约束 得最优解 方法方法1 分解为 分解为8个个LP子模型子模型 汽车厂生产计划汽车厂生产计划 若生产某类汽车 则至少生产80辆 求生产计划 若生产某类汽车 则至少生产80辆 求生产计划 321 432xxxzMax 600535 1 321 xxxts 60000400250280 321 xxx x1 x2 x3 0 或 或 80 x1 80 x2 150 x3 0 最优值 最优值z 610 80 0 0 321 xxx 0 80 0 321 xxx 80 80 0 321 xxx 0 0 80 321 xxx 0 80 80 321 xxx 80 0 80 321 xxx 80 80 80 321 xxx 0 321 xxx LINDO中对中对0 1变量的限定 变量的限定 int y1 int y2 int y3 方法方法2 引入 引入0 1变量 化为整数规划变量 化为整数规划 M为大的正 数 可取 为大的正 数 可取1000 OBJECTIVE FUNCTION VALUE 1 610 0000 VARIABLE VALUE REDUCED COST X1 80 000000 2 000000 X2 150 000000 3 000000 X3 0 000000 4 000000 Y1 1 000000 0 000000 Y2 1 000000 0 000000 Y3 0 000000 0 000000 若生产某类汽车 则至少生产80辆 求生产计划 若生产某类汽车 则至少生产80辆 求生产计划 x1 0 或 80 x2 0 或 80 x3 0 或 80 1 0 80 11111 yyxMyx 1 0 80 22222 yyxMyx 1 0 80 33333 yyxMyx 最优解 同前 最优解 同前 NLP虽然可用现成的数学软件求解 如虽然可用现成的数学软件求解 如LINGO MATLAB 但是其结果常依赖于初值的选择 但是其结果常依赖于初值的选择 方法方法3 化为非线性规划 化为非线性规划 非线性规划 非线性规划 Non Linear Programming 简记 简记NLP 实践表明 本例仅当初值非常接近上面方法算出 的最优解时 才能得到正确的结果 实践表明 本例仅当初值非常接近上面方法算出 的最优解时 才能得到正确的结果 若生产某类汽车 则至少生产80辆 求生产计划 若生产某类汽车 则至少生产80辆 求生产计划 x1 0 或 80 x2 0 或 80 x3 0 或 80 0 80 11 xx 0 80 22 xx 0 80 33 xx 应如何安排原油的采购和加工 应如何安排原油的采购和加工 例例4 3 2 原油采购与加工原油采购与加工 市场上可买到不超过市场上可买到不超过1500吨的原油吨的原油A 购买量不超过购买量不超过500吨时的单价为吨时的单价为10000元 吨 元 吨 购买量超过购买量超过500吨但不超过吨但不超过1000吨时 超过吨时 超过500吨的 部分 吨的 部分8000元 吨 元 吨 购买量超过购买量超过1000吨时 超过吨时 超过1000吨的部分吨的部分6000元 吨 元 吨 售价售价4800元元 吨吨 售价售价5600元元 吨吨 库存库存500吨吨 库存库存1000吨吨 汽油甲汽油甲 A 50 原油原油A 原油原油B 汽油乙汽油乙 A 60 决策 变量 决策 变量 目标 函数 目标 函数 问题 分析 问题 分析 利润 销售汽油的收入 购买原油利润 销售汽油的收入 购买原油A的支出的支出 难点 原油难点 原油A的购价与购买量的关系较复杂的购价与购买量的关系较复杂 6 5 8 4 22122111 xcxxxxzMax 甲甲 A 50 A B 乙乙 A 60 购买购买x x11 x12 x21 x22 4 8千元千元 吨吨 5 6千元千元 吨吨 原油原油A的购买量 原油的购买量 原油A B生产汽油甲生产汽油甲 乙的数量乙的数量 c x 购买原油购买原油A的支出的支出 利润利润 千元千元 c x 如何表述 如何表述 原油供应原油供应 约束 条件 约束 条件 xxx 500 1211 1000 2221 xx 1500 x 500 1 1000 30006 1000 500 1000 8 500 0 10 xx xx xx xc x 500吨单价为吨单价为10千元 吨 千元 吨 500吨 吨 x 1000吨 超过吨 超过500吨的吨的8千元 吨 千元 吨 1000吨 吨 x 1500吨 超过吨 超过1000吨的吨的6千元 吨 千元 吨 目标 函数 目标 函数 购买购买x A B x11 x12 x21 x22 库存库存500吨 库存 吨 库存1000吨吨 目标函数中目标函数中c x 不是线性函数 是非线性规划 不是线性函数 是非线性规划 对于用分段函数定义的对于用分段函数定义的c x 一般的非线性规划软 件也难以输入和求解 一般的非线性规划软 件也难以输入和求解 想办法将模型化简 用现成的软件求解 想办法将模型化简 用现成的软件求解 汽油含原油汽油含原油A 的比例限制的比例限制 5 0 2111 11 xx x 6 0 2212 12 xx x 2111 xx 2212 32xx 约束 条件 约束 条件 甲甲 A 50 A B 乙乙 A 60 x11 x12 x21 x22 x1 x2 x3 以价格以价格10 8 6 千元 吨 采购千元 吨 采购A的吨数的吨数 目标 函数 只有当以 目标 函数 只有当以10千元千元 吨的价格购买吨的价格购买x1 500 吨 时 才能以 吨 时 才能以8 千元千元 吨的价格购买吨的价格购买x2 方法方法1 6810 6 5 8 4 32122122111 xxxxxxxzMax 0 500 32 xx500 0 321 xxx 非线性规划模型 可以用非线性规划模型 可以用LINGO求解求解 模型求解模型求解 x x1 x2 x3 c x 10 x1 8x2 6x3 500吨 吨 x 1000吨 超过吨 超过500吨的吨的8千元 吨千元 吨 增加约束增加约束 0 500 21 xx x x1 x2 x3 c x 10 x1 8x2 6x3 方法方法1 LINGO求解求解Model Max 4 8 x11 4 8 x21 5 6 x12 5 6 x22 10 x1 8 x2 6 x3 x11 x12 x 500 x21 x22 0 2 x12 3 x22 0 x x1 x2 x3 x1 500 x2 0 x2 500 x3 0 x1 500 x2 500 x3 0 x11 0 x12 0 x21 0 x22 0 x1 0 x2 0 x3 0 end Objective value 4800 000 Variable Value Reduced Cost X11 500 00000 0000000E 00 X21 500 00000 0000000E 00 X12 0 0000000E 00 0 0000000E 00 X22 0 0000000E 00 0 0000000E 00 X1 0 1021405E 13 10 00000 X2 0 0000000E 00 8 000000 X3 0 0000000E 00 6 000000 X 0 0000000E 00 0 0000000E 00 LINGO得到的是局部最优解 还 能得到更好的解吗 得到的是局部最优解 还 能得到更好的解吗 用库存的用库存的500吨原油吨原油A 500吨原油吨原油B 生产汽油甲 不购买新的原油生产汽油甲 不购买新的原油A 利润为 利润为4 800千元 千元 y1 y2 y3 1 以价格以价格10 8 6 千元 吨 采购千元 吨 采购A 增 加 约 束 增 加 约 束 方法方法2 0 1线性规划模型 可 用 线性规划模型 可 用LINDO求解求解 112 500500yxy 223 500500yxy 33 500yx y1 y2 y3 0或或1 OBJECTIVE FUNCTION VALUE 1 5000 000 VARIABLE VALUE REDUCED COST Y1 1 000000 0 000000 Y2 1 000000 2200 000000 Y3 1 000000 1200 000000 X11 0 000000 0 800000 X21 0 000000 0 800000 X12 1500 000000 0 000000 X22 1000 000000 0 000000 X1 500 0000000 000000 X2 500 0000000 000000 X3 0 000000 0 400000 X 1000 0000000 000000 购买购买1000吨原油吨原油A 与 库存的 与 库存的500吨原油吨原油A和和 1000吨原油吨原油B一起 生 产汽油乙 利润为 一起 生 产汽油乙 利润为5 000 千元 千元 x1 x2 x3 以价格以价格10 8 6 千元 吨 采购千元 吨 采购A的吨数的吨数 y 0 x 0 x 0 y 1 优于方法优于方法1的结果的结果 b1 b2b3b4 方法方法3 b1 x b2 x z1b1 z2b2 z1 z2 1 z1 z2 0 c x z1c b1 z2c b2 c x x 12000 9000 5000 050010001500 b2 x b3 x z2b2 z3b3 z2 z3 1 z2 z3 0 c x z2c b2 z3c b3 b3 x b4 x z3b3 z4b4 z3 z4 1 z3 z4 0 c x z3c b3 z4c b4 500 1 1000 30006 1000 500 1000 8 500 0 10 xx xx xx xc 直接处理分段线性函数直接处理分段线性函数c x IP模型 模型 LINDO求 解 得到的结果与 方法 求 解 得到的结果与 方法2相同 相同 处理分段线性函数 方法处理分段线性函数 方法3更具一般性更具一般性 44332211 bzbzbzbzx 44332211 bczbczbczbczxc bk x bk 1 yk 1 否则 否则 yk 0 3432321211 yzyyzyyzyz 4 3 2 1 0 1 4321 kzzzzz k 10 1 321321 或 yyyyyy 方法方法3 bk x bk 1 x zkbk z k 1 bk 1 zk zk 1 1 zk zk 1 0 c x zkc bk zk 1 c bk 1 c x x 12000 9000 5000 050010001500 b1 b2b3b4 对于对于k 1 2 3 分派问题分派问题 4 3 接力队选拔和选课策略接力队选拔和选课策略 若干项任务分给一些候选人来完成 每人的专长不同 完成每项任务取得的效益或需要的资源就不同 如何分 派任务使获得的总效益最大 或付出的总资源最少 若干项任务分给一些候选人来完成 每人的专长不同 完成每项任务取得的效益或需要的资源就不同 如何分 派任务使获得的总效益最大 或付出的总资源最少 若干种策略供选择 不同的策略得到的收益或付出的 成本不同 各个策略之间有相互制约关系 如何在满 足一定条件下作出决择 使得收益最大或成本最小 若干种策略供选择 不同的策略得到的收益或付出的 成本不同 各个策略之间有相互制约关系 如何在满 足一定条件下作出决择 使得收益最大或成本最小 丁的蛙泳成绩退步到丁的蛙泳成绩退步到1 15 2 戊的自由泳成绩进 步到 戊的自由泳成绩进 步到57 5 组成接力队的方案是否应该调整 组成接力队的方案是否应该调整 如何选拔队员组成4 100米混合泳接力队 如何选拔队员组成4 100米混合泳接力队 例例4 3 1 混合泳接力队的选拔混合泳接力队的选拔 甲甲乙乙丙丙丁丁戊戊 蝶泳蝶泳1 06 857 21 18 1 10 1 07 4 仰泳仰泳1 15 61 06 1 07 81 14 21 11 蛙泳蛙泳1 27 1 06 41 24 61 09 61 23 8 自由泳自由泳58 653 59 457 21 02 4 5名候选人的百米成绩名候选人的百米成绩 穷举法 组成接力队的方案共有穷举法 组成接力队的方案共有5 120种 种 目标 函数 目标 函数 若选择队员若选择队员i参加泳姿参加泳姿j 的比赛 记的比赛 记xij 1 否则记 否则记xij 0 0 1规划模型规划模型 cij 秒 秒 队员队员i 第第j 种泳姿的百米成绩种泳姿的百米成绩 约束 条件 约束 条件 每人最多入选泳姿之一每人最多入选泳姿之一 ciji 1i 2i 3i 4i 5 j 166 857 2787067 4 j 275 66667 874 271 j 38766 484 669 683 8 j 458 65359 457 262 4 4 1 5 1ji ijij xcZMin 每种泳姿有且只有1人每种泳姿有且只有1人 5 1 1 4 1 ix j ij 4 1 1 5 1 jx i ij 模型求解模型求解 最优解 最优解 x14 x21 x32 x43 1 其它变量为其它变量为0 成绩为成绩为253 2 秒 秒 4 13 2 MIN 66 8x11 75 6x12 87x13 58 6x14 67 4x51 71 x52 83 8x53 62 4x54 SUBJECT TO x11 x12 x13 x14 1 x41 x42 x43 x44 1 x11 x21 x31 x41 x51 1 x14 x24 x34 x44 x54 1 END INT 20 输入输入LINDO求解求解 甲甲乙乙丙丙丁丁戊戊 蝶泳蝶泳1 06 857 21 18 1 10 1 07 4 仰泳仰泳1 15 61 06 1 07 81 14 21 11 蛙泳蛙泳1 27 1 06 41 24 61 09 61 23 8 自由泳自由泳58 653 59 457 21 02 4 甲甲 自由泳 乙自由泳 乙 蝶泳 丙 蝶泳 丙 仰泳 丁仰泳 丁 蛙泳 蛙泳 丁蛙泳丁蛙泳c43 69 6 75 2 戊自由泳 戊自由泳c54 62 4 57 5 方案是否调整 敏感性分析 方案是否调整 敏感性分析 乙乙 蝶泳 丙蝶泳 丙 仰泳 丁仰泳 丁 蛙泳 戊蛙泳 戊 自由泳自由泳 IP规划一般没有与规划一般没有与LP规划相类似的理论 规划相类似的理论 LINDO 输出的敏感性分析结果通常是没有意义的 输出的敏感性分析结果通常是没有意义的 最优解 最优解 x21 x32 x43 x51 1 成绩为成绩为4 17 7 c43 c54的新数据重新输入模型 用的新数据重新输入模型 用LINDO求解求解 指派 指派 Assignment 问题 问题 每项任务有且只有一人承担 每人只能承担一项 效益不同 怎样分派使总效益最大 每项任务有且只有一人承担 每人只能承担一项 效益不同 怎样分派使总效益最大 讨论讨论 甲甲 自由泳 乙自由泳 乙 蝶泳 丙 蝶泳 丙 仰泳 丁仰泳 丁 蛙泳 蛙泳 原 方 案 原 方 案 为了选修课程门数最少 应学习哪些课程 为了选修课程门数最少 应学习哪些课程 例例4 3 2 选课策略选课策略 要求至少选两门数学课 三门运筹学课和两门计算机课要求至少选两门数学课 三门运筹学课和两门计算机课 课号课号课名课名学分学分所属类别所属类别先修课要求先修课要求 1微积分微积分5数学数学 2线性代数线性代数4数学数学 3最优化方法最优化方法4数学 运筹学数学 运筹学微积分 线性代数微积分 线性代数 4数据结构数据结构3数学 计算机数学 计算机计算机编程计算机编程 5应用统计应用统计4数学 运筹学数学 运筹学微积分 线性代数微积分 线性代数 6计算机模拟计算机模拟3计算机 运筹学计算机 运筹学计算机编程计算机编程 7计算机编程计算机编程2计算机计算机 8预测理论预测理论2运筹学运筹学应用统计应用统计 9数学实验数学实验3运筹学 计算机运筹学 计算机微积分 线性代数微积分 线性代数 选修课程最少 且学分尽量多 应学习哪些课程 选修课程最少 且学分尽量多 应学习哪些课程 0 1规划模型规划模型 决策变量决策变量 目标函数目标函数 xi 1 选修课号选修课号i 的 课程 的 课程 xi 0 不选 不选 9 1 i i M inZx 选修课程总数最少选修课程总数最少 约束条件约束条件 最少最少2门数学课 门数学课 3门运筹学课 门运筹学课 2门计算机课 门计算机课 2 54321 xxxxx 3 98653 xxxxx 2 9764 xxxx 课号课号课名课名所属类别所属类别 1微积分微积分数学数学 2线性代数线性代数数学数学 3最优化方法最优化方法数学 运筹学数学 运筹学 4数据结构数据结构数学 计算机数学 计算机 5应用统计应用统计数学 运筹学数学 运筹学 6计算机模拟计算机模拟计算机 运筹学计算机 运筹学 7计算机编程计算机编程计算机计算机 8预测理论预测理论运筹学运筹学 9数学实验数学实验运筹学 计算机运筹学 计算机 先修课程要求先修课程要求 74 xx 02 215 xxx 0 76 xx 0 58 xx 02 219 xxx 最优解 最优解 x1 x2 x3 x6 x7 x9 1 其它为其它为0 6门课程 总学分门课程 总学分21 02 213 xxx 0 1规划模型规划模型 约束条件约束条件 x3 1必有必有x1 x2 1 2313 xxxx 0 74 xx 模型求解 模型求解 LINDO 课号课号课名课名先修课要求先修课要求 1 微积分微积分 2 线性代数线性代数 3 最优化方法最优化方法微积分 线性代数微积分 线性代数 4 数据结构数据结构计算机编程计算机编程 5 应用统计应用统计微积分 线性代数微积分 线性代数 6 计算机模拟计算机模拟计算机编程计算机编程 7 计算机编程计算机编程 8 预测理论预测理论应用统计应用统计 9 数学实验数学实验微积分 线性代数微积分 线性代数 学分最多学分最多 多目标优化的处理方法 化成单目标优化 多目标优化的处理方法 化成单目标优化 两目标 多目标 规划两目标 多目标 规划 9876 54321 3223 43445 xxxx xxxxxWMax WZMin 讨论 选修课程最少 学分尽量多 应学习哪些课程 讨论 选修课程最少 学分尽量多 应学习哪些课程 9 1i i xZMin 课程最少课程最少 以学分最多为目标 不 管课程多少 以学分最多为目标 不 管课程多少 以课程最少为目标 不 管学分多少 以课程最少为目标 不 管学分多少 最优解如上 最优解如上 6门课 程 总学分 门课 程 总学分21 最优解显然是选修所 有 最优解显然是选修所 有9门课程 门课程 多目标规划多目标规划 在课程最少的前提下 以学分最多为目标 在课程最少的前提下 以学分最多为目标 最优解 最优解 x1 x2 x3 x5 x7 x9 1 其它为其它为0 总 学分由 总 学分由21增至增至22 注意 最优解不唯一 注意 最优解不唯一 课号课号课名课名学分学分 1微积分微积分5 2线性代数线性代数4 3最优化方法最优化方法4 4数据结构数据结构3 5应用统计应用统计4 6计算机模拟计算机模拟3 7计算机编程计算机编程2 8预测理论预测理论2 9数学实验数学实验3 LINDO无法告诉优化 问题的解是否唯一 无法告诉优化 问题的解是否唯一 可将可将x9 1 易为易为x6 1 增加约束 以学分最多为目标求解 增加约束 以学分最多为目标求解 6 9 1 i i x 多目标规划多目标规划 对学分数和课程数加权形成一个目标 如三七开 对学分数和课程数加权形成一个目标 如三七开 9876 54321 3223 43445 xxxx xxxxxW 9 1i i xZ 最优解 最优解 x1 x2 x3 x4 x5 x6 x7 x9 1 其它为其它为0 总学分 总学分28 课号课号课名课名学分学分 1微积分微积分5 2线性代数线性代数4 3最优化方法最优化方法4 4数据结构数据结构3 5应用统计应用统计4 6计算机模拟计算机模拟3 7计算机编程计算机编程2 8预测理论预测理论2 9数学实验数学实验3 WZWZYMin3 07 0 21 讨论与思考讨论与思考 WZYMin 21 3 2 1 多目标规划多目标规划 9876 54321 3223 43445 xxxx xxxxxW 9 1i i xZ 最优解与最优解与 1 1 2 0的结果相同的结果相同 课程最少课程最少 4 4饮料厂的生产与检修饮料厂的生产与检修 单阶段生产计划单阶段生产计划 多阶段生产计划多阶段生产计划 生产批量问题生产批量问题 企业生产计划 外部需求和内部 资源随时间变化 企业生产计划 外部需求和内部 资源随时间变化 考虑与产量无关的固定费用考虑与产量无关的固定费用 给优化模型求解带来新的困难给优化模型求解带来新的困难 安排生产计划安排生产计划 满足每周的需求满足每周的需求 使使4周总费用最小 周总费用最小 存贮费 每周每千箱饮料存贮费 每周每千箱饮料 0 2千元 千元 例4 4 1 饮料厂的生产与检修计划例4 4 1 饮料厂的生产与检修计划 在在4周内安排一次设备检修 占用当周周内安排一次设备检修 占用当周15千箱生产能 力 能使检修后每周增产 千箱生产能 力 能使检修后每周增产5千箱 检修应排在哪一周 千箱 检修应排在哪一周 周次周次需求量需求量 千箱千箱 生产能力生产能力 千箱千箱 成本成本 千元千元 千箱千箱 115305 0 225405 1 335455 4 425205 5 合计合计100135 某种饮料某种饮料4周的需求量 生产能力和成本周的需求量 生产能力和成本 问题分析问题分析 除第除第4周外每周的生产 能力超过每周的需求 周外