第四章 线线性规规划 引言v 什么是线性规划 如果最优化问题三要素中的目标函数和约束条件都是线性的，则该最优化问题 称为线性规划问题 v 线性规划的应用和发展 线性规划（Linear Programming，简写成LP）是最优化理论和方法中的重要领 域之一。其理论上的完整性、方法上的有效性以及应用上的广泛性，较其他分 支都成熟的多，同时很多实际问题都可以转化为线性规划来解决 线性规划的要点就是在满足线性约束条件的前提下，使预定的线性目标函数达 到最优。现在线性规划已不仅仅是一种数学方法，在理论上，它启发了诸如对 偶、凸性等最优化理论的核心概念，在实际中更是大量被运用于经济学和管理 学领域，成为科学决策的一个有效手段 乔治丹齐格（G. B. Dantzig）被认为是线性规划之父。自从1947年他提出求解 线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在应用上也日益深 入，成为科学与工程领域广泛应用的数学模型。特别是在计算机能处理海量约 束条件和设计变量的线性规划问题之后，线性规划就更加受到青睐线性规划的典型实例v 运输问题 设有两个建材厂C1和C2，每年沙石的产量分别为35万吨和55万吨，这些沙石需 要供应到W1、W2和W3三个建筑工地，每个建筑工地对沙石的需求量分别为26 万吨、38万吨和26万吨，各建材厂到建筑工地之间的运费（万元/万吨）如表所 示，问题是应当怎么调运才能使得总运费最少？ 运费 工地建材厂W1W2W3C110129 C281113线性规划的典型实例v 运输问题 问题分析 假设xij代表建材厂Ci运往建筑工地Wj的数量（万吨），则各建材厂和工地之间的运量 可以用下表来表示 目标函数即为总运费 建材厂C1、 C2的输出量应分别为建材厂C1、 C2的产量 各工地的沙石需求量应当为从各建材厂接收到沙石的总量 运输量xij为一非负值 分配量 工地（万吨） 建材厂W1W2W3输出总 量C1x11x12x1335 C2x21x22x2355 接收总量26382690线性规划的典型实例v 运输问题 数学模型v 线性规划问题的特征 均可以用一组设计变量来表示一种实施方案 每个问题都有一定的约束条件，这些条件可以用一组线性等式或者线性不等式 表达 在上述前提下，一般都有一个目标函数，该函数用于衡量方案的优劣，可以表 达为设计变量的一个线性函数，我们的目的一般为使得目标函数达到最大值或 者最小值线性规划问题的标准型 v 线性规划问题的一般标准型 根据线性规划的定义，线性规划问题即求取设计变量x=x1, x2, xnT的值，在 线性约束条件下使得线性目标函数达到最大，线性规划问题的一般标准型为：其中，ci 、aij 、bi 为给定的常数v 线性规划问题的标准型的特点 目标函数为设计变量的线性函数，且需要极大化； 约束条件为设计变量的一组线性等式，也称为约束方程组； 设计变量x1, x2, xn都有非负限制。线性规划问题的标准型v 线性规划问题的矩阵标准型 利用向量或矩阵符号，线性规划问题的标准型还可以用矩阵形式表达： 其中 为n维行向量 为mn维矩阵为m维列向量为n维列向量 是指其各分量 线性规划问题的标准型v 不同类型的非标准型化为标准型的方法 问题为极小化目标函数 设原有线性规划问题为极小化目标函数 则可设将极小化目标函数问题转化为极大化目标函数问题 约束条件为不等式如果原有线性规划问题的约束条件为不等式，则可增加一个或减去一个非负变量，使约束 条件变为等式，增加或减去的这个非负变量称为松弛变量。例如，假如约束为则可以在不等式的左边增加一个非负变量xn+1，使不等式变为等式 如果约束为 则可在不等式的左边减去一个非负变量xn+1，使不等式变为等式 模型中的某些变量没有非负限制若对某个变量xj并无限制，取值可正可负，这时可设两个非负变量 和 ，令注意到，因为对原设计变量进行了代换，还需要将代换式代入目标函数和其他约束条件 做相应的代换，这样就可以满足线性规划标准型对变量非负的要求线性规划问题的标准型v 例子 将线性规划模型标准化 将目标函数两边乘上-1转化为求极大值 原问题的约束条件中的前两个条件均为不等式，在第一个不等式的左边加上一个松 弛变量x4，在第二个不等式的左边减去一个松弛变量x5，将两者转化为等式约束 原问题对设计变量x3没有非负限制，故在此引入非负变量 和 ，令 经过上述步骤整理后的标准型为 线性规划问题中解的概念 v 概述 为了帮助分析线性规划求解过程，先介绍线性规划解的概念。仍然考虑式(4-2) 中的线性规划的矩阵标准型： 求解上述线性规划问题实际上就是要求出向量x=x1,x2,xnT使其满足Ax=b和 x0，且目标函数f达到最大值，这个向量称为线性规划问题的解。 当求解Ax=b时，假设独立方程的个数为m个，设计变量的维数为n，根据线性 代数的知识，如果m=n，则方程有唯一解，无优化的自由度；如果mn，方程 个数大于未知数的个数，则有些约束可能不能被满足，上述两类问题不在我们 探讨的范围之列，也就是我们仅讨论mm)，则基本解的数量小于或等于 基本解不是线性规划问题的解，而是仅满足约束方程组的解 线性规划问题中解的概念v 可行解、可行域 上面的分析仅考虑了约束方程组Ax=b，下面进一步考虑线性规划问题的非负约 束。我们称既满足约束方程组Ax=b，又满足非负约束x0的解为线性规划问题 的可行解，即可行解满足线性规划问题的所有约束。可行解的集合称为可行域 ，记作：v 基本可行解 特别的，若线性规划问题的基本解能够满足线性规划问题中的非负约束，即：则称该解xB为基本可行解，简称基可行解，称B为可行基。基可行解的数量不会 超过 个。显然，基本可行解一定是可行解，基可行解是可行域中一种特殊的 解 v 最优解 能使得线性规划问题的目标函数值达到最大的可行解称为最优解。线性规划问 题中的最优解，一定可以在基可行解中找到，而基可行解的数量是有限的，因 而这就在理论上保证了可以在有限的步骤之内求出线性规划问题的最优解。 线性规划问题中解的概念v 实例线性规划标准型为 于是取矩阵A的线性无关列P1和P2构成2阶非奇异子矩阵 ，B1是线性规划问题的一个基矩阵，与其对应的基变量为x1和x2，即 ，相应的非基矩阵和非基变量分别为令非基变量x3=0，可以求出对应基矩阵B1的基本解为 ，基矩阵B1解向量的各分量均为非负 ，故是线性规划问题的基本可行解。如果这个解可以使得目标函数取得最大值则该解为最优解。是否 最优解的判断方法将在后续的章节中探讨。若取矩阵A的后两个线性无关列P2和P3，构成线性规划的另一个基矩阵用相同的方法进行分析，可知，此时的基变量为x2和x3，非基变量为x1，于是令x1=0，可以得到对应基 矩阵B2的一组基本解为： ，由于对应基矩阵B2解向量的第二个分量即x3为负，故该 解不是线性规划问题的基本可行解 由理论分析可知，该线性规划问题基本解的个数为3个，也就是还可以选取P1和P3构成基矩阵B3，求 取该问题的第三个基本解，只要有一个基矩阵，就可以求出一个对应的基本解，至于该基本解是否基 本可行解和最优解则需要进一步判断。线性规划问题的图解法 v 用图解法求解如下二维线性规划问题 分析可行域 引入平面直角坐标系，以x1作为横轴，以x2作为纵轴，由于线性规划问题满足非负条 件x1, x20，故问题的探讨局限在平面直角坐标系的第一象限 分析x1-2x24，取直线x1-2x2=4，则直线上的点和直线以上的区域满足该不等式 分析x1+2x28，取直线x1+2x2=8，则直线上的点和直线以下的区域满足不等式 于是可行域为四边形ACBO内的区域（包括边界上的点），在图中用阴影表示 分析最优解 分析目标函数f =x1+x2，可以将其改写成为x2=-x1+ f 可以发现改写后的方程是以f为参量，以-1为斜率的一族平行的直线，这些平行线越向右上方移动，离原点越远，对应的目标函数值就越大。当直线运动到经过点C时，即不能再继续向上移动，否则将脱离线性规划问题的可行域，故线性规划问题在点C达到最大值 线性规划问题求解的单纯形法v 理论基础 称T(B)为对应于基B的单纯形表，b0j (j=1,2n)称为检验数 线性规划问题最优解的判定 若T(B)中所有检验数b0j 0 (j=1,2n) ，则xB=B-1b-B-1NxN是最优解。 若T(B)中有某一个检验数b0,m+s ”的约束形式，则我们需要通过添加松弛变量使得 不等式约束变为等式约束 之后，我们只需要将所有的约束（包括不等式约束和等式约束）转化为矩阵形式的 即可线性规划问题的MATLAB求解v 将问题转化为MATLAB标准型原问题是对目标函数求极大，故添加负号使目标变为：min f=-4x1+2x2-x3 原问题中存在“”的约束条件，故添加负号使其变为8x1-2x2+2x3-8将约束整理为矩阵形式用MATLAB表达则为c=-4; 2; -1;%将目标函数转化为求极小 A=2 -1 1; 8 -2 2; b=12; -8; %不等式约束系数矩阵 Aeq=-2 0 1; 1 1 0;beq=3; 7;%等式约束系数矩阵 lb=0; 0; 0;ub=Inf; Inf; Inf %对设计变量的边界约束线性规划问题的MATLAB求解v 函数调用格式 MATLAB优化工具箱中求解线性规划问题的命令为linprog，其函数调用方法有 多种形式如下所示x = linprog(c,A,b)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 = linprog(problem)x,fval = linprog(.)x,fval,exitflag = linprog(.)x,fval,exitflag,output = linprog(.)x,fval,exitflag,output,lambda = linprog(.)线性规划问题的MATLAB求解v 输入参数 MATLAB工具箱中的linprog函数在求解线性规划问题时，提供的参数为：模型 参数、初始解参数和算法控制参数。 模型参数x、c、lb、ub、b、beq、A和Aeq在MATLAB标准型中已经介绍了其具体物 理意义和获得方法 x0为线性规划问题的初始解，该设置仅在中型规模算法中有效，而在默认的大型规 模算法和单纯形算法中，MATLAB将忽略一切初始解。 options为包含算法控制参数的结构变量，我们可以通过optimset命令对这些具体的控 制参数进行设置，例如下述格式options = optimset(param1,value1,param2,value2,.)该命令格式创建一组控制参数结构变量options，将参