广东自考线性规划

1、第一章第一章 线性规划问题线性规划问题 线性规划是运筹学的一个大分支数学规划数学规划的组成部分。 数学规划分为静态规划静态规划和动态规划动态规划； 静态规划又分为线性规划线性规划和非线性规划非线性规划。 静态数学规划一般来说是研究一个n元实函数（称为目标函数）在一组等式或不等式约束条件下的极值问题。如果目标函数和约束条件都是线性的，则称为线性规划线性规划；否则，称之为非线性规划。非线性规划。一、线性规划问题的三要素1.决策变量 问题需要求解的未知量。它是通过模型计算来确定的决策因素。2.目标函数目标的数学表达式。目标函数是求变量的线性函数的极大值和极小值这样一个极值问题。 3.约束条件实现目标

2、的制约因素。它包括：生产资源的限制（客观约束条件）、生产数量、质量要求的限制（主观约束条件）、特定技术要求和非负限制。 二、线性规划问题的基本结构 Min Z=10 x1+20 x2 s.t. x1+x210 3x1+x215 x1+6x215 x10 , x20 约束条件目标函数非负限制三、线性规划模型的一般形式（极大值型）Max Z=c1x1+c2x2+c3x3+cnxn a11x1+a12x2+a1nxn b1 (1) a21x1+a22x2+a2nxn b2 (2) am1x1+am2x2+amnxn bm (m) x1 ，x2 ，xn0njxmibxatsxcxcxcZjinjjij

3、nn, 3 , 2 , 1,0)3 , 2 , 1(. .max12211其简缩形式为其简缩形式为 线性规划模型的一般形式（极小值型）Min Z=c1x1+c2x2+c3x3+cnxn a11x1+a12x2+a1nxn b1 (1) a21x1+a22x2+a2nxn b2 (2) am1x1+am2x2+amnxn bm (m) x1 ，x2 ，xn0njxmibxatsxcxcxcZjinjjijnn, 3 , 2 , 1,0)3 , 2 , 1(. .min12211其简缩形式为其简缩形式为 四、线性规划问题的标准形式结构： 目标函数统一成求最小值；约束条件归结为一组线性方程组和非负性

4、限制。注意点： 目标函数是求最大值,要化为求最小值；约束条件是不等式，要化为等式和非负性限制。标准形式：njxmibxatsxcxcxcZjinjjijnn, 3 , 2 , 1,0),3 , 2 , 1(. .min12211若使用向量和矩阵记号，则标准形式可写为：此标准形式也称为LP。 nxxxX21mnmmnnaaaaaaaaaA2122221112110.minxbAxtscxzbmbbb21 其中：C=(c1,c2,cn) 0是n维零向量，即)3 , 2 , 1 (, 0, 00000njxxj则五、线性规划模型的建立步骤：1、确定决策变量。2、确定目标函数。3、确定约束条件。4、变

5、量取值限制。常见的线性规划问题资源利用问题运输问题合理下料问题经济配料问题布局问题分配问题证券投资与组合问题例题1（经济配料问题）某饲料公司用甲、乙两种原料配制饲料，甲乙两种原料的营养成份及配合饲料中所含各营养成份最低量由表1给出。已知单位甲、乙原料的价格分别为10元和20元，求满足营养需要的饲料最小成本配方。 设配合饲料中，用甲x1单位，用乙x2单位，则配合饲料的原料成本函数，即决策的目标函数为Z=10 x1+20 x2。考虑三种营养含量限制条件后，可得这一问题的线性规划模型如下： Min Z=10 x1+20 x2 x1+x210 3x1+x215 x1+6x215 x10 , x20例题

6、例题2（资源利用问题）（资源利用问题） 某农户计划用某农户计划用12公顷耕地生产玉米，大豆和公顷耕地生产玉米，大豆和地地瓜，可投入瓜，可投入48个劳动日，资金个劳动日，资金360元。生产玉米元。生产玉米1公顷，需公顷，需6个劳动日，资金个劳动日，资金36元，可获净收入元，可获净收入20元；生产元；生产1公顷大豆，需公顷大豆，需6个劳动日，资金个劳动日，资金24元，元，可获净收入可获净收入150元；生产元；生产1公顷地瓜需公顷地瓜需2个劳动个劳动日，资金日，资金18元，可获净收入元，可获净收入1200元，问怎样安排元，问怎样安排才能使总的净收入最高。才能使总的净收入最高。 设种玉米，大豆和地瓜的

7、数量分别为x1、x2和x3公顷，根据问题建立线性规划问题模型如下： Max Z=200 x1+150 x2+100 x3 x1+x2+x312(1) 6x1+6x2+2x348(2) 36x1+24x2+18x3360(3) x10，x20，x30 例例33某农户有耕地20公顷，可采用甲乙两种种植方式。甲种植方式每公顷需投资280元，每公顷投工6个，可获收入1000元，乙方式每公顷需投资150元，劳动15个工日，可获收入1200元，该户共有可用资金4200元、240个劳动工日。问如何安排甲乙两种方式的生产，可使总收入最大?解：设甲方式种x1公顷，乙方式种x2公顷，总收入为Z，则有： Max Z

8、=1000 x1+1200 x2 280 x1+150 x24200 6x1+15x2240 x1+x220 x10,x20 例题4、（合理下料问题）某工厂生产过程中分别需要长度为3.3米、2.5米、1.7米的同种棒料毛坯200根、100根、300根。现有的原料为9米长棒材，问如何下料可使废料最少？一根9米的棒材截断的方案如下表：设按八种方案下料的9米棒各x1、x2 、x3、 x4 、x5 、x6、 x7 、x8根则所求的数学模型为: min f = 0.7x1+0.7x2+1.5x3+0.6x4+1.5x5+0.6x6+1.4x7+0.5x8 s.t. 均为整数且jjxjxxxxxxxxxx

9、xxxxxx),83 , 2 , 1 (, 03005323100222002876431765324321六、非标准形式转化为标准形式w 目标函数是求最大值解的，可令f = -z ,则转化为求-z的最小值解。w 约束条件是不等式约束要化为等式约束。两种情况：0,11knkknnjjkjknjjkjxbxxabxa等价于加上一个正数0,11lnllnnjjkjlnjjkjxbxxabxa等价于减去一个正数xn+k与xn+l都是增添的变量，称为松弛变量。有时也把xn+l称为剩余变量。综上所述，任何线性规划问题都可化为：求一组非负变量的值，使之满足一个线性方程组，并使一个线性函数达到最小值。w 如

10、果原问题对某决策变量xj没有非负限制，则可令即可用两个非负变量 取代原变量。右端值都是非负数。, 0, 0,/jjjjjxxxxx/,jjxx其他符号也可以，但要注意不是题出现的符号。例题：将下列线性问题化为标准形式：34263. .4max2212121xxxxxtsxxz2009年1月自考题0243132. .2max21212121xxxxxxtsxxf09年10月自考题042134. .3max2212121xxxxxtsxxf几个概念： （一）可行解 线性规划问题的可行解是指，满足规划中所有约束条件及非负约束的决策变量的一组取值，其仅与约束条件有关而与目标函数值的大小无关。 （二）可

11、行域 可行域是由所有可行解构成的集合。根据线性规划的基本理论，任一个线性规划问题的可行域，都是一个有限或无限的凸多边形，凸多边形的每个角，称为可行域的极点。 （三）最优解 线性规划的最优解是指，使目标函数值达到最优(最大或最小)的可行解。一个线性规划问题可以是有解的，也可能是无解的，最优解的个数可能是惟一的，也可能是有无穷多个，即决策变量有许多组不同的取值，都使目标函数达到同一个最优值。 njxmibxatsxcxcxcZjinjjijnn, 3 , 2 , 1,0),3 , 2 , 1(. .min12211可行解最优解七、二变量规划问题的图解法 两个变量的线性问题，可以在直角坐标平面上用作

12、图求解。 步骤： 第一步，找出问题的可行域 在直角坐标系上找出满足约束条件中的每一个不等式的点集。 第二步，在可行域中寻求最优解 目标函数z=ax1+bx2,目标函数等值线族便是由方程ax1+bx2=h（h为参数）所表示的平行直线束。其正法向量 z=（a,b)T 沿着这个方向移动等值线，目标函数递增，反之，目标函数递减。 因此，当等值线沿z方向移动，即将脱离可行域时，便是目标函数z取最大值的点；当等值线沿z反方向移动，即将脱离可行域时，便是目标函数z取最小值的点。 若若b0, -a/b为等值线的斜率。为等值线的斜率。例题1：求解线性规划问题 min Z=10 x1+20 x2 s.t. x1+

13、x210 3x1+x215 x1+6x215 x10, x201515105105OABCDx2x1x1+6x2=15可行域3x1+x2=15x1+x2=1010 x1+20 x2h等值线沿着正法向量的反方向移动，移动到点C时即将脱离可行域。点C是目标函数取最小值的点。这个交点坐标为（9，1），因此最优值z=910+120=110例题2、求解线性规划问题 max f = 2x1+4x2 s.t. x1+2x210 0 x1 4 0 x2 3解：作出可行域K的图形，如图所示： 由于目标函数的等值线族2x1+4x2=h恰与可行域K的BC边平行，故沿着正法向量的方向平推等值线时，最后与BC边重合。因

14、此BC边上每一点都使目标函数取最大值。解：作出可行域K的图形，如图所示：0 x23x20 x14Ax1x1+2x210oB(2,3)C(4,2)DK例题3 求解线性规划问题min f = -2x1+x2 s.t. x1+x21 x1-3x2-3 x10, x20解：作出可行域，如图所示： 当目标函数的等值线族-2x1+x2=h沿正法向量的反方向移动时，总是与K相交，没有脱离可行域，则问题没有最优解。x2x1kox1+x21x1-3x2-3思考：如果将此问题中的min f 改为max f，其他不变，则是否有最优解？可行域可行域K上无下界有上界，极小值线性上无下界有上界，极小值线性规划问题没有最优

15、解；但极大值线性规规划问题没有最优解；但极大值线性规划问题有最优解。划问题有最优解。可行域可行域K上无上界有下界，极大值线性上无上界有下界，极大值线性规划问题没有最优解；但极小值线性规规划问题没有最优解；但极小值线性规划问题有最优解。划问题有最优解。例题4：求解线性规划问题min f = 3x1+4x2 s.t. - x1+x21 x1+x2-2 x10, x20解：作图可知，没有可行域，即问题没有可行解，也就没有最优解。x1x2o上面4个例子表明了两个决策变量的线性问题仅有的4种可能情况：w 问题有惟一最优解，此时最优解在可行问题有惟一最优解，此时最优解在可行域一个顶点上达到；域一个顶点上达

16、到；w 问题有无穷多个最优解，此时最优解在问题有无穷多个最优解，此时最优解在可行域的一条边界上达到；可行域的一条边界上达到；w 问题有可行解但无最优解，此时，可行问题有可行解但无最优解，此时，可行域无界，目标函数在可行域上无下界域无界，目标函数在可行域上无下界（或无下界）；（或无下界）；w 问题无可行解，自然也就没有最优解。问题无可行解，自然也就没有最优解。这样的结论，一般的线性问题也成立小结：1、线性规划问题有最优解，一定有可行解。、线性规划问题有最优解，一定有可行解。2、线性规划问题有可行解，但不一定有最优解。、线性规划问题有可行解，但不一定有最优解。3、如果线性规划问题有可行解没有最优解，则、如果线性规划问题有可行解没有最优解，则可行域无界，极小值线性规划问题在可行域没可行域无界，极小值线性规划问题在可行域没下界，极大值线性规划问题在可行域没上界。下界，极大值线性规划问题在可行域没