最优化方法—线性规划.ppt

线性规划;引言;引言;引言;引言;线性规划（LP）;圆桌 0.18 0.08 6;[解]设生产圆桌x1个，衣柜x2个; 线性规划问题：约束条件及目标函数均为未知量的线性函数，求目标函数的最大或最小值问题。 ;a21x1+a22x2=b2;那么，怎样找这条直线呢？让直线c1x1+c2x2=h 沿着它的正法线（梯度）方向移动，移动到刚刚开始要离开K的时候，这时的直线仍与K相交，也就是还通过K的点.;x1+x2=5;x1-3x2=-3;例4．Max S=3x1+x2 s.t. x1-x2≤-1 x1+x2≤-1 x1,x2≥0 此问题无可行解。 ;;化一般问题为标准形式：;a11 a12 …a1n ┆ ┆ ┆ am1 am2 …amn ;4 线性规划问题的解;例. Min Z=2x1+x2 s.t. x1+x2+x3 =5 -x1+x2 +x4 =0 6x1+2x2 +x5=21 xj≥0,j=1,2, …5;1 0 0 0 1 0 0 0 1;2.线性规划问题的几何意义;2.2基本定理 ;单纯形法的基本思想 ;3.单纯形法;s.t. x1 +x3 =4 x2 +x4 =3 x1+2x2 +x5=8 xj≥0,j=1,2,…,5;系数矩阵A为:;将基变量关于非基变量解出;x1=2时,x5=0;(0,3); 2.若约束条件是“≤”形式的不等式，则可以通过标准化的方法，引入m个非负的松驰变量; min Ζ=CBXB+CNXN s.t. BXB+NXN=b XB,XN≥0 ;若把上面的矩阵形式表示为方程组，则 ;2.无穷多最优解判别定理：;令xm+k=??0，显然，这时目标函数值为 z=z0+??m+k→+? （?→+? ） 故没有有限最优解。; 一般取?j0中的最大者 max(?j0)=?k 对应的xk为换入变量。 ;§4.单纯形法的计算步骤 ;4.2计算步骤;例1 minΖ=2x1+5x2 s.t. x1≤4 x2≤3 x1+2x2≤8 x1,x2≥0 ; XB b x1 x2 x3 x4 x5 θ x3 4 1 0 1 0 0 - x4 3 0 1 0 1 0 3 x5 8 1 2 0 0 1 4 0 2 5 0 0 0 ;例2．min z=3x1+x2+3x3 s.t. 2x1+x2+x3≤2 x1+2x2+3x3≤5 2x1+2x2+x3≤6 xi≥0,i=1,2,3 [解] 标准化后，写出单纯形表 ; XB b x1 x2 x3 x4 x5 x6 θ x2 1 5 1 0 3 -1 0 1/5 x3 1 -3 0 1 -2 1 0 - x6 3 -5 0 0 -4 1 1 - 7 0 0 3 -2 0 ;5.单纯形法的进一步讨论 5.1人工变量法 若线性规划问题的约束条件 a11x1+…+a1nxn=b1 ┆ ┆ ┆ am1x1+…+amnxn=bm 不存在单位矩阵。我们可以强行为约束条件加入一单位矩阵 a11x1+…+a1nxn+xn+1 =b1 a21x1+…+a2nxn +xn+2 =b2 ┆ ┆ ┆ ┆ am1x1+…+amnxn +xn+m=bm xj≥0,j=1,2, …,m+n xn+1, …,xn+m称为人工变量。因为人工变量必须为零，所以若经过基变量的逐步转换，最优解中不存在人工变量;则原问题有解；若最优解中还存在人工