CHAPETR 2

LINEAR PROGRAMMING

1
Linear Programming
 Linear Programming Problems in math is a system
process of finding a maximum or minimum value
of any variable in a function, it is also known by
the name of optimization problem.
 LPP is helpful in developing and solving a decision
making problem by mathematical techniques.
 The problem is generally given in a linear function
which needs to be optimized subject to a set of
different constraints. Major usage of LPP is in
advising the management to make the most
efficient & effective use of the scarce resources
 Mathematical programming is used to
find the best or optimal solution to a problem
that requires a decision or set of decisions
about how best to use a set of limited
resources to achieve a state goal of objectives
 Linear programming requires that all the
mathematical functions in the model be linear
functions.
Steps involved in mathematical
programming
 Conversion of stated problem into a
mathematical model that abstracts all the
essential elements of the problem.
 Exploration of different solutions of the
problem.
 Finding out the most suitable or optimum
solution
 Parts of the LP Model
1. Decision Variable
 Variables which are changeable & going to impact the
decision function. Like the profit function is effected by
both sales and price, now which one of these two is
changeable, will be our decision variable.
2. Objective Function
 Linear function of the objective, either to Maximize or
minimize, like Maximize Profit, sales, production etc.
and Minimize Cost, Loss, energy, consumption, wastage
etc.
3. Constraints
 Any kind of limitation or scarcity explained through a
function like Limitations of raw materials, time, funds,
equipment etc. Non-Negative Constraints will also be
there which will remain non-negative all the time.
The Linear Programming Model (1)

Let: X1, X2, X3, ………, Xn = decision variables

Z = Objective function or linear function
Requirement: Maximization of the linear function Z.
Z = c1X1 + c2X2 + c3X3 + ………+ cnXn ….. Eq (1)
subject to the following constraints:….. Eq (2)

where aij, bi, and cj are given constants

 The linear programming model can be written in more
efficient notation as
steps to solve linear programming
problems

 Step 1: Identify the decision variables.

 Step 2: Formulate the objective function

 Step 3: Write down the constraints.

 Step 4: Ensure that the decision variables are

greater than or equal to 0.

8
 Application areas

 Product Mix Problem

maximize total income
 Blending Problem
total cost is minimized
 Production Scheduling Problem
 minimize the sum of production & storage costs
 Transportation Problem
total cost of transportation is a minimum
 Flow Capacity Problem
maximum flow or capacity of the network.
A Product Mix Problem
 A manufacturer has fixed amounts of
different resources such as raw material,
labor, and equipment.
 These resources can be combined to
produce any one of several different
products.
 The decision maker wishes to produce
the combination of products that will
maximize total income
A Blending Problem
 Blending problems refer to situations in which a
number of components (or commodities) are
mixed together to yield one or more products.
 Each commodity has known characteristics and
costs
 The problem is to determine how much of each
commodity should be purchased and blended
with the rest so that the characteristics of the
mixture lie within specified bounds and the total
cost is minimized
A Production Scheduling Problem
 A manufacturer knows that he must supply a given
number of items of a certain product each month
for the next n months.
 They can be produced either in regular time,
subject to a maximum each month, or in overtime.
The cost of producing an item during overtime is
greater than during regular time. A storage cost is
associated with each item not sold at the end of
the month
 The problem is to determine the production
schedule that minimizes the sum of production and
storage costs.
A Flow Capacity Problem
One or more commodities (e.g., traffic,
water, information, cash, etc.) are flowing
from one point to another through a
network whose branches have various
constraints and flow capacities.
 The direction of flow in each branch and
the capacity of each branch are known.
 The problem is to determine the
maximum flow, or capacity of the
network
A Transportation Problem
 A product is to be shipped in the amounts al, a2,
..., am from m shipping origins and received in
amounts bl, b2, ..., bn at each of n shipping
destinations.
 The cost of shipping a unit from the ith origin to
the jth destination is known for all combinations
of origins and destinations.
 The problem is to determine the amount to be
shipped from each origin to each destination such
that the total cost of transportation is a minimum.
Formulation of an LP Problem
 Recognize the decision variables and assign
symbols to them like X,Y, Z & so on). Now
these are the quantities we wish to find out
 Express all the constraints in terms of
inequalities in relation the decision variable
 Formulate the objective function in terms of
the decision variables
 Add the non-negativity condition or
constraints.
 Product Mix Problem
The N. Dustrious Company produces two products: I and II.
The raw material requirements, space needed for storage,
production rates, and selling prices for these products.
Production rate for N. Dustrious Company

Product I Product II

Storage space ( m2/unit) 4 5

Raw materials (kg/unit) 5 3
Production rate (units/hr) 60 30
Selling price (Birr/unit) 13 11

The total amount of raw material available per day for both
products is 1575kg. The total storage space for all products is
1500 m2, and a maximum of 7 hours per day can be used for
production
Developing a model
The company has decided that it wants to maximize its sale income,
which depends on the number of units of product I and II that it
produces.
Therefore, the decision variables, x1 and x2 can be the number of units
of products I and II, respectively, produced per day.
The object is to maximize the equation: Z = 13x1 + 11x2
subject to the constraints on storage space, raw materials, and
production time.

Space : 4X1 + 5X2 <=1500

Raw material: 5X1 + 3X2 <=1575
Time: X1 /60 + X2/30<=7 or X1+2 X2<=420
X1, X2>= 0
 The problems of linear programs can be
solved using different methods
Graphical method
Analytical
Matrix
Software
 Graphical method of solving linear
programs are easy to apply if the decision
variables are few usually two.
18
 Important definitions and concepts before
moving on with the Graphical Method

1. Solution: A set of decision variables values which

satisfy all the constraints of an LPP
2. Feasible solution: Any solution which also satisfies the
non-negativity limitations of the problem.
3. Optimal feasible solution: Any feasible solution which
maximizes or minimizes the objective function.
4. Feasible Region: The common region determined by all
the constraints and non-negativity limitations of LPP.
5. Corner point: A point in the feasible region that is the
intersection of two boundary lines
Step 1. Formulate the LPP problems and develop
objective function along with all the constraints function.
Step 2. Graph the feasible region and find the corner
points. The coordinates of the corner points can be
obtained by either inspection or by solving the two
equations of the lines intersecting at that point.
Step 3. Make a table listing the value of the objective
function at each corner point.
Step 4. Determine the optimal solution from the table in
step 3. If the problem is of maximization (minimization)
type, the solution corresponding to the largest (smallest)
value of the objective function is the optimal solution of
the LPP
Graphical Solution to LP Problems
 An equation of the form 4x1 + 5x2 = 1500 defines a
straight line in the x1-x2 plane. An inequality defines an
area bounded by a straight line. Therefore, the region
below and including the line 4x1 + 5x2 = 1500 in the
Figure represents the region defined by 4x1 + 5x2 <=
1500.
 The shaded area of the figure comprises the area
common to all the regions defined by the constraints and
contains all pairs of x1 and x2 that are feasible solutions
to the problem.
 This area is known as the feasible region or feasible
solution space. The optimal solution must lie within this
region.
 There are various pairs of x1 and x2 that satisfy the
constraints such as:
 Trying different solutions, the optimal solution will be:
X1 = 270
X2 = 75
 This indicates that maximum income of $4335 is obtained
by producing 270 units of product I and 75 units of
product II.
 In this solution, all the raw material and available time are
used, because the optimal point lies on the two constraint
lines for these resources.
 However, 1500- [4(270) + 5(75)], or 45 m2 of storage
space, is not used. Thus the storage space is not a constraint
on the optimal solution; that is, more products could be
produced before the company ran out of storage space.
Thus this constraint is said to be slack.
 If the objective function happens to be parallel to one of
the edges of the feasible region, any point along this
edge between the two extreme points may be an
optimal solution that maximizes the objective function.
When this occurs, there is no unique solution, but there
is an infinite number of optimal solutions.
 The graphical method of solution may be extended to a
case in which there are three variables. In this case, each
constraint is represented by a plane in three dimensions,
and the feasible region bounded by these planes is a
polyhedron.
 Example 2
Let us look at this diet problem, A house wife
wishes to mix two types of food F1 and F2 in such
a way that the vitamin contents of the mixture
contain at least 8 units of vitamin A and 11 units of
vitamin B.
Food F1 costs E60/Kg and Food F2 costs E80/kg.
Food F1 contains 3 units/kg of vitamin A and 5
units/kg of vitamin B while Food F2 contains 4
units/kg of vitamin A and 2 units/kg of vitamin B.
Formulate this problem as a linear programming
problem to minimize the cost of the mixtures,
 Food (kg) Requirement
Vitamin content
( units)

F1 F2

Vitamin A (unit /kg) 3 4 8

Vitamin B (unit /kg) 5 2 11

 steps to formulate
 1. The kgs of the F1 and F2 in the mixture are our
decision variables. Suppose the mixture has X Kg of
Food F1 and Y Kg of food F2.
 2. In this example, the constraints are the minimum
requirements of the vitamins. The minimum
requirement of vitamin A is 8 units. Therefore 3X + 4Y
≥ 8. Similarly, the minimum requirement of vitamin B
is 11 units. Therefore, 5X + 2Y ≥ 11
 3. The cost of purchasing 1 Kg of food F1 is E60. The
cost of purchasing 1 Kg of food F2 is E80. The total
cost of purchasing X Kg of food F1 and Y Kg of food
F2 is C = 60X + 80Y, which is the objective function.
 4. The non-negativity conditions are X ≥ 0, Y ≥ 0
The mathematical formulation of the LPP is:
Minimize: C = 60X + 80Y
Subject to: 3X + 4Y ≥ 8
5X + 2Y ≥ 11
X ≥ 0 ,Y ≥ 0

Exercise
Solve using graphical method
 Example 2
Furniture company produces inexpensive tables and chairs.
The production process for each is similar in that both
require a certain number of hours of carpentry work and a
certain number of labor hours in the painting department.
Each table takes 4 hours of carpentry and 2 hours in the
painting department. Each chair requires 3 hours of
carpentry and 1 hour in the painting department. During the
current production period, 240 hours of carpentry time are
available and 100 hours in painting is available. Each table
sold yields a profit of E7; each chair produced is sold for a
E5 profit. Find the best combination of tables and chairs to
manufacture in order to reach the maximum profit.
The decision variables can be defined as X = number of tables to be
produced & Y = number of chairs to be produced.

Now linear programming (LP) problem can be formulated in terms of X and Y

and Profit (P). maximize P = 7X + 5Y (Objective function) subject to 4X + 3Y
≤ 240 (hours of carpentry constraint) 2X + Y ≤ 100 (hours of painting
constraint) X ≥ 0, Y ≥ 0 (Non-negativity constraint).

Therefore the mathematical formulation of the LPP is:

Maximize: P = 7X + 5Y
Subject to: 4X + 3Y ≤ 240
2X + Y ≤ 100
X ≥ 0 ,Y ≥ 0
To find the optimal solution to this LP using the graphical
method we first identify the region of feasible solutions
and the corner points of the of the feasible region
 In this example the corner points are (0,0), (50,0), (30,40)
and (0,80). Testing these corner points on P = 7X + 5Y
gives

Because the point (30,40) produces the highest profit

we conclude that producing 30 tables and 40 chairs will
yield a maximum profit of E410.
 The graphical method is one of the easiest way to solve a small LP
problem. However this is useful only when the decision variables are
not more than two.

 It is not possible to plot the solution on a two-dimensional graph when

there are more than two variables and we must turn to more complex
methods.

 Another limitation of graphical method is that, an incorrect or

inconsistent graph will produce inaccurate answers, so one need to be
very careful while drawing and plotting the graph.

 A very useful method of solving linear programming problems of any

size is the so called Simplex method. We will discuss simplex method
once you are done with the practice on graphical method.
 The Simplex Method
 The graphical method of solving a linear programming
problem can be used when there are only two decision
variables. If the problem has three or more variables, the
graphical method is not suitable. In that case we use the
SIMPLEX METHOD which will be discussed separately in the
next PPT .
 Simplex method is an approach to solving linear
programming models by hand using slack variables, tableaus,
and pivot variables as a means to finding the optimal
solution of an optimization problem.
 Simplex tableau is used to perform row operations on the
linear programming model as well as for checking optimality.
 When decision variables are more than 2, it
is always advisable to use Simplex Method to
avoid lengthy graphical procedure
 The simplex method is not used to examine
all the feasible solutions.
 It deals only with a small and unique set of
feasible solutions, the set of vertex points
(i.e., extreme points) of the convex feasible
space that contains the optimal solution
 Steps involved in Simplex
method
1.Locate an extreme point of the feasible region.

2. Examine each boundary edge intersecting at this

point to see whether movement along any edge
increases the value of the objective function.

3. If the value of the objective function increases along

any edge, move along this edge to the adjacent extreme
point. If several edges indicate improvement, the edge
providing the greatest rate of increase is selected.

4. Repeat steps 2 and 3 until movement along any edge

no longer increases the value of the objective function.
 Example
Product I Product II

Storage space ( m2/unit) 4 5

Raw materials (kg/unit) 5 3

Production rate (units/hr) 60 30

Selling price (Birr/unit) 13 11

The total amount of raw material available per day for both
products is 1575 kg. The total storage space for all products is
1500 m2, and a maximum of 7 hours per day can be used for
production. The company wants to determine how many
units of each product to produce per day to maximize
its total income
 Step 1: Convert all the inequality constraints into
equalities by the use of slack variables. Let
 Introducing these slack variables into the inequality constraints
and rewriting the objective function such that all variables are on
the left-hand side of the equation. Equation 4 can be expressed as:
 Since the coefficients of x1 and x2 in Eq. (A1) are both
negative, the value of Z can be increased by giving either
x1 or x2 some positive value in the solution.
 In Eq. (B1), if x2 = S1 = 0, then x1 = 1500/4 = 375. That
is, there is only sufficient storage space to produce 375
units at product I.
 From Eq. (C1), there is only sufficient raw materials to
produce 1575/5 = 315 units of product I.
 From Eq. (D1), there is only sufficient time to produce
420/1 = 420 units of product I.
 Therefore, considering all three constraints, there is
sufficient resource to produce only 315 units of x1. Thus
the maximum value of x1 is limited by Eq. (C1).
 Step 2: From Equation CI, which limits the maximum
value of x

Substituting this equation into equations yields the

following new formulation of the model
It is now obvious from these equations that the new feasible solution
is:
 x1 = 315, x2 = 0, S1 = 240, S2 = 0, S3 = 105, and Z = 4095
It is also obvious from Eq.(A2) that it is also not the optimum
solution.The coefficient of x1 in the objective function
represented by A2 is negative ( -16/5), which means that the
value of Z can be further increased by giving x2 some positive
value.
Following the same analysis procedure used in step 1, it is clear
that:
In Eq. (B2), if S1 = S2 = 0, then x2 = (5/13)(240) = 92.3.
From Eq. (C2), x2 can take on the value (5/3 )(315) = 525 if x1 = S2 =
0
From Eq. (D2), x2 can take on the value (5/7)(105) = 75 if S2 = S3 = 0
  Therefore, constraint D2 limits the maximum value of
x2 to 75. Thus a new feasible solution includes x2 = 75,
S2 = S3=0

From these equations, the new feasible solution is readily found to be: x1 =
270, x2 = 75, S1 = 45, S2 = 0, S3 = 0, Z = 4335.