第四章数学规划模型习题解答.doc

萧澜 1题： 污水处理问题问题的提出如下图，有若干工厂的污水经排污口流入某江，各口有污水处理站，处理站对面是居民点。工厂1上游江水流量和污水浓度，国家标准规定的水的污染浓度，以及各个工厂的污水流量和污水浓度均已知道。设污水处理费用与污水处理前后的浓度差和污水流量成正比，使每单位流量的污水下降一个浓度单位需要的处理费用为已知。处理后的污水与江水混合，流到下一个排污口之前，自然状态下的江水也会使污水浓度降低一个比例系数，该系数可以估计。试确定各污水处理站出口的污水浓度，使在符合国家标准规定的条件下总的处理费用最小。 工厂1 工厂2 工厂3 处理站1 处理站2 处理站3 江水 居民点1 居民点2 居民点3先建立一般的数学模型，再求解以下的具体问题：设上游江水流量为10001012l/min，污水浓度为0.8mg/l，三个工厂的污水流量均为51012l/min，污水浓度（从上游到下游排列）分别为100，60，50（mg/l），处理系数均为1万元/（1012 l/min）(1mg/l)），3个工厂之间的两段江面的自净系数（从上游到下游）分别为0.9，0.6。国家标准规定的污染浓度不超过1mg/l。（1）为了使江面上所有地段的水污染达到国家标准，最少需要花费多少费用？（2）如果只要求三个居民点上游的水污染达到国家标准，最少需要花费多少费问题的解决解：设有n个工厂和n个污水处理站,以处理站的出口向上游划分江面,，以处理站出口向上游划分江面，如下图。记第k段江面的流量和污水浓度分别为 Qk和Ck，工厂k和处理站k流出的污水流量相同，均为*Qk，而污水浓度分别为uk,vk ，处理站k的处理系数为 rk，第k段江面的自净系数为 bk，通常 *Qk远小于Qk ，当没有其它水源入江时，可视 Qk为常数Q，国家标准规定的水的污染浓度为C0 。以上参数中Q， C0，C1 ，*Qk ，uk ， rk，bk 已知，vk 为决策变量。在Qk 简化为常数Q的情况下，处理站k的污水与江水混合后的污水浓度为Dk=Ck+(*Qk/Q)*vk，第k段江面自净后的污水浓度为Ck+1=bkDk ，处理站k的处理费用为 rk*Qk(uk-vk)，于是在江面上所有地段的水污染达到国家标准的条件下，把具体问题数据 Q=1000*1012L/min， C1=0.8mg/l， C0=1mg/l，*Q1=*Q2=*Q3=5*1012L/min,u1=100,u2=60,u3=50mg/l,r1=r2=r3=1万元/(1012L/min)*(mg/l) ,b1=0.9,b2=0.6经手工代入使总费用最小的模型为： Min 5u1-5v1+5u2-5v2+5u3-5v3st 0.005v1=0.20.0045v1+0.005v2=0.280.003v1+0.003v2+0.005v3=0.578v1=100v2=60v3=50u1=100u2=60u3=50endLP OPTIMUM FOUND AT STEP 4OBJECTIVE FUNCTION VALUE1) 500.0000VARIABLE VALUE REDUCED COSTU1 100.000000 0.000000V1 40.000000 0.000000U2 60.000000 0.000000V2 20.000002 0.000000U3 50.000000 0.000000V3 50.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 100.0000233) 0.000000 1000.0000004) 0.148000 0.0000005) 60.000000 0.0000006) 40.000000 0.0000007) 0.000000 5.0000008) 0.000000 -5.0000009) 0.000000 -5.00000010) 0.000000 -5.000000NO. ITERATIONS= 4Min 5u1-5v1+5u2-5v2+5u3-5v3st 0.0045v1=0.280.003v1+0.003v2=0.578u1=100u2=60u3=50v1=100v2=60v3=50endLP OPTIMUM FOUND AT STEP 0OBJECTIVE FUNCTION VALUE1) 188.8889VARIABLE VALUE REDUCED COSTU1 100.000000 0.000000V1 62.222225 0.000000U2 60.000000 0.000000V2 60.000000 0.000000U3 50.000000 0.000000V3 50.000000 0.000000ROW SLACK OR SURPLUS DUAL PRICES2) 0.000000 1111.1112063) 0.211333 0.0000004) 37.777775 0.0000005) 0.000000 5.0000006) 0.000000 5.0000007) 0.000000 -5.0000008) 0.000000 -5.0000009) 0.000000 -5.000000NO. ITERATIONS= 0 11 题目： 有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且有允许插队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）： 秘书初试 主管复试 经理面试 同学甲 13 15 20 同学乙 10 20 18 同学丙 20 16 10 同学丁 8 10 15这4名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8：00，问他们最早何时能离开公司？模型分析:由此题可以得知要想最早得时间离开公司必定是求最小值,而又要保证一起离开,那么每一个阶段得时间又要取最大值,故我们可确定目标函数.模型建立:记为第名同学参加第阶段的面试所需要的时间(已知),令表示第名同学参加第阶段的面试的开始时间(不妨令早上8:00面试开始的时间为0时刻)目标函数: Min 约束条件:1）时间先后次序的约束(每个人只有参加完前一个阶段的面试后才能进入下一个阶段): 2）每一个阶段同一时间只能面试一名同学:用01变量表示第名同学是否排在第名同学的前面(1表示是,0表示否),则 那么我们可以将目标函数改写为: Min T s.t. 加上约束条件1），2），用Lingo求解得到：Lingo语言程序:model:min T； ； end所得的结果:Local optimal solution found at iteration: 4357Objective value: 84.00000 Variable Value Reduced Cost T 84.00000 0.000000 36.00000 0.000000 20.00000 0.000000 56.00000 0.000000 18.00000 0.000000 74.00000 0.000000 10.00000 0.000000 21.00000 0.000000 15.00000 0.000000 8.000000 0.000000 13.00000 0.000000 21.00000 0.000000 10.00000 0.000000 36.00000 0.000000 20.00000 0.000000 37.50000 0.000000 20.00000 0.000000 57.75000 0.000000 16.00000 0.000000 0.000000 0.9999970 8.000000 0.000000 11.00000 0.000000 10.00000 0.000000 0.000000 -83.99950 0.000000 0.000000 1.000000 83.99950 0.000000 -83.99950 1.000000 0.000000 1.000000 0.000000那么可以得到甲乙丙丁要完成所有得面试至少要84分钟.面试的顺序为:4123 即丁甲乙丙.1题目:某公司将4 种不同含硫量的液体原料（分别记为甲,乙,丙,丁）混合生产两种产品（分别记为A B）.按照生产工艺的要求，原料甲,乙,丁必须首先倒入混合池中混合，混合后的液体再分别与原料丙混合生产A,B。已知原料甲,乙,丙,丁的含硫量分别是3,1,2,1（%）。进货价格分别为6,16,10,15（千元/吨）；产品A,B的含硫量分别不能超过2.5,1.5（%），售价分别为9,15（千元/吨），根据市场信息，原料甲,乙,丙的供应没有限制，原料丁的供应量最多为50吨；产品A,B的市场需求分别为100吨,200吨.问应如何安排生产?一、 模型假设:1. 设y1,z1分别为产品A中来自混合池和原料丙的吨数.2. 设y2,z2分别是产品B中来自混合池和原料丙的吨数.3. 设混合池原料甲,乙,丁所占比例为x1,x2,x4.二、 模型建立:Max (96x116x215x4)y1(156x116x215x4)y2(916x2)z2s.t x4(y1y2)=50 y1z1=100 y2z2=200 (3x1x2x42.5)y1-0.5z1=0 (3x1x2x41.5)y2+0.5z2=0三、 模型求解:输入LINGO软件如下:Model:Max=(96x116x215x4)y1(156x116x215x4)y2(916x2)z2;x4(y1y2)=50;y1z1=100;y2z2=200; (3x1x2x42.5)y1-0.5z1=0;(3x1x2x41.5)y2+0.5z2=0;x2=0;x4=0;y1=0;y2=0;z1=0;z2=0;endx1=0,x2=x4=0.5,y1=0,y2=z2=100,max=450.另解：某公司将4种不同含硫量的液体原料（分别记为甲、乙、丙、丁）混合生产两种产品（分别记为A，B）。按照生产工艺的要求，原料甲、乙、丁、必须倒入混合池中混合，混合后的液体再分别与原料丙混合生产A，B。已知原料甲、乙、丙、丁的含硫量分别是3，1，2，1（%），进货价格分别为6，16，10，15（千元/吨）；产品A，B的含硫量分别不能超过 2.5，1.5（%），售价分别为9，15（千元/吨）。根据市场信息，原料甲、乙、丙的供应没有限制，原料丁的供应量最多为50吨；产品A，B的市场需求量分别为100吨、200吨。问应如何安排生产？一、 模型假设1、 设在整个生产过程中所有原料没有损失，即质量守恒。2、 设在生产过程中硫的含量也没有任何的损失。3、 没有其它因素的影响。二、 变量假设X 生产中需要甲原料的吨数。X 生产中需要乙原料的吨数。Y 生产A过程中需要丙原料的吨数。Y 生产B过程中需要丙原料的吨数。X 生产中需要丁原料的吨数。X 甲、乙、丁的混合液中用于生产A的吨数。X 甲、乙、丁的混合液中用于生产B的吨数。 生产过程产生的利润。三、 模型分析本题是一个生产的最优安排问题，利用有限的资源生产出最大的利润。我们可以知道生产中产生的A为X+ Y，生产的B为X+ Y，我们从题目中可以寻找一些约束限制：1、 原料限制问题，由于生产过程中原料甲、乙、丙的供应没有限制，原料丁的供应量最多为50吨所以要求：2、 含硫量的限制，由于产品A，B的含硫量分别不能超过 2.5，1.5（%）。生产中A的含硫吨数为：，生产中B的含硫吨数为：，所以 X+ Y 0.025； X+ Y 0.015；3、 生产中质量守恒的原则即用与生产A和B的混合液不能超过混合池中混合液的总量表示为数学表达式为：X+X4、 为了使生产中利润最大化不能使生产的产量超过市场的需求即： X+ Y100； X+ Y200； 此时产生的利润为销售总额减去生产成本 四、 建立模型目标函数为：MAX 约束条件为： X+ Y 0.025； X+ Y 0.015； X+X X+ Y100； X+ Y200； 8题：某电力公司经营两座发电站,发电站分别位于两个水库上,位置如下图所示 水源B.水源A水库A发电站A水库B发电站B已知发电站A可以将水库A的1万M3的水转换为400千度的电能，发电站B只能将水库B的1万M3的水转换为200千度的电能，发电站A，B每月最大发电能力分别为60000千度，35000千度，每月最多有50000千度电能够以200元/千度的价格出售，多余的电能只能够以140元/千度的价格出售。水库A，B的其他有关数据如下（单位：万立方米）水库A水库B水源流入水量本月20040下月13015水库最大畜水量20001500水库最小畜水量1200800本月目前畜水量1900850请您为该公司制订本月和下月的生产经营计划。解：假设水源流入水量是每个月开始发生的，根据题中的数据，水库中的水应允许不发电而直接放走。假设XA1,XA2，XB1，XB2分别为本月从水库和下月从水库A，B直接放走的水量。ZA1，ZA2，ZB1，ZB2分别为本月和下月结束时水库A，B的水量。用U1，U2分别表示本月和下月以高价（200元/千度）售出的电量，V1，V2分别表示本月和下月以低价（140元/千度）售出的电量优化目标为 Max 200(U1+U2)+140(V1+V2)约束条件为 （1） 每个月的发电量等于当月卖出的电量 400XA1+200XB1=U1+V1 400XA2+200XB2=U2+V2（2） 水量守恒约束：XA1+YA1+ZA1=1900+200XB1+YB1+ZB1=850+40+XA1+YA1XA2+YA2+ZA2=ZA1+130XB2+YB2+ZB2=ZB2+15+XA2+YA2（3） 发电能力限制： 400XA160000，400XA260000200XB135000，200XB135000（4） 水库蓄水限制： 1200ZA12000，1200ZA22000800ZB11500，800ZB21500（5） 高价电量的限制： U150000，U250000 注意到总发电量中尽量以高价卖出，以上约束可以保证只有U1=50000时，才可能有U10。只有U2=50000时才可能有U20。 用LINEDO求解得： OBJECTIVE FUNCTION VALUE 0.5276000E+0.8UARIABLE VALUE REDUCEDCOST U1 50000.000000 0.000000 U2 50000.000000 0.000000 V1 45000.000000 0.000000 V2 18900.000000 0.000000 XA1 150.000000 0.000000 XB1 175.000000 0.000000 XA2 150.000000 0.000000 XB2 895.000000 0.000000 YA1 0.000000 28000.000000 ZA1 1950.000000 0.000000 YB1 65.000000 0.000000 ZB1 800.000000 0.000000 YA2 730.000000 0.000000 ZA2 1200.000000 0.000000 YB2 0.000000 28000.000000 ZB2 800.000000即水库A供应电站A发电的水量本月和下月均为150万m3,水库B供应电站B发电的水量本月和下月分别为175万m3和895万m3。本月和下月以高价售出电量均为50000千度，本月和下月以低价售出的电量分别为45000和189000千度，总收入527.6105元。11题目：有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）。由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如下表所示（单位：分钟）：秘书初试主管复试经理面试同学甲131520同学乙102018同学丙201610同学丁81015这四名同学约定他们全部面试完以后一起离开公司。假定现在时间是早晨8：00，问他们最早何时能离开公司？建立模型：记为第i名同学参加第j阶段面试需要的时间，令表示第名同学参加第阶段面试的开始时刻（记早上8：00面试开始为0时刻）（=1,2,3,4;=1,2,3）.优化目标为 约束条件：1 时间先后次序约束（每人只有参加完前一个阶段的面试后才能进入下一个阶段）： (=1,2,3,4;=1,2,)2)每个阶段同一时间只能面试1名同学：用01变量表示第名同学是否排在第名同学前面（1表示是，0表示否），则 (,=1,2,3;=1,2,3；) (，=1,2,3;=1,2,3;)则目标函数为： (=1,2,3,4;=1,2,) (,=1,2,3;=1,2,3;) (,=1,2,3;=1,2,3;)模型求解：本问题是一个排列排序问题。对于阶段数不小于3的问题没有有效算法，也就是说对于学生数稍多一点儿（比如20）的情况是无法精确求解的。为此人们找到了很多近似算法。这里我们建立的规划模型可以实现该问题的精确求解，但你会看到它的变量和约束是学生数的平方。因此，当学生数稍多一点儿规划模型的规模经很大，求解会花费很长时间。程序如下：!三阶段面试模型;model:sets: students; !学生集三阶段面试模型; phases; !阶段集; sp(students,phases):t,x; ss(students,students) | &1 #LT# &2:y;endsetsdata: students = s1.s4; phases = p1.p3; t= 13 15 20 10 20 18 20 16 10 8 10 15; enddata ns=size(students); !学生数; np=size(phases); !阶段数; !单个学生面试时间先后次序的约束; for(sp(I,J) | J #LT# np: x(I,J)+t(I,J)=x(I,J+1) ); !学生间的面试先后次序保持不变的约束; for(ss(I,K): for(phases(J): x(I,J)+t(I,J)-x(K,J)=200*y(I,K); x(K,J)+t(K,J)-x(I,J)=200*(1-y(I,K); ) ); !目标函数; min=TMAX; for(students(I): x(I,3)+t(I,3)=TMAX ); !把Y定义0-1变量; for(ss: bin(y);end计算的部分结果为：Global optimal solution found at iteration: 896 Objective value: 84.00000 Variable Value Reduced Cost NS 4.000000 0.000000 NP 3.000000 0.000000 TMAX 84.00000 0.000000 T( S1, P1) 13.00000 0.000000 T( S1, P2) 15.00000 0.000000 T( S1, P3) 20.00000 0.000000 T( S2, P1) 10.00000 0.000000 T( S2, P2) 20.00000 0.000000 T( S2, P3) 18.00000 0.000000 T( S3, P1) 20.00000 0.000000 T( S3, P2) 16.00000 0.000000 T( S3, P3) 10.00000 0.000000 T( S4, P1) 8.000000 0.000000 T( S4, P2) 10.00000 0.000000 T( S4, P3) 15.00000 0.000000 X( S1, P1) 8.000000 0.000000 X( S1, P2) 21.00000 0.000000 X( S1, P3) 36.00000 0.000000 X( S2, P1) 21.00000 0.000000 X( S2, P2) 36.00000 0.000000 X( S2, P3) 56.00000 0.000000 X( S3, P1) 31.00000 0.000000 X( S3, P2) 56.00000 0.000000 X( S3, P3) 74.00000 0.000000 X( S4, P1) 0.000000 1.000000 X( S4, P2) 8.000000 0.000000 X( S4, P3) 18.00000 0.000000 Y( S1, S2) 0.000000 -200.0000 Y( S1, S3) 0.000000 0.000000 Y( S1, S4) 1.000000 200.0000 Y( S2, S3) 0.000000 -200.0000 Y( S2, S4) 1.000000 0.000000 Y( S3, S4) 1.000000 0.000000 Row Slack or Surplus Dual Price 1 0.000000 0.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 177.0000 0.000000 5 0.000000 1.000000 6 165.0000 0.000000 7 0.000000 0.000000 8 162.0000 0.000000 9 10.00000 0.000000 10 157.0000 0.000000 11 20.00000 0.000000 12 149.0000 0.000000 13 18.00000 0.000000 14 152.0000 0.000000 15 179.0000 0.000000 16 0.000000 1.000000 17 172.0000 0.000000 18 3.000000 0.000000 19 162.0000 0.000000 20 3.000000 0.000000 21 0.000000 0.000000 22 170.0000 0.000000 23 0.000000 0.000000 24 164.0000 0.000000 25 0.000000 1.000000 26 172.0000 0.000000 27 169.0000 0.000000 28 13.00000 0.000000 29 152.0000 0.000000 30 18.00000 0.000000 31 144.0000 0.000000 32 23.00000 0.000000 33 149.0000 0.000000 34 23.00000 0.000000 35 136.0000 0.000000 36 38.00000 0.000000 37 134.0000 0.000000 38 41.00000 0.000000 39 84.00000 -1.000000 40 28.00000 0.000000 41 10.00000 0.000000 42 0.000000 1.000000 43 51.00000 0.000000 44 0.000000 1.000000 45 0.000000 0.000000 46 5.000000 0.000000 47 0.000000 1.000000 48 5.000000 0.000000 49 2.000000 0.000000 50 0.000000 0.000000 51 0.000000 0.000000 即所有面试完成至少需要84分钟，面试顺序为：41-23（丁甲乙丙）。饮料的生产与检修 某饮料厂生产一种饮料用以满足市场需求。该厂销售科根据市场预测，已经确定了未来四周该饮料的需求量。计划科根据本厂实际情况给出了未来四周的生产能力和生产成本，如下表，每周当饮料满足需求后有剩余时，要支出储存费，为每周每千箱饮料0.2千元。问应如何安排生产计划，在满足每周市场要求的条件下，使每周的总费用（生产成本与储存费之和）最小？ 如果工厂必须在未来四周的某一周中安排一次设备检修，检修将占用当周15千箱的生产能力，但会使检修后每周的生产能力提高5千箱，则检修应该安排在哪一周。周次需求量（千箱）生产能力（千箱）成本（）115305.0225405.1335455.4425205.5合计100135问题分析 从表中我们可以看到，前三周的生产能力都超过需求量，只有第四周供不应求，经计算发现，这四周的生产能力加起来超过需求量，即可以满足市场的需求。所以，只要前三周多余的生产量正好可以弥补第四周的生产能力对需求量的不足，就可以使总的存贮费最小。但是，生产成本又在逐周增长，所以为了考虑总费用最小，我们就应该考虑在前几周多生产一些备用，这样就能得到最优方案。下面我们就建立数学规划模型来寻求最优的生产与存贮策略。模型假设 考虑到费用最小，我们就假设饮料厂在第一周和最后一周都没有库存，上一周的库存可以留到下一周再利用。分别用，代表饮料厂未来四周的生产量；用，分别记前三周的库存量；则第四周的总生产成本与存贮费之和是所要求的目标函数，记为。模型的建立与求解 显然，这四周的生产量，库存与需求只有个平衡的关系，根据这个原理我们就可以建立如下的数学规划模型： =5.0+5.1+5.4+5.5+0.2（+） . -=15 +-=25 +-=35 +=2530，40，45，20，0上面总共有7个自变量，用C语言编程序求解得到对优解为（， ，）=（15，40，25，20，0，15，5）。附带C语言程序：#includemain()int x1,x2,x3,x4,y1,y2, y3;int z=0,Max=0;for(x1=1;x1=30;x1+) for(x2=1;x2=40;x2+) for(x3=1;x3=45;x3+) for(x4=1;x40;y1+) for(y2=1;y20;y2+) for(y2=1;y20;y2+) for(y3=1;y30;y3+) if(x1-y1=15&x2+y1-y2=25&x3+y2-y3=35&x4+y3=25) z=5.0x1+5.1x2+5.4x3+5.5x4+0.2(y1+y2+y3); if(zMax) continue; else Max=z; printf(%d,%d,%d,%d,%d,%d,%dn”,x1,x2,x3,x4,y1,y2,y3,Max); 结果分析 从以上结果可以看到，生产计