CHAPTER TWO

2. LINEAR PROGRAMMING PROBLEM AND MODELS (LPPM)

2.1. Meaning and Definition
LPP is a model, which is used for optimum allocation of scarce or limited resources to competing
products or activities under such assumptions as certainty, linearity, fixed technology, and constant profit
per unit, is linear programming.
The restrictions may be imposed internally or externally.
i. Internal restrictions are:
The amount of raw materials, availability of labor time, machine time, technical requirements and budgets
that a department has to produce its products
ii. External restrictions are:
Labor regulations (e.g. safety equipment, training requirements overtime) that limit the options open to
decision maker.
It is the mathematical representation of LP problems that has been developed to help management in
decision making, involving the efficient allocation of scarce resources to achieve an optimization
objective.
Scares Resource
To beallocated to: Objectives Optimization

Subject to Maximization Minimization

Constraints

Non-negativity Resource
Constraints constraints
Figure 2.1. The linear programming problem/model
2..2. Components of LP models
A. Objective Function
 is the goal or objective of a management, stated as intent to maximize or to minimize some
important quantity such as profits or costs.
B. Decision Variables
 Represent the unknown values to be solved by the decision makers.
 Are the variables whose values are unknown and are searched
C. Parameters:
 Are fixed values that specify the impact of one unit on the objective function and the constraint.
D. Constraints
 Are limitations or restrictions imposed by the problems? It includes:
 Resource constraints: are restrictions that should be clearly identifiable and measurable in
quantitative terms, which arise from limitation of available resources.
Examples of limited resources are:
 Plant capacity
 Raw materials availability
 Labor power
 Market demand, etc
 Individual constraints: are constraints which are subject to individual decision variables.
 Non-negativity constraints: are constraints that require the decision variables not to take on
negative values.
Generally speaking, a constraint consists of four elements. These are:
I. A right hand side value (RHS): represents quantity that specifies the limit for that
constraint. It must be a constant, not a variable.
II. An algebraic sign: represents whether the limit is:
 An upper bound (< )that cannot be exceeded
 A lower bound (> )that is the lowest acceptable limit
 An equality (=) that must be met exactly.
III. The decision variable: to which the constraint applies.
IV. Parameters: The impact that one unit of each decision variable will have on the right hand
side quantity of the constraint.
2.3.3. Assumptions of LPP models
The following are some important assumptions made in formulating a linear programming model:
A. Linearity
 The Objective Function and the constraints must be linear in nature in order to deal with a Linear
Programming Problems (LPP). Here the term linearity implies proportionality and additively .
B. Certainty
 It is assumed that the decision maker here is completely certain (i.e., deterministic conditions)
regarding all aspects of the situation, i.e., availability of resources, profit contribution of the
Products, technology, courses of action and their consequences etc.
C. Divisibility
 It is assumed that the decision variables are continuous. It means that companies manufacture
products in fractional units. For example, a company manufactures 2.5 vehicles, 3.2 barrels of oil
etc.
D. Non- Negativity
  Indicate all variables are restricted to non-negative values (i.e., their numerical value will be ≥
0).i.e. negative values of variables are unrealistic or meaningless.
2.4. FORMULATION OF LPPM
Formulating linear programming problem models involves the following steps
1. Identify the decision variables and represent them in terms of X1, X 2…..
2. Determine the objective function:
 First decide whether the problem is maximization or minimization problem.
 Second identify the coefficients of each decision variable.
 If the problem is a maximization problem, the profit per unit for each variable must be
determined.
 If the problem is a minimization problem the cost per unit must be determined.
 Make sure the units of measurements of all coefficients in the objective functions must be
the same.
3. Identify the constraints
 First, express each constraint in words.
 Second identify the coefficients of the decision variables in the constraints; and the RHS
values of the constraints.
 Determine the limits for the constraints i.e. see whether the constraint is of the form (<),
(>) or (=).
 Write the equation.
4. Using the above information (step 1 to 3), build the model.

Note

 The coefficients of the variables in the Objective Function are called the
profit or cost coefficients. They express the rate at which the value of the
Objective Function increases or decreases by including in the solution
one unit of each of the decision variables.
 The coefficients of the constraints’ variables are called the input- output
coefficients that indicate the rate at which the given resources are
depleted or utilized.
Example 1
 A firm that assembles computers and computer equipment is about to start production two new
microcomputers. Each type of microcomputers will require assembly time, inspection time and
storage space. The amount of each of these resources that can be devoted to the production of
these microcomputers is limited. The manager of the firm would like to determine the quantity
 of each microcomputer to produce in order to maximize the profit generated by sales of these
microcomputers.
Additional information
 In order to develop a suitable model of the problem, the manager has met with design and
manufacturing personnel. As a result of these meetings the manager has obtained the following
information.

TYPE ONE TYPE TWO

Profit per unit Birr 60 Birr 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

The manager has also acquired information on the availability of company resources. These weekly
resources are:

RESOURCE AMOUNTS AVAILABLE

Assembly time 100 hours
Inspection time 22 hours
Storage space 39 cubic feet

 The manager also met with the firm’s marketing manager and learned that demand for the
microcomputers was such that what ever combination of these two types of microcomputers is
produced, all of the outputs can be sold.
Required:
 Formulate the LPPM of the problem.
Solution
Step 1: identify the decision variable
 the quantity/ amount/ units of each microcomputer( microcomputer type 1 and
microcomputer type 2) to be produced

Let x1= represent quantity of microcomputer type 1 to be produced

x2= represent quantity of microcomputer type 2 to be produced
Step 2: Identify the objective function
 The problem is maximization problem, as indicated in the problem (5 th line of the problem)
  To write the equation both the objective function and the constraints summarize the given
information in tabular form accordingly

RESOURCE TYPE ONE TYPE TWO AVAILABILITY

Assembly time per unit 4 hours 10 hours 100 hours
Inspection time per unit 2 hours 1 hour 22 hour
Storage space per unit 3 cubic feet 3 cubic feet 39 cubic feet
Profit per unit Birr 60 Birr 50

Hence, the objective function is

 Max Z = 60x1 + 50 x2
Step 3: identify each constraints and write the equation
 Assembly time 4x1 + 10x2< 100
 Inspection time 2x1 + x2< 22
 Storage space 3x1+ 3x2 < 39
 Non negativity constraint x1 & x2 > 0
Step 4: write the summarized form of the model
In summary, the mathematical model of the
microcomputer problem is:
Max Z= 60x1 + 50x2
Subject to
4x1 + 10x2< 100
2x1 + x2< 22
3x1+ 3x2 < 39
x 1 & x2 > 0

Example 2
A firm is engaged in breeding pigs. The pigs are feed on various products grown on the farm. In
view of the need to ensure certain nutrient constituents (call them vitamins, minerals and
proteins) it is necessary to buy two additional products say A and B. One unit of product A
contains 36 units of vitamins, 3 units of minerals and 20 units of proteins. One units of product B
contains 6 units of vitamins, 12 units of minerals and 10 units of proteins. The minimum
requirement of vitamins, minerals and proteins is 108units, 36units and 100 units respectively.
Product A costs birr 20 per unit and product B costs birr 40 per unit
Required
Formulate the LPPM of the problem
Solution
Step 1: identify the decision variables
  Product A and B to be purchased to prepare the food for pigs
Let x1 represent product A to be purchased
X2 represent products B to be purchased
Step 2: identify the objective function
 The problem is a minimization problem, so the equation;
Min Z = 20x1 + 40 x2
 we can put the information in a tabular form as follows
NUTRIENT
CONSTITUENTS PRODUCT A PRODUCT B REQUIREMENT
Vitamins 36 units 6 units 108 units
Minerals 3 units 12 units 36 units
Proteins 20 units 10 units 100 units
Cost per unit Birr 20 Birr 40
Step 3: identify each constraints and write the equation
 Vitamins 36x1 + 6x2> 108
 Minerals 3x1 +12 x2> 36
 Proteins 20x1+ 10x2 >100
 Non negativity constraint x1 & x2 > 0
Step 4: write the summarized form of the model

In summary, the mathematical model of the problem is:

Min Z=20x1 + 40x2
Subject to
36x1 + 6x2> 108
3x1 +12 x2> 36
20x1+ 10x2 >100
x 1 & x2 > 0

2.5. APPROACHES TO SOLVE LPPM

There are two methods used to solve LP problems
1. Graphical methods
2. Simplex methods
2.5.1. Graphical methods
 Is used to find solutions for LPP when the decision variables of the problem are not greater
than two.

Note: Graphical LP is a two-dimensional model

Procedure
To apply this method, we should follow the following steps.
1. Draw a graph including all the constraints
2. Identify the feasible solution region
3. Identify the corner points and their respective coordinates
 4. Evaluate the objective function at each corner point and obtain a point on the feasible
region that optimizes the objective function-optimal solution
5. Interpret the results
Example 1
Consider the microcomputer problem formulated above and solve it using the graphical
approach.
Step one: Graph each constraints:
 To draw the graph first change the inequality to equality i.e. replace the < and > sign into =
sign.
Max Z=60x1 + 50x2
Subject to
36x1 + 6x2> 100 36x1 + 6x2= 100
3x1 +12 x2> 22 3x1 +12 x2= 22
20x1+ 10x2 >39 20x1+ 10x2 =39
x1 & x2 > 0 x1 & x2 = 0
 Then find the x and y intercepts (in our case x 1 and x2 respectively) - points where each
constraint intersects the axis. To do so, set x 1 = 0 to find values for x 2 and set x2= 0 to find
values for x1.
For the first constraint:
4x1 + 10x2 = 100 4x1 + 10x2 = 100
4(0) + 10 x2 = 100 4x1 + 10(0) = 100
10x2= 100 4x1= 100
X2= 10 x1 = 25
The x1 and x2 intercepts are (0, 10) (25, 0). Similarly calculate for the second and third constraints.
For the second constraint the intercepts are (0, 22) (11, 10)
For the third constraint the intercepts are (0, 13) (13, 0)
Graph the constraints using the intercepts calculated above. The graph is:
  As indicated in the graph, the corner points of the feasible region (the corner points of the
shaded region) are A, B, C, D and E. The next task is to find the coordinates of these corner
points, some are determined by observation and some are through simultaneous equation.
Then we test each corner points to find the points that results the optimal solution. These
activities are indicated in the following table.

Evaluating the corner points

Point Coordinates How determined Value of the objective function
X1 X2 Max Z=60x1 + 50x2
A 0 0 Inspection 60(0) + 50(0) = 0
B 11 0 Inspection 60(11) + 50(0) =660
C 9 4 Simultaneous equation 60(9) + 50(4) =740
D 5 8 Simultaneous equation 60(5) + 50(8) =700
E 0 10 Inspection 60(0) + 50(10)=500

Since the maximum value (because the objective function of the problem is maximization) is 740, the
solution is:
X1= 9, X2= 4 and The Maximum Profit is Birr 740.
When we interpret the result, we state the company should produce 9 units of microcomputer type one
and 4 units of microcomputer type two to get a maximum profit of Birr 740.
Example 2
Max .Z=50 X 1 +80 X 2
St :
X 1 +2 X 2 ≤32
X 1 +2 X 2 ≤82
X 1 , X 2≥0
Note: Try to solve the problem by yourself, in separate piece of paper before you check the
answer.

Example 3
 Consider two models of color TV sets; Model A and B, are produced by a company to maximize
profit. The profit realized is $300 from a TV set of model A, and $250 from that of set B. The
limitations are:
A. availability of only 40hrs of labor each day in the production department
B. a daily availability of only 45 hrs on machine time
C. ability to sale 12 set of model A

Required
How many sets of each model will be produced each day so that the total profit will be as large as
possible?

Resources used per unit

Constraints Model A Model B Maximum Available hrs.
(X1) (X2)
Labor hr. 2 1 40

Machine hr. 1 3 45
Marketing hr. 1 0 12

Profit $300 $250

Note: Try to solve the problem by yourself, in separate piece of paper before you check
the answer.
Solution
1. Formulation of mathematical modeling of LPP
Max Z=300X1 +250X2
St:
2X1 +X2< 40
X1 +3X2< 45
LPP Model
X1 < 12
X1, X2 > 0

2. Convert constraints inequalities into equalities

2X1 +X2 = 40
X1 +3X2= 45
X1 = 12
3. Draw the graph by intercepts
2X1 +X2 = 40 ==> (0, 40) and (20, 0)
X1 +3X2= 45==> (0, 15) and (45, 0)
X1 = 12==> (12, 0)
X1, X2 >0
2X1 +X2 =40

X2
X 1=0
40 X 1=12
 X1 +X2 =
4. Identify the feasible area of the solution which satisfies all constrains.
5. Identify the corner points in the feasible region
A (0, 0), B (0, 15), C (12, 11) and D (12, 0)
6, Identify the optimal solution point
Corners Coordinates Max Z=300 X1 +250X2
A (0, 0) $0
B (0, 15) $3750
C (12, 11) $6350
D (12, 0) $3600
Interpretation
12 units of product A and 11 units of product B should be produced so that the total
profit will be $6350
Example 4
A manufacturer of light weight mountain tents makes two types of tents, REGULAR tent and
SUPER tent. Each REGULAR tent requires 1 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 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?
Solution
_________________________________________________________
Labor hours per tent
Department REGULAR (X1) SUPER(X2) Maximum labor-hours
available per week
___________________________________________________________________
Cutting department 1 2 32
Assembly department 3 4 84
Selling price per tent $160 $210
Cost per tent $110 $130
Profit per tent $50 $80

 The distributor will not take more than 12 SUPER tents per week. Thus, the manufacturer
should not produce more than 12 SUPER tents per week.
Decision variable: number of regular and super tent to be produced per week.
Let X1 =The No of REGULAR tents produced per week.
X2 =The No of SUPER tents produced per week.
X1 and X2 are called the decision variables
Max . Z=50 X 1 +80 X 2
St : ……….Cutting department constraint
X 1 +2 X 2 ≤32
……….Assembly department constraint
X 1 +4 X 2 ≤82
X 2≤12
……….Demand constraint
LPP Model
X 1 , X 2≥0
Corners Coordinates Max Z=50 X1 +800X2
A (0, 0) $0
B (0, 12) $960
C (8, 12) $1360
D (20, 6) $1480

E (28, 0) $1400
Interpretation
The manufacturer should produce and sale 20 REGULAR tents and 6 SUPERS tents to get a
maximum weekly profit of $1480.
Example 5
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 machine vary in the amount of product
produced per hr., in 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 utilize at least the regular
labor force. How much should we utilize each machine in order to utilize total costs and still
meets the requirement?
Solution: The key information inputs in the problem are provided as follows
_______________________________________________________________
Resource used

Machine 1 (X1) Machine (X2) Minimum required hours

 _________________________________________________________________________
Product produced/hr 20 15 100
Labor/hr 2 3 15______
Operation Cost $25 $30____________________________________
The problem is formulated in the next model
Min. Z=25 X 1 +30 X 2
St :
20 X 1 +15 X 2 ≥100 LPP Model

2 X 1 +3 X 2 ≥15
X 1 , X 2≥0
Constraint equation:
20X1 +15X2=100 ==> (0, 20/3) and (5, 0)
2X1+3X2=15 ==> (0, 5) and (7.5, 0)
X1 X2> 0
The feasible solution space and the corner points are specified on the graph below

X2
X 1 =0
A (0, 20/3)

FeasibleRegion

B (2.5, 3.33)
X 2 =0

X1
___________________________________________________________________________________________
5 C (7.5, 0)
Corners Coordinates MinZ=25 X1 + 30X2

A (0, 20/3) 200

B (2.5, 3.33) 162.5
C (7.5, 0) 187.5
_____________________________________________________________

The optimal solution mix is represented by X1 =2.5, X2=3.33, and Min Z= 162.5
Example 6
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 standardize? Solve graphically.
Solution
No of days per week of Minimum flour in
Mil A (X1) Mill B(X2) quintals
HIGH Capacity (in quintal) 6 2 12
MEDIUM Capacity (in quintal) 2 2 8
LOW Capacity (in quintal) 4 12 24
Running cost/day $1000 $800

Max . Z=100 X 1 +800 X 2

St :
6 X 1 +2 X 2 ≥12
2 X 1 +2 X 2 ≥8
4 X 1 +12 X 2 ≥24
X 1 , X 2≥0
Optimal Solution values: X1 =1 X2=3 and Min Z= $3400
Note

In maximization problems, our point of interest is looking the furthest point

2.5.2.
fromSolving for LPPs using the Simplex method
the origin.
The graphical method to solving LPPs provides fundamental concepts for fully understanding the LP
process. However, the graphical method can handle problems involving only two decision variables (say
X1 and X2).
In the 1940s George B. Dantzig developed an algebraic approach called the Simplex Method, which is an
efficient approach to solve applied problems containing numerous constraints; and involving many
variables that cannot be solved by the graphical method.
The simplex method is an ITERATIVE or “step by step” method or repetitive algebraic approach that
moves automatically from one basic feasible solution to another basic feasible solution improving the
situation each time until the optimal solution is reached at.
Similar to the graphical solution approach, this method can be applied to solve for LPPs of different
objectives with various set of constraints.

SOLVING MAXIMIZATION PROBLEMS

1. Maximization having all the constraints in “<”form
Example 1
Consider the microcomputer problem which is solved with graphical method so that you can
compare and contrast the two approaches.
Max Z= 60x1 + 50x2
Subject to
4x1 + 10x2< 100
2x1 + x2< 22
3x1+ 3x2 < 39
x1 & x2 > 0
Solution procedure
To solve the problem using the simplex approach, follow the following steps.
Step 1: Formulate LPP Model:
In our example it is already done.
Step 2: Standardize the problem
Convert each constraint into a standard form by introducing a variable called Slack variable,
surplus variable and artificial variable
Slack Variables(S): is /are added to the left hand side of a < constraint to convert the constraint
into its standard form. The value of the slack variable shows unused or underutilized resource.
Surplus variables(S): is/are added to the left hand side of a > constraints to convert the constraint
into its standard form. The value of the surplus variable shows the excess resources used.
Artificial variables (A): somewhat analogous to slack variables in that they are added to equality
and a > constraints in the same way that slack variables are added to a < constraints. However
artificial variables have no physical interpretation, they merely serve as a device to enable us to
use the simplex process.
Since the above problem constraints have all a < algebraic sign, we use slack variables for standardizing
the problem.

Note-A slack variable is always added for a < constraint to convert the constraint
to a standard form.
 Slack variables represent unused resource or idle capacity. Thus, they don’t produce any product and their
contribution to profit is zero.

Slack variables are added to the objective function with zero coefficients.
Max Z= 60x1 + 50x2+0s1+0s2+0s3
Subject to
4x1 + 10x2+s1=100
2x1 + x2+s2= 22
3x1+ 3x2 +s3=39
x1 , x2 ,s1,s2,&s3= 0
Note

 To standardize an LPP, start from the constraint and finally move to the
objective function.
 When you add the slack variables, it should be according to the existence of the
constraints (how it is written in the model).
 Add S1 to the first constraint, s2 to the second constraints etc

Step 3
 Obtain the initial simplex tableau
To make the data ready for analysis, the simplex method uses a table called the simplex tableau or the
simplex matrix.
In constructing the initial simplex tableau, the search for the optimal solution begins at the origin.
Indicating that nothing can be produced;
Thus, based on this assumption, no microcomputer type one and microcomputer type two is
produced, which implies that x1 =0 and x2=0
==>4x1+10x2 + s1 +0 s2+ 0 s3= 100 ==> 2x1+x2 +0s1 + s2+ 0s3= 22
4(0) +10(0) + s1 +0 s2+ 0 s3= 100 2(0) +0 + 0s1 + s2+ 0 s3= 22
s1= 100 – Unused assembly time. s2= 22 – Unused inspection time.
==> 3x1+ 3x2+0s1 +0s2+ s3= 39
3(0) +3(0) +0s1 +0 s2+ s3= 39
s3= 39 – Unused storage space.
Therefore, Max Z=60x1 +50x2 + 0 s1 +0 s2+ 0 s3
=60(0) +50(0) + 0(100) +0(22) + 0(39) = 0
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
 are variables that are in the basic solution
 have 0 values in the C-Z row
b. Non-basic variables
 are variables with zero solution values
 are variables that are out of the solution
From the above example n=5 variables (x1, x2, s1, s2, and s3) and m=3 constraints (assembly, inspection
and storage space constraints), excluding non-negativity.
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 1st simplex tableau) because they
have non-zero solution values.
Step 3: Construct the initial simplex tableau
Initial simplex tableau
Slack variables

Real
Profit
Bas or
per
columns

ic decis
unit
or ion
column
DV varia
quantity
Solution

bles
column

col
um colu

Profit per unit

C 60 50 0 0 0
BV X1 X2 S1 S2 S3 Q
S1 0 4 10 1 0 0 100 R1
Constraint
S2 0 2 1 0 1 0 22 R2
equation
S3 0 3 3 0 0 1 39 R3
Z 0 0 0 0 0 0
Gross Profit
C–Z
60 50 0 0 0
Net Profit
Step 4: Choose the “incoming” or “entering” variables row
/Indicator
Note:

 The entering variable is the variable that has the most (the largest) positive value in the C - Z
row (indicator row).
 It is the variable that has the highest contribution to profit per unit.
 X1 in our case is the entering variable. (Because the maximum number in the c-z
row is 60)
 Step 5: Choose the “leaving “or “outgoing”variable and the “pivot element”
In this step, we determine the variable that will leave the solution for X1.
To identify the leaving variable, we should calculate the ratio first and then we should select the
minimum non negative ratio.

Note
The pivot element is the intersection point between the pivot row and pivot column; No 2 in the
The leaving variable is the variable that has the smallest replacement ratio.
 example
above
 S2 in our case is the leaving variable. (Because the smallest replacement ratio is
11
 The row associated with the entering variable is called key or pivot row S 2 row in
our case.
Replacement Ratio (RR) = Solution Quantity (Q)
Corresponding values in pivot column

In our case
100 =25
4
22 = 11 is the minimum
2
39 =13
3

It is interesting to note that the three ratios (25, 11, 13) corresponding to the intersections of the
constraints with the x1(look the graphical solution). Note that the smallest of the ratios represents the
extreme point of the feasible solution space; the other points lie beyond the feasible solution space. Hence
by selecting the smallest ratio, the simplex procedure stays within the feasible solution space. It
sometimes happens that some of the substation rates for the variable we want to bring into solution are
zero or negative. We don’t nee to divide the quantity values by a negative or a zero substitution rates.
Step 6:
 Perform row operations. Perform algebraic operations on the PIVOT COLUMN to convert
the pivot element into 1 and the remaining pivot column numbers into 0. Obtain the new row
values through the following two operations:
 Multiply (divide) all of the elements in a row by a constant
 Add or subtract the multiple of the row to or from another row
After identifying the entering, leaving and pivot element construct the second tableau by replacing the
S2 by X1 in the basic solution.
2nd tableau

C 60 50 0 0 0
SV X1 X2 S1 S2 S3 Q RR
S1 0 0 8 1 -2 0 56 56/8=7 R’1=R1+ (-
X1 60 1 1/2 0 1/2 0 11 11/1/2=22 R’2=R2/2
S3 0 0 3/2 0 -3/2 1 6 6/3/2=4 R’3=R3+ (-
Z 60 30 0 30 0 660
C–Z
0 20 0 -30 0

Note the following to see how it is calculated

Since the minimum replacement ratio (RR) is associated with the 2 nd row we should start the operation
on the second row i.e. we should change the pivot element into 1. To do so we should divide the whole
elements of the 2nd row by the pivot element of the first tableau.
See the analysis below.
2 1 0 1 0 22 when we divide it by 2 we get 1 ½ 0 ½ 0 11 so this will be the
new set row values of the second tableau.
Then calculate the new values of the first row and the third row of the second tableau. You can begin in
ether row one or row three.
Let’s start with the first row
Bring the first row values of the initial tableau
4 10 1 0 0 100
Then take the second row values of the 2nd tableau
1 ½ 0 ½ 0 11
Then, in order to change 4 into 0, ask your self what algebraic operation should be done. Very
simple, multiply the whole elements of the second tableau’s value by -4.
You get
-4 -20 -2 0 -44, then add this value to the first row value of initial tableau.
Look at the summary below.
4 10 1 0 0 100 4 10 1 0 0 100 4 10 1 0 0 100
1 ½ 0 ½ 0 11 -4( 1 ½ 0 ½ 0 11) + -4 -2 0 -2 0 -44
 0 8 1 -2 0 56 will be the new
values of the first row of the second tableau. To put it in a simple formula
R’1=R1 + (-4R’2)
Similarly calculate for row three of the second tableau
3 3 0 0 1 39 3 3 0 0 1 39 3 3 0 0 1 39
1 ½ 0 ½ 0 11 -3( 1 ½ 0 ½ 0 11) + -3 -3/2 0 -3/2 0 -33
0 3/2 0 -3/2 1 6 will be the new
values of the 3rd row value of the second tableau. To put it in a simple formula again it will be:
R’3=R3 + (-3R’2)

Note
Then calculate the Z row values i.e. these are found by multiplying the values in each column by the
 Divide each element of the pivot row by the pivot element to find new values in
corresponding coefficients in the C column and adding them.
the key or pivot row.
BV C X1 x2 s1 s2 s3 Q

S1 0 0(0 ) =0 0 (8 )=0 0 (1)=0 0(-2 ) =0 0(0)=0 0(56)=0

X1 60 60(1 )=60 60 (1/2) =30 60( 0 )=0 60(1/2)=30 60 (0)=0 60(11)=660

S3 0 0(0 )= 0 0(3/2) =0 0( 0 )=0 0(-3/2)=0 0( 1)=0 0(6)= 0

Z 60 30 0 30 0 660

Then finally calculate C – Z row. It is simply about following the formula.

Step 7
 Repeat step 4-6 till optimum basic feasible solution is obtained. I.e. repeat these steps till no
positive value occurs in the C – Z row.
Note
 A simplex solution in a maximization problem is optimal when the C-Z row
consists entirely zeros and negative No (when there are no positive values
in the C-Z row.

3rd simplex tableau

BV C 60 50 0 0 0 Q
X1 X2 S1 S2 S3
S1 0 0 0 1 6 - 24
16/3 R’’1=R’1+ (-
8R’ ) R’2+ (-
R’’23=
X1 60 1 0 0 1 -1/3 9
1/2R’ 3) /3/
R’’3=R’
X2 50 0 1 0 -1 2/3 4 3

Z 60 50 0 10 40/3 740 2
C-Z 0 0 0 -10 - 40/3

 The entire C – Z < 0 indicating that no additional potential for improvement exists.
 Optimal solution is reached.
 the optimal solution is where X1=9, X2=4, S1=24and Max Z=740
Interpretation of the Results
The last step is interpreting the result: in order to achieve the maximum weekly profit of birr 740,
the company should produce 9 units of microcomputer type one and 4 units of microcomputer
type two. This will leave no slack in either inspection (s 2=0) or storage space (s3 =0). How ever,
there will be 24 hours of assembly time that is unused.
Example 2
A Juice producing Company has available two kinds of fruit 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. Where as 1 Bottle of punch B
requires 10 liters of Orange Juice and 15 liters of Grape Juice. .From each 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
b. How many bottles of Punch A and Punch B the company should produce in order to maximize
profit? (Using the simplex method)
c. What is this maximum profit?

Solution
 Juice needed for one bottle of
Juice Punch A Punch B Juice Available
__________________________________________________________________________
Orange Juice (lt) 20 10 230
Grape Juice (lt) 5 15 120
Profit per tent $4 $3
Let X1= the No of bottles of punch A produced.
X2= the No of bottles of punch B produced.
The LPP Model of the problem is:
Max Z=4X1 +3X2
St:
20X1 +10X2 < 230 Orange Constraint

5X1 +15X2 < 120 Grape Constraint

X1, X2 >0 Non-negativity constraint

The Standard form of this model will be

Max Z=4x1 +3x2 + 0 s1 +0 s2+ 0 s3
St:
20 x1+10x2 + s1 +0 s2 = 230 Standard form
5x1+15x2 +0s1 + s2+ = 120
x1 , x2 , s1 , s2 =0
Where, s1 =Unused orange juice
s2 =Unused grape juice
Initial feasible solution
1st tableau

B C 4 3 0 0
X1 X2 S1 S2 Q RR

S1 0 20 10 1 0 230 11.5

S2 0 5 15 0 1 120 24
Z 0 0 0 0 0
C–Z 4 3 0 0

2
 n2nd
simplex tableau

B C 4 3 0 0
X1 X2 S1 S2 Q RR

X1 4 1 ½ 1/20 0 11.5 23

S2 0 0 25/2 -1/4 1 62.5 5

Z 4 2 1/5 0 46
C–Z 0 1 -1/5 0

Optimal solution mix: the 3rd simplex tableau

4 3 0 0
B C Q
X1 X2 S1 S2
X1 4 1 0 3/50 - 1/25 9
X2 3 0 1 -1/50 2/25 5
4 3 0.18 0.08
Z
51
C- Z
0 0 - 0.18 -0.08

Optimal Solution
X1= 9 X2= 5 s1 =0 s2=0 and Max Z=$51