合金工厂的生产规划.pptVIP

* * 数学实验 合金工厂的 生产规划 数学既不严峻，也不遥远，她和几乎所有的人类活动有关，还让每个对她感兴趣的人受益。 ― R.C.Buck 数学是理解世界及其发展的一把主要钥匙 。 ― 里约热内卢宣言 数学规划是运筹学和管理科学中应用级广泛的分支，在多数情况下，数学规划的使用如此成功以至它超出运筹学的范畴，成为人们日常的规划工具。 数学规划包括线性规划，非线性规划，整数规划，几何规划和多目标规划等，每种规划包含无数的实例，由于计算量的巨大，算法问题是极为重要的。 实际问题 由于A、B、C三种元素都是原料市场上十分紧缺的货品, 工厂每月所能得到的这些元素的供应量分别为200kg、200kg和360kg. 工厂生产每吨甲种合金的利润为30万元，生产每吨乙种合金的利润为40万元. 某合金工厂生产甲、乙两种合金， 生产每 A元素20 kg、 B元素40 kg和C元素90 kg， 吨甲种合金需用 而生产每吨乙种合金需用 A元素100 kg、B元素80 kg和C元素60 kg. 试问：该工厂应如何安排生产，才能获得最大利润？ 数学模型 设每月生产甲种合金x1 吨，乙种合金x2 吨，利润为 u 万元, 那么 u= 30 x1+40 x2 要求何时有 max u= max (30 x1+40 x2) x1, x2 满足约束条件 线性规划问题 求最优解 二元一次方程 a1x1+a2x2 =b 代表x1 x2平面上的一条直线，而二元一次不等式a1x1+a2x2 ? b则代表了以此直线为界的半平面 图解法 a1x1+a2x2 =b a1x1+a2x2 ? b 这问题中约束条件意味着五个半平面的交集. 它是一个包含边界的凸多边形OPQRS 线性规划的 容许集 x2 p Q R 0 S x1 x2 p Q R 0 S x1 30x1+40x2= u 将u视作参数，则30x1+40x2= u代表一条直线，随着u的增或减，直线向右上或左下方平移. 若直线经过容许集的某顶点时再增减将使直线离开容许集，则此临界状态直线所对应的u 的就是所求的最大值，所过顶点的坐标就是问题的最优解 从图看出最 优解应为R点 最优解在R点，由R是直线40x1+ 80x2= 200与直线90x1+ 60x2= 360的交点,可得最优解为x1=3.5, x2=0.75,此时有最大值为u=135. 说明安排月生产甲、乙种合金分别为3.5吨、0.75吨t，才能获得最大利润135万元 问题的解答 图解法的局限 画图并不方便，可以不画图而求出容许集所有的顶点，再将目标函数在这些顶点上的值加以比较来求出最优解.但在约束条件多或多变量时，也是难以做到的 单纯形法 基本思路是：线性规划(通常是求最小值的形式)若有最优解，其必定在容许集(在相应几何空间中是一个凸多面体)的顶点达到，故从某一个顶点出发，沿着凸多面体的棱向另一顶点迭代，使得目标函 数的值下降,经过有限次 迭代,将达到最优解点. 利用Mathematica 单纯形法的计算是线性规划算法中极为重要的内容 In[1]:= ConstrainedMin[-30x1- 40x2， {20x1+100x2=200,40x1+80x2=200, 90x1+60x2=360},{x1,x2}] Out[2]