The Simplex Method Definition 2.1 Before the simplex algorithm can be used to solve an LP,the LP must be converted into an equivalent problem in which all constraints are equations and all variables are nonnegative.An LP in this form is said to be in standard form. By adding a slack variable s;to each constraint,we have max 4x+3x2 s.t. 为+2+51=40 2X灯+2+52=60 1,2,51,52≥0 Similarly,an excess variable (sometimes called a surplus variable)e;can be added to each constraint. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 21/148
The Simplex Method Definition 2.1 Before the simplex algorithm can be used to solve an LP, the LP must be converted into an equivalent problem in which all constraints are equations and all variables are nonnegative. An LP in this form is said to be in standard form. By adding a slack variable si to each ≤ constraint, we have max 4x1 + 3x2 s.t. x1 + x2 + s1 = 40 2x1 + x2 + s2 = 60 x1, x2,s1,s2 ≥ 0 Similarly, an excess variable (sometimes called a surplus variable) ei can be added to each ≥ constraint. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 21 / 148
The Simplex Method Suppose we have converted an LP with m constraints into standard form. Assuming that the standard form contains n variables(labeled for convenience x1,x2,...,xn),the standard form for such an LP is max f(x)=C1X1+c2x2+...+CnXn a11X1+a12X2+...+a1nXn b1 a21X1+a22X2+...+a2nXn b2 s.t. (1) am1X灯十 am2X2十..+amnXn= bm x≥0，i=1,2,,n or in matrix form max f(x)=cx s.t.Ax =b,x>0, where c is row vector representing the coefficients for decision variables in the objective function. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 22/148
The Simplex Method Suppose we have converted an LP with m constraints into standard form. Assuming that the standard form contains n variables (labeled for convenience x1, x2, . . . , xn), the standard form for such an LP is max f (x) = c1x1 + c2x2 + . . . + cnxn s.t. a11x1 + a12x2 + . . . + a1nxn = b1 a21x1 + a22x2 + . . . + a2nxn = b2 . . . . . . . . . am1x1 + am2x2 + . . . + amnxn = bm xi ≥ 0, i = 1, 2, . . . , n (1) or in matrix form max f (x) = cx s.t. Ax = b, x ≥ 0, where c is row vector representing the coefficients for decision variables in the objective function. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 22 / 148
The Simplex Method Definition 2.2 A basic solution to Ax =b is obtained by setting n-m variables equal to 0 and solving for the values of the remaining m variables.This assumes that setting the n-m variables equal to 0 yields unique values for the remaining m variables or,equivalently,the columns for the remaining m variables are linearly independent. To find a basic solution to Ax=b,we choose a set of n-m variables (the nonbasic variables,or NBV)and set each of these variables equal to 0.Then we solve for the values of the remaining n-(n-m)=m variables (the basic variables,or BV)that satisfy Ax b. Different choices of nonbasic variables will lead to different basic solutions! =(}12)B=(PP)→a,=(210) B2=(P2P3)→xB2=(07-4),B3→xB4=? Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 23/148
The Simplex Method Definition 2.2 A basic solution to Ax = b is obtained by setting n − m variables equal to 0 and solving for the values of the remaining m variables. This assumes that setting the n − m variables equal to 0 yields unique values for the remaining m variables or, equivalently, the columns for the remaining m variables are linearly independent. To find a basic solution to Ax = b, we choose a set of n − m variables (the nonbasic variables, or NBV) and set each of these variables equal to 0. Then we solve for the values of the remaining n − (n − m) = m variables (the basic variables, or BV) that satisfy Ax = b. Different choices of nonbasic variables will lead to different basic solutions! A = 1 1 1 3 1 −1 −2 1 , B1 = P1 P2 ⇒ xB1 = 2 1 0 T , B2 = P2 P3 ⇒ xB2 = 0 7 −4 T , B3 ⇒ xB3 =? Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 23 / 148
The Simplex Method Definition 2.3 Any basic solution to (1)in which all variables are nonnegative is a basic feasible solution (or bfs). Theorem 2.1 A point in the feasible region of an LP is an extreme point if and only if it is a basic feasible solution to the LP. Proof. Suppose first that x=(x1,x2,...,xm0,0,...,0)is a bfs to (1).Then ai=b,where a1,a2,...,am,the first m columns of A,are linearly independent.Suppose that x could be expressed as a convex combination of two other points;say,x=ay +(1-a)z,0<a<1,yz.Since all components of x,y,z are nonnegative and 0<a<1,it follows that the last n-m components of y and z are zero.Thus,ya=b and =b.Since the vectors a1,a2.am are linearly independent,it follows that x =y=z and hence x is an extreme point. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 24/148
The Simplex Method Definition 2.3 Any basic solution to (1) in which all variables are nonnegative is a basic feasible solution (or bfs). Theorem 2.1 A point in the feasible region of an LP is an extreme point if and only if it is a basic feasible solution to the LP. Proof. Suppose first that P x = (x1, x2, . . . , xm, 0, 0, . . . , 0) is a bfs to (1). Then m i=1 xiai = b, where a1, a2, . . . , am, the first m columns of A, are linearly independent. Suppose that x could be expressed as a convex combination of two other points; say, x = αy + (1 − α)z, 0 < α < 1, y 6= z. Since all components of x, y, z are nonnegative and 0 < α < 1, it follows that the last n − m components of y and z are zero. Thus, Pm i=1 P yiai = b and m i=1 ziai = b. Since the vectors a1, a2, . . . , am are linearly independent, it follows that x = y = z and hence x is an extreme point. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 24 / 148
The Simplex Method contd Conversely,assume that x is an extreme point.Let us assume that the nonzero components of x are the first k components.Then we have a=b withi=1,2....,k.To show that x is a bfs,it must be shown that the vectors a1,a2,...,ak are linearly independent. We do this by contradiction. Suppose a1,a2,...,ak are linearly dependent.Then there is a nontrivial linear combination that is zero=0.Define the n-vector y=(y1,y2,...,yk,0,0,...,0).Since xi>0,i=1,2,...,k,it is possible to select e such that x+y≥0andx-ey≥0.Then x=x+)+2x-. which expresses x as a convex combination of two distinct vectors.This cannot occur,since x is an extreme point.Thus a1,a2,...,ak are linearly independent and x is a bfs. )Q0 Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 25/148
The Simplex Method contd. Conversely, assume that x is an extreme point. Let us assume that the nonzero components of P x are the first k components. Then we have k i=1 xiai = b with xi > 0, i = 1, 2, . . . , k. To show that x is a bfs, it must be shown that the vectors a1, a2, . . . , ak are linearly independent. We do this by contradiction. Suppose a1, a2, . . . , ak are linearly dependent. Then there is a nontrivial linear combination that is zero Pk i=1 yiai = 0. Define the n-vector y = (y1, y2, . . . , yk , 0, 0, . . . , 0). Since xi > 0, i = 1, 2, . . . , k, it is possible to select such that x + y ≥ 0 and x − y ≥ 0. Then x = 1 2 (x + y) + 1 2 (x − y), which expresses x as a convex combination of two distinct vectors. This cannot occur, since x is an extreme point. Thus a1, a2, . . . , ak are linearly independent and x is a bfs. Xi Chen (chenxi0109@bfsu.edu.cn) Linear Programming 25 / 148