CHAPTER TWO

LINEAR PROGRAMMING PROBLEMS

 Chapter Content
2.1 Introduction to linear programming
2.2 Mathematical Model Formulation
2.3 Graphical Solution Method
2.4 The Simplex Solution Method
2.5 Sensitivity Analysis
2.6 Duality in Linear Programming Problems
2.1 Introduction to Linear Programming

 Linear programming is a mathematical technique designed

to aid managers in allocating scarce resources such as
labor, capital, or energy among competing activities.
 It reflects, in the form of a model, the organization's
attempt to achieve some objective;
 Maximizing profit contribution, production capacity,

 Minimizing cots, in view of limited or constrained

resources available such as capital or labor, raw
material, market demand, production process, service
levels, machine time, budgets and storage capacity etc.
 Cont…
 The linear programming technique can be said to
have a linear objective function that is to be
optimized either maximized or minimized, subject to
linear equality or inequality constraints and sign
restrictions on the variables.
 The term linear describes the proportionate
relationship of two or more variables.
A given change in one variable will always cause a
resulting proportional change in another variable.
 Properties of LPP
 Any linear programming model (problem) must
have the following properties:
1.There must be linear relationship between
variables and constraints
2. The model must have an objective function
3. The model must have structural constraints
4. The model must have non-negativity constraint
 Assumptions of LPP
There are four basic assumptions of LP models.
i) Linearity: requirement is that each decision variable has a
linear impact on the objective function and in each constraint
ii) Divisibility: pertains to potential values of decision
variables can assume non-integer values are acceptable.
iii) Certainty: requirement involves two aspects of LP models,
one aspect relates to the model parameters (i.e., numerical
value). It is assumed that those values are known and constant. It
is the assumption that all relevant constraints have been
identified and represented in the model
iv) Non-negativity
Application of Linear Programming

 Can be used for many Managerial Decisions:

1. Product mix
2. Make or buy decision
3. Media selection
4. Marketing research
5. Portfolio selection
6. Shipping & transportation
7. Multi-period scheduling
2.2 Mathematical Model
Formulation
 Components of LP Model
1. Objective and Objective Function - a single, quantifiable
objective must be specified by the decision maker
 Maximization
 Minimization
2. Decision Variables - unknown quantities to be solved for
3. Constraints - restrictions or limits coming from a variety of sources
System constraints – involve more than one decision variable
Individual constraints – involve only one variable

 Non-negativity constraints – specify that no variable will be allowed

to take on a negative value
4. Parameters – are numerical values in objective function and
constraints
LP Model Example
 Steps in Model Formulation
 Steps for Formulating the LP Model
1. Identify the unknown decision variables to be
determined and assign symbols to them.
2. Identify the objective or aim and represent it also as
a linear function of decision variables.
3. Identify all the restrictions or constraints in the
problem and express them as linear equations or
inequalities of decision variables.
 Example 1.
 A firm manufactures two products A & B on which
the profits earned per unit are Birr 3 & 4
respectively. Each product is processed on two
machines M1 & M2. Product A requires one minute
of processing time on M1 and two minute on M2,
while product B requires one minute in M1 and one
minute on M2. Machine M1 is available for not
more than 7:30 hours and M2 is available for 10
hours, during any working day.
 Formulate the mathematical LP model that will determine
the optimal production quantities for profit maximization
 Example 2.
 A firm produces three products. These products
are processed on three different machines. The
time required manufacturing one unit of the
three products and the daily capacity of the
three machines are given in the next table.
 The profit per unit for product 1, 2 & 3 is Birr 4, 3 &
6 respectively.
 Formulate the mathematical LP model that will
determine the daily optimal production quantities for
profit maximization.
 Cont…

Time per unit (minutes) Machine

Machine capacity
Product 1 Product 2 Product 3 (minutes)

M1 2 3 2 440

M2 4 - 3 470

M3 2 5 - 430
 Example 3.
A toy manufacturer makes three versions of a toy robot.
The first version requires 10 minutes for fabrication and 2
pound of plastic, the second version requires 12 minutes for
fabrication and 3 pounds of plastic, and the 3rd version
requires 15 minutes for fabrication and 4 pounds of plastic.
There are 8 hours of fabrication time available and 200
pounds of plastic available for the next production cycle.
The unit profits are Birr 12 for each version 1, Birr 60 for
each version 2, and Birr 72 for each version 3. A minimum
of 10 units of each robot must be made to fill backorder.
 Formulate an LP model that will determine the optimal
production quantities for profit maximization.
 Example 4.
The agriculture research institute suggested to a farmer
to spread out at least 4800kg of a special phosphate
fertilizer and not less than 7200kg of a special nitrogen
fertilizer to raise productivity of crops in his field. There
are two sources for obtaining these- mixtures A and B.
both of these are available in bags weighing 100kg
each and they cost birr 40 and birr 24 respectively.
Mixture A contains phosphate and nitrogen equivalent
of 20kg and 80kg respectively, while mixture B
contains these ingredients equivalent of 50kg each.
Formulate an LP model.
 Example 5
The orient manufacturing company produces three
type of typewriters Tik-Tik, Mik-Mik, Pik-Pik. All the
three types are required first to be machined and
then to be assembled. The total available machine
time and assembly times are, respectively, 4000
and 1240 hours per month. The time requirements
for the various types and the data regarding selling
price and costs for the three are on the next slide.
 Formulate the mathematical LP model that may help us
to determine the optimal production quantities for profit
maximization.
 Cont…

Type Machine time assembly time

(in hours) (in hours)
Tik-Tik 15 4.4
Mik-Mik 13 3.5
Pik-Pik 12 4.0

Tik-Tik Mik-Mik Pik-pik

Selling price 11000 5000 3000
Cost 8000 2400 1500
 Example 6
ABC Company is investigating the possibility of
introducing a new cereal. It would be composed
of wheat, rice, and cornflakes. The cost per
ounce and dietary requirements are shown in the
following table.
 Cont…
Wheat Rice Corn Requirement per
oz box
Protein (g.per oz) 4 2 2 At least 27g
Carbohydrate (g per oz) 20 25 21 At least 240g
Calories (g per oz) 90 110 100 No more than
1260 calories
Cost per oz $.03 $.03 $.02

Formulate an LPM that will determine the optimal

quantities of wheat, rice and corn per box that will
achieve the requirement at minimum cost.
2.3 Graphical Solution Method
 Considerations in Graphical Solution
Method
 In graphical method:
 The inequalities (structural constraints) are considered to
be equations. This is because; one cannot draw a graph
for inequality.
 Only two variable problems are considered, because we
can draw straight lines in two-dimensional plane (X-1
axis and X-2 axis).
 More over as we have non negativity constraint in the
problem that is all the decision variables must have
positive values always the solution to the problem lies in
first quadrant of the graph.
 Cont…
 This method consists of the following steps:
 Formulate the mathematical model for the given
problem.
 Convert the constraints given in the form inequality to
that of equality.
 Draw the x and y intercepts.

 Plot each of the constraints on the graph.

 Identify the feasible (solution) region.

 Techniques of Graphical Method
 Corner (extreme) point method: this method includes
the following steps.
 Identify each of the extreme points of the feasible
region.
 Find the values of objective function at each extreme
point.
 The optimal solution occurs at that corner point which
maximizes objective function in case of maximization
problem.
 The optimal solution occurs at that corner point which
minimizes objective function in case of minimization
problem.
 1. Maximization Problem
Example: a microcomputer firm is about to start production of two
new microcomputers, X1 and X2. The manager wants to determine
how much of each computer to produce in order to maximize the
profit generated by selling them.
Resources Amount Available
Assembly time 100 hours
Inspection time 22 hours
Storage space 39 cubic feet
Type 1 Type 2
Profit per unit $60 $50
Assembly time per unit 4 hours 10 hours
Inspection time per unit 2 hours 1 hour
Storage space per unit 3 cubic feet 3 cubic feet
 1. Maximization Problem
 The model is:
 Maximize Z= 60X1 + 50X2
 Subject to: Assembly 4 X 1 +10 X 2 < 100 hours
Inspection 2 X 1 + 1 X 2 < 22 hours
Storage 3 X 1 + 3 X 2 < 39 cubic feet
Where; X1, X2 > 0
 Required: Solve the problem using graphic method
 Interpret the result
 Check resource consumption (availability of slack)
Cont…
Cont.….
Corner Coordinate Point Value of Objective Function
Point (X1, X2) (Z=60X1 + 50X2)
a (0, 10) 60(0) + 50(10) = 500
b (5, 8) 60(5) + 50(8) = 700
c (9, 4) 60(9) + 50(4) = 740
d (11, 0) 60(11) + 50(0) = 660
Interpretation:
 For a firm to maximize its profit (740), it should produce 9
units of the Model I microcomputer and 4 units of model II.
Checking resource consumption (availability of slack)
 (4*9) + (10*4) = 76 assembly hours
 (2*9) + (1*4) = 22 inspection hours
 (3*9) + (3*4) = 39 cubic storage space
 1. Maximization Problem
A company manufactures two types of boxes, corrugated and
ordinary cartons. The boxes undergo two major processes:
cutting and pinning operations. The profits per unit are Br. 6
and Br. 4 respectively. Each corrugated box requires 2
minutes for cutting and 3 minutes for pinning operation,
whereas each carton box requires 2 minutes for cutting and 1
minute for pinning. The available operating time is 120
minutes and 90 minutes for cutting and pinning machines.
Required: Determine the optimum quantities
Interpret the result
Check if there is any slack/unused resource
 2. Minimization Problem
Example 1:
 A person requires at least 10, 12, and 12 units of
chemicals A, B and C respectively for his garden. A
liquid product contains 5, 2 and 1 units of A, B and C
respectively per jar. A dry product contains 1, 2 and 4
units of A, B and C per carton. If the liquid product
sells for Br.3 per jar and the dry product sells for Br.2
per carton,
 How many of each should be purchased, in order to
minimize the cost and meet the requirements?
 2. Minimization Problem
Example 1:
 Suppose that a machine shop has two different
types of machines; machine 1 and machine 2, which
can be used to make a single product. These
machines vary in the amount of product produced
per hr. and the amount of labor used and in the cost
of operation. Assume that at least a certain amount
of product must be produced and that we would
like to minimize at least the regular labor force.
 For How many hours should we utilize each
machine in order to minimize total costs and still
meets the requirement?
2. Minimization Problem
 2. Minimization Problem
 Example 2:
 Min. Z = 0.1X+0.07Y

 Subject to:

6X+2Y > 18
8X+10Y > 40
Y>1
 Where; X, Y > 0
 Find the values of X and Y which makes the
objective function minimum.
 Cont…
Solution:
 The coordinates of corner point’s feasible region are:
 A = (0, 9), B = (2.27, 2.18), C = (3.75, 1)
 Compute objective function value at each corner point
of the feasible region.
Corner point coordinates(x1, x2) Z = 0.1x1+0.07x2
A (0, 9) (0.1x 0) + (0.07 x 9) =0.63
B (2.27, 2.18) (0.1 x 2.27) + (0.07 x2.18) =0.38
C (3.75, 1) (0.1 x 3.75) + (0.07 x 1) = 0.445
Exercise
A company owns two flour mills (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.
Required:
How many days per week should each mill be operated in
order to meet the contract order most economically? Solve
graphically.
Exercise - Mix of Constraints

ABC Gasoline Company has two refineries with different

production capacities. Refinery A can produce 4,000 gallons
per day of SUPER UNLEADED GASOLINE, 2,000 gallons per
day of REGULAR UNLEADED GASOLINE and 1,000 gallons
per day of LEADED GASOLINE. On the other hand, refinery B
can produce 1,000 gallons per day of SUPER UNLEADED,
3,000 gallons per day of REGULAR UNLEADED and 4,000
gallons per day of LEADED. The company has made a contract
with an automobile manufacturer to provide 24,000 gallons of
SUPER UNLEADED, 42,000 gallons of REGULAR UNLEADED
and 36,000 gallons of LEADED. The automobile manufacturer
wants delivery from each refinery in not more than 14 days.
The cost of running refinery A is $1500 per day and refinery
Exercise Cont…
Required:
a. Formulate this problem as a LPP.
b. Determine the number of days the gasoline company
should operate each refinery in order to meet the terms
of the above contract most economically (i.e. At a
minimum running cost)
c. Which grade of gasoline would be over produced?
Graphical Solutions for the
Special Cases of LP
 i) Unboundedness

 Example:
Max Z = 10X1 + 20X2
Subject to 2X1 + 4X2 > 16
X1 + 5X2 > 15
X1, X2 > 0
The reason for it may be concluded to be wrong
formulation of the problem such as incorrectly
maximizing instead of minimizing and/or errors in the
given problem.
Checking equalities or rethinking the problem statement
will resolve the problem.
 Cont…

The shaded area represents the set of all feasible solutions

and as can be seen from the graph, the solution is
unbounded.
 ii) Infeasibility

 Infeasibility is a condition that arises when no value of

the variables satisfy all the constraints simultaneously.
 Such a problem arises due to wrong model formulation
with conflicting constraints
 Example:
Max Z = 3X1+2X2
Subject to: 2X1 + X2 < 2
3X1 + 4X2 > 12
X1, X2 > 0
Cont…
 iii) Multiple Optimal Solutions

 Example:
Max Z = 8X1+16X2
Subject to: X1 + X2 < 200 ……. C1
3X1 + 6X2 < 900 ……. C2
X2 < 125 ……. C3
X1, X2 > 0
 Cont..

 The objective function assumes its maximum value of

2,400 at two corner points;
 B (50,125) and C (100,100).
Therefore, the optimal solution is found on the line segment
connecting the two corner points.
 Important terms of Solutions in LPP

 Solutions: are values of decisions variable of linear programming

model
 A feasible solution is a solution for which all the constraints are
satisfied.
 An infeasible solution is a solution for which at least one constraint is
violated.
 The feasible region is the collection of all feasible solutions.
 An optimal solution is a feasible solution that has the most favorable
value of the objective function. The most favorable value is;
 the largest value if the objective function is to be maximized,
 whereas it is the smallest value if the objective function is to be
minimized.
 Slack Versus Surplus

Slack:
 Slack is the amount of a scarce resource that is unused
by a given solution. Slack can potentially exist in a <
constraint. Slack variables are considered in the
objective function by using a coefficient of zero for
each of them. When all the constraints are written as
equalities after adding a slack variable to each of
them, the linear program is said to be in standard form.
For example, in the Assembly constraint 4X1 +10X2 <
100 hrs, the slack value is 100 – [4(9) +10(4)] = 24.
 Cont…
 Surplus: on the other hand 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, i.e., substitute the
optimal 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
should also be accounted for in the objective
function by using coefficients of zero like wise.
2.4 THE SIMPLEX SOLUTION METHOD
 Steps in Simplex Method
1. Write the Problem in Standard Form
 Characteristics:
 All constraints are expressed in the form of equalities or
equations.
 All right hand sides are non-negative
 All variables are non-negative
 Standardization/Tableau Form/:
Types of constraint Standard form
≤ Add a slack variable
= Add an artificial variable
≥ Subtract a surplus variable
and add an artificial variable
 Cont…
2. Develop an Initial Simplex Tableau
 Steps in developing initial simplex tableau:
I. List the variables in the model across the top of the
tableau
II. Next fill-in the parameters of the model in the
appropriate rows and columns
III. Add two columns to the left side of the tableau.
The first column is a list of variables called Basis.
IV. The C at the top column indicates that the values in
that column and the values in that row are
objective function coefficients.
 Cont…
V. The last column at the right is called the quantity
column. It refers to the right hand side values (RHS)
of the constraints.
VI. There are two more rows at the bottom of the
tableau. The first raw is a Z-row. For each column
the Z – value is obtained by multiplying each of the
number of the column by their respective row
coefficient in column C.
VII. The last raw is Cj-Z row. The values in this row are
also calculated column by column. For each Column,
the value in row Z is subtracted form the C value in
the top row.
 Cont…
3. Determining the Entering Variable:
 For a maximization problem; the entering variable is identified
as the one which has the largest positive value in Cj-Z row.
 This column corresponding to the entering variable is called
pivot column.
 In a minimization problem, the entering variable is the one
which has the largest negative Cj-Z row value in the simplex
tableau.
4. Determining the Leaving Variable:
 The leaving variable is identified as the one with the smallest
non-negativity ratio for quantity divided by respective positive
pivot columnar entries.
 The row of the leaving variable is pivot row.
 Cont...

5. Drive the Revised Tableau for Improved

Solution
A. Divide each element of the pivot row (including
quantity) by the pivot element to get the
corresponding value in the new tableau. The
divided raw values is called the replacement
row.
B. For each raw other than the pivot raw;
 New row element = old row element – (row
element in pivot column X corresponding
replacement row elements)
 Cont…
6. Check for Optimality
 Remark:
 A simplex solution for a maximization problem is
optimal if and only if cj – z row contains only zeros
and negative value (i.e. if there are no positive
values in the cj – z row).
 The simplex solution for a minimization problem is
optimal if Cj-Z row contains only zero and positive
values (Cj-Z ≥ 0).
Note: if the solution is not optimal the steps will be
repeated again and again until the optimal solution is
obtained!
 1. Maximization Problems
Example: Solve the problem using simplex method.
 Max Z = 60X1+50X2

 Subject to: 4X1+10X2 ≤100

2X1+ X2 ≤ 22
3X1+ 3X2 ≤ 39
 Where; X1, X2 > = 0
 1. Maximization Problems
A Juice Company has available two kinds of food Juices: Orange Juice
and Grape Juice. The company produces two types of punches: Punch A
and Punch B. One bottle of punch A requires 20 liters of Orange Juice
and 5 liters of Grape Juice. One Bottle of punch B requires 10 liters of
Orange Juice and 15 liters of Grape Juice. From each of bottle of
Punch A, a profit of $4 is made and from each bottle of Punch B, a
profit of $3 is made. Suppose that the company has 230 liters of
Orange Juice and 120 liters of Grape Juice available.
Required:
a. Formulate this problem as a LPP (2%)
b. How many bottles of Punch A and Punch B the company should
produce in order to maximize profit? (Using the simplex method) (5%)
c. What is this maximum profit and interpret the result? (1%)
 2. Minimization Problems
 The Big-M Method is a technique, which is used in
removing artificial variables from the basis
 In this method; we assign coefficients to artificial
variables, undesirable from the objective function
point of view
 If objective function Z is to be minimized, then a very
large positive price (called penalty) is assigned to
each artificial variable
 Example
 Minimize Z = 7X1+9X2
 Subject to 3X1+6X2 >= 36
8X1+4X2 > = 64
Where; X1, X2 > = 0
Step 1: Write in Standard Form
 We subtract surplus and add artificial variables into both
constraints and write as follows
Minimize Z = 7X1+9X + 0S1+0S2+MA1+MA2
Subject to 3X1+6X - S1 + A1= 36
8X1+4X2 –S2+A2 = 64
X1, X2 > = 0
 Step 2: Initial Tableau

Basic V. Cj 7 9 0 0 M M

Quantity
X1 X2 S1 S2 A1 A2

M A1 3 6 -1 0 1 0 36

M A2 8 4 0 -1 0 1 64

Zj 11M 10M -M -M M M
100M
Cj-Zj 7-11M 9-10M M M 0 0
 Step 3: Determine the Entering and
Leaving Variables
 The entering variable is identified as the one
which has the largest negative Cj-Z row value in
the simplex tableau
 The leaving variable is the smallest positive ratio
in quantity column
 The artificial variables in a minimization problem
will be expressed in the objective function with a
large positive coefficient so that they are quickly
eliminated as we proceed with the solution
Step 4: Develop Second Tableau

Cj 7 9 0 0 M
Basic V. X1 X2 S1 S2 A1 Quantity
A1 M 0 9/2 -1 3/8 1 12
X1 7 1 ½ 0 -1/8 0 8
Zj 7 7/2+9/2M -M 3/8M-7/8 M 56+12M
Cj-Zj 0 11/2-9/2M M 7/8-3/8M 0
Step 5: Develop Third Tableau

Cj 7 9 0 0
Basic V. X1 X2 S1 S2 Quantity
X2 9 0 1 -2/9 1/12 8/3
X1 7 1 0 1/9 -1/6 20/3
Zj 7 9 -11/9 -5/12 212/3
Cj-Zj 0 0 11/9 5/12
 Step 6: Check of Optimality
 The third tableau represents a final tableau since
it is the optimal solution with entirely zeros and
non-negative values in the Cj-Zj row

 Therefore, the optimal solution is: X1 = 20/3

and X2 = 8/3 and value of objective function
is 212/3
 Summary of Extra Variables
Coefficient of Extra Variables Presence of
Types of in the Objective Function variables in the
Extra Variables to be Initial Solution Mix
Constraint
added
Max Z Min Z
<= Add only slack variable (S) 0 0 Yes
>= Subtract surplus variable 0 0 No
(S) and add artificial
variable (A) -M +M Yes
= Add artificial variable (A) -M +M Yes