再将(1-17)式代入目标函数(1-11)式得到 z=9+2x 令非基变量x=x3=0,得到z=9,并得到另一个基可行解X (1) X=(0,3,2,16,0
再将(1-17)式代入目标函数(1-11)式得到 • (1 18) 4 3 9 2 z = + x1 − x5 − 令非基变量 x1=x5=0，得到 z=9，并得到另一个基可行解 X (1) X (1)=(0,3,2,16,0)T
从目标函数的表达式(1-18)中可以看到,非基 变量x1的系数是正的,说明目标函数值还可以 增大,X①)还不是最优解。 于是再用上述方法,确定换入、换出变量,继 续迭代,再得到另一个基可行解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-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)
再检查(-19)式,可见到所有非基变量x3x的 系数都是负数。这说明若要用剩余资源x3X 就必须支付附加费用。 所以当x3x4=0时,即不再利用这些资源时,目 标函数达到最大值。所以ⅹ(3)是最优解。即当 产品Ⅰ生产4件,产品Ⅱ生产2件,工厂才能得 到最大利润
• 再检查(1-19)式，可见到所有非基变量x3 ,x4的 系数都是负数。这说明若要用剩余资源x3 ,x4， 就必须支付附加费用。 • 所以当x3=x4=0时，即不再利用这些资源时，目 标函数达到最大值。所以X(3)是最优解。即当 产品Ⅰ生产4件，产品Ⅱ生产2件，工厂才能得 到最大利润
通过上例,可以了解利用单纯形法求解线性规划 问题的思路。现将每步迭代得到的结果与图解法 做一对比,其几何意义就很清楚了 原例1的线性规划问题是二维的, 即两个变量x1,x2;当加入松弛变量x3,x,x后, 变换为高维的。 这时可以想象,满足所有约束条件的可行域是高维 空间的凸多面体(凸集)
通过上例，可以了解利用单纯形法求解线性规划 问题的思路。现将每步迭代得到的结果与图解法 做一对比，其几何意义就很清楚了。 • 原例1的线性规划问题是二维的， • 即两个变量x1 ,x2；当加入松弛变量x3 ,x4 ,x5后， • 变换为高维的。 • 这时可以想象，满足所有约束条件的可行域是高维 空间的凸多面体(凸集)
这凸多面体上的顶点,就是基可行解。 初始基可行解X0=(0,0,8,16,12)T 就相当于图1-2中的原点(0,0), X()=(0,3,2,16,0)T 相当于 x1+2x2=8 4x1=16 图1-2中 4x2=12 的Q点(0,3); Q1 0
这凸多面体上的顶点，就是基可行解。 初始基可行解 X (0)=(0,0,8,16,12) T 就相当于图1-2中的原点(0，0)， X (1)=(0,3,2,16,0) T 相当于 图1-2中 的Q4点(0，3)；