数学建模-线性规划.docx

《数学建模-线性规划.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第八章线性规划8.1引言有一个关于伟大数学家欧拉（Euler）的故事是这样说的，因为没有足够的篱笆，小欧拉的父亲为修建羊圈而发愁，小欧拉问父亲：为什么不将羊圈建成方的，这样不就能用更少的篱笆围成更大的面积吗？这个三百年前出自一个小儿之口的问题道出了一大类的科学问题：最优化问题。这类问题是如此的普遍，它遍及宇宙的每一个角落，也渗透在人们的每一根神经之中。这类问题的特点是有一个目标，这个目标，在一定的条件下可以用函数表达出来，比如上面的面积是矩形的长和宽的函数。我们的目的就是使目标函数达到最大或者最小。但是面积并不能无限的大

2、，因为受到篱笆长度（周长）的限制。也就是说最大化的同时要受到约束条件的限制。通过分析上面的例子可以发现，描述最优化问题有三个基本要素，即决策变量、目标函数和约束条件。决策变量：确定问题目标值大小的众多因素中，其中决策者可以控制的量称为决策变量。决策变量的取值确定了系统的最终性能，也是决策者采用决策的依据。应该注意，在系统中还有一些量，它们不能由决策者所控制，而是由系统所处的环境所决定，我们称之为参数。在一些问题的建模过程中，确定变量经常是第一步的同时也可能是最困难的工作。目标函数：它代表决策者希望对其进行优化的那个指标。

3、目标函数是决策变量的函数。对应决策者而言，对其有利的程度必须定量的测度,在商业应用中，有效性的测度经常是利润或者成本,但对于政府，更经常的使用投入产出率来测度。表示有效性测度的经常称为目标函数。大部分的模型中，确实目标函数比较简单，因此，我们建模是往往从这里寻找思路。约束条件：它们是决策变量在现实世界中所受到的限制，约束条件决定了决策变量和参数之间的关系。约束集界定决策变量可以取某些值而不能取其他的值。在实际问题中，决策变量带有约束是普遍的。有时一些问题的约束可能非常复杂。一般地，建立最优化模型遵循如下的过程：（1）明确

4、问题的目标，找到确定目标性能的主要因素，从而确定决策变量；（2）分析上面给出的决策变量和目标之间的函数关系，确定目标函数；（3）确定决策变量和参数之间的关系和限制，确定约束条件。8.2引例线性规划在实际生产和生活中有非常广泛的应用，比如生产计划问题，交通运输问题，管理调度问题等等，下面以三个例子作为线性规划问题的典型例子加以说明。例1：（生产计划问题）某工厂生产甲乙丙三种产品，单位产品分别可为工厂带来4元、3元和2元的利润。同时生产这些产品的过程中，需要耗费原材料和人力：单位产品耗费的原材料A为2、3和1个单位，而可用于

5、生产的原材料A总数为34个单位；同时消耗原材料B均为1个单位，而可用于生产的原材料B总数为20个单位，而且材料B不能保存只能用完；单位产品需要的工时数为3、2和1.5，而可供使用的工时数不超过36；。问如何组织生产，可以获得最大的利润？（选择原因：题目简单，适合作为入门级的例子，同时生产计划问题是线性规划问题最常见的例子之一）分析：按照题目，容易知道，问题的目标非常明确，就是利润最大，而和决定利润的因素在单个产品利润给定的情形下，决定总利润的因素无非是生产的数量，更确切的说就是甲乙丙三种产品的生产数量，因此可以确定规划问

6、题的决策变量是三种产品的生产数量，分别记为x1,x2和x3。在此基础上，我们能容易的写出目标函数为利润P=4x1+3x2+2x3。再看看这些决策变量有没有受到什么限制，根据题意，生产产品需要消耗原材料和工时，而这两种资源都有一定的限制，当生产x1,x2和x3个甲乙丙产品时，耗费的原材料A为2x1+3x2+x3，由于可用于生产的原材料A为34，所以有约束2x1+3x2+x3≤34.对于原材料B，有约束x1+x2+x3=20.同样地，生产过程中受到工时的限制，有3x1+2x2+1.5x3≤36.最后，注意到生产的产品数量不可

7、能是负数，也就是x1,x2和x3是非负的，因此我们得到如下的规划问题：（8.1）注意：这个分析过程很好的给出了建立模型的思维过程，即明确目标，寻求决定目标的因素，确定问题的决策变量，使用决策变量写成目标函数，然后分析这些决策变量受到什么样的约束，逐个的给出决策变量受到的约束并用或不等式的方式表达出来。例2.（运输问题）永辉超市有限公司在重庆地区有n家超市，这些超市的蔬菜主要来自m家蔬菜生产基地。第j家超市每天蔬菜的销量为aj顿（j=1,2,...,n），第i家生产基地每天的产量为bi（i=1,2,...,m）。假设从第i

8、家基地到第j家超市的距离为cij公里（i=1,2,...,m，j=1,2,...,n）。为简单起见，假定每天基地生产蔬菜的总量和超市需求的总量相等，即。问如何制定调运方案，既可以满足供需关系，又使运输的顿公里数达到最少。（选择原因：运输问题是线性规划最常见的例子之一，也是可以扩充的任何使用的例子的基础，实际上这个例子