Understanding Linear Programming for Optimal Resource Allocation

Linear Programming

Linear Programming is an optimization technique useful for allocating scarce resources among competing demands.

Examples of LP Applications

• Selecting the product mix in a factory to make the best use of machine and labor hours available while maximizing the firm’s profit.
• Scheduling tellers at banks so that needs are met during each hour of the day while minimizing the total cost of labor.
• Determining food ingredient combinations that satisfy stated nutritional requirements at a minimum cost level.

Basic Concepts

• A single objective function states mathematically what is being maximized or minimized.
• Decision variables represent choices that the decision maker can control.
• Constraints are limitations that restrict the decision variables. One of three types: ≤, ≥, =.

Feasible Region

• Parameter or coefficient.
• Linear objective function and constraints.
• Nonnegativity.

Formulating a Problem

1. Step 1: Define the decision variables.
2. Step 2: Write out the objective function.
3. Step 3: Write out the constraints.

As a consistency check, make sure the same unit of measure is being used on both sides of each constraint and the objective function.

Feasible Region: The feasible region is the area on the graph that contains the solutions which satisfy all of the constraints simultaneously, including the nonnegativity restrictions.

Locate the area that satisfies all of the constraints using three rules:

• For the = constraint, only the points on the line are feasible solutions.
• For the ≤ constraint, the points on the line and the points below and/or to the left are feasible solutions.
• For the ≥ constraint, the points on the line and the points above and/or to the right are feasible solutions.

Slack and Surplus Variables

A binding constraint is a resource that is completely exhausted when the optimal solution is used because it limits the ability to improve the objective function.

Insert the optimal solution into a constraint equation and solve it. If the number on the left-hand side and the number on the right-hand side are equal, then the constraint is binding.

Relaxing a constraint means increasing the right-hand side for a ≤ constraint and decreasing the right-hand side for a ≥ constraint.

Relaxing a binding constraint means a better solution is possible.

Rarely are the parameters in the objective function and constraints known with certainty.

Usually, parameters are just estimates which don’t reflect uncertainties such as absenteeism or personal transfers in the Stratton Company problem.

After solving the problem using these estimated values, the analysts can determine how much the optimal values of the decision variables and the objective function value Z would be affected if certain parameters had different values. This type of post-solution analysis for answering “what-if” questions is called sensitivity analysis.

Reduced Cost

The sensitivity number is relevant only for a decision variable that is 0 in the optimal solution.

It reports how much the objective function coefficient must improve before it would enter the optimal solution at some positive level.

Shadow Price: The number is relevant only for binding constraints.