资源描述
线性规划模型的标准型线性规划模型的标准型 基本概念与基本定理基本概念与基本定理 单纯形法的基本思想单纯形法的基本思想(一一)、一般型、一般型a11X1+a12X2+a1nXn=b=b1 1a21X1+a22X2+a2nXn=b=b2 2 am1X1+am2X2+amnXn=b=bm mXj j 0(0(j=1,2,n)Max Z=C1X1+C2X2+CnXn其中其中 bi 0(0(i=1,2,m)线性规划模型的标准型线性规划模型的标准型(二二)、矩阵型、矩阵型Max Z=CXAX=bX 0 0 P P1 1 P P2 2 P Pn n a11 a12 a1n其中其中 A=A=a21 a22 a2n am1 am2 amn X1 X=X2 Xn b1 b=b2 bmC=(C1 C2 Cn)Max Z=CX AX=b X 0 01 1可行解可行解 X X 满足满足 0XbAX2 2最优解最优解 X X 满足满足 CXCX*(m n)r(A)=m,至少有一个至少有一个m阶子式不为阶子式不为0基（基阵）基（基阵）a11 a1m a1m+1 a1na21 a2m a2m+1 a2n am1 amm amm+1 amnP1 Pm Pm+1 PnBNA=定义：定义：基基(基阵基阵)A中一个子矩阵中一个子矩阵B是可逆是可逆矩阵，则方阵矩阵，则方阵B称为称为LP问题的一个基。问题的一个基。A=(P1 Pm Pm+1 Pn)=(B N)基向量基向量 非基向量非基向量X=(X1 Xm Xm+1 Xn)T=基变量基变量 非基变量非基变量 XB=(X1 Xm)T XN=(Xm+1 Xn)T)(NBXX例例1、X1+2X2+X3=30=30 3X1+2X2 +X4=60 2X2 +X5=24 X1 X5 0 01 2 1 0 03 2 0 1 00 2 0 0 1P1 P2 P3 P4 P5A=4 4基本解基本解对应于基对应于基B，为为AX=b的一个解。的一个解。01bBXXXNB基本可行解基本可行解满足满足的的基本解基本解，基基B-B-可行基可行基01bB001NBXbBX max Z=70X1+120X2 P1 P2 P3 P4 P5 9X1+4X2+X3=360 9 4 1 0 0 4X1+5X2+X4=200 A=4 5 0 1 0 3X1+10X2+X5=300 3 10 0 0 1 Xj0 j=1,2,5这里m=3,n=5。Cmn=10 基(p3,p4,p5)，令非基变量x1,x2=0，则基变量x3=360,x4=200,x5=300,可行解 基（p2,p4,p5）,令非基变量x1=0,x3=0基变量x2=90,x4=250,x5=600.非可行解 基（p2,p3,p4），令非基变量x1,x5=0，则基变量x2=30,x3=240,x4=50,可行解（P17图）可行解可行解基基本本解解Cnm=n!m!(n-m)!(m n)基本可行解个数有限，当约束条件为基本可行解个数有限，当约束条件为m个，个，n个变量时，基本可行解个数不超过个变量时，基本可行解个数不超过:定理定理1：线性规划问题的可行解域一定：线性规划问题的可行解域一定是凸集。目标函数在凸集的顶点处达是凸集。目标函数在凸集的顶点处达到最优到最优 定理定理2:基本可行解基本可行解可行域顶点可行域顶点I.单纯形法单纯形法 的基本思想的基本思想迭代法迭代法初始可行基B0XB0=B0-1b，XN=0检验是否最优？确定新的可行基B，XB比原来好。停Y YN N1.初始可行基（基本可行解）的确定.，若A中有单位矩阵I，直接取初始可行基 A中不含有有单位矩阵I，用人工变量确定B0 bAX IB 0Max Z=CX AX=b X 0 0通过目标函数表达式其中：检验数 若所有，则目前解为最优解。jNjjBIjxbBCCXZ1jBjjPBCc10j2.检验：已知B0可行基，判断基本可行解是否最优 01NBXbBXTNBXXX),(Xr为出基变量由最小比值法求：kmrrakmiiababkmi0min取max j=m+kXm+k 进基变量0j出基变量进基变量3.若 ，寻找更好的基 .4.以为主元，换基迭代。kmra5.这样，不断迭代，直至检验数，找到最优解。0j
展开阅读全文