经济数学（第三版） 教案 4.最优配置与最佳效果分析

第四讲最优配置与最佳效果分析-------安排生产问题及解决方案教学目标：掌握安排生产问题的解决方案。教学内容：讨论安排生产问题问题，线性规划概念及图解法。教学重点：建立线性规划模型教学难点：安排生产问题与线性规划模型的联系一、问题引入引例：美国空军为了保证士兵的营养，规定每餐的食品中，要保证一定的营养成份，例如蛋白质、脂肪、维生素等等，都有定量的规定。当然这些营养成分可以由各种不同的食物来提供，例如牛奶提供蛋白质和维生素，黄油提供蛋白质和脂肪，胡萝卜提供维生素，等等。由于战争条件的限制，食品种类有限，又要尽量降低成本，于是在一盒套餐中，如何决定各种食品的数量，使得既能满足营养成分的需求，又可以降低成本？问题分析：在本例中要利用有限的资源，去使得一份套餐既能满足营养要求又可以降低成本。用数学语言来说，就是在一定的约束条件下，求线性函数的最大和最小值问题。更加广义的来看待配餐问题，我们知道，现代的企业管理问题千变万化，企业内部的生产计划有各种不同的情况。从空间层次看，在工厂要根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制定产品的生产计划，在车间级则要根据产品生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制定生产批量计划。而这类问题都可以通过建立相应的线性规划模型来解决。那么，什么是线性规划？怎样建立线性规划模型？这正是我们要学习的内容。二、典型问题解决方案案例1：某企业生产甲、乙两种产品，要用、、3种不同的原料．从工艺资料知道：每生产1吨甲产品，需耗用3种原料分别为1，1，0单位；生产1吨乙产品，需耗用3种原料分别为1，2，1单位．每天原料供应的能力分别为6，8，3单位．又知道每生产1吨甲产品，企业的利润收入为300元，每生产1吨乙产品，企业利润收入为400元．那么该企业应该如何安排生产计划，使一天的总利润最大呢？解决方案：设企业每天生产甲产品为吨，生产乙产品为吨，称，为决策变量，他们不能任意取值，要受到可供利用的原料资源数量的限制．又因为产品的产量一般是一个非负数，所以有，，称为非负约束．由于生产1吨甲产品需耗用3种原料分别为1，1，0单位，因而生产吨甲产品需要耗用3种原料分别为，，0单位；由于生产1吨乙产品需耗用3种原料分别为1，2，1单位，因而生产吨乙产品需要耗用3种原料分别为，2，单位．又因为每天3种原料的供应能力分别为6，8，3单位，所以当企业每天生产甲产品吨，乙产品吨时，对于原料、、，我们有如下的不等式：原料：，原料：，原料：.上面得到的3种原料的线性不等式是决策变量，取值所必须满足的条件，它们约束了决策变量，不能取任意值，称它们为约束条件．容易看出，满足约束条件的变量，的值不唯一，即表示约束条件的线性不等式组有无穷多组解．如是一组解，此外也是一组解，还可以找出许多．这说明仅考虑到原料供应量的制约，对生产的安排是有选择余地的．这些安排生产的方案都是可行的，应该从中挑选出最优方案．那么，根据什么挑选最优方案？由于每一个可行方案，即每一组满足约束条件的变量值，都对应一个两种产品的总利润，在一般情况下，不同可行方案所对应的总利润也不相同，所以应该找出使得总利润最大的可行方案，这就是最优方案．由于生产1吨甲产品企业的利润收入为300元，生产1吨乙产品企业的利润收入为400元．于是甲乙两种产品的总利润为元，它是决策变量，的线性函数，称函数为目标函数．这样，最优方案就是使得目标函数最大的可行方案．综上所述，得到描述原问题的数学模型如下：（1）利用Excel求解可得，当时，取得最大值元．线性规划的相关概念从引例1可知最优化问题就是在给定条件下寻找最优方案的问题，其数学模型由三部分组成的：=1\*GB3①决策变量；=2\*GB3②目标函数；=3\*GB3③约束条件．进一步，如果目标函数和约束条件均为线性关系，我们把这样的最优化问题称为线性规划问题，条件=1\*GB3①、=2\*GB3②、=3\*GB3③称为线性规划问题的三要素．=1\*GB3①决策变量决策变量是指最优化问题中所涉及的与约束条件和目标函数有关的待确定的量.一般来说，它们都有一些限制条件（约束条件），与目标函数紧密关联.如引例2企业生产的甲、乙两种产品数量,是两个决策变量，决策变量一般表示为.=2\*GB3②目标函数线性规划问题中与变量有关的可以是求最大值，也可以是求最小值的函数称为目标函数，例如，若目标函数表示生产费用，则希望生产费用最小．无论目标函数是最大还是最小，总之是希望目标函数达到最优．目标函数一般表达式为：.=3\*GB3③约束条件在最优化问题中，求目标函数的最值时，决策变量必须满足的限制称为约束条件.例如，许多实际问题变量要求必须非负，这是一种限制；在产品的安排生产问题时，产品的产量受到原材料、人力资源的限制等.在研究问题时，这些限制我们必须用数学表达式准确地描述它们.约束条件按照表达式可分为等式约束和不等式约束：不等式约束;等式约束.综上所述，本章将要讨论的线性规划问题的数学模型可表示如下(7.1)在线性规划问题模型中，满足约束条件的解称为可行解，所有可行解的集合称为可行集；使目标函数取值最大或最小的可行解称为最优解，对应于最优解的目标函数值称为最优值．三、图解法学习图解法的主要目的在于帮助理解线性规划问题解的性质.下面首先通过一个具体实例来说明图解法的原理和步骤.例7.1求解线性规划问题解(1)建立平面直角坐标系，画出可行域.因为，所以满足约束条件的点都落在第一象限及坐标轴的正半轴上.在坐标系中画出直线，这条直线将整个坐标平面分成两个半平面，显然，坐标原点满足不等式，所以，满足约束条件的所有点落在直线上及原点所在一侧的半平面内.同理，满足约束条件的所有点位于直线上及以该直线为分割线的原点所在一侧的半平面内；满足约束条件的所有点位于直线上及以该直线为分割线的原点所在一侧的半平面内.上述三个平面点集在第一象限的交集即为可行域（包含边界），如图7-1.可行域内任意一点的坐标都是该线性规划问题的可行解.图7-1可行域图(2)绘制目标函数等值线.在几何上，目标函数代表平面上的一族平行直线，其中一条直线对应一个值.落在同一条直线上的点，如果又落在可行域上，那么这样的点就是具有相同目标函数值的可行解，所以平行直线族中的每一条直线又称为等值线.试探性给定值，如、，画出相应的等值线，如图7-1.不难发现，等值线离原点越远，的值越大.(3)确定最优解.最优解必须是满足约束条件，并使目标函数达到最优值的解，故的值只能在可行域中去寻找.当等值线由原点开始向右上方移动时，的值逐渐增大，于是，当移动到与可行域相切时，切点就是代表最优解的点.本例中等值线与可行域的切点为，点是直线和的交点，坐标为，所以，最优解为，最优值为19.通过例7.1，不难总结出图解法的基本步骤如下：（1）根据约束条件画出可行域；（2）根据目标函数的表达式画出目标函数等值线，并标明目标函数值增加的方向；（3）在可行域中，寻求符合要求的等值线与可行域边界相切的点或点集，并求出最优解和最优值.例7.2某校伙食长期以面粉和大米为主食，面食每100g含蛋白质6个单位，含淀粉4个单位，售价0.5元，米食每100g含蛋白质3个单位，含淀粉7个单位，售价0.4元，学校要求给学生配制盒饭，每盒盒饭至少有8个单位的蛋白质和10个单位的淀粉.问：应如何配制盒饭，才既科学又费用最少?1.模型建立决策变量：设每盒盒饭需要面食（百克），米食（百克）.目标函数：使费用最少，即.约束条件：营养需求约束：每盒盒饭至少需要含有8个单位的蛋白质和10个单位的淀粉，故可得非负约束：每盒盒饭需要面食和米食的重量均必须大于等于0，所以有综上所述，得药品生产问题的数学规划模型为：2.图解法求解(1)建立平面直角坐标系，根据约束条件画出可行域，如图7-2所示.图7-2配餐问题的可行域图(2)目标函数代表平面上的一族平行直线，其中一条直线对应一个值，如图中虚线所示.(3)本例中等值线与可行域的切点为，此时目标函数取得最小值，点是直线和的交点，坐标为，所以，最优解为，最优值为.因此，当每盒盒饭面食（百克），米食（百克）时既符合营养要求又费用最少，最少费用为元.例7.3某工厂在计划期内要安排生产=1\*ROMANI、=2\*ROMANII两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：表7-1产品的消耗、资源的限制表=1\*ROMANI=2\*ROMANII资源限制设备11300（台时）原料A21400（千克）原料B01250（千克）单位产品获利（元）50100问：工厂应分别生产多少单位=1\*ROMANI、=2\*ROMANII产品才能使工厂获利最多？1.模型建立决策变量：设产品=1\*ROMANI生产单位，产品=2\*ROMANII生产单位.目标函数：要使得获利最多，即约束条件：资源限制约束：设备的最多可用台时为300台时，即同理，原料A、B的消耗量不能超过资源限制，因此可得非负约束：每种原料的含量均必须大于等于0，所以有综上所述，得药品生产问题的数学规划模型为：2.图解法求解(1)建立平面直角坐标系，根据约束条件画出可行域，如图所示.图7-3安排生产问题的可行域图(2)目标函数代表平面上的一族平行直线，其中一条直线对应一个值，如图中直线.(3)本例中等值线与可行域的切点为，点是直线和的交点，坐标为，所以，最优解为，最优值为27500.因此，当工厂生产产品=1\*ROMANI：50单位，=2\*ROMANII：250单位时，获得最大利润为27500元.线性规划问题解的性质图解法虽然只能用来求解只含两个变量的线性规划问题，但通过它的解题思路和几何直观所得到的一些性质，对线性规划问题解的理解有很大的帮助.一般地，含两个变量的线性规划问题的解有下面四种情况：（1）有可行解且有唯一最优解；（2）有可行解且有无穷多最优解；（3）有可行解但无最优解；（4）无可行解.同时，若线性规划问题存在最优解，它一定在可行域的某个顶点得到，若在两个顶点同时得到最优解，则它们连线段上的任意一点都是最优解，即有无穷多最优解.上述结论可以推广到变量多于两个的一般情形，得线性规划问题解的性质如下：性质1求解线性规划问题时，解的情况有：唯一最优解、无穷多最优解、无界解、无可行解.性质2若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解）一定可以在基可行解(顶点)中找到.习题1．试述线性规划问题数学模型的组成部分及特征，判别下列数学模型是否为线性规划模型（模型中为常数，为可取某一常数值的参变量，为变量）。2.考虑如表9.2所示的生产计划问题，建立线性规划模型，以确定最优生产方案。表9.23某工厂用A、B两种配件生产甲、乙两种产品，每生产一件甲产品使用4个A配件耗时1h，每生产一件乙产品使用4个B配件耗时2h.该厂每天最多可从配件厂获得16个A配件和12个B配件，按每天工作8h计算，若生产一件甲产品获利2万元，生产一件乙产品获利3万元，问工厂应如何安排生产，以使得总利润最大？4．某矿山车队有4辆载重量为10t的甲型卡