《运筹学》线性规划（课堂PPT）

第2章线性规划,1,例1穗羊公司的例子,问该公司每周应生产产品I与产品II各多少单位，才能使每周的获利达到最大？,2,假设产品I、II每周的产量分别是x1和x2，得到如下的数学模型,其中s.t.是英文词组subjectto的缩写，表示“受限制于”的意思，有时也约去不写出来。,该问题常称为生产计划问题或产品组合（productmix）问题。,3,例2设有一批规格为10米长的圆钢筋，将它截成分别为3米，4米长的预制构件的短钢筋各100根，问怎样截取最省料？,因为，10米长的钢筋截为3米或4米长，共有三种截法：截法：3331米截法：3340米截法：4402米假设按截法，各截取10米长的钢筋分别为x1,x2,x3根,则可以获得3米长的短钢筋的根数是3x1+2x2,4米长短钢筋的根数是x2+2x3,按问题要求它们应该不小于100根。,总共用料是x1+x2+x3,要达到最省料的目的，就必须使总用料最小。,4,例2的模型就是,例2中的问题常称为下料问题。,5,线性规划的三个要素：决策变量目标函数约束条件,其次线性规划模型必须满足如下两个要求：目标函数必须是决策变量的线性函数；约束条件必须是含决策变量的线性等式或不等式。,运筹学建模步骤:识别问题定义决策变量建立约束条件建立目标函数,6,2.2线性规划模型的一般形式和标准形式,为了讨论一般的线性规划问题的求解。我们先给出线性规划模型的一般形式如下：,2.2.1线性规划的一般模型,7,这里一共包含有n个决策变量，m个约束条件；对目标函数既可以求最大的也可以求最小；约束条件有,=型；决策变量通常非负，但也可以有其它情况；cj:称为价值系数；bi:资源常数（右端常数）aij称为技术系数、工艺系数,8,在今后的讨论中，为方便起见，还将用到线性规划模型一般形式的各种简写的形式。利用和号“”，线性规划模型的一般形式可写为：,9,利用向量，可以将一般形式表示为：,其中,10,在今后的讨论，常将矩阵称为线性规划问题的（约束条件）系数矩阵。明显地系数矩阵与矩阵之间存在关系：,用矩阵的记号可以将线性规划模型一般形式写成：,其中同上，而矩阵是由各约束条件的系数（技术系数）构成的矩阵：,11,2.2.2线性规划的标准形式,它具有如下四个特征：目标函数求max；约束条件两端用“=”连结；bi非负；所有决策变量xj非负。,12,2.2.3将线性规划的模型化为标准形式,1、目标函数求最小值的情形取原目标函数的相反数为新的目标函数，对原目标函数求最小值的问题就等价于对这一新的目标函数求最大值的问题。,例如：,等价于,13,2、约束条件为不等式(a),转化为,xs表示决策中尚未使用的那部分资源，因此称这一变量为松弛变量。,（b）,转化为：,它表示决策结果超过了实际需要的部分，因此常称它为剩余变量。无论是松弛变量还是剩余变量在决策中都不产生实际价值，因此它们在目标函数中的系数都应该为零。在后面的讨论中，有时也将松弛变量和剩余变量统称为松弛变量。,14,3、约束条件右端常数为负数只需将这一约束条件两端同乘“-1”就可化为一个等价的约束条件，其右端常数满足标准形式的要求。,4、决策变量不满足非负约束（a）,（b）如x3无约束，则令,15,例如，将例1中的线性规划模型化为标准形式就是：,其中就是分别对第一、第二、第三个约束条件中添加的松弛变量。,16,例3化如下的线性规划问题模型,为标准形式。,(1)变量,是非正的，所以要将模型中的所有,都用,代替，其中,(2)变量,无约束，因此取两个变量,使得,。在模型中，所有的,都用,代替。,。在模型中，所有的,17,(5)约束条件2是“,”型的，因此需要在左边加上一个松弛变量,化为等式，即,”型的，并且右端的常数小于零。,(3)目标函数是求最小值的，因此令,，即,(4)约束条件1是“,然后在两端乘以-1得,也就是,因此先将其左边减取一个剩余变量,使它化为等式：,也就是,18,。,从而得到模型的标准形式为,19,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,20,课堂练习,某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）,养分,饲料,答案：设购买M饲料x1，N饲料x2,0.5x1+0.1x2100.2x1+0.3x250.3x1+0.4x280.2x27x1,x20,s.t.,MinZ=300 x1+200 x2,21,2.3线性规划的图解法,对只包含两个决策变量的线性规划问题，可以用图解法来求解。图解法顾名思义就是通过作图来求解的方法，它简单直观、并有助于说明一般线性规划问题求解的基本原理。,22,有关概念可行解：我们将满足线性规划问题的所有约束条件的变量x1和x2的一组取值称为线性规划问题的一个可行解。通常用X表示。可行域：我们将可行解的集合称为可行域。最优解：因此我们求解线性规划问题，就是要求使得目标函数取最优值（对例1，就是取最大值）的可行解，这样的可行解就称为线性规划问题的最优解。通常用X*表示。最优值：即最优的目标函数值,通常用z*表示,23,图解法步骤:建立平面直角坐标系图示约束条件,求可行域图示目标函数求最优解,24,建立直角坐标系,图示约束条件，求可行域,x1,x2,25,图示目标函数,求最优解,x1,x2,最优解,等值线向右上方移动，函数值变大。在其即将离开可行域时达到B（3/2,1）点。所以最优解为：,此时最优值为：,26,2.2.2线性规划求解的可能结局,1、有唯一的最优解,2、有无穷多个最优解（将目标函数改为z=4x1+3x2）,27,maxz=3x1+5.7x2s.t.x1+1.9x23.8x1-1.9x23.8x1+1.9x211.4x1-1.9x2-3.8x1，x20,x1,x2,o,x1-1.9x2=3.8,x1+1.9x2=3.8,x1+1.9x2=11.4,（7.6,2）,D,0=3x1+5.7x2,maxZ,minZ,（3.8,4）,34.2=3x1+5.7x2,可行域,x1-1.9x2=-3.8,(0,2),(3.8,0),绿色线段上的所有点都是最优解,即有无穷多最优解。Zman=34.2,28,3、无界解,指线性规划问题有可行解，但是在可行域，目标函数值是无界的，因而达不到有限最优值。因此线性规划问题不存在最优解。,29,4、无可行解,指找不到一组变量能满足线性规划的所有约束条件的情况，也就是线性规划问题不存在可行解，或者说可行域是空集。例如线性规划问题：,30,LP解的几种情况,注：出现（3）、（4）情况时，建模有问题,31,另外两个重要的结论：线性规划问题可行域若不是空集，则它是一个凸集；线性规划问题的最优解若存在，则一定可以在其可行域的一个顶点上达到。,32,最优解：x1=0，x2=1最优目标值z=3,课堂练习图解法求解线性规划,33,例某工厂经市场调研，决定生产甲、乙两种产品，其单台利润分别为60元和30元，两种产品共用一种钢材、一台设备，其资源及获利情况如下：,求利润最大的产品结构决策。,作业练习,34,确定目标函数及约束条件建立数学模型,目标函数：,将不等式变为等式并在x1x2坐标图中作出直线,最优点在凸边形的顶点，代入（1）式可得maxP,解：,设变量：设甲生产x1台，乙生产x2台，可得最大利润,35,36,2.4线性规划解的基本概念与性质,在本节，我们主要考虑模型具有标准形式的线性规划问题,（2.6）,37,线性规划问题解的概念及性质,对于线性规划问题（2.6）来说，可行解实际上是由约束条件构成的线性方程组（常称为约束方程组）,的解，并且还满足非负约束条件，即各个决策变量都取非负值：。,38,对于线性规划问题（2.6），可以证明如下的结论：定理2.1线性规划问题的可行域如果不是空集，就一定是凸集。凸集:指一个非空集，并且以其中任意两个点为端点的直线段上的所有点都属于该集合。,顶点：在凸集中，如果一个点不位于其他两点为端点的线段的内部，则称其为该凸集的顶点。例如上图中第一个凸集的A点，或第二个凸集的B点，分别是相应的凸集的顶点。,哪个是凸集呢？,39,今后我们将A的任一个具有这样的特征的子矩阵B称为线性规划问题（2.6）的一个基。也就是说线性规划问题的基就是矩阵A的一个且行列式不为零的子矩阵。,我们将约束方程组的系数矩阵,称为线性规划问题的系数矩阵，并且总假定其秩等于其行数：,。这意味着系数矩阵,的各行是线性无关的，,这也表明约束方程中的各个方程是相互独立的。,由于矩阵A的秩为m,故至少存在一个的子矩阵B，其行列式不为零。,40,例如，对于线性规划问题,其系数矩阵为,则下面两个矩阵都是该线性规划问题的基。,和,还能找出其它基吗？,41,例如，对上面的线性规划问题，若我们考虑基则线性规划问题的基变量就是x2和x4，而x1和x3就是非基变量。但如果我们考虑的基是则基变量是x1和x2，非基变量是x3和x4。可见在线性规划问题中所谓基变量就是由m个变量构成的一组变量，其系数构成的行列式不等于零；反之满足系数行列式不等于零的一组m个变量，就是基变量。,42,基解：在约束方程组中，令非基变量等于0的解。基可行解：基解+可行解,例如，对于上面的线性规划问题，如果取x1，x2为基变量，则令非基变量x3，x4为零，约束方程组为,解之得。故我们得到基解注意到这个基解还是一个可行解。,是否所有的基解都是基可行解？（选x1,x3作为基变量）,43,定理2.2：线性规划问题的基可行解是其可行域的顶点。定理2.3：线性规划问题的最优解如果存在，则一定有一个基可行解是最优解。,44,2.6单纯形法计算,基本思路：首先将线性规划问题化成标准形式求出初始基本可行解判断其是否为最优解如果不是最优，则迭代到其相邻的基本可行解，并再次检验,45,旦茨基教授在一次演说中，形象而风趣地说明了单纯形解法的奇效：设给70个人分配70项任务，每人一项。如果每人完成各项任务所需要付出的代价（时间、工资）都知道，要寻求代价最小的方案。所有的可行方案共有70！种。70！比还要大。不仅如此，还能预测当方案中某因素发生变化，对决策目标的影响。,神奇的单纯形法,46,线性规划问题的可行解有无穷多个，与某一凸集上的无穷多个点一一对应。要从无穷多个可行解中寻找最优解，几乎不可能。可以证明，最优解必定能取在凸集的顶点（极点、基本可行解）上，而极点的个数是有限的。当然，这个“有限”，数字往往相当可观，如前面的70！，要逐个比较的话，也不现实。而单纯形解法，用跨跃的方式，高速地优化基本可行解，迅速达到最优。,单纯形法跨跃式地寻求最优解,maxS,S=o,A,B,C,D,E,47,初始可行解,为了便于求解，并使得整个求解过程程序化，我们通常是从求一个特殊的基可行解出发进行求解。这个特殊的基可行解称为初始基可行解。要求初始基可行解需先确定初始基变量。我们称基矩阵为单位矩阵（或单位矩阵交换了列以后得到的矩阵）的基变量为初始基变量。因此初始基变量具有特征：它们是一组变量，个数等于约束方程的个数，每个变量仅出现在一个约束方程中且系数为1。初始基变量对应的基解一定是可行解称为初始基可行解。,48,解：数学模型maxS=6x1+4x2s.t.2x1+3x21004x1+2x2120 x1,x20,引进松弛变量x3,x40数学模型标准形式：maxS=6x1+4x2s.t.2x1+3x2+x3=1004x1+2x2+x4=120 x1,x2,x3,x40,49,A=（P1，P2，P3，P4）=23104201X=（x1,x2,x3,x4)B=(P3，P4）=1001P3，P4线性无关，x3,x4是基变量，x1,x2,是非基变量。,令A=（P1，P2，P3，P4）=23104201X=（x1,x2,x3,x4),50,用非基变量表示的方程：x3=100-2x1-3x2x4=120-4x1-2x2(I)S=6x1+4x2,令非基变量（x1,x2）t=（0，0）t得基础可行解：x(1)=(0,0,100,120)tS1=0经济含义：不生产产品甲乙，利润为零。分析：S=6x1+4x2（分别增加单位产品甲、乙，目标函数分别增加6、4，即利润分别增加6百元、4百元。）增加单位产品对目标函数的贡献，这就是检验数的概念。,51,增加单位产品甲（x1）比乙对目标函数的贡献大（检验数最大），把非基变量x1换成基变量，称x1为进基变量，而把基变量x4换成非基变量，称x4为出基变量。,确定了进基变量x1，出基变量x4以后，得到新的系统：x3=40-2x2+（1/2）x4x1=30-（1/2）x2-（1/4）x4(II)S=180+x2-（3/2）x4令新的非基变量（x2，x4）=（0，0）t得到新的基础可行解：x(2)=(30,0,40,0)tS2=180经济含义：生产甲产品30个，获得利润18000元。,52,这个方案比前方案，但是否是最优？分析：S=180+x2-（3/2）x4非基变量x2系数仍为正数，确定x2为进基变量。在保证常数项非负的情况下，确定x3为出基变量。得到新的系统：x1=20+（1/4）x3-（3/8）x4x2=20-（1/2）x3+（1/4）x4(III)S=200-（1/2）x3-（5/4）x4,53,令新的非基变量（x3,x4）t=（0,0）t得到新的基础可行解：x(3)=(20,20,0,0)tS3=200经济含义：分别生产甲乙产品20个，可获得利润20000元。分析：S=200-（1/2）x3-（5/4）x4目标函数中的非基变量的系数无正数，S3=200是最优值，x(3)=(20,20,0,0)t是最优解。该企业分别生产甲乙产品20个，可获得最大利润20000元。,54,利用单纯形表进行计算,从前面的单纯形法的计算过程可见，所有计算其实都归结为对标准形式的模型的系数的计算。因此可以通过将线性规划的系数矩阵及目标函数系数列成表格的方式进行计算。,maxz=3x1+2x2,x1+2x2+x3=5,2x1+x2+x4=4,4x1+3x2+x5=9,x1,x2,x50,32,121005,210104,430019,32000,单纯形表,检验数,55,以x3,x4,x5作为初始基变量得到初始单纯形表如下所示：,该初始单纯形表对应的初始解为X=(0，0，5，4，9)T。对应目标函数值为0.因为x1的检验数,我们选择x1作为换入变量。这样可以使目标函数增加得更快。然后用b列的数除以换入变量列的正的系数，所得最小商对应的变量x4为换出变量。,56,以x3,x1,x5作为基变量得到第二张单纯形表按如下方式计算：,该元素称为主元。下面开始迭代，迭代的目标就是把主元化为1，然后把主元所在列其他系数化为0。,x1,3,3,2,1/2,0,1/2,1,0,0,0,3/2,1,-1/2,0,0,0,1,0,-2,1,1,0,1/2,0,-3/2,6,0,该单纯形表对应的基可行解为X=（2，0，3，0，1）T，对应目标函数值为6。现在x2的检验数为1/20，且最大，所以我们选择x2为换入变量。因为min3/(3/2),2/(1/2),1/1=1,所以选择x5作为换出变量。,57,以x3,x1,x2作为基变量得到第三张单纯形表如下所示：,2,x2,0,1,0,-2,1,1,0,0,0,1,5/2,-3/2,3/2,3,1,0,0,3/2,-1/2,3/2,0,0,0,-1/2,-1/2,13/2,现在所有的检验数都小于或者等于0，所以得到最优解为：,最优目标函数值为13/2。,该表称为最终单纯形表，其具有什么特征？,58,合并的单纯形表,59,单纯形法计算过程,构造初始单纯形表对标准化后的线性规划问题，首先找出初始基变量，构造初始单纯形表。相应地可以得到初始基可行解，基可行解的目标函数值。最优性检验若得到单纯形表中所有的检验数都小于或等于零，则该单纯形表给出的基可行解就是最优解，终止计算。否则进行下一步。确定换入变量选择最大的正检验数对应的非基变量为换入变量。确定换出变量若换入变量（更一般地，若某个正检验数对应的变量）所作列的系数均小于或等于零，则线性规划问题为无界解，终止计算。否则用换入变量所作列的系数去除b列的对应数，在除得的商中选择最小者对应的基变量为换出变量。旋转运算确定换入和换出变量后得到新的基变量，然后以换入变量所在列、换出变量所在行交