TWO-VARIABLE LP MODEL
This section deals with the graphical solution of a two-variable LP. Though two-variable problems hardly exist in practice, the treatment provides concrete foundations for the development of the general simplex algorithm presented in Chapter 3.
Example 2.1-1 (The Reddy Mikks Company)
Reddy Mikks produces both interior and exterior paints from two raw materials, Ml and M2. The following table provides the basic data of the problem:
A market survey indicates that the daily demand for interior paint cannot exceed that for exterior paint by more than 1 ton. Also, the maximum daily demand for interior paint is 2 tons.
Reddy Mikks wants to determine the optimum (best) product mix of interior and exterior paints that maximizes the total daily profit.
The LP model, as in any OR model, has three basic components.
1. Decision variables that we seek to determine.
2. Objective (goal) that we need to optimize (maximize or minimize).
3.Constraints that the solution must satisfy.
The proper definition of the decision variables is an essential first step in the development of the model. Once done, the task of constructing the objective function and the constraints becomes more straightforward.
For the Reddy Mikks problem, we need to determine the daily amounts to be produced of exterior and interior paints. Thus the variables of the model are defined as
x1 = Tons produced daily of exterior paint
x2 = Tons produced daily of interior paint
To construct the objective function, note that the company wants to maximize (i.e., increase as much as possible) the total daily profit of both paints. Given that the profits per ton of exteri-or and interior paints are 5 and 4 (thousand) dollars, respectively, it follows that
Total profit from exterior paint = 5x1 (thousand) dollars
Total profit from interior paint = 4X2 (thousand) dollars
Letting z represent the total daily profit (in thousands of dollars), the objective of the company is
Maximize z = 5X1 + 4X2
Next, we construct the constraints that restrict raw material usage and product demand. The raw material restrictions are expressed verbally as
The daily usage of raw material MI is 6 tons per ton of exterior paint and 4 tons per ton of inte-rior paint. Thus
Usage of raw material M1 by exterior paint = 6X1 tons/day
Usage of raw material M1 by interior paint = 4X2 tons/day
Usage of raw material M1 by both paints = 6X1 + 4x2 tons/day
In a similar manner,
Usage of raw material M2 by both paints = IX1 + 2X2 tons/day
Because the daily availabilities of raw materials M1 and M2 are limited to 24 and 6 tons, respectively, the associated restrictions are given as
6x1 + 4x2 <= 24 (Raw material M1)
x1 + 2x2 <=6 (Raw material M2)
The first demand restriction stipulates that the excess of the daily production of interior over exterior paint, X2 - Xl, should not exceed 1 ton, which translates to
x2 – x1 =< 1 (Market limit)
The second demand restriction stipulates that the maximum daily demand of interior paint is limited to 2 tons, which translates to
x2 =< 2 (Demand limit)
An implicit (or "understood-to-be") restriction is that variables xl and x2 cannot assume negative values. The non negativity restrictions, x1>= 0, x2 > = 0, account for this requirement.
The complete Reddy Mikks model is
Maximize z = 5x1 + 4x2
6xI + 4x2 <= 24 (1)
xI + 2x2 =< 6 (2)
-x1 +x2 <= 1 (3)
X2 <= 2 (4)
x1,x2 >= 0 (5)
Any values of x1 and x2 that satisfy all five constraints constitute a feasible solution. Otherwise, the solution is infeasible. For example, the solution, x1 = 3 tons per day and x2 = I ton per day, is feasible because it does not violate any of the constraints, including the nonnegativity restrictions. To verify this result, substitute (x1 = 3, x2 = 1) in the left-hand side of each constraint. In constraint (1) we have 6x1 + 4x2 = 6 x 3 + 4 X 1 == 22, which is less than the right-hand side of the constraint (= 24). Constraints 2 through 5 will yield similar conclusions (verify!). On the other hand, the solution x1 = 4 and x2 = 1 is infeasible because it does not satisfy constraint (I)-namely, 6 X 4 + 4 X 1 = 28, which is larger than the right-hand side (= 24).
The goal of the problem is to find the best feasible solution, or the optimum, that maximizes the total profit. Before we can do that, we need to know how many feasible solutions the Reddy Mikks problem has. The answer, as we will see from the graphical solution in Section 2.2, is "an infinite number," which makes it impossible to solve the problem by enumeration. Instead, we need a systematic procedure that will locate the optimum solution in a finite num-ber of steps. The graphical method in Section 2.2 and its algebraic generalization in Chapter 3 will explain how this can be accomplished.
Properties of the LP Model. In Example 2.1-1, the objective and the constraints are all linear functions. Linearity implies that the LP must satisfy three basic properties:
1. Proportionality: This property requires the contribution of each decision variable in both the objective function and the constraints to be directly proportional to the value of the variable. For example, in the Reddy Mikks model, the quantities 5x1 and 4x1 give the profits for producing x1 and x2 tons of exterior and in- 2.2 terior paint, respectively, with the unit profits per ton, 5 and 4, providing the constants of proportionality. If, on the other hand, Reddy Mikks grants some sort of quantity discounts when sales exceed certain amounts, then the profit will no longer be proportional to the production amounts, x1 and x2, and the profit function becomes nonlinear.
2. Additivity: This property requires the total contribution of all the variables in the objective function and in the constraints to be the direct sum of the individual contributions of each variable. In the Reddy Mikks model, the total profit equals the sum of the two individual profit components. If, however, the two products compete for market share in such a way that an increase in sales of one adversely affects the other, then the additivity property is not satisfied and the model is no longer linear.
3. Certainty: All the objective and constraint coefficients of the LP model are deterministic. This means that they are known constants-a rare occurrence in real life, where data are more likely to be represented by probabilistic distributions. In essence, LP coefficients are average-value approximations of the probabilistic distributions. If the standard deviations of these distributions are sufficiently small, then the approximation is acceptable. Large standard deviations can be accounted for directly by using stochastic LP algorithms (Section 19.2.3) or indirectly by applying sensitivity analysis to the optimum solution (Section 3.6).
PROBLEM SET 2.1A
1. For the Reddy Mikks model, construct each of the following constraints and express it with a linear left-hand side and a constant right-hand side:
(a) The daily demand for interior paint exceeds that of exterior paint by at least 1 ton.
(b) The daily usage of raw material M2 in tons is at most 6 and at least 3.
(c) The demand for interior paint cannot be less than the demand for exterior paint.
(d) The minimum quantity that should be produced of both the interior and the exterior paint is 3 tons.
(e) The proportion of interior paint to the total production of both interior and exterior paints must not exceed .5.
2. Determine the best feasible solution among the following (feasible and infeasible) solutions of the Reddy Mikks model:
(a) x1 = 1, x2 = 4
(b) x1 = 2, x2 = 2
(c) x1 =3, x3 = 1.5
(d) x1 = 2, x2 = 1
(e) x1 =2, x2 = -1
3. For the feasible solution x1=2, x2=2 of the Reddy Mikks model, determine the unused amounts of raw materials Ml and M2.
4. Suppose that Reddy Mikks sells its exterior paint to a single wholesaler at a quantity discount.The profit per ton is $5000 if the contractor buys no more than 2 tons daily and $4500 otherwise. Express the objective function mathematically. Is the resulting function linear?