优化方法-线性规划.pptVIP

系数矩阵A为:令x2增加（由于目标函数中的x2系数较大），而x1仍保持为零，并使原基变量之一变为非基变量。0100A=010102001P3,P4,P5构成一个基，对应的基变量为x3,x4,x5,令非基变量x1,x2取零，则得一基本可行解（0,0,4,3,8）Tx1=0时，x3=4≥0x4=3-x2≥0x5=8-2x2≥0将基变量关于非基变量解出Ζ=2x1+5(3-x4)=15+2x1-5x4令x1增加，使原基变量之一为零x4=0时x3=4-x1≥0x2=3≥0x5=2-x1≥0其仍然不是最优解.这时，得一基本可行解（0,3,4,0,2）T，目标函数值为15.并将目标函数中的基变量用非基变量代替x3=4-x1x2=3-x4x5=8-x1-2(3-x4)=2-x1+2x4x1=2时,x5=0用非基变量表示基变量x1=2+2x4-x5x2=3-x4x3=2-2x4+x5单击此处添加小标题用非基变量替换目标函数中的基变量，得Ζ=15+2(2+2x4-x5)-5x4=19-x4-2x5单击此处添加小标题从一个基本可行解向另一个基本可行解的迭代过程，相当于从一个极点向另一邻接极点的过渡。这时得到最优解（2,3,2,0,0）T，Ζmax=19.单击此处添加小标题(0,3)(2,3)(4,2)(4,0)x1x20...3.2初始基本可行解的确定1.若线性规划问题minΖ=CXs.t.AX=bX≥0系数矩阵A中存在一单位矩阵B，则B为一个可行基。2.若约束条件是“≤”形式的不等式，则可以通过标准化的方法，引入m个非负的松驰变量AX+IXS=bX≥0,XS≥03.若约束条件是“≥”形式或等式约束不存在单位矩阵的情况，则采用人造基方法（见后面）3.3最优性检验以矩阵形式表示单纯形的迭代过程minΖ=CXs.t.AX=bX≥0A=(B,N),X=(XB,XN)T,C=(CB,CN)，则上式可写为minΖ=CBXB+CNXNs.t.BXB+NXN=bXB,XN≥0将基变量用非基变量表示XB=B-1b-B-1NXN代入目标函数，得Ζ=CB(B-1b-B-1NXN)+CNXN=CBB-1b+(CN-CBB-1N)XNXB=B-1b,XN=0为一基本可行解。1.最优解判别定理：若X(0)=(B-1b,0)T为对应于基B的基本可行解，且CN-CBB-1N≥0,则X(0)为最优解。[证]对一切可行解XCX=CBB-1b+（CN-CBB-1N）XN≥CBB-1b所以，X(0)=(B-1b,0)T为最优解。若把上面的矩阵形式表示为方程组，则为对应于基B的基本可行解，且对于一切j=m+1,2,…,n,?j?0，则X(0)为最优解。则上面的判别定理表示为：若X(0)=(b1?,b2?,…,bm?,0,…0)T2.无穷多最优解判别定理：添加标题若X(0)=(b1’,b2’,…,bm’,0,…0)T为一基本可行解，对于一切j=m+1,…,n,有?j≤0,又存在某个非基变量xm+k的检验数?m+k=0,则线性规划问题有无穷多最优解。添加标题[证]只需将非基变量xm+k换入基变量中，找到一个新的基本可行解X（1），因?m+k=0，知z=z0，故X（1）也是最优解，由2.2定理3可知，X(0)、X（1）连线上所有点都是最优解。添加标题无界解判别定理：添加标题[证]取xm+k为进基变量，令xm+k增加，并取其余非基变量为零，则得添加标题若X(0)=(b1’,b2’,…,bm’,0,…0)T为一基可行解，且有一个?m+k0,并且对i=1,2,…,m,有ai’,m+k≤0,那么该线性规划问题没有有限最优解。添加标题令xm+k=??0，显然，这时目标函数值为z=z0+??m+k→+?（?→+?）故没有有限最优解。01添加标题基变换02添加标题换入变量的确定03一般取?j0中的最大者max(?j0)=?k对应的xk为换入变量。换出变量的确定迭代（旋转运算）0102线性规划数学教研室石鸿雁引言线性规划是数学规划的一个重要分支，历史比较悠久，理论比较成熟，方法较为完善。线性规划的思想最早可以追溯到1939年，当时的苏联数学家、经济学家（康特罗维奇）在《生产组织与计划中的数学方法