运筹学oroperationsresearch运筹学是应用分析、试验

运筹学oroperationsresearch运筹学是应用分析、试验内容摘要：

2121112211nmnmnmmnnnnnnxxbxaxaxabxaxaxabxaxaxaxcxcxcZ设系数矩阵 A的秩是 m， 即 A的 m个行向量是线性无关的。 若 B是 A的 m阶满秩子阵 ，称 B为问题的一个基。 B=( P1， P2 ， … ， Pm) 对应的变量 ( x1， x2 ， … ， xm)称为基变量 其它的变量称为非基变量； 令非基变量等于 0，从方程组可以唯一解出基变量的值，从而得到方程组的一个解，称为基本解；如果它的各个分量非负，即它同时又是可行解，则称之为基可行解，对应的基称为可行基。 三、 LP解的性质 设 D为 n维空间的点集，若对任意 X1∈ D，X2∈ D，和实数 α（ 0≤α≤1），都有 αX1+（ 1－ α） X2∈ D，则称 D为凸集。 凸集 D中如果不存在两个不同的点 X1∈ D，X2∈ D，使 X=αX1+（ 1－ α） X2（ 0α1）成立，那么点 X称为极点。 定理 1 线性规划的可行域 R是凸集。 证 对于 LP max z=CX AX =b X ≥0 设 X1∈ R， X2∈ R， 则有 Xi≥0， AXi=b 对于任意 α∈ [0， 1]， X=αX1+（ 1－ α） X2≥0 AX=A[αX1+（ 1－ α） X2] = αAX1+（ 1－ α） AX2 =αb+（ 1－ α） b=b 故 X∈ R， R是凸集。 引理 设 X是线性规划的可行解，则 X是基可行解的充分必要条件是 X的正分量对应的系数列向量是线性无关的。 证 （ 1）必要性。 由基可行解的定义显然成立。 （ 2）充分性。 不妨设 X的前 k个分量为正，若向量P1,P2,…, Pk线性无关，则必有 k≤m。 当 k=m时，它们恰好构成一个基，从而 X是基可行解。 当 km时，由于 A的秩为 m，从 A中一定可以再找出 mk个列向量与 P1,P2,…, Pk线性无关，共同构成一个基，其对应的解就是 X，所以 X是基可行解。 定理 2 X是线性规划基可行解的充分必要条件是 X是可行域的极点。 证 （ 1） X不是基可行解， 则 X不是可行域的极点。 不失一般性，假设 X的前 m个分量为正，则有 1bmjjjPx由引理知 P1,P2,…, Pm线性相关，即存在不全为零的数 ( 1 , , )i im  使得 1 1 2 2 0mmP P P     1 1 2 2 0mmP P P        （ 1） （ 2） 令 m i n 0j jjx则 0jjx 设 1 1 1 2 2( , , , , 0 , , 0) TmmX x x x        2 1 1 2 2( , , , , 0 , , 0) TmmX x x x        则 12,X R X R（ 1） +（ 2）得： 1 1 1 2 2 2( ) ( ) ( ) bm m mx P x P x P           （ 1） （ 2）得： 1 1 1 2 2 2( ) ( ) ( ) bm m mx P x P x P           又 12( ) / 2X X X即 X不是可行域的顶点。 （ 2） X不是可行域的极点， 则 X不是基可行解。 不失一般性，设 12( , , , , 0 , , 0) TrX x x x不是可行域的极点 存在两个不同的点 ,Y R Z R 有 X=αY+(1－ α)Z 即 ( 1 ) ( 0 1。 1 , , )j j jx y z j n       因 0 , 1 0   故 0jx 时 0jjyz故 11=bnrj j j jjjP x P x因 11=bnrj j j jjjP y P y11=bnrj j j jjjP z P z（ 1） （ 2） （ 1） （ 2）得： 1( ) = 0rj j jjy z P因 YZ 故 P1,P2,…, Pr线性相关 定理 3 线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。 证 （ 1）不失一般性，假设可行解 X的前 m个分量为正。 如果 P1,P2,…, Pm线性无关，则 X是基可行解。 ( 1 , , )i im 使得 1 1 2 2 0mmP P P     令 m i n 0j kjkjx x  则 0jjx 设 1 1 1 2 2( , , , , 0 , , 0) TmmX x x x        2 1 1 2 2( , , , , 0 , , 0) TmmX x x x        则 12,X R X R 12( ) / 2X X X若 0k 则 X2比 X少一个正分量，若 X2的 m1个列向量 线性无关，则 X2是基可行解，否则，重复以上过程，直到找到基可行解为止。 如果线性相关即存在不全为零的数 （ 2）设 X0是最优解，如果它不是基可行解，则有 10X X R   20X X R  1 0 0()CX C X CX C      2 0 0()CX C X CX C      00C X C X C 00C X C X C 则 0C  0 1 2CX CX CX故 X1， X2也是最优解，如前所述， X1， X2中一定有一个点比X0少一个正分量。 同理，如果 X1（ X2）还不是基可行解，则能找到第三个最优解，其正分量比 X1（ X2）少一个，如此继续下去，一定可以求得一个最优解，它的正分量是线性无关的，即这个最优解为基可行解。 第三节单纯形法 一、 单纯形法的解题思路 cj c1 c2 … cm cm+1 … ck … CB XB b x1 x2 … xm xm+1 … xk … xn c1 c2 cm x1 x2 xm b1 b2 bm 1 0 … 0 a1m+1 … a1k … a1n 0 1 … 0 a2m+1 … a2k … a2n 0 0 … 1 amm+1 … amk … amn σj 0 0 … 0         。