线性规划运用举例

.,线性规划运用举例,汽油调和问题生产工艺优化问题多周期动态生产计划问题.,.,1、汽油调和问题,例：原点炼油厂生产的70,80,85号三种汽油由三种原料调和而成，且有不同的质量要求，每种原料每日可用量、质量指标、成本以及每种汽油的质量要求和价格见表。该炼油厂如何调和才能使得利润最大？假定调和中的质量指标都符合线性相加关系。,.,问题分析:最优调和方案什么原料调入什么产品，调入的数量是多少目标：调和方案的利润最大利润=销售收入-调和成本=产品价格*销售数量-原料成本*用量变量：产品数量？原料数量？其他量？j产品生产数量=各原料调入j产品数量和i原料使用量=i原料调入各个产品的数量和xij=i原料调入各j产品的数量和,.,2、生产工艺优化问题,例：丽佳化工厂生产洗涤剂。原料可从市场上以每公斤5元的价格买到。处理1公斤原料可生产0.5公斤洗衣粉和0.3公斤洗涤剂。处理1公斤原料的费用为1元。工厂还可继续对其进行精加工。用1公斤普通洗衣粉生产0.5公斤浓缩洗衣粉，用1公斤普通洗涤剂生产0.25公斤高级洗涤剂。工厂每日可处理4吨原材料。产品价格，生产成本指标见表。如果市场和原料供应没有限制，问该工厂如何生产才能使其利润最大？,.,3、多周期动态生产计划问题,例：华新机器制造厂专为拖拉机厂配套生产柴油机。今年头四个月收到的订单数量分别为3000，4500,3500,5000台柴油机，该厂正常生产每月可生产柴油机3000台，利用加班还可生产1500台。正常生产成本为每台5000元，加班生产还要追加1500元成本，库存成本为每台每月200元。华新厂如何组织生产才能使其生产成本最低？,.,整数规划应用举例,整数变量特殊约束处理背包问题集合覆盖问题固定费用问题旅行推销商问题下料问题,.,1、整数变量,表示不可分割的数量；表示决策变量（0-1整数变量，具有很多优良特点）；表示决策变量之间的逻辑关系，例如，决策i必须以决策j的结果为前提；描述互斥的选择，从多种方案中选择一个方案；,.,项目投资问题,例：某公司有600万元资金用于投资，有5个项目列入投资计划，各项目投资额和期望受益见下表。由于技术原因，投资受到以下约束：项目1,2和3中必须且只能有一项被选中；项目3和4最多只能被选中一项；项目5被选中的前提是项目1被选中；问如何选择最好的投资方案，使投资收益最大。,.,2、特殊约束处理,互为矛盾的约束：须同时出现的矛盾约束；绝对值约束（改写成两个矛盾约束）；多种选一的约束（n个约束中只有一个约束有效）；描述互斥的选择，从多种方案中选择一个方案；逻辑关系约束（ifthen约束）,.,3、排班问题,邮局一年356天都要有人值班，每天需要的职工人数因业务忙闲而异，据统计邮局每天需要的人数按周期变化，一周内每天需要的人数如下：,排班要符合每周连续工作五天，休息两天的规定，如何排班可使用人最少？,.,4、背包问题,例：一登山队员做登山准备，需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相机和通讯设备。每种物品的重要性系数和重量见下表：,.,5、集合覆盖问题,例：某城市有6个区，规划建消防站，任何区发生火警时消防车要在15分钟内赶到，各区间消防车行驶的时间见下表，求设置消防站最少的方案。,.,6、固定费用问题,人们经常会遇到固定费用问题。例如，要建一条生产线，由生产能力确定的投资规模是固定的，要建设，就要投入一笔固定数量资金；再如，如果生产要租用设备，则不管如何使用该设备，你都要支付一笔固定的租金，租金一般不随生产量的变化而变化，求解这类不连续变化的固定费用问题也要借助整数规划。,.,例：服装厂可生产西服，衬衫和羽绒服。生产不同服装要使用不同设备，该厂可从租赁公司租用这些设备。假定市场需求不成问题，服装厂每月可用人工工时为2000小时，该厂如何安排生产可使每月利润最大。设备租金和其它经济参数见下表：,.,7、旅行推销商问题（TSP）,旅行推销商问题是求访n个城市。每个城市必须访问到，且只能访问一次的最短旅行路线问题（类似中国邮路问