UNIT 3: INTRODUCTION TO

LINEAR PROGRAMMING

By: H/mariam K.
CONTENTS
 Introduction
 Linear Programming Models
 Formulating LP Models
 Solution Approaches to Linear

Programming Problems
OBJECTIVES AND AIMS
Atthe end of this chapter You
should be able to:
Apply knowledge of linear
programming to solve
managerial problems,
Be able to use linear
programming models to solve
managerial problems having
quantitative application.
 INTRODUCTION
 “Linear programming” consists of two words as linear
and programming.
 The word “linear” defines the relationship between

multiple variables with degree one.

 Programming” defines the process of selecting
the best solution from various alternatives.
 Linear programming- is an optimization

method which shows how to allocate scarce

resources in the best possible way subject to
more than one limiting condition expressed in
the form of inequalities and /or equations.
 Enables users to find optimal solution to

certain problems in which the solution must

satisfy a given set of requirements or constraints.
INTRODUCTION
 Optimization in linear
programming implies either
Maximization (max) Profit, revenue,
sales, market share or
Minimization (min) Cost, time,
distance, or a certain objective
function.
 We can’t max/min two quantities
in one model.
LINEAR PROGRAMING
 Involves linearly related multi-
variety functions i.e.
Functions with more than one
independent variables.
 Goal : finding the best solution
given the constraints imposed by
the problem, hence the term
constrained optimization.
 LINEAR PROGRAMMING
MODELS
 LP models are mathematical
representation of LP problems.
 Some models have a specialized

format where as others have a more

generalized format.
 Despite this, LPMs have certain

characteristics in common
Knowledge of these characteristics
enables us to recognize problems that are
amenable to a solution using LP models
and to correctly formulate a LP model.
…. CHARACTERISTICS …
 The characteristics can be grouped
into two categories:
1)Components and
2)assumptions.
 Components relate to the
structure of a model,
 Assumptions describe the
conditions under which the model
is valid.
CHARACTERSTICS …
COMPONENTS
CHARACTERISTICS….. ASSUMPTIONS
COMPONENTS OF LP MODEL
 Objective function: is the
mathematical/ quantitative
expression of the objective of the
company/ model.
 The objective in problem solving is

the criterion by which all decisions

are evaluated.
 COMPONENTS OF LP MODEL
 In
LPMs a single quantifiable objective
must be specified by the decision
maker.
For example, the objective might
relate to profits, or costs or market
share, best to only one of these.
 Moreover,because we are dealing
with optimization, the objective will be
either maximization or minimization,
but not both at a time
 COMPONENTS OF LP MODEL
 The Decision Variables: represent
unknown quantities to be resolved for.
 Decision variables may represent such

things as the:
 Number of units of different products to be sold
 The Number of of dollars to invest in various
projects
 the Number of of ads to place with different
media
 Sincethe decision maker has freedom of
choice among actions, these decision
variables are controllable variables.
COMPONENTS OF LP MODEL
Constraints: are restrictions
which define or limit the
attainability (achievability) or
feasibility of a proposed
course of action.
They limit the degree to which

the objective can be pursued.

COMPONENTS OF LP MODEL
Atypical restriction embodies
scarce resources
labor supply, raw materials,
production capacity, machine time,
storage space,
legal or contractual requirements
(leg. Product standards, work
standards), or
Other limits based on forecasts,
customer orders, company policies
etc.
COMPONENTS OF LP MODEL
Parameters- are fixed values
that specify the impact that
one unit of each decision
variable will have on the
objective and on any
constraint it pertains to as
well as to the numerical value
of each constraint.
COMPONENTS OF LP MODEL
Components are the building
blocks of any LP model.
We can better understand

their meaning by examining a

simple LP model as follows.
EXAMPLE :
 System constraints- involve more than
one decision variables
 Individual constraint- involve only one

decision variable.
 None-negativity constrains- specify

that no variable will be allowed to take

on a negative value.
 The non negativity constraints

typically apply in a LP model, whether

they are explicitly stated or not.
 ASSUMPTION OF LP MODELS
A) LINEARITY: RELATIONSHIP BETWEEN
MULTIPLE VARIABLES WITH DEGREE ONE.

 The linearity requirement is that each

decision variable has a linear impact on
the objective function and in each
constraint in which it appears.
 Taking the above example, producing one

more unit of products add br 4 to the total

profit.
 This is true over the entire range of possible

values of x1.
 Thesame applies (true) to each of the
constraints.
B) DIVISIBILITY:
 The divisibility requirement
pertains to potential values of
decision variables.
 It is assumed that non-integer

values are acceptable.

 For example: 3.5 TV sets/ hr

would be acceptable 7TV sets/

2hr.
C) CERTAINTY:
 The parameters are known and constant.
 The certainty requirement involves two aspects

of LP models.
 The constraint equations do not change.

 With respect to model parameters (i.e. the

numerical values) –It is assumed that these
values are known and constant.
 Eg. In the above example each unit of product
1 requires 2 labor hours is known and remain
constant, and also the 300 labor available is
deemed to be known and constant.
 All the relevant constraints identified and
represented in the model are as they are.
D) NON-NEGATIVITY-
The non-negativity constraint
is that negative values of
variables are unrealistic and,
Therefore, will not be

considered in any potential

solutions, only positive values
and zero will be allowed.
FORMULATING LP MODELS
 Once a problem has been
defined, the attention of the
analyst shifts to formulating a
model.
 To solve the problem it is

important to carefully formulate

the model.
 If the LP model is ill formulated,

ill-structured, it can easily lend

to poor decisions.
FORMULATING LINEAR PROGRAMMING
MODELS INVOLVES THE FOLLOWING STEPS:

A) Define the problem/

problems definition:
To determine the number
of type 1 and type 2
products to be produced
per month so as to
maximize the monetary
profit given the restriction.
FORMULATING LINEAR
PROGRAMMING MODELS ….

B) Identity the decision

variables or represent
unknown quantities.
 Let X and X be the
1 2
monthly quantities of type
1 and type 2 products.
FORMULATING LINEAR
PROGRAMMING MODELS ….
C) Determine the objective
function:
 Once the variables have been

identified, the objective function

can be specified.
 It is necessary to decide if the

problem is a maximization or a
minimization problem and the
coefficients of each decision
variable.
FORMULATING LINEAR
PROGRAMMING MODELS …

D) Identify the constraints

System constraints- more

than one variable

Individual constraints- one

variable
Non-negativity constraints.
 CHECK YOUR PROGRESS
1. A firm that assembles computers and
computer equipment is about to start
production of two new micro computers.
Each type of microcomputer will require
assembly time, inspection time, and
storage space. The amount of each of
three resources that can be devoted to the
production of micro computers is limited.
The manager of the firm would like to
determine the quantity of each micro computer
to produce in order to maximize the profit
generated by sales of these micro computers.
 CHECK …ADDITIONAL INFORMATION
 Inorder to develop a suitable model of the
problem, the manager has met with the
design and manufacturing personnel. As
a result of these meetings, the manager has
obtained the following information:
CHECK …
 The manager also has acquired
information on the available company
resources.
 These (weekly) amounts are:
CHECK …ADDITIONAL
INFORMATION
 The manager has also met with the
firms marketing manager and learned
that demand for the micro computers
was such that whatever combination
of these two types of micro
computers is produced, all of the
output can be sold.
SOLUTION
 Step 1: Problem definition
 To determine the number of two

types of microcomputers to be
produced (and sold) per week so as
to maximize the weekly profit
given the restrictions.
 Step 2: Variable representation

 Let X and X be the weekly

1 2
quantities of type 1 and type 2
microcomputers respectively.
 SOLUTION …
 Step 3: Develop the objective
function
 Maximize or Z max = 60X + 50X
1 2
 Step 4: Constraint identification
SOLUTION
 EXAMPLE 2
2. An electronics firm produces three types of
switching devices. Each type involves a two-
step assembly operation. The assembly times
are shown in the following table:
 EXAMPLE 2 ….
 Each workstation has a daily working
time of 7.5 hrs. The manager want to
obtain the greatest possible profit
during the next five working days.
 Model A yields a profit of br. 8.25 per

unit, Model B a profit of br 7.5 per unit

and model C a profit of Br 7.8 per unit.
Assume that the firm can sell all it
produces during this time, but it must
fill outstanding orders for 20 units of
each model type.
REQUIRED: FORMULATE THE LINEAR
PROGRAMMING MODEL OF THIS PROBLEM.
Solution
 Step 1: Problem definition: to
determine the number of three types
of switching devices to be produced
and sold for the next 5 days (working)
so as to maximize the 5 days profit.
 Step 2: Variable representation

 Let X , X , and X be the number of

1 2 3
model A, B and C switching devices to
be produced and sold.
 SOLUTION ….
 Step3:Develop objective function
Z max = 8.25X1 + 7.50X2 + 7.80X3
SOLUTION …
SOLUTION APPROACHES TO LINEAR
PROGRAMMING PROBLEMS

There are too approaches

to solve linear
programming problems.
The graphic solution
method
The algebraic solution/
simplex algorithm
THE GRAPHIC SOLUTION METHOD
Relatively straight forward
method for determining the
optimal solution to certain
linear programming problems.
It gives us a clear picture.
 Canbe used only to solve
problems that involve two
decision variables.
…. GRAPHIC SOLUTION ….
 However, most linear
programming applications involve
situations that have more than
two decision variables, so the
graphic approach is not used to
solve these.
 Example 1. Solving the micro-

computer problem with graphic

approach.
…. GRAPHIC SOLUTION ….
STEPS
 Plot each of the constraints and
identify its region.
 Identify the common region,

which is all area that contains all

of the points that satisfy the
entire set of constraints.
 Determine the optimal solution-

identify the point which lead to

maximum benefit or minimum
cost.
 To identity the maximum (minimum) value we
use the corner point approach or the extreme
point approach.
 The corner point/ extreme point approach has

one theorem.
 It states that: For problems that have optimal

solutions, a solution will occur at an extreme,

or corner point.
 Thus if a problem has a single optimal

solution, it will occur at a corner point.

 If it has multiple optimal solutions, at least

one will occur at a corner point consequently,

in searching for an optimal solution to a
problem, we need any consider the extreme
points because one of those must be optimal
 Determining the value of the objective
function at each corner point, we could
identify the optimal solution by
selecting the corner point that has the
best value (i.e. maximum or minimum,
depending on the optimization case) of
the objective function.
 Extreme points represent interactions

of constraints.
 Determine the values of the decision

variables at each corner point.

 Some times, this can be done by
impaction (observation) and
sometimes by simultaneous
equation.
 Substitute the value of the

decision variables at each

corner point into the
objective function to obtain
its value at each corner point.
 After getting optimal solution, substitute
the value of the decision variables into the
constraints and check whether all the
resources available are used or not.
 If there is any unused resources we can use

it for any other purpose.

 The amount of unused resource is known as

slack- the amount of a scarce resource

that is unused by a given solution.
 The slack can range from zero, for a

case in which all of a particular resource is

used, to the original amount of the resource
that was available (i.e. none of it is used.)
SLACK
 SLACK….. BINDING CONSTRAINT

 Constraints that have no slack are

sometimes referred to as binding
constraints since they limit or bind the
solution.
 In the above cases, inspection time and

storage space are binding constraints,

while assembly time has slack.
 Knowledge of unused capacity can be

useful for planning.

 A manager may be able to use the

remaining assembly time for other

products, or, perhaps to schedule
equipment maintenance, safety
Interpretation: The company is
advised to produce 9 units of type
1 micro computer and 4 units of
type 2 micro computers per week
to maximize its early profit to Br.
740, and in doing so the company
would be left with unused resource
of 24 assembly hrs which can be
used for other purposes.
EXAMPLE 2: SOLVING THE DIET
PROBLEM WITH GRAPHIC APPROACH.
SOLUTION….

Basic solution X1 = 5 pounds X2 = 3

pounds C = 49 br.
Interpretation to make the diet the
minimum cost of br 49 we have to purchase
5 pounds of type 1 food and 3 pounds type
2 food.
 If there is a difference between the
minimum required amount and the
optimal solution, we call the difference
surplus.
 Surplus is the amount by which the optimal

solution causes a constraint to exceed the

required minimum amount.
 It can be determined in the same way that

slack can: substitute the optimum values of

the decision variables into the left side of the
constraint and solve.
 The difference between the resulting value

and the original right-hand side amount is

the amount of surplus.
 Surplus can potentially occur in a constraint.
The Simplex Algorithm/
Algebraic Solution
Method
 SIMPLEX
 An iterative technique that begins with
a feasible solution that is not
optimal, but serves as a starting point.
 Through algebraic manipulation,

the solution is improved until no

further improvement is possible (i.e.
until the optimal solution has been
identified.)
 Each iteration/ repetition moves one

step closer to the optimal solution.

 SIMPLEX …
 The optimal solution to a LPM will occur at an

extreme point of the feasible solution space.

 This is true even if a model involves more than

two variables; optimal solutions will occur at

these point of the feasible solution space; some
will be outside of the feasible solution space.
 Hence, not every solution will be a feasible

solution.
 Solutions which represent information of

constraints are called basic solutions; those

which also satisfy all of the constraints,
including the non-negativity constraints, are
called basic feasible solutions.
 SIMPLEX …
 The simplex method is an algebraic
procedure for systematically
examining basic feasible solutions.
 If an optimal solution exists, the

simplex method will identify it.

 # of basic solution n + mCm  not

all basic solutions are feasible.

THE SIMPLEX PROCEDURE FOR A MAXIMIZATION
PROBLEM WITH ALL CONSTRAINTS CONSISTS
OF THE FOLLOWING STEPS.

1. Write the LPM in a Standard form:

Constraints are written as
equalities, the LP program is said
to be in a standard form.
We convert the LPM in to a
standard form by applying the
slack variables, s, which carries
a subscript that denotes which
constraint it applies to.
 For example,
 S1 refers to the amount of slack in the first
constraint,
 S2 to the amount of slack in the second constraint,
and so on.
 When slack variables are introduced to the
constraints, they are no longer inequalities b/c the
slack variable accounts, they become equalities.
 Further more, every variable in a model must be
represented in the objective function.
 However, since slack does not provide any real
contribution to the objective, each slack variable
is a assigned a coefficient of zero in the objective
function.
2. Develop the initial tableau
List the variables across the top
of the table and write the
objective function coefficient of
each variables just above it.
There should be one row in the
body of the table for each
constraint.
List the slack variables in the
basis column, one per row.
 Inthe Cj column, enter the objective
function coefficient of zero for each slack
variable.
 Compute values for row Zj.

Compute values for Cj – Zj.

Cj = Coefficinte of variable J in the
objective function.
bj = RHSV of constraint i.

Aij – coefficient of variable j in

constraint i
3. Develop subsequent tables
 3.1 Identify the entry variable –variable

that has a largest positive value in the

Cj – Zj row.
 3.2 Identify the leaving variable –using

the constraint coefficient or substitution

rates in the entering variable column
divide each one into the corresponding
quantity value RHS.
 However do not divide by a zero or

negative value.
 The smalls non negative ratio that

results indicate which variable will leave

the solution
4. Find unique vectors for the new basic
variable using row operations on
the pivot element.
5. Compute Cj – Zj row
6. If all Cj – Zj Values are zeros and
negatives, you have reached
optimality
7. If this is not the case (step 6), repeat
2 to 5 until you get optional
solution.
 “A simplex solution in a maximization problem
in optional if the Cj – Zj row consists entirely of
zeros and negative numbers (i.e. there are no
positive values in the bottom row.)”
 Note: The variables in solution all have unit

vectors in their respective columns for the

constraint equations.
 Further, note that a zero appears in row C – Z

in every column whose variable is in solution,

in row C – Z in every column whose variable is
in solution, indicating that its maximum
contribution to the objective function has been
realized.