线性规划问题单纯形法.ppt

线性规划LinearProgramming（LP）单纯形表计算步骤举例给定线性规划问题maxz=50X1+30X2s.t.4X1+3X2≤1202X1+X2≤50X1，X2≥0maxz=50X1+30X2s.t.4X1+3X2+X3=1202X1+X2+X4=50X1，X2，X3，X4≥0线性规划LinearProgramming（LP）单纯形表计算步骤举例maxz=50X1+30X2s.t.4X1+3X2+X3=1202X1+X2+X4=50X1，X2，X3，X4≥02120/450/2X111/201/2250201-2050-2520/125×211X2150-1/23/210-5-15线性规划LinearProgramming（LP）单纯形法的进一步讨论人工变量法：当一般线性规划问题标准化之后，我们或可得到一个显然的基本可行解（如松弛变量作为基变量的一个初始基本可行解），这样我们就可以马上进入单纯形表的运算步骤。然而，并非所有问题标准化之后我们都可得到一个显然的初始基本可行解，这时就需要我们首先确定出一个基本可行解作为初始基本可行解。通常采用的是人工变量法来确定这样的初始基本可行解。这种情况下一般有两种方法：大M法（罚因子法）两阶段法第五章与单纯形表线性规划LinearProgramming（LP）图解法的启示线性规划问题解的可能情况a.唯一最优解b.无穷多最优解c.无解（没有有界最优解，无可行解）若线性规划问题的可行域非空，则可行域是一个凸集；若线性规划问题的最优解存在，则一定可以在可行域的凸集的某个顶点上达到。线性规划LinearProgramming（LP）单纯形法单纯形方法是G.B.Danzig于1947年首先发明的。近50年来，一直是求解线性规划的最有效的方法之一，被广泛应用于各种线性规划问题的求解。本节讨论单纯形法的基本概念、原理及算法。线性规划LinearProgramming（LP）单纯形法给定线性规划问题（标准形式）maxz=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2s.t.……………am1x1+am2x2+…+amnxn=bmxj≥0（j=1，2…n）线性规划LinearProgramming（LP）单纯形法一、线性规划问题的解的概念可行解最优解基基解（基本解）基可行解可行基线性规划LinearProgramming（LP）单纯形法二、凸集及其顶点凸集顶点（极点）凸集凹集线性规划LinearProgramming（LP）12345678基解（可行）基解（不可行）线性规划LinearProgramming（LP）单纯形法三、线性规划基本定理基本定理1线性规划所有可行解组成的集合S={X|AX=b，X≥0}是凸集。基本定理2X是线性规划问题的基本可行解的充要条件为是X是凸集S={X|AX=b，X≥0}的极点。基本定理3给定线性规划问题，A是秩为m的m?n矩阵，（i）若线性规划问题存在可行解，则必存在基本可行解（ii）若线性规划问题存在有界最优解，则必存在有界最优基本可行解。线性规划LinearProgramming（LP）单纯形法