Course 4 : Parametric linear programming

Author: OptimizationCity Group

Sensitivity analysis

Sensitivity analysis is a procedure that is implemented after obtaining the optimal solution. Sensitivity analysis determines the sensitivity of the optimal solution against certain changes in the original model.

As mentioned before, one of the assumptions of linear programming is that the parameters of the model including a_ij, c_j and b_i are certain and definite values. But we know that the value of each parameter used in the model is estimated based on assumptions and predictions. These estimates are based on information that is usually incomplete and sometimes non-existent. Therefore, the parameters that are first entered in formulating the model are considered only as an empirical estimate, and sometimes it is possible that people estimate the value of the parameters lower or higher than their actual value. the experienced manager always look at the results with skepticism. It even often looks at these results as a starting point for a comprehensive analysis.

It is for the above reasons that sensitivity analysis becomes important. Changes that are usually studied in the linear programming model include the following:

1) Changes in the numbers on the right hand side

2) Changes in the coefficients of the objective function

3) Add a new constraint

Generally, the result of these changes is one of the following three situations:

1) The optimal answer remains unchanged, that is, the basic variables and their values ​​do not change at all.

2) Basic variables should not change, but their values ​​should change.

3) The basic solution should be completely changed.

The first case shows the insensitivity of the optimal solution to model changes and the third case shows more sensitivity.

Sensitivity analysis of right hand side

The goal in analyzing the sensitivity of the numbers on the right hand side to determine a change in the range of the right hand side so that the final table will remain feasible (that is, none of the numbers on the right hand side will be negative). This case is explained using the following example.

Example:

In the following problem, in order to produce two products whose production values ​​are represented by x₁ and x₂, four resources a, b, c, and d are used, which are on the right hand side of the constraint 1, 2, 3, and 4, respectively. The amount of available resources is equal to a=6, b=8, c=1, d=2, and the four constriants of the problem are written based on the limitations of these four resources. If the profit per unit of the first and second product is 3 and 2 respectively, the model is as follows.

The optimal solution of the problem, which is determined by point C, is:

As can be seen, for production at the optimal point, sources 1 and 2 are completely finished, but the level of sources 3 and 4 will be equal to 3 and 0.666, respectively. In this example, the following question is raised.

How much can the amount of resources (numbers on the right) decrease or increase?

After determining the optimal solution, it will be possible to study the possible changes in the optimal solution. In particular, we are interested in two types of analysis:

1) In order to improve the optimal value of the objective function, how much of a resource can be increased?

2) How much of a resource can be reduced without causing a change in the current optimal solution?

Since the source level is expressed by the numbers on the right side of the constraints, this type of analysis is called the sensitivity analysis of the right hand side.

In the above problem, only constraints 1 and 2, which represent the amount of resources a and b, are effective. Logically, if a constraint is important, it is considered as a scarce resource because all available resources are completely used (s₁=0, s₂=0). On the other hand, a constraint indicates a non-scarce resource (s₃≠0,s₄≠0). Therefore, we are interested in knowing how much scarce resources increase, in order to improve the value of the objective function, and similarly, we want to change how much non-scarce resources can be reduced without affecting the optimal solution.

Constraints 1 and 2 represent scarce resources. First, source a is checked. As the amount of source a increases, constraint 1 or line CD moves upward and parallel to itself, and triangle CDK gradually shrinks (sides CK and DK of triangle DKC are constraints 2 and 4 .). When it reaches the point K, constraints 2 and 4 become important and the optimal solution is located at the point K and the ABKEF area is the feasible region.

The further increase of the first source capacity causes the movement of the first constraint upwards and parallel to itself, while this increase after point K has no effect on the feasible region and the improvement of the objective function. Because this increase will cause the first constraint being redundant, thus the value of the first source will increase until the constraint of this resource crosses the point K.

The first constraint will pass through the point K if the number on the right hand side is greater than 6. To calculate this increase, it is enough to place the coordinates of point K in the first constraint, which is as follows:

In this way, the maximum increase of the first limit is from 6 to 7, which is equal to one unit.

The figure below shows the effect of increasing the second source. This case has been made regardless of the changes of the first source. Increasing the second source until the second constraint reaches point J will improve Z (objective function). The coordinates of point J are obtained from the intersection of the second constraints and the non-negativity constraint of the x₂ variable as follows.

By placing the coordinates of point J in the second constraint, the number on the right hand side of the second constraint and the new value of source b are obtained.

In this way, the maximum increase of the right hand side of the second constraint is possible from 8 to 12, which will be 4 units.

Now check the decrease in the numbers on the right hand side of the redundant constriant. Since s₃ and s₄ are not zero, two constraints 3 and 4 are redundant. Consider constraint 4. The figure below shows that the fourth constraint ( line ED) can be reduced as far as it passes point C, without affecting the optimal solution. Since the point C is x₁=3.333 and x₂=1.333, the number on the right hand side of the fourth constraint can be reduced to 1.333  at most without a change in the optimal point.

Now consider the third constraint. Again, the right hand side of the constraint can be reduced so that the equation corresponding to the third constraint (-x₁+x₂=1) passes through point C. Therefore, the right hand side of the third constraint is equal to –x₁+x₂=(-3.333)+(1.333)=-2. This change does not affect the current optimal point, C. The results of the above discussions are summarized in the table below.

Which resources should be increased?

Considering the budget limitation, which we normally face in the economic aspect, we would like to know which of the sources has more priority in capital allocation. Naturally, because we want to increase profits, we are willing to invest in a source that increases profits the most. This is stated in the table below.

If y_i is the value of each unit of resource i, then y_i is obtained from the following formula.

Sensitivity analysis of objective function coefficients

The change in the coefficients of the objective function affects the slope of the objective function line. If this change exceeds a certain amount, the optimal point will change. This means that changes in the coefficients of the objective function can change a set of important restrictions and consequently the status (scarce or redundant) of the resources. The objective function sensitivity analysis aims to answer this question:

How much coefficients of the objective function can be changed (increased or decreased) without changing the optimal point?

Example:

If the coefficients of the objective function in the previous example are denoted by C₁ and C₂, the objective function becomes:

As shown in the figure below, as C₁ increases or C₂ decreases, the objective function line rotates clockwise around point C. Conversely, a decrease in C₁ or an increase in C₂ causes Z to move counterclockwise. Therefore, point C remains optimal until the slope of the objective function (Z) changes between the slopes of constraints 1 and 2. When the slope Z coincides with the slope of the first constraint, the problem will have two optimal corner points C and D. Similarly, when the slope of Z coincides with the slope of the second constraint, the two points C and B will be optimized. Any small change outside the above defined range for C₁ will place the new optimal solution at point B or D. In order to calculate the range of changes, first the numerical value of the coefficient x₂ is kept constant and the coefficient x₁ is denoted by C₁.

The figure above shows that C₁ can be increased until to the second constraint (CB line), or decreased until to the first constraint (DC line). Therefore, the minimum or maximum value of C₁ can be obtained by making the slope of Z equal to the slope of the first and second constraint. The slope of Z is -C₁/2 and the slope of the first and second limits will be -1/2 and -2. Here, the minimum value of C₁ is found from the following relationship.

Similarly, the maximum value of C₁ to remain optimal at point C is:

The range of changes of C₁ to remain optimal at point C is as follows:

When C₁ is equal to 1, the optimal solution will be at point C or D. If the value of C₁ becomes less than 1, the optimal solution moves to D. Similarly, there can be an interpretation for C₁ equal to or greater than 4. If C₁ is greater than 4, the optimal solution moves to B.

Added a new limit

After solving the problem and finding the optimal solution, it is possible that due to economic or technical conditions, a new constraint will be added to the previous constraints, and may cause a decrease in the feasible region or do not have an impact on a feasible region. This effect can be shown in the following two cases:

Adding a redundant constraint

As stated earlier, a redundant constraint is a constraint whose presence or absence has no effect on the feasible region and consequently has no optimal solution. According to the previous example, as shown in the figure below, if a restriction of x₁+0.5x₂<=5 is added to the previous four constraints, it will not affect the feasible region and the optimal solution remains optimal.

Addition of an effective constraint

An effective constraint is a constraint that is effective in changing the feasible region and can change the optimal solution. The constraint of 4x₁+3x₂<=12 reduces the feasible area and changes Z* from 12.66 to 9.5.

Parametric linear programming

In the sensitivity analysis, the discrete effect of model parameters on the final solution was investigated. Whenever the impact of continuous changes of parameters in all possible domains is considered, parametric linear programming should be used.

Systematic change of parameters c_j

Consider the following objective function:

In parametric programming, the above objective function is replaced by the following function.

a_j are constant data that will represent the rate of changes in the coefficients of the objective function. The value of θ gradually becomes larger than zero. To illustrate the performance of the linear programming model as θ varies, consider the following example.

Example:

Solution:

Consider the value α₁=2 and α₂=-1. Therefore, the objective function is as follows.

We start from the final simplex table with θ=0, the objective function becomes as follows.

We add the changes of the objective function to the left side of the objective function, which is as follows.

Because x₁ and x₂ are basic variables (which appeared in equations 2 and 3), the coefficient of these two variables in the above objective function should be equal to zero, which is possible by adding equations 2 and 3 to the objective function, which is as follows:

According to the stopping condition of the prime simplex algorithm, as long as the coefficients of the non-basic variables remain non-negative, the basic feasible solution is optimized, so we have:

Therefore, if θ>9/7 becomes, x₄ is selected as the basic input variable and a new optimal solution is obtained using the prime simplex method. The new simplex table with x₄ entering the base and x₃ leaving the base (according to the ratio test) is as follows.

Therefore, if θ>5 becomes, x₅ is selected as the basic input variable and a new optimal solution is obtained using the initial simplex method. The new simplex table with x₅ entering the base and x₂ leaving the base (according to the ratio test) is as follows.

As it is clear in the above table, zero rows will be non-negative for θ>5 and the value of θ can be increased to infinity and there will be no change in the basic variables. The summary of the above procedure for all θ values is given in the table below.

Also, the value of the objective function of the optimal solution as a function of θ is as follows.

Systematic changes of the right parameters (b_i)

In this case, b_i is replaced by b_i+α_iθ, where α_i are fixed data. Therefore, the problem is as follows.

The purpose of this section is to determine the optimal job as a function of θ. The solution procedure described below is very similar to the process of what was said for the change of c_j, which is because the change in the coefficients of the objective function of the prime problem is equivalent to the change in the coefficients of the right hand side of the dual problem. To explain the issue further, we will solve some examples.

Example:

Use the parametric linear programming procedure to perform systematic changes in b_i and obtain the optimal solution of the following problem as a function of θ for 0≤ θ≤25 .

Solution:

Regardless of the value of θ, we get the optimal solution of the above model, which is given in the table below.

For 0≤θ≤1, the last table will have optimal conditions. But for θ>1, variable X₄ leaves the base and variable X₅ enters the base. In the next optimal table, for 1≤θ≤5  the optimal table will remain. But for θ>5, variable X₂ leaves the base and variable X₃ enters the base. In the next optimal table, for θ≥5, the optimal table will remain. As θ increases, there will be no change in the optimal conditions and feasibility of the table. The corresponding simplex table is given for each change of θ.

The results are summarized in the table below.

Example:

Suppose that Z(θ) represents the profit and the objective function can be changed to some extent by the proper transfer of manpower between the two activities. Specifically, suppose that the profit of the first activity can be increased from 8 (up to 18). But for every unit increase in the profit of the first unit, the profit of the second activity decreases by two units. Therefore, Z(θ) should be represented as follows.

that θ itself is a decision variable so that 0≤θ≤10.

a) Use parametric linear programming and determine the optimal solution as well as the optimal value of Z(θ) as a function of θ for 0≤θ≤10.

b) Determine the optimal value of θ. Then show how to find this optimal value using only the solution of two linear programming problems.

Solution:

a)

It can be concluded from the above figure:

The optimal solution (0,5) holds as long as

The optimal solution (3.33,3.33) holds as long as

The optimal solution (5,0) holds as long as

If we want to get the above results using the simplex table, we do as follows. At iteration 0, X₃ leaves the base and X₂ enters the base, which in this case has optimal conditions for θ=0 in the iteration 1. For 0≤θ≤2, the iteration 1 has optimality conditions. If θ>2 is, the coefficient of X₁ becomes negative in the row 0, and therefore, according to the prime simplex method, X₁ enters the base and the variable X₄ leaves the base. The row 0 coefficients for 2≤θ≤8  will be non-negative in iteration 2. For θ>8, the coefficient X₃ becomes negative in the row 0 and enters the basis according to the prime simplex method, and the variable X₂ leaves the base, which leads to iteration 3. In the iteration 3, the non-negative zero row will remain for θ≥8 and the basic solution will not change with the increase of this parameter. For different values ​​of θ, we calculate the value of the objective function using the simplex table.

The table below shows the optimal solution of the model for all values of 0≤θ≤10 .

The above table is displayed graphically as follows.

b) According to the graph above, we can understand that we will have the best model solution for θ=0. Considering that Z(θ) is a convex function in terms of θ, the maximum value occurs at the boundary of θ and therefore it is enough to solve the linear programming for the values of θ=0 and θ=10.

Example:

Obtain the optimal value of the following model for 0≤θ≤20 using parametric linear programming.

Solution:

The optimal value of the objective function for different values of  is as follows.

Example:

Use the parametric linear programming method and obtain the optimal solution of the following problem as a function of θ for 0≤θ≤30.

Solution:

For θ≤30, the optimal solution is 840+28θ and (0,0,30+θ,0,105-3θ,108).