UNIT THREE

INTRODUCTION TO LINEAR PROGRAMMING

After studying this unit, you should be able
to:
Understand the meaning and concepts of linear
programming.
Know the technicalities of formulating
linear programming problems in both cases of
minimization and maximization.
Develop familiarity with the graphical method for
solving linear programming problems.
Determine the optimal solution for
linear programming problems by using the
systematic technique of simplex approach.
1
 Defining Linear Programming Model

Linear Programming (LP) is a mathematical

process that has been developed to help
management in decision-making involving the
efficient allocation of scares resources to
achieve a certain objective.
It is a method for choosing the best alternative
from a set of feasible alternatives.
2
Diagrammatically,

3
 3.2 Requirements to Apply Linear Programming

To apply LP, the following conditions must be

satisfied.
 There must be a clearly defined and measurable
objective (e.g., max. profit or sales, Min. cost).
 All activities included must be clearly identifiable
and measurable in quantitative terms.
 Both the objective function and the constraint
relationships must be linear.
 There should be a series of feasible alternative
courses of actions available to the decision-maker
that is determined by the resource constraints.
4
 Formulation of Linear Programming Model
Problem Formulation or Modeling is the
process of translating the verbal statement of a
problem in to mathematical statements.
The characteristics can be grouped into two
categories:
1. Components and
2. Assumptions.
The components relate to the structure of a
model, where as the assumptions describe the
conditions under which the model is valid.
5
The Objective function:
 Is the mathematical/ quantitative expression of the
objective of the company/ model.
 the first major requirement of linear programming problem
(LPP) is that we should be able to identify the goal in
terms of the objective function
The Constraints:
 another requirement of linear programming is that the
resources must be in limited supply
 The mathematical relationship which is used to explain
this limitation is inequality. The limitation itself is known
as a constraint.
Non-negativity Condition:
x1 and x2, being the number of units produced, can't have
negative values. Thus both of them can assume values only
greater than or equal to zero. 6
General Statement of Linear Programming Problem

A Linear Programming Problem is the process of

maximizing or minimizing a linear objective function
subject to a set of linear constraints (equalities or
inequalities) and non-negativity conditions on the decision
variables.
The constraints in the maximization problems are of the <
type, and
The constraints in the minimization problems are of > type ,
a given problem might contain a mix of the constraints,
involving the signs <, >, and /or =. 7
Steps for Formulating Linear Programming Models
[Link] the Problem: Clearly understand what needs
to be optimized (profit, cost, production, etc.).
[Link] Decision Variables:-Represent the unknown
quantities to be determined.
[Link] the Objective Function: Decide whether to
maximize (e.g., profit) or minimize (e.g., cost).
[Link] Constraints
 System Constraints: more than one variable
 Individual Constraints: only 1 variable, e.g., min or max. requirements
 Non-negativity Constraints:
8
Maximization Problem can be written as

Objective Function

System Constraints

Non-negativity

9
 The Maximization Case
In a maximization problem, the goal is to maximize an
objective function, usually representing profit, revenue, or
production a set of constraints.

Example 3.1
A firm is engaged in producing two products, A and B. Each unit of
product A requires two Kgs of raw material and four labor hours for
processing whereas each unit of product B requires three kg of raw
material and three hours of labor of the same type. Every week the firm
has an availability of 60 kgs of raw material and 96 labor hours. One unit
of product A sold yields Birr 40 and one unit of product B sold yields Birr
35 as profit.

• Formulate this problem as a linear programming problem to determine

as to how many units of each of the products should be produced per
week so that the firm can maximum the profit.

10
Minimization Problem can be written as

Objective Function

System Constraints

Non-negativity

11
 The Minimization Case
In a minimization problem, the goal is to reduce or minimize a certain
quantity, such as cost, time, waste, or distance.

Example
The agricultural Research institute has suggested to a farmer to spread out
at least 4800 kg of a special phosphate fertilizer and no less than 7200 kg
of a special nitrogen fertilizer to raise productivity of crops in his fields.
There are two resources for obtaining these mixtures A and B. Both of
these are available in bags weighing 100 kg each and they cost Birr 40 and
Birr 24 respectively. Mixture A contains phosphate and nitrogen equivalent
of 20 kg and 80 respectively, while mixture B contains these ingredients
equivalent of 50 kg each.

• Write this as a linear programming problem and determine how many

bags of each type the farmer should buy in order to obtain the required
fertilizer at minimum cost.

12
 Assumptions Underlying Linear Programming
A linear programming model is based on the assumptions of
proportionality, additively, continuity, certainty, and finite choices.
•Proportionality: A basic assumption of linear programming is that
proportionality exists in the objective function and the constraint
inequalities.
•Additively: states, in the objective function and constraint
inequalities both, the total of all the activities is given by the sum total
of each activity conducted separately.
•Continuity: states that the decision variables are continuous.
Therefore, combinations of output with fractional values, in the
context of production problems, are possible and obtained frequently.
•Certainty: states that the various parameters, namely, the objective
function coefficients, the coefficients of the inequality/equality
constraints and the constraint (resource) values are known with 13
certainty.
 Approaches of Solving LPPs
• Linear programming problems can be solved by
using graphic method or by applying algebraic
method, called the Simplex Method.

1. The graphic method is restricted in application it

can only be used when two variables are involved.

2. The simplex method, whereas is the mathematical

technique of solving linear programming problems
with two or more variables.

14
1. Graphical Solution to LPPs
Steps in Graphic Method of LPP
To use the graphic method, the following steps are needed:

Identify the problem – determine the decision variables, the objective

function, and the constraints.

Draw a graph - including all the constraints and identify the feasible
region.
Obtain a point on the feasible region - that optimizes the objective function
optimal solution.

Interpret the results.

Note: Graphical LP is a two-dimensional model.

15
 The Maximization Problem
Example 3.3
A manufacturer of Light Weight mountain tents makes two types of tents:
REGULAR tent and SUPER tent. Each REGULAR tent requires one labor-
hour from the cutting department and 3 labor-hours from the assembly
department. Each SUPER tent requires 2 labor-hours from the cutting
department and 4 labor-hours from the assembly department. The
maximum labor hours available per week in the cutting department and the
assembly department are 32 and 84 respectively. Moreover, the distributor,
because of demand, will not take more than 12 SUPER tents per week. The
manufacturer sales each REGULAR tents for $160 and costs $110 per tent
to make. Where as SUPER tent ales for $210 per tent and costs $130 per
tent to make.
Required:
a) Formulate the mathematical model of the problem
b) Using the graphic method, determine how many of each tent the company should
manufacture each week so as to maximize its profit?
c) What is this maximum profit assuming that all the tents manufactured in each week are
sold in that week? 16
 The Minimization Problem
Example
A company owns two flourmills (A and B) which have different
production capacities for HIGH, MEDIUM and LOW grade flour. This
company has entered contract supply flour to a firm every week with
12, 8, and 24 quintals of HIGH, MEDIUM and LOW grade
respectively. It costs the Co. $1000 and $800 per day to run mill A and
mill B respectively. On a day, mill A produces 6, 2, and 4 quintals of
HIGH, MEDIUM and LOW grade flour respectively. Mill B produces
2, 2 and 12 quintals of HIGH, MEDIUM and LOW grade flour
respectively.
• How many days per week should each mill be operated in order to
meet the contract order most economically. Solve the problem
graphically.
17