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|
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 xr + 7 xe|
|3 xr + 4 xe £ 650|
|2 xr + 3 xe £ 500|
|xr ³ 0, xe ³ 0.|
What we have just formulated is called a linear program. In this example, it has two decision variables, xr and xe, an objective function, 5 xr + 7 xe, 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 xr and xe. 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 3x2 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"), x1, x2, ..., xn, has the following general format:
|Maximize or Minimize||c1 x1 + c2 x2 + ... + cn xn|
|a11 x1 + a12 x2 + ... + a1n xn £, =, or ³ b1|
|a21 x1 + a22 x2 + ... + a2n xn £, =, or ³ b2|
|am1 x1 + am2 x2 + ... + amn xn £, =, or ³ bm|
|x1, x2, ..., xn ³ 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 5xr and 7xe.|
|Additivity: The combined contribution from different variables, say x1 and x2, to either the objective function or a constraint is the sum of their individual contributions; i.e., the combined contribution assumes the form c1x1 + c2x2. In the product-mix problem, for example, the total net profit equals the sum of 5xr and 7xe.|
|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 cj's, the aij's, and the bi'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.