Question

Assume that two products \(\mathrm{x}_{1}\) and \(\mathrm{x}_{2}\) are manufactured on two machines 1 and \(2 .\) Product \(\mathrm{x}_{1}\) requires three hours on machine 1 and one-half hour on machine \(2 .\) Product \(\mathrm{x}_{2}\) requires two hours on machine 1 and 1 hour on machine \(2 .\) There are six hours of available capacity on machine 1 and four hours on machine \(2 .\) Finally, each unit of \(\mathrm{x}_{1}\) produces a net increase in profit of \(\$ 12.00\) and each unit of \(\mathrm{x}_{2}\) an incremental profit of \(\$ 4.00 .1\) ) Maximize the profit. 2 ) Obtain a solution to this problem using the simplex method. 3) Apply sensitivity analysis to the final tableau.

Short answer

The optimal solution is to produce \(x_1 = 0\) units of product \(x_1\) and \(x_2 = 3\) units of product \(x_2\), resulting in a maximum profit of \$12. Sensitivity analysis shows that for \(x_1\) to become part of the optimal solution, its profit per unit would have to increase by at least \$6 to \$18. The shadow prices for Machine 1 and Machine 2 indicate that additional machine capacity would improve profits for Machine 1 by \$2 per unit added, whereas additional capacity on Machine 2 would decrease profits by \$0.5 per unit added.

Step-by-step solution

Define Decision Variables and Objective Function

Let \(x_1\) be the number of units of product \(x_1\) produced, and let \(x_2\) be the number of units of product \(x_2\) produced. Our objective is to maximize the profit, which is given by: $$ P(x_1, x_2) = 12x_1 + 4x_2 $$

Define Constraints

We have the following constraints, based on the given machine capacities: $$ 3x_1 + 2x_2 \leq 6 \quad (Machine\ 1) $$ $$ 0.5x_1 + x_2 \leq 4 \quad (Machine\ 2) $$ Furthermore, we must have the non-negativity constraints: $$ x_1 \geq 0, \quad x_2 \geq 0 $$

Transform the Constraints into Canonical Form

Introduce slack variables \(s_1\) and \(s_2\) to transform the inequalities into equalities: $$ 3x_1 + 2x_2 + s_1 = 6 \quad (1) $$ $$ 0.5x_1 + x_2 + s_2 = 4 \quad (2) $$ Now the constraints are in canonical form: $$ x_1, x_2, s_1, s_2 \geq 0 $$

Set up Initial Simplex Tableau

Construct the initial simplex tableau, writing the coefficients of each variable, the constraints, and the objective function: $$ \begin{array}{cccccc} & x_1 & x_2 & s_1 & s_2 & RHS \\ \hline s_1 & 3 & 2 & 1 & 0 & 6 \\ s_2 & 0.5 & 1 & 0 & 1 & 4 \\ -Z & 12 & 4 & 0 & 0 & 0 \\ \end{array} $$

Perform the Simplex Method

Pivot on the second column of the first row, as this will allow us to increase the objective function most rapidly: $$ \begin{array}{cccccc} & x_1 & x_2 & s_1 & s_2 & RHS \\ \hline x_2 & 1.5 & 1 & 0.5 & 0 & 3 \\ s_2 & 0 & 1 & -0.5 & 1 & 1 \\ -Z & 6 & 0 & 2 & 0 & 12 \\ \end{array} $$ Both entries in the objective function row are nonnegative, so we have reached the optimal solution.

Read off Optimal Solution

The optimal solution is: $$ x_1 = 0, x_2 = 3, s_1 = 0, s_2 = 1 $$ With the maximum profit being \(12(0) + 4(3) = \) \$12.

Sensitivity Analysis

The final tableau is already in optimal form. To perform sensitivity analysis, we can examine the reduced costs of the nonbasic variables to determine how much the objective coefficients of any nonbasic variable would have to increase (for maximization problems) before that variable would enter the optimal solution. In this case, the only nonbasic variable with a potential to enter the solution is \(x_1\). The reduced cost for \(x_1\) is \(6\). This means that, for \(x_1\) to become part of the optimal solution, its profit per unit would have to increase by at least \(6\) to \$18. We can also analyze the shadow prices (dual variables) associated with the capacity constraints on the machines. The shadow prices are the amounts by which the optimal solution would improve if an additional unit of machine capacity were available. In this case, the shadow prices are: $$ \begin{align*} \text{For Machine 1: } & 2 \\ \text{For Machine 2: } & -0.5 \\ \end{align*} $$ This means that an additional unit of capacity on Machine 1 would improve the profit by \(2, while an additional unit of capacity on Machine 2 would decrease the profit by \)0.5 (since the shadow price is negative, there is currently excess capacity on Machine 2 that is not being utilized).

Key concepts

Linear Programming

Linear programming (LP) is a mathematical method for determining a way to achieve the best outcome in a given mathematical model whose requirements are represented by linear relationships. It is a foundational technique in operational research and a powerful tool in making strategic business decisions. LP aims to maximize or minimize a linear function subject to linear inequality constraints, typified in the given exercise where the goal is to maximize the profit from manufacturing two products, given the constraints on machine hours.

LP problems consist of an objective function, non-negativity constraints, and a set of linear inequalities known as the constraints of the model. The objective function, in this case, represents the total profit to be maximized from the sale of products \(x_1\) and \(x_2\), while the constraints encapsulate the limited machine hours available for production. The constraints here are \(3x_1 + 2x_2 \leq 6\) for Machine 1 and \(0.5x_1 + x_2 \leq 4\) for Machine 2, along with non-negativity constraints for the production units.

Optimization Constraints

Optimization constraints are the limits or bounds within which an optimization problem must be solved. In the exercise, these constraints are the available hours on the machines that cannot be exceeded. Translating such practical limitations into mathematical constraints is crucial in LP so that any proposed solution is not only optimal in terms of the objective function but also feasible in real-world application.

These constraints often involve resource limitations, such as time, money, or raw materials like in our exercise where machine time is the restricted resource. To solve the LP problem using the simplex method, each inequality constraint is converted to an equation by adding slack variables, \(s_1\) and \(s_2\), which represent the unused capacity of each machine. The introduction of slack variables helps in visualizing and solving the problem through the simplex tableau, ensuring that all conditions for maximum profit are tested and met.

Sensitivity Analysis

Sensitivity analysis in linear programming assesses how sensitive an optimal solution is to changes in the coefficients of the objective function or in the right-hand side constants of the constraints. The ability to perform sensitivity analysis is a significant advantage of LP as it allows decision-makers to understand the impact of variability and uncertainty in their data.

After obtaining the optimal solution using the simplex method, two critical values usually result from sensitivity analysis: reduced costs for the nonbasic variables and shadow prices for the constraints. In the context of the exercise, \(x_1\) is a nonbasic variable with a reduced cost of \(6\). This value indicates how much the profit per unit of \(x_1\) would need to increase for it to be included in the production plan. Additionally, shadow prices provide insights into constraint resources — with shadow prices indicating how much the objective function value would change with a one-unit increase in the resource. The sensitivity analysis reveals that adding one unit of capacity to Machine 1 would be beneficial to profit, whereas there is excess capacity on Machine 2.