The Simplex Method D 60 50 B 30 20 10 20 30 40 50 60 Cresnd between Basic Feasile ons and Comer Points or Leather Limited Besic Nonhasic Basic Correspands lo Vanables Variables Feasible Salution Corner Point X1,2 S1,S2 s1=52=0.x1=x=20 E XISI I S x3=3=0,x1=30,1=10 C X1,5 x2,31 x2=1=0,x1=40,2=-20 Not a bfs because s<0 X2,S1 ,2 1=$2=0,3=-20,x2=60 Not a bfs because s<0 x2,S2 x1+S1 x1==0,x3=40s2=20 B 51,8 x1,2 x=x2=0,s1=40,52=60 F Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 26/148
The Simplex Method Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 26 / 148
The Simplex Method Definition 2.4 Consider an LP in standard form with feasible region S and constraints Ax b and x>0.A nonzero vector d is a direction of unboundedness if for all x∈S and any c≥0，x+cd∈S. 7x灯+2x2≥28 4 2x+12x2≥24 1,2≥0 10 10 d= 1194 2=1320 8101214 d is a direction of unboundedness iff Ad =0,d >0. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 27/148
The Simplex Method Definition 2.4 Consider an LP in standard form with feasible region S and constraints Ax = b and x ≥ 0. A nonzero vector d is a direction of unboundedness if for all x ∈ S and any c ≥ 0, x + cd ∈ S. 7x1 + 2x2 ≥ 28 2x1 + 12x2 ≥ 24 x1, x2 ≥ 0 d = 1 1 9 14 d is a direction of unboundedness iff Ad = 0, d ≥ 0. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 27 / 148
The Simplex Method Theorem 2.2 Consider an LP in standard form,having bfs b1,b2,...,bk.Any point x in the LP's feasible region may be written in the form x=d+ibi, where d is or a direction of unboundedness,=1,and 0. Proof. First consider the case where the set s is bounded,so that there are no direction of unboundedness and d=0.Let x E S be any feasible point.If x is an extreme point,the result is trivial. If x is not an extreme point,by Theorem 2.1,it is not a bfs.The columns of A corresponding to the nonzero entries are linearly dependent and we can find a feasible direction p such that Ap=0,p>0 and pi=0 if x;=0.If e is small in magnitude,we have A(x+p)=b,x+p≥0，(x+ep)i=0ifx=0. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 28/148
The Simplex Method Theorem 2.2 Consider an LP in standard form, having bfs b1, b2, . . . , bk . Any point x in the LP’s feasible region may be written in the form x = d + Pk i=1 σibi , where d is 0 or a direction of unboundedness, Pk i=1 σi = 1, and σi ≥ 0. Proof. First consider the case where the set S is bounded, so that there are no direction of unboundedness and d = 0. Let x ∈ S be any feasible point. If x is an extreme point, the result is trivial. If x is not an extreme point, by Theorem 2.1, it is not a bfs. The columns of A corresponding to the nonzero entries are linearly dependent and we can find a feasible direction p such that Ap = 0, p ≥ 0 and pi = 0 if xi = 0. If is small in magnitude, we have A(x + p) = b, x + p ≥ 0, (x + p)i = 0 if xi = 0. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 28 / 148
The Simplex Method contd Hence,x+ep E S.Since S is bounded,as e increases in magnitude (either positive or negative),eventually points are encountered where some additional component x+ep becomes zero.Let y1 be the point obtained with e>0 and y2 be the point obtained with e<0.Then x is a convex combination of y1 and y2,both of which have at least one more zero component than x does. If y1 and y2 are both extreme points,then we are finished.Otherwise,the same reasoning is applied as necessary to one or both of y1 and y2 to express them as convex combinations of points with one more zero component.This is repeated until eventually a representation is obtained in terms of extreme points. The argument also shows that the set of extreme points is nonempty. Because the number of nonzero component is decreasing by one at each step,and is bounded below by zero,eventually the points generated by this scheme must be a bfs,namely,an extreme point. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 29/148
The Simplex Method contd. Hence, x + p ∈ S. Since S is bounded, as increases in magnitude (either positive or negative), eventually points are encountered where some additional component x + p becomes zero. Let y1 be the point obtained with > 0 and y2 be the point obtained with < 0. Then x is a convex combination of y1 and y2 , both of which have at least one more zero component than x does. If y1 and y2 are both extreme points, then we are finished. Otherwise, the same reasoning is applied as necessary to one or both of y1 and y2 to express them as convex combinations of points with one more zero component. This is repeated until eventually a representation is obtained in terms of extreme points. The argument also shows that the set of extreme points is nonempty. Because the number of nonzero component is decreasing by one at each step, and is bounded below by zero, eventually the points generated by this scheme must be a bfs, namely, an extreme point. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 29 / 148
The Simplex Method contd The unbounded case is proved similarly.Choose x E S.If x is not an extreme point,we can form x+ep as before.But it is possible that either p or-p is a direction of unboundedness if either p>0 or p<0.Suppose p is a direction of unboundedness.A move in the director-p will hit the boundary at some point y2,i.e.,x-yp=y2 with y>0.Hence,we have ×=yp+1·y2=d+1y2 so that x is the sum of a direction of unboundedness and a(trivial)convex combination of y2.As before,y2 has at least one more zero entry than x does. Finally,the same argument can be applied inductively to show that y2 can be expressed as a convex combination of extreme points plus a nonnegative linear combination of directions of unboundedness with nonnegative coefficients.Since such a combination of directions of unboundedness is also a direction of unboundedness,the proof is complete. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 30/148
The Simplex Method contd. The unbounded case is proved similarly. Choose x ∈ S. If x is not an extreme point, we can form x + p as before. But it is possible that either p or −p is a direction of unboundedness if either p ≥ 0 or p ≤ 0. Suppose p is a direction of unboundedness. A move in the director −p will hit the boundary at some point y2 , i.e., x − γp = y2 with γ > 0. Hence, we have x = γp + 1 · y2 = d + 1 · y2 so that x is the sum of a direction of unboundedness and a (trivial) convex combination of y2 . As before, y2 has at least one more zero entry than x does. Finally, the same argument can be applied inductively to show that y2 can be expressed as a convex combination of extreme points plus a nonnegative linear combination of directions of unboundedness with nonnegative coefficients. Since such a combination of directions of unboundedness is also a direction of unboundedness, the proof is complete. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 30 / 148