数学建模-线性规划.docx

第八章 线性规划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 = 4 x1 + 3 x2 + 2 x3。再看看这些决策变量有没有受到什么限制，根据题意，生产产品需要消耗原材料和工时，而这两种资源都有一定的限制，当生产x1, x2和x3个甲乙丙产品时，耗费的原材料A为2 x1 + 3 x2 + x3，由于可用于生产的原材料A为34，所以有约束2 x1 + 3 x2 + x3 34.对于原材料B，有约束x1 + x2 + x3 = 20.同样地，生产过程中受到工时的限制，有3 x1 + 2 x2 + 1.5 x3 36.最后，注意到生产的产品数量不可能是负数，也就是x1, x2和x3是非负的，因此我们得到如下的规划问题： （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）。为简单起见，假定每天基地生产蔬菜的总量和超市需求的总量相等，即。问如何制定调运方案，既可以满足供需关系，又使运输的顿公里数达到最少。（选择原因：运输问题是线性规划最常见的例子之一，也是可以扩充的任何使用的例子的基础，实际上这个例子中可以向很多方向扩展，比如蔬菜的种类有多种多样，蔬菜基地可以具有短暂的储存功能，超市也有一定的储存功能，但是蔬菜可能有较大的损坏，此外，超市的销售量也可能是随机的，所以，容易扩展到各种各样的和运输相关的问题）分析：同样地，我们明确我们的目标是运输的吨公里（有时也称为运费）最小，这个值和蔬菜基地和超市之间的距离和运输的量共同决定，其中蔬菜基地和超市的距离是确定的常量，而不同基地和超市之间的运输量是可控的量并且决定了最终的运费，因此应该选择基地i到超市j的运量xij作为决策变量（i = 1, 2, ., m， j = 1, 2, ., n）。这样可以写出运输的吨公里数.这些运输量显然的受到一些限制，比如从一个产地运向各个超市的运量之和不能超过该基地的产量，这类约束我们称为产地约束，于是有.此外，对于任何一家超市，来自与不同产地的蔬菜总量应该能够满足该超市的销售量，因此又有如下的约束.同时，注意到所有的运输量是非负的变量，于是可以得到下面的线性规划模型 （8.2）（关于问题的扩充：可以在练习题里面体现，比如两种货物，又比如一些基地和超市的对接限制等，又比如怎么确定如果一家基地最多只能为几家超市供货等。）例3. （人员组织安排）随着电话银行等业务的开展，香港汇丰银行在美国的服务中心需要雇佣一批话务员处理相关业务。通过对以往数据的分析，发现一天中不同的时段打进电话的数量是不同的，通过估计从上午9时到下午5时每个小时的话务员需要量分别是10，12，14，16，18，17，15和10人。话务员可以使用全职雇员和临时雇员，全职雇员的薪水是每天120美元，临时雇员是每小时10美元。全职雇员从上午9时工作到下午5时，但中间有一个小时的休息时间。一般地，一半的雇员在11时开始休息，一半的雇员在12时休息。临时雇员每次是工作连续的四小时，中间没有休息时间。公司可用的全职雇员不超过12人。同时要求一半以上的工作由全职雇员完成。试给出一个人员的雇佣方案，使得公司所支付的薪水总数最少。（选择原因：难度适中的题目，处理中决策变量的选择需要适当的分析，此外全职雇员占一半的条件也是需要处理的。此外，例子的可扩充性也是选择的重要原因，比如可以仅仅给出每天打入电话的记录，估计需要的话务员的数量。）分析：雇佣的人员的多少决定了公司所支付的薪水数量，本题的目标是设计适当的雇佣方案，使得所支付的薪水最少。决定这个目标值的量就是两类雇员的数量，全职雇员的数量假设为x1，而临时雇员的数量为x2，目标函数可以容易的表达出来，即为120 x1 + 10 x2。当进一步考虑这些变量受到的约束时，我们发现有很大的困难，主要的原因就是临时雇员什么时候开始工作不能确定，而这个不能确定时，在不同时段人员需求的要求就不能满足。由于临时雇员时工作连续的四个小时，如果我们假定从9点开始上班的临时雇员数为x2，10点开始上班的临时雇员数为x3，11点开始上班的临时雇员数为x4，12点开始上班的临时雇员数为x5，下午1点开始上班的临时雇员数为x6，这时目标函数仍然能简单的表达出来，为.每一个时段的人数为：在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。因此关于满足不同时段人数要求的约束可以表达为还有一个约束是全职雇员人数不超过12人，也就是x1 12。对于全职雇员完成一半以上的工作的约束，注意到总工作量为112人小时，而全职雇员平均工作时间为7小时，所以有x1 8.当然，各种雇员的人数是非负的，因此还有一个非负约束。综上所述，我们可以得到本问题的线性规划模型如下： （8.3）8.3 线性规划模型及求解 在上一节中，我们通过几个例子说明线性规划模型的特点和建模过程，也清楚了规划问题的基本结构：线性规划具有一个目标函数，可以是寻找最大值（比如例题1）也可能是寻求最小值（比如例题2和3）；其次，问题包括若干个约束条件。这些目标函数和约束条件都是关于决策变量的线性函数，约束中可能还包括一类特殊的约束，比如三个例子中的最后一个约束，还有(8.3)的倒数第二个约束，称为决策变量的下界或上界。这类问题统称为线性规划问题。如果使用矩阵表达这些例子，比如例1，只要记，。则规划问题（8.1）可以表达为 （8.4）对于一般的线性规划问题，有如下的形式： （8.5）其中Aeq和Beq是对应于线性等式约束的矩阵和右端向量，lb和ub是向量的下界和上界向量。 解决上述问题的最常用的算法称为单纯型法（simplex algorithm），该算法在1947年由美国数学家Danzig提出，被称为二十世纪最著名的十大算法之一。其基本思想如下：问题（8.5）的所有满足约束条件的点构成一个集合，称为问题的可行集。由于约束是一系列的线性等式和不等式构成，在几何上形成空间的一个凸的超立方体，问题的最优解如果存在，则一定可以在立方体的顶点取得。求解的过程是从立方体的一个顶点开始（称为初始点），在剩余的顶点中找目标函数值减小的顶点，这样就完成一次迭代，一直的重复这个过程直到不能目标值不能减小为止。关于算法的理论和具体的步骤，有兴趣的同学可以参考线性规划的相关著作。 能解决线性规划问题的软件有多种，本书仅对两种非常常用的软件加以介绍，其中一个是Matlab，另一个是Lingo。本节主要介绍Matlab软件解决线性规划。Matlab使用Linprog.m程序求解线性规划问题（8.5）的解。下面是Matlab软件的帮助文件对于该程序的说明： linprog min cTx s.t. Axb Aeqx beq lb x ub Solve a linear programming problem where c, x, b, beq, lb, and ub are vectors and A and Aeq are matrices. 调用格式:x = linprog(c,A,b,Aeq,beq) x = linprog(c,A,b,Aeq,beq,lb,ub) x = linprog(c,A,b,Aeq,beq,lb,ub,x0) x = linprog(c,A,b,Aeq,beq,lb,ub,x0,options) x,fval = linprog(.) x,fval,exitflag = linprog(.) x,fval,exitflag,output = linprog(.) x,fval,exitflag,output,lambda = linprog(.)上面的x,c,x,beq,lb,ub,A,Aeq的意义已经说明，这里的x0是迭代的初始点（可以给也可以不给），求解的结果x就是最优解，fval是对应的最优值。需要特别指出的是，Matlab对上述参数采用对号入座的形式，当你所要处理的问题中没有靠前的参数时，在对应的位置上用“ ”占位。当处理的问题是最大值问题时，可以通过目标函数乘以-1转变成为最小值问题。而在不等式约束中是”“的形式时，也用同样的方法统一成“”的形式。下面是前述三个例子的求解程序。例1：c=-4 3 2;A=2 3 1;3 2 1.5;b=34;36;Aeq=1 1 1;Beq=20;x,fval=linprog(c,A,b，Aeq，beq)输出的结果为：Optimization terminated.x = 2.0000 6.0000 12.0000fval = -50.0000注意：由于问题是计算最大值，所以将c乘上-1，转换成最小化问题，最优值是-50，也就是最大利润为50元。此外，应当注意，该Linprog在缺省情况下假定所以变量非负，所以最后一个约束不需要写出来。例3c=120 40 40 40 40 40;A=-1 1 0 0 0 0;1 1 1 0 0 0;1 1 1 1 0 0;0.5 1 1 1 1 0;0.5 0 1 1 1 1;1 0 0 1 1 1;1 0 0 0 1 1;1 0 0 0 0 1;b=-10;12;14;16;18;17;15;10;lb=8;0;0;0;0;0;ub=12;inf;inf;inf;inf;inf;x,fval=linprog(c,A,b,lb,ub)输出结果为：Optimization terminated.x = 8.0000 2.0000 4.1069 2.4839 3.4256 3.9836fval = 1.6000e+003 本题给出的结果并不非常满意，因为雇员的人员应该是整数，但上面的结果是小数。也就是说，实际上决策变量除了上面的限制之外，应该还有必须是整数的限制，否则就可能得到小数的结果。遗憾的是，现有版本的Matlab没有求解整数规划的功能，一个不规范但有时是有效的方法是固定一些量取成整数的方法继续求解，比如x6接近与4，因此固定x6 = 4，也就是增加一组等式约束的条件，重新求解，实际发现，问题的最优值不变，x3,x4,x5仍然是小数，再使用同样的方法可以得到整数解。具体的过程希望读者自己完成。但显然上面的方法没有一般性，特别是问题规模很大时。Lingo软件具有求解整数规划的功能，我们在后面将进行介绍。8.4 Lingo软件的线性规划解法 解决线性规划问题，除了Matlab之外，Lingo是一款很优秀的软件。实际上，Lingo能解决的规划问问远远不只是线性规划问题。相比于Matlab，Lingo有下面的一些有点和特点：（1）对于大规模问题，Lingo输入更加方便；（2）可以进行灵敏性分析；（3）适合求解整数规划问题；（4）求解问题的规模更大更快；（5），对于非线性，有时候得到的解优于Matlab。8.4.1 Lingo的描述线性规划问题 要了解Lingo程序，我们先从规划问题的特点出发。前面说过，规划问题包括决策变量，目标函数和约束条件，当然还有一些已知数据。编程的目的就是告诉计算机我们需要求解的问题具体形式是怎样的。也就是说要告诉计算机有那些已知数据，决策变量是什么，目标函数是什么，约束条件是什么。 比如我们来看前面的例1，只要在Lingo的编辑窗口中输入如下内容：图1这里基本上按照原始模型的数学表达直接输入，比如（1）对于计算最大值问题用“max”，当计算最小值问题时用“min”；（2）约束条件直接写在下面，一般每条语句占一行，以“；”结束；（3）对于不等式约束，大于等于直接使用“”，对于小于等于直接使用“”。（4）缺省情况下，决策变量为非负。 点击执行按钮，就可以得到下面的结果界面：图2第一行得到的结果是问题的全局最优解；第二行表示的目标函数的最优值是50；第三行说明问题经过2次的迭代得到最优解；随后的四行指明问题的最优解：x1，x2和x3分别取2，6和12时达到最大值50，此外，当变量是基变量时”Reduced Cost“值为0，反之，如果某个变量的值非0，则表示该变量增加一个单位是对于目标函数的增加值；最后的五行主要说明松紧性，其中最后三行分别说明三个约束都是紧约束（也就是松弛变量取值为0），”Dual Price“称为对偶价格， 表示右端向量的值增加是可以导致目标值的增加量。 上面的例子主要针对小规模的规划问题，但是在实际的计算中，Lingo提供了一种非常高效的描述规划问题的方式。 实际上，最优化问题都有非常规范的结构，包括目标函数和约束条件，而对于线性规划问题，目标函数和约束条件在形式上的规范性使得这样的问题容易用类似与程序的方式描述。下面是用另外一种方式描述的例子。也就是说，因为目标函数是价格参数和决策变量的线性和，因此在Lingo需要一个求和的运算，使用函数“sum()”。上面的第十二行表示需要计算的问题是最大化问题，目标函数是c(i)*x(i)关于i求和。这个对应于上面提到的目标函数。为了描述问题的三个约束条件，这里分别用第十三、十四和十五行语句分布描述。注意每一个约束的形式，比如第一个是线性和小于一个量的形式，因此仍然使用sum()语句，就是矩阵A的第一行元素乘以x的三个元素然后对i求和，求和的结果小于b(1)。后面的两个语句有类似的解释。因为用到带有结果的变量形式，因此需要定义数据集（相当数据类型）。这一部分由第二到第六五行语句定义，由“sets:”和“endsets”开头和结尾。第三行定义了一个数据集叫做price，这个数据集由三个分量构成（由“/1.3/”所定义），具体定义的变量有两个，即c和x。第四行定义了一个叫做rhs的数据集，也是一个三个分量构成，用于存放三个约束条件右端的元素，具体定义的变量为b。这里的另外一个数据集是“mat”，它由前面的两个数据集派生而成，其维数为前面两个数据集维数的乘积，具体定义的变量A，用以存放约束中的矩阵。第七到第十一行称为数据段，用以为模型的参数赋值。需要注意的是，所有的参数作为一个向量的形式赋值，不管是行向量，列向量还是矩阵（注意，矩阵的赋值是先第一行，然后第二行，一直到最后一行）。 上述看似复杂化的输入