第4章线性规划的基本概念及基本原理.pptVIP

线性规划的可行域是凸集 线性规划的最优解在极点上 * 武汉理工大学 能源与动力工程学院 优化技术基础 第1节 线性规划的基本概念及基本原理 第四章 线性规划 重点： 线性规划及解的概念，图解法，线性规划的基本定理 §1.1 线性规划所研究的问题 线性规划问题:在一组线性等式或不等式限制条件下,寻求一个线性函数的最大值或最小值问题. 例1 生产计划中的最优化问题 某厂生产两种型号机器，生产一台所需原材料分别为2和3个单位，所需工时分别为4和2个单位，而产值分别为6和4个单位，如果每天工厂能提供的原材料为100个单位，能提供的工时为120个单位，问这两种型号机器各生产多少台，能使产值最大？ 解:设生产两种型号机器A、B分别为x1、x2台，则限制条件为 2x1+3x2?100 （原材料限制） 4x1+2x2 ?120 （工时限制） x1、x2?0 （变量非限制） 要求：总产值最大，maxf(x1、x2)= 6x1+4x2 求出x1、x2的值 maxf(x1、x2) 两个变量的线性规划 例2 分配任务的最优化问题 现有四种不同规格的产品要分配在四台不同性能的机床上同时加工，由于产品的规格不同和机床的性能各异，因此每一件产品在不同机床上加工的工时定额是不同的，其工时定额如表，问应如何分配加工任务，使总的加工时间最少？ 16 43 27 48 4 42 25 16 21 3 35 40 13 20 2 1 16 50 7 1 4 3 2 1 产品 机床 工时 解:今要求四种产品同时在四台不同的机床上进行加工，因此每种产品只能而且必须分配在一台机床上，同时每台机床只能而且必须加工一种产品，所以这个问题属于任务分配问题 设 xij= 0 (表示产品j不分配在机床i上加工） 1 (表示产品j分配在机床i上加工） 则限制条件为 (第i台机床只加工一种产品) (第j种产品只在一台机床上加工) 总加工时间最少： 例３配料的最优化问题 现有４种标号的标准汽油，今用它们配制２种标号的飞机汽油，标准汽油的主要性能指标及库存量列于表1-2；飞机汽油的性能指标及生产的数量要求见表1-3，性能指标有辛烷数与蒸汽压。 130000 28.45*10-2 108.0 ４ 408100 5.69*10-2 87.0 ３ 265200 11.38*10-2 93.0 ２ 380000 7.11*10-2 107.5 １ 库存量,L 蒸汽压 (*0.1MPa) 辛烷数 标准 汽油 表1-2 表1-3 不少于250000 不大于9.96*10-2 不小于100.0 ２ 越多越好 不大于9.96*10-2 不小于91.0 １ 生产指标,L 蒸汽压 (*0.1MPa) 辛烷数 飞机 汽油 如何配制两种汽油，在保证飞机汽油性能指标和库存量的限制下，能使飞机汽油２号满足数量要求而飞机汽油１号的数量为最大？ 分析： 原料与产品之间有两方面的关系： １）产品所用原料数不应多于原料的库存量 ２）产品的性能指标与原料的性能指标之间的关系 产品的性能指标：质量守衡（容积数量） 原料的性能指标：物理、化学定律（分压定律） 辛烷值：汽油的点火性能 蒸汽压：汽油的安全使用 解：x1,x2,x3,x4分别为飞机汽油１中所用标准汽油１,２,３,４的体积数量，单位为Ｌ; x5,x6,x7,x8分别为飞机汽油２中所用标准汽油1,2,3,4的体积数量，单位为Ｌ 目的：飞机汽油１的总产量越多越好 　maxz= x1+x2+x3+x4 X5+x6+x7+x8≥250000(2号飞机汽油的生产指标限制) X1+x5≤380000(标准汽油1号的库存量限制) X2+x6≤265200 (标准汽油2号的库存量限制) X3+x7≤408100 (标准汽油3号的库存量限制) X4+x8≤130000 (标准汽油4号的库存量限制) xj≥0 j=1,2,…,8 (非负限制) 限制条件： 1、库存量和产量指标的限制 2、蒸汽压和辛烷值的限制条件 分压定律：设有一混合气体，由n种气体组成。令混合气体的压力为p，所站总容积为v；各组分的压力分别为p1,p2….pn,各组分所占容积分别为V1，V2，…..Vn,则“ ”， 利用分压定律建立蒸汽压力的限制条件： 根据表1-2，飞机汽油1的蒸汽压力应为： 根据表1-3，蒸汽压力不大于9.96*10-2 整理后得： 2.85x1-1.42x2+4.27x3-18.49x4≥0 (1号飞机汽油蒸汽压指标限制) 要求飞机汽油2的蒸汽压力与飞机汽油1的相同，则： 2.85x5-1.42x6+4.27x7-18.49x8≥0 (2号