Chapter -three

Linear programming

1
 Learning Objectives
 Define and explain LP
 Explain the basic assumption LP
 Describe merits and limitation LP
 Understand the application areas of LP
 Identify basic steps LP formulation
 Be able to formulate LP for various problems.

2
 3.1. Basic Concepts of Linear Programming

• Linear Programming: is a technique for making

decisions under certainty i.e.; when all the courses of
options available to an organization are known & the
objective of the firm along with its constraints are
quantified.
• That course of action is chosen out of all possible
alternatives which yield the optimal results

3
Basic Concepts of Linear Programming …cont’d

Linear Programming is an optimization

technique, where the underlying objective is
either to maximize the profits or to minimize the Cost.

It deals with the problem of allocation of finite

limited resources amongst different competing
activities in the most optimal manner.

4
 Basic Concepts of Linear Programming …cont’d

• Therefore , LP is a mathematical method for determining a

way to achieve the best outcome (such as maximum profit or
lowest cost) in a given mathematical model for some list of
requirements represented as linear relationships.

• More formally, linear programming is a technique for the

optimization of a linear objective function, subject to
linear equality and linear inequality constraints

5
Application of LP

 Linear Programming has been highly successful in

solving the following types of problems :

Product-mix problems.

Investment planning problems.

Blending strategy formulations

Marketing & Distribution management

6
 Application of LP…cont’d
 Moreover, Some of the major application areas to which
LP can be applied are:
Work scheduling
Production planning & Production process
Capital budgeting
Financial planning
Blending (e.g. Oil refinery management)
Farm planning
Distribution

7
 Common properties of LP

 The objective is always the same (i.e. profit Maximization or

cost minimization).

 Presence of constraints (which limit the extent to which

the objective can be achieved.)

 Availability of alternatives (i.e.; different courses of

action to choose from, )

 The objectives and constraints can be expressed in the

form of linear relation.

8
 Components of LPM

1.Objective
2.Decision variables
3.Constraints
4.Parameters

9
basic assumptions in LP
Proportionality:
 The contribution to the objective function from each
decision variable is proportional to the value of the
decision variable.
Additivity:
• The contribution to the objective function for any
decision variable is independent of the values of the other
decision variables

10
 Assumptions… cont’d
Divisibility.
• Variables may be assigned fractional
values. i.e.; they need not necessarily
always be in whole number. If a fraction of a
product cannot be produced, an integer
programming problem exists.
• Thus, the continuous values of the
decision variables and resources must be
permissible in obtaining an optimal solution.
11
 Assumptions… cont’d
Certainty.
– It is assumed that conditions of certainty exist
i.e.; all the relevant parameters or coefficients in
the Linear Programming model are ful1y and
completely known and that they don't change during
the period. However, such an assumption may not
hold good at all times.
Finiteness. LP assumes the presence of a finite
number of activities and constraints without
which it is not possible to obtain the best or the
optimal solution.
12
13
 Merits and limitation LP
• Following are certain advantages of linear programming:

1. Linear programming helps in attaining the optimum use

of productive resources.
2. Linear programming techniques improve the quality of
decisions. The decision-making approach of the user of
this technique becomes more objective and less
subjective.

14
 Merits and limitation LP….cont’d

3. Linear programming techniques provide

possible and practical solutions since there might
be other constraints operating outside the
problem which must be taken into account.

15
 Merits and limitation LP….cont’d

4. Highlighting of bottlenecks in the

production process is the most significant
advantage of this technique
5. Linear programming also helps in re-
evaluation of a basic plan for changing
conditions

16
 Merits and limitation LP….cont’d

2. Limitations of Linear Programming:

• there are some limitations associated with this
technique. These are given here below
1. Linear programming treats all relationships among
decision variables as linear. However, generally, neither
the objective functions nor the constraints in real-life
situations concerning business and industrial problems,
are linearly related to the variables.

17
 Merits and limitation LP….cont’d
2. While solving an LP model, there is no guarantee that we
will get integer valued solutions.
 For example, in finding out how many men and
machines would be required to perform a particular job, a
non-integer valued solution will be meaningless.
Rounding off the solution to the nearest integer will not
yield an optimal solution.
 In such cases integer programming is used to ensure
integer value to the decision variables. 18
Structure of LPM

19
 Cont’d…
Where:
• (< = >) means any of the three signs may be there:
• Optimize means maximize or minimize objective
function
• All constraints are equations except for non-negativity
restrictions which are inequalities
• The right hand side (RHS) of each constraints are non-
negative
20
• Inequality constraints can be changed to equality by adding
or subtracting the LHS of each constraint by non-negative
variable i.e., a slack variable S1 is added to LHS of

constraint with the sign < and a surplus variable S2 is

subtracted on the LHS of constraint with the sign >) and
also artificial variables in case of equal signs and > signs

• aij and bm are known coefficients and xj is unknown

variable
21
 Linear Programming problem Formation
Steps in Formulating a Linear Programming Model:
Step I: Identification of the decision variables.
The decision variables (parameters) having a bearing on the decision at
hand shall first be identified, and then expressed or determined in the
form of linear algebraic functions or in equations
a) Express each constraint in words. For this first see whether the
constraint is of the form ≥ (at least, as large as), or of the form ≤ (no
larger than) or = (exactly equal)

b) Then express the objective function verbally.

c) Step (a) and (b) should then allow you to verbally identify the
decision variables.
22
 Steps cont’d..
Step II : Identification of the constraints.
All the constraints in the given problem which restrict the
operation of a firm at a given point of time must be identified in
this stage.
Further these constraints should be broken down as linear
functions in terms of the pre-defined decision variables.
Step III : formulate the objective function.
In the last stage, the objective which is required to be optimized
(i.e., maximized or minimized ) must be dearly identified and
expressed in terms of the pre-defined decision variables
23
 Example :1
• 3F furniture Ltd. manufactures two products, tables & chair. Both the products
have to be processed through two machines Ml & M2 the total machine-hours

available are: 200 hours of M1 and 400 hours of M2 respectively. Time in hours
required for producing a chair and a table on both the machines is as follows:
Time in hour
Machine Table Chair
M1 7 4
M2 5 5
Profit from the Sale of table is Birr 40 and that of a chair is Birr 30

Required: formulate the LP Problem (LPP)?

24
Solution
Step I Identification of the decision variables. Let
x1 = Number of tables produced and
X2 = Number of Chairs produced
Step II List down all the constraints.
a. Total time on machine M1 cannot exceed 200 hour

(Sinceit takes 7 hours to produce a table & 4 hours to produce a chair

on machine M1)

25
 Solution… cont’d..
b. Total time on machine M2 cannot exceed 400 hour

(Since it takes 5 hours to produce both a table & a chair on

machine M2)
Step III. The objective function for maximizing the profit is given by
Maximize

• (Since profit per unit from a table and a chair is Birr 40 & Birr.
30 respectively).

26
 Solution…cont’d
• Presenting the problem as LPP, the given problem can
now be formulated as a linear programming model as
follows:
Maximize Z
Subject to:

Further;

27
 Example :2

XYZ manufactures two types of wooden toys: soldiers and trains. A soldier
sells for 27 birr and uses 10 birr worth of raw materials, and variable with
overhead cost is 14 birr. A train sells for 21 birr and uses 9 birr worth of raw
materials, and variable with overhead cost is 10 birr. They need two types
of skilled carpentry and finishing. A soldier requires 2 hrs of finishing labor
and 1 hr of carpentry labor. A train requires 1 hr of finishing and 1 hr of
carpentry labor . The company has 100 finishing hours and 80 carpentry
hours in a week. Demand for trains is unlimited, but at most 40 soldiers are
bought each week. Formulate mathematical model that can be used to
maximize profit.

28
 Decision Variables

x1= number of soldiers produced each week

x2= number of trains produced each week

29
Objective Function
Maximize z=3x1+2x2
Constraints
• Constraint 1: Each week, no more than 100 hours
of finishing time may be used.
• Constraint 2: Each week, no more than 80 hours of
carpentry time may be used.
• At most 40 soldiers should be produced each week
• 2x1 +x2 ≤ 100
• x1 +x2 ≤ 80
• x1 ≤ 40
30
 Sign Restrictions

• x1>=0
• x2>=0

31
 Method for solving LPP

• There are two types of finding a solution for

Linear programming problems.
–Graphic solution and
–Simplex solution

32
 Graphical Method of solving Linear Programming Problems

• The graphic solution procedure is one of

the methods of solving two variable linear
programming problems

33
 Graphical Method of solving LP P….cont’d
Steps in graphic solution method:-
1. Step I: Defining the problem.
 Formulate the problem mathematically. Express it in
terms of several mathematical constraints & an
objective function.
 The objective function relates to the optimization
aspect, i.e. Maximization or minimization
Criterion.

34
 Graphical Method of solving LP P….cont’d

2. Step II Plot the constraints graphically.

Each inequality in the constraint equation has to be treated
as an equations

An arbitrary value is assigned to one variable & the value of

the other variable is obtained by solving the equation.

In the similar manner, a different arbitrary value is again

assigned to the variable & the corresponding value of other
variable is easily obtained. 35
Graphical Method of solving LP P….cont’d

These 2 sets of values are now plotted on a graph

and connected by a straight line. The same
procedure has to be repeated for all the constraints.

Hence, the total straight lines would be equal to the

total no of equations, each straight line representing
one constraint equation.

36
 Graphical Method of solving LP P….cont’d
Step III Locate the solution space.
Solution space or the feasible region is the
graphical area which satisfies all the constraints
at the same time.
Such a solution point (x, y) always occurs at the
corner Points of the feasible Region and the
feasible region is determined as follows:

37
 Graphical Method of solving LP P….cont’d

1. For "greater than" & "greater than or equal to"

constraints, the feasible region or the solution space
is the area that lays above the constraint lines.

2. For" Less Then" &" Less than or equal to"

constraint, the feasible region or the solution space
is the area that lays below the constraint lines

38
 Graphical Method of solving LP P….cont’d
Step IV : Selecting the graphic solution technique.
 Select the appropriate graphic technique to be used for
generating the solution. There are two graphic techniques
to find solution;
– Corner Point Method and

– Iso-profit (or Iso-cost) method may be used;

• However, it is easier to generate solution by using the

corner point method and we use this method to find
solution. 39
 Important Terms

 Some of the important terms commonly used in linear

programming are disclosed as follows:
 Solution: Values of the decision variable satisfying the
constraints of a general linear programming model is known
as the solution to that linear programming model.
 Feasible solution: Out of the total available solution a
solution that also satisfies the non-negativity restrictions of
the linear programming problem is called a feasible
solution.
40
 Important Terms
Basic solution:
 For a set of simultaneous equations in Q unknowns (P, Q)
a solution obtained by setting
 (P - Q) of the variables equal to zero & solving the
remaining P equation in P unknowns is known as a basic
solution.
 The variables which take zero values at any solution are
detained as non-basic variables & remaining are known as-basic
variables, often called basic solution
41
 Important Terms

• Basic feasible solution: A feasible solution to a

general linear programming problem which is
also basic solution is called a basic feasible
solution.

• Optimal feasible solution: Any basic feasible

solution which optimizes (i.e. maximize or
minimizes) the objective function of a LP models
is known as the optimal feasible solution to that
linear programming model.
42
 Important Terms

• Degenerate Solution: A basic solution to the

system of equations is termed as degenerate if
one or more of the basic variables become equal
to zero.

43
 Example
• Rift Valley University Wishes to purchase a maximum of 3600
units of two types of product, A & B are available in the market.
Product A occupies a space of 3 cubic feet & cost Birr 9
whereas B occupies a space of 1 cubic feet & cost Birr 13 per
unit. The budgetary constraints of RVU do not allow spending
more than Birr 39,000. The total availability of space in RVU
good own is 6000 cubic feet. Profit margin of both the product
A & B is Birr 3 & Birr 4 respectively.

44
 Example

• Formulate the above problem as a linear

programming model and solve it by using
graphical method. You are required to ascertain
the best possible combination of purchase of A &
B so that the total profits are maximized.

45
Example: Solution

46
47
48
49
50
Step III Finding feasible region by plotting the graph Always
keep in mind two things: -

51
X2

52
• Step IV. Find the optimal solution by the corner point method. At
corner points (O, A, B, C), find the profit value from the objective
function. Those points which maximize the profit are the optimal
point.

53
In order to get the value of point B apply simultaneous equation by taking the two intersection lines. Solve the point .

54
55
 Simplex Method

• The above limitation of the graphical method is tackled

by what is known as the simplex method.
• Note: The Simplex method starts with a corner that is in
the solution space or feasible region and moves to another
corner, the solution space improving the value of the
objective function each time until optimal solution is
reached at the optimal corner.

56
 Standard forms of Linear Programming (LP) problems

• The use of the simplex method to solve a LP problem requires that

the problem be converted into its standard form.
• The standard form of the LP problem should have the following
characteristics:

All the constraints should be expressed as equations by adding slack

or surplus and/or artificial variables.

The right hand side of each constraint should be made non-negative;

if it is not, this should be done by multiplying both side of the

resulting constraint by -1.

The objective function should be of the maximization type. 57

Standard forms of Linear Programming (LP) problems

58
59
60
61
62
63
The major steps and activities to solve LP model by using simplex
method

i. This method utilizes the property of a LP problem of having

optimal solution only at the corner point of the feasible solution
space. It systematically generates corner point solutions &
evaluates them for optimality. The method stops when an optimal
solution is found. Hence, it is an iterative (repetitive) technique.

• If we get more variables & less equation, we can set extra

variables equal to zero, to obtain a system of equal variables
& equal equations. Such solution is called basic solution.

64
The major steps and activities to solve LP model by using simplex method…

ii. The variables having positive values in a basic feasible

solution are called basic variable while the variables which
are set equal to zero, so as to define a corner point are called
non-basic variables.
iii. Slack variables are the fictitious variables
which indicate how much of a particular
resource remains unused in any solution. These
variables can’t be assigned negative values. A zero
value indicates that all the resources are fully used
up in the production process.
65
The major steps and activities to solve LP model by using simplex method…

66
The major steps and activities to solve LP model by using simplex method…

• The rules used under simplex method, for solving

a linear programming problem are as follows:-
1. Convert the LP to the following form:

• Convert the given problem into Standard

maximization Problem i.e. minimization problem

into a maximization one (by multiplying the

objective function by -1).

67
 The major steps and activities to solve LP model by using simplex method…cont’d

• All variables must be non-negative. All right hand

side values must be non-negative (multiply both

sides by -1, if needed).

• All constraints must be in ≤ form (except the non-

negativity conditions). No strictly equality or ≥

constraints are allowed.

68
The major steps and activities to solve LP model by using simplex method…

69
The major steps and activities to solve LP model by using simplex method …

70
The major steps and activities to solve LP model by using simplex method…

71
The major steps and activities to solve LP model by using
simplex method…cont’d

72
The major steps and activities to solve LP model by using
simplex method…

73
The major steps and activities to solve LP model by
using simplex method…

74
The major steps and activities to solve LP model by
using simplex method…

75
Simplex algorism (Maximization Case)

76
 Example

• Smart Limited manufactures two types of cement

which are sold under the brand name quick and
Tuff. Each product consumes the same raw
materials but in varying proportions. The
following table depicts the amount of raw
materials along with their respective cost.

77
78
 Example.. cont’d

• Quick can be blended @ 1000 kg /hour where as

the blending rate for Tuff is 1250 kg/hour. Their
respective selling prices are Birr. 1010 & Birr 845
You may assume the variable costs to be Birr 500
per hour of plant production time.
• The maximum availability of raw materials is:

79
Formulate as a linear programming model and find
out the optimal units of quick & tuff to be produced
so as to maximize the profits.

80
 Solution
Solution
Step I: List the objective & constraint equations.
Step II: Introduce the slack variables
Step III: Arrange in the form of initial table.
Step IV: Find out the profit-margins from given
sales price.
Step V: Generate solutions.

81
 Solution
The detailed solutions are as under:
Step I :List the objective & constraint equations

82
How to calculate the Profit Margin?

• Late first find the time taken to manufacture 1000Kg of

both types. It is required for allocating variable
production costs to finished product.
∴ 1250 kg Tuff is made in one hour.
∴ 1000 kg of Tuff = 0.8 hr.
∴Variable production cost for Tuff 0.8 x 500 = Rs. 400
∴Variable production cost for Quick Rs. 500 ( ∴ in 1 hr.
1000 kg is made)
83
Solution… cont’d

84
Solution …cont’d

85
Solution …cont’d

86
 Solution …cont’d

Step II Introduce the slack variables:

Slack Variables:
• A slack variable (s) is added to the left hand side
of a < constraint to covert the constraint
inequality in to equality. The value of the slack
variable shows unused resource.
• A slake variable emerges when the LPP (linear
programming problem) is a maximization
problem.
• Thus, they don’t produce any product and their
contribution to profit is zero. 87
 Solution …cont’d
Note:
• In general, whenever there are n variables and m constraints
(excluding the non-negativity), where m is less than n (m<n), n-
m variables must be set equal to zero before the solution can be
solved algebraically.
a. Basic variables are variables with non-zero solution values.
Or: basic variables are variables that are in the basic solution.
Basic variables have 0 values in the row.
b. Non-basic variables are variables with zero solution values.
Or: non-basic variables are variables that are out of the solution.
==>n=5 variables (x1 , x2, s1, s2, and s3) and m=3 constraints (Labor,
machine and marketing constraints), excluding non-negativity.

88
 Solution …cont’d

• Therefore, n-m=5-3=2 variables(x1 and x2) are

set equal to zero in the 1st simplex tableau. These
are non-basic variables. 3 Variables (s1, s2, and s3)
are basic variables (in the 1 st simplex tableau)
because they have non-zero solution values.

89
Solution …cont’d

90
Solution …cont’d

91
Solution …cont’d

92
Solution …cont’d

93
Solution …cont’d

94
Solution …cont’d

95
Solution …cont’d

96
Solution …cont’d

97
Solution …cont’d

98
Solution …cont’d

99
Solution …cont’d

100
Solution …cont’d

101
Solution …cont’d

102
Solution …cont’d

103
104