数学建模基础知识 线性规划-单纯形方法[精品].ppt

例 求线性规划问题： max Z = 2x1 + x2 s.t. x1-x2 ≥-5 2x1-5 x2 ≤10 x1,x2 ≥ 0 标准型为： max Z = 2x1 + x2 s.t. -x1+x2 + x3 =5 2x1-5 x2 + x4=10 x1,x2 ，x3 ， x4 ≥0 * max Z = 2x1 + x2 s.t. -x1+x2 + x3 =5 2x1-5 x2 + x4=10 x1,x2 ，x3 ， x4 ≥0 * σ 2＞0, P 2 ≤0,无最优解。 * 例 求线性规划问题： max Z = 2x1 +4 x2 s.t. 2x1+2x2 ≤ 12 x1+2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12 x1,x2 ≥ 0 标准型为： max Z = 2x1 +4 x2 s.t. 2x1+2x2 + x3 =12 x1+2x2 +x4 = 8 4x1 + x5 = 16 4x2 + x6 = 12 xi ≥ 0,i=1,2,3,4,5,6 * 最终表为： x6换入x5换出 * 例1-19 求线性规划问题： max S = 2x1 + 3x2 s.t. x1+2x2 = 8 4x1 = 16 4x2 = 12 x1,x2=0 * 解：对目标函数标准化 max S = 2x1 +3x2 s.t. x1+2x2 +x3 = 8 4x1 +x4 = 16 4x2 +x5 = 12 x1 , x2 , x3 , x4 ,x5 = 0 1 2 1 0 0 A= 4 0 0 1 0 0 4 0 0 1 （ x1 x2 x3 x4 x5 ） =（ N B ） * 解： 1 0 0 B= 0 1 0 = I b = (8,16,12)T 0 0 1 x3 x4,x5为基变量，CB=（0，0, 0） x1 ,x2为非基变量。 有B-1=I, B-1b=b, B-1A=A,单纯性表如下： * 初始单纯性表TAB(1)为： * x2换入,x5 换出；得TAB(2)为： * x1换入,x3换出；得TAB(3)为： * x5换入,x4 换出；得TAB(4)为： * 此时所有的检验数小于等于零，此时的基础可行解 X=（4，2，0，0,4）T 就是最优解，对应的目标函数值： S = 14 就是最优值，对应的B