数学建模-线性规划

第八章线性规划8.1引言有一个关于伟大数学家欧拉（Euler）的故事是这样说的，因为没有足够的篱笆，小欧拉的父亲为修建羊圈而发愁，小欧拉问父亲：为什么不将羊圈建成方的，这样不就能用更少的篱笆围成更大的面积吗？这个三百年前出自一个小儿之口的问题道出了一大类的科学问题：最优化问题。这类问题是如此的普遍，它遍及宇宙的每一个角落，也渗透在人们的每一根神经之中。这类问题的特点是有一个目标，这个目标，在一定的条件下可以用函数表达出来，比如上面的面积是矩形的长和宽的函数。我们的目的就是使目标函数达到最大或者最小。但是面积并不能无限的大，因为受到篱笆长度（周长）的限制。也就是说最大化的同时要受到约束条件的限制。通过分析上面的例子可以发现，描述最优化问题有三个基本要素，即决策变量、目标函数和约束条件。决策变量：确定问题目标值大小的众多因素中，其中决策者可以控制的量称为决策变量。决策变量的取值确定了系统的最终性能，也是决策者采用决策的依据。应该注意，在系统中还有一些量，它们不能由决策者所控制，而是由系统所处的环境所决定，我们称之为参数。在一些问题的建模过程中，确定变量经常是第一步的同时也可能是最困难的工作。目标函数：它代表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数。对应决策者而言，对其有利的程度必须定量的测度,在商业应用中，有效性的测度经常是利润或者成本,但对于政府，更经常的使用投入产出率来测度。表示有效性测度的经常称为目标函数。大部分的模型中，确实目标函数比较简单，因此，我们建模是往往从这里寻找思路。约束条件：它们是决策变量在现实世界中所受到的限制，约束条件决定了决策变量和参数之间的关系。约束集界定决策变量可以取某些值而不能取其他的值。在实际问题中，决策变量带有约束是普遍的。有时一些问题的约束可能非常复杂。一般地，建立最优化模型遵循如下的过程：（1）明确问题的目标，找到确定目标性能的主要因素，从而确定决策变量；（2）分析上面给出的决策变量和目标之间的函数关系，确定目标函数；（3）确定决策变量和参数之间的关系和限制，确定约束条件。8.2引例线性规划在实际生产和生活中有非常广泛的应用，比如生产计划问题，交通运输问题，管理调度问题等等，下面以三个例子作为线性规划问题的典型例子加以说明。例1：（生产计划问题）某工厂生产甲乙丙三种产品，单位产品分别可为工厂带来4元、3元和2元的利润。同时生产这些产品的过程中，需要耗费原材料和人力：单位产品耗费的原材料A为2、3和1个单位，而可用于生产的原材料A总数为34个单位；同时消耗原材料B均为1个单位，而可用于生产的原材料B总数为20个单位，而且材料B不能保存只能用完；单位产品需要的工时数为3、2和1.5，而可供使用的工时数不超过36；。问如何组织生产，可以获得最大的利润？（选择原因：题目简单，适合作为入门级的例子，同时生产计划问题是线性规划问题最常见的例子之一）分析：按照题目，容易知道，问题的目标非常明确，就是利润最大，而和决定利润的因素在单个产品利润给定的情形下，决定总利润的因素无非是生产的数量，更确切的说就是甲乙丙三种产品的生产数量，因此可以确定规划问题的决策变量是三种产品的生产数量，分别记为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.最后，注意到生产的产品数量不可能是负数，也就是x1,x2和x3是非负的，因此我们得到如下的规划问题：123123123123123max432..233420321.536,,0xxxstxxxxxxxxxxxx（8.1）注意：这个分析过程很好的给出了建立模型的思维过程，即明确目标，寻求决定目标的因素，确定问题的决策变量，使用决策变量写成目标函数，然后分析这些决策变量受到什么样的约束，逐个的给出决策变量受到的约束并用或不等式的方式表达出来。例2.（运输问题）永辉超市有限公司在重庆地区有n家超市，这些超市的蔬菜主要来自m家蔬菜生产基地。第j家超市每天蔬菜的销量为aj顿（j=1,2,...,n），第i家生产基地每天的产量为bi（i=1,2,...,m）。假设从第i家基地到第j家超市的距离为cij公里（i=1,2,...,m，j=1,2,...,n）。为简单起见，假定每天基地生产蔬菜的总量和超市需求的总量相等，即11nmjijiab。问如何制定调运方案，既可以满足供需关系，又使运输的顿公里数达到最少。（选择原因：运输问题是线性规划最常见的例子之一，也是可以扩充的任何使用的例子的基础，实际上这个例子中可以向很多方向扩展，比如蔬菜的种类有多种多样，蔬菜基地可以具有短暂的储存功能，超市也有一定的储存功能，但是蔬菜可能有较大的损坏，此外，超市的销售量也可能是随机的，所以，容易扩展到各种各样的和运输相关的问题）分析：同样地，我们明确我们的目标是运输的吨公里（有时也称为运费）最小，这个值和蔬菜基地和超市之间的距离和运输的量共同决定，其中蔬菜基地和超市的距离是确定的常量，而不同基地和超市之间的运输量是可控的量并且决定了最终的运费，因此应该选择基地i到超市j的运量xij作为决策变量（i=1,2,...,m，j=1,2,...,n）。这样可以写出运输的吨公里数11mnijijijcx.这些运输量显然的受到一些限制，比如从一个产地运向各个超市的运量之和不能超过该基地的产量，这类约束我们称为产地约束，于是有1,1,2,,nijijxbim.此外，对于任何一家超市，来自与不同产地的蔬菜总量应该能够满足该超市的销售量，因此又有如下的约束1,1,2,,mijjixajn.同时，注意到所有的运输量是非负的变量，于是可以得到下面的线性规划模型1111min..,1,2,,,1,2,,0,1,2,,,1,2,,mnijijijnijijmijjiijcxstxbimxajnximjn（8.2）（关于问题的扩充：可以在练习题里面体现，比如两种货物，又比如一些基地和超市的对接限制等，又比如怎么确定如果一家基地最多只能为几家超市供货等。）例3.（人员组织安排）随着电话银行等业务的开展，香港汇丰银行在美国的服务中心需要雇佣一批话务员处理相关业务。通过对以往数据的分析，发现一天中不同的时段打进电话的数量是不同的，通过估计从上午9时到下午5时每个小时的话务员需要量分别是10，12，14，16，18，17，15和10人。话务员可以使用全职雇员和临时雇员，全职雇员的薪水是每天120美元，临时雇员是每小时10美元。全职雇员从上午9时工作到下午5时，但中间有一个小时的休息时间。一般地，一半的雇员在11时开始休息，一半的雇员在12时休息。临时雇员每次是工作连续的四小时，中间没有休息时间。公司可用的全职雇员不超过12人。同时要求一半以上的工作由全职雇员完成。试给出一个人员的雇佣方案，使得公司所支付的薪水总数最少。（选择原因：难度适中的题目，处理中决策变量的选择需要适当的分析，此外全职雇员占一半的条件也是需要处理的。此外，例子的可扩充性也是选择的重要原因，比如可以仅仅给出每天打入电话的记录，估计需要的话务员的数量。）分析：雇佣的人员的多少决定了公司所支付的薪水数量，本题的目标是设计适当的雇佣方案，使得所支付的薪水最少。决定这个目标值的量就是两类雇员的数量，全职雇员的数量假设为x1，而临时雇员的数量为x2，目标函数可以容易的表达出来，即为120x1+10x2。当进一步考虑这些变量受到的约束时，我们发现有很大的困难，主要的原因就是临时雇员什么时候开始工作不能确定，而这个不能确定时，在不同时段人员需求的要求就不能满足。由于临时雇员时工作连续的四个小时，如果我们假定从9点开始上班的临时雇员数为x2，10点开始上班的临时雇员数为x3，11点开始上班的临时雇员数为x4，12点开始上班的临时雇员数为x5，下午1点开始上班的临时雇员数为x6，这时目标函数仍然能简单的表达出来，为12345612040()xxxxxx.每一个时段的人数为：在9-10时人数：x1+x2;在10-11时人数：x1+x2+x3;在11-12时人数：x1/2+x2+x3+x4;在12-1时人数：x1/2+x2+x3+x4+x5;在1-2时人数：x1+x3+x4+x5+x6;在2-3时人数：x1+x4+x5+x6;在3-4时人数：x1+x5+x6;在4-5时人数：x1+x6。因此关于满足不同时段人数要求的约束可以表达为1212312341234513456145615616101214/216/218171510xxxxxxxxxxxxxxxxxxxxxxxxxxxx还有一个约束是全职雇员人数不超过12人，也就是x1≤12。对于全职雇员完成一半以上的工作的约束，注意到总工作量为112人小时，而全职雇员平均工作时间为7小时，所以有x1≥8.当然，各种雇员的人数是非负的，因此还有一个非负约束。综上所述，我们可以得到本问题的线性规划模型如下：12345612123123412345134561456156161min12040()..101214/216/2181715108120,2,,6ixxxxxxstxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxi（8.3）8.3线性规划模型及求解在上一节中，我们通过几个例子说明线性规划模型的特点和建模过程，也清楚了规划问题的基本结构：线性规划具有一个目标函数，可以是寻找最大值（比如例题1）也可能是寻求最小值（比如例题2和3）；其次，问题包括若干个约束条件。这些目标函数和约束条件都是关于决策变量的线性函数，约束中可能还包括一类特殊的约束，比如三个例子中的最后一个约束，还有(8.3)的倒数第二个约束，称为决策变量的下界或上界。这类问题统称为线性规划问题。如果使用矩阵表达这些例子，比如例1，只要记432Tc，123Txxxx，231321.5A，3436b，111Aeq，20beq。则规划问题（8.1）可以表达为max..0TcxstAxbAeqxbeqx（8.4）对于一般的线性规划问题，有如下的形式：min..TcxstAxbAeqxbeqlbxub（8.5）其中Aeq和Beq是对应于线性等式约束的矩阵和右端向量，lb和ub是向量的下界和上界向量。解决上述问题的最常用的算法称为单纯型法（simplexalgorithm），该算法在1947年由美国数学家Danzig提出，被称为二十世纪最著名的十大算法之一。其基本思想如下：问题（8.5）的所有满足约束条件的点构成一个集合，称为问题的可行集。由于约束是一系列的线性等式和不等式构成，在几何上形成空间的一个凸的超立方体，问题的最优解如果存在，则一定可以在立方体的顶点取得。求解的过程是从立方体的一个顶点开始（称为初始点），在剩余的顶点中找目标函数值减小的顶点，这样就完成一次迭代，一直的重复这个过程直到不能目标值不能减小为止。关于算法的理论和具体的步骤，有兴趣的同学可以参考线性规划的相关著作。能解决线性规划问题的软件有多种，本书仅对两种非常常用的软件加以介绍，其中一个是Matlab，另一个是Lingo。本节主要介绍Matlab软件解决线性规划。Matlab使用Linprog.m程序求解