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

1、1.什么是规划论 在消费生活以及军事领域经常会遇到资源分配问题，不同的分配方案产生的效益是不一样的，所以，为了追求最正确效益，必需在不同的分配方案中选择最正确的资源分配方案。规划论就是研讨针对不同需求对有限资源进展分配的一个运筹学分支。第三章 规划论 其中，线性规划是构成最早也是最成熟的一个分支。到目前为止，它的运用也最广泛，是数学规划及运筹学其他分支的根底。线性规划整数规划动态规划零一规划非线性规划目的规划2 实际分支实际分支康脱络维奇论文 “消费组织与方案中的数学方法 ，1939年。1947年，丹捷格提出了 单纯形法 第一节 线性规划 对于一个实践问题，假设采用线性规划去求解，应做两方面的

2、任务，一是把求解问题笼统成能用线性规划来解的数学模型，这就是数学建模。二是对这个线性规划进展求解。即数学建模求解1 线性规划方法处理问题的过程3.线性规划的数学模型1引例 某军工厂预备用三种原料来制造两种产品，有关数据如下表所示。问如何安排消费，以使总利润到达最大化。单位产品 产品 耗费量原料公斤III原料总量A94360B200C310300单位产品利润元7 122 线性规划问题的数学模型 确定目的：求出消费两种产品的数量各为公斤，以使总利润到达最大。 建立数学模型：设 I 产品消费 x1 公斤，II 产品消费 x2 公斤 MAX 总利润 Z 7 x1 + 12 x2 目的是9 x1 + 4

3、 x2 3604 x1 + 5 x2 2003 x1 + 10 x2 300 x1，x2，x3 0建立数学模型：设 I 产品消费 x1 公斤，II 产品消费 x2 公斤 MAX 总利润 Z 7 x1 + 12 x2 目的是9 x1 + 4 x2 3604 x1 + 5 x2 2003 x1 + 10 x2 300 x1，x2，x3 0 以上问题属于线性规划问题，这类问题从数学上讲所具有的共同特征是：1决策变量。 每一个问题都用一组未知数x1.x2xn表示某一方案，这组未知数的一组定值代表一个详细的规划方案。通常要求这些未知数取值是非负。以后我们称这组未知数为决策变量。 2约束条件。3目的函数。

4、 线性规划问题都有一个目的要求，并且这个目的可以表示为一组未知数的线性函数，称之为目的函数，按研讨问题的实践情况目的函数可以是求最小值也可以是求最大值。我们总是希望收益、效益、效率等目的到达最大化，而对于本钱、费用 、支出等目的那么希望到达最小化。2线性规划问题的共同特征综合上述这三点，这类问题都可以用如下数学言语来描画。目的函数： max ( min ) Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = ，b1 a21x1 + a22x2 + a2nxn = ，b2 am1x1 + am2x2 + amnxn = ，bm x1，x2， xn 0

5、3 线性规划问题的规范方式1线性规划的规范方式是： 目的函数： max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1 a21x1 + a22x2 + a2nxn = b2 am1x1 + am2x2 + amnxn = bm x1，x2， xn 0线性规划的规范方式是： max Z = c1 x1 + c2 x2 + + cn xna11 x1 + a12 x2 + a1n xn = b1a21 x1 + a22 x2 + a2n xn = b2 am1 x1 + am2 x2 + amn xn = bm x1，x2， xn 0max

6、Z =x j 0用求和符号表示规范方式，那么规范方式可简写为： 3 线性规划问题的规范方式线性规划的规范方式是： max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1a21x1 + a22x2 + a2nxn = b2 am1x1 + am2x2 + amnxn = bm x1，x2， xn 0 用矩阵表示规范方式，那么规范方式可简写为令C表示由目的函数的系数构成的矩阵，即 用A表示由约束条件的系数构成的矩阵， 即令X 表示由决策变量构成的矩阵，即 B表示约束条件向量，即 C=(c1，c2 ， ，c )； 3 线性规划问题的规范方式线性

7、规划的规范方式是： max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1a21x1 + a22x2 + a2nxn = b2 am1x1 + am2x2 + amnxn = bm x1，x2， xn 0 用矩阵表示规范方式，那么规范方式可简写为maxZ=CXC=(c1，c2 ， ，c )； AX=BX0 3 线性规划问题的规范方式线性规划的规范方式是： max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1a21x1 + a22x2 + a2nxn = b2 am1x1 + am2

8、x2 + amnxn = bm x1，x2， xn 0 几点称谓决策向量约束方程组的限定向量C=(c1，c2 ， ，c )； 价值向量约束条件系数矩阵2 将非规范形化为规范方式非规范方式是max ( min ) Z = c1x1 + c2x2 + + cnxna11x1 + a12x2 + a1nxn = ，b1a21x1 + a22x2 + a2nxn = ，b2 am1x1 + am2x2 + amnxn = ，bm x1，x2， xn 0规范方式是： max Z = c1x1 + c2x2 + + cnxn a11x1 + a12x2 + a1nxn = b1a21x1 + a22x2

9、+ a2nxn = b2 am1x1 + am2x2 + amnxn = bm x1，x2， xn 0 2 将非规范形化为规范方式非规范方式min Z = c1x1 + c2x2 + + cnxna11x1 + a12x2 + a1nxn = b1a21x1 + a22x2 + a2nxn = b2 am1x1 + am2x2 + amnxn = bm x1，x2， xn 0 1 假设目的函数求最小值可以把它转化为求负的同一目的函数的最大值，即 令Z= -Z min Z = max Z非规范方式 max Z = c1x1 + c2x2 + + cnxna11x1 + a12x2 + a1nxn

10、 b1a21x1 + a22x2 + a2nxn b2 am1x1 + am2x2 + amnxn bm x1，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 am1x

11、1 + am2x2 + amnxn = bm xk 无非负要求， xj 0 ，其他的变量大于等于零。3 假设决策变量无非负要求令xk =xk-xk, xk , xk03 假设要求决策变量 xj 0可令 xj = - xj xj 0 2 将非规范形化为规范方式试将线性规划问题化为规范方式： minz= -x1 + 2x2 - 3x3 x1 + x2 + x3 7 x1 - x2 + x3 2 -3 x1 + x2 + 2 x3 = 5 x1 ，x20例题 2 将非规范形化为规范方式4 用图解法求解线性规划 线性规划的图解法就是利用解析几何的方法来求解线性规划的问题。由于只需二维几何空间最为直观，

12、所以图解法只能用来求解二维线性规划问题，也就是只需两个决策变量的线性规划问题。下面我们结合实例来讲解线性规划的图解法。 求解线性规划问题maxZ2x1+5x2x14x23x1+2x2 8x10,x20例题 把 x1，x2 看作上平面上点的坐标，在第一象限内用图形将此规划问题的约束条件和目的函数都反映出来就是 约束条件围成了一个区域，这个凸多边形oabcd内的任一点的坐标都满足约束条件。而凸边形外的点都不能满足约束条件，所以凸多边形内的任一点的坐标都是这个线性规划问题的一个解，我们称之为可行解。凸多边形构成的可行解的全体，称为可行解集可行域。满足目的函数的一个可行解的全体z=2x1+5x2是一组

13、平行线，随z的添加不断向上平移，当移到b点时，到达最大值 2x1+5x2=19。图解法解题的根本步骤 确定可行域 确定目的函数挪动的方向 确定最优解用图解法求解如下线性规划问题min Z = 2x1 + 2x2x1 - x2 1x1 + 2x2 0 x1 ，x2 0练习1 用图解法求解如下线性规划问题min Z = 2x1 + 2x2-x1 + x2 1x1 + x2 -2x1，x2 0练习2 5 有关线性规划问题解的概念可行域一切可行解所构成的集合就是可行域对于图解法，可行域就是由约束条件围成的一个凸多边形，我们假设用R表示可行域，那么 R=x/Ax=b,x0可行解同样，在可行域上的点都满足

14、约束条件所以，我们称这些点为可行解。 x=(x1,x2xn)T x1 + x2 + x3 + x4+ x5 = 55 有关线性规划问题解的概念基设为约束方程组中的mn阶系数矩阵，其秩为m，秩为m的意思为m行线性无关，又B是中mn非奇特子矩阵|B|不等于0，那么称B是这个线性规划问题的一个基。 B=a11x1 + a12x2 + a1nxn = b1a21x1 + a22x2 + a2nxn = b2 am1x1 + am2x2 + amnxn = bm x1，x2， xn 0这是它的系数矩阵5 有关线性规划问题解的概念基设为约束方程组中的mn阶系数矩阵，其秩为m，秩为m的意思为m行线性无关，又

15、B是中mn非奇特子矩阵|B|不等于0，那么称B是这个线性规划问题的一个基。 B=B=a11x1 + a12x2 + a1nxn = b1a21x1 + a22x2 + a2nxn = b2 am1x1 + am2x2 + amnxn = bm =P1，P2，PM 基变量称Pj ( j=1,2m ) 为基向量，与Pj相对应的Xj ( j =1,2m)称为基变量。B=a11x1 + a12x2 + a1nxn = b1a21x1 + a22x2 + a2nxn = b2 am1x1 + am2x2 + amnxn = bm =P1，P2，PM 非基变量其他变量称为对应于的非基变量。根本解当取定一个

16、基时，令非基变量为0，由克莱姆法那么可得对应于该基的独一解。此解的非零数目不超越个m个，非0分量的数目等于m的根本解称为非退化的，否那么称为退化的。a11x1 + a12x2 + a1mx2 + + a1nxn = b1a21x1 + a22x2 + a2mx2 + + a2nxn = b2 am1x1 + am2x2 + a2mx2 + + amnxn = bm 例如当我们取为基时B=为基时根本解当取定一个基时，令非基变量为0，由克莱姆法那么可得对应于该基的独一解。此解的非零数目不超越个m个，非0分量的数目等于m的根本解称为非退化的，否那么称为退化的。a11x1 + a12x2 + a1mx

17、2 + + a1nxn = b1a21x1 + a22x2 + a2mx2 + + a2nxn = b2 am1x1 + am2x2 + a2mx2 + + amnxn = bm X=(x1 , x2 , , xm , 0 , 00)根本可行解满足非负条件的根本解叫根本可行解，它是根本解又是可行解。根本可行解的数目非零分量不大于m，并且都是非负的。普通地说，根本可行解的数目小于根本解的数目，最多是相等。 a11x1 + a12x2 + a1mx2 + + a1nxn = b1a21x1 + a22x2 + a2mx2 + + a2nxn = b2 am1x1 + am2x2 + a2mx2 +

18、 + amnxn = bm x1，x2， xn 0根本可行解X=(x1 , x2 , , xm , 0 , 00)根本可行解满足满足目的函数要求的可行解，称为线性规划问题的最优解。a11x1 + a12x2 + a1mx2 + + a1nxn = b1a21x1 + a22x2 + a2mx2 + + a2nxn = b2 am1x1 + am2x2 + a2mx2 + + amnxn = bm x1，x2， xn 0最优解X=(x1 , x2 , , xm , 0 , 00)max Z = c1x1 + c2x2 + + cnxn满足非负条件可行解根本解取定一个基根本可行解最优解满足目的函数

19、要求解 之 间 的 关 系max z= x3x1 + x2 + x3 + x4+ x5 = 4x1 + x2 + x3 + x4- x5= 4xi 0, i = 1,2,52 实际分支 例题1 对于约束方程组 x1 - x2 + 2 x3 = 1 x1 + x2 + x3 =1 x1 , x2 , x3 0系数矩阵 基 退化解 非退化解 2 实际分支 例 题 2 对于约束方程组 系数矩阵 基 退化解 非退化解 x1 + x2 - x3 = 1 x1 - x2 - x3 = 2x1 , x2 , x3 06 线性规划解的性质 设 是 n 维欧氏空间的一个点集，衔接中恣意两点 X、Y 的线段仍在内

20、，那么称 为凸集。 1、凸集的概念 XYXY图中每个点都是由n 维坐标表示的，这个n 维坐标与 向量是一致的，而向量是与线性规划问题的解是一致的。=1=u=1-u1 u 0 xyzZ= x+ ( y- x) u= ( 1- u) x+ u y任一点的表示方法令X Y 之间的相对长度为1，X Z之间的长度站整个长度 的 比例为U，6 线性规划问题解的性质 设 集合R是 n 维线性空间，假设其中恣意两点 X 和 Y ，假设对于恣意 1 u 0，都有 ( 1 - u ) x + u y 依然属于 R ，那么可说 R 为凸集。 1根本概念凸集数学表述 顶点 设 集合 R 是一个凸集，Z 是这个集合中中

21、的一点，假设在此集合中找不到两个不同的点 X 和 Y ，使 Z = ( 1- u ) x+ u y ，1 u 0 成立，那么可说 Z 点为S凸集的顶点。 x1x2x1x2 顶点的直观解释2线性规划问题解的性质定理 定理 1 线性规划问题的可行解集 R 为凸集。 首先，线性规划问题的可行解 X=(x1 , x2 , , xn)是一个 n 维向量，它可以看成是一个由 n 个坐标构成的点。线性规划问题能够有不止一个可行解,也就是说能够有很多个这样的点，这些点就构成了一个集合，很显然这个集合就是一个 n 维欧氏空间 ，我们要证明的结论，就是这个集合是一个凸集。XY线性规划问题一切的解 所构成的集合证明

22、这个问题的根本思绪 也就是，知 X 和 Y 是线性规划问题的两个不同的解，要证明这两个解的连线中间的恣意一个点也是线性规划问题的解，也就是 ( 1- u) x+ u y 也是一个解，也就是它也属于集合 R。证明过程设恣意 X 和 Y R， 目的是要证明对于恣意1 u 0, Z= u X + ( 1- u) Y R A Z = A u X + ( 1- u) Y 由于X、Y R，所以X 0， Y 0，而且 AX = B AY = B = A uX + A ( 1- u) Y = u B + ( 1- u) B = B定理 2 凸集的顶点对应于根本可行解。 首先，线性规划问题的可行解 X=(x1

23、, x2 , , xn)是一个 n 维向量，它可以看成是一个由 n 个坐标构成的点。线性规划问题能够有不止一个可行解,也就是说能够有很多个这样的点，这些点就构成了一个集合，上面曾经证明这个集合是一个 凸集。 此定理说，这个凸集的顶点是根本可行解 , 同样根本可行解也必是这个凸集的顶点. 首先还要了解根本可行解的含义, 根本可行解是线性规划问题系数矩阵一个特定的基所对应的可行解.根本解首先是一个可行解 , 然后它还是一个根本解.可行域R必要性的证明 也就是知线性规划问题的一个解X 是这个线性规划问题可行解集合(可行域) R 的顶点,要证明 X 是此线性规划问题的一个根本可行解.简单地加以分析 在

24、这个问题中,曾经知道了X 线性规划问题可行解集合(可行域) R 的顶点, 那么 X 就一定是一个可行解了. 关键是要如何再证明这个可行解是一个根本解了.可行域RX 设 X = (x1 , x2 , , xn)T ,中有 K 个分量大于 0 , 不失普通性可以设其前K 个分量大于 0 , 那么 X =(x1 , x2 , , xK , 0 , 0 , , 0 )T 那么约束条件 AX=B 中 AX 的就可以写成AX=x1 X2 xK0 0=(P1, P2,Pk)x1 X2 xKx1 X2 xK0 0=P1 P2 Pk Pn=x1 X2 xK0 0=x1 P1+ x2 P2+ xk Pk最终整理结

25、果就是： 那么,假设我们可以证明 P1,P2,Pk 是线性无关的 , 那么由P1,P2,Pk 列向量所构成的矩阵=x1 P1+ x2 P2+ xk Pkx1 X2 xK0 0AX=P1 P2 Pk Pn中的K个列向量是线性无关的,那么阐明必然存在一个K阶子矩阵BK是非奇特矩阵,也就阐明BK是一个基.这样,也就证明了X是一个根本可行解. 所以整个问题就转化为证明向量P1,P2,Pk 是线性无关的 ， 用反证法来证明这个问题。P1 P2 Pk 假设P1,P2,Pk是线性相关的 , 那么必然存在K个不全为0的数，y1, y2, , yk,使 y1 P1+ y2 P2+ yk Pk =0 成立。=x1

26、 P1+ x2 P2+ xk Pkx1 X2 xK0 0AX=P1 P2 Pk Pn 假设P1,P2,Pk是线性相关的 , 那么必然存在K个不全为0的数，y1, y2, , yk,使 y1 P1+ y2 P2+ yk Pk =0 成立。=x1 P1+ x2 P2+ xk Pkx1 X2 xK0 0AX=P1 P2 Pk Pn y1 P1+ y2 P2+ yk Pk=(P1, P2,Pk)y1 y2 yK(P1, P2,Pk,0, 0)y1 y2 yK00=AY而=0我们再来看向量 X X =(x1 , x2 , , xK , 0 , 0 , , 0 )T 由于 X 是可行解，所以X中的每个分量

27、 x1 , x2 , , xK 都必然大于0 ， 那么就可以取足够小的数 ，使X+ Y0， XY0 由于AX=B , AY=0那么 A X+ Y = A X+ A Y =B+0=B 同理 A X Y = B 这阐明X+ Y ， XY都分别是线性规划问题的解。 而X=1/2X+ Y + 1/2 XY 这阐明点 X 是点X+ Y和点 XY的中间点。是中间点就不是顶点。这与知相互矛盾，阐明假设不成立。也就证明向量P1,P2,Pk 是线性无关的，进而证明了解X 是线性规划问题的一个根本可行解。充分性的证明留给同志们本人课下学习定理 3 假设可行域 R 有界，那么线性规划问题的目的函数一定在其顶点处到达

28、最大值。有界可行域 R 无界可行域 R ABCD用反证法来证明这个问题，设X1， X2 Xh是可行域的顶点，而X0不是可行域的顶点，但目的函数却在X0处到达了最大值。有界可行域 R X1X2XH首先我们来证明X0可用其他顶点进展线性表示。即 X0=u1 X1+u2 X2+ uh Xh,而且u1 +u2 + uh =1X0首先我们来证明X0可用其他顶点进展线性表示。即 X0=u1 X1+u2 X2+ uh Xh,而且u1 +u2 + uh =1有界可行域 R XIXLXYX0 我们以二维可行域为例来证明这个问题。 由于X0=1-u1 XY+ u1 XK而 XK= 1-u2 XI+ u2 XLu1

29、1-u1XKu21-u2 最后可得 X0=1-u1 XY+ u1 1-u2 XI+ u1 u2 XL 可以验证各顶点前的 系数之和为 1。我们可以将此结论进展普通推行，就可得到首先我们来证明X0可用其他顶点进展线性表示。即 X0=u1 X1+u2 X2+ uh Xh,而且 u1 +u2 + uh =1有界可行域 R X1X2XHX0在回到原来的问题上，由于X0=u1 X1+u2 X2+ uh Xh,而且u1 +u2 + uh =1，因此 Z =C X0=C u1 X1+u2 X2+ uh Xh=u1C X1+u2C X2+ uh CXh 在一切顶点的目的函数值中，必然要有一个最大者，假设它是X

30、mu1C Xm+u2C Xm+ uh CXm=u1C Xm+u2C Xm+ uh CXm=CXm最终得到Z =C X0 CXm这与知是矛盾的，同时也阐明了最优解必然在顶点上获得。定理 3 假设可行域 R 有界，那么线性规划问题的目的函数一定在其顶点处到达最大值。定理 1 线性规划问题的可行解集 R 为凸集。 定理 2 凸集的顶点对应于根本可行解。 定理 3 假设可行域 R 有界，那么线性规划问题的目的函数一定在其顶点处到达最大值。定理 1 线性规划问题的可行解集 R 为凸集。 定理 2 凸集的顶点对应于根本可行解。 三个定理的回想以上三个定理阐明线性规划问题的一切可行解组成一个集合，也就是可行

31、域，这个可行域是凸集，这个 有有限个顶点，线性规划问题每一个根本可行解都对应着可行域的一个顶点，假设线性规划问题有最优解，那么最优解必然在顶点上到达。 以上三个定理阐明线性规划问题的一切可行解组成一个集合，也就是可行域，这个可行域是凸集，这个 有有限个顶点，线性规划问题每一个根本可行解都对应着可行域的一个顶点，假设线性规划问题有最优解，那么最优解必然在顶点上到达。三个定理 顶点个数 =1 单纯形法求解线性规划问题的根本思想第二节 单纯形法 123 对于线性规划问题的规范方式，从可行域中一个根本可行解出发，寻求使目的函数值有较大添加的另一个根本可行解，由于根本可行解个数是有限的，所以经过有限次迭

32、代目的函数值将逐渐增大最终到达最优。可行域 R 初始根本可行解改良根本可行解 终了最优 ？单纯形法求解线性规划问题的根本思想 123可行域 R 从以上分析可以看出 ，运用单纯形法求解线性规划问题，需求处理的三个方面问题是：1、初始根本可行解如何求；2、如何判别能否最优 ； 3、如何求改良的根本可行解。引 例 求解如下线性规划max Z = 2 x1 + 3 x2 2 x1 + x2 2 X1 + 3 x2 3 X1 , x2 0 1将上例化为规范方式max Z = 2 x1 + 3 x2 2 x1 + x2 +x3 =2 X1 + 3 x2 +x4 =3 X1 , x2 , x3, x4 0

33、第一步 首先要求出其根本可行解来2、找初始根本可行解约束方程的系数矩阵为: 此系数矩阵 A 中的两行很显然是线性独立的，所以它的秩为2， 我们可以恣意地组合其列向量 ，从而得到一个基，并求根本解。 例如，列向量P3，P4是线性无关的 ，所以P3，P4组合为矩阵可作为一个基。根据这个基，对照原约束方程组，就可以求出其对应的根本可行解来X1=0，0，2，3，将这个根本可行解代入目的函数表达式， max Z = 2 x1 + 3 x2 中，得到目的函数值为0， 从目的函数的表达式中，直观地看，添加非基变量x2的值，可以是目的函数得到较大的增长，所以 应该让非基变量 x2 变为基变量进基x1, 仍为非

34、基变量。即令x1=0，同时此例中不能超越二个基变量由于约束条件的系数矩阵的秩为2，最优解一定是二为的，还得从x3, x4中换出一个做非基变量离基并需保证非负条件， 2判别根本可行解能否是最优解 假设选 x 3 变量出基也就是使x 3 变量变为非基变量，非基变量的值为0，根据1式得到 x 2 =2，将 x 2 =2 代入2式得到， x4 =-3，这就不满足了第三个约束条件。所以不能选择x 3 作为出基变量。 同样方法，可以验证，选择 x4 变量作为出基变量是可以的。 3迭代也就是求改良的根本可行解 2 x1 + x2 +x3 = 2 1 X1 + 3 x2 +x4 = 3 2 X1 , x2 ,

35、 x3, x4 0 以上选择出基变量的方法可用数学的方法归纳为min 2/1 , 3/3,也就是 :min b1/a1j , b2/a2j , b3/a3j, , bm/amj 在确定了x 2 进基， x 4 出基以后，为了求得以 x2，x3 为基变量的上述新的根本可行解x (1) 及目的值z (x (1)，只需对原约束方程进展一次初等变换，即把方程组中第二等式里x2 的系数化为 1 也就是以第二等式里 x2 的系数化为1， 也就是以第二等式中 x2 的系数为主元进展一次高斯消元，得到 2 x1 + x2 +x3 =2 X1 + 3 x2 +x4 = 3 X1 , x2 , x3, x4 0

36、也就是以第二个等式中 x2 的系数为主元进展一次高斯消元，得到 1/3x1+x2 +1/3x4 = 1 5/3x1 +x3- 1/3x4 = 1 1/3x1+x2 + 1/3x4 = 1 3 5/3x1 +x3 -1/3x4 = 1 4将上述约束条件，变成关于基变量的表达式： x2=1-1/3x1-1/3x40 x3=1-5/3x1+1/3x40 将这个表达式代入目的函数得到： Z=3+x1-x4判别能否是最优解迭代 2 单纯形法的普通原理1从线性规划的系数矩阵能直接察看到。 x1 + 3 x4 + 2 x5 = 360 x2 + 4 x4 + 5 x5 = 200 x3 + 2 x4 + 7

37、 x5 = 300 x1，x2，x3 0MAX Z 7 x1 + 12 x2 B=P1，P2，P3=1、初始根本可行解确实定 由以上的引例我们可以看出，对于一个线性规划的问题，为了确定初始根本可行解，首先要找到一个初始可行基，这个可行基最好是一个单位矩阵，主要有三种方法： x1 + 3 x4 + 2 x5 = 360 x2 + 4 x4 + 5 x5 = 200 x3 + 2 x4 + 7 x5 = 300 x1，x2，x3 0MAX Z 7 x1 + 12 x2 x1 + 3 x4 + 2 x5 = 360 x2 + 4 x4 + 5 x5 = 200 x3 + 2 x4 + 7 x5 =

38、300 x1，x2，x3 0B=B=不能直接看出，要调整顺序 2对于约束条件是 “ 方式的不等式的情况，经过加非负的松弛变量可以等到一个单位矩阵。MAX Z 7 x1 + 12 x2 9 x1 + 4 x2 3604 x1 + 5 x2 2003 x1 + 10 x2 300 x1，x2，x3 0MAX Z 7 x1 + 12 x2 9 x1 + 4 x2 + x3 = 3604 x1 + 5 x2 + x4 = 2003 x1 + 10 x2 + x5 = 300 x1，x2，x3 ，x4 ，x5 0B= 3对于约束条件是“的方式，采用人工造基的方法减去一个非负的松弛变量，再加上一个非负的人

39、工变量总能得到一个单位矩阵。 x1 + 3 x4 + 2 x5 = 360 x2 + 4 x4 + 5 x5 = 200 2x3 + 2 x4 + 7 x5 300 x1，x2，x3 0MAX Z 7 x1 + 12 x2 黑板演示 找到了初始根本可行基，也就相应地找到了初始根本可行解。然后就要判别这个解能否是最优解。 判别最优时，目的函数必需化成关于非基变量的函数，假设是最优解，停顿；反之继续选代。 判别最优的规范，就是在目的函数中一切非基变量的系数均为负，假设系数大于零那么目的函数还能够添加，因此需求将一个非基变量进基，同时相应地要选择另一个基变量离基。2、最优性检验最优性检验的准那么 x1 + + a1m+1xm+1 + + a1nxn = b1 x2 + + a2m+1xm+1 + + a2nxn = b2 xm + ammxm+1 + + amnxn = bm x1，x2， xn 0max Z = c1x1 + c2x2 + + cnxnx1 = b1 -( a1m+1xm+1 + + a1nxn )x2 = b2 -( a2m+1xm+1 + + a2nxn ) xm