欢迎来到天天文库
浏览记录
ID:36221823
大小:482.00 KB
页数:11页
时间:2019-05-07
《数学实验实验九new》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、[实验九]合金工厂的生产规划问题一、实验目的本实验涉及线性代数,通过实验复习矩阵的运算、初等变换和解线性方程组等知识,另外介绍了运筹学中一类重要的问题:线性规划问题和求解的基本方法。二、实验内容本实验以合金工厂的生产规划作为实际问题,对合金工厂的生产进行定量分析。这种生产的定量分析能力能够使企业找到改善生产指标的真正原因并进行优化,从而达到指标领先,此种能力还能使企业在原燃料、产品品种等生产条件发生变化时,能对生产结构进行优化设计并重新选择最佳操作参数,从而保证生产指标最佳。并能够帮助工厂合理安排生产,以取得最大利润。实际问题如下:某合金工厂生产甲、乙两种
2、合金,生产每吨甲种合金需用A元素20kg、B元素40kg和C元素90kg,而生产每吨乙种合金需用A元素100kg、B元素80kg和C元素60kg。由于A、B、C三种元素都是原料市场上十分紧缺的货品,工厂每月所能得到的这些元素的供应量分别为200kg、200kg、和360kg。工厂生产每吨甲种合金的利润为30万元,生产每吨乙种合金的利润为40万元。试问:该工厂应如何安排生产,才能获得最大利润?三、采用方法现通过建立数学模型来解决以上问题:设工厂每月生产甲种合金,乙种合金利润为u万元,那么显然,问题是求何时有而、满足约束条件:其中最后一行的不等式是反映产量是非
3、负的。这就是实际问题的数学模型。它是求一个线性函数在非负自变量受到线性不等式(或等式)的约束时极值问题,称之为线性规划;所求极值问题的解称为线性规划的最优解。四、具体方法①图解法我们在平面上考察问题(9.2)、(9.3)。二元一次方程代表了坐标平面上的一条直线,而二元一次不等式则代表了以此直线为界的半平面,因此约束条件(9.3)意味着五个半平面的交集。图9.2中的阴影部分给出了这个集合,它是一个包含边界的凸多边形OPQRS.显然,代表上述线性规划的最优解的点必定位于这个集合中,故称此集合(确切地说是此点集对应的坐标向量集)为线性规划的容许集。再来看由式(9
4、.1)给出的目标函数,如果将u视作参数,那么代表了斜率为的直线,随着u的增加或减少,直线向右上方或左下方平移(见图9.2)容易理解:若直线经过容许集的某个顶点而此时u再增加将使直线离开容许集,则此临界状态的直线所对应的参数值就是所求问题的最大值,所过顶点的坐标就是问题的最优解。从图9.2可看出最优解应为R点。由于R是直线的交点,可得最优解应该为此时U有最大值为U=135.这说明应安排每月生产甲、乙合金分别为3.5t、0.75t,才能获得最大利润135万元。3然而上述方法虽然简单,但在实际中却很少应用,因为在源于实践的真正的线性规划问题中,变量通常不是两三个
5、而往往是几十甚至几百个,所以既无法画图也很难求出所有的容许集顶点,因此我们介绍了一种更普遍有效的方法。②单纯形法单纯形法的基本思路是:线性规划(通常是求最小值的形式)若有最有解,其必定在容许集(相应几何空间中的凸多面体)的顶点达到,故从某一个定点出发,沿着凸多面体的棱向另一顶点迭代,使得目标函数的值下降,经过有限次迭代,将达到最优解点。I.标准型首先我们通过令V=-U,把问题变为求在约束下的极小值,再引进新变量,将线性规划(9.2),(9.3)化为求:满足约束条件:于是,除了变量非负之外,其他的约束条件都化为等式,且约束等式的个数不超过变两个数,等式右端项
6、非负。我们将符合这样条件的线性规划形式称为标准行型。那么约束条件(9.5)中的等式组成的方程组可写为在向量a1、a2、a3、a4、a5中选取三个成为线性无关组,通常总可以(或采取一些方法)取到单位向量,例如这里可以选取a3、a4、a5,称之为基,相应的变量x3,x4,x5称为基变量,而其余的变量x1,x2称为非基变量。记N1=(a1,a2),那么式(9.6)即令可得注意,b1的分量非负,故(9.8),(9.9)不仅构成了(9.6)的一个解,而且也是(9.5)的一个解,称之为初始容许解。这就是单纯形法的出发点。现考虑是否和如何转向下一个点,为说明一般的原则,
7、把目标函数V写成对应基变量的系数记为,而非基变量系数记为将(9.7)代入上式,则记那么注意,对应基变量的总是为零。以上显然是将目标函数写成仅含非基变量的形式,不过在我们的(9.4)、(9.5)中目标函数已有了这形式。从而容易看出:(1)若非基变量的系数均不大于零,那么初始容许解就是最优解。(2)可以证明:在所有大于零的所对应的非基变量aj中,只要有一个向量的所有分量小于或等于零,则这个线性规划无解。在我们的问题中,它们对应的均无非正分量,因此不能得出以上两种结论。此时,就将进行所谓换基。(3)换基的选择是先从(9.11)给出的所有大于零的系数中比较出最大者
8、,则其所对应的非基变量将成为基变量,在这个问题中故将进入基变量。记
此文档下载收益归作者所有