Changes in the Right Hand Side (RHS) of the Constraint (Sensitivity Analysis in Linear Programming)

Vector on Right Hand Side (RHS) associated with the constrains of a Linear Programming model may have different practical interpretations such as the availability of inputs for the manufacture of certain products, limiting of capacity, demand requirements, among other. As a result it is interesting to analyze the impact of the change of one or more coefficients of the vector on right hand side over the original results of the model without the need of optimizing again. In particular if we verify that:

vector-xb

It can be said that the current optimal base is preserved. This implies that the basic variables of the model will remain so under this new scenario and therefore you will find the new optimal solution of the problem through the resolution of the original system of equations (the original active constrains are preserved). Now, if any of the coefficients in the calculation of the basic variables vector takes a negative value, we have an infeasible basic solution, which forces us to make an update of the results of the model to find the new solution, optimal base and optimal value, but not needing  to passing through the reoptimization of it.

Changes in the Right Hand Side (RHS) of the Constraint

Consider the following Linear Programming model:

linear-programing-two-decis

When solving this Linear Programming model with Simplex Method you reach the next final tableau, where s1, s2, and s3 are the slack variables of the constrains 1, 2, and 3, respectively:

simplex method optimal tableau

The basic variables are x=100, s2=400, y=350, all of which meet the conditions of non negativity (i.e. is a basic feasible solution) and also the reduced cost of the non-basic variables (s1 y s3) are bigger or equal to zero, the necessary and sufficient condition to ensure that we have the optimal solution of the problem (optimal basic feasible  solution). In addition and related with the previous proposition we can confirm the results we got:

basic variables vector

Now lets consider that the right hand side of the constrain 1 changes from its original value 1.600 to 1.650. Does it change the current optimal basis? To do this we recalculate the vector of the basic variables:

modify xb vector

You can see that all the coefficients of the vector of basic variables (Xb) are bigger or equal to zero, i.e. the optimum base (same basic variables) is preserved but the optimal solution changes to x=125, s2=250, y=350. Additionally the optimal value now is V(P)=3.175. However, it is not necessary to continue the iterations of the Simplex Method (as we are facing an optimal basic feasible solution) and preventing us from doing a reoptimization.

The natural question is: What happens if, when calculating the vector of the basic variables, at least one of the variables gets a negative value? Now let´s modify simultaneously the right sides of constrains 1 and 2 to 2.000 and 1.500, respectively. The new basic variables vector is defined in the following way:

xb vector 2

Notice that now the basic variable s2=-1.000 takes a value that does not satisfy the condition of non negativity for the decision variables. To address this situation of infeasibility  it is necessary to update the final tableau of the Simplex Method with the value of the basic variables and the objective function value:

simplex method tableau 2

In order to find the optimal solution of this problem from the above table, the Dual Simplex Method can be applied. The basic variable given by the base is s2 (basic variable associated with row 2 where we find the negative ‘right hand side’). In order to decide the variable that goes to the base, we calculate the minimum quotient: Min{-3/2/-3}=1/2 ==> s1 goes to the base. We update the tableau of the Simplex Method with the following:

optimal solution simplex method

You can see that it was only necessary to do an additional iteration to get the optimal solution for the new scenario (x=400/3, s1=1.000/3, y=350) with an optimal value of V(P)=3.200. The following chart made with Geogebra,  allows us to see the new optimal solution and structure of the problem, where now the optimal solution finds the 2 and 3 active constrains (the original problem in its optimal solution considered 1 and 3 as active constraints):

optimal solution linear programming with geogebra

Rating: 3.7. From 3 votes.
Please wait...

, , , , , , , ,

Sin Comentarios aun. Se el primero en comentar!

Leave a Reply

Our Site is Proudly Hosted on