线性规划与整数规划.ppt

《线性规划与整数规划.ppt》由会员分享，可在线阅读，更多相关《线性规划与整数规划.ppt（25页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、线性规划模型第一节 线性规划模型一、线性规划及其数学模型1线性规划问题在生产管理和经营活动中，经常提出一类问题，既如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效益。问题拟定生产计划问题拟定生产计划问题提出问题提出某公司生产炊事用具需要两种资源劳动力和原材料，某公司计划生产三种不同产品，生产管理部门提供的数据如下：劳动力（小时件）原材料（千克件）利润（元件）每天可供应原材料为千克，每天可使用的劳动力为小时，问如何安排生产计划，才能是公司总收益最大？模型建立模型建立设每天生产、三种产品的件数分别为最大利润为则该问题就是在条件下，求利润的最大值。问题运输问题问题运输问题问题的提出问

2、题的提出两个煤炭厂每月进煤分别为60t和100t，联合供应三个居民区三个居民区每月对煤的需求量依次为50t、70t、40t，煤厂离居民区的距离分别为10km、5km、6km，煤厂离居民区的距离分别为4km、8km、12km，如何分配供煤量才能使总运输量达到最小？模型建立模型建立 设表示煤厂提供给居民区的煤量，表示总运输量，则所求问题就是在条件下，求总运输量的最小值。线性规划问题的特点和数学模型从以上两个实例可以看出，它们都属于一类优化问题，其共同特点是：（）所给问题都用一组决策变量表示某一方案，这组决策变量的值就代表一个具体方案，一般这些变量的取是非负的；（）存在一定的约束条件，这些约束条件可

3、以用一组线性等式或线性不等式来表示；（）都有一个要求达到的目标，它可以用决策变量的线性函数来表示，这个函数称为目标函数。按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划问题的数学模型，其一般形式为：目标函数：约束条件：3.线性规划模型的标准型实际问题的线性规划模型是多种多样的，在多种多样的模型中，可规定一种形式为标准型，以便于研究和求解。（1）线性规划模型的标准型如果在线性规划模型中，有n个决策变量m个约束条件，约束条件为等式约束，决策变量非负，求目标函数的最小值，这种线性规划模型就叫做标准型。其表达式为：在标准型中，规定否则等式两端乘以“-1”，其矩阵形式

4、为：其中，称为约束条件的系数矩阵，一般有称为价值向量；向量称为资源向量；称为决策向量；为零向量。（2）任意一线性规划模型都可以化为标准型若原模型要求目标函数实现最大化，即则即目标函数可化为这就与标准型的目标函数一致了。若原模型中的约束条件为不等式，有两种情况：若原模型中的约束条件为不等式：左端右端，则在左端加上“非负松弛变量”使不等式化为等式：左端+非负松弛变量=右端。若原模型中的约束条件为不等式：左端右端，则在左端减去“非负松弛变量”使不等式化为等式：左端-非负松弛变量=右端。例1将问题1的模型化为标准型。二、应用举例1食谱问题食谱问题问题提出一饲养场饲养供实验用的动物，已知动物的生长对饲料

5、中的三种营养成分：蛋白质、矿物质和维生素特别敏感，每个动物每天至少需要蛋白质克，矿物质克，维生素毫克。该场能买到种饲料，各种饲料每千克的成本及所含营养成分如下表所示，请确定既能满足动物需要，又使总成本最低的饲料配方。饲料成本（元）蛋白质（克）矿物质（克）维生素（克）0.20.300.100.050.72.000.050.100.41.000.020.020.30.600.200.200.51.800.050.08设每个动物每天食用的混合饲料中所含的第种饲料的数量为千克，混合饲料的总成本为z,则上述问题的数学模型为连续投资问题连续投资问题问题提出某部门在今后五年内考虑给下列四个项目投资，项目，从

6、第一年到第四年年初需要投资，并于次年末回收本利的115%；项目，第三年年初需要投资，到第五年年末能回收本利125%，但规定最大投资不超过万元；项目，第二年年初需要投资，到第五年年末能回收本利140%，但规定最大投资不超过万元；项目，五年内每年年初购买公债，于当年末归还，并加利息6%。该部门现有资金10万元，问如何分配这些项目每年的投资额，使到第五年末拥有资金的本利总额最大？问题分析（）五年中每年年初该部门拥有的资金是变化的，设表示第i年年初给第j项项目的投资额，显然（）该部门每年的投资额等于部门年初所拥有的资金，下面分年度讨论：第一年，年初拥有资金万元，所以有第二年，年初拥有资金仅为项目在第一

7、年末回收的本息所以有第三年，年初拥有资金为所以有第四年，年初拥有资金为所以有第五年，年初拥有资金为所以有又，由题意知目标函数：模型建立模型建立将上述分析整理，可得此问题的数学模型为：3.下料问题下料问题问题的提出 计划做100套钢架,每套用长为2.9米、2.1米、1.5米的圆钢各一根。设原材料长7.4米，问如何下料，才能使所用原料最少？分析 最简单的做法是在每一根原料上截取三种长度不同的圆钢各一根组成一套，但浪费较大。若改为套截，则可节省原料。8种套截方案如下表：方案配件123456782.9211100002.1021032101.510130234余料0.10.30.901.10.20.8

8、1.4设按第i种方案下料的原料根数为表示总余料,则所求问题的数学模型为注:该问题的数学模型的目标函数也可以为:其中表示使用原料总根数.第二节 整数规划模型在一般的线性规划模型中,再加上决策变量取整的条件,所得到的一类规划问题称为整数线性规划.问题问题1 货物托运问题货物托运问题某公司拟用集装箱托运A,B两种货物，每箱的体积、重量、可获得利润以及托运所受限制如下表所示。问两种货物各运多少箱可获得最大利润？货物体积（立方米/箱）重量（公斤/箱）利润（元/箱）A51002000B42501000托运限制24650一、整数规划模型设分别表示这两种货物的托运箱数，则该问题的数学模型为：一般地，某公司拟用

9、集装箱托运n种货物每箱的体积、重量、可获得利润以及托运所受限制为V和M，问怎么装箱可获得最大利润？问题问题2 分派问题分派问题分配n个人去完成n项任务，第i个人完成第j项任务的效率为每个人恰好完成一项任务，如何分配使总效率最大？设0-1变量则此问题的数学模型为二、0-1整数规划模型0-1整数规划模型是整数规划模型中的特殊情形，它的决策变量仅取0或1。这时又叫0-1变量。问题问题2 分派问题分派问题就是0-1整数规划模型整数规划模型问题问题3 选址问题选址问题问题提出问题提出 某公司欲在城市的东、西、南三区建立门市部，拟议中有7个位置可供选择，规定在东区，由三个位置中至多选两个；在西区，由两个个

10、位置中至少选一个；在南区，由两个个位置中至少选一个。如果选用则设备投资费用为每年可获利润为但投资总额不能超过B元，问应选择哪几个位置，可使年利润最大？模型建立 首先引入0-1变量则此问题的数学模型为习题1.某昼夜服务的公交线路每天各时间段内所需要司机和乘务员如下表。设司机和乘务员分别在各时间区段一开始时上班，并连续工作8小时。问该公交线路至少要配备多少司机和乘务员？班次时间段所需人数班次时间段所需人数16:0010:0060418:0022:0050210:0014:0070522:002:0020314:0018:006062:006:0030设每人每天只上一轮班(8小时),第i时间段开始时

11、有名人员上班,则2.背包问题背包问题 一个旅行者必须决定在旅途中要携带哪些物品,才能使携带的总重量不超过b公斤,以使总的“价值”最大,这样的问题称为背包问题.设有n件物品,第i件物品的重量为公斤,携带的“价值”为试建立背包问题的数学模型.首先引入0-1变量则此问题的数学模型为3.比赛安排问题比赛安排问题 已知下列5名运动员各种游泳项目的成绩(各为50米)如下表所示,问如何从中选拔一个参加200米混合游泳的接力队,使预期成绩最好.项目赵钱张王周仰泳37.332.933.837.035.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.14.加工任务安排加工任务安排某工厂用两台机床加工三种不同的零件.已知在一个生产周期内只能工作80机时;只能工作100机时.一个生产周期内计划加工三种不同的零件分别为:70件、50件、20件。两台机床加工每个零件的时间和成本分别如下表所示：加工每个零件的时间（单位：机时/个）零件机床123113加工每个零件的成本（单位：元/个）零件机床235336问怎样安排两台机床一个周期的加工任务，才能是加工成本最低？