线性规划与整数规划

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,线性规划模型,第一节 线性规划模型,一、线性规划及其数学模型,1线性规划问题,在生产管理和经营活动中，经常提出一类问题，既如何合理地,利用有限的人力、物力、财力等资源，以便得到最好的经济效益。,问题拟定生产计划,问题提出,某公司生产炊事用具需要两种资源劳动力和原材,料，某公司计划生产三种不同产品，生产管理部门提供的数据如下：,劳动力（小时件）,原材料（千克件）,利润（元件）,每天可供应原材料为千克，每天可使用的劳动力为小,时，问如何安排生产计划，才能是公司总收益最大？,模型建立,设每天生产、三种产品的件数分别为,最大利润为,则该问题就是在条件,下，求利润,的最大值。,问题运输问题,问题的提出,两个煤炭厂,每月进煤分别为60t和100t，,联合供应三个居民区,三个居民区每月对煤的需求量依次,为50t、70t、40t，煤厂,离居民区,的距离分别为10km、,5km、6km，煤厂,离居民区,的距离分别为4km、8km、,12km，如何分配供煤量才能使总运输量,达到最小？,模型建立,设,表示煤厂,提供给居民区,的煤量，,表示总运输量，则所求问题就是在条件,下，求总运输量,的最小值。,线性规划问题的特点和数学模型,从以上两个实例可以看出，它们都属于一类优化问题，其共同,特点是：,（）所给问题都用一组决策变量,表示某一方案，,这组决策变量的值就代表一个具体方案，一般这些变量的取是非,负的；,（）存在一定的约束条件，这些约束条件可以用一组线性,等式或线性不等式来表示；,（）都有一个要求达到的目标，它可以用决策变量的线性,函数来表示，这个函数称为,目标函数,。按问题的不同，要求目标,函数实现,最大化或最小化,。,满足以上三个条件的数学模型称为线性规划问题的数学模型，,其一般形式为：,目标函数：,约束条件：,3.线性规划模型的标准型,实际问题的线性规划模型是多种多样的，在多种多样的模型中，,可规定一种形式为标准型，以便于研究和求解。,（1）线性规划模型的标准型,如果在线性规划模型中，有,n,个决策变量,m,个约束条件，约束,条件为等式约束，决策变量非负，求目标函数的最小值，这种线性,规划模型就叫做标准型。其表达式为：,在标准型中，规定,否则等式两端乘以“-1”，其,矩阵形式为：,其中，,称为约束条件的系数矩阵，一般有,称为价值向量；向量,称为资源向量；,称为决策向量；,为零向量。,（2）任意一线性规划模型都可以化为标准型,若原模型要求目标函数实现最大化，即,则,即目标函数可化为,这就,与标准型的目标函数一致了。,若原模型中的约束条件为不等式，有两种情况：,若原模型中的约束条件为不等式：左端,右端，则在左端加,上“非负松弛变量”使不等式化为等式：左端+非负松弛变量=右端。,若原模型中的约束条件为不等式：左端,右端，则在左端减,去“非负松弛变量”使不等式化为等式：左端-非负松弛变量=右端。,例1将问题1的模型,化为标准型。,二、应用举例,1食谱问题,问题提出一饲养场饲养供实验用的动物，已知动物的生长对,饲料中的三种营养成分：蛋白质、矿物质和维生素特别敏感，每个,动物每天至少需要蛋白质克，矿物质克，维生素毫克。,该场能买到种饲料，各种饲料每千克的成本及所含营养成分如下,表所示，请确定既能满足动物需要，又使总成本最低的饲料配方。,饲料,成本（元）,蛋白质（克）,矿物质（克）,维生素（克）,0.2,0.30,0.10,0.05,0.7,2.00,0.05,0.10,0.4,1.00,0.02,0.02,0.3,0.60,0.20,0.20,0.5,1.80,0.05,0.08,设每个动物每天食用的混合饲料中所含的第,种饲料,的数量,为,千克，混合饲料的总成本为,z,则上述问题的数学模型为,连续投资问题,问题提出某部门在今后五年内考虑给下列四个项目投资，项,目，从第一年到第四年年初需要投资，并于次年末回收本利的,115%；项目，第三年年初需要投资，到第五年年末能回收本利,125%，但规定最大投资不超过万元；项目，第二年年初需要,投资，到第五年年末能回收本利140%，但规定最大投资不超过万,元；项目，五年内每年年初购买公债，于当年末归还，并加利息,6%。,该部门现有资金10万元，问如何分配这些项目每年的投资额，使,到第五年末拥有资金的本利总额最大？,问题分析,（）五年中每年年初该部门拥有的资金是变化的，设,表示第,i,年年初给第,j,项项目的投资额，显然,（）该部门每年的投资额等于部门年初所拥有的资金，下面,分年度讨论：,第一年，年初拥有资金万元，所以有,第二年，年初拥有资金仅为项目在第一年末回收的本息,所以有,第三年，年初拥有资金为,所以有,第四年，年初拥有资金为,所以有,第五年，年初拥有资金为,所以有,又，由题意知,目标函数：,模型建立,将上述分析整理，可得此问题的数学模型为：,3.,下料问题,问题的提出 计划做100套钢架,每套用长为2.9米、2.1米、1.5米,的圆钢各一根。设原材料长7.4米，问如何下料，才能使所用原料,最少？,分析 最简单的做法是在每一根原料上截取三种长度不同的,圆钢各一根组成一套，但浪费较大。若改为套截，则可节省原料。,8种套截方案如下表：,方案,配件,1,2,3,4,5,6,7,8,2.9,2,1,1,1,0,0,0,0,2.1,0,2,1,0,3,2,1,0,1.5,1,0,1,3,0,2,3,4,余料,0.1,0.3,0.9,0,1.1,0.2,0.8,1.4,设按第,i,种方案下料的原料根数为,表示总余料,则所求问题的数学模型为,注:该问题的数学模型的目标函数也可以为:,其中,表示使用原料总根数.,第二节 整数规划模型,在一般的线性规划模型中,再加上决策变量取整的条件,所得到的,一类规划问题称为整数线性规划.,问题1,货物托运问题,某公司拟用集装箱托运A,B两种货物，每箱的体积、重量、可,获得利润以及托运所受限制如下表所示。问两种货物各运多少箱,可获得最大利润？,货物,体积（立方米/箱）,重量（公斤/箱）,利润（元/箱）,A,5,100,2000,B,4,250,1000,托运限制,24,650,一、,整数规划模型,设,分别表示这两种货物的托运箱数，则该问题的数学模型,为：,一般地，某公司拟用集装箱托运,n,种货物,每箱的体积、,重量、可获得利润,以及托运所受限制为,V,和,M,，,问怎么装箱可获得最大利润？,问题2,分派问题,分配,n,个人去完成,n,项任务，第,i,个人完成第,j,项任务的效率为,每个人恰好完成一项任务，如何分配使总效率,最大？,设0-1变量,则此问题的,数学模型为,二、0-1,整数规划模型,0-1,整数规划模型是整数规划模型中的特殊情形，它的,决策变量,仅取0或1。这时,又叫0-1变量。,问题2,分派问题,就是,0-1,整数规划模型,问题3 选址问题,问题提出,某公司欲在城市的东、西、南三区建立门市部，拟,议中有7个位置,可供选择，规定,在东区，由,三个位置中至多选两个；,在西区，由,两个个位置中至少选一个；,在南区，由,两个个位置中至少选一个。,如果选用,则设备投资费用为,每年可获利润为,但投资总额不能超过,B,元，问应选择哪几个位置，可使年利润最大？,模型建立 首先引入0-1变量,则此问题的数学模型为,习题,1.某昼夜服务的公交线路每天各时间段内所需要司机和乘务员如,下表。设司机和乘务员分别在各时间区段一开始时上班，并连续工作,8小时。问该公交线路至少要配备多少司机和乘务员？,班次,时间段,所需人数,班次,时间段,所需人数,1,6:0010:00,60,4,18:0022:00,50,2,10:0014:00,70,5,22:002:00,20,3,14:0018:00,60,6,2:006:00,30,设每人每天只上一轮班(8小时),第,i,时间段开始时有,名人员上班,则,2.背包问题,一个旅行者必须决定在旅途中要携带哪些物品,才,能使携带的总重量不超过,b,公斤,以使总的“价值”最大,这样的问题称,为背包问题.设有,n,件物品,第,i,件物品的重量为,公斤,携带的“价值”,为,试建立背包问题的数学模型.,首先引入0-1变量,则此问题的数学模型为,3.比赛安排问题,已知下列5名运动员各种游泳项目的成绩(各,为50米)如下表所示,问如何从中选拔一个参加200米混合游泳的接,力队,使预期成绩最好.,项目,赵,钱,张,王,周,仰泳,37.3,32.9,33.8,37.0,35.4,蛙泳,43.4,33.1,42.2,34.7,41.8,蝶泳,33.3,28.5,38.9,30.4,33.6,自由泳,29.2,26.4,29.6,28.5,31.1,4.,加工任务安排,某工厂用,两台机床加工,三种,不同的零件.已知在一个生产周期内,只能工作80机时;,只能工作,100机时.一个生产周期内计划加工,三种不同的零件分别为:,70件、50件、20件。两台机床加工每个零件的时间和成本分别如下,表所示：,加工每个零件的时间（单位：机时/个）,零件,机床,1,2,3,1,1,3,加工每个零件的成本,（,单位：元/个）,零件,机床,2,3,5,3,3,6,问怎样安排两台机床一个周期的加工任务，才能是加工成本最低？,