线性规划运用举例PPT优秀课件

《线性规划运用举例PPT优秀课件》由会员分享，可在线阅读，更多相关《线性规划运用举例PPT优秀课件（18页珍藏版）》请在装配图网上搜索。

1、1线性规划运用举例线性规划运用举例 汽油调和问题汽油调和问题 生产工艺优化问题生产工艺优化问题 多周期动态生产计划问题多周期动态生产计划问题.21 1、汽油调和问题、汽油调和问题产品产品辛烷值辛烷值含硫量含硫量%销售价格销售价格（元（元/顿）顿）7070号汽油号汽油大于等大于等于于7070小于等小于等于于1.01.09009008080号汽油号汽油大于等大于等于于8080小于等小于等于于1.01.0120012008585号汽油号汽油大于等大于等于于8585小于等小于等于于0.60.615001500例：原点炼油厂生产的例：原点炼油厂生产的70,80,8570,80,85号三种汽油由三种原号三

2、种汽油由三种原料调和而成，且有不同的质量要求，每种原料每日可料调和而成，且有不同的质量要求，每种原料每日可用量、质量指标、成本以及每种汽油的质量要求和价用量、质量指标、成本以及每种汽油的质量要求和价格见表。该炼油厂如何调和才能使得利润最大？假定格见表。该炼油厂如何调和才能使得利润最大？假定调和中的质量指标都符合线性相加关系。调和中的质量指标都符合线性相加关系。原料原料辛烷辛烷值值含含硫硫量量%销售价格销售价格（元（元/顿）顿）可用量可用量（顿（顿/日）日）直馏直馏汽油汽油62621.51.560060020002000催化催化汽油汽油78780.80.890090010001000重整重整汽油

3、汽油90900.20.2140014005005003问题分析问题分析:最优调和方案最优调和方案 什么原料调入什么产品，调入的数量是多少什么原料调入什么产品，调入的数量是多少目标：调和方案的利润最大目标：调和方案的利润最大利润利润=销售收入销售收入-调和成本调和成本 =产品价格产品价格*销售数量销售数量-原料成本原料成本*用量用量变量：产品数量？原料数量？其他量？变量：产品数量？原料数量？其他量？j j产品生产数量产品生产数量=各原料调入各原料调入j j产品数量和产品数量和 i i原料使用量原料使用量=i i原料调入各个产品的数量和原料调入各个产品的数量和 x xij ij=i i原料调入各原

4、料调入各j j产品的数量和产品的数量和42 2、生产工艺优化问题、生产工艺优化问题例：丽佳化工厂生产洗涤剂。原料可从市场上以每公斤例：丽佳化工厂生产洗涤剂。原料可从市场上以每公斤5 5元的价格买到。处理元的价格买到。处理1 1公斤原料可生产公斤原料可生产0.50.5公斤洗衣粉和公斤洗衣粉和0.30.3公斤洗涤剂。处理公斤洗涤剂。处理1 1公斤原料的费用为公斤原料的费用为1 1元。工厂还可元。工厂还可继续对其进行精加工。用继续对其进行精加工。用1 1公斤普通洗衣粉生产公斤普通洗衣粉生产0.50.5公斤公斤浓缩洗衣粉，用浓缩洗衣粉，用1 1公斤普通洗涤剂生产公斤普通洗涤剂生产0.250.25公斤高

5、级洗涤公斤高级洗涤剂。工厂每日可处理剂。工厂每日可处理4 4吨原材料。产品价格，生产成本指吨原材料。产品价格，生产成本指标见表。如果市场和原料供应没有限制，问该工厂如何标见表。如果市场和原料供应没有限制，问该工厂如何生产才能使其利润最大？生产才能使其利润最大？产品产品销售价格销售价格元元/公斤公斤加工成本加工成本元元/公斤公斤普通洗衣粉普通洗衣粉8 8-普通洗涤剂普通洗涤剂1212-浓缩洗衣粉浓缩洗衣粉24243 3高级洗衣剂高级洗衣剂55553 353 3、多周期动态生产计划问题、多周期动态生产计划问题例：华新机器制造厂专为拖拉机厂配套生产柴油机。今年例：华新机器制造厂专为拖拉机厂配套生产柴

6、油机。今年头四个月收到的订单数量分别为头四个月收到的订单数量分别为30003000，4500,3500,50004500,3500,5000台台柴油机，该厂正常生产每月可生产柴油机柴油机，该厂正常生产每月可生产柴油机30003000台，利用加台，利用加班还可生产班还可生产15001500台。正常生产成本为每台台。正常生产成本为每台50005000元，加班生元，加班生产还要追加产还要追加15001500元成本，库存成本为每台每月元成本，库存成本为每台每月200200元。华元。华新厂如何组织生产才能使其生产成本最低？新厂如何组织生产才能使其生产成本最低？6整数规划应用举例整数规划应用举例 整数变量

7、整数变量 特殊约束处理特殊约束处理 背包问题背包问题 集合覆盖问题集合覆盖问题 固定费用问题固定费用问题 旅行推销商问题旅行推销商问题 下料问题下料问题71 1、整数变量、整数变量 表示不可分割的数量；表示不可分割的数量；表示决策变量（表示决策变量（0-10-1整数变量，具有很多优良特点）；整数变量，具有很多优良特点）；表示决策变量之间的逻辑关系，例如，决策表示决策变量之间的逻辑关系，例如，决策i i必须以决策必须以决策 j j的结果为前提；的结果为前提；描述互斥的选择，从多种方案中选择一个方案；描述互斥的选择，从多种方案中选择一个方案；8项目投资问题项目投资问题例：某公司有例：某公司有600

8、600万元资金用于投资，有万元资金用于投资，有5 5个项目列入投资计划，各个项目列入投资计划，各项目投资额和期望受益见下表。由于技术原因，投资受到以下约束：项目投资额和期望受益见下表。由于技术原因，投资受到以下约束：项目项目1,21,2和和3 3中必须且只能有一项被选中；中必须且只能有一项被选中；项目项目3 3和和4 4最多只能被选中一项；最多只能被选中一项；项目项目5 5被选中的前提是项目被选中的前提是项目1 1被选中；被选中；问如何选择最好的投资方案，使投资收益最大。问如何选择最好的投资方案，使投资收益最大。项目项目投资额（万元）投资额（万元）投资收益（万元）投资收益（万元）1 12102

9、101501502 23003002102103 310010060604 413013080805 526026018018092 2、特殊约束处理、特殊约束处理 互为矛盾的约束：须同时出现的矛盾约束；互为矛盾的约束：须同时出现的矛盾约束；绝对值约束（改写成两个矛盾约束）；绝对值约束（改写成两个矛盾约束）；多种选一的约束（多种选一的约束（n n个约束中只有一个约束有效）；个约束中只有一个约束有效）；描述互斥的选择，从多种方案中选择一个方案；描述互斥的选择，从多种方案中选择一个方案；逻辑关系约束（逻辑关系约束（if then if then 约束）约束）103 3、排班问题、排班问题邮局一年邮

10、局一年356356天都要有人值班，每天需要的职工人天都要有人值班，每天需要的职工人数因业务忙闲而异，据统计邮局每天需要的人数按数因业务忙闲而异，据统计邮局每天需要的人数按周期变化，一周内每天需要的人数如下：周期变化，一周内每天需要的人数如下：周一周一周二周二周三周三周四周四周五周五周六周六周日周日1717131315151919141416161111排班要符合每周连续工作五天，休息两天的规定，排班要符合每周连续工作五天，休息两天的规定，如何排班可使用人最少？如何排班可使用人最少？114 4、背包问题、背包问题序号序号1 12 23 34 45 56 67 7物品物品食品食品氧气氧气冰镐冰镐绳

11、索绳索帐篷帐篷照相机照相机通讯设备通讯设备重量重量重要系数重要系数5 520205 515152 218186 6141412128 82 24 44 41010例：一登山队员做登山准备，需要携带的物品有：例：一登山队员做登山准备，需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相机和通讯设食品、氧气、冰镐、绳索、帐篷、照相机和通讯设备。每种物品的重要性系数和重量见下表：备。每种物品的重要性系数和重量见下表：125 5、集合覆盖问题、集合覆盖问题地区地区1 12 23 34 45 56 61 12 23 34 45 56 60 01010161628282727202010100 02424

12、323217171010161624240 01212272721212828323212120 01515252527271717272715150 01414202010102121252514140 0例：某城市有例：某城市有6 6个区，规划建消防站，任何区发生个区，规划建消防站，任何区发生火警时消防车要在火警时消防车要在1515分钟内赶到，各区间消防车行分钟内赶到，各区间消防车行驶的时间见下表，求设置消防站最少的方案。驶的时间见下表，求设置消防站最少的方案。136 6、固定费用问题、固定费用问题人们经常会遇到固定费用问题。例如，要建一条生人们经常会遇到固定费用问题。例如，要建一条生产线

13、，由生产能力确定的投资规模是固定的，要建产线，由生产能力确定的投资规模是固定的，要建设，就要投入一笔固定数量资金；再如，如果生产设，就要投入一笔固定数量资金；再如，如果生产要租用设备，则不管如何使用该设备，你都要支付要租用设备，则不管如何使用该设备，你都要支付一笔固定的租金，租金一般不随生产量的变化而变一笔固定的租金，租金一般不随生产量的变化而变化，求解这类不连续变化的固定费用问题也要借助化，求解这类不连续变化的固定费用问题也要借助整数规划。整数规划。14例：服装厂可生产西服，衬衫和羽绒服。生产不同例：服装厂可生产西服，衬衫和羽绒服。生产不同服装要使用不同设备，该厂可从租赁公司租用这些服装要使

14、用不同设备，该厂可从租赁公司租用这些设备。假定市场需求不成问题，服装厂每月可用人设备。假定市场需求不成问题，服装厂每月可用人工工时为工工时为20002000小时，该厂如何安排生产可使每月利小时，该厂如何安排生产可使每月利润最大。设备租金和其它经济参数见下表：润最大。设备租金和其它经济参数见下表：序号序号服装种类服装种类租金租金元元生产成生产成本本销售价销售价格格人工工人工工时时设备工设备工时时设备可用设备可用工时工时1 1西服西服500050002802804004005 53 33003002 2衬衫衬衫20002000303040401 10.50.53003003 3羽绒服羽绒服3000

15、30002002003003004 42 2300300157 7、旅行推销商问题（、旅行推销商问题（TSPTSP）旅行推销商问题是求访旅行推销商问题是求访n n个城市。每个城市必须访个城市。每个城市必须访问到，且只能访问一次的最短旅行路线问题（类似问到，且只能访问一次的最短旅行路线问题（类似中国邮路问题，沿着街道走，走过所有街道，回到中国邮路问题，沿着街道走，走过所有街道，回到原地，网络中的问题）。原地，网络中的问题）。16地区地区1 12 23 34 45 51 12 23 34 45 50 01313222216166 613130 0292920208 8222229290 01111

16、30301616202011110 020206 68 8303020200 0例：旅行推销商要走五个城市，各城市间的距离如例：旅行推销商要走五个城市，各城市间的距离如下表：下表：17 2.9m 2.9m钢筋架子钢筋架子100100个，每个需用个，每个需用 2.1m 2.1m 各各1 1，原料长，原料长7.4m7.4m 1.5m 1.5m求：如何下料，使得残余料头最少。求：如何下料，使得残余料头最少。解：首先列出各种可能的下料方案；解：首先列出各种可能的下料方案；计算出每个方案可得到的不同长度钢筋的数量及残余计算出每个方案可得到的不同长度钢筋的数量及残余料头长度；料头长度；确定决策变量；确定决

17、策变量；根据下料目标确定目标函数；根据下料目标确定目标函数；根据不同长度钢筋的需要量确定约束方程。根据不同长度钢筋的需要量确定约束方程。8 8、合理下料问题、合理下料问题18设按第设按第i i种方案下料的原材料为种方案下料的原材料为x xi i根根8,7,6,5,4,3,2,1100432030100002302010000002.4.18.02.01.109.03.01.087654321876543218765432187654321ixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxZMini为大于零的整数，组合方案组合方案 1 2 3 4 5 6 7 8 2.9m 2 1 1 1 0 0 0 0 2.1m 0 2 1 0 3 2 1 0 1.5m 1 0 1 3 0 2 3 4 合合 计计 7.3m 7.1m 6.5m 7.4m 6.3m 7.2m 6.6m 6.0m 料料 长长 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 7.4m 料料 头头 0.1m 0.3m 0.9m 0.0m 1.1m 0.2m 0.8m 1.4m