Dictionary Method Solution of equation (2.1) in Chvatal

Dictionary2_1

Dictionary Method Solution of equation (2.1) in Chvatal
Equation (2.1) of Chvatal
The problem in equation (2.1) of Chvatal is



maximize    5*x1 + 4*x2 + 3*x3

subject to  2*x1 + 3*x2 +   x3 <= 5

            4*x1 +   x2 + 2*x3 <= 11

            3*x1 + 4*x2 + 2*x3 <= 8

              x1 ,   x2 ,   x3 >= 0

Add Slack And Objective Variables



maximize    z  =      5*x1 + 4*x2 + 3*x3

subject to  s1 = 5  - 2*x1 - 3*x2 -   x3 

            s2 = 11 - 4*x1 -   x2 - 2*x3

            s3 = 8  - 3*x1 - 4*x2 - 2*x3 

            x1, x2, x3, s1, s2, s3 >= 0

Basic Feasible Solution
The basic feasible solution sets the variables on the right side of the equations to zero and then solves for the ones on the left side; i.e., the basic feasible solution corresponding to the case above is



     x1=0, x2=0, x3=0, s1=5, s2=11, s3=8, z=0

Choose First Pivot
We notice that z increases as we increase x1 and keep x2 = x3 = 0 (because the x1 coefficient in the equation for z is positive). If the resulting point is feasible,



     0 <= s1 = 5  - 2*x1; i.e.,      x1 <=  5/2

     0 <= s2 = 11 - 4*x1; i.e.,      x1 <= 11/4

     0 <= s3 = 8  - 3*x1; i.e.,      x1 <=  8/3

We notice that if we choose x1 so that s1 is zero, all the constraints will be satisfied. This corresponds exchanging the roles of x1 and s1 in the set of equations.

First Variables Exchange
We solve for the variable x1 in the row corresponding to s1; i.e,



     x1 = 2.5 - .5*s1 - 1.5*x2 - .5*x3

We replace the row corresponding to s1 with this equation and we use this equation to replace all other occurrences of x1 in the problem; i.e.,



maximize    z  =       5*(2.5 - .5*s1 - 1.5*x2 - .5*x3) +  4*x2 +  3*x3

subject to  x1 =          2.5 - .5*s1 - 1.5*x2 - .5*x3 

            s2 = 11  - 4*(2.5 - .5*s1 - 1.5*x2 - .5*x3) -    x2 -  2*x3

            s3 = 8   - 3*(2.5 - .5*s1 - 1.5*x2 - .5*x3) -  4*x2 -  2*x3

            x1, x2, x3, s1, s2, s3 >= 0

Regrouping terms we have the equivalent problem



maximize    z  = 12.5 - 2.5*s1 - 3.5*x2 + .5*x3

subject to  x1 = 2.5  -  .5*s1 - 1.5*x2 - .5*x3 

            s2 = 1    +   2*s1 +   5*x2 

            s3 = .5   + 1.5*s1 +  .5*x2 - .5*x3 

            x1, x2, x3, s1, s2, s3 >= 0

The basic feasible solution corresponding to the representation above is



     x1=2.5, x2=0, x3=0, s1=0, s2=1, s3=.5, z=12.5

We note that the vale of z has increased from the previous problem representation.

Choose Second Pivot
We notice that z increases as we increase x3 and keep s1 = x2 = 0 (because the x3 coefficient in the equation for z is positive). If the resulting point is feasible,



     0 <= x1 = 2.5 - .5*x3; i.e.,      x3 <= 5

     0 <= s2 = 1;           i.e.,       0 <= 1

     0 <= s3 = .5 -  .5*x3; i.e.,      x3 <= 1

We notice that if we choose x3 so that s3 is zero, all the constraints will be satisfied. This corresponds exchanging the roles of x3 and s3

Second Variables Exchange
We solve for the variable x3 in the row corresponding to s3; i.e,



maximize    z  = 12.5 - 2.5*s1 - 3.5*x2 + .5*(1 + 3*s1 + x2 - 2*s3)

subject to  x1 = 2.5  -  .5*s1 - 1.5*x2 - .5*(1 + 3*s1 + x2 - 2*s3) 

            s2 = 1    +   2*s1 +   5*x2 

            x3 =                              1 + 3*s1 + x2 - 2*s3 



            x1, x2, x3, s1, s2, s3 >= 0

Regrouping terms we have the equivalent problem



maximize    z  = 13 -   s1 - 3*x2 -   s3

subject to  x1 = 2  - 2*s1 - 2*x2 +   s3 

            s2 = 1  + 2*s1 + 5*x2 

            x3 = 1  + 3*s1 +   x2 - 2*s3 



            x1, x2, x3, s1, s2, s3 >= 0

The basic feasible solution corresponding to the representation above is



     x1=2, x2=0, x3=1, s1=0, s2=1, s3=0, z=13

We note that the vale of z has increased from the previous problem representation. This is the optimal solution (because there is no feasible direction in which the objective function increases).

Input File: Dictionary2_1.omh