17.6 Sensitivity Analysis

As presented in Section 16.5 of the previous chapter, one of the hypotheses of a linear programming model is to assume that all the model parameters (objective function coefficients c_j, constraint variable coefficients a_ij, and independent terms b_i) are deterministic, that is, constant and known with certainty. However, many times, the estimation of these parameters is based on future forecasts, such that changes may happen until the final solution is implemented in the real world. As examples of changes, we can mention changes in the amount of resources available, launching of a new product, variation in a product’s price, increase or decrease in production costs, among others.

Therefore, the sensitivity analysis is essential in the study of linear programming problems, since it has as its main objective to investigate the effects that certain changes in the model parameters would have on the optimal solution.

The sensitivity analysis discusses the variation that the objective function coefficients and constants on the right-hand side of each constraint can assume (lower and upper limits), without changing the initial model’s optimal solution or without changing the feasibility region. This analysis can be done graphically, by using algebraic calculations, or directly through the Solver in Excel or other software packages, such as, Lindo, considering one alteration at a time.

Therefore, the sensitivity analysis being studied considers two cases:

1. (a) The model’s sensitivity analysis based on the alterations in one of the objective function coefficients, without changing the model’s original basic solution (the basic solution remains optimal). Since one of the objective function coefficients is altered, the value of objective function z also changes.
2. (b) The model’s sensitivity analysis based on the alterations in the independent terms of the constraints, without changing the optimal solution or the feasibility region.

Thus, we eliminate the need to recalculate a model’s new optimal solution after changes in its parameters.

Section 17.6.1 graphically analyzes the possible changes in the model’s objective function coefficients. The same analysis, based on the independent terms of the constraints, will be studied in Section 17.6.2. Both cases can also be analyzed by Solver in Excel (see Section 17.6.4), always considering one alteration at a time.

The sensitivity analysis studied in this section will be described based on Example 17.12.

17.6.1 Alteration in one of the Objective Function Coefficients (Graphical Solution)

Fig. 17.73 presented the graphical solution for Example 17.12, in which extreme point C represents the model’s optimal solution (x₁ = 20,x₂ = 35 with z = 1,000). Now, let’s carry out a sensitivity analysis based on changes in the values of the objective function coefficients, performing one alteration at a time. The main objective is to determine the value range that each objective function coefficient can take on, maintaining the other coefficients constant, without impacting the model’s basic solution (the basic solution remains optimal). This analysis is based on the comparison between the angular coefficients of the active constraints (treated as equality constraints) and the angular coefficient of the objective function. The active constraints are the ones that define the model’s optimal solution. If the model’s inactive constraints are eliminated, the optimal solution will not be affected.

• Slope and angular coefficient of line

Let α be the angle formed by the line and the X-axis, counterclockwise, called line slope. The angular coefficient m determines the direction of the line, that is, the trigonometric tangent of slope α:

$m=\mathit{tg}\left(\alpha \right)$

  (17.28)

In a graphical way, Fig. 17.74 specifies four cases for m from different values of α.

From Fig. 17.74, we can see that every nonvertical line has a real number m that specifies its direction. Case d is a special case since there is no tangent for slope α = 90° and, consequently, there is no angular coefficient m for a vertical line.

This relationship can be better visualized in Fig. 17.75 that shows the tangent chart for different values of α. For instance, for case (a) in the previous figure (0° < α < 90°), we can see that tg 0° = 0 and tg 45° = 1. As α gets closer to 90°, the value of m tends to infinity.

The angular coefficient can be calculated from two points in the line. Given two distinct points in the Cartesian plane, A(x₁, y₁) and B(x₂, y₂), there is a single line r that goes through these two points. The angular coefficient of r can be calculated as:

$m=\mathit{tg}\left(\alpha \right)=\frac{\text{opposite}\mathrm{leg}}{\text{adjacent}\mathrm{leg}}=\frac{\mathrm{\Delta }y}{\mathrm{\Delta }x}=\frac{y_2-y_1}{x_2-x_1}$

  (17.29)

• Angular coefficient of the objective function from its reduced equation

Consider the general equation of an objective function with two decision variables (x₁ and x₂):

$z=c_1{x}_1+c_2{x}_2$

  (17.30)

To determine the reduced equation of Expression (17.30), we have to isolate variable x₂ from the general equation:

$x_2=-\frac{c_1}{c_2}{x}_1+\frac{z}{c_2}$

  (17.31)

where:

• m = $-\frac{c_1}{c_2}$ is the angular coefficient of the objective function.

• Value range for c₁ or c₂ that do not change the model’s original basic solution

By calculating the angular coefficient of each active constraint in the model (treated as an equality constraint) and the angular coefficient of the objective function, be it from the reduced equation of the line or from two points in the line [Expression (17.28)], we can determine the value range for c₁ or c₂ that does not change the model’s original basic solution. Let’s illustrate this condition through an example.

Going back to Example 17.12, from the graphical solution presented in Fig. 17.73, we can see that only the first two constraints of Expression (17.27) are considered active. Hence, to carry out the sensitivity analysis from variations in one of the objective function coefficients, we must calculate the angular coefficient of the first and second constraints, treated as equality equations. First, we can see that the slope of the first equation 5x₁ + 4x₂ = 240 and of the second equation 4x₁ + 8x₂ = 360 are within the interval 90^° < α < 180^°. Therefore, the angular coefficient of both lines will be negative. From Fig. 17.75, we conclude that the value of m₁ (angular coefficient of the first equation) will be smaller when compared to m₂ (angular coefficient of the second equation). The value of the angular coefficient of each equation will be determined from the reduced equation of the line.

The first equation 5x₁ + 4x₂ = 240 can be written in the reduced form:

$x_2=-5/4x_1+60$

  (17.32)

So, the angular coefficient of the first equation is m₁ = − 5/4.

Analogously, the reduced form of the second equation can be expressed as:

$x_2=-1/2x_1+45$

  (17.33)

We can conclude that the angular coefficient of the second equation is m₂ = − 1/2.

According to Fig. 17.73, we can see that while the angular coefficient of the objective function (− c₁/c₂) is between − 5/4 and − 1/2, that is, between the angular coefficients of the model’s first and second equations (active equations), the original problem’s basic solution does not change, remaining optimal. Mathematically, the value of the original basic solution remains constant, while:

$-\frac{5}{4}\le -\frac{c_1}{c_2}\le -\frac{1}{2}\text{or}0.5\le \frac{c_1}{c_2}\le 1.25$

  (17.34)

Example 17.13

From the problem of company Romes Shoes (Example 17.2), carry out a sensitivity analysis considering the following changes:

1. (a) Let’s assume that there was an increase in the unit profits of flip-flops and clogs to $20.00 and $25.00, respectively, based on reductions in production costs, mainly in terms of human resources. Verify if the basic solution remains optimal. If yes, what is the new value of z?
2. (b) Which possible variations in c₂ would maintain the original model’s basic solution? Note: The other parameters remain constant.
3. (c) Do the same for c₁.
4. (d) Imagine that there was an increase in the price of leather, the main raw material for producing clogs, diminishing its unit profit to $18.00. In order for the original model’s basic solution to remain unaltered, which interval must the unit profit of flip-flops satisfy?

Solution

1. (a) Considering the new objective function equation (z = 20x₁ + 25x₂), we can determine the ratio $\frac{c_1}{c_2}=\frac{20}{25}=0.8$ directly.
   Therefore, the condition $0.5\le \frac{c_1}{c_2}\le 1.25$ continues being satisfied, such that the original model’s basic solution (x₁ = 20 and x₂ = 35) remains optimal. Therefore, the new value of z is z = 20 × 20 + 25 × 35 = 1,275.
2. (b) Substituting c₁⁰ = 15 (original value of c₁) in the condition $0.5\le \frac{c_1}{c_2}\le 1.25$, we have:

$\left\{\begin{array}{l}0.5\times c_2\le 15\Rightarrow c_2\le 30\\ 1.25\times c_2\ge 15\Rightarrow c_2\ge 12\end{array}\right.\Rightarrow 12\le c_2\le 30\text{or}{c}_2^0-8\le c_2\le c_2^0+10$

Thus, while c₂ continues satisfying the interval specified here, the original model’s optimal basic solution (x₁ = 20 and x₂ = 35) will remain unaltered.

1. (c) Substituting c₂⁰ = 20 (original value of c₂) in the condition $0.5\le \frac{c_1}{c_2}\le 1.25$, we have:

$0.5\times 20\le c_1\le 1.25\times 20\Rightarrow 10\le c_1\le 25\text{or}{c}_1^0-5\le c_1\le c_1^0+10$

Therefore, while the conditions specified for c₁ continue being satisfied, the original model’s basic solution will remain unaltered.

1. (d) By substituting c₂ = 18 in the condition $0.5\le \frac{c_1}{c_2}\le 1.25$, we have:

$0.5\times 18\le c_1\le 1.25\times 18\Rightarrow 9\le c_1\le 22.5$

Therefore, while c₁ continues satisfying the interval specified , for a value of c₂ = 18, the basic solution remains optimal.

Example 17.14

Consider the following maximization problem:

$\begin{array}{l}maxz=15x_1+20x_2\\ \text{subject to}:\\ 4x_1+8x_2\le 360\left(1\right)\\ x_1\le 60\left(2\right)\\ x_j\ge 0,j=1,2\end{array}$

  (17.35)

Determine:

1. (a) The graphical solution for the original model represented in Expression (17.35).
2. (b) The possible variations in c₁ that would maintain the original model’s basic solution (the basic solution remains optimal), maintaining the other parameters constant. Do the same for c₂.

Solution

Fig. 17.76 shows the model’s graphical solution of Expression (17.35).

The current model’s optimal solution, represented by extreme point C, is x₁ = 60 and x₂ = 15 with z = 1,200. From Fig. 17.76, we can see that we have a special case, since the model’s second constraint of Expression (17.35) corresponds to a vertical line (slope of 90° in relation to axis x₁). When one of the active constraints is vertical, there will be no upper or lower limit for the angular coefficient of the objective function, since there is no tangent for α = 90°.

Now, let’s carry out a sensitivity analysis from variations in c₁ or c₂. In order to do that, we need to calculate the angular coefficient of the first constraint (treated in the equality form), be it from its reduced equation or from two points in the line. Let’s use the first case.

The reduced form of the first equation in Expression (17.35) is:

$x_2=-1/2x_1+45$

So, its angular coefficient is − 1/2.

According to Fig. 17.76, we can see that, while the angular coefficient of the objective function is between the angular coefficients of the vertical equation and equation 4x₁ + 8x₂ = 360, that is, between −∞ (there is no lower limit for the 90° tangent) and − 1/2, the basic solution remains optimal. Mathematically, the original basic solution remains constant, while:

$-\infty \le -\frac{c_1}{c_2}\le -\frac{1}{2}\text{or}0.5\le \frac{c_1}{c_2}\le \infty$

By setting c₂ = 20 (original value) in the condition $0.5\le \frac{c_1}{c_2}\le \infty$, we have:

$0.5\times 20\le c_1\le \infty \Rightarrow 10\le c_1\le \infty$

Thus, while c₁ is within the interval specified, the original model’s basic solution (x₁ = 60 and x₂ = 15) will remain unaltered.

By setting c₁ = 15 (original value) in the condition $0.5\le \frac{c_1}{c_2}\le \infty$, we have:

$\left\{\begin{array}{l}0.5\times c_2\le 15\Rightarrow c_2\le 30\\ c_2\ge \frac{15}{\infty }\cong 0\Rightarrow c_2\ge 0\end{array}\right.\Rightarrow 0\le c_2\le 30$

Therefore, while c₂ continues satisfying the condition specified, the basic solution will remain optimal.

17.6.2 Alteration in One of the Constants on the Right-Hand Side of the Constraint and Concept of Shadow Price (Graphical Solution)

The sensitivity analysis from alterations in the value of one of the constants on the right-hand side of the constraint (availability of resources) is based on the concept of shadow price, which can be defined as the increase (or decrease) of the objective function in case 1 unit is added to (or removed from) the current amount of resources available of the i-th constraint (b_i⁰).

Calculating the shadow price (P_i) in case 1 unit of resources is added to b_i⁰ is:

$P_i=\frac{\mathrm{\Delta }{z}_{+1}}{\mathrm{\Delta }{b}_{i,+1}}=\frac{z_{+1}-z_0}{+1}$

  (17.36)

where:

• Δz₊₁ = increase in the value of objective function z in case 1 unit of resources is added to b_i⁰.
• z₀ = initial value of the objective function.
• z₊₁ = new value of the objective function after 1 unit is added to b_i⁰.
• Δb_i,+1 = increase in b_i⁰. The definition of shadow price considers an increase of 1 unit in the amount of resources i.

Calculating the shadow price (P_i) in case 1 unit of resources is removed from b_i⁰ is:

$P_i=\frac{\mathrm{\Delta }{z}_{-1}}{\mathrm{\Delta }{b}_{i,-1}}=\frac{z_{-1}-z_0}{-1}=\frac{z_0-z_{-1}}{1}$

  (17.37)

where:

• Δz₋₁ = decrease in the value of objective function z in case 1 unit of resources is removed from b_i⁰.
• z₀ = initial value of the objective function.
• z₋₁ = new value of the objective function after 1 unit is removed from b_i⁰.
• Δb_i,−1 = decrease in b_i⁰. The definition of shadow price considers a decrease of 1 unit in the amount of resources i.

Shadow price can be interpreted as the fair price to pay for using 1 unit of resource i or the opportunity cost of resources due to the loss of 1 unit of resource i.

After defining the shadow price for resource i (P_i), the main goal of this sensitivity analysis is to determine the value range in which b_i can vary (maximum increase allowed of p units in b_i⁰ or decrease allowed of q units in b_i⁰), that is, b_i⁰ − q ≤ b_i ≤ b_i⁰ + p, in which the shadow price remains constant. The interval must be determined in order to satisfy the following relationship:

$\frac{\mathrm{\Delta }{z}_{+p}}{\mathrm{\Delta }{b}_{i,+p}}=\frac{\mathrm{\Delta }{z}_{-q}}{\mathrm{\Delta }{b}_{i,-q}}=\frac{z_{+p}-z_0}{p}=\frac{z_0-z_{-q}}{q}=P_i$

  (17.38)

where:

• Δz_+p = increase in the value of objective function z in case p units of resources are added to b_i⁰.
• Δz_−q = decrease in the value of objective function z in case p units of resources are removed from b_i⁰.
• z₀ = initial value of the objective function.
• z_+p = new value of the objective function after p units are added to b_i⁰.
• z_−q = new value of the objective function after q units are removed from b_i⁰.
• Δb_i,+p = increase of p units in b_i⁰.
• Δb_i,−q = decrease of q units in b_i⁰.

Thus, for the interval specified in which the shadow price remains constant, if p units were added to b_i⁰, the value of the objective function would increase Δz_+p = P_i × p. This equation can also be interpreted as the fair price to pay for using p units of resource i, being proportional to the shadow price. Analogously, if q units were removed from b_i⁰, the value of the objective function would decrease Δz_−q = P_i × q. This equation can also be interpreted as the opportunity cost due to the loss of q units of resource i.

The calculation of the shadow price is only valid for active constraints (which define the model’s optimal solution). Otherwise, variations in b_i within the feasibility region will not impact the model’s optimal solution, concluding that the shadow price for nonactive constraints is zero.

Solving the problem in an analytical or algebraic way, this means that the current model’s optimal solution (that contains a value different from b_i, however, within the interval specified above in which the shadow price remains constant) will have the same basic variables as the original model’s optimal solution (the original basic solution remains optimal); however, the values of the decision variables and of the objective function are altered due to changes in b_i.

Solving the problem in a graphical way, as the amount of resources b_i varies, the i-th constraint moves parallel to the i-th original constraint. Nevertheless, the current model’s optimal solution continues being determined by the intersection of the same active lines in the original model (intersection between the i-th constraint altered and another active constraint from the initial model). While the intersection between these lines happens inside the feasibility region, that is, between the extreme points that limit the feasible solution space analyzed, the increase in the value of the objective function due to the use of p units of resource i or the decrease due to the loss of q units of the same resource will be proportional to the shadow price (the shadow price will remain constant for the interval b_i⁰ − q ≤ b_i ≤ b_i⁰ + p, in which b_i⁰ represents its original value). For any value of b_i out of this range, it will be necessary to recalculate the model’s new optimal solution, since the feasible region is altered.

Example 17.15

Similar to Example 17.13, the sensitivity analysis based on changes in the resources will also be applied to the case of Romes Shoes (Example 17.12). From the model’s graphical solution, determine:

1. (a) The shadow price for each sector (cutting, assembly and finishing).
2. (b) The maximum permissible decrease and increase for each b_i that would maintain its shadow price constant (when it is positive), or that would not change the initial model’s optimal solution (when the shadow price is null).

Solution

As presented in Expression (17.27), Example 17.12 of company Romes Shoes can be mathematically represented as:

$\begin{array}{l}maxz=15x_1+20x_2\\ \text{subject to}:\\ 5x_1+4x_2\le 240\left(1\right)\text{cutting}\\ 4x_1+8x_2\le 360\left(2\right)\text{assembly}\\ 7,5x_2\le 300\left(3\right)\text{finishing}\\ x_j\ge 0,j=1,2\end{array}$

  (17.39)

The original model’s optimal solution is x₁ = 20 and x₂ = 35 with z = 1,000.

• Changes in the availability of resources in the cutting sector

1. (a) Shadow price

If the time available for the cutting sector increases in one man-hour, the first constraint in Expression (17.39) becomes 5x₁ + 4x₂ ≤ 241. The new optimal solution is then determined by the intersection between active lines 5x₁ + 4x₂ = 241 and 4x₁ + 8x₂ = 360, being represented by point H (x₁ = 20.333 and x₂ = 34.833 with z = 1,001.667), as shown in Fig. 17.77.

The shadow price for the cutting sector (P₁), considering an increase of 1 man-hour in the availability of resources, can be calculated as:

$P_1=\frac{1,001.667-1,000}{241-240}=1.667$

Thus, for each man-hour added to the cutting sector, the objective function increases 1.667. Or the fair price paid for each man-hour used in the cutting sector is 1.667.

If there were a reduction of 1 man-hour in the cutting sector, we would obtain the same result for the shadow price. By changing the value of the constant of the first constraint to b₁ = 239, the model’s new optimal solution becomes: x₁ = 19.667 and x₂ = 35.167 with z = 998.333. The calculation of the shadow price, considering a decrease of 1 man-hour for the cutting sector, is:

$P_1=\frac{1,000-998.33}{240-239}=1.667$

Hence, for each man-hour removed from the cutting sector, the objective function decreases 1.667. Or the opportunity cost for each man-hour lost in the cutting sector is 1.667.

1. (b) Maximum permissible decrease and increase for b₁

The main objective is to determine the value range in which b₁ can vary (b₁⁰ − q ≤ b₁ ≤ b₁⁰ + p), and in which the shadow price remains constant. While this happens, the price to be paid for the use of p man-hours in the cutting sector will be P₁ × p = 1.667 × p. Analogously, the opportunity cost due to the loss of q man-hours in the same sector will be P₁ × q = 1.667 × q.

From Fig. 17.77, we can see that the original model’s optimal solution is determined by the intersection of lines 5x₁ + 4x₂ = 240 and 4x₁ + 8x₂ = 360. Also note that the new constraint 5x₁ + 4x₂ ≤ 241 is parallel to the original constraint 5x₁ + 4x₂ ≤ 240. As the value of b₁ increases, the line moves in the direction of extreme point G, always parallel to the original constraint. Similarly, as the value of b₁ decreases, the line moves in the direction of extreme point D. While the intersection of equations 5x₁ + 4x₂ = b₁ and 4x₁ + 8x₂ = 360 occurs within the feasibility region (segment DG), the shadow price will remain constant. Extreme points D and G represent the lower and upper limits for b₁. Any point out of this segment will result in a new basic solution. Therefore, the lower and upper limits for b₁ can be determined by substituting the coordinates of point D (x₁ = 10 and x₂ = 40) and G (x₁ = 90 and x₂ = 0), respectively, in 5x₁ + 4x₂:

Lower limit for b₁ (point D): 5 × 10 + 4 × 40 = 210

Upper limit for b₁ (point G): 5 × 90 + 4 × 0 = 450

We can conclude that, while the value of b₁ is within the interval 210 ≤ b₁ ≤ 450, its shadow price remains constant. The interval can also be specified based on the maximum permissible decrease and increase for b₁⁰ = 240 (its original value), being expressed as:

$b_1^0-30\le b_1\le b_1^0+210$

For example, for a value of p = 210, the price to be paid for the use of these 210 man-hours in the cutting sector will be P₁ × 210 = 1.667 × 210 = 350 (if 210 man-hours were added to the total time available for the cutting sector, the objective function would increase $350.00). Conversely, for a value of q = 30, the opportunity cost due to the loss of these 30 man-hours in the total time available in the cutting sector will be P₁ × 30 = 1.667 × 30 = 50 (if 30 man-hours were removed from the total time available for the cutting sector, the objective function would decrease $50.00). For any value of b₁ out of this interval, it is necessary to recalculate the new optimal solution, because the feasible region is altered.

These results can be better visualized in Fig. 17.78. Polygon AEDB represents the feasibility region for a value of b₁ = 210 (lower limit for b₁). Whereas polygon AEDG represents the feasibility region for a value of b₁ = 450 (upper limit for b₁).

• Changes in the availability of resources in the assembly sector

1. (a) Shadow price

By adding 1 man-hour to the assembly sector, the second constraint of (1) becomes 4x₁ + 8x₂ ≤ 361. The new optimal solution is then determined by the intersection between active lines 5x₁ + 4x₂ = 240 and 4x₁ + 8x₂ = 361, being represented by point I (x₁ = 19.833 and x₂ = 35.208 with z = 1,001.667), as illustrated in Fig. 17.79.

Since the new value of the objective function is also 1,001.667 (similar to the cutting sector), we obtain the same shadow price (P₂ = 1.667). Therefore, for each man-hour added in the assembly sector, the objective function also increases 1.667.

By reducing the time available for the assembly sector in 1 man-hour (b₂ = 359), the model’s new optimal solution becomes: x₁ = 20.167 and x₂ = 34.792 with z = 998.333. Thus, the shadow price in this case is also P₂ = 1.667. Therefore, for each man-hour removed from the assembly sector, the objective function also decreases 1.667.

1. (b) Maximum permissible decrease and increase for b₂

Fig. 17.79 illustrates the new constraint 4x₁ + 8x₂ ≤ 361 for the assembly sector, parallel to the original constraint 4x₁ + 8x₂ ≤ 360. As the value of b₂ increases, the line moves in the direction of extreme point J, always parallel to the original constraint. Similarly, as the value of b₂ decreases, the line moves in the direction of extreme point B. While the intersection of the equations 5x₁ + 4x₂ = 240 and 4x₁ + 8x₂ = b₂ happens within the feasibility region (segment BJ), the shadow price will remain constant. Extreme points B and J represent the lower and upper limits for b₂. Any point out of this segment will result in a new basic solution. Hence, the lower and upper limits for b₂ can be determined by substituting the coordinates of point B (x₁ = 48 and x₂ = 0) and J (x₁ = 16 and x₂ = 40), respectively, in 4x₁ + 8x₂:

Lower limit for b₂ (point B): 4 × 48 + 8 × 0 = 192

Upper limit for b₂ (point J): 4 × 16 + 8 × 40 = 384

We can conclude that, while the value of b₂ is within the interval 192 ≤ b₂ ≤ 384, its shadow price remains constant. The interval can also be specified based on the maximum permissible decrease and increase for b₂⁰ = 360 (its initial value), being expressed as:

$b_2^0-168\le b_2\le b_2^0+24$

For example, for a value of p = 24, the price to be paid by the use of these 24 man-hours in the assembly sector will be P₂ × 24 = 1.667 × 24 = 40 (if 24 man-hours were added to the total time available for the assembly sector, the objective function would increase $40.00). On the other hand, for a value of q = 168, the opportunity cost due to the loss of these 168 man-hours in the total time available for the assembly sector will be P₂ × 168 = 1.667 × 168 = 280 (if 168 man-hours are removed from the total time available for the assembly sector, the objective function would decrease $280.00). For any value of b₂ out of this interval, it is necessary to recalculate the new optimal solution.

These results can be better visualized in Fig. 17.80. Polygon ABJE represents the feasibility region for a value of b₂ = 384 (upper limit for b₂). Whereas triangle ABK represents the feasibility region for a value of b₂ = 192 (upper limit for b₂).

• Changes in the availability of resources in the finishing sector

1. (a) Shadow price

As presented in Fig. 17.77, the original model’s optimal solution is determined by the intersection of the two first equations 5x₁ + 4x₂ = 240 and 4x₁ + 8x₂ = 360. Since the finishing constraint (7.5x₂ ≤ 300) is not active, changes in the value of b₃ within the feasibility region will not impact the original model’s optimal solution. So, its shadow price is zero.

1. (a) Maximum permissible decrease and increase for b₃

Since the constraint 7.5x₂ ≤ 300 is not active, the main goal here is to determine the value range in which b₃ can vary without changing the initial model’s optimal solution (x₁ = 20 and x₂ = 35 with z = 1,000). To determine the lower limit for b₃, we just need to substitute the value of coordinate x₂ of optimal point C (x₂ = 35) in 7.5x₂ = b₃ (intersection of lines 4x₁ + 8x₂ = 360 and 7.5x₂ = b₃). So, the lower limit for b₃ is 7.5 × 35 = 262.5. In contrast, any value for b₃ above its initial value will continue not impacting the initial model’s optimal solution, such that the value range for b₃ can be written as:

$262.5\le b_3$

The interval can also be specified based on the maximum permissible decrease and increase for b₃⁰ = 300 (its initial value), being expressed as:

$b_3^0-37.5\le b_3$

17.6.4 Sensitivity Analysis With Solver in Excel

The sensitivity analysis through Solver in Excel will be presented in this section for the problem of company Romes Shoes (Example 17.12). Fig. 17.81 (see file Example17.12_Romes.xls) shows the modeling of the problem in Excel, already with the model’s optimal solution.

Having solved the model through the Solver in Excel, the window Solver Results appears. Select the option Sensitivity Report, as shown in Fig. 17.82.

The results of the sensitivity analysis for the problem of Rome Shoes, considering the changes in one of the objective function coefficients (Section 17.6.1), changes in one of the constants on the right-hand side and concept of shadow price (Section 17.6.2), and the concept of reduced cost (Section 17.6.3), from the Solver in Excel, are consolidated in Fig. 17.83.

Lines 4 and 5 show the results of the sensitivity analysis based on changes in one of the objective function coefficients (Section 17.6.1), based on the final value of variable cells (B14 and C14), which represent the model’s decision variables. According to column D, these values are x₁ = 20 and x₂ = 35. Column E shows the reduced cost of each variable. Since both are basic, their values are null. If one of the variables were nonbasic, its reduced cost would appear with a negative sign in the sensitivity report in Excel, that is, with the opposite sign to the one presented in this book, as already mentioned previously. Analogously, for a minimization problem, the costs reduced of the nonbasic variables are presented with a positive sign in the sensitivity report in Excel. The initial values of the coefficients of each variable in the objective function are presented in column F. On the other hand, columns G and H show the maximum permissible increase and decrease for each coefficient, from its initial value, the other parameters remaining constant, without changing the original model’s optimal basic solution.

Lines 10, 11, and 12 show the results of the sensitivity analysis based on changes in the amount of resources of each one of the model constraints (Section 17.6.2). By substituting the optimal values of each variable on the left-hand side of each constraint, we obtain the optimal number of resources necessary for each sector, as shown in column D. These values can also be updated in Fig. 17.81, if the option Keep Solver Solution is chosen in the window Solver Results. The shadow price (price paid for the use or opportunity cost due to the loss of 1 unit of each resource) is presented in column E. The initial amount available of each resource is presented in column F. Alternatively, the maximum permissible increase and decrease for each resource that maintains its shadow price constant or within the feasibility region, from its initial value, are specified in columns G and H, respectively.

17.6.4.1 Special Case: Multiple Optimal Solutions

As presented in Section 17.2.3.1, in a graphical solution, we can identify a special case of linear programming with multiple optimal solutions when the objective function is parallel to an active constraint.

Alternatively, through the Simplex method (see Section 17.4.6.1), we can identify a case with multiple optimal solutions when, in the optimal tabular form, the coefficient of one of the nonbasic variables is null in row 0 of the objective function.

According to Ragsdale (2009), it is also possible to identify a case with multiple optimal solutions through the Sensitivity Report in Solver in Excel. This case happens when the increase or decrease permissible regarding the coefficient of one or more variables in the objective function is zero and we do not have a degenerate solution (see following Section).

For the maximization problem (max z = 8x₁ + 4x₂) presented in Section 17.2.3.1 (Example 17.3), the graphical solution was obtained from Fig. 17.84.

The representation of this problem in Excel can be seen in Fig. 17.85.

By solving this example in the Solver in Excel, it was possible to find a feasible solution, obtaining the same message presented in Fig. 17.82, that Solver found a solution and all the optimized constraints and conditions were met. However, the Solver provided only one of the optimal solutions: x₁ = 4 and x₂ = 0 with z = 32 (vertex B), not displaying any messages about the special case of multiple optimal solutions.

By solving the problem through Solver in Excel and selecting the option Sensitivity Report in Solver Results, we obtain Fig. 17.86.

As shown in rows 9 and 10 of Fig. 17.86, the decrease allowed for the coefficient of x₁ in the objective function and the increase allowed for the coefficient of x₂ in the objective function are null. Since there is no degeneration (see following Section 17.2.4.2), we have a case with multiple optimal solutions.

Ragsdale (2009) recommends two strategies that can be applied to determine a new optimal solution through Solver in Excel: 1) to insert a new constraint into the model that does not change the optimal value of the objective function and maintains the model’s feasibility; and 2) when the increase allowed for one of the decision variables is null, we must maximize the value of this variable (the objective function must be altered for a maximization problem that has as a objective cell the respective variable and not function z any more). When the decrease allowed for one of the variables is null, we must minimize the value of this variable (the objective function must be altered for a minimization problem that has as an objective cell such variable).

For example, if we only use the first strategy, inserting the new constraint x₁ − x₂ ≥ 1 into the model, a new optimal solution is determined: x₁ = 3 and x₂ = 2 with z = 32.

Through Fig. 17.86, note that the maximum increase allowed for the coefficient of variable x₂ in the objective function is zero. Analogously, the decrease allowed for the coefficient of variable x₁ in the objective function is also zero. Therefore, regarding the second strategy proposed by Ragsdale, we would have two alternatives: to maximize the new objective cell $C$11 that represents variable x₂, or to minimize the new objective cell $B$11 that represents variable x₁.

Thus, if we got the same initial solution (x₁ = 4 and x₂ = 0 with z = 32) by only using the first strategy, in addition to inserting the constraint x₁ − x₂ ≥ 1, we should use one of the alternatives listed for the second strategy. For instance, if we inserted the constraint x₁ − x₂ ≥ 1 and changed the objective function for a maximization problem that has as a target the cell $C$11, we would also obtain the new optimal solution: x₁ = 3 and x₂ = 2 with z = 32, as shown in Fig. 17.87.

On the other hand, instead of constraint x₁ − x₂ ≥ 1, if we inserted constraint 2x₁ + x₂ ≥ 8 into the original model and changed the objective function to a minimization problem that has as a target the cell $B$11 that represents the variable x₁, we would obtain a new optimal solution: x₁ = 2 and x₂ = 4 with z = 32, as shown in Fig. 17.88.

17.6.4.2 Special Case: Degenerate Optimal Solution

As discussed in Section 17.2.3.4, in a graphical solution, we can identify a degenerate solution when one of the vertices of the feasible region is obtained by the intersection of more than two distinct lines.

Whereas through the Simplex method (see Section 17.4.5.4), we can identify a case with a degenerate solution when, in one of the solutions of the Simplex method, the coefficient of one of the basic variables is null. If there is degeneration in the optimal solution, we have a case known as degenerate optimal solution.

As presented in Section 17.4.5.4, the degeneration problem is that, in some cases, the algorithm Simplex can go into a loop, which generates the same basic solutions, since it cannot leave that solution space. In this case, the optimal solution will never be achieved.

We can detect a case with degeneration through the Sensitivity Report in the Solver in Excel when the increase permissible or decrease permissible regarding the amount of resources of one of the constraints is zero.

The same Example 17.6 presented in Section 17.2.3.4 for the case with a degenerate optimal solution will be solved in this section from Solver in Excel. The graphical solution for this example (min z = x₁ + 5x₂) is in Fig. 17.89.

Analogous to the case with multiple optimal solutions, by solving Example 17.6 through the Solver in Excel, it was also possible to find a feasible solution, obtaining the same message as the one in Fig. 17.82: that Solver found a solution and all the optimized constraints and conditions were met. However, Solver does not display any message about the special case of a degenerate solution.

By solving the problem above through Solver in Excel and selecting the option Sensitivity Report in Solver Results, we obtain Fig. 17.90.

As shown in rows 15 and 17 of Fig. 17.90, the permissible increase regarding the amount of resources available in the first and third constraints is null. Whereas row 16 shows that the permissible decrease regarding the amount of resources in the second constraint is also zero. Therefore, we have a case with a degenerate optimal solution. In this case, the analysis of the Sensitivity Report may be compromised. Ragsdale (2009) and Lachtermacher (2009) highlight the precautions that must be taken when we identify a case with a degenerate optimal solution:

1. 1. When the increase or decrease allowed for the coefficient of one of the variables in the objective function is also zero, the statement that multiple optimal solutions have occurred is no longer reliable.
2. 2. The reduced costs of the variables may not be unique. Moreover, in order for the optimal solution to change, the coefficients of the variables in the objective function must at least improve their respective reduced costs.
3. 3. The permissible changes in the coefficients of the variables in the objective function are maintained; however, values outside this interval may continue not changing the current optimal solution.
4. 4. The shadow prices may not be unique, jointly with the permissible increase or decrease regarding the availability of resources of each constraint.

17.7 Exercises

Section 17.2 (ex.1). Determine the feasible solution space that satisfies each one of the constraints separately, considering x₁, x₂ ≥ 0:

1. (a) 3x₁ + 2x₂ ≤ 12
2. (b) 2x₁ + 3x₂ ≥ 24
3. (c) 3x₁ − 2x₂ ≤ 6
4. (d) x₁ − x₂ ≥ 4
5. (e) − x₁ + 4x₂ ≤ 16
6. (f) − x₁ + 2x₂ ≥ 10

Section 17.2.1 (ex.1). For each maximization function z, determine the direction in which the objective function increases:

1. (a) max z = 5x₁ + 3x₂
2. (b) max z = 4x₁ − 2x₂
3. (c) max z = − 2x₁ + 6x₂
4. (d) max z = − x₁ − 2x₂

Section 17.2.1 (ex.2). Determine the graphical solution (feasible solution space and the optimal solution) of the following LP maximization problems:

1. (a) $\begin{array}{l}maxz=3x_1+4x_2\\ \text{subject to}:\\ 2x_1+5x_2\le 18\\ 4x_1+4x_2\le 12\\ 5x_1+10x_2\le 20\\ x_1,x_2\ge 0\end{array}$
2. (b) $\begin{array}{l}maxz=2x_1+3x_2\\ \text{subject to}:\\ 2x_1+2x_2\le 10\\ 3x_1+4x_2\le 24\\ x_2\le 4\\ x_1,x_2\ge 0\end{array}$
3. (c) $\begin{array}{l}maxz=4x_1+2x_2\\ \text{subject to}:\\ x_1+x_2\le 16\\ 3x_1-2x_2\le 36\\ x_1\le 10\\ x_2\le 6\\ x_1,x_2\ge 0\end{array}$

Section 17.2.1 (ex.3). Graphically solve Venix Toys’ production mix problem (Example 16.3 presented in Section 16.5.1 of the previous chapter, solved through the Solver in Excel in Section 17.5.2.1 of this chapter).

Section 17.2.1 (ex.4). Are the solutions in the feasible region of Venix Toys’ problem?

1. (a) x₁ = 30,   x₂ = 25
2. (b) x₁ = 30,   x₂ = 30
3. (c) x₁ = 44,   x₂ = 24
4. (d) x₁ = 45,   x₂ = 28
5. (e) x₁ = 75,   x₂ = 15
6. (f) x₁ = 90,   x₂ = 14
7. (g) x₁ = 100,   x₂ = 14
8. (h) x₁ = 120,   x₂ = 10
9. (i) x₁ = 130,   x₂ = 5

Section 17.2.2 (ex.1). For each minimization function z, determine the direction in which the objective function decreases:

1. (a) min z = 5x₁ + 8x₂
2. (b) min z = 2x₁ − 3x₂
3. (c) min z = − 4x₁ + 5x₂
4. (d) max z = − 7x₁ − 5x₂

Section 17.2.2 (ex.2). Determine the graphical solution for the following LP minimization problems:

1. (a) $\begin{array}{l}minz=2x_1+x_2\\ \text{subject to}:\\ x_1-x_2\ge 10\\ 2x_1+3x_2\ge 30\\ x_1,x_2\ge 0\end{array}$
2. (b) $\begin{array}{l}minz=2x_1-x_2\\ \text{subject to}:\\ x_1-2x_2\ge 2\\ -x_1+3x_2\ge 6\\ x_1,x_2\ge 0\end{array}$
3. (c) $\begin{array}{l}minz=6x_1+4x_2\\ \text{subject to}:\\ 2x_1+2x_2\ge 40\\ x_1+3x_2\ge 30\\ 4x_1+2x_2\ge 60\\ x_1,x_2\ge 0\end{array}$

Section 17.2.3 (ex.1). Graphically identify in which of the special cases each LP problem finds itself: a) multiple optimal solutions; b) unlimited objective function z; c) there is no optimal solution; d) degenerate optimal solution.

1. (a) $\begin{array}{l}maxz=2x_1+x_2\\ \text{subject to}:\\ x_1+4x_2\le 12\\ 4x_1+2x_2\le 20\\ 3x_2\le 6\\ x_1,x_2\ge 0\end{array}$
2. (b) $\begin{array}{l}minz=2x_1+x_2\\ \text{subject to}:\\ 4x_1+5x_2\ge 20\\ x_1+x_2\le 3\\ x_1,x_2\ge 0\end{array}$
3. (c) $\begin{array}{l}maxz=2x_1+3x_2\\ \text{subject to}:\\ 4x_1+2x_2\ge 20\\ x_1-x_2\le 10\\ x_1,x_2\ge 0\end{array}$
4. (d) $\begin{array}{l}maxz=6x_1+4x_2\\ \text{subject to}:\\ 4x_1-4x_2\le 20\\ 3x_1+2x_2\le 30\\ x_2\le 12\\ x_1,x_2\ge 0\end{array}$
5. (e) $\begin{array}{l}minz=2x_1+3x_2\\ \text{subject to}:\\ -x_1+x_2\le 10\\ 4x_1+2x_2\ge 20\\ 4x_2\ge 40\\ x_1,x_2\ge 0\end{array}$
6. (f) $\begin{array}{l}minz=2x_1+3x_2\\ \text{subject to}:\\ -x_1+x_2\le 10\\ 4x_1+2x_2\ge 20\\ x_1+x_2\le 4\\ x_1,x_2\ge 0\end{array}$

Section 17.2.3 (ex.2). Graphically determine the alternative optimal solutions for the following LP problems:

1. (a) $\begin{array}{l}maxz=6x_1+4x_2\\ \text{subject to}:\\ 3x_1+2x_2\le 90\\ 2x_1+x_2\le 50\\ x_1,x_2\ge 0\end{array}$
2. (b) $\begin{array}{l}minz=2x_1+3x_2\\ \text{subject to}:\\ 4x_1-x_2\ge 11\\ 4x_1+6x_2\ge 32\\ x_1,x_2\ge 0\end{array}$

Section 17.3 (ex.1) Consider the following LP minimization problem:

$\begin{array}{l}minz=3x_1+2x_2\\ \mathrm{subject}\mathrm{t}\mathrm{o}:\\ 8x_1+5x_2\ge 140\\ 4x_1+3x_2\ge 80\\ x_1,x_2\ge 0\end{array}$

By solving the problem in an analytical way, determine:

1. (a) The number of possible basic solutions for this system.
2. (b) The feasible basic solutions for the problem, and graphically represent them.
3. (c) The optimal solution.

Section 17.3 (ex.2) Do the same for the following LP maximization problem:

$\begin{array}{l}maxz=4x_1+3x_2+5x_3\\ \text{subject to}:\\ 3x_1-x_2+2x_3\ge 10\\ 4x_1+2x_2+5x_3\le 50\\ x_1,x_2,x_3\ge 0\end{array}$

Section 17.4.2 (ex.1) Consider the following LP maximization problem:

$\begin{array}{l}maxz=4x_1+5x_2+3x_3\\ \text{subject to}:\\ 2x_1+3x_2-x_3\le 48\\ x_1+2x_2+5x_3\le 60\\ 3x_1+x_2+2x_3\le 30\\ x_1,x_2,x_3\ge 0\end{array}$

Solve the problem through the analytical form of the Simplex method.

Section 17.4.3 (ex.1) Solve the production mix problem of Venix Toys through the Simplex method.

Section 17.4.3 (ex.2) Use the Simplex method to solve the following LP maximization problems:

1. (a) $\begin{array}{l}maxz=3x_1+2x_2\\ \text{subject to}:\\ 3x_1-x_2\le 6\\ x_1+3x_2\le 12\\ x_1,x_2\ge 0\end{array}$
2. (b) $\begin{array}{l}maxz=2x_1+4x_2+3x_3\\ \text{subject to}:\\ x_1+x_2+2x_3\le 6\\ 2x_1+2x_2+3x_3\le 16\\ x_1+4x_2+x_3\le 18\\ x_1,x_2,x_3\ge 0\end{array}$
3. (c) $\begin{array}{l}maxz=3x_1+x_2+2x_3\\ \text{subject to}:\\ 2x_1+2x_2+x_3\le 20\\ 3x_1+x_2+4x_3\le 60\\ x_1+x_2+2x_3\le 30\\ x_1,x_2,x_3\ge 0\end{array}$

Section 17.4.3 (ex.3) What is the biggest difficulty in solving the farmer’s problem (Example 16.7 in Section 16.5.4 of the previous chapter, solved through the Solver in Excel in Section 17.5.2.5 of this chapter) through the Simplex method?

Section 17.4.4 (ex.1) Use the Simplex method to solve the following LP minimization problems:

1. (a) $\begin{array}{l}minz=2x_1-x_2\\ \mathrm{subject}\mathrm{t}\mathrm{o}:\\ -2x_1+6x_2\le 24\\ 8x_1+2x_2\le 40\\ x_1,x_2\ge 0\end{array}$
2. (b) $\begin{array}{l}minz=5x_1-6x_2\\ \text{subject to}:\\ -4x_1+2x_2\le 10\\ x_1+3x_2\le 22\\ x_1,x_2\ge 0\end{array}$
3. (c) $\begin{array}{l}minz=2x_1-x_2-x_3\\ \text{subject to}:\\ 3x_1+5x_2+4x_3\le 120\\ -x_1+2x_2+4x_3\le 90\\ 2x_1-x_2+2x_3\le 60\\ x_1,x_2,x_3\ge 0\end{array}$
4. (d) $\begin{array}{l}minz=-x_1+3x_2-x_3\\ \text{subject to}:\\ 4x_1-2x_2+2x_3\le 160\\ 2x_1+5x_2+10x_3\le 200\\ x_1-x_2+x_3\le 50\\ x_1,x_2,x_3\ge 0\end{array}$

Section 17.4.5.1 (ex.1) Solve the following LP maximization problem through the Simplex method:

$\begin{array}{l}maxz=4x_1-x_2\\ \text{subject to}:\\ 3x_1-3x_2\le 175\\ 8x_1-2x_2\le 460\\ x_1\le 60\\ x_1,x_2\ge 0\end{array}$

1. (a) Demonstrate that we have a special case with multiple optimal solutions here.
2. (b) Determine at least two of the alternative optimal solutions.
3. (c) Solve the problem graphically and compare the results obtained.

Section 17.4.5.1 (ex.2) Do the same for the LP minimization problem:

$\begin{array}{l}minz=3x_1+6x_2\\ \text{subject to}:\\ 2x_1+4x_2\ge 620\\ 7x_1+3x_2\ge 630\\ x_1,x_2\ge 0\end{array}$

Section 17.4.5.1 (ex.3) Determine all the optimal FBS of the following maximization problem:

$\begin{array}{l}maxz=4x_1+4x_2\\ \text{subject to}:\\ x_1+x_2\le 1\\ x_1,x_2\ge 0\end{array}$

Section 17.4.5.2 (ex.1) Demonstrate that the LP maximization problem has an unlimited objective function z.

$\begin{array}{l}maxz=5x_1+2x_2\\ \text{subject to}:\\ 2x_1-3x_2\le 66\\ -9x_1-3x_2\le 99\\ x_1,x_2\ge 0\end{array}$

Section 17.4.5.2 (ex.2) Demonstrate that the LP maximization problem has an unlimited objective function z.

$\begin{array}{l}minz=-3x_1-2x_2\\ \text{subject to}:\\ -2x_1+x_2\le 12\\ -3x_1-2x_2\le 24\\ x_1,x_2\ge 0\end{array}$

Determine a feasible basic solution with z = − 90.

Section 17.4.5.3 (ex.1) Demonstrate that the LP maximization problem has an unfeasible solution.

$\begin{array}{l}maxz=18x_1+12x_2\\ \mathrm{subject}\mathrm{t}\mathrm{o}:\\ 4x_1+16x_2\le 1850\\ -8x_1-5x_2\ge 4800\\ x_1,x_2\ge 0\end{array}$

Section 17.4.5.3 (ex.2) Do the same for the following minimization problem:

$\begin{array}{l}minz=7x_1+5x_2\\ \text{subject to}:\\ 6x_1+4x_2\ge 24\\ x_1+x_2\le 3\\ x_1,x_2\ge 0\end{array}$

Section 17.4.5.4 (ex.1) Demonstrate that the LP maximization problem has a degenerate optimal solution.

$\begin{array}{l}maxz=2x_1+3x_2\\ \text{subject to}:\\ x_1-x_2\ge 10\\ 2x_1+3x_2\le 90\\ x_1\le 24\\ x_1,x_2\ge 0\end{array}$

Section 17.4.5.4 (ex.2) Do the same for the minimization problem.

$\begin{array}{l}minz=6x_1+8x_2\\ \text{subject to}:\\ 2x_1+4x_2\ge 60\\ 5x_1-4x_2\ge 80\\ 3x_1+8x_2\ge 100\\ x_1,x_2\ge 0\end{array}$

Section 17.4.5 (ex.1) Through the Simplex method, identify in which of the special cases each LP problem finds itself: a) multiple optimal solutions; b) unlimited objective function z; c) there is no optimal solution; d) degenerate optimal solution.

1. (a) $\begin{array}{l}maxz=x_1+3x_2\\ \text{subject to}:\\ 2x_1+6x_2\le 48\\ 3x_1+5x_2\le 60\\ x_1+8x_2\le 6\\ x_1,x_2\ge 0\end{array}$
2. (b) $\begin{array}{l}minz=2x_1-6x_2\\ \text{subject to}:\\ 3x_1+2x_2\ge 24\\ 2x_1+6x_2\ge 30\\ x_1,x_2\ge 0\end{array}$
3. (c) $\begin{array}{l}maxz=2x_1+x_2\\ \text{subject to}:\\ 8x_1+4x_2\le 600\\ 4x_1+2x_2\le 300\\ x_1,x_2\ge 0\end{array}$

Section 17.4.5 (ex.2) From each one of the tabular forms presented, identify if we have a special case of the Simplex method or not. If yes, determine the special case in which the problem analyzed finds itself: a) multiple optimal solutions; b) unlimited objective function z; c) there is no optimal solution; d) degenerate optimal solution. In each tabular form, we specify if the original problem is a maximization or a minimization.

1. (a) Maximization problem

1. (b) Minimization problem

1. (c) Minimization problem

1. (d) Maximization problem

1. (e) Minimization problem

Section 17.5.2 (ex.1). Consider Exercise 1 proposed in Section 16.5.1 of the previous chapter, regarding the production mix problem of company KMX:

1. (a) Represent the problem in an Excel spreadsheet.
2. (b) Determine the optimal solution through the Solver in Excel.

Section 17.5.2 (ex.2). Do the same for Exercise 2 proposed in Section 16.5.1 of the previous chapter, regarding the production mix problem of company Refresh.

Section 17.5.2 (ex.3). Do the same for Exercise 3 of Section 16.5.1 of the previous chapter, regarding the company Golmobile.

Section 17.5.2 (ex.4). Do the same for Exercise 1 of Section 16.5.2 of the previous chapter, regarding the petroleum mix problem.

Section 17.5.2 (ex.5). Do the same for Exercise 1 of Section 16.5.4 of the previous chapter, regarding the capital budget problem of company GWX.

Section 17.5.2 (ex.6). Do the same for Exercise 1 of Section 16.5.5 of the previous chapter, regarding the portfolio optimization problem.

Section 17.5.2 (ex.7). Do the same for Exercise 3 of Section 16.5.5 of the previous chapter, regarding the portfolio optimization problem of CTA Investment Bank.

Section 17.5.2 (ex.8). Do the same for Exercise 1 of Section 16.5.7 of the previous chapter, regarding the aggregate planning problem of company Pharmabelz.

Section 17.6.1 (ex.1). Company Solutions manufactures two types of thermometers: digital and mercury ones. Each digital thermometer guarantees a net unit profit of $7.00, while a mercury thermometer generates a net unit profit of $5.00. Manufacturing these 2 types of thermometers requires 3 types of operations. To manufacture one digital thermometer, 4, 5, and 2 minutes in each one of the operations are necessary. Whereas a mercury thermometer requires 2, 3, and 3 minutes for each operation. The availability for each operation is 300, 360, and 180 minutes.

1. (a) Determine the model’s graphical solution.
2. (b) Determine the maximum permissible increase in the net unit profit of a digital thermometer that would maintain the original basic solution unaltered. Assume that the other model parameters remain constant.
3. (c) Determine the maximum permissible decrease in the unit profit of a mercury thermometer that would maintain the original basic solution unaltered, assuming that the other parameters remain constant.
4. (d) Assuming that there was a reduction in the unit profit of digital thermometers to $3.00, check and see if the original model’s optimal solution remains optimal.
5. (e) Assuming that there was an increase in the unit profit of mercury thermometers to $10.00, verify if the original model’s optimal solution remains optimal.

Section 17.6.1 (ex.2). Consider the following maximization problem:

$\begin{array}{l}maxz=8x_1+6x_2\\ \text{subject to}:\\ 2x_1+5x_2\le 30\\ 3x_1+6x_2\le 54\\ 2x_1+8x_2\le 64\\ x_1,x_2\ge 0\end{array}$

1. (a) Determine the model’s graphical solution.
2. (b) What is the value range in which c₁ can vary that would maintain the original basic solution unaltered, assuming that c₂ remains constant?
3. (c) Determine the value range in which c₂ can vary that would maintain the original basic solution unaltered, assuming that c₁ remains constant.

Section 17.6.1 (ex.3). Consider the following minimization problem:

$\begin{array}{l}minz=8x_1+6x_2\\ \text{subject to}:\\ 2x_1+5x_2\ge 60\\ 3x_1+6x_2\ge 102\\ 2x_1+8x_2\ge 128\\ x_1,x_2\ge 0\end{array}$

1. (a) Determine the model’s graphical solution.
2. (b) In the original model’s optimal solution, we verified that variable x₂ is basic. Thus, if the non-negativity constraint is not established over the possible variations of c₂, which problem will occur?
3. (c) What is the value range in which c₁ can vary that would maintain the original basic solution unaltered, assuming that c₂ remains constant?
4. (d) Determine the value range in which c₂ can vary that would maintain the original basic solution unaltered, assuming that c₁ remains constant.

Section 17.6.1 (ex.4). Consider Venix Toys’s production mix problem (Example 16.3 of the previous chapter):

1. (a) Determine the optimality condition (c₁/c₂) that would maintain the original model’s basic solution unaltered.
2. (b) Let’s assume that there was a simultaneous reduction in the unit profits of toy cars and tricycles to $10.00 and $50.00, respectively, due to the competition in the market. Verify if the original model’s basic solution remains optimal and determine the new value of z.
3. (c) What are the possible changes in the unit profit of toy cars that would maintain the original model’s basic solution unaltered? Assume that the other model parameters remain constant.
4. (d) What is the value range in which the unit profit of tricycles can vary without impacting the original model’s basic solution? Assume that the other parameters remain constant.
5. (e) If there is a reduction in the unit profit of toy cars to $9.00, will the original model’s basic solution remain optimal? In this case, what is the new value of the objective function?
6. (f) If there is an increase in the unit profit of tricycles to $80.00, will the original model’s basic solution be affected (the other parameters remain constant)? What is the new value of the objective function after these changes?
7. (g) Imagine that there has been a significant reduction in the production costs of tricycles, increasing their unit profit to $100.00. In order for the original model’s basic solution to remain unaltered, which interval must the unit profit of toy cars satisfy?

Section 17.6.2 (ex.1). Once again, consider the production mix problem of Venix Toys:

1. (a) Determine the shadow price for the machining, painting, and assembly departments.
2. (b) Determine the value range in which each b_i can vary that maintains the shadow price constant.
3. (c) If the availability in the machining sector increases to 40 hours, what will be the increase in the value of objective function?
4. (d) If the availability in the painting sector is reduced to 18 hours, what will be the decrease in the value of the objective function? Also determine the new values of x₁ and x₂.

Section 17.6.2 (ex.2). Consider Exercise 1 proposed in Section 17.6.1 of company Solutions:

1. (a) If the availability of each operation increases in 1 minute, which one of them must have priority?
2. (b) Determine the maximum permissible increase and decrease (p and q minutes, respectively) in b₁, b₂, and b₃ that maintains the shadow price constant.
3. (c) What is the fair price to pay for using p minutes of b₂?
4. (d) What is the opportunity cost due to the loss of q minutes of b₃?

Section 17.6.3 (ex.1). Consider the following maximization problem:

$\begin{array}{l}maxz=3x_1+2x_2\\ \text{subject to}:\\ x_1+x_2\le 6\\ 5x_1+2x_2\le 20\\ x_1,x_2\ge 0\end{array}$

Table 17.1 shows the initial tabular form of the model, Table 17.2 shows the tabular form in the first iteration, and Table 17.3 the optimal tabular form of the same problem.

We would like you to:

1. (a) Interpret the reduced costs of Tables 17.2 and 17.3.
2. (b) Determine the values of z₁¹, z₂¹, z₁^∗, and z₂^∗.

Section 17.6.3 (ex.2). Consider the following minimization problem:

$\begin{array}{l}minz=4x_1-2x_2\\ \text{subject to}:\\ 2x_1+x_2\le 10\\ x_1-x_2\le 8\\ x_1,x_2\ge 0\end{array}$

Tables 17.4 and 17.5 show the initial tabular form and the optimal tabular form of the model, respectively.

We would like you to:

1. (a) Interpret the reduced costs of Table 17.5.
2. (b) Determine the values of z₁^∗ and z₂^∗.

Section 17.6.4 (ex.1). Consider Exercise 1 of Section 17.6.1 of company Solutions:

1. (a) Solve it through the Solver in Excel.
2. (b) Through the Solver Sensitivity Report, determine the maximum permissible increase and decrease in c₁ that maintains the original basic solution unaltered.
3. (c) Through the Solver Sensitivity Report, determine the maximum permissible increase and decrease in c₂ that maintains the original basic solution unaltered.
4. (d) Through the Solver Sensitivity Report, determine the shadow price for each operation.
5. (e) Through the Solver Sensitivity Report, determine the maximum permissible increase and decrease in b₁, b₂, and b₃ that maintains the shadow price constant.

Section 17.6.4 (ex.2). Do the same for the production mix problem of company Venix Toys.

Section 17.6.4 (ex.3). Through the Solver Sensitivity Report, identify if the problems belong to the special case “multiple optimal solutions” or “degenerate optimal solution.”

1. (a) $\begin{array}{l}maxz=4x_1+2x_2\\ \text{subject to}:\\ 6x_1+2x_2\le 240\\ 2x_1+3x_2\le 200\\ 3x_1+x_2\le 120\\ x_1,x_2\ge 0\end{array}$
2. (b) $\begin{array}{l}maxz=3x_1+8x_2\\ \text{subject to}:\\ 2x_1+2x_2\le 300\\ 5x_1+4x_2\le 800\\ 9x_1+24x_2\le 1,080\\ x_1,x_2\ge 0\end{array}$
3. (c) $\begin{array}{l}maxz=2x_1+6x_2\\ \text{subject to}:\\ 2x_1+2x_2\le 600\\ 2x_1+8x_2\le 800\\ x_1-8x_2\le 0\\ x_1,x_2\ge 0\end{array}$
4. (d) $\begin{array}{l}maxz=4x_1+2x_2\\ \text{subject to}:\\ 6x_1+2x_2\le 240\\ 2x_1+3x_2\le 200\\ 8x_1+4x_2\le 240\\ x_1,x_2\ge 0\end{array}$
5. (e) $\begin{array}{l}minz=6x_1+3x_2\\ \text{subject to}:\\ 4x_1+2x_2\ge 832\\ 7x_1+3x_2\ge 714\\ 2x_1+9x_2\ge 900\\ x_1,x_2\ge 0\end{array}$
6. (f) $\begin{array}{l}minz=4x_1+5x_2\\ \text{subject to}:\\ 2x_1+3x_2\ge 675\\ 2x_1+5x_2\ge 1,125\\ 3x_1+4x_2\ge 900\\ x_1,x_2\ge 0\end{array}$
7. (g) $\begin{array}{l}minz=2x_1+x_2\\ \text{subject to}:\\ 4x_1+8x_2\ge 1,920\\ 3x_1+2x_2\ge 600\\ 7x_1+3x_2\ge 1,050\\ x_1,x_2\ge 0\end{array}$