Linear Programming

Operations > Linear Programming

Linear Programming

Operations management often presents complex problems that can be modeled by linear functions. The mathematical technique of linear programming is instrumental in solving a wide range of operations management problems.

Linear Program Structure

Linear programming models consist of an objective function and the constraints on that function. A linear programming model takes the following form:

Objective function:

Z = a₁X₁ + a₂X₂ + a₃X₃ + . . . + a_nX_n

Constraints:

b₁₁X₁ + b₁₂X₂ + b₁₃X₃ + . . . + b_1nX_n < c₁

      b₂₁X₁ + b₂₂X₂ + b₂₃X₃ + . . . + b_2nX_n < c₂
      .
      .
      .
      b_m1X₁ + b_m2X₂ + b_m3X₃ + . . . + b_mnX_n < c_m

In this system of linear equations, Z is the objective function value that is being optimized, X_i are the decision variables whose optimal values are to be found, and a_i, b_ij, and c_i are constants derived from the specifics of the problem.

Linear Programming Assumptions

Linear programming requires linearity in the equations as shown in the above structure. In a linear equation, each decision variable is multiplied by a constant coefficient with no multiplying between decision variables and no nonlinear functions such as logarithms. Linearity requires the following assumptions:

Proportionality - a change in a variable results in a proportionate change in that variable's contribution to the value of the function.
Additivity - the function value is the sum of the contributions of each term.
Divisibility - the decision variables can be divided into non-integer values, taking on fractional values. Integer programming techniques can be used if the divisibility assumption does not hold.

In addition to these linearity assumptions, linear programming assumes certainty; that is, that the coefficients are known and constant.

Problem Formulation

With computers able to solve linear programming problems with ease, the challenge is in problem formulation - translating the problem statement into a system of linear equations to be solved by computer. The information required to write the objective function is derived from the problem statement. The problem is formulated from the problem statement as follows:

Identify the objective of the problem; that is, which quantity is to be optimized. For example, one may seek to maximize profit.
Identify the decision variables and the constraints on them. For example, production quantities and production limits may serve as decision variables and constraints.
Write the objective function and constraints in terms of the decision variables, using information from the problem statement to determine the proper coefficient for each term. Discard any unnecessary information.
Add any implicit constraints, such as non-negative restrictions.
Arrange the system of equations in a consistent form suitable for solving by computer. For example, place all variables on the left side of their equations and list them in the order of their subscripts.

The following guidelines help to reduce the risk of errors in problem formulation:

Be sure to consider any initial conditions.
Make sure that each variable in the objective function appears at least once in the constraints.
Consider constraints that might not be specified explicitly. For example, if there are physical quantities that must be non-negative, then these constraints must be included in the formulation.

The Effect of Constraints

Constraints exist because certain limitations restrict the range of a variable's possible values. A constraint is considered to be binding if changing it also changes the optimal solution. Less severe constraints that do not affect the optimal solution are non-binding.

Tightening a binding constraint can only worsen the objective function value, and loosening a binding constraint can only improve the objective function value. As such, once an optimal solution is found, managers can seek to improve that solution by finding ways to relax binding constraints.

Shadow Price

The shadow price for a constraint is the amount that the objective function value changes per unit change in the constraint. Since constraints often are determined by resources, a comparison of the shadow prices of each constraint provides valuable insight into the most effective place to apply additional resources in order to achieve the best improvement in the objective function value.

The reported shadow price is valid up to the allowable increase or allowable decrease in the constraint.

Applications of Linear Programming

Linear programming is used to solve problems in many aspects of business administration including:

product mix planning
distribution networks
truck routing
staff scheduling
financial portfolios
corporate restructuring

Operations > Linear Programming