《运筹学》线性规划

第2章线性规划例1穗羊公司的例子III每周可使用量A（千克）125B（吨）214C（百工时）439单位产品利润（万元）32问该公司每周应生产产品I与产品II各多少单位，才能使每周的获利达到最大？假设产品I、II每周的产量分别是x1和x2，得到如下的数学模型0,934425223max2121212121xxxxxxxxs.t.xxz其中s.t.是英文词组subjectto的缩写，表示“受限制于”的意思，有时也约去不写出来。该问题常称为生产计划问题或产品组合（productmix）问题。例2设有一批规格为10米长的圆钢筋，将它截成分别为3米，4米长的预制构件的短钢筋各100根，问怎样截取最省料？因为，10米长的钢筋截为3米或4米长，共有三种截法：截法Ⅰ：3331米截法Ⅱ：3340米截法Ⅲ：4402米假设按截法Ⅰ，Ⅱ，Ⅲ各截取10米长的钢筋分别为x1,x2,x3根则可以获得3米长的短钢筋的根数是3x1+2x24米长短钢筋的根数是x2+2x3按问题要求它们应该不小于100根。总共用料是x1+x2+x3要达到最省料的目的，就必须使总用料最小。例2的模型就是0,,10021003..min3213221321xxxxxxxtsxxxw例2中的问题常称为下料问题。线性规划的三个要素：决策变量目标函数约束条件其次线性规划模型必须满足如下两个要求：①目标函数必须是决策变量的线性函数；②约束条件必须是含决策变量的线性等式或不等式。运筹学建模步骤:识别问题定义决策变量建立约束条件建立目标函数2.2线性规划模型的一般形式和标准形式为了讨论一般的线性规划问题的求解。我们先给出线性规划模型的一般形式如下：0,...,,)()()(..min)max(2122122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz，或或，或或，或或或2.2.1线性规划的一般模型这里一共包含有n个决策变量，m个约束条件；对目标函数既可以求最大的也可以求最小；约束条件有,,=型；决策变量通常非负，但也可以有其它情况；cj:称为价值系数；bi:资源常数（右端常数）aij称为技术系数、工艺系数在今后的讨论中，为方便起见，还将用到线性规划模型一般形式的各种简写的形式。利用和号“”，线性规划模型的一般形式可写为：njxmibxatsxczjinjjijnjjj,...,2,1,0,...,2,1,)(..min)max(11，或或或利用向量，可以将一般形式表示为：0)(..min)max(1XbPCX，或或或njjjxtsz其中在今后的讨论，常将矩阵称为线性规划问题的（约束条件）系数矩阵。明显地系数矩阵与矩阵之间存在关系：用矩阵的记号可以将线性规划模型一般形式写成：0)(..min)max(XbAXCX，或或或tsz其中同上，而矩阵是由各约束条件的系数（技术系数）构成的矩阵：bCX,,Amnmmnnaaaaaaaaa212222111211AnmAAjPnPPPA212.2.2线性规划的标准形式0,...,,..max2122122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz它具有如下四个特征：①目标函数求max；②约束条件两端用“=”连结；③bi非负；④所有决策变量xj非负。2.2.3将线性规划的模型化为标准形式1、目标函数求最小值的情形取原目标函数的相反数为新的目标函数，对原目标函数求最小值的问题就等价于对这一新的目标函数求最大值的问题。32132minxxxz32132'maxxxxz例如：等价于2、约束条件为不等式(a)232321xxx转化为232321sxxxxxs表示决策中尚未使用的那部分资源，因此称这一变量为松弛变量。（b）3423321xxx转化为：3423321sxxxx它表示决策结果超过了实际需要的部分，因此常称它为剩余变量。无论是松弛变量还是剩余变量在决策中都不产生实际价值，因此它们在目标函数中的系数都应该为零。在后面的讨论中，有时也将松弛变量和剩余变量统称为松弛变量。3、约束条件右端常数为负数只需将这一约束条件两端同乘“-1”就可化为一个等价的约束条件，其右端常数满足标准形式的要求。4、决策变量不满足非负约束（a）01x11xx01x则（b）如x3无约束，则令333xxx例如，将例1中的线性规划模型化为标准形式就是：0,,,,934425223max5432152142132121xxxxxxxxxxxxxxxxz其中就是分别对第一、第二、第三个约束条件中添加的松弛变量。543,,xxx例3化如下的线性规划问题模型0,,0223223223min321321321321xxxxxxxxxxxxz无约束为标准形式。1x1x1x011xx(1)变量是非正的，所以要将模型中的所有都用代替，其中2x0,022xx222xxx2x22xx(2)变量无约束，因此取两个变量使得。在模型中，所有的都用代替。。在模型中，所有的(5)约束条件2是“”型的，因此需要在左边加上一个松弛变量化为等式，即”型的，并且右端的常数小于零。(3)目标函数是求最小值的，因此令zz，即32232132122323)23(xxxxxxxxxxz4x2324321xxxx2324321xxxx232243221xxxxx(4)约束条件1是“然后在两端乘以-1得也就是因此先将其左边减取一个剩余变量5x22325321xxxx2233253221xxxxx使它化为等式：也就是。0,,,,,223322322223max54322153221432213221xxxxxxxxxxxxxxxxxxxxz从而得到模型的标准形式为课堂练习某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）ABCD价格M0.50.20.30300N0.10.30.40.2200每头日需10587养分饲料课堂练习某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）ABCD价格M0.50.20.30300N0.10.30.40.2200每头日需10587养分饲料答案：设购买M饲料x1，N饲料x20.5x1+0.1x2≥100.2x1+0.3x2≥50.3x1+0.4x2≥80.2x2≥7x1,x2≥0s.t.MinZ=300x1+200x22.3线性规划的图解法对只包含两个决策变量的线性规划问题，可以用图解法来求解。图解法顾名思义就是通过作图来求解的方法，它简单直观、并有助于说明一般线性规划问题求解的基本原理。有关概念可行解：我们将满足线性规划问题的所有约束条件的变量x1和x2的一组取值称为线性规划问题的一个可行解。通常用X表示。可行域：我们将可行解的集合称为可行域。最优解：因此我们求解线性规划问题，就是要求使得目标函数取最优值（对例1，就是取最大值）的可行解，这样的可行解就称为线性规划问题的最优解。通常用X*表示。最优值：即最优的目标函数值,通常用z*表示图解法步骤:建立平面直角坐标系图示约束条件,求可行域图示目标函数求最优解0,934425223max2121212121xxxxxxxxs.t.xxz5221xx4221xx93421xx建立直角坐标系图示约束条件，求可行域x1x20,934425223max2121212121xxxxxxxxs.t.xxz5221xx4221xx93421xx图示目标函数求最优解x1x2最优解等值线向右上方移动，函数值变大。在其即将离开可行域时达到B（3/2,1）点。所以最优解为：12x21623*21xxz此时最优值为：,231x2.2.2线性规划求解的可能结局1、有唯一的最优解2、有无穷多个最优解（将目标函数改为z=4x1+3x2）x1x2Ox1+2x2=52x1+x2=44x1+3x2=9ABCD0,934425234max2121212121xxxxxxxxs.t.xxzmaxz=3x1+5.7x2s.t.x1+1.9x2≥3.8x1-1.9x2≤3.8x1+1.9x2≤11.4x1-1.9x2≥-3.8x1，x2≥0x1x2ox1-1.9x2=3.8x1+1.9x2=3.8x1+1.9x2=11.4（7.6,2）D0=3x1+5.7x2maxZminZ（3.8,4）34.2=3x1+5.7x2可行域x1-1.9x2=-3.8(0,2)(3.8,0)绿色线段上的所有点都是最优解,即有无穷多最优解。Zman=34.23、无界解指线性规划问题有可行解，但是在可行域，目标函数值是无界的，因而达不到有限最优值。因此线性规划问题不存在最优解。0,1212332max21212121xxxxxxxxzx1x2O-3x1+2x2=1x1-2x2=14、无可行解指找不到一组变量能满足线性规划的所有约束条件的情况，也就是线性规划问题不存在可行解，或者说可行域是空集。例如线性规划问题：0,22232422max2121212121xxxxxxxxxxzx1x2O2x1-3x2=2-x1+2x2=42x1+x2=2LP解的几种情况（1）唯一解（2）多重最优解（3）无可行解注：出现（3）、（4）情况时，建模有问题（4）无有限最优解另外两个重要的结论：①线性规划问题可行域若不是空集，则它是一个凸集；②线性规划问题的最优解若存在，则一定可以在其可行域的一个顶点上达到。最优解：x1=0，x2=1最优目标值z=3课堂练习图解法求解线性规划0,)3(22)2(22)1(432min2121212121xxxxxxxxstxxz012341234x1x2O-1-2(1)(2)(3)例某工厂经市场调研，决定生产甲、乙两种产品，其单台利润分别为60元和30元，两种产品共用一种钢材、一台设备，其资源及获利情况如下：甲乙现有资源钢材消耗定额（公斤/台）24600公斤台时消耗定额（小时/台）31400小时配件（件/台）20250件利润（元）6030求利润最大的产品结构决策。50,425023400326004213060max211212121xxxxxxxxxP②确定目标函数及约束条件——建立数学模型目标函数：③将不等式变为等式并在x1－x2坐标图中作出直线)(450030150)(750060125)(8250302560125)(90001003010060元元元元ADcbMMMM④最优点在凸边形的顶点，代入（1）式可得maxP解：①设变量：设甲生产x1台，乙生产x2台，可得最大