数学模型与决策-新.pdf

1 Data Models 若若若若s 100 则最优决则最优决则最优决则最优决 策为策为策为策为X 0 即不生产该产品即不生产该产品即不生产该产品即不生产该产品 注意注意注意注意 在实际问题中在实际问题中在实际问题中在实际问题中 假如还需要考虑生产条件约束或资源假如还需要考虑生产条件约束或资源假如还需要考虑生产条件约束或资源假如还需要考虑生产条件约束或资源 约束约束约束约束 以上模型还需要进一步修正以上模型还需要进一步修正以上模型还需要进一步修正以上模型还需要进一步修正 此外此外此外此外 边际收益或单位边际收益或单位边际收益或单位边际收益或单位 生产成本随着产量生产成本随着产量生产成本随着产量生产成本随着产量X的不同还可能变化等等的不同还可能变化等等的不同还可能变化等等的不同还可能变化等等 需要进一步需要进一步需要进一步需要进一步 完善数学模型直到检验合格为止完善数学模型直到检验合格为止完善数学模型直到检验合格为止完善数学模型直到检验合格为止 线性规划线性规划线性规划线性规划 Linear Programming LP 是是是是 数学规划的一个分支数学规划的一个分支数学规划的一个分支数学规划的一个分支 数学规划着重解决资源的优数学规划着重解决资源的优数学规划着重解决资源的优数学规划着重解决资源的优 化配置化配置化配置化配置 一般可以表达成以下两个问题中的一个一般可以表达成以下两个问题中的一个一般可以表达成以下两个问题中的一个一般可以表达成以下两个问题中的一个 1 当资源给定时当资源给定时当资源给定时当资源给定时 要求完成的任务最多要求完成的任务最多要求完成的任务最多要求完成的任务最多 2 当任务给定时当任务给定时当任务给定时当任务给定时 要求为完成任务所消耗的资源要求为完成任务所消耗的资源要求为完成任务所消耗的资源要求为完成任务所消耗的资源 最少最少最少最少 若上述问题的目标若上述问题的目标若上述问题的目标若上述问题的目标 约束都能表达成变量的线性约束都能表达成变量的线性约束都能表达成变量的线性约束都能表达成变量的线性 关系关系关系关系 则这类优化问题称则这类优化问题称则这类优化问题称则这类优化问题称LP问题问题问题问题 LP是一种解决在线性约束条件下追求最大或最是一种解决在线性约束条件下追求最大或最是一种解决在线性约束条件下追求最大或最是一种解决在线性约束条件下追求最大或最 小的线性目标函数的方法小的线性目标函数的方法小的线性目标函数的方法小的线性目标函数的方法 本章内容重点 线性规划模型与解的主要概念 线性规划的单纯形法 线性规划 多解分析 线性规划应用 建模与求解软 件 例例例例1 红星机械厂开发出两个产品红星机械厂开发出两个产品红星机械厂开发出两个产品红星机械厂开发出两个产品 产品甲与产品乙产品甲与产品乙产品甲与产品乙产品甲与产品乙 已知产品甲需要原料已知产品甲需要原料已知产品甲需要原料已知产品甲需要原料A 产品乙需要用原料产品乙需要用原料产品乙需要用原料产品乙需要用原料B 由于两种产品都在一个设备上生产由于两种产品都在一个设备上生产由于两种产品都在一个设备上生产由于两种产品都在一个设备上生产 且设备工时有限且设备工时有限且设备工时有限且设备工时有限 须合理安排两种产品的产量须合理安排两种产品的产量须合理安排两种产品的产量须合理安排两种产品的产量 使得在资源有限的条件下获得利润最大使得在资源有限的条件下获得利润最大使得在资源有限的条件下获得利润最大使得在资源有限的条件下获得利润最大 设设设设x1为产品甲的产量为产品甲的产量为产品甲的产量为产品甲的产量 x2为为为为 产品乙的产量产品乙的产量产品乙的产量产品乙的产量 这是一个典型的利润最大化的生产计划问这是一个典型的利润最大化的生产计划问这是一个典型的利润最大化的生产计划问这是一个典型的利润最大化的生产计划问 题题题题 其中其中其中其中 MaxMaxMaxMax 是英文单词是英文单词是英文单词是英文单词 MaximizeMaximizeMaximizeMaximize 的缩写的缩写的缩写的缩写 含义为含义为含义为含义为 最大化最大化最大化最大化 s t s t s t s t 是是是是 subject tosubject tosubject tosubject to 的缩的缩的缩的缩 写写写写 表示表示表示表示 满足于满足于满足于满足于 因此因此因此因此 上述模型的含义是上述模型的含义是上述模型的含义是上述模型的含义是 在给定条件限制下在给定条件限制下在给定条件限制下在给定条件限制下 求使目标函数求使目标函数求使目标函数求使目标函数 z 达到最达到最达到最达到最 大的大的大的大的x1 x2的取值的取值的取值的取值 例例例例2 2 2 2 劳动力分配问题劳动力分配问题劳动力分配问题劳动力分配问题 设设设设xi为产品为产品为产品为产品i i i i的生产数量的生产数量的生产数量的生产数量 i 1 2 3 i 1 2 3 i 1 2 3 i 1 2 3 美克制造公司生产三种产品美克制造公司生产三种产品美克制造公司生产三种产品美克制造公司生产三种产品 每单每单每单每单 位产品的利润分别为位产品的利润分别为位产品的利润分别为位产品的利润分别为100元元元元 90元和元和元和元和 95元元元元 两个产品都要经过两个产品都要经过两个产品都要经过两个产品都要经过4个车间加个车间加个车间加个车间加 工工工工 假定每个车间的工人总工时是假定每个车间的工人总工时是假定每个车间的工人总工时是假定每个车间的工人总工时是 给定的给定的给定的给定的 每单位产品在各车间需要每单位产品在各车间需要每单位产品在各车间需要每单位产品在各车间需要 的工时如表所示的工时如表所示的工时如表所示的工时如表所示 Max 123 1009095ZXXX s t 123 123 123 123 0 81 22800 0 30 40 41800 0 91 20 63900 0 80 40 62800 XXX XXX XXX XXX 123 0XXX 11 例例例例3 配料问题配料问题配料问题配料问题 新农饲料公司希望用玉米和红薯两新农饲料公司希望用玉米和红薯两新农饲料公司希望用玉米和红薯两新农饲料公司希望用玉米和红薯两 种原料配制一种混合饲料种原料配制一种混合饲料种原料配制一种混合饲料种原料配制一种混合饲料 由于由于由于由于玉玉玉玉 米和红薯米和红薯米和红薯米和红薯 包含的营养成份和采购成包含的营养成份和采购成包含的营养成份和采购成包含的营养成份和采购成 本都不相同本都不相同本都不相同本都不相同 公司希望能够确定混公司希望能够确定混公司希望能够确定混公司希望能够确定混 合饲料中玉米和红薯的数量合饲料中玉米和红薯的数量合饲料中玉米和红薯的数量合饲料中玉米和红薯的数量 使得使得使得使得 饲料能够以最低的成本达到给定的饲料能够以最低的成本达到给定的饲料能够以最低的成本达到给定的饲料能够以最低的成本达到给定的 营养要求营养要求营养要求营养要求 Min Z s t 0 50 8 采购成本采购成本采购成本采购成本 元元元元 20 18 16 4 6 5 8 3 1 碳水化合物碳水化合物碳水化合物碳水化合物 蛋白质蛋白质蛋白质蛋白质 维他命维他命维他命维他命 最低最低最低最低 要求要求要求要求 每公斤每公斤每公斤每公斤 红薯红薯红薯红薯 每公斤每公斤每公斤每公斤 玉米玉米玉米玉米 营养成份营养成份营养成份营养成份 x1 混合饲料中玉米的数量 x2 混合饲料中红薯的数量 12 0 80 5xx 12 12 12 8420 3418 516 0 1 2 i xx xx xx xi 12 例例例例4 4 4 4 广告投入与收益均衡问题广告投入与收益均衡问题广告投入与收益均衡问题广告投入与收益均衡问题 美美美美丽欣公司是一家生产乳制品的公司丽欣公司是一家生产乳制品的公司丽欣公司是一家生产乳制品的公司丽欣公司是一家生产乳制品的公司 生产儿童奶粉生产儿童奶粉生产儿童奶粉生产儿童奶粉 鲜牛奶鲜牛奶鲜牛奶鲜牛奶 成人奶粉成人奶粉成人奶粉成人奶粉 公司希望通过一系列促销措施来提高公司希望通过一系列促销措施来提高公司希望通过一系列促销措施来提高公司希望通过一系列促销措施来提高 自己三个产品的市场占有率自己三个产品的市场占有率自己三个产品的市场占有率自己三个产品的市场占有率 具体要求具体要求具体要求具体要求 如下如下如下如下 1 儿童奶粉市场占有率希望提高儿童奶粉市场占有率希望提高儿童奶粉市场占有率希望提高儿童奶粉市场占有率希望提高 8 2 鲜牛奶市场占有率希望提高鲜牛奶市场占有率希望提高鲜牛奶市场占有率希望提高鲜牛奶市场占有率希望提高 13 3 成人奶粉市场占有率希望提高成人奶粉市场占有率希望提高成人奶粉市场占有率希望提高成人奶粉市场占有率希望提高 5 s t 123 0XXX 公司的促销措施有促销会公司的促销措施有促销会公司的促销措施有促销会公司的促销措施有促销会 电视电视电视电视 广告广告广告广告 印刷媒体广告三种印刷媒体广告三种印刷媒体广告三种印刷媒体广告三种 每种促每种促每种促每种促 销措施销措施销措施销措施 每单位每单位每单位每单位 增加各种产品的市增加各种产品的市增加各种产品的市增加各种产品的市 场占有率和单位成本如下表所示场占有率和单位成本如下表所示场占有率和单位成本如下表所示场占有率和单位成本如下表所示 160210100单位成本单位成本单位成本单位成本 万元万元万元万元 8 3 5 2 3 2 3 1 0 1 2 2 儿童奶粉儿童奶粉儿童奶粉儿童奶粉 鲜牛奶鲜牛奶鲜牛奶鲜牛奶 成人奶粉成人奶粉成人奶粉成人奶粉 要要要要 求求求求 印刷印刷印刷印刷 媒体媒体媒体媒体 电视电视电视电视 广告广告广告广告 促销促销促销促销 会会会会 产品产品产品产品 x1 促销会的单位数量促销会的单位数量促销会的单位数量促销会的单位数量 x2 电视广告的单位数量电视广告的单位数量电视广告的单位数量电视广告的单位数量 x3 印刷媒体广告的单位数量印刷媒体广告的单位数量印刷媒体广告的单位数量印刷媒体广告的单位数量 Min Z 100 x1 210 x2 160 x3 123 123 13 328 2313 225 0 1 2 3 i xxx xxx xx xi 线性规划的 一般形式 目标函数Max Min Z C1X1 C2X2 CnXn a11X1 a12X2 a1n X n b1 约束条件a21X1 a22X2 a2n X n b2 am1X1 am2X2 amnXn bm 非负条件X1 X2 Xn 0 或无约束或无约束或无约束或无约束 线性规划的标准型线性规划的标准型线性规划的标准型线性规划的标准型 技术系数右端项价值系数 约束行数变量个数 2 1 0 2 1 0 max 2211 22222121 11212111 2211 ijij i j mnmnmm nn nn nn abc mn mib njx bxaxaxa bxaxaxa bxaxaxa ts xcxcxcZ L L L M L L L 非标准形非标准形非标准形非标准形LPLPLPLP问题的标准化问题的标准化问题的标准化问题的标准化 1 1 1 1 若目标函数为若目标函数为若目标函数为若目标函数为MinZMinZMinZMinZ 令令令令Z Z Z Z Z Z Z Z 则则则则MinZMinZMinZMinZ等价于等价于等价于等价于MaxZMaxZMaxZMaxZ 2 2 2 2 若为不等式约束若为不等式约束若为不等式约束若为不等式约束 若为若为若为若为 在方程左边加一非负新变量在方程左边加一非负新变量在方程左边加一非负新变量在方程左边加一非负新变量 称松弛变量称松弛变量称松弛变量称松弛变量 若为若为若为若为 在方程左边减一非负新变量在方程左边减一非负新变量在方程左边减一非负新变量在方程左边减一非负新变量 称剩余变量或松弛称剩余变量或松弛称剩余变量或松弛称剩余变量或松弛 变量变量变量变量 3 3 3 3 若若若若b b b bi i i i 0 0 0 0 方程两边同乘方程两边同乘方程两边同乘方程两边同乘 1 1 1 1 4 4 4 4 若变量不满足非负若变量不满足非负若变量不满足非负若变量不满足非负 若若若若x x x xK K K K 0 0 0 0 令令令令x x x xK K K K x x x xK K K K x x x xK K K K 0 0 0 0 用用用用 x x x xK K K K 替换替换替换替换x x x xk k k k 若若若若x x x xK K K K无约束无约束无约束无约束 令令令令x x x xK K K K x x x xK K K K x x x xK K K K x x x xK K K K x x x xK K K K 0 0 0 0 用此式替换用此式替换用此式替换用此式替换 模型中模型中模型中模型中x x x xk k k k 1 min n jj j Zc x 1 max n jj j Zc x 等价于等价于等价于等价于 例例例例6 将下列线性规划问题化为标准形式 123 123 123 123 13 min235 32320 25 24 0 0 Zxxx xxx xxx st xxx xx 222 xxx 令 1223 12234 12235 1223 122345 max2335 322320 25 2 4 0 Zxxxx xxxxx xxxxx st xxxx x xxx xx 17 2 3 线性规划图解法线性规划图解法线性规划图解法线性规划图解法 例1 线性规划问题 Max 12 43Zxx 1 2 12 12 6 28 2318 0 x x xx x x s t 7 4 6 5 3 2 1 100654321879 x2 x1 x1 6 2x2 8 2x1 3x2 18 Z 4x1 3x2 12 目标等值线目标等值线目标等值线目标等值线 Q 6 2 18 03 69x1 6 4 2 x2 可行域可行域可行域可行域 Z 36 3 4 多重解举例多重解举例多重解举例多重解举例 此线段上的点 均为最优点 1 2 12 12 6 28 2318 0 x x xx x x s t Max Z 4x1 6x2 19 无界解举例无界解举例无界解举例无界解举例 Max Z X1 X2 2X1 X2 3 3 3 3 X1 2X2 4 4 4 4 X1 X2 0 0 0 0 A 053179 x1 x2 k 4 6 2 x2 x1 Z Z Z Z值增大方向值增大方向值增大方向值增大方向 20 无可行解举例无可行解举例无可行解举例无可行解举例 Max Z 4X1 3X2 X1 6 6 6 6 2X2 8 8 8 8 2X1 3X2 18 18 18 18 X1 X2 12 12 12 12 X1 X2 0 0 0 0 无公共区域 可行域 7 4 6 5 3 2 1 100654321879 x2 x1 21 4 3线性规划应用案例线性规划应用案例线性规划应用案例线性规划应用案例 18 25 130001 20成分成分成分成分4 最少最少最少最少30 最多最多最多最多20 110001 36成分成分成分成分3 最多最多最多最多40 最少最少最少最少35 120001 15成分成分成分成分2 最少最少最少最少25 最多最多最多最多30 60000 85成分成分成分成分1 特殊汽油特殊汽油特殊汽油特殊汽油 产品要求产品要求产品要求产品要求 一般汽油产一般汽油产一般汽油产一般汽油产 品要求品要求品要求品要求 最大供应量最大供应量最大供应量最大供应量 加仑加仑加仑加仑 单位成本单位成本单位成本单位成本 美元美元美元美元 石油成石油成石油成石油成 分分分分 一般汽油产品售价为每单位一般汽油产品售价为每单位一般汽油产品售价为每单位一般汽油产品售价为每单位2 5美元美元美元美元 特殊汽油产品售特殊汽油产品售特殊汽油产品售特殊汽油产品售 价为每单位价为每单位价为每单位价为每单位2 67美元美元美元美元 引入决策变量引入决策变量引入决策变量引入决策变量xij 表示第表示第表示第表示第j 种汽油产品种汽油产品种汽油产品种汽油产品 中成份中成份中成份中成份i的含量的含量的含量的含量 例例例例3 混合问题混合问题混合问题混合问题 巨斯特石油公司要生产两种汽油产品巨斯特石油公司要生产两种汽油产品巨斯特石油公司要生产两种汽油产品巨斯特石油公司要生产两种汽油产品 一种是一般的汽油一种是一般的汽油一种是一般的汽油一种是一般的汽油 另一种是另一种是另一种是另一种是 特殊的汽油特殊的汽油特殊的汽油特殊的汽油 公司希望通过合成公司希望通过合成公司希望通过合成公司希望通过合成4类石油成份来生产这两种汽油产品类石油成份来生产这两种汽油产品类石油成份来生产这两种汽油产品类石油成份来生产这两种汽油产品 这些汽油的售这些汽油的售这些汽油的售这些汽油的售 价不同价不同价不同价不同 三种石油成份成本也不同三种石油成份成本也不同三种石油成份成本也不同三种石油成份成本也不同 公司希望确定一种混合这公司希望确定一种混合这公司希望确定一种混合这公司希望确定一种混合这4类石油成份以生产两类石油成份以生产两类石油成份以生产两类石油成份以生产两 种汽油产品的方案来获取最大的利润种汽油产品的方案来获取最大的利润种汽油产品的方案来获取最大的利润种汽油产品的方案来获取最大的利润 x32x31成分成分成分成分3 x42x41成分成分成分成分4 x22x21成分成分成分成分2 x12x11成分成分成分成分1 特殊特殊特殊特殊 汽油汽油汽油汽油 一般一般一般一般 汽油汽油汽油汽油 j i 22 目标函数目标函数目标函数目标函数 1121314112223242 1112212231324142 2 5 2 67 0 85 1 15 1 36 1 2 Zxxxxxxxx xxxxxxxx 石油成分石油成分石油成分石油成分供应量供应量供应量供应量约束约束约束约束 1112 6000 xx 2122 12000 xx 3132 11000 xx 4142 13000 xx 成分成分成分成分1 成分成分成分成分2 成分成分成分成分3 成分成分成分成分4 130001 20成分成分成分成分4 110001 36成分成分成分成分3 120001 15成分成分成分成分2 60000 85成分成分成分成分1 最大最大最大最大 供应量供应量供应量供应量 单位成单位成单位成单位成 本本本本 石油成石油成石油成石油成 分分分分 23 产品规格约束产品规格约束产品规格约束产品规格约束 1111213141 0 3 xxxxx 由由由由 一般汽油产品含成分一般汽油产品含成分一般汽油产品含成分一般汽油产品含成分1最多最多最多最多30 可知可知可知可知 类似地类似地类似地类似地 我们有我们有我们有我们有 2111213141 0 35 xxxxx 3111213141 0 2 xxxxx 4111213141 0 25 xxxxx 1212223242 0 25 xxxxx 2212223242 0 4 xxxxx 3212223242 0 3 xxxxx 4212223242 0 18 xxxxx 0 1 2 3 4 1 2 ij xij 非负约束非负约束非负约束非负约束 成分成分成分成分4 成分成分成分成分3 成分成分成分成分2 成分成分成分成分1 石油石油石油石油 成分成分成分成分 18 25 30 20 40 35 25 30 特殊汽油特殊汽油特殊汽油特殊汽油 要求要求要求要求 一般汽一般汽一般汽一般汽 油要求油要求油要求油要求 x32x31成分成分成分成分3 x42x41成分成分成分成分4 x22x21成分成分成分成分2 x12x11成分成分成分成分1 特殊特殊特殊特殊 汽油汽油汽油汽油 一般一般一般一般 汽油汽油汽油汽油 j i 24 1112212231324142 max1 651 821 351 521 141 311 31 47Zxxxxxxxx 1112 6000 xx 2122 12000 xx 3132 11000 xx 4142 13000 xx 2111213141 0 35 xxxxx 3111213141 0 2 xxxxx 4111213141 0 25 xxxxx 1212223242 0 25 xxxxx 2212223242 0 4 xxxxx 3212223242 0 3 xxxxx 4212223242 0 18 xxxxx 0 1 2 3 4 1 2 ij xij 1111213141 0 3 xxxxx Lingo求解求解求解求解 25 例例例例2 2 2 2 劳动力分配问题劳动力分配问题劳动力分配问题劳动力分配问题 设设设设xi为产品为产品为产品为产品i i i i的生产数量的生产数量的生产数量的生产数量 i 1 2 3 i 1 2 3 i 1 2 3 i 1 2 3 美克制造公司生产三种产品美克制造公司生产三种产品美克制造公司生产三种产品美克制造公司生产三种产品 每单每单每单每单 位产品的利润分别为位产品的利润分别为位产品的利润分别为位产品的利润分别为100元元元元 90元和元和元和元和 95元元元元 两个产品都要经过两个产品都要经过两个产品都要经过两个产品都要经过4个车间加个车间加个车间加个车间加 工工工工 假定每个车间的工人总工时是假定每个车间的工人总工时是假定每个车间的工人总工时是假定每个车间的工人总工时是 给定的给定的给定的给定的 每单位产品在各车间需要每单位产品在各车间需要每单位产品在各车间需要每单位产品在各车间需要 的工时如表所示的工时如表所示的工时如表所示的工时如表所示 Max 123 1009095ZXXX s t 123 123 123 123 0 81 22800 0 30 40 41800 0 91 20 63900 0 80 40 32800 XXX XXX XXX XXX 123 0XXX Lingo求解求解求解求解 26 四种资源四种资源四种资源四种资源 车间的用工量车间的用工量车间的用工量车间的用工量 的使用量分别为的使用量分别为的使用量分别为的使用量分别为2800 1300 3900和和和和 1550 由此可见由此可见由此可见由此可见 按这种生产方案按这种生产方案按这种生产方案按这种生产方案 第一和第三种是紧缺资源第一和第三种是紧缺资源第一和第三种是紧缺资源第一和第三种是紧缺资源 第二和第四种资源有剩余第二和第四种资源有剩余第二和第四种资源有剩余第二和第四种资源有剩余 27 假定这四个车间的用工量可以集中调配 不妨用表示第个车间工 时分配量 i 1 2 3 4 总的可调用工时为 四个车间可用工时总量 2800 1800 3900 2800 11300 模型可调整为模型可调整为模型可调整为模型可调整为 i T Lingo求解求解求解求解 28 2502 4 t42车间车间车间车间4 1502 3 t341 8 t31车间车间车间车间3 2002 2 t23车间车间车间车间2 1002 1 t132 t12车间车间车间车间1 最大最大最大最大 转移转移转移转移 量量量量 培训后培训后培训后培训后 转到车转到车转到车转到车 间间间间4 培训后转培训后转培训后转培训后转 到车间到车间到车间到车间3 培训后培训后培训后培训后 转到车转到车转到车转到车 间间间间2 培训后培训后培训后培训后 转到车转到车转到车转到车 间间间间1 原部原部原部原部 门门门门 95元元元元90元元元元100元元元元单位产品利润单位产品利润单位产品利润单位产品利润 2800 1800 3900 2800 1 2 0 4 0 6 0 3 0 8 0 4 1 2 0 4 1 0 0 3 0 9 0 8 1 2 3 4 总可用工时总可用工时总可用工时总可用工时产品产品产品产品3产品产品产品产品2产品产品产品产品1车间车间车间车间 更一般地更一般地更一般地更一般地 假定不同车间不能随意调动假定不同车间不能随意调动假定不同车间不能随意调动假定不同车间不能随意调动 如要调动须经过如要调动须经过如要调动须经过如要调动须经过 培训培训培训培训 允许转移方案和单位培训转移费用允许转移方案和单位培训转移费用允许转移方案和单位培训转移费用允许转移方案和单位培训转移费用 如表如表如表如表 29 123121323313442 100909522 12 21 82 32 4MaxZXXXtttttt 1311213 2800Tttt 2124223 1800Tttt 313233134 3900Ttttt 43442 2800Ttt 1213 100tt 23 200t 3134 150tt 42 250t 123 1234 0 0 XXX T T T T 0 tij i 1 2 3 4 j 1 2 3 4 Xi 产品产品产品产品i的生产数量的生产数量的生产数量的生产数量 tij 车间车间车间车间i转到车间转到车间转到车间转到车间j的工时数的工时数的工时数的工时数 i T 第第第第i个车间工时分配量个车间工时分配量个车间工时分配量个车间工时分配量 2502 4 t4 车间车间车间车间4 1502 3 t341 8 t31 车间车间车间车间3 2002 2 t23 车间车间车间车间2 1002 1 t132 t12 车间车间车间车间1 最大量最大量最大量最大量转到转到转到转到4转到转到转到转到3转到转到转到转到2转到转到转到转到1原车间原车间原车间原车间 30 1231 1232 1233 1234 0 81 2 0 30 40 4 0 91 20 6 0 80 40 6 XXXT XXXT XXXT XXXT 1311213 2800Tttt 2124223 1800Tttt 313233134 3900Ttttt 43442 2800Ttt 1213 100tt 23 200t 3134 150tt 42 250t 123121323313442 100909522 12 21 82 32 4MaxZXXXtttttt Lingo求解求解求解求解 31 总部设在汉中市的飞达航空公司拥有总部设在汉中市的飞达航空公司拥有总部设在汉中市的飞达航空公司拥有总部设在汉中市的飞达航空公司拥有B737飞机飞机飞机飞机3架架架架 Electra飞机飞机飞机飞机8架和架和架和架和 DC9 飞机飞机飞机飞机2架架架架 经常飞往经常飞往经常飞往经常飞往A B C D四个城市四个城市四个城市四个城市 不同类型飞机由汉中飞往各个城不同类型飞机由汉中飞往各个城不同类型飞机由汉中飞往各个城不同类型飞机由汉中飞往各个城 市的往返费用市的往返费用市的往返费用市的往返费用 往返飞行时间等如表所示往返飞行时间等如表所示往返飞行时间等如表所示往返飞行时间等如表所示 2 2 6 12 2000 3500 6000 10000 A B C D DC9 1 4 8 20 1000 2000 4000 A B C D Electra 2 4 5 10 6000 7000 8000 10000 A B C D B737 飞行时间飞行时间飞行时间飞行时间 小时小时小时小时 飞行费用飞行费用飞行费用飞行费用 元元元元 飞往城市飞往城市飞往城市飞往城市飞机类型飞机类型飞机类型飞机类型 例例例例5飞达航空公司的航线安排问题飞达航空公司的航线安排问题飞达航空公司的航线安排问题飞达航空公司的航线安排问题 32 假定每架飞机每天的最大飞行时间为假定每架飞机每天的最大飞行时间为假定每架飞机每天的最大飞行时间为假定每架飞机每天的最大飞行时间为18小时小时小时小时 城市城市城市城市A每天每天每天每天8班班班班 城市城市城市城市B每天每天每天每天11班班班班 城市城市城市城市C每天每天每天每天10班班班班 城市城市城市城市D每天每天每天每天6班班班班 管理层希望合理安排飞行使得总费用最低管理层希望合理安排飞行使得总费用最低管理层希望合理安排飞行使得总费用最低管理层希望合理安排飞行使得总费用最低 解解解解 用用用用i 1 2 3分别表示分别表示分别表示分别表示3种类型飞机种类型飞机种类型飞机种类型飞机B737 Electra DC9 j 1 2 3 4 分别代表分别代表分别代表分别代表A B C D这四个城市这四个城市这四个城市这四个城市 我们引入决策变量我们引入决策变量我们引入决策变量我们引入决策变量 ij x 表示安排第表示安排第表示安排第表示安排第i种飞机种飞机种飞机种飞机 飞往城市飞往城市飞往城市飞往城市j的次数的次数的次数的次数 i 1 2 3 j 1 2 3 4 33 11121314212223 31323334 60007000800010000100020004000 20003500600010000 MinZxxxxxxx xxxx 112131 122232 132333 1434 11121314 212223 31323334 8 11 10 6 2451054 48144 2261236 0 1 2 3 1 2 3 4 ij xxx xxx xxx xx xxxx xxx xxxx xij 34 例例例例4 下料问题下料问题下料问题下料问题 宏伟机械厂要做宏伟机械厂要做宏伟机械厂要做宏伟机械厂要做100套钢架套钢架套钢架套钢架 每套用长为每套用长为每套用长为每套用长为2 9 m 2 1m 1 5m 的圆钢各一根的圆钢各一根的圆钢各一根的圆钢各一根 已知原料每根长已知原料每根长已知原料每根长已知原料每根长7 4 m 问问问问 应如何下料应如何下料应如何下料应如何下料 可使所用原料最省可使所用原料最省可使所用原料最省可使所用原料最省 根数最少或料头最少根数最少或料头最少根数最少或料头最少根数最少或料头最少 解解解解 先根据经验列出若干能使料头较少的下料方案先根据经验列出若干能使料头较少的下料方案先根据经验列出若干能使料头较少的下料方案先根据经验列出若干能使料头较少的下料方案 并用并用并用并用 x x x xi i i i代表按第代表按第代表按第代表按第i i i i种方案种方案种方案种方案 共共共共8 8 8 8种种种种 下料的下料的下料的下料的原料原料原料原料数数数数 1 41 10 90 80 30 20 10料头料头料头料头 6 06 36 56 67 17 27 37 4合计合计合计合计 401302131 5m 031122002 1m 001010212 9m 87654321方案方案方案方案 35 1 41 10 90 80 30 20 10料头料头料头料头 6 06 36 56 67 17 27 37 4合计合计合计合计 401302131 5m 031122002 1m 001010212 9m x8x7x6x5x4x3x2x1方案方案方案方案 36 此例不同此例不同此例不同此例不同目标目标目标目标 不同约束下的解不同约束下的解不同约束下的解不同约束下的解 方案方案方案方案1安排下料数为安排下料数为安排下料数为安排下料数为30 方案方案方案方案2安排下料数为安排下料数为安排下料数为安排下料数为10 方案方案方案方案4安排下料数为安排下料数为安排下料数为安排下料数为50 其它方案下料数均为其它方案下料数均为其它方案下料数均为其它方案下料数均为0 用的原料数为用的原料数为用的原料数为用的原料数为90根根根根 37 灵敏度分析灵敏度分析灵敏度分析灵敏度分析 模型中的参数一般是预测估计的确定值 而在计划 实施时 这些值一般不可能正好是事先估计的值 因 此有必要在求解后 分析这些参数值在将来可能变化 后对最优解的影响 灵敏度分析就是计算为保持原最优解性质不变灵敏度分析就是计算为保持原最优解性质不变灵敏度分析就是计算为保持原最优解性质不变灵敏度分析就是计算为保持原最优解性质不变 模模模模 型中某一个参数型中某一个参数型中某一个参数型中某一个参数 C C C Cj j j j或或或或b b b bi i i i 单独变化的允许范围单独变化的允许范围单独变化的允许范围单独变化的允许范围 38 例例例例1 红星机械厂开发出两个产品红星机械厂开发出两个产品红星机械厂开发出两个产品红星机械厂开发出两个产品 产品甲与产品乙产品甲与产品乙产品甲与产品乙产品甲与产品乙 已知产品甲需要原料已知产品甲需要原料已知产品甲需要原料已知产品甲需要原料A 产品乙需要用原料产品乙需要用原料产品乙需要用原料产品乙需要用原料B 由于两种产品都在一个设备上生产由于两种产品都在一个设备上生产由于两种产品都在一个设备上生产由于两种产品都在一个设备上生产 且设备工时有限且设备工时有限且设备工时有限且设备工时有限 须合理安排两种产品的产量须合理安排两种产品的产量须合理安排两种产品的产量须合理安排两种产品的产量 使得在资源有限的条件下获得利润最大使得在资源有限的条件下获得利润最大使得在资源有限的条件下获得利润最大使得在资源有限的条件下获得利润最大 设设设设x1为产品甲的产量为产品甲的产量为产品甲的产量为产品甲的产量 x2为为为为 产品乙的产量产品乙的产量产品乙的产量产品乙的产量 39 Lingo Range求解求解求解求解 C C C Cj j j j灵敏度分析灵敏度分析灵敏度分析灵敏度分析 产品甲产品甲产品甲产品甲的单位利润可减少的单位利润可减少的单位利润可减少的单位利润可减少2 产品产品产品产品乙的单位利润乙的单位利润乙的单位利润乙的单位利润 可增加可增加可增加可增加3 也可减少也可减少也可减少也可减少3 即允许变化范围即允许变化范围即允许变化范围即允许变化范围 0 6 资源量增加资源量增加资源量增加资源量增加 或减少或减少或减少或减少 一个单位导致目标函数的增加一个单位导致目标函数的增加一个单位导致目标函数的增加一个单位导致目标函数的增加 或减少或减少或减少或减少 量称为这种资源量称为这种资源量称为这种资源量称为这种资源 的影子价格的影子价格的影子价格的影子价格 原料原料原料原料A的的的的影子价格是影子价格是影子价格是影子价格是2 即即即即原料原料原料原料A单独增加单独增加单独增加单独增加一个单位利润一个单位利润一个单位利润一个单位利润增加增加增加增加两个两个两个两个 单位单位单位单位 原料原料原料原料B的的的的影子价格是影子价格是影子价格是影子价格是0 即即即即单独增加原料单独增加原料单独增加原料单独增加原料B不会不会不会不会增加增加增加增加利润利润利润利润 设备的设备的设备的设备的影子影子影子影子 价格是价格是价格是价格是1 即即即即设备单独增加设备单独增加设备单独增加设备单独增加一个单位利润一个单位利润一个单位利润一个单位利润增加增加增加增加1个单位个单位个单位个单位 b b b bi i i i灵敏度分析灵敏度分析灵敏度分析灵敏度分析 原料原料原料原料A可增加可增加可增加可增加3 也可减少也可减少也可减少也可减少3 即允许变化范围即允许变化范围即允许变化范围即允许变化范围 3 9 原料原料原料原料B可减少可减少可减少可减少4 40 原料原料原料原料A的的的的影子价格是影子价格是影子价格是影子价格是2 即即即即 原料原料原料原料A单独增加单独增加单独增加单独增加一个单位一个单位一个单位一个单位 利润利润利润利润增加增加增加增加两个单位两个单位两个单位两个单位 原问题原问题原问题原问题 Z 4x1 3x2 4 6 3 2 30 新问题新问题新问题新问题 Z 4x1 3x2 4 7 3 4 3 32 x1 7 41 补例补例补例补例 一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产A1 A2两种奶制品两种奶制品两种奶制品两种奶制品 1桶牛奶可以在甲车间用桶牛奶可以在甲车间用桶牛奶可以在甲车间用桶牛奶可以在甲车间用12小时加工成小时加工成小时加工成小时加工成3公斤公斤公斤公斤A1 或者或者或者或者 在乙车间用在乙车间用在乙车间用在乙车间用8小时加工成小时加工成小时加工成小时加工成4公斤公斤公斤公斤A2 根据市场需求根据市场需求根据市场需求根据市场需求 生生生生 产的产的产的产的A1 A2全部能售出全部能售出全部能售出全部能售出 且每公斤且每公斤且每公斤且每公斤A1获利获利获利获利24元元元元 每公斤每公斤每公斤每公斤 A2获利获利获利获利16元元元元 现在加工厂每天能得到现在加工厂每天能得到现在加工厂每天能得到现在加工厂每天能得到50桶牛奶的供桶牛奶的供桶牛奶的供桶牛奶的供 应应应应 每天正式工人总的劳动时间每天正式工人总的劳动时间每天正式工人总的劳动时间每天正式工人总的劳动时间480小时小时小时小时 并且甲车间并且甲车间并且甲车间并且甲车间 每天至多能加工每天至多能加工每天至多能加工每天至多能加工100公斤公斤公斤公斤A1 乙车间的加工能力没有限乙车间的加工能力没有限乙车间的加工能力没有限乙车间的加工能力没有限 制制制制 试为该厂制订一个生产计划试为该厂制订一个生产计划试为该厂制订一个生产计划试为该厂制订一个生产计划 使每天获利最大使每天获利最大使每天获利最大使每天获利最大 并并并并 进一步讨论以下进一步讨论以下进一步讨论以下进一步讨论以下3个附加问题个附加问题个附加问题个附加问题 1 若用若用若用若用35元可以买到元可以买到元可以买到元可以买到1桶牛奶桶牛奶桶牛奶桶牛奶 应否作这项投资应否作这项投资应否作这项投资应否作这项投资 若若若若 投资投资投资投资 每天最多购买多少桶牛奶每天最多购买多少桶牛奶每天最多购买多少桶牛奶每天最多购买多少桶牛奶 2 若可以聘用临时工人以增加劳动时间若可以聘用临时工人以增加劳动时间若可以聘用临时工人以增加劳动时间若可以聘用临时工人以增加劳动时间 付给临时工付给临时工付给临时工付给临时工 人的工资最多是每小时几元人的工资最多是每小时几元人的工资最多是每小时几元人的工资最多是每小时几元 3 由于市场需求变化由于市场需求变化由于市场需求变化由于市场需求变化 每公斤每公斤每公斤每公斤A1的获利增加到的获利增加到的获利增加到的获利增加到30元元元元 应否改变生产计划应否改变生产计划应否改变生产计划应否改变生产计划 42 一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产一奶制品加工厂用牛奶生产A1 A2两种奶制品两种奶制品两种奶制品两种奶制品 1桶牛奶可以桶牛奶可以桶牛奶可以桶牛奶可以 在甲车间用在甲车间用在甲车间用在甲车间用12小时加工成小时加工成小时加工成小时加工成3公斤公斤公斤公斤A1 或者在乙车间用或者在乙车间用或者在乙车间用或者在乙车间用8小时加小时加小时加小时加 工成工成工成工成4公斤公斤公斤公斤A2 根据市场需求根据市场需求根据市场需求根据市场需求 生产的生产的生产的生产的A1 A2全部能售出全部能售出全部能售出全部能售出 且且且且 每公斤每公斤每公斤每公斤A1获利获利获利获利24元元元元 每公斤每公斤每公斤每公斤A2获利获利获利获利16元元元元 现在加工厂每天能现在加工厂每天能现在加工厂每天能现在加工厂每天能 得到得到得到得到50桶牛奶的供应桶牛奶的供应桶牛奶的供应桶牛奶的供应 每天正式工人总的劳动时间每天正式工人总的劳动时间每天正式工人总的劳动时间每天正式工人总的劳动时间480小时小时小时小时 并且甲车间每天至多能加工并且甲车间每天至多能加工并且甲车间每天至多能加工并且甲车间每天至多能加工100公斤公斤公斤公斤A1 乙车间的加工能力没乙车间的加工能力没乙车间的加工能力没乙车间的加工能力没 有限制有限制有限制有限制 试为该厂制订一个生产计划试为该厂制订一个生产计划试为该厂制订一个生产计划试为该厂制订一个生产计划 使每天获利最大使每天获利最大使每天获利最大使每天获利最大 设用设用设用设用x1桶牛奶加工桶牛奶加工桶牛奶加工桶牛奶加工A1 用用用用x2桶牛奶加工桶牛奶加工桶牛奶加工桶牛奶加工A2 模型代码如下模型代码如下模型代码如下模型代码如下 max 72 x1 64 x2 x1 x2 50 12 x1 8 x2 480 3 x1 100 43 最优解为最优解为最优解为最优解为x1 20 x2 30 最优值为最优值为最优值为最优值为z 3360 即用即用即用即用20桶牛桶牛桶牛桶牛 奶生产奶生产奶生产奶生产A1 30桶牛奶生产桶牛奶生产桶牛奶生产桶牛奶生产A2 可获最大利润可获最大利润可获最大利润可获最大利润3360元元元元 原料原料原料原料 劳动时间的剩余均为零劳动时间的剩余均为零劳动时间的剩余均为零劳动时间的剩余均为零 车间甲尚余车间甲尚余车间甲尚余车间甲尚余40 公斤公斤公斤公斤 加工能力加工能力加工能力加工能力 增加增加增加增加1个单位个单位个单位个单位 1桶牛奶桶牛奶桶牛奶桶牛奶 时利润增长时利润增长时利润增长时利润增长48 元元元元 劳动时劳动时劳动时劳动时 间增加间增加间增加间增加1个单位个单位个单位个单位 1小时小时小时小时 时利润增长时利润增长时利润增长时利润增长2 元元元元 增加车间增加车间增加车间增加车间 甲的能力不会使利润增长甲的能力不会使利润增长甲的能力不会使利润增长甲的能力不会使利润增长 max 72 x1 64 x2 x1 x2 50 12 x1 8 x2 480 3 x1 100 44 进一步讨论以下进一步讨论以下进一步讨论以下进一步讨论以下3个附加问题个附加问题个附加问题个附加问题 1 若用若用若用若用35元可以买到元可以买到元可以买到元可以买到1桶牛奶桶牛奶桶牛奶桶牛奶 应否作这项投资应否作这项投资应否作这项投资应否作这项投资 若若若若 投资投资投资投资 每天最多购买多少桶牛奶每天最多购买多少桶牛奶每天最多购买多少桶牛奶每天最多购买多少桶牛奶 用影子价格的概念知用影子价格的概念知用影子价格的概念知用影子价格的概念知 用用用用35元可以买到元可以买到元可以买到元可以买到1桶牛奶桶牛奶桶牛奶桶牛奶 低于低于低于低于 1桶牛奶的影子价格桶牛奶的影子价格桶牛奶的影子价格桶牛奶的影子价格48 当然应该作这项投资当然应该作这项投资当然应该作这项投资当然应该作这项投资 增加增加增加增加1个单位个单位个单位个单位 1桶牛奶桶牛奶桶牛奶桶牛奶 时利润增长时利润增长时利润增长时利润增长48 元元元元 劳动时间劳动时间劳动时间劳动时间 增加增加增加增加1个单位个单位个单位个单位 1小时小时小时小时 时利润增长时利润增长时利润增长时利润增长2 元元元元 增加车间甲的能增加车间甲的能增加车间甲的能增加车间甲的能 力不会使利润增长力不会使利润增长力不会使利润增长力不会使利润增长 由由由由 Allowable Increase 知牛奶原料最多增加知牛奶原料最多增加知牛奶原料最多增加知牛奶原料最多增加10 桶桶桶桶 45 3 由于市场需求变化由于市场需求变化由于市场需求变化由于市场需求变化 每公斤每公斤每公斤每公斤A1的获利增加到的获利增加到的获利增加到的获利增加到30 元元元元 应否改变生产计划应否改变生产计划应否改变生产计划应否改变生产计划 2 若可以聘用临时工人以增加劳动时间