位置对换 为了求得以x3,x4,x2为基变量的一个基可行解和进 一 步分析问题，需将(1-13)中x,的位置与x的位置对换。 得到 x3=8-x1-2x2 x4=16-4x1 (1-13) =12 4×2 x3 +2X2=8-x1 () XA =16-4x1 (2) (1-16) 4X2 =12 一X5 (3)
位置对换 )131( 412 416 28 5 2 4 1 3 21 − ⎪⎩ ⎪⎨⎧ −= −= −−= x x x x xxx ( ) ( ) ( ) )161( 124 3 416 2 82 1 2 5 4 1 3 2 1 − ⎪⎪⎩ ⎪⎪⎨⎧ −= −= −=+ x x x x xx x 为了求得以x3,x4,x2为基变量的一个基可行解和进一 步分析问题，需将(1-13)中x2的位置与x5的位置对换。 得到
高斯消去法 ·将(1-16)式中x,的系数列向量变换为单位列向量。 其运算步骤是： ③′=③/4；①′=①-2×③′；②′=②， ·并将结果仍按原顺序排列有： X3=2-1+ -x5 () x4=16-4x1 (2) 1-17) 1 X2=3 3)
高斯消去法 • 将(1-16)式中x2的系数列向量变换为单位列向量。 其运算步骤是： • ③′=③/4；①′=①-2×③′;②′=②, • 并将结果仍按原顺序排列有： ( ) ( ) ( ) ( ) 171 3 4 1 3 416 2 1 2 1 2 ' 2 5 ' 4 1 ' 3 51 − ⎪⎪⎪⎩ ⎪⎪⎪⎨⎧ = − −= +−= x x x x x xx
再将(1-17)式代入目标函数(1-11)式得到 3 z=9+2145 1-18 令非基变量x=X0,得到z9,并得到另一个基可行解X1 X=(0,3,2,16,0)
再将(1-17)式代入目标函数(1-11)式得到 ( ) 181 4 3 29 −+= xxz 51 − 令非基变量 x1=x 5=0，得到 z=9，并得到另一个基可行解 X(1) X(1)=(0,3,2,16,0)T
迭代 ·从目标函数的表达式(1-18)中可以看到，非基 变量x,的系数是正的，说明目标函数值还可以 增大，X)还不是最优解 0 于是再用上述方法，确定换入、换出变量，继 续迭代，再得到另一个基可行解X2 ·X2)=(2,3,0,8,0)T ·再经过一次迭代，再得到一个基可行解X3) ·X3)=(4,2,0,0,4)1 ·而这时得到目标函数的表达式是： ·z=14-1.5x30.125x4 (1-19)
迭代 • 从目标函数的表达式(1-18)中可以看到，非基 变量x1的系数是正的，说明目标函数值还可以 增大，X(1)还不是最优解。 • 于是再用上述方法，确定换入、换出变量，继 续迭代，再得到另一个基可行解X(2) • X(2)=(2,3,0,8,0)T • 再经过一次迭代，再得到一个基可行解X(3) • X(3)=(4,2,0,0,4)T • 而这时得到目标函数的表达式是： • z=14-1.5x3-0.125x4 (1-19)
最优解 ·再检查(1-19)式，可见到所有非基变量 X2x4的系数都是负数。这说明若要用剩 余资源x3,x4,就必须支付附加费用。 ·所以当X,X0时，即不再利用这些资源 时，目标函数达到最大值。所以X3)是最 优解。即当产品I生产4件，产品Ⅱ生产 2件，工厂才能得到最大利润
最优解 • 再检查(1-19)式，可见到所有非基变量 x3,x4的系数都是负数。这说明若要用剩 余资源x3,x4，就必须支付附加费用。 • 所以当x3=x4=0时，即不再利用这些资源 时，目标函数达到最大值。所以X(3)是最 优解。即当产品Ⅰ生产4件，产品Ⅱ生产 2件，工厂才能得到最大利润