A linear program is a mathematical optimization model that has a linear objective function and a set of linear constraints. To provide a quick overview, we describe below what is known as the product-mix problem.
The Product-Mix Problem
A company manufactures two models of a product, which we call the regular model and the enhanced model. Two resources, A and B, are needed for the manufacturing of units of this product; and the detailed resource requirements are given in the following table:
Regular Model | Enhanced Model | |
Resource A | 3 | 4 |
Resource B | 2 | 3 |
Suppose further that the company has 650 units of Resource A and 500 units of Resource B available per week, and that the net profits for selling units of the regular model and the enhanced model are given respectively as $5 and $7 per unit. The question of interest is: What are the optimal weekly production levels for these two models?
To formulate this problem, we first define a set of decision variables. Let
Next, suppose our goal is to maximize weekly total profit. Then, in terms of these decision variables, we have:
Our problem can now be stated formally as:
Maximize | 5 x_{r} + 7 x_{e} |
Subject to: | |
3 x_{r} + 4 x_{e} £ 650 | |
2 x_{r} + 3 x_{e} £ 500 | |
x_{r} ³ 0, x_{e} ³ 0. |
What we have just formulated is called a linear program. In this example, it has two decision variables, x_{r} and x_{e}, an objective function, 5 x_{r} + 7 x_{e}, and a set of four constraints. The objective function is to be maximized subject to the specified constraints on the decision variables. It is customary to refer to the first group of constraints,
Notice that each term in the objective function has the form cx, where c is a constant and x is a variable. In other words, the objective function is linear in the decision variables x_{r} and x_{e}. Notice further that the left-hand-side expressions in all four constraints are also linear. This is why we call the above problem a linear program.
If a term such as 3x^{2} appears in a formulation, then the resulting problem is said to be nonlinear.
More generally, a linear program with m functional constraints and n decision variables (or "activities"), x_{1}, x_{2}, ..., x_{n}, has the following general format:
Maximize or Minimize | c_{1} x_{1} + c_{2} x_{2} + ... + c_{n} x_{n} |
Subject to: | |
a_{11} x_{1} + a_{12} x_{2} + ... + a_{1n} x_{n} £, =, or ³ b_{1} | |
a_{21} x_{1} + a_{22} x_{2} + ... + a_{2n} x_{n} £, =, or ³ b_{2} | |
..... | |
a_{m1} x_{1} + a_{m2} x_{2} + ... + a_{mn} x_{n} £, =, or ³ b_{m} | |
x_{1}, x_{2}, ..., x_{n} ³ 0, |
In any formulation effort, one has to make simplifying assumptions. We now describe more formally a number of important assumptions in a linear-programming formulation:
Proportionality: The total contribution of any variable (or activity), say x, to either the objective function or a constraint is proportional to x; i.e., the total contribution assumes the form cx, where c is a constant. In the product-mix problem, for example, the total contributions to the net profit from the sale of the regular model and the enhanced model are assumed to be given, respectively, by 5x_{r} and 7x_{e}. |
Additivity: The combined contribution from different variables, say x_{1} and x_{2}, to either the objective function or a constraint is the sum of their individual contributions; i.e., the combined contribution assumes the form c_{1}x_{1} + c_{2}x_{2}. In the product-mix problem, for example, the total net profit equals the sum of 5x_{r} and 7x_{e}. |
Divisibility: Every decision variable can assume fractional values; i.e., all variables are continuous. This assumption may not be valid in the product-mix problem, since the product under consideraton could be, say, cars. |
Certainty: All input parameters of the problem (i.e., the c_{j}'s, the a_{ij}'s, and the b_{i}'s) are assumed to be known with certainty, i.e., deterministic. |
Other assumptions that are implicit in our formulation of the product-mix problem include:
The product-mix problem can be solved by the Simplex method, which is an efficient mathematical procedure for solving linear programs. It can be shown that the optimal solution to our product-mix problem is to produce a "mix" of: 0 regular model and 162.5 enhanced models. This solution achieves an objective-function value of 1137.5.
This optimal solution was generated by LINDO, a software for solving mathematical programs. You should download and install the software now.