Contributed by
We still have to consider a major issue, namely: optimization. In other words, the simplex method is supposed to optimize a linear function subject to linear constraints. We have shown how we can easily generate basic feasible solutions from a given basic feasible solution, but we have said nothing about optimization. The question is then: how do we incorporate an objective function into the above framework?
The Simplex Method conducts a sequence of pivot operations of the type we described above with a view to optimize a prescribed linear function of the decision variables. This is done by ensuring that in each step there is an improvement in the value of the objective function, namely if we maximize then the objective function will increase and if we minimize the objective function will decrease. Since there are finitely many basic feasible solutions, sooner or later this process must terminate. The theory of linear programming guarantees that if we cannot improve the objective function by a single pivot operation (moving from a basic feasible solution to an adjacent (neighbouring) basic feasible solution) then the current basic feasible solution is (globally) optimal. We can thus stop!
To show how this is done, let us first explain how the linear objective function we try to optimize is incorporated into the Gaussian procedure as a constraint.
So let c denote the vector of coefficients of the objective function under consideration, namely assume that our objective is to optimize the function
f(x):= c1x1 + ... + cnxn subject to a system of linear equations and the beloved non-negativity constraint.
Then this is equivalent to optimizing the scalar z subject to
z - c1x1 - ... - cnxn = 0 and the other "conventional" constraints, observing that in this framework z is also a decision variable.
To see how this idea works, let us consider the linear objective function associated with the coefficient vector =(4,3,0,0,0). If we add the corresponding contraint to the original system, the resulting model is as follows:
2x1 + x2 + x3 = 40 x1 + x2 + x4 = 30 x1 + x5 = 15 z - 4x1 - 3 x2 = 0 The associated tableau is then:
BV z x1 x2 x3 x4 x5 RHS x3 0 2 1 1 0 0 40 x4 0 1 1 0 1 0 30 x5 0 1 0 0 0 1 15 z 1 -4 -3 0 0 0 0 In summary, a new row is appended to the table (at the bottom) comprising the negative values of the coefficients of the objective function and zero in the last position resulting from the definition of the additional variable z. As we shall see, this last position will store the value of the objective function pertaining to the current basic feasible solution. In our case this value is equal to zero because all the cost coefficients of the original basic variables are equal to zero.
Needless to say, if the cost coeffcients of the original basic variables are non-zero, pivot operations will have to be performed to create an identity matrix out of the columns of the basic variables, which always include the z-column. For example, if the cost vector is c=(4,3,0,0,1) then would initially have
BV z x1 x2 x3 x4 x5 RHS x3 0 2 1 1 0 0 40 x4 0 1 1 0 1 0 30 x5 0 1 0 0 0 1 15 z 1 -4 -3 0 0 -1 0 This tableau is not in a canonical form, and to fix this detail we have to pivot on the -1 entry in the x 5 column. This yields the following tableau:
BV z x1 x2 x3 x4 x5 RHS x3 0 2 1 1 0 0 40 x4 0 1 1 0 1 0 30 x5 0 1 0 0 0 1 15 z 1 -3 -3 0 0 0 15 The corresponding basic solution is x=(0,0,40,30,15) with z=15.
As far as terminology goes, we shall refer to the elements of the z-row corresponding to the columns of x as reduced costs. This title is not very good, actually it is quite bad! but it has become a sort of standard in this business and we shall thus have to stick with it here.
You may wonder at this point why we keep schlepping the z-column in the tableau: since we have do not plan to pivot on elements of the z-row it is clear that the z-column will never change! So why keep it there?
This is a good suggestion and we shall adopt it immediately: from now own we shall not include the z-column in the simplex tableau. Thus, the last tableau will be displayed as follows:
BV x1 x2 x3 x4 x5 RHS x3 2 1 1 0 0 40 x4 1 1 0 1 0 30 x5 1 0 0 0 1 15 z -3 -3 0 0 0 15 So we conclude that the introduction of an objective function into the analysis can be easily dealt with by the Gaussain procedure: the same operation, ie pivoting, that is used to generate new basic feasible solutions to the problem is used to update the value of the objective function. Life is indeed beautiful!!!!! Try it!
For your convenience there is a choice between a framed and an unframed version of this page.
Contributed by
|
|