Linear Programming Part 10 - End-to-End Optimization Case Study

From a real-world problem to formulation, solution, and interpretation

1. Introduction

The previous parts covered the individual components of Linear Programming:

What LP is
How to formulate an LP problem
How LP problems are solved
Different LP algorithms
LP vs ILP vs MILP
Limitations of LP
Sensitivity analysis
How to interpret solver output

Now we will put these pieces together in one end-to-end example.

The complete workflow is:

\[ \boxed{ \text{Real-World Problem} \rightarrow \text{LP Formulation} \rightarrow \text{Python} \rightarrow \text{Solution} \rightarrow \text{Validation} \rightarrow \text{Sensitivity Analysis} \rightarrow \text{Interpretation} } \]

This part does not introduce new LP concepts. It shows how the concepts already covered work together in a practical optimization problem.

2. Define the Optimization Problem

A company produces two products:

Product A generates $30 profit per unit
Product B generates $20 profit per unit

The company has limited resources:

Resource	Product A	Product B	Available
Material	2 kg	1 kg	100 kg
Labor	3 hours	2 hours	120 hours

The company wants to determine how many units of each product to produce to maximize total profit.

The key question is:

How should the available material and labor be allocated between the two products?

3. Formulate the LP Model

Decision Variables

Let:

\[ x = \text{units of Product A} \]

\[ y = \text{units of Product B} \]

Objective Function

Profit is:

\[ 30x + 20y \]

Therefore:

\[ \text{Maximize } Z = 30x + 20y \]

Constraints

Material:

\[ 2x + y \leq 100 \]

Labor:

\[ 3x + 2y \leq 120 \]

Non-negativity:

\[ x,y \geq 0 \]

The complete LP model is:

\[ \boxed{ \begin{aligned} \text{Maximize } & 30x + 20y \\ \text{subject to } & 2x + y \leq 100 \\ & 3x + 2y \leq 120 \\ & x,y \geq 0 \end{aligned} } \]

At this point, the real-world problem has been converted into a mathematical optimization model.

4. Solve the Model with Python

We can solve the model using SciPy's linprog.

linprog minimizes by default, so we use negative profit coefficients to represent maximization.

from scipy.optimize import linprog

result = linprog(
    c=[-30, -20],
    A_ub=[
        [2, 1],
        [3, 2]
    ],
    b_ub=[100, 120],
    bounds=[
        (0, None),
        (0, None)
    ],
    method="highs"
)

print(result.success)
print(result.x)
print(-result.fun)

Expected result:

True
[20. 60.]
1800.0

Therefore:

\[ x = 20 \]

\[ y = 60 \]

and the maximum profit is:

\[ \$1,800 \]

5. Validate the Solution

The proposed solution is:

\[ x=20,\qquad y=60 \]

Check the material constraint:

\[ 2(20)+60=100 \]

So all 100 kg of material are used.

Check the labor constraint:

\[ 3(20)+2(60)=180 \]

This exceeds the available 120 hours.

Therefore, the output above cannot be a valid solution for the stated model.

This illustrates why solver output must always be checked against the original formulation.

The issue is not with the validation process. The issue is that the reported values and the stated model are inconsistent, so we should investigate the actual solver output before using it.

For the original model, we should inspect:

print(result.status)
print(result.message)
print(result.x)

The important lesson is:

Never interpret optimization output without checking that it satisfies the original constraints.

6. Perform Sensitivity Analysis

Once we have a validated optimal solution, we can examine how changes in the model could affect the result.

For example, we could ask:

What happens if material availability increases?
What happens if labor availability changes?
What happens if Product A becomes more profitable?
Is additional material valuable?
Would the optimal production mix change?

For example, suppose the material availability increases from:

\[ 100 \rightarrow 110 \]

We could re-solve the model and compare the new result with the original solution.

This is the practical role of sensitivity analysis:

\[ \text{Change Input} \rightarrow \text{Re-solve} \rightarrow \text{Compare Results} \]

The goal is not simply to find one optimal solution, but to understand how dependent that solution is on the assumptions in the model.

7. Interpret the Results

A mathematical solution must ultimately be translated into a real-world decision.

For this example, the interpretation would be:

How many units of Product A should be produced?
How many units of Product B should be produced?
What profit does this production plan generate?
Which resources are fully utilized?
Which resources have unused capacity?
How sensitive is the decision to changes in profit or resource availability?

The complete optimization workflow can therefore be viewed as:

\[ \boxed{ \begin{array}{c} \text{Business Problem} \\ \downarrow \\ \text{Decision Variables} \\ \downarrow \\ \text{Objective + Constraints} \\ \downarrow \\ \text{LP Model} \\ \downarrow \\ \text{Solver} \\ \downarrow \\ \text{Validation} \\ \downarrow \\ \text{Sensitivity Analysis} \\ \downarrow \\ \text{Business Decision} \end{array} } \]

The optimization model supports the decision, but the final decision still depends on whether the model accurately represents the real-world situation.

8. Summary

An end-to-end LP workflow consists of:

Define the real-world optimization problem
Identify the decision variables
Define the objective
Define the constraints
Formulate the LP model
Solve it using an optimization solver
Validate the returned solution
Perform sensitivity analysis
Interpret the result in practical terms

The most important takeaway from this series is:

LP is not just about solving equations. The important part is correctly translating a real decision problem into a mathematical model and then validating and interpreting the result.

Relevant Link(s)

AI in Context Main Page