《同济大学线性规划教案.doc》由会员分享，可在线阅读，更多相关《同济大学线性规划教案.doc（44页珍藏版）》请在金锄头文库上搜索。
1、第一章 线 性 规 划标准型线性规划(LP):min f = c1X1+ cjXj+cnXn =cjXjs.t a11x1+a1jxj+a1nxn = b1 ai1x1+aijxj+ainxn = bi am1x1+amjxj+amnxn = bm xj0, j=1,n.C= X = b=A=min f=C T Xs.t AX=bx0min f = c1X1+ cjXj+cnXn =cjXjs.t ai1x1+aijxj+ainxn = bi i=1,m xj0, j=1,n. 在几何直观上告诉我们，若两个变量的线性规划问题的最优解存在且唯一，则最优解必为可行域K的一个顶点，而K为凸多边形对于
2、目标函数求min的两个变量的线性规划，根据目标函数的等值线与可行域K的各种关系，我们可以得知它的解可能会出现以下几种情况(1) 最优解存在且唯一这时，K是一个非空的、有界或无界的凸多边形，最优解X*必为K的一个顶点，最优值f*为一个有限值。(2)最优解x*存往但不唯一这时，K是一个非空、有界或无界的凸多边形，最优值f*是一个有限值，f的等值线c1x1+c2x2= f*与K之交是K的一个边界，网此该边界上的点都为最优解；但是，我们至少可以取到K的一个顶点为最优解。(3)可行解存在但目标函数值在K内无下界(简称线性规划无下界)这时，K必是一个非空无界的凸多边形，最优解不存在，minf (4)可行解
3、不存在(或称线性规划不可行)这时，K为空集。 通过以上各种情况的分析，关于2个变量的线性规划的解，我们可以得到以下两点结论： 如果K(空集)，则K必是x1ox2坐标平面第一象限内的一个凸多边形(今后，在线性规划理论中，称为凸集)，K的顶点一定存在如果最优解X*存在，则最优解中至少有一个为K的顶点（请学生看书第9页，请教师朗读书上这些结论） 13基本可行解非基本变量（独立变量）基本变量 （非独立变量）基本解 基本可行解基 B若BO，称B为（LP）的一个基。Min f = c1X1+ cjXj+cnXn =cjXjs.t ai1x1+aijxj+ainxn = bi I=1,mxj0, j=1,n
4、.令C = b= X=A= B=min f=C T Xs.t AX=bx0A= IB对应的基本矩阵B：B=矩阵B为基本变量xB ,， xBm在A矩阵中的系数列向量。ai1x1+aijxj+ainxn = bi I=1,m w+ c1X1+ cjXj+cnXn =0当IB给定时，将上述方程组变换为典型方程组：xBi +0w +yijXj+ = , i=1,mw+ rjXj + =f。 + = i, w +rjXj =f。-f（X）+rjXj = f。= f（X。）f（X）= f（X。）+rjxj 14 单纯形法单纯形法的基本步骤是： 1、 求(LP)的初始基本可行解X。，并将(LP) 的有关信息
5、制成表格(称为单纯形表)。2 、判别X。是否为最优解?为此，需要给出一个基本可行解是否为最优解的判别准则。 3、若X。不是最优解，则应另求基本可行解x，且使CTX CTX。(至少CTXCTX。)。同时，我们由X。相应的单纯形表给出x相应的单纯形表。（该步骤称为转轴）(4)当x不是最优解时，视x为X。，重复上述步骤，直至(LP)求得最优解或判定f在K内无下界。 定理1-2（3）如果T（B）中存在rt0（tID），且对于i=1，m均有yit0，则（LP）的目标函数在可行域上无下界。15单纯形表的矩阵描述我们前面已经说明过： ai1x1+aijxj+ainxn = bi i=1,m w+ c1x1+
6、 cjxj+cnxn =0当IB给定时，将上述方程组变换为典型方程组：xBi +0w +yijxj+ = , i=1,mw+ rjxj + =f。这些信息就构成了单纯形表。即 + = w +rjXj =f。若是记：yj=(y1j,yij,ymj)T， = (由挂图的单纯形表中得到， XB + = , 下面我们来推导和yj以及rj的公式。给定IB和基本矩阵B（BO），假设：A=B，DAX=b化成 B，D= b BXB + DXD = b，两边左乘B-1XB + B-1DXD = B-1bXB + B-1，A.j,=B-1 bXB + =B-1b进行比较可得：yj= B-1A.j,= B-1b由w
7、+ rjXj + =f。得：w +rjXj =f。现在我们来推导rj的公式。得到由w+ c1x1+ +cjxj+cnxn =0即w+ CTX =0，（结合挂图讲解CBT和CDT）w+ CBT，CDT =0，即w+ CBT XB + CDT XD = 0由XB + = ， 得 XB = - 代入：得到rj= cj - CBT yj= cj- CBT B-1A.j f。= CBT= CBT B-1b请同学看书27页yj= B-1A.j= B-1brj= cj - CBT yj= cj- CBT B-1A.jf。= CBT= CBT B-1b 17大M法和两阶段法171大M法min f =s.t.
8、i=1,m, xj0, j=1, n.引进松弛变量xn+1,xn+m, min f =s.t. i=1,m,xj0, j=1,n我们取IB=n+1，n+m，由于b0,可以很方便地取得一个初始基本可行解。如果我们的规划是下列形式，问题就变得复杂： min f =s.t.（=，）bi， i=1,m, xj（=，）0, j=1, n.将它标准化后，不能够很快地观察出一个初始基本可行解。 例1-14min f= -x1 - 3x2 + x3s.t. x1 + x2 + 2x3 = 4-x1 + 2x2 + x3 = 4 xj0, j=1,2，3. 人工变量x4和 x5x1 + x2 + 2x3 + x
9、4 = 4-x1 + 2x2 + x3 + x5 = 4 min f= -x1 - 3x2 + x3 + Mx4 + Mx5s.t. x1 + x2 + 2x3 +x4 = 4-x1 + 2x2 + x3 + x5 = 4xj0, j=1，5.（LPM）C-1 -3 1 M MCBXBx1 x2 x3 x4 x5Mx4x51 1 2 1 0-1 2 1 0 144 M r-1 -3-3M 1-3M 0 0-8MC-1 -3 1 M MCBXBx1 x2 x3 x4 x5Mx4x51 1 2 1 0-1 2 1 0 144 M r-1 -3-3M 1-3M 0 0-8MXBx1 x2 x3 x4
10、 x5x4x23/2 0 3/2 1 -1/2-1/2 1 1/2 0 1/222r-1.5M-2.5 0 -1.5M+2.5 0 1.5M+1.5-2M+6Y11=3/2作为转轴元素，带上括弧，得下表：XBx1 x2 x3 x4 x5X1X21 0 1 2/3 -1/30 1 1 1/3 1/34/38/3r0 0 5 M+（5/3） M+（2/3）28/3最优解X*=（4/3，8/3，0）T最优值f*=-28/3。例1- 15min f= -3x1- 2x2 s.t. 2x1 + x2 23x1 + 4x2 12xj0, j=1,2.其（LPM）为：min f= -3x1- 2x2+ Mx
11、5 s.t. 2x1 + x2 + x3 = 23x1 + 4x2 x4 + x5 = 12xj0, j=1,，5.解： C -3 -2 0 0 MCBXBx1 x2 x3 x4 x50Mx3x52 （1） 1 0 03 4 0 -1 1212r-3M-34M-2 0 M 0-12MCBXBx1 x2 x3 x4 x5-2MX2x52 1 1 0 0-5 0 -4 -1 124r5M+1 0 4M+2 M 0-4M+4线性规划不可行。例1-16min f= 2x1- x2 s.t. 2x1 + 3x2 6x1 -x2 6xj0, j=1,2.其（LPM）为：min f= 2x1- x2+ Mx5 s.t. 2x1 +3 x2 - x3 + x5 = 6x1 -x2 +x4 = 6xj0, j=1,，5.解： C 2 -1
