DEFINITION
OF LPP
Mathematical technique used in
computer modeling (simulation) to find
the best possible solution in allocating limited resources (energy,
machines, materials, money, personnel, space, time, etc.) to achieve maximum profit or minimum cost.
However, it is applicable only where
all relationships are linear, and can accommodate only a limited class of cost functions. For problems involving more complex cost
functions, another technique called 'mixed integer modeling' is employed. Developed by the Russian economist Leonid Kantorovich (1912-86) and the US economist C.
Koopmans (1910-86), on the basis of the work of the Russian mathematician Andrei Nikolaevich Kolmogorov
(1903-87).
LINEAR
PROGRAMMING INVOLVING TWO VARIABLES
Many
applications in business and economics involve a process called optimization,
in which we are required to find the minimum cost, the maximum profit, or
the minimum use of resources. Here we discuss one type of optimization problem
called linear programming.
A
two-dimensional linear programming problem consists of a linear objective
function and a system of linear inequalities called constraints. The
objective function gives the quantity that is to be maximized (or minimized), and
the constraints determine the set of feasible solutions.
For example,
consider a linear programming problem in which we are asked to maximize the
value of
z = ax + by Objective
function
subject to a set
of constraints that determine the region indicated in Figure 1. Because every
point in the region satisfies each constraint, it is not clear how we should go
about finding the point that yields a maximum value of z. Fortunately,
it can be shown that if there is an optimal solution, it must occur at one of
the vertices of the region. In other words, we can find the maximum value by
testing z at each of the vertices, as illustrated in Example 1.
The
objective function has its optimal value at one of the vertices of the region
determined by the constraints.
Theorem 9.1 Optimal Solution of a Linear Programming Problem
If a linear programming problem has a solution, it must
occur at a vertex of the set of feasible solutions. If the problem has more
than one solution, then at least one of them must occur at a vertex of the set
of feasible solutions. In either case, the value of the objective function is
unique.
EXAMPLE
1: Solving a Linear Programming
Problem
Find the maximum
value of
z = 3x + 2y Objective
function
subject to the
following constraints.
Solution
The constraints form the region shown in Figure 2. At the four
vertices of this region, the objective function has the following values.
Thus,
the maximum value of z is 8, and this occurs when x = 2 and y = 1.