LINEAR
PROGRAMMING
ALBERT R. ANTIPUESTO, IE, LPT, MA-MATH
LINEAR PROGRAMMING
• Refers to planning through the use of a linear relationship of the
variables involved. It applies mathematical techniques to find the best
possible solution to problems in spite of limited resources.
• A good manager can maximize the profit and minimize the cost without
violating the limitation or restriction of variables, such as time and
quantity of available raw material. It is therefore, a must for any
prospective manager to learn and understand linear programming
problems (maximization and minimization).
THE GRAPHICAL METHOD
• Graph is used to arrive at the optimum solution. The optimum solution
is one that makes the objective function as large as possible in the case
of a maximization process and as small as possible in the case of a
minimization process.
• The set of all points in the graph satisfying the constraints is called the
feasible solution. These points are located at the feasible region of the
graph.
• A linear program consists of two parts: the objective function and the
constraints or limitation. The objective function is a mathematical
expression introduced by the words “maximize” or “minimize”. The
constraints are introduced by the word “subject to”.
THE GRAPHICAL METHOD
• The mathematical expression in the constraints is written as
inequalities. Two kinds of constraints may occur. Explicit constraints
means that a condition expressed in a mathematical sentence is
derived from the condition of the problems.
• Implicit constraints are implied conditions such as when time or raw
materials are variables in the problems. These factors must always be
expressed as positive values.
MATHEMATICAL FORMULATION
1. Represent the unknown value in the problem by a variable. If necessary, tabulate the
data to form mathematical sentences.
2. Formulate the objective function and constraints.
3. Using a coordinate plane, graph the constraints to determine the feasible region.
4. The point of intersection of lines can be seen. Solve for the coordinates of the point.
5. Substitute the coordinates at the vertices of the feasible region in the objective function.
6. From the values of coordinates at the vertices, the decision will rely on either the
highest value which corresponds to maximization or the lowest value which corresponds
to minimization.
LINEAR PROGRAMMING:
MAXIMIZATION PROBLEMS
• Graphic Art Inc., a manufacturer of photographic products, prepares
two types of film developers each day: fine and extra fine, using
solutions A and B as the raw material. Suppose that each quart of fine
contains 2 oz of solution A and 1 oz of solution B, while each quart of
extra fine contains 1 oz of solution A and 2 oz of solution B. Suppose
also that the profit is Php80 for each quart of fine and Php100 for each
quart of extra fine. If the firm has 50 oz of solution A and 70 oz of
solution B available each day, how many quarts of fine and how many
quarts of extra fine should be made daily to maximize the profit?
SOLUTION
• Step 1. Tabulate the data and statement of variables
Representatio Number of Quart of Number of Quart of Profit
ns of Fine and Extra Fine Fine and Extra Fine
variables Contained in Solution Contained in Solution
A B
Let x be the 2x x 80x
number of fine
to be made
Let y be the y 2y 100y
number of
extra fine to be
made
Total 2x+y X+2y 80x+100
y
SOLUTION
• Step 2. Formulate the objective function and constraints.
Maximize: 80
• Subject to:
SOLUTION
• Step 3. Graph the objective functions by first converting the
inequalities into equations. Next, find their intercepts.
SOLUTION
