【安全课件】第三章规划论

1.什么是规划论在生产生活以及军事领域经常会遇到资源分配问题，不同的分配方案产生的效益是不一样的，所以，为了追求最佳效益，必须在不同的分配方案中选择最佳的资源分配方案。规划论就是研究针对不同需求对有限资源进行分配的一个运筹学分支。第三章规划论其中，线性规划是形成最早也是最成熟的一个分支。到目前为止，它的应用也最广泛，是数学规划及运筹学其他分支的基础。线性规划整数规划动态规划零一规划非线性规划目标规划2理论分支理论分支康脱络维奇——论文“生产组织与计划中的数学方法”，1939年。1947年，丹捷格提出了单纯形法第一节线性规划对于一个实际问题，如果采用线性规划去求解，应做两方面的工作，一是把求解问题抽象成能用线性规划来解的数学模型，这就是数学建模。二是对这个线性规划进行求解。即数学建模求解1线性规划方法解决问题的过程3.线性规划的数学模型（1）引例某军工厂准备用三种原料来制造两种产品，有关数据如下表所示。问如何安排生产，以使总利润达到最大化。单位产品产品消耗量原料（公斤）III原料总量A94360B４５200C310300单位产品利润（元）7122线性规划问题的数学模型确定目标：求出生产两种产品的数量各为公斤，以使总利润达到最大。建立数学模型：设I产品生产x1公斤，II产品生产x2公斤MAX总利润Z＝7x1+12x2目标是9x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1，x2，，x3≥0建立数学模型：设I产品生产x1公斤，II产品生产x2公斤MAX总利润Z＝7x1+12x2目标是9x1+4x2≤3604x1+5x2≤2003x1+10x2≤300x1，x2，，x3≥0以上问题属于线性规划问题，这类问题从数学上讲所具有的共同特征是：1）决策变量。每一个问题都用一组未知数（x1.x2……xn）表示某一方案，这组未知数的一组定值代表一个具体的规划方案。通常要求这些未知数取值是非负。以后我们称这组未知数为决策变量。2）约束条件。3）目标函数。线性规划问题都有一个目标要求，并且这个目标可以表示为一组未知数的线性函数，称之为目标函数，按研究问题的实际情况目标函数可以是求最小值也可以是求最大值。我们总是希望收益、效益、效率等指标达到最大化，而对于成本、费用、支出等指标则希望达到最小化。（2）线性规划问题的共同特征综合上述这三点，这类问题都可以用如下数学语言来描述。目标函数：max(min)Z=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn≥（=，≤）b1a21x1+a22x2+…a2nxn≥（=，≤）b2……am1x1+am2x2+…amnxn≥（=，≤）bmx1，x2，…xn≥03线性规划问题的标准形式（1）线性规划的标准形式是：目标函数：maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2……am1x1+am2x2+…amnxn=bmx1，x2，…xn≥0线性规划的标准形式是：maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2……am1x1+am2x2+…amnxn=bmx1，x2，…xn≥0maxZ=njjjxc1ijijijbxa,minj11ijijijbxa,xj≥0用求和符号表示标准形式，则标准形式可简写为：3线性规划问题的标准形式线性规划的标准形式是：maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2……am1x1+am2x2+…amnxn=bmx1，x2，…xn≥0用矩阵表示标准形式，则标准形式可简写为令C表示由目标函数的系数构成的矩阵，即用A表示由约束条件的系数构成的矩阵，即mnmmnnaaaaaaaaa212222111211Ａ＝令X表示由决策变量构成的矩阵，即nxxxX21B表示约束条件向量，即nbbbB21C=(c1，c2，…，c)；3线性规划问题的标准形式线性规划的标准形式是：maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2……am1x1+am2x2+…amnxn=bmx1，x2，…xn≥0用矩阵表示标准形式，则标准形式可简写为maxZ=CXmnmmnnaaaaaaaaa212222111211Ａ＝nbbbB21C=(c1，c2，…，c)；nxxxX21AX=BX≥03线性规划问题的标准形式线性规划的标准形式是：maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2……am1x1+am2x2+…amnxn=bmx1，x2，…xn≥0几点称谓mnmmnnaaaaaaaaa212222111211Ａ＝nxxxX21决策向量nbbbB21约束方程组的限定向量C=(c1，c2，…，c)；价值向量约束条件系数矩阵（2）将非标准形化为标准形式非标准形式是max(min)Z=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn≥（=，≤）b1a21x1+a22x2+…a2nxn≥（=，≤）b2……am1x1+am2x2+…amnxn≥（=，≤）bmx1，x2，…xn≥0标准形式是：maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2……am1x1+am2x2+…amnxn=bmx1，x2，…xn≥0（2）将非标准形化为标准形式非标准形式minZ=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2……am1x1+am2x2+…amnxn=bmx1，x2，…xn≥0（1）若目标函数求最小值可以把它转化为求负的同一目标函数的最大值，即令Z‵=--ZminZ=maxZ‵非标准形式maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn≤b1a21x1+a22x2+…a2nxn≥b2……am1x1+am2x2+…amnxn≤bmx1，x2，…xn≥0（2）约束方程组中有不等式，这时有两种情况：一种是“≤”形式的不等式，则可在式子的左端加一非负变量称为“松弛变量”；如：x1+x2+x3≤60另外一种是≥形式的不等式则在左端减一松弛变量使之变为等式约束。如：x1+x2+x3≥60（2）将非标准形化为标准形式非标准形式是max(min)Z=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2………………………………………am1x1+am2x2+…amnxn=bmxk无非负要求，xj≤0，其余的变量大于等于零。（3）若决策变量无非负要求令xk=xk`--xk``,xk`,xk``≥0（3）若要求决策变量xj≤0可令xj`=--xjxj≥0（2）将非标准形化为标准形式试将线性规划问题化为标准形式：minz=-x1+2x2-3x3x1+x2+x3≤7x1-x2+x3≥2-3x1+x2+2x3=5x1，x2≥0例题（2）将非标准形化为标准形式4用图解法求解线性规划线性规划的图解法就是利用解析几何的方法来求解线性规划的问题。因为只有二维几何空间最为直观，所以图解法只能用来求解二维线性规划问题，也就是只有两个决策变量的线性规划问题。下面我们结合实例来讲解线性规划的图解法。求解线性规划问题maxZ＝2x1+5x2x1≤4x2≤3x1+2x2≤8x1≥0,x2≥0例题把x1，x2看作上平面上点的坐标，在第一象限内用图形将此规划问题的约束条件和目标函数都反映出来就是约束条件围成了一个区域，这个凸多边形oabcd内的任一点的坐标都满足约束条件。而凸边形外的点都不能满足约束条件，所以凸多边形内的任一点的坐标都是这个线性规划问题的一个解，我们称之为可行解。凸多边形构成的可行解的全体，称为可行解集（可行域）。满足目标函数的一个可行解的全体z=2x1+5x2是一组平行线，随z的增加不断向上平移，当移到b点时，达到最大值2x1+5x2=19。图解法解题的基本步骤确定可行域确定目标函数移动的方向确定最优解用图解法求解如下线性规划问题minZ=2x1+2x2x1-x2≥1x1+2x2≤0x1，x2≥0练习1用图解法求解如下线性规划问题minZ=2x1+2x2-x1+x2≥1x1+x2≤-2x1，x2≥0练习25有关线性规划问题解的概念可行域——所有可行解所构成的集合就是可行域对于图解法，可行域就是由约束条件围成的一个凸多边形，我们如果用R表示可行域，则R={x/Ax=b,x≥0}可行解——同样，在可行域上的点都满足约束条件所以，我们称这些点为可行解。x=(x1,x2…xn)Tx1+x2+x3+x4+x5=55有关线性规划问题解的概念基——设Ａ为约束方程组中的m×n阶系数矩阵，其秩为m，（秩为m的意思为m行线性无关），又B是Ａ中m×n非奇异子矩阵（|B|不等于0），则称B是这个线性规划问题的一个基。mmmmmmaaaaaaaaa212222111211B=a11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2……am1x1+am2x2+…amnxn=bmx1，x2，…xn≥0mnmmnnaaaaaaaaa212222111211这是它的系数矩阵5有关线性规划问题解的概念基——设Ａ为约束方程组中的m×n阶系数矩阵，其秩为m，（秩为m的意思为m行线性无关），又B是Ａ中m×n非奇异子矩阵（|B|不等于0），则称B是这个线性规划问题的一个基。mmmmmmaaaaaaaaa212222111211B=mmmmmmaaaaaaaaa212222111211B=a11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2……am1x1+am2x2+…amnxn=bm=（P1，P2，……，PM）基变量——称Pj(j=1,2…m)为基向量，与Pj相对应的Xj(j=1,2…m)称为基变量。mmmmmmaaaaaaaaa212222111211B=a11x1+a12x2+…a1nxn=b1a21x1+a22x2+…a2nxn=b2……am1x1+am2x2+…amnxn=bm=（P1，P2，……，PM）非基变量——其余变量称为（对应于Ｂ）的非基变量。基本解——当取定一个基时，令非基变量为0，由克莱姆法则可得对应于该基的唯一解。此解的非零数目不超过个m个，非0分量的数目等于m的基本解称为非退化的，否则称为退化的。a11x1+a12x2+…a1mx2+…+a1nxn=b1a21x1+a22x2+…a2mx2+…+a2nxn=b2……am1x1+am2x2+…a2mx2+…+amnxn=bm例如当我们取为基时mmmmmmaaaaaaaaa212222111211B=为基时基本解——当取定一个基时，令非基变量为0，由克莱姆法则可得对应于该基的唯一解。此解的非零数目不超过个m个，非0分量的数目等于m的基本解称为非退化的，否则称为退化的。a11x1+a12x2+…a1mx2+…+a1nxn=b1a21x1+a22x2+…a2mx2+…+a2nxn=b2……am1x1+am2x