经济数学（第三版） 课件 第七章 最优配置与最佳效果分析

第七章

最优配置与最佳效果分析目

录CONTENTS1安排生产问题及解决方案ArrangeproductionproblemsandSolutions2使用EXCEL讨论线性规划问题UsingExceltodiscusslinearprogramming3进一步学习的数学知识：单纯形法Furthermathematicsknowledge:Simplexmethod安排生产问题及解决方案ArrangeproductionproblemsandSolutions1一、问题的引入问题分析:这是一个最优化问题，应先设出目标变量和关键变量并建立目标函数，然后根据目标函数的类型，选择合适的方法求最值。

引例某企业生产甲、乙两种产品，要用3种不同的原料A、B、C．

从工艺资料可知：每生产1吨甲产品，需耗用3种原料分别为1，1，0单位；生产1吨乙产品，需耗用3种原料分别为1，2，1单位．每天原料供应的能力分别为6，8，3单位．

又知道每生产1吨甲产品，企业的利润收入为300元，每生产1吨乙产品，企业利润收入为400元．那么该企业应该如何安排生产计划，使一天的总利润最大呢？一、问题的引入设企业每天生产甲产品为吨，生产乙产品为吨，称，为决策变量，他们不能任意取值，要受到可供利用的原料资源数量的限制．又因为产品的产量一般是一个非负数，所以有，，称为非负约束．

解决方案

上面得到的3种原料的线性不等式是决策变量，取值所必须满足的条件，它们约束了决策变量，不能取任意值，称它们为约束条件．数学模型由三部分组成的：

①决策变量；

②线性的目标函数；③线性的约束条件．线性规划问题的三要素．一、问题的引入生产1吨甲产品企业的利润收入为300元，生产1吨乙产品企业的利润收入为400元．于是甲、乙两种产品的总利润为：它是决策变量的线性函数，并称此函数为目标函数.综上所述，得到描述原问题的数学模型如下：二、线性规划模型的相关概念

在线性规划问题中，满足约束条件的解称为可行解，所有可行解的集合称为可行集；使目标函数取值最大或最小的可行解称为最优解，对应于最优解的目标函数值称为最优值．

目标函数和约束条件均为线性关系的最优化问题称为线性规划问题，线性规划问题的数学模型一般形式如下：三、图解法例1

利用图解法求解线性规划问题

学习图解法的主要目的在于帮助理解线性规划问题解的性质.下面首先通过一个具体实例来说明图解法的原理和步骤.三、图解法解

(1)建立平面直角坐标系，根据约束条件画出可行域.图中阴影部分即为线性规划问题的可行域，可行域内任意一点的坐标都是该线性规划问题的可行解.(2)绘制目标函数等值线.

在几何上，目标函数代表平面上的一族平行直线，其中一条直线对应一个Z值.落在同一条直线上的点，如果又落在可行域上，那么这样的点就是具有相同目标函数值的可行解，所以平行直线族中的每一条直线又称为等值线.三、图解法(3)确定最优解最优解必须是满足约束条件，并使目标函数达到最优值的解，故的值只能在可行域中去寻找.当等值线由原点开始向右上方移动时，Z的值逐渐增大，于是，当移动到与可行域相切时，切点就是代表最优解的点.本例中等值线与可行域的切点为C点当时最优解为：19三、图解法例2某校伙食长期以面粉和大米为主食，面食每100g含蛋白质6个单位，含淀粉4个单位，售价0.5元，米食每100g含蛋白质3个单位，含淀粉7个单位，售价0.4元，学校要求给学生配制盒饭，每盒盒饭至少有8个单位的蛋白质和10个单位的淀粉.问：应如何配制盒饭，才既科学又费用最少?模型建立决策变量：设每盒盒饭需要面食（百克），米食（百克）目标函数：使费用最少，即约束条件：营养需求约束：非负约束：三、图解法综上所述，得药品生产问题的数学规划模型为：三、图解法模型求解：

(1)建立平面直角坐标系，根据约束条件画出可行域.(2)绘制目标函数等值线.目标函数代表平面上的一族平行直线，如图中虚线所示.(3)确定最优解本例中等值线与可行域的切点为A，此时目标函数取得最小值.当时最优解为：四、线性规划问题解的性质一般地，含两个变量的线性规划问题的解有下面四种情况：

（1）有可行解且有唯一最优解；

（2）有可行解且有无穷多最优解；

（3）有可行解但无最优解；

（4）无可行解.

同时，若线性规划问题存在最优解，它一定在可行域的某个顶点得到，若在两个顶点同时得到最优解，则它们连线段上的任意一点都是最优解，即有无穷多最优解.性质1求解线性规划问题时，解的情况有：唯一最优解、无穷多最优解、无界解、无可行解.性质2若线性规划问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解）一定可以在基可行解(顶点)中找到.使用Excel讨论线性规划问题UsingExceltodiscusslinearprogramming2一、使用EXCEL求解线性规划

Excel具有强大的规划求解功能，可以解决最多有200个变量，100个外在约束和400个简单约束（决策变量整数约束的上下边界）的线性规划与非线性规划问题．因此，可通过Excel的规划求解功能实现问题的求解。第一步：在Excel工作表中输入目标函数的系数、约束条件的系数矩阵和右端常数项（每一个单元格输入一个数据）；第二步：选定一个单元格存储目标函数，用定义公式的方式在这个目标单元格内定义目标函数；第三步：选定与决策变量个数相同的单元格（称为可变单元格），用以存储决策变量；再选择与约束条件个数相同的单元格，用定义公式的方式在每一个单元格内计算出相应的约束函数（称为约束函数单元格）；第四步：点击规划求解按钮，打开规划求解参数设定对话框，添加约束条件，完成规划模型的设定.使用规划求解加载宏求解数学规划的步骤：二、典型案例典型问题1某奶制品加工厂用牛奶生产两种奶制品，1桶牛奶可以在设备甲，或者在设备乙上用8小时加工成4公斤．根据市场全部能售出，且每公斤获利24元，每公斤加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设，设备乙的加工能力没有限制．请为该厂制定一个生产上用12小时加工成3公斤需求，生产的获利16元.现在备甲每天至多能加工100公斤计划，使得工厂每天获利最大．解决方案1.模型建立决策变量：设每天用桶牛奶生产设每天用桶牛奶生产目标函数：每天获利，使获利最大，即约束条件：原料供应：劳动时间：设备能力：非负约束：综上所述，数学规划模型为：二、典型案例2.模型求解第一步：建立表格.在工作表中的A1，A2，A3，D2，E2，A8单元格中分别输入“目标函数系数”，“决策变量”，“约束条件系数”，“目标函数值”，“约

束条件左端的值”，“约束条件右端的值”；在B1，C1单元格中输入目标函数的系数72，64，在B3，C3单元格中输入第一个约束条件的系数1，1；同理，在相应单元格中输入其他约束条件的系数与约束条件右端的值，如下图所示：二、典型案例第二步：计算约束条件左端的值和目标函数值．在D3单元格中输入公式“=B3*$B$2+C3*$C$2”，并使用句柄填充拖曳至D7单元格.目标函数的值等于目标函数系数乘以决策变量，从而在B8单元格中输入公式“=B1*B2+C1*C2”，如下图所示．二、典型案例第三步：输入各项参数

单击【数据】菜单中的【规划求解】命令，在弹出的规划求解对话框中输入各项参数．（1）设置目标单元格和可变单元格在“规划求解参数”对话框中选中“最大值”前的单选按钮，设置目标单元格为“$D$10”，可变单元格为“$B$2:$D$2”

，如右图所示．（2）添加约束条件单击【添加】按钮，打开【添加约束】对话框，单击单元格引用位置文本框，然后选定工作表中的D3至D5单元格，则在文本框中显示“$D$3:$D$5”，选择“<=”约束条件；单击约束值文本框，然后选定工作表中的E3至E5单元格，如图所示．二、典型案例第四步：在【规划求解结果】对话框中，单击【确定】按钮，工作表中就显示出规划求解的结果，如图所示．

如果要生成运算结果报告，可在【规划求解】对话框中选择【报告】列表框中的【运算结果报告】．单击【确定】按钮，则产生运算结果报告表.二、典型案例饲料配料问题在现代化的大型畜牧业中，经常使用工业生产的饲料.设某种饲料由四种原料混合而成，要求它含有三种成份（如维生素、抗菌素等）的数量分别不少于25、36、40个单位，各种原料的每百公斤重含三种成份的数量及各种原料的单价如表所示.问：应如何配料，使合成饲料（产品）既含有足够的所需成份，又使成本最低?二、典型案例二、典型案例1.模型建立目标函数：要使得成本最低，即决策变量：百公斤.设合成饲料中原料

的含量分别为

解决方案

在生产过程中，要使合成饲料含有足够的所需成份也就是说合成饲料中所含三种成份的总量要大于等于每种成份的需要量.同时，总成本最低，也就是使得合成饲料过程中四种原料的含量总成本最低.二、典型案例约束条件：需求量约束：合成饲料中成份

的含量需要大于等于需要量，即非负约束：综上所述，得数学规划模型为：二、典型案例2.模型求解第一步：在Excel工作表中建立线性规划模型，并计算约束条件左端的值和目标函数值，如图所示：第二步：单击【数据】菜单下的【规划求解】选项，在弹出的规划求解对话框中输入各项参数，如图7-11所示．二、典型案例第三步：单击【求解】按钮，弹出【规划求解结果】对话框，同时结果显示在工作表中，如图7-12所示．即在生产合成饲料的过程只需要用原料：7200公斤，最小生产成本为79.2元.二、典型案例药品生产问题

某药品生产企业准备投入生产六种药品，经过调查发现，生产每种药品所需要消耗的劳动力、原材料、每种药品的单位利润、需求量以及现有可

用的劳动力和原材料具体数据如下表所示：

产品1产品2产品3产品4产品5产品6现有劳动力（小时）65432.51.54500原料（磅）3.22.61.50.80.70.31600单位利润（元）65.35.44.23.81.8

需求量（磅）960928104197710841055

问：该药品生产企业该如何安排生产，使得总获利最大？二、典型案例

解决方案1.模型建立目标函数：要使得获利最大，即决策变量：设该药品生产企业生产药品1～6的产量分别为

药品生产企业通常需要确定每月（或每周）生产计划，列出每种产品必须生产的数量.具体来说就是，产品组合问题就是要确定公司每月应该生产的每种产品的数量以使利润最大化.产品组合通常必须满足以下约束：

（1）产品组合使用的资源不能超标.

（2）对每种产品的需求都是有限的.我们每月生产的产品不能超过需求的数量，因为生产过剩就是浪费（例如，易变质的药品）.二、典型案例约束条件：资源约束：生产药品所消耗的劳动力用时不能超过总的可用劳动力时，即同理，生产药品所消耗的原材料不能超过总的可用原材料量.需求量约束：每种药品的生产量不能超过需求量，从而可得非负约束：二、典型案例综上所述，得药品生产问题的数学规划模型为：二、典型案例2.模型求解第一步：在Excel工作表中建立线性规划模型，并计算约束条件左端的值和目标函数值，如图所示：二、典型案例第二步：单击【数据】菜单下的【规划求解】选项，在弹出的规划求解对话框中输入各项参数，如图所示．二、典型案例第三步：单击【求解】按钮，弹出【规划求解结果】对话框，同时结果显示在工作表中，如图7-15所示．即生产产品4：597.6667磅，生产产品5：1084磅，可获得最大利润为6625.2元．二、典型案例

自来水运送问题(运输问题)

某市有甲、乙、丙、丁四个居民区，自来水由三个水库供应，四个区每天必须得到保证的基本生活用水量分别为30，70，10，10千吨，但由于水源紧张，三个水库每天最多只能供应50，60，50千吨自来水．由于地理位置的差别，自来水公司从各水库向各区送水所付出的引水管理费不同.其他管理费都是450元/千吨．根据公司规定，各区用户按照统一标准900元/千吨收费．此外，四个区都向公司申请了额外用水量，分别为每天50，70，20，40千吨．该公司如何分配供水量，才能获利最多？引水管理费（元/千吨）甲乙丙丁A160130220170B140130190150C190200230二、典型案例决策变量：

假设三个水库

分别向甲、乙、丙、丁四区的供水量为由于水库与丁之间没有输水管道，即，因此只有11个决策变量．

1.模型建立

目标函数：问题的目标可以从获利最多转化为引水管理费最少，于是有二、典型案例

约束条件：约束条件有两类：一类是水库的供应量限制，另一类是各区的需求

量限制．由于供应量总能卖出并获利，水库的供应量限制可以表示为：考虑到各区的基本生活用水与额外用水量，需求量限制可以表示为：二、典型案例综上所述，自来水运送问题的数学规划模型为：二、典型案例2.模型求解

第一步：在Excel工作表中建立线性规划模型，并计算约束条件左端的值和目标函

数值．本例中决策变量有12个，在Excel工作表中B2至M2单元格，分别表示决策变量，然后输入各个约束条件（包括非负条件）的系数，同时计算约束条件左端的值和目标函数的值，如图所示．二、典型案例

第二步：在弹出的【规划求解参数】对话框中输入参数．单击【求解】按钮，得到

图所示结果．因此，最佳送水方案为：水库向乙区供应50千吨，

水库向乙、丁区分别供应50，水库向甲、丙区分别供应40，10千吨．10千吨，进一步学习的数学知识：单纯形法Furthermathematicsknowledge:Simplexmethod3

线性规划问题的标准型主要是针对线性规划问题的约束条件而言的，具体表现形式为：其中皆非负．

一、线性规划问题的标准型一、线性规划问题的标准型在解决实际问题时，根据实际问题建立的模型常常不是标准型，那么如何把一个线性规划问题转化为标准型呢？

(2)若约束条件中含有线性不等式约束，则需要引进新的非负变量，把线性不等式约束化为线性等式约束，这样引进的新非负变量称为松弛变量．(1)若求目标函数

的最小值，则引进新的目标函数

(a)当约束条件是时，在不等式左端加上松弛变量，将不等式约束化为等式约束．

(b)当约束条件是

时，在不等式左端减去松弛变量，将不等式约束化为等式约束．(3)若约束条件中线性等式约束的常数项为负值，则将该约束条件两端同时乘以，使得常数项为正值．(4)若对某一变量无约束，可令

作变量替换,使得对全部变量皆有非负限制．

一、线性规划问题的标准型一、线性规划问题的标准型例3将如下线性规划问题转化为标准型解

因为目标函数为最小值，所以引进新的目标函数又因为约束条件为两个不等式约束，故引进松弛变量一、线性规划问题的标准型从而线性规划问题化为：上式第一个约束等式右端的常数为负值，因而在该约束条件两端同时乘以-1，得到所给线性规划问题的标准形式为：二、单纯形法的原理与步骤例4

运用单纯形法求解线性规划问题二、单纯形法的原理与步骤第一步：引进松弛变量将所给线性规划问题化为标准型：

第二步：用非基变量表示基变量和目标函数求出一个基本可行解．由标准型可知：，令各非基变量等于0,即，得到基变量，它们构成初始基本可行解．

二、单纯形法的原理与步骤第三步：最优性检验最优性检验：判断基本可行解是否是最优解．

检验数：用非基变量表示的目标函数中的各非基变量的系数

最优解判定定理：

在极大化问题中，对于某个基本可行解，所有检验数，则这个基本可行解是最优解．二、单纯形法的原理与步骤第四步：确定换入变量

在决定哪个变量从非基本变量转化为基本变量时，当存在时，

选择作为换入变量.若检验数大于0的非基变量不止一个，则可以任选其中一个作为换入本例选择作为换入变量.变量．第五步：确定换出变量在决定出基变量时，按最小比值规则进行．在本例中，因为要从基变量

中换出一个，基变量的系数是1，

的系数是1，从而有

因此，选取作为换出变量．二、单纯形法的原理与步骤第六步：回到第三步进行新的基本可行解的最优性检验．用非基变量表示目标函数有因为非基变量的检验数

，由最优解判定定理可知，

基本可行解还不是最有解．第七步：确定新的换入变量、换出变量在目标函数

中，只有非基变量

的检验数大于0，因此我们选取作为换入变量,作为换出变量．令非基变量,得到基变量第三组基本可行解．二、单纯形法的原理与步骤第八步：回到第三步

判断第三组基本可行解是否是最有解．用非基变量表示目标函数有非基变量的检验数，非基变量的检验数由最优性判定定理，我们可知，此时的基本可行解就是最优解.

最优解

应用单纯形解法求解线性规划问题，相当于从可行解集的一个极点跳总结到另一个极点，逐步接近最优解，并最后到达最优解．三、对偶单纯形法的原理与步骤

线性规划的对偶单纯形法是根据对偶问题求解的特点和对称性设计出的一种解法.对偶单纯形法和单纯形法的主要区别：单纯形法在整个迭代过程中，始终保持原问题的可行性，即常数列大于等于0；

对偶单纯形法则是在整个迭代过程中，始终保持对偶问题的可行性，即全部检验数大于等于