Tag Archives: feasible solutions

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

Problem of Cutting, Assembling and Production of Chairs solved with Excel Solver

“The Old Chairs”, a rustic company manufactures, among many other products, three types of chairs A, B and C, which are sold at price of 11, 13 and 12 dollars each respectively. The chairs go through three processes, Cutting, Assembly and Painting, for which up to 17, 13 and 15 hours a week respectively are dedicated to these operations for these products. The type A chair takes 3 hours for cutting, 1 hour for assembling and 3 hours for painting. The type B chair takes 1 hour for cutting, 4 hours for assembling and 3 hours for painting. And finally the type C chair takes 5 hours for cutting, 2 hours for assembling and 2 hours for painting. According to the above information:

a) Solve the problem with continuous variables and point out the results for each variable.

Decision Variables: the level of weekly production was set for each of the varieties of chair as detailed below:

decision-variables-chairs

Objective Function: Maximize weekly earnings associated with the production and sale of the chairs.

objective-function-chairs

Constraints: In the process of cutting, assembling and painting the availability of weekly hours must be respected. Additionally the constraints of non-negativity must be met.

constraints-chairs

The computational implementation of the above problem with Excel Solver can achieve the following results:

optimal-solution-chairs

Where the optimal solution is A=1,914286, B=1,828571 y C=1,885714 with optimal value V(P)=67,45714.

b) Modify the conditions of the variables and select them whole (integer) and observe the difference between the response from point a) and this new one found.

When defining the decision variables as integers we are facing an Integer Programming model (being the first stage a problem in Linear Programming). The results are:

integer-optimal-solution-ch

The optimal solution is A=1B=2 y C=2 with optimal value V(PE)=61.

c) Reach to a conclusion about what happened between continuous variables and integer variables.

It is important to note that the domain of feasible solutions of the problem (part b) is a subset of the domain of feasible solutions of the linear problem (part a). Therefore it is natural that, without obtaining a solution with integer values for the decision variables in the first problem, the optimal value necessarily will decrease in whole variant of this maximization (V(PE)<V(P)). It can also be noted that the integer solution, not necessarily is achieved by approximating the fractional results of a solution of a linear problem to the nearest lower or higher integer. Consequently, to address the resolution of a model which takes integer values for the decision variables efficiently, it requires a specific algorithmic alternative such as the Branch and Bound Method.

Below is a link to download the Excel file used for solving the problem of cutting, assembling and production of chairs. Two sheets corresponding to part a) and b) the proposed problem are included in the file: Production of Chairs.