线性规划运用举例PPT课件.ppt

线线性性规规划运用划运用举举例例汽油汽油调调和和问题问题生生产产工工艺优艺优化化问题问题多周期多周期动态动态生生产计产计划划问题问题.1.1 1、汽油、汽油调调和和问题问题产产品品辛辛烷值烷值含硫量含硫量%销销售价格售价格（元（元/顿顿）7070号汽油号汽油大于等大于等于于7070小于等小于等于于1.01.09009008080号汽油号汽油大于等大于等于于8080小于等小于等于于1.01.0120012008585号汽油号汽油大于等大于等于于8585小于等小于等于于0.60.615001500例：原点例：原点炼炼油厂生油厂生产产的的70,80,8570,80,85号三种汽油由三种原号三种汽油由三种原料料调调和而成，且有不同的和而成，且有不同的质质量要求，每种原料每日可量要求，每种原料每日可用量、用量、质质量指量指标标、成本以及每种汽油的、成本以及每种汽油的质质量要求和价量要求和价格格见见表。表。该炼该炼油厂如何油厂如何调调和才能使得利和才能使得利润润最大？假定最大？假定调调和中的和中的质质量指量指标标都符合都符合线线性相加关系。性相加关系。原料原料辛辛烷烷值值含含硫硫量量%销销售价格售价格（元（元/顿顿）可用量可用量（顿顿/日）日）直直馏馏汽油汽油62621.51.560060020002000催化催化汽油汽油78780.80.890090010001000重整重整汽油汽油90900.20.2140014005005002.问题问题分析分析:最最优调优调和方案和方案 什么原料什么原料调调入什么入什么产产品，品，调调入的数量是多少入的数量是多少目目标标：调调和方案的利和方案的利润润最大最大利利润润=销销售收入售收入-调调和成本和成本 =产产品价格品价格*销销售数量售数量-原料成本原料成本*用量用量变变量：量：产产品数量？原料数量？其他量？品数量？原料数量？其他量？j j产产品生品生产产数量数量=各原料各原料调调入入j j产产品数量和品数量和 i i原料使用量原料使用量=i i原料原料调调入各个入各个产产品的数量和品的数量和 x xij ij=i i原料原料调调入各入各j j产产品的数量和品的数量和3.2 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公斤高公斤高级级洗洗涤涤剂剂。工厂每日可。工厂每日可处处理理4 4吨原材料。吨原材料。产产品价格，生品价格，生产产成本指成本指标见标见表。如果市表。如果市场场和原料供和原料供应应没有限制，没有限制，问该问该工厂如何工厂如何生生产产才能使其利才能使其利润润最大？最大？产产品品销销售价格售价格元元/公斤公斤加工成本加工成本元元/公斤公斤普通洗衣粉普通洗衣粉8 8-普通洗普通洗涤剂涤剂1212-浓缩浓缩洗衣粉洗衣粉24243 3高高级级洗衣洗衣剂剂55553 34.3 3、多周期、多周期动态动态生生产计产计划划问题问题例：例：华华新机器制造厂新机器制造厂专为专为拖拉机厂配套生拖拉机厂配套生产产柴油机。今年柴油机。今年头头四个月收到的四个月收到的订单订单数量分数量分别为别为30003000，4500,3500,50004500,3500,5000台台柴油机，柴油机，该该厂正常生厂正常生产产每月可生每月可生产产柴油机柴油机30003000台，利用加台，利用加班班还还可生可生产产15001500台。正常生台。正常生产产成本成本为为每台每台50005000元，加班生元，加班生产还产还要追加要追加15001500元成本，元成本，库库存成本存成本为为每台每月每台每月200200元。元。华华新厂如何新厂如何组织组织生生产产才能使其生才能使其生产产成本最低？成本最低？5.整数整数规规划划应应用用举举例例整数整数变变量量特殊特殊约约束束处处理理背包背包问题问题集合覆盖集合覆盖问题问题固定固定费费用用问题问题旅行推旅行推销销商商问题问题下料下料问题问题6.1 1、整数、整数变变量量 表示不可分割的数量；表示不可分割的数量；表示决策表示决策变变量（量（0-10-1整数整数变变量，具有很多量，具有很多优优良特点）；良特点）；表示决策表示决策变变量之量之间间的的逻辑逻辑关系，例如，决策关系，例如，决策i i必必须须以决策以决策 j j的的结结果果为为前提；前提；描述互斥的描述互斥的选择选择，从多种方案中，从多种方案中选择选择一个方案；一个方案；7.项项目投目投资问题资问题例：某公司有例：某公司有600600万元万元资资金用于投金用于投资资，有，有5 5个个项项目列入投目列入投资计资计划，各划，各项项目投目投资额资额和期望受益和期望受益见见下表。由于技下表。由于技术术原因，投原因，投资资受到以下受到以下约约束：束：项项目目1,21,2和和3 3中必中必须须且只能有一且只能有一项项被被选选中；中；项项目目3 3和和4 4最多只能被最多只能被选选中一中一项项；项项目目5 5被被选选中的前提是中的前提是项项目目1 1被被选选中；中；问问如何如何选择选择最好的投最好的投资资方案，使投方案，使投资资收益最大。收益最大。项项目目投投资额资额（万元）（万元）投投资资收益（万元）收益（万元）1 12102101501502 23003002102103 310010060604 413013080805 52602601801808.2 2、特殊、特殊约约束束处处理理 互互为为矛盾的矛盾的约约束：束：须须同同时时出出现现的矛盾的矛盾约约束；束；绝对值约绝对值约束（改写成两个矛盾束（改写成两个矛盾约约束）；束）；多种多种选选一的一的约约束（束（n n个个约约束中只有一个束中只有一个约约束有效）；束有效）；描述互斥的描述互斥的选择选择，从多种方案中，从多种方案中选择选择一个方案；一个方案；逻辑逻辑关系关系约约束（束（if then if then 约约束）束）9.3 3、排班、排班问题问题邮邮局一年局一年356356天都要有人天都要有人值值班，每天需要的班，每天需要的职职工人工人数因数因业务业务忙忙闲闲而异，据而异，据统计邮统计邮局每天需要的人数按局每天需要的人数按周期周期变变化，一周内每天需要的人数如下：化，一周内每天需要的人数如下：周一周一周二周二周三周三周四周四周五周五周六周六周日周日1717131315151919141416161111排班要符合每周排班要符合每周连续连续工作五天，休息两天的工作五天，休息两天的规规定，定，如何排班可使用人最少？如何排班可使用人最少？10.4 4、背包、背包问题问题序号序号1 12 23 34 45 56 67 7物品物品食品食品氧气氧气冰冰镐镐绳绳索索帐帐篷篷照相机照相机通通讯设备讯设备重量重量重要系数重要系数5 520205 515152 218186 6141412128 82 24 44 41010例：一登山例：一登山队员队员做登山准做登山准备备，需要携，需要携带带的物品有：的物品有：食品、氧气、冰食品、氧气、冰镐镐、绳绳索、索、帐帐篷、照相机和通篷、照相机和通讯设讯设备备。每种物品的重要性系数和重量。每种物品的重要性系数和重量见见下表：下表：11.5 5、集合覆盖、集合覆盖问题问题地区地区1 12 23 34 45 56 61 12 23 34 45 56 60 01010161628282727202010100 02424323217171010161624240 01212272721212828323212120 01515252527271717272715150 01414202010102121252514140 0例：某城市有例：某城市有6 6个区，个区，规规划建消防站，任何区划建消防站，任何区发发生生火警火警时时消防消防车车要在要在1515分分钟钟内赶到，各区内赶到，各区间间消防消防车车行行驶驶的的时间见时间见下表，求下表，求设设置消防站最少的方案。置消防站最少的方案。12.6 6、固定、固定费费用用问题问题人人们经们经常会遇到固定常会遇到固定费费用用问题问题。例如，要建一条生。例如，要建一条生产线产线，由生，由生产产能力确定的投能力确定的投资规资规模是固定的，要建模是固定的，要建设设，就要投入一笔固定数量，就要投入一笔固定数量资资金；再如，如果生金；再如，如果生产产要租用要租用设备设备，则则不管如何使用不管如何使用该设备该设备，你都要支付，你都要支付一笔固定的租金，租金一般不随生一笔固定的租金，租金一般不随生产产量的量的变变化而化而变变化，求解化，求解这类这类不不连续变连续变化的固定化的固定费费用用问题问题也要借助也要借助整数整数规规划。划。13.例：服装厂可生例：服装厂可生产产西服，西服，衬衬衫和羽衫和羽绒绒服。生服。生产产不同不同服装要使用不同服装要使用不同设备设备，该该厂可从租厂可从租赁赁公司租用公司租用这这些些设备设备。假定市。假定市场场需求不成需求不成问题问题，服装厂每月可用人，服装厂每月可用人工工工工时为时为20002000小小时时，该该厂如何安排生厂如何安排生产产可使每月利可使每月利润润最大。最大。设备设备租金和其它租金和其它经济经济参数参数见见下表：下表：序号序号服装种服装种类类租金租金元元生生产产成成本本销销售价售价格格人工工人工工时时设备设备工工时时设备设备可用可用工工时时1 1西服西服500050002802804004005 53 33003002 2衬衬衫衫20002000303040401 10.50.53003003 3羽羽绒绒服服300030002002003003004 42 230030014.7 7、旅行推、旅行推销销商商问题问题（TSPTSP）旅行推旅行推销销商商问题问题是求是求访访n n个城市。每个城市必个城市。每个城市必须访须访问问到，且只能到，且只能访问访问一次的最短旅行路一次的最短旅行路线问题线问题（类类似似中国中国邮邮路路问题问题，沿着街道走，走，沿着街道走，走过过所有街道，回到所有街道，回到原地，网原地，网络络中的中的问题问题）。）。15.地区地区1 12 23 34 45 51 12 23 34 45 50 01313222216166 613130 0292920208 8222229290 0111130301616202011110 020206 68 8303020200 0例：旅行推例：旅行推销销商要走五个城市，各城市商要走五个城市，各城市间间的距离如的距离如下表：下表：16.2.9m 2.9m钢钢筋架子筋架子100100个，每个需用个，每个需用 2.1m 2.1m 各各1 1，原料，原料长长7.4m7.4m 1.5m 1.5m求：如何下料，使得残余料求：如何下料，使得残余料头头最少。最少。解：首先列出各种可能的下料方案；解：首先列出各种可能的下料方案；计计算出每个方案可得到的不同算出每个方案可得到的不同长长度度钢钢筋的数量及残余筋的数量及残余料料头长头长度；度；确定决策确定决策变变量；量；根据下料目根据下料目标标确定目确定目标标函数；函数；根据不同根据不同长长度度钢钢筋的需要量确定筋的需要量确定约约束方程。束方程。8 8、合理下料、合理下料问题问题17.设设按第按第i i种方案下料的原材料种方案下料的原材料为为x xi i根根组组合方案合方案 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.4m18.