合金工厂的生产规划问题.ppt

* * [实验四] 合金工厂的生产规划问题 ? 一、实验目的 本实验涉及线性代数，通过实验复习矩阵的运算、初等变换和解线性方程组等知识，另外介绍了运筹学中一类重要的问题：线性规划问题和求解的基本方法。 二、实际问题 某合金工厂生产甲、乙两种合金，生产每吨甲种合金需用A元素20kg、B元素40kg和C元素90kg，而生产每吨乙种合金需用A 元素100kg 、B元素80kg 和 C元素60kg。由于A、B、C三种元素都是原料市场上十分紧缺的货品，工厂每月所能得到的这些元素的供应量分别为200kg 、200kg、和360 kg。工厂生产每吨甲种合金的利润为30万元，生产每吨乙种合金的利润为40万元。试问：该工厂应如何安排生产，才能获得最大利润？ 三、数学模型 设工厂每月生产甲种合金 乙种合金 利润为 u万元，那么 显然，问题是要求何时有 而 满足约束条件 其中最后一行的不等式是反映产量是非负的。 这就是实际问题的数学模型。它是求一个线性函数在非负自变量受到线性不等式（或等式）的约束时极值问题，称之为线性规划；所求极值问题的解称为线性规划的最优解。 四、图解法 我们在 平面上考察问题 (9.2) 、(9.3)二元一次方程 代表了坐标平面上的一条直线，而二元一次不等式 则代表了以此直线为界的半平面，因此约束条件(9.3)意味着五个半平面的交集。图 9.1中的阴影部分给出了这个集合，它是一个包含边界的凸多边形 OPQRS.显然，代表上述线性规划的最优解的点必定 位于这个集合中，故称此集合（确切地说是此点集对应的坐标向量集）为线性规划的容许集。 再来看由式 （9.1）给出的目标函数 , 如果将 U 视作参数，那么 代表了斜率为 的直线，随着U的增加或减少，直线向右上方或左下方平移（见图9.2）容易理解：若直线经过容许集的某个顶点而此时U再增加将使直线离开容许集，则此临界状态的直线所对应的参数值就是所求问题的最大值，所过顶点的坐标就是问题的最优解。从图9.2可看出最优解应为R点。 由于R 是直线 的交点,可得最优解为 此时 U 有最大值为U=135. 这说明应安排每月生产甲、乙合金分别为 3.5t、0.75 t，才能获得最大利润135万元。 图解法告诉我们，线性规划的最优解往往在容许集的顶点取得。因此在确定了容许集是有界的条件下，也可以不画图而求出容许集所有顶点，再将目标函数在这些顶点上的值加以比较来求出最有解。这种做法一般在三个变量时采用，因为三维空间中的多面体一般是不容易画的。 然而上述方法虽然简单，但在实际中却很少应用，因为在源于实践的真正的线性规划问题中，变量通常不是两三个而往往是几十甚至几百个，所以既无法画图也很难求出所有的容许集顶点，因此我们介绍了一种更普遍有效的方法。 五、单纯形法 单纯形法的基本思路是：线性规划（通常是求最小值的形式）若有最有解，其必定在容许集（相应几何空间中的凸多面体）的顶点达到，故从某一个定点出发，沿着凸多面体的棱向另一顶点迭代，使得目标函数的值下降，经过有限次迭代，将达到最优解点。 ? I. 标准型 首先我们通过令V= - U，把问题变为求 在约束下的极小值，再引进新变量，将线性规划（9.2）,（9.3）化为求： 满足约束条件 于是，除了变量 非负之外，其他的约束条件都化为等式，且约束等式的个数不超过变两个数，等式右端项非负。我们将符合这样条件的线性规划形式称为标准行型。 Ⅱ. 单纯形法 那么约束条件(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)的一个解，