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.

**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 = 5X_{1}
+ *4X _{2}*

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 = 6X_{1} tons/day

Usage of
raw material *M1 *by interior paint = *4X _{2}* tons/day

Hence

Usage of
raw material *M _{1}* by both paints =

In a
similar manner,

Usage of
raw material *M _{2}* by both paints = IX

Because
the daily availabilities of raw materials *M _{1}* and

6x_{1} + *4x _{2}* <= 24 (Raw
material

x_{1 }+ 2x_{2} <=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

x_{2}
– x_{1} =< 1 (Market limit)

The
second demand restriction stipulates that the maximum daily demand of interior
paint is limited to 2 tons, which translates to

*x _{2}* =< 2 (Demand limit)

An
implicit (or "understood-to-be") restriction is that variables x_{l}
and *x _{2}* cannot assume
negative values. The non negativity restrictions, x

The
complete Reddy Mikks model is

Maximize
z = 5x_{1} + 4x_{2}

subject
to

6x_{I} + 4x_{2} <= 24 (1)

x_{I}^{
} + 2x_{2} =< 6 (2)

-x_{1}
+x_{2} <= 1 (3)

X_{2}
<= 2 (4)

x_{1},x_{2}
>= 0 (5)

Any
values of x_{1} and *x _{2}*
that satisfy

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 5x_{1} and *4x _{1 }* give the profits for producing x

**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) x_{1}
= 1, x_{2} = 4

(b) x_{1}
= 2, x_{2} = 2

(c) x_{1}
=3, x_{3} = 1.5

(d) x_{1}
= 2, x_{2} = 1

(e) x_{1}
=2, x_{2} = -1

3. For
the feasible solution x_{1}=2, x_{2}=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?

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Operations Research: An Introduction : Modeling with Linear Programming : Two-Variable LP Model |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.