每步迭代的几何意义 ·原例1的线性规划问题是二维的，即两个变量 x1,x2;当加入松弛变量x3,X4,x后，变换为 高维的。 ·这时可以想象，满足所有约束条件的可行域 是高维空间的凸多面体（凸集）。 ·这凸多面体上的顶点，就是基可行解
每步迭代的几何意义 • 原例1的线性规划问题是二维的，即两个变量 x 1,x 2；当加入松弛变量x 3,x 4,x 5后，变换为 高维的。 • 这时可以想象，满足所有约束条件的可行域 是高维空间的凸多面体(凸集)。 • 这凸多面体上的顶点，就是基可行解
每步迭代的几何意义 ·初始基可行解Xo)=(0,0,8,16,12)T相当于图中的 原点(0,0) ·X1)=(0,3,2,16,0)T相当于图1-2中的Q4点(0,3)； x1+2x2=8 4x1=16 4x2=12 Q2 X1
每步迭代的几何意义 • 初始基可行解 X(0)=(0,0,8,16,12) T相当于图中的 原点(0，0) • X(1)=(0,3,2,16,0) T相当于图1-2中的Q 4点(0，3)；
一x1+2x2=8 4x1=16 Q 4x2=12 Q2 ·X(2)=(2,3,0,8,0)T 相当于图中的Q3点(2,3) ·最优解X(3)=(4,2,0,0,4)T 相当于图中的Q2点(4,2)。 ·从初始基可行解Xo)开始迭代，依次得到X1), X2),X③)。这相当于图中的目标函数平移时， 从0点开始，首先碰到Q4,然后碰到Q3,最后达 到Q2
• X(2)=(2，3，0，8，0)T 相当于图中的 Q3点(2，3) • 最优解X(3)=(4，2，0，0，4)T 相当于图中的 Q2点(4，2)。 • 从初始基可行解X(0)开始迭代，依次得到X(1)， X(2)，X(3)。这相当于图中的目标函数平移时， 从0点开始，首先碰到Q4，然后碰到Q3，最后达 到Q2
3.2初始基可行解的确定 ·为了确定初始基可行解，要首先找出初 始可行基，其方法如下： (1)直接观察 (2)加松弛变量 (3)加非负的人工变量
3.2 初始基可行解的确定 • 为了确定初始基可行解，要首先找出初 始可行基，其方法如下： (1)直接观察 (2)加松弛变量 (3)加非负的人工变量
(1)直接观察 若线性规划问题 max 1-20） i=i ∑Px,=b 1-21) i=1 x)≥0 j=1,2,…,n
(1)直接观察 ( ) ( ) njx bxP xcz j n j jj n ij jj ,,2,10 211 max 201 1 =≥ " = − = − ∑ ∑ = = 若线性规划问题