网络与规划模型实验.doc

14.4 网络与规划模型实验学习目标1 能进行机器负荷分配问题中的动态规划运算；2 会进行食谱问题中的线性规划运算；3 会进行污水处理控制问题中的线性规划运算。一、 机器负荷分配问题1 问题 设某工厂有1000台机器，生产两种产品A、B，若投入y台机器生产A产品，则纯收入为5y，若投入y台机器生产b产品，则纯收入为4y，又知：生产A产品机器的年折损率为20%,生产B产品机器的年折损率为10%，问在5年内如何安排各年度的生产计划，才能使总收入最高？2 问题分析与建立模型 问题可分为5个阶段（k=1，2，3，4，5）。 第k个阶段第k年初到k+1年初 令 xk第k年初完好机器数 uk第k年安排生产A种产品的机器数 则显然有： xk - uk第k年安排生产B种产品的机器数，且0ukxk 在以上假设的基础上，则知： 第k + 1年初完好的机器数=（1 - 生产A产品的机器折旧率（20%）第k年安排生产A产品的机器数+（1 - 生产B产品的机器折旧率（10%）第k年安排生产B产品的机器数，即 xk +1 =（1 - 0.2）uk+（1 - 0.1）（xk - uk） =0.8 uk + 0.9（xk - uk） =0.9xk - 0.1uk 又令：L（xk，uk）第k年的纯收入； vk（xk）第k年初往后各年的最大利润之和。3 计算过程（1） 算法 第1步 定义 X=Tablex（i），i，5 U=Tableu（i），i，5 V=Tablev（i），i，5 第2步 v6（x6）=0第3步 f（x，y，z）=5y + 4（x - y）+ z， g（x，y）=0.9x - 0.1y 第4步 k = 5 第5步 Price=f（xk，uk，vk +1） 其中vk +1= g（xk，uk） 若：Price关于uk 的导数大于0，则：uk = xk 否则uk =0 vk（xk）= Price 第6步 k = k - 1 第7步 判断k 1？若是则转5，否则，转8 第8步 x1 = 1000 第9步 i = 2 第10步 xi = 0.9xi -1 - 0.1ui -1 第11步 i = i + 1 第12步 若i = 6，则转13，否则，转10 第13步 输出X，U，X - U，最大利润。（2） 源程序 ClearX，U，V，x，y，z； X=Tablexi，i，5；U=Tableui，i，5；V=Tablevi，i，5； v6=0； fx_，y_，z_：=5y+4（x-y）+z；gx_，y_：=0.9x - 0.1y； k=5； Whilek=1，xh=fxk，uk，vk+1/.xk+1gxk，uk； IfDxh，uk0， uk= xk；vk=xh/.ukxk，uk=0；vk= xh/.uk0；k； x1=1000；i=2； Whilei=70， 0.1 x1+0.05x2+0.02 x3+0.2 x4+0.05 x5 =3， 0.05 x1+0.1x2+0.02 x3+0.2 x4+0.08 x5 =10， x1，x2，x3，x4，x5 Out1=24.7436，x10，x20，x30， x439.7436，x525.6414. 结果分析可以看出，用两个不同函数LinearProgramming和ConstrainedMin求得相同的解，即：该公司可分别购买第四种饲料39.74（kg）和第五种饲料25.64（kg）配成混合饲料，所耗成本24.74（元）为满足营养条件下的最低成本。这类线性规划模型还可以描述很多诸如合理下料、最小成本运输、合理分派任务等问题，具有很强的代表性。三、 污水处理控制问题1 问题如图14-8，有若干个排污口流入某江，各口有污水处理站，江面各段的流量和污水浓度分别为Qk和Ck，工厂污水的流量和浓度分别为Qk和uk ，污水处理站流出的流量和浓度分别为Qk和uk*。尽管国家对各种排污有严格的标准，如果由于经济原因不可能全面达标，那么如何安排各排污点的位置或为了保证重点城市的卫生标准，对各排污点或污水处理站制定排放标准。其中流量单位：m3/s，浓度单位：mg/l。图14-8 污水处理问题污染浓度的递推关系应该满足水质自净方程 （1） ak是与江段地理位置相关的系数，称为k=e-ak为自净系数。2 问题分析与建立模型 要考虑一种合理的安排，尽量使居民点处的江水合乎标准，这样就有一个对排污口的位置安排问题，以及灵活考虑排污口的治理问题。比如有个排污口离居民点较远，尽管排污超标，但通过流水的自净作用在到达居民点前已合乎标准了，为了节约资金，也可暂时不予治理，或者提出一个更宽松的标准，于是我们希望解决如下问题： 我们的目标是根据流出来的江水水质和国家规定的水质标准，来确定各排污口的排放量和最大允许污物浓度。 在使各段检测点（居民点）的水污染不超过国家标准C的条件下，使投入污水处理的总资金最少。 如果不考虑居民点C1和C2，只考虑使居民点C3符合标准C（重点控制方案），那么我们的标准如何制定？ 该问题是在一定约束条件下的最优化问题，并且约束条件是线性的，因此可以用线性规划模型加以解决。 为了使问题简化，我们做如下假设： 国家的污染控制标准是多指标的，我们取其中主要的一项，以污染浓度来表示。 各排污口排出的污水量和污水的污染浓度一定，即Qk和uk 为常数。 污水处理即要降低污染浓度，一般来说，使污水处理的污水浓度差u-u*越大（u*为处理后的污水浓度），要求投入越多（包括技术、设备、能耗等），这种投入我们以资金投入计算。 为了简单起见，不妨设污水处理费用与污水浓度差u-u*成正比，与污水水量Qk成正比，即 Tk=rkQk（uk- u*k） （2） 其中rk为比例系数，它实际上表示了第k个污水处理站的每流量单位降低每个浓度单位所需的资金。当然rk的大小可以反映污水处理的技术水平，这里我们暂且不讨论，一般将rk看作常数。污水浓度递推关系满足水质自净方程（1），我们可改写为 C *k=（Qk Ck + Qku *k）/ Qk+1 （3） C k+1= k C *k （4） 显然，0k 1，自净因子（或自净系数）与河流状态（水量、污染程度、地质状况、温度等）有关，在某一段江水中，比如说四川省境内，由于地理位置相差不大可以看成常数。自净因子的获得可以利用监测数据，利用参数估计的方法计算获得。 我们定义单位时间流过某一断面的污染物的总量为此断面的污染通量Vk，显然有污水治理站的流入污水通量为 Vk=Qkuk （5） 流出通量为 V *k=Qku *k （6） 我们定义 （7） 为第k个污水处理站的治理系数，显然k反映了治理能力，一般有0k 1，k =0表示未治理，而k越接近于1，则治理效果越好。治理系数也可以看成是对污水治理要求达到的一项指标，当然，治理系数与投资也是密切相关的。将（5）式改写为 V *k=(1-k)Vk （8）将(5)、(6)式代入（2）式可得 Tk= rk (Vk - V *k)= rk Vkk （9） 由此可见，污水处理的费用与处理系数k成正比，同污水的污染通量Vk成正比。 设Qk比Qk小得多，即污水的流量比江水流量小得多，且在整个一段范围内流量Qk为常数。即Qk+Qk =Q，则污水进入江水混合以后的浓度为 C *k = = （10） 则自净方程简化为：C k+1= C *kk （11） 模型A 水质全面达标模型 本模型要求使江水水质全面达到质量标准，即使各污染点与江水均匀混合后都能达到卫生标准，即C *kC。 min T =rkQk（uk- u*k） （12） s.t. （13） 模型B 居民点上游水质达标模型 我们将uk作为已知（污染点的污染浓度），将治理系数k作为变量，再由（9）、（10）两式，则模型A可改写为 min T = （14） s.t. （15） 显然，目标函数关于k是线性函数，而约束条件关于k也是线性的，于是本模型归结为线性规划问题得以解决。3 计算过程模型A：水质全面达标模型设 C1=0.8 (mg/l)Q=1000 (1012 l/min)，u1=100，u2=60，u3=50 (mg/l) Q1 = Q2 = Q3 =5 (1012 l/min) （16） 1=0.9，2=0.6，r1 = r2 = r3 =1， C=1 （每个流量单位，每降低一个浓度单位需1万元）则 r1 V1 =500，r2 V2 =300，r3 V3 =250，C1， C*1=1.3-0.51，C*2=1.47-0.451-0.32，C*3=1.32-0.271-0.182-0.253 因此，由计算机计算得出 1=0.6，2=0.666667，3=0 minT=500（万元） 模型B：居民点上游水质达标模型 在参数（16）式的条件下，江水在各段通过自净后，在到达居民点之前达到标准，即 minT=5001+3002+2503 （17） C11，C2=1.17-0.4511 C3=0.882-0.271-0.1821 （18） 0k1 用计算机求解得：1=0.377778，2=0，3=0 minT=188.889（万元）4 结果分析 模型B与模型A比较，由于水质控制的范围缩小了，从全面水质污染控制到居民点（上游）水质控制，因此，治理费用也随之减少，这是充分利用了江水自净的功能。 从模型A到模型B，都是由于控制范围的逐渐缩小而使得总费用降低。当然，我们这里的数据是设定的，不一定合乎实际，但是计算结果反映了对江水污染控制的规律，是符合人们的认识的，当然，在实际中可以根据实际数据，用此模型算出各污染点的治理系数。这些数据可以作为控制污染的参考数据。k越大，说明这个污染点的治理系数越小，治理的要求就可以降低，这样也可以分得出治理的轻重缓急。 模型A的Mathematica源程序：C1=0.8；Q=1000.；u1=100.；u2=60.；u3=50.；Q1=Q2=Q3=5.；B1=0.9；B2=0.6；r1=r2=r3=1.； V1=Q1*u1；V2=Q2*u2；V3=Q3*u3；C1X=C1+V1/Q - V1/Q*Lm1；C2=C1X*B1；C2X=C2+V2/Q - V2/Q*Lm2；C3=C2X*B2；C3X=C3+V3/Q - V3/Q*Lm3； SimplifyC1X SimplifyC2X SimplifyC3X 运行结果： 1.3-0.5Lm1 1.47-0.45Lm1-0.3Lm2 1.132-0.27Lm1-0.18Lm2-0.25Lm3 Mathematic程序：ConstrainedMin500x + 300y + 250z， 1.3 - 0.5x = 1， 1.47 - 0.45x - 0.3y = 1， 1.132 - 0.27x - 0.18y - 0.25z = 1， x = 1，y = 1，z = 1，x，y，z 运行结果： 500.，x0.6，y0.666667，z0 模型B的Mathematica源程序： C1=0.8；Q=1000.；u1=100.；u2=60.；u3=50.；Q1=Q2=Q3=5.； B1=0.9；B2=0.6；r1=r2=r3=1.；V1=Q1*u1；V2=Q2*u2；V3=Q3*u3；C1X=C1+V1/Q-V1/Q*Lm1；C2=C1X*B1；C2X=C2+V2/Q-V2/Q*Lm2；C3=C2X*B2； SimplifyC1 SimplifyC2 SimplifyC3 运行结果： 0.8 1.17-0.45Lm1 0.882-0.27Lm1-0.18Lm2 Mathematica程序：ConstrainedMin500x + 300y + 250z， x =1， 1.47 - 0.45x = 1， 0.882 - 0.27x - 0.18y = 1， x = 1，y = 1，z = 1，x，y，z 运行结果：188.889，x0.377778，y0，z0习题14.41 如下图所示，从A0地要铺设一条管道到A6地，中间必须经过五个中间站。第一站可以在A1、B1两地中任选一个，类似地，第二、三、四、五站可供选择的地点分别是 A2，B2，C2，D2、 A3，B3，C3、 A4，B4，C4、 A5，B5。连接两点间的管道的距离，用图中两点连线上的数字表示，两点间没有连线的相应两点间不能铺设管道，现在要选择从A0到A6的铺管线路，使总距离最短。图14-9 最短路问题2 某工厂制造A，B两种产品，制造产品A每吨需用煤9吨，电力4千瓦，3个工作日；制造产品B每吨需用煤5吨，电力5千瓦，10个工作日。已知制造产品A和B每吨分别获利7000元和12000元，现在该厂由于条件限制，只有煤360吨，电力200千瓦，工作日300个可以利用，问A，B两种产品各应生产多少吨才能获利最大？3 在污水处理控制问题中，将u1=100，u2=60换成u1=60，u2=100再计算结果，分析数据有何变化？考虑使江水全面达到标准，即在经过处理的污水与江水均匀混合后即达到标准（Ck*1）时，总费用有何变化。复习题十四1 有三对夫妻过河，船最多能载2人，由于封建意识严重，要求任一女子不能在丈夫不在场的情况下与另外的男人在一起。如何安排3对夫妻过河？2 为了改变平淡的自行车外表，给自行车添加一份美妙的动感，同时，也为了增加骑车人的“安全系数”，一些骑车人及自行车厂家在自行车的辐条上安装一块亮丽夺目的饰物。当有这种饰物的自行车在马路上驶过时，这饰物就如游龙一样，对街边的行人闪过一道波浪形的轨迹。这一波一闪的光亮游龙，也默默地维护着自行车及骑车人的安全。这轨迹是什么曲线？试画出它的图形。当这自行车又在一个抛物线形的拱桥上通过时，或是在一拱一拱的正弦曲线（例如山地摩托车赛场）上通过时，这饰物又画出一条曲中有曲的轨迹。这轨迹是什么曲线？试画出它的图形。3 一天文学家要确定一颗小行星绕太阳运行的轨迹，他在轨道平面内建立以太阳