项目数据分析师 - 运筹学之线性规划

1、项目数据分析师 -运筹学之线性规划线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支 数学规划， 而线性规划 (Linear Programming 简记 LP) 则是数学规划的一个重要分支。自从 1947 年 G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线线性规划划的实例例与定义义 例 1 某某机床厂厂

2、生产甲甲、乙两两种机床床，每台台销售后后的利润润分别为为 40000 元与 30000 元元。生产产甲机床床需用 A 、 B 机机器加工工，加工工时间分分别为每每台 22 小时时和 11 小时时；生产产乙机床床需用 A 、 B 、 C 三种种机器加加工，加加工时间间为每台台各一小小时。若若每天可可用于加加工的机机器时数数分别为为 A 机器 10 小时、 B 机器器 8 小时和和 C 机器 7 小小时，问问该厂应应生产甲甲、乙机机床各几几台，才才能使总总利润最最大？ 上述问题的的数学模模型：设设该厂生生产台甲甲机床和和乙机床床时总利利润最大大，则应应满足 这里变量称称之为决决策变量量，（ 1 ）

3、式式被称为为问题的的目标函函数，（ 2 ）中中的几个个不等式式是问题题的约束束条件，记记为 ss.t.( 即即 suubjeect to) 。上上述即为为一规划划问题数数学模型型的三个个要素。由由于上面面的目标标函数及及约束条条件均为为线性函函数，故故被称为为线性规规划问题题。 总之，线性性规划问问题是在在一组线线性约束束条件的的限制下下，求一一线性目目标函数数最大或或最小的的问题。 在解决实际际问题时时，把问问题归结结成一个个线性规规划数学学模型是是很重要要的一步步，但往往往也是是困难的的一步，模模型建立立得是否否恰当，直直接影响响到求解解。而选选取适当当的决策策变量，是是我们建建立有效效模

4、型的的关键之之一。 1.2 线线性规划划的 MMatllab 标准形形式 线性规划的的目标函函数可以以是求最最大值，也也可以是是求最小小值，约约束条件件的不等等号可以以是小于于号也可可以是大大于号。为为了避免免这种形形式多样样性带来来的不便便， MMatllab 中规定定线性规规划的标标准形式式为 1.3 线线性规划划问题的的解的概概念 一般线性规规划问题题的标准准型为 可行解 满满足约束束条件（ 4 ）的的解 ) , , , ( 2 11 n x xx x x LL = ，称为为线性规规划问题题的可行行解，而而使目标标函数（ 3 ）达达到最小小值的可可行解叫叫最优解解。 可行域 所所有可行行

5、解构成成的集合合称为问问题的可可行域，记记为 RR 。 1.4 线线性规划划的图解解法 图解法简单单直观，有有助于了了解线性性规划问问题求解解的基本本原理。我我们先应应用图解解法来求求解例 1 如如上图所所示，阴阴影区域域即为 LP 问题的的可行域域 R 。对于于每一固固定的值值，使目目标函数数值 zz 等于于的点构构成的直直线称为为目标函函数等位位线，当当 z 变动时时，我们们得到一一族平行行直线。让让等位线线沿目标标函数值值减小的的方向移移动，直直到等位位线与可可行域有有交点的的最后位位置，此此时的交交点（一一个或多多个）即即为 LLP 的的最优解解。 对于例 11 ，显显然等位位线越趋趋

6、于右上上方，其其上的点点具有越越大的目目标函数数值。不不难看出出，本 例的最优解解为，最最优目标标值 。 从上面的图图解过程程可以看看出并不不难证明明以下断断言： （ 1 ）可可行域 R 可能能会出现现多种情情况。 R 可能能是空集集也可能能是非空空集合，当当 R 非空时时，它必必定是若若干个半半平面的的交集（除除非遇到到空间维维数的退退化）。 R 既可可能是有有界区域域，也可可能是无无界区域域。 （ 2 ）在在 R 非空时时，线性性规划既既可以存存在有限限最优解解，也可可以不存存在有限限最优解解（其目目标函数数值无界界）。 （ 3 ） R 非非空且 LP 有有限限最优解解时，最最优解可可以唯

7、一一或有无无穷多个个。 （ 4 ）若若线性规规划存在在有限最最优解，则则必可找找到具有有最优目目标函数数值的可可行域 R 的“顶顶点”。 上述论断可可以推广广到一般般的线性性规划问问题，区区别只在在于空间间的 nn维数。在在一般的的 n 维空间间中，满满足一线线性等式式的点集集被称为为一个超超平面，而而满足一一线性不不等式 的点集被称称为一个个半空间间（其中中 为一一 n 维行向向量， b 为为一实数数）。有有限个半半空间的的交集被被称为多多胞形，有有界的多多胞形又又被称为为多面体体。易见见，线性性规划的的可行域域必为多多胞形（为为统一起起见，空空集 也被被视为多多胞形）。 在一般 nn 维空

8、空间中，要要直接得得出多胞胞形“顶顶点”概概念还有有一些困困难。二二维空间间中的顶顶点可以以看成为为边界直直线的交交点，但但这一几几何概念念的推广广在一般般 n 维空间间中的几几何意义义并不十十分直观观。为此此，我们们将采用用另一途途径来定定义它。 定义 1 说明凸凸集中任任意两点点的连线线必在此此凸集中中；而定定义 22 说明明，若 x 是凸凸集 RR 的一一 个极点，则则 x 不能位位于 RR 中任任意两点点的连线线上。不不难证明明，多胞胞形必为为凸集。同同样也不不难 证明，二维维空间中中可行域域 R 的顶点点均为 R 的极极点（ R 也没没有其它它的极点点）。 1.5 求求解线性性规划的

9、的 Maatlaab 解解法 单纯形法是是求解线线性规划划问题的的最常用用、最有有效的算算法之一一。单纯纯形法是是首先由由 Geeorgge DDanttzigg 于 19447 年年提出的的，近 60 年来，虽虽有许多多变形体体已被开开发，但但却保持持着同样样的基本本观念。由由于有如如下结论论：若线线性规划划问题有有有限最最优解，则则一定有有某个最最优解是是可行区区域的一一个极点点。基于于此，单单纯形法法的基本本思路是是：先找找出可行行域的一一个极点点，据一一定规则则判断其其是否最最优；若若否，则则转换到到与之相相邻的另另一极点点，并使使目标函函数值更更优；如如此下去去，直到到找到某某一最优

10、优解为止止。这里里我们不不再详细细介绍单单纯形法法，有兴兴趣的读读者可以以参看其其它线性性规划书书籍。下下面我们们介绍线线性规划划的 MMatllab 解法。 Matlaab5.3 中中线性规规划的标标准型为为 基本函数形形式为 linnproog(cc,A,b) ，它的的返回值值是向量量 x 的值。还还有其它它的一些些函数调调用形式式（在 Mattlabb 指令令窗运行行 heelp linnproog 可可以看到到所有的的函数调调用形式式），如如： x,fvval=liinprrog(c,AA,b,Aeqq,beeq,LLB,UUB,XX 0 ,OPPTIOONS) 这里 fvval 返回

11、目目标函数数的值， Aeqq 和 beqq 对应应等式约约束 bbeq x AAeq = * ， LB 和 UUB 分分别是变变量 xx 的下下界和上上界， x 0 是 xx 的初初始值， OPTTIONNS 是是控制参参数 . 例 2 求求解下列列线性规规划问题题 解（ i ）编写写 M 文件 c=2;3;-5; a=-22,5,-1; bb=-110; aeq=1,11,1; beq=77; x=linnproog(-c,aa,b,aeqq,beeq,zzeroos(33,1) valuee=c*x （ ii ）将 M 文文件存盘盘，并命命名为 exaamplle1.m 。 （ iiii ）在在 Maatlaab 指指令窗运运行 eexammplee1 即即可得所所求结果果。 例 1 求求解线性性规划问问题 解编写 MMatllab 程序如如下： c=2;3;11; a=1,4,22;3,2,00; b=8;6; x,y=liinprrog(c,-a,-b,zzeroos(33,1) 1.6 可可以转化化为线性性