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