线性规划的建模ppt课件.ppt

《线性规划的建模ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章线性规划引论◇学习重点1、线性规划问题的建模及图解法(熟练掌握)2、非标准形LP化成标准形(重点.后续内容学习的基础）第一节线性规划问题及其数学模型线性规划概论：线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。解决两类问题：1、如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。2、如何合理使用人力，物力和资金，以达到最经济的方式，完成生产计划的要求。1.1线性规划问题的实例例1资源的合理利用问题某厂计划在一个生产周期内生产甲，乙

2、两种产品，要消耗和三种资源，已知每件产品对这三种资源的消耗，这三种资源的现有数量和每件产品可获得的利润如表1-1所示。问如何安排生产计划，使得即能充分利用资源，又使总利润最大？单件产品消耗资源甲乙资源限制522315170100150单件利润1018表1-1解：将这么一个实际问题转化为线性规划模型，它需要有以下几个步骤：1．确定决策变量：x1=生产甲产品的数量x2=生产乙产品的数量2．确定约束条件：5x1+2x2170（A1资源的限制）2x1+3x2100（A2资源的限制）x1+5x215

3、0（A3资源的限制）变量取值限制：一般情况，决策变量只取正值（非负值）x10,x203．确定目标函数：工厂的目标是总利润最大maxz=10x1+18x2得到该问题的数学模型为：maxz=10x1+18x25x1+2x2170s.t.2x1+3x2100x1+5x2150x1,x20线性规划数学模型三要素：决策变量、目标函数、约束条件例2营养配餐问题假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择，它们每千克所含的热量和

4、营养成分和市场价格见下表。问如何选择才能在满足营养的前提下使购买食品的费用最小？表1.2（各种食物的营养成分表）解：设xj为第j种食品每天的购入量，则配餐问题的线性规划模型为：(x1—猪肉,x2—鸡蛋,x3—大米,x4—白菜)minZ=14x1+6x2+3x3+2x4s.t.1000x1+800x2+900x3+200x4300050x1+60x2+20x3+10x455400x1+200x2+300x3+500x4800x1，x2，x3，x40例3生产组织与计划问题；某工厂拥有A、B、

5、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的机时数如下表所示：甲乙机时数设备A3265设备B2140设备C0375利润（元/件）15002500表1.3问题：工厂应如何安排生产可获得最大的总利润？解：设变量xi为第i种（甲、乙）产品的生产件数（i＝1，2）。根据题意，我们知道两种产品的生产受到设备能力（机时数）的限制。对设备A，两种产品生产所占用的机时数不能超过65，于是我们可以得到不等式：3x1+2x2≤65；对设备B，

6、两种产品生产所占用的机时数不能超过40，于是我们可以得到不等式：2x1+x2≤40；对设备C，两种产品生产所占用的机时数不能超过75，于是我们可以得到不等式：3x2≤75；另外，产品数不可能为负，即x1,x2≥0。同时，我们有一个追求目标，即获取最大利润。于是可写出目标函数z为相应的生产计划可以获得的总利润：z=1500x1+2500x2。综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型：目标函数maxz=1500x1+250

7、0x2约束条件s.t.3x1+2x2≤652x1+x2≤403x2≤75x1,x2≥0例1.4合理下料问题假定现有一批某种型号的圆钢长8m，需要截取长2.5m的毛坯100根、长1.3m的毛坯200根，问应该怎样选择下料方式。才能既满足需要，又使总的用料最少？根据经验，我们可先将各种可能的搭配方案列表如下：P11方案下料件数毛坯型号ⅠⅡⅢⅣ需要根数2.5m32101001.3m0246200表1.4设决策变量xj(j=1,2,3,4)表示第j种方式所用的原料根数，则问题的数学模型可归结为：求xj(

8、j=1,2,3,4)，使得minZ=x1+x2+x3+x43x1+2x2+x3100s.t.2x2+4x3+6x4200xj0(j=1,2,3,4)例1.5运输问题某物流公司需将甲、乙、丙三个工厂生产的一种新产品运送到A、B两个仓库，甲、乙两个工厂的产品可以通过铁路运送到仓库A，数量不限；丙工厂的产品可以通过铁路运送到仓库B，同样，产品数量不限。由于铁路运输成本较高，公司也可考虑由独立的卡车来运输，可将多达80个单位的产品由甲、乙、丙三个工厂运到一个配送中心，再从配送中心以最多90单位的载