运筹学-线性规划

第2章线性规划例1

穗羊公司的例子III每周可使用量A（千克）125B（吨）214C（百工时）439单位产品利润（万元）32问该公司每周应生产产品I与产品II各多少单位，才能使每周的获利达到最大？假设产品I、II每周的产量分别是x1和x2，得到如下的数学模型其中s.t.是英文词组subjectto的缩写，表示“受限制于”的意思，有时也约去不写出来。该问题常称为生产计划问题或产品组合（productmix）问题。例2

设有一批规格为10米长的圆钢筋，将它截成分别为3米，4米长的预制构件的短钢筋各100根，问怎样截取最省料？因为，10米长的钢筋截为3米或4米长，共有三种截法：截法Ⅰ：3331米截法Ⅱ：3340米截法Ⅲ：4402米假设按截法Ⅰ，Ⅱ，Ⅲ各截取10米长的钢筋分别为x1,x2,x3根则可以获得3米长的短钢筋的根数是3x1+2x2

4米长短钢筋的根数是x3+2x2

按问题要求它们应该不小于100根。总共用料是x1+x2

+x3要达到最省料的目的，就必须使总用料最小。例2的模型就是例2中的问题常称为下料问题。线性规划的三个要素：决策变量目标函数约束条件其次线性规划模型必须满足如下两个要求：目标函数必须是决策变量的线性函数；约束条件必须是含决策变量的线性等式或不等式。2.2线性规划的图解法

对只包含两个决策变量的线性规划问题，可以用图解法来求解。图解法顾名思义就是通过作图来求解的方法，它简单直观、并有助于说明一般线性规划问题求解的基本原理。有关概念可行解：

我们将满足线性规划问题的所有约束条件的变量x1和x2的一组取值称为线性规划问题的一个可行解。通常用X表示。最优解：

因此我们求解线性规划问题，就是要求使得目标函数取最优值（对例1，就是取最大值）的可行解，这样的可行解就称为线性规划问题的最优解。通常用X*表示。最优值：

通常用z*表示可行域：

我们将可行解的集合称为可行域。图解法步骤:建立平面直角坐标系图示约束条件,求可行域图示目标函数求最优解建立平面直角坐标系（通常只画第一象限），并画出第一条约束直线

可行域图示目标函数（画出等值线）等值线向右上方移动，函数值变大。在其即将离开可行域时达到B（3/2,1）点。所以最优解为：此时最优值为：2.2.2线性规划求解的可能结局1、有唯一的最优解2、有无穷多个最优解（将目标函数改为z=4x1+3x2

）3、无界解

指线性规划问题有可行解，但是在可行域，目标函数值是无界的，因而达不到有限最优值。因此线性规划问题不存在最优解。4、无可行解

指找不到一组变量能满足线性规划的所有约束条件的情况，也就是线性规划问题不存在可行解，或者说可行域是空集。例如线性规划问题：另外两个重要的结论：线性规划问题可行域若不是空集，则它是一个凸集；线性规划问题的最优解若存在，则一定可以在其可行域的一个顶点上达到。2.3线性规划模型的一般形式和标准形式

为了讨论一般的线性规划问题的求解。我们先给出线性规划模型的一般形式如下：

2.3.1线性规划的一般模型这里一共包含有n个决策变量，m个约束条件；对目标函数既可以求最大的也可以求最小；约束方程有<=,>=,=；决策变量通常非负，但也可以有其它情况；cj:称为价值系数；bi:资源常数（右端向量）Aij称为技术系数、工艺系数在今后的讨论中，为方便起见，还将用到线性规划模型一般形式的各种简写的形式。利用和号“”，线性规划模型的一般形式可写为：利用向量，可以将一般形式表示为：其中在今后的讨论，常将矩阵称为线性规划问题的（约束条件）系数矩阵。明显地系数矩阵与矩阵之间存在关系：用矩阵的记号可以将线性规划模型一般形式写成：其中同上，而矩阵是由各约束条件的系数（技术系数）构成的矩阵：2.3.2线性规划的标准形式它具有如下四个特征：目标函数求max；约束方程符号取“=”；bi非负；所有决策变量xj非负。2.3.3将线性规划的模型化为标准形式1、目标函数求最小值的情形

取原目标函数的相反数为新的目标函数，对原目标函数求最小值的问题就等价于对这一新的目标函数求最大值的问题。例如：等价于

2、约束条件为不等式

(a)转化为xs表示决策中尚未使用的那部分资源，因此称这一变量为松弛变量。（b）转化为：它表示决策结果超过了实际需要的部分，因此常称它为剩余变量。无论是松弛变量还是剩余变量在决策中都不产生实际价值，因此它们在目标函数中的系数都应该为零。在后面的讨论中，有时也将松弛变量和剩余变量统称为松弛变量。3、约束条件右端常数为负数只需将这一约束条件两端同乘“-1”就可化为一个等价的约束条件，其右端常数满足标准形式的要求。4、决策变量不满足非负约束

（a）

（b）如x3无约束，则令例如，将例1中的线性规划模型化为标准形式就是：其中就是分别对第一、第二、第三个约束条件中添加的松弛变量。

例3化如下的线性规划问题模型为标准形式。

(1)变量是非正的，所以要将模型中的所有都用代替，其中(2)变量无约束，因此取两个变量使得。在模型中，所有的都用代替。

(5)约束条件2是“”型的，因此需要在左边加上一个松弛变量化为等式，即”型的，并且右端的常数小于零。(3)目标函数是求最小值的，因此令，即(4)约束条件1是“然后在两端乘以-1得也就是因此先将其左边减取一个剩余变量使它化为等式：也就是。从而得到模型的标准形式为2.4线性规划解的基本概念与性质在本节，我们主要考虑模型具有标准形式的线性规划问题（2.6）线性规划问题解的概念及性质对于线性规划问题（2.6）来说，可行解实际上是由约束条件构成的线性方程组（常称为约束方程组）的解，并且还满足非负约束条件，即各个决策变量都取非负值：。

对于线性规划问题（2.6），可以证明如下的结论：定理2.1

线性规划问题的可行域如果不是空集，就一定是凸集。凸集:指一个非空集，并且以其中任意两个点为端点的直线段上的所有点都属于该集合。顶点：在凸集中，如果一个点不位于其他两点为端点的线段的内部，则称其为该凸集的顶点。例如上图中第一个凸集的A点，或第二个凸集的B点，分别是相应的凸集的顶点。哪个是凸集呢？今后我们将A的任一个具有这样的特征的子矩阵B称为线性规划问题（2.6）的一个基。也就是说线性规划问题的基就是矩阵A的一个我们将约束方程组的系数矩阵称为线性规划问题的系数矩阵，并且总假定其秩等于其行数：。这意味着系数矩阵的各行是线性无关的，这也表明约束方程中的各个方程是相互独立的。且行列式不为零的子矩阵。

例如，对于线性规划问题其系数矩阵为则下面两个矩阵都是该线性规划问题的基。和还能找出其它基吗？例如，对上面的线性规划问题，若我们考虑基则线性规划问题的基变量就是x2和x4，而x1和x3就是非基变量。但如果我们考虑的基是则基变量是x1和x2，非基变量是x3和x4。可见在线性规划问题中所谓基变量就是由m个变量构成的一组变量，其系数构成的行列式不等于零；反之满足系数行列式不等于零的一组m个变量，就是基变量。基解：令非基变量等于0的解。基可行解：基解+可行解例如，对于上面的线性规划问题，如果取x1，x2为基变量，则令非基变量x3，x4为零，约束方程组为

解之得。故我们得到基解注意到这个基解还是一个可行解。是否所有的基解都是基可行解？（选x1,x3作为基变量）

定理2.2：

线性规划问题的基可行解是其可行域的顶点。定理2.3：

线性规划问题的最优解如果存在，则一定有一个基可行解是最优解。2.6单纯形法计算基本思路：首先求出初始基本可行解判断其是否为最优解如果不是最优，则迭代到其相邻的基本可行解，并再次检验求解如下线性规划首先转化为标准形式以x3,x4,x5作为初始基变量得到初始单纯形表如下所示：32000CBXBx1x2x3x4x5b000x3x4x5124213100010001549320000该初始单纯形表对应的初始解为X=（0，0，5，4，9）T。对应函数值为0.因为x1的检验数我们选择x1作为换入变量。解方程得到：为了保证x3,x4,x5非负所以选择x4作为换出变量。以x3,x1,x5作为基变量得到第二张单纯形表如下所示：32000CBXBx1x2x3x4x5b000x3x4x5124213100010001549320000该元素称为主元。下面开始迭代，迭代的目标就是把主元化为1，然后把主元所在列其他系数化为0。x13321/201/210003/21-1/200010-21101/20-3/260该初始单纯形表对应的基可行解为X=（2，0，3，0，1）T，对应函数值为6。现在x2的检验数为1/2>0，且最大，所以我们选择x2为换入变量。因为min{3/(3/2),2/(1/2),1/1}=1,所以选择x5作为换出变量。以x3,x1,x2作为基变量得到第三张单纯形表如下所示：32000CBXBx1x2x3x4x5b030x3x1x50103/21/21100-1/21/2-200132101/20-3/2062x2010-21100015/2-3/23/231003/2-1/23/2000-1/2-1/213/2

现在所有的检验数都小于或者等于0，所以得到最优解为：

最优函数值为13/2。该表称为最终单纯形表，其具有什么特征？合并的单纯形表32000CBXBx1x2x3x4x5b000x3x4x51[2]42131000100015495/14/29/4320000030x3x1x50103/21/2[1]100-1/21/2-200132124101/20-3/206032x3x1x20100011005/23/2-2-3/2-1/213/23/21000-1/2-1/213/2单纯形法计算过程构造初始单纯形表对标准化后的线性规划问题，首先找出初始基变量，构造初始单纯形表，其中检验数由（2.18）计算。相应地可以得到初始基可行解，基可行解的目标函数值。最优性检验若得到单纯形表中所有的检验数都小于或等于零，则该单纯形表给出的基可行解就是最优解，终止计算。否则进行下一步。确定换入变量选择最大的正检验数对应的非基变量为换入变量。确定换出变量若换入变量（更一般地，若某个正检验数对应的变量）所作列的系数均小于或等于零，则线性规划问题为无界解，终止计算。否则用换入变量所作列的系数去除b列的对应数，在除得的商中选择最小者对应的基变量为换出变量。旋转运算确定换入和换出变量后得到新的基变量，然后以换入变量所在列、换出变量所在行交叉处的元素为主元，通过矩阵的初等行变换（一般不使用交换两行的运算）将约束方程组增广矩阵中主元变换为1，主元列的其它元素变换为零。从而得到一个新的单纯形表。然后回到第2步。例2.4利用单纯形法求解下列线性规划问题首先将线性规划标准化很明显可以以x4、x5作为初始基变量，得到初始单纯形如下：-21200CBXBx1x2x3x4x5b00x4x532-2-1-21100114-21200此时，x2的检验数大于0，还没有得到最优解。但是我们以x2作为换入变量，但是x2所在列所有系数都小于0，此时该线性规划存在无界解。例2.5求解如下线性规划问题注意该问题已经满足标准形式的要求，而且可以找到初始基变量x1、x3、x6，只是他们在目标函数中的系数不为0。例2.5的单纯形表1-110-30

CBXBx1x2x3x4x5x6b

1x1120-2005

1x3011-12063.000x60201[3]182.670-403-5011

1x11[2]0-20052.51x30-1/31-5/30-2/32/3-3x502/301/311/38/340-2/3014/305/3-7/3-1x21/210-1005/21x31/601-20-2/33/2-3x5-1/300111/311/300405/3-42.7单纯形法的进一步讨论例2.6考虑如何求解线性规划问题首先将其标准化得到：将约束方程添加人工变量得到：2.7.1大M法将人工变量在目标函数中反映出来得到如下形式的线性规划：-231000-M-MCBXBx1x2x3x4x5x6x7x8b-Mx7[2]-12-100101-Mx82210-100120x6-121001004-2+4M3+M1+3M-M-M000-2x11-1/21-1/2001/201/2-Mx80[3]-11-10-1110x603/22-1/2011/209/202+3M3-M-1+M-M01-M0-2x110[5/6]-1/3-1/601/31/62/33x201-1/31/3-1/30-1/31/31/30x6005/2-11/211-1/24008/3-5/32/30-M+5/3-M-2/3-231000-M-MCBXBx1x2x3x4x5x6x7x8b1x36/501-2/5-1/502/51/54/53x22/5101/5-2/50-1/52/53/50x6-3000[1]10-12-22/500-1/57/50-M+1/5-M-3/51x33/501-2/501/52/506/53x2-4/5101/502/5-1/507/50x5-3000110-12-1/500-1/50-7/5-M+1/5-M27/5。为了减少计算工作量，红色阴影部分可以不写！因此最优解为最优目标函数值为需要说明的是，如果在用大M法求解线性规划问题时，最终表的基变量中还含有人工变量，那么这个最终表并没有给出原来问题的基可行解，从而没有给出原来的线性规划问题最优解。这时原来线性规划问题为无可行解。用EXCEL执行该计算过程2.7.2两阶段法求解如下LP:第一阶段：求解辅助的线性规划问题

00000011

CBXBx1x2x3x4x5x6x7x8b1x7[2]-12-1001011x82210-100120x6-121001004

-4-1-311000

0x11-1/21-1/2001/201/21x80[3]-11-10-1110x603/22-1/2011/209/2

0-31-11020

0x1105/6-1/3-1/601/31/62/30x20