线性规划的应用上机操作教学PPT.ppt

1,线性规划的上机操作,2,例 某工厂准备做100套钢架，每套钢架均由长为2.9米、2.1米和1.5米的钢管各一根所组成，已知原料长7.4米，如何下料方能使原料最省？,解：原料的下料方式如下表。,3,设按照方式 aj下料的原料有 xj 根（j =1，8）；所用原料为 y 根。于是，该下料问题的数学模型是：,4,采取单纯形法来求解。可知最优解（x1，x2，x3，x4，x5，x6，x7，x8）=（40，20，0，0，0，30，0， 0）。这表明，只须采用下料方式a1 、a2 和 a6，而且所用原料分别为40根、20根和30根，可使所用原料最省。,放宽:得到相应线性规划为：,5,该例还可以采用另外的目标函数，即100套钢架的料头总长度为 y 米。数学模型是：,注意“=”要改为“=”,6,7,8,输入数据,9,10,第四节、线性规划的应用,11,例1 载货问题：有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如下面表所示。,现有三种货物待运，已知有关数据列于下面表。,为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间载重量比例上偏差不超过 15%，前、后舱之间不超过 10%。问该货轮应装载 a、b、c各多少件，运费收入为最大？,12,(2) 确定目标函数 商品 a 的件数为：x11 + x12 + x13，即装于货轮前、中、后舱商品 a 的件数之和； 商品 b 的件数为：x21 + x22 + x23，即装于货轮前、中、后舱商品 b 的件数之和； 商品 c 的件数为：x31 + x32 + x33，即装于货轮前、中、后舱商品 c 的件数之和。 为使运费总收入最大，目标函数为 max z = 1000(x11 + x12 + x13) + 700(x21 + x22 + x23) + 600(x31 + x32 + x33),解：(1) 确定决策变量 因为a、b、c三种商品在货轮的前、中、后舱均可装载，令 i = 1, 2, 3 分别代表商品 a、b、c，用 j = 1, 2, 3 分别代表前、中、后舱。设决策变量 xij 为装于 j 舱位的第 i 种商品的数量（件）。,13,(3) 确定约束条件,a、b、c 三种商品数量限制为： x11 + x12 + x13 600 x21 + x22 + x23 1000 x31 + x32 + x33 800,前、中、后舱位体积限制为： 10x11 + 5x21 + 7x31 4000 10x12 + 5x22 + 7x32 5400 10x13 + 6x23 + 7x33 1500,前、中、后舱位载重量限制为： 8x11 + 6x21 + 5x31 2000 8x12 + 6x22 + 5x32 3000 8x13 + 6x23 + 5x33 1500,14,xij 0，i = 1, 2, 3，j = 1, 2, 3。 综上所述，该问题的线性规划模型如下：,根据各舱实际载重量大体应保持各舱最大允许载重量的比例关系，且前、后舱分别与中舱之间载重量比例上偏差不超过 15%，前、后舱之间不超过 10%，可得舱体平衡条件为：,15,16,最后解得： x11 = 206.7722，x12 = 318.2278， x13 = 75， x21 = 0， x22 = 0， x23 = 150， x31 = 69.1646， x32 = 90.8354， x33 = 0； 总费用为：8.01105。,17,例2：库存问题 某公司在今后四个月内需租用仓库堆放物资。已知各月所需仓库面积如下：,该厂根据需要，在各月初办理租借合同，可同时签订不同面积、不同期限的合同。请制定一个费用最小的租借方案。,仓库租借费用，与租借合同期限有关，越长则折扣越大，具体如下：,18,决策变量xij: 第i月租借期限为j个月的仓库面积,19,例3、合金的添加优化问题 某特钢公司炼钢厂用电炉冶炼特种钢，其钢种数目达数百个之多，这些特殊钢所含的元素少的有六七种，多的达十一种。这些元素通常是由各种铁合金提供，即在钢水中添加适量的各种铁合金，使炼成的钢符合各个钢种的要求，一般说来，在添加各种铁合金之前，钢水中的各种元素的含量低于规格要求，因此添加各种铁合金多少，向来是工程技术人员的一个难题。 该厂过去一直沿用“经验估计法”来调整各种元素的含量，质量不稳定，还经常发生报废现象；而且为了某些主要元素含量偏低，往往将某些元素加到上限，而铁合金是一种价格昂贵的材料，这无形提高了钢的成本。 为了提高钢的质量，降低生产成本，我们必须采用线性规划模型来解决这类问题。 已知下列数据： (1)钢水的重量：w (2)钢水中各种受控元素为 m 个，目前，在钢水的含量为：b1,bm（%） (3)钢的规格要求：各种元素最低不得低于：a1,am 不得高于：c1,cm (4)现有 n 种铁合金，它们各种元素的含量及价格如下表：,20,21,例4、生产存贮问题 一个合资食品企业面临某种食品一至四月的生产计划问题。四个月的需求分别为4500吨、3000吨、5500吨、4000吨。目前（一月初）该企业有100个熟练工人，正常工作时每人每月可以完成40吨，每吨成本200元。由于市场需求浮动较大，该企业可通过以下方法调节生产： （1）利用加班增加生产，但加班生产每人每月不能超过10吨，其成本为300元/吨。 （2）利用库存来调节，库存费用为60元/吨/月，最大库存能力为1000吨。 请为该企业构造一个线性规划模型，在满足需求的前提下使四个月总费用为最小。 假定该企业在一月初的库存为0，要求四月底库存为500吨。,22,23,例5、配料问题 绿色饲料公司生产雏鸡、蛋鸡、肉鸡三种饲料，三种饲料由a、b、c三种原料混合而成，产品规格要求、产品单价、产品日销售量、原料单价见下表：,受资金及生产能力限制，每天只能生产30吨，问如何安排生产，获利最大？,24,例6、工厂选址问题 有a、b、c三个原料产地，其原料要在工厂加工，制成成品，再在销售地出售，a、b两地又是销售地，已知有关数据如下：,其中：4吨原料制成1吨成品，原料运费每百公里300元，成品运费每百公里200元。如在b地设加工厂，每年产成品不能超过5万吨，a、c设厂，则不受限制。问应在哪建厂，总费用（为简化问题，在这只包括产品加工费、运费）最低？,25,表中出现了x12、x21是否矛盾？,26,min z =5.5*(y11+y12)+ 4*(y21+y22)+ 3*(y31+y32) +0.3*1.5*(x12+x21)+ 1.0*(x13+x31) +2.0*(x23+x32) +0.2*1.5*(y12+y21) +1.0* y31+ 2.0* y32,第一类约束条件： 原材料的运输数量是成品数量的4倍 a：30+x21+x31-x12-x13 = 4*（y11+y12） b：26+x12+x32-x21-x23 = 4*（y21+y22） c：24+x13+x23-x31-x32 = 4*（y31+y32）,27,28,例7：投资计划问题,某投资机构在今后3年内有4种投资机会： 1、在3年内每年年初投资，年底可获利润20%，并可将本金 收回。 2、在第一年年初投资，第二年年底可获利50%，并可将本金 收回，但该项投资金额不超过200万元。 3、在第二年年初投资，第三年年底收回本金，可获利60%， 但该项投资金额不超过150万元。 4、在第三年年初投资，第三年年底收回本金，并获利40%， 但该项投资金额不超过100万元。 现在该机构准备了300万元资金，如何制定投资方案，使到第三年年末本利和最大。,29,30,例8：某医药公司现有两个制药厂a1和a2，三个销售点b1、b2 和 b3。由于供不应求，公司打算由两个拟建的制药厂a3 和 a4 中选择一个来兴建新厂。新厂投产后，估计每月的固定成本：a3 是100万元，a4 是120万元。各销售点每月药品需求量、各制药厂每月药品产量和每箱药品运费见下。在两个拟建的制药厂中，应当选择哪个，使总成本最低（建立数学模型）？,31,设：,解：建立数学模型,xij: 制药厂ai 每月运到销售点bj 的药品箱数（i =1,2，3，4； j =1，2，3）,0-1型整数变量,纯整数变量,32,目标函数： min z= 3x11 + 2x12 + 3x13 （a1每月的运费） + 10x21 + 5x22 + 8x23 （a2每月的运费） + x31 + 3x32 + 10x33 （a3每月的运费） + 4x41 + 5x42 + 3x43 （a4每月的运费） + 1000000 （a3每月的固定成本） + 1200000 （a4每月的固定成本）,33,目标函数： min z= 3x11 + 2x12 + 3x13 （a1每月的运费） + 10x21 + 5x22 + 8x23 （a2每月的运费） + x31 + 3x32 + 10x33 （a3每月的运费） + 4x41 + 5x42 + 3x43 （a4每月的运费） + 1000000 u （a3每月的固定成本） + 1200000 v （a4每月的固定成本）,34,约束条件：,(1) u 和 v 全是 01 变量：,(2) 由 a3 和 a4 选择一个来兴建新厂：,u + v =1,(3) 每个制药厂每周运到各销售店的药品不会超过其产量：,x11 + x 12 + x13 500000 x21 + x 22 + x23 700000 x31 + x 32 + x33 200000 x41 + x 42 + x43 200000,u ， v =0，1,35,约束条件：,(1) u 和 v 全是 01 变量：,(2) 由 a3 和 a4 选择一个来兴建新厂：,u + v =1,(3) 每个制药厂每周运到各销售店的药品不会超过其产量：,x11 + x 12 + x13 500000 x21 + x 22 + x23 700000 x31 + x 32 + x33 200000 u x41 + x 42 + x43 200000 v,u ， v =0，1,36,(4) 每个销售店每周药品的需求量能够得到各制药厂的充分供应：,（5）药品箱数一定取非负整数：,xij 0，且为整数,x11 + x21 + x31 + x41 = 500000 x12 + x22 + x32 + x42 = 600000 x13 + x23 + x33 + x43 = 300000,37,例1的数学模型为：,min z = 3x11 + 2x12 + 3x13 + 10 x21 + 5x22 + 8x23+ x31 + 3x32 +10x33+ 4x41 + 5x42 + 3x43+1000000u+1200000v,本数学模型属于混合整数线性规划,38,例9：一个公司考虑到北京、上海、广州和武汉四个城市设立库房，这些库房负责向：华北、华中、华南三个地区供货，每个库房每月可处理1000件。在北京设库房每月成本为4.5万元，上海为5万元，广州为7万元，武汉为4万元，每个地区的月平均需求量为：华北每月500件，华中每月800件，华南每月700件。发运货物的费用（元/件）见下表： 公司要求在满足地区需求的条件下使平均月成本为最小，且还要求满足以下条件： （1）在上海设库房，则必须也在武汉设库房。 （2）最多设两个库房。 （3）武汉和广州不能同时设库房。 请写一个满足上述要求的整数规划数学模型。,39,设 yi= 1 表示在i地建厂 0 表示在i地不建厂 i=1，2，3，4 即：北京、上海、广州、武汉 xij：第i地向第j地发送