《线性规划的应用上机操作教学PPT.ppt》由会员分享，可在线阅读，更多相关《线性规划的应用上机操作教学PPT.ppt（39页珍藏版）》请在三一办公上搜索。
1、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,该例还可以采用另外的目标函
2、数，即100套钢架的料头总长度为 y 米。数学模型是：,注意“=”要改为“=”,6,7,8,输入数据,9,10,第四节、线性规划的应用,11,例1 载货问题：有一艘货轮，分前、中、后三个舱位，它们的容积与最大允许载重量如下面表所示。,现有三种货物待运，已知有关数据列于下面表。,为了航运安全，要求前、中、后舱在实际载重量上大体保持各舱最大允许载重量的比例关系。具体要求前、后舱分别与中舱之间载重量比例上偏差不超过 15%，前、后舱之间不超过 10%。问该货轮应装载 A、B、C各多少件，运费收入为最大？,12,(2)确定目标函数 商品 A 的件数为：x11+x12+x13，即装于货轮前、中、后舱商品
3、 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)确定约束条件,
4、A、B、C 三种商品数量限制为：x11+x12+x13 600 x21+x22+x23 1000 x31+x32+x33 800,前、中、后舱位体积限制为：10 x11+5x21+7x31 4000 10 x12+5x22+7x32 5400 10 x13+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。综上所述，该问题的线性规划模型如下：,根据各舱实际载重量大体应保持各舱最大允许载重量的比例关系，且前、后舱分别与中
5、舱之间载重量比例上偏差不超过 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
6、个月的仓库面积,19,例3、合金的添加优化问题 某特钢公司炼钢厂用电炉冶炼特种钢，其钢种数目达数百个之多，这些特殊钢所含的元素少的有六七种，多的达十一种。这些元素通常是由各种铁合金提供，即在钢水中添加适量的各种铁合金，使炼成的钢符合各个钢种的要求，一般说来，在添加各种铁合金之前，钢水中的各种元素的含量低于规格要求，因此添加各种铁合金多少，向来是工程技术人员的一个难题。该厂过去一直沿用“经验估计法”来调整各种元素的含量，质量不稳定，还经常发生报废现象；而且为了某些主要元素含量偏低，往往将某些元素加到上限，而铁合金是一种价格昂贵的材料，这无形提高了钢的成本。为了提高钢的质量，降低生产成本，我们必须
7、采用线性规划模型来解决这类问题。已知下列数据：(1)钢水的重量：W(2)钢水中各种受控元素为 M 个，目前，在钢水的含量为：b1,bm（%）(3)钢的规格要求：各种元素最低不得低于：a1,am 不得高于：c1,cm(4)现有 n 种铁合金，它们各种元素的含量及价格如下表：,20,21,例4、生产存贮问题 一个合资食品企业面临某种食品一至四月的生产计划问题。四个月的需求分别为4500吨、3000吨、5500吨、4000吨。目前（一月初）该企业有100个熟练工人，正常工作时每人每月可以完成40吨，每吨成本200元。由于市场需求浮动较大，该企业可通过以下方法调节生产：（1）利用加班增加生产，但加班生
8、产每人每月不能超过10吨，其成本为300元/吨。（2）利用库存来调节，库存费用为60元/吨/月，最大库存能力为1000吨。请为该企业构造一个线性规划模型，在满足需求的前提下使四个月总费用为最小。假定该企业在一月初的库存为0，要求四月底库存为500吨。,22,23,例5、配料问题 绿色饲料公司生产雏鸡、蛋鸡、肉鸡三种饲料，三种饲料由A、B、C三种原料混合而成，产品规格要求、产品单价、产品日销售量、原料单价见下表：,受资金及生产能力限制，每天只能生产30吨，问如何安排生产，获利最大？,24,例6、工厂选址问题 有A、B、C三个原料产地，其原料要在工厂加工，制成成品，再在销售地出售，A、B两地又是销
9、售地，已知有关数据如下：,其中：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+X
10、21+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万元。现在该机构准
11、备了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,目标函数：
12、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,约束条
13、件：,(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
14、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+10 x33+4x41+5x42+3x43+1000000u+1200000v,本数学模型属于混合整数线性规划,38,例9：一个
15、公司考虑到北京、上海、广州和武汉四个城市设立库房，这些库房负责向：华北、华中、华南三个地区供货，每个库房每月可处理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地发送的货物量。j=1,2,3 Min z=45000*Y1+50000*Y2+70000*Y3+40000*Y4+CijXij（Cij：第i地向第j地发送的货物的单位成本）X11+X12+X13=1000*Y1 X21+X22+X23=1000*Y2 X31+X32+X33=1000*Y3 X41+X42+X43=1000*Y4 X11+X21+X31+X41=500 X12+X22+X32+X42=800 X13+X23+X33+X43=700 Y2=Y4 Y1+Y2+Y3+Y4=2 Y3+Y4=1,
