CHAPTER TWO

LINEAR PROGRAMMING PROBLEMS

2.1 Introduction to Linear Programming (LP)

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 frequently, 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.

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. Thus, a given change in one variable will always cause a resulting

proportional change in another variable.

L.P is solved in a step – by – step manner called iterations. Each step of the procedure is an
attempt to improve on the solution until the "best answer" is obtained or until it is shown that no
feasible answer exists.

Linear Programming (LP) Can Be Used for Many Managerial Decisions:

• Product mix
• Make-buy
• Media selection
• Marketing research
• Portfolio selection
• Shipping & transportation
• Multi-period scheduling
• etc.

2.1.1 Properties and Assumptions of Linear Programming Model

Any linear programming model (problem) must have the following properties:
a. The relationship between variables and constraints must be linear.
b. The model must have an objective function.
c. The model must have structural constraints.
d. The model must have non-negativity constraint.

Basic assumptions considered while using linear programming model for decision making are
the following.
1|Page
I. Proportionality
Proportionality exists in the objective function and the constraint inequalities to the level of
activity. Example: If the product is assumed to contribute 10 Birr towards the profit, the total
contribution would be 10x. If one unit require 2 hours of labour of certain type, then 10 units
would require 20 hours.
• Volume discounts, set-up charges, and nonlinear efficiencies are potential sources of
violation

II. Additivity
The total of all activities is given by the sum total of each activity conducted separately. There is
no interaction among the decision variables. Interaction is possible, for instance, if some product
is a by-product of another one.
– The total profit in the objective function is determined by the sum of profit contributed by
each of the product separately.
– Similarly the total amount of resource used is equal to the sum of resource values used by
various resources.

III. Continuity
The decision variables are continuous. As a consequence, combination of output with fractional
values, in the context of production problems is possible.
• Fractional values for decision variables are permitted
• Although in many situations we can have only integer values, but we can deal with
fractional values in the following manner.
1. When the decision is one shot decision (not repetitive in nature), we may round the fractional
values to the nearest integer values.
However, when we do so, we should evaluate the revised solution to determine whether the
solution represented by the rounded values is visible solution and also it is the best integer
solution.
2. If the problem related to continuum of time and it is designed to determine an optimal solution
for a given time period only, then the fractional values may not be rounded.
Example: The best solution to the problem might be to produce A= 5 1/3 units and B= 10 1/3
units per week.
– The fractional amount of production would be taken to the work in progress and become a
portion of production of the following week. In this case, an output of 17 units of A and 31
units of B over a three-week period.
3. We may reset the problem as an integer programming problem (forcing the solutions to be in
integers only).

IV. Certainty

2|Page
Data elements aij , cj , bi , uj are known with certainty
• Nonlinear or integer programming models should be used when some subset of
assumptions (i), (ii) and (iii) are not satisfied.
• Stochastic models should be used when a problem has significant uncertainties in the
data that must be explicitly taken into account [a relaxation of assumption (iv)].

V. Non negativity
The decision variables cannot have negative values. Example: Units produced.

2.1.2. Components of Linear Programming Models

There are four major components of Linear Programming models including: Objective function,
decision variables, constraints and parameters.

1. Objective and Objective Function

The objective in problem solving is the criterion by which all decisions are evaluated. It provides
the focus for problem solving. In linear programming models, a single, quantifiable objective
must be specified by the decision maker. Because we are dealing with optimization, the objective
will be either maximization or minimization. Hence, every Linear Programming problem will be
either maximization or a minimization problem. Once the objective is specified, it becomes the
measure of effectiveness against which alternate solutions are judged. A Linear Programming
model consists of a mathematical statement of the objective called the objective function.

2. Decision Variables
They represent unknown quantities to be solved for. The decision maker can control the value of
the objective, which is achieved through choices in the levels of decision variables. For example,
how much of each product should be produced in order to obtain the greatest profit?

3. Constraints
However, the ability of a decision maker to select values of the decision variables in a Linear
Programming problem is subject to certain restrictions or limits coming from a variety of
sources. The restrictions may reflect availabilities of resources (e.g., raw materials, labor time,
etc.), legal or contractual requirements (e.g., product standards, work standards, etc.),
technological requirements (e.g., necessary compressive strength or tensile strength) or they may
reflect other limits based on forecasts, customer orders, company policies, and so on. In Linear
Programming model, the restrictions are referred to as constraints. Only solutions that satisfy all
constraints in a model are acceptable and are referred to as feasible solutions. The optimal
solution will be the one that provides the best value for the objective function.
Generally speaking, a constraint has four elements:
 A right hand side (RHS) quantity that specifies the limit for that constraint. It must be a
constant, not a variable.

3|Page
  An algebraic sign that indicates whether the limit is an upper bound that cannot be
exceeded, a lower bound that is the lowest acceptable amount, or an equality that must be
met exactly.
 The decision variables to which the constraint applies.
 The impact that one unit of each decision variable will have on the right-hand side
quantity of the constraint.
Constraints can be arranged into three groups:
 System constraints – involve more than one decision variable,
 Individual constraints – involve only one variable, and
 Non-negativity constraints – specify that no variable will be allowed to take on a negative
value. The non-negativity constraints typically apply in a Linear Programming model,
whether they are explicitly stated or not.

4. Parameters
The objective function and the constraints consist of symbols that represent the decision
variables (e.g., X1, X2, etc.) and numerical values called parameters. The parameters are fixed
values that specify the impact that one unit of each decision variable will have on the objective
and on any constraint it pertains to as well as the numerical value of each constraint.
The following simple example illustrates the components of Linear Programming models:

II.2 Mathematical Model Formulation

The effective use of Linear Programming in real life problems requires proper and accurate
formulation of model, which has objective function along with constraints. The steps for
formulating the L.P are:
1. Identify the unknown decision variables to be determined and assign symbols to them.
2. Identify all the restrictions or constraints in the problem and express them as linear
equations or inequalities of decision variables.
3. Identify the objective or aim and represent it also as a linear function of decision
variables.
Let xi = decision variable for ith variable.

4|Page
 ci = profit or cost co-efficient of ith variable.
z = function to be maximized or minimized.
Thus for n decision variables, the objective function is to maximize or minimize
z = c1 x1 + c2 x2 + ... + cn xn
Let aij = co-efficient of the jth constraint and ith variable
bi = resource limitation for ith constraint
Thus the restrictions may be expressed in the general form

a11x1 + a12x2 + ... + a1nxn ¿ b1

a21x1 + a22x2 + ... +a2nxn ¿ b2
am1x1+ am2x2 + ...+ amnxn ¿ bm
and xi > 0 for all values of i from 1 to n
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 Linear
Programming model.

Solution

Maximize Z = 3x1 + 4x2 Objective Function

Subject to x1 + x2 ¿ 450
2x1 + x2 ¿ 600 Linear Structural Constraints
Where x1, x2 ¿ 0 Non - Negativity Constraint
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 table.

Machine Time per unit (minutes) Machine capacity (minutes)

Product 1 Product 2 Product 3

M1 2 3 2 440

M2 4 - 3 470

M3 2 5 - 430

The profit per unit for product 1, 2 & 3 is Birr 4, 3 & 6 respectively. Formulate the mathematical
Linear Programming model that will maximize daily profit.

5|Page
Solution

Max Z = 4x1 + 3x2 + 6x3 objective function

Subject to: 2x1 + 3x2 + 2x3 ¿ 440 linear structural constraint 1
¿
4x1 + 0x2 + 3x3 470 linear structural constraint 2
¿
2x1 + 5x2 + 0x3 430 linear structural constraint 3
Where x1, x2 & x3 ¿ 0 non negativity constraint
Example 3
A person wants to decide the constituents of a diet which will fulfill his daily requirement of
proteins, fats & carbohydrates at a minimum cost. The choice is to make from different types of
foods. The yields per unit of this food are given below. Formulate Linear Programming model
for the problem.

Yield per unit Cost per unit

(Birr)
Food types Proteins Fats Carbohydrates

1 3 2 6 45

2 4 2 4 40

3 8 7 7 85

4 6 5 4 65

Minimum 800 200 700

requirement

Solution

Minimize Z = 45x1 + 40x2 + 85x3 + 65x4

Subject to 3x1 + 4x2 + 8x3 + 6x4 ¿ 800
2x1 + 2x2 + 7x3 + 5x4 ¿ 200
6x1 + 4x2 + 7x3 + 4x4 ¿ 700
Where x1, x2, x3 & x4 ¿ 0

2.3 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. This method
consists of the following steps.
1. Formulate the mathematical model for the given problem.
2. Convert the constraints given in the form inequality to that of equality.
3. Draw the x and y axes.
6|Page
 4. Plot each of the constraints on the graph.
5. Identify the feasible (solution) region.

2.3.1 Techniques of Graphical method

Corner (extreme) Point Method: This method includes the following steps.
1. Identify each of the extreme points of the feasible region.
2. 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 Problems
Example
In order to demonstrate the method, let us take a microcomputer problem in which a firm is
about to start production of two new microcomputers, X 1 and X2. Each requires limited resources
of assembly time, inspection time, and storage space. The manager wants to determine how
much of each computer to produce in order to maximize the profit generated by selling them.
Other relevant information is given below:
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
Availability of company resources:
Resources Amount available
Assembly time 100 hours
Inspection time 22 hours
Storage space 39 cubic feet
The model is then:
Maximize 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
X1, X2 > 0

Solution
Graphical solution method involves the following steps.

Step 1. Plot each of the constraints

The step begins by plotting the non-negativity constraint, which restricts our graph only to the
first quadrant. We then can deal with the task of graphing the rest of the constraints in two parts.
7|Page
For example, let us take the first constraint 4X 1 + 10X2 < 100 hours. First we treat the constraint
as equality: 4X1 + 10X2 = 100. Then identify the easiest two points where the line intersects each
axis by alternatively equating each decision variable to zero and solving for the other: when
X1=0, X2 becomes 10 and when X2=0, X1 will be 25. We can now plot the straight line that is
boundary of the feasible region as we have got two points (0, 10) and (25, 0).

Step 2. Identify the feasible region

The feasible region is the solution space that satisfies all the constraints simultaneously. It is the
intersection of the entire region represented by all constraints of the problem. We shade in the
feasible region depending on the inequality sign. In our example above, for all the constraints
except the non-negativity constraint, the inequality sign is ‘less than or equal to’ and it represents
region of the plane below the plotted lines.

Step 3. Locate the optimal solution.

The feasible region contains an infinite number of points that would satisfy all the constraints of
the problem. Point that will make the objective function optimum will be our optimal solution.
This point is always found among the corner points of the solution space.
Once the constraints are plotted and feasible region is determined, we use either of the two
graphic methods of Graphic approach to find a solution for LP model consisting of only two
decision variables:
Maximization of objective function involves finding the point where the combination of products
results in maximum value of objective function. The constraints are connected with < sign. The

8|Page
solution space lies below the slant line and is bounded by the line segments. The origin and other
points below the slant lines are in the solution space (i.e., feasible region).

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

Using this method for our example, simultaneously solving for corner points a, b, c, and d, we
find corresponding profit values of 500, 700, 740, and 660, respectively giving us the same
solution as the above one at C. Therefore, the optimal solution is x1= 9 units and x2 = 4 units
while the optimal value of objective function is 740.
 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)
The production of 9 units of Model I and 4 units of Model II consume:
– 4x1+ 10x2 of assembly hours.
(4*9) + (10*4) = 76 assembly hours;
– 2x1 + x2 of inspection hours;
(2*9) + (1*4) = 22 inspection hours
– 3x1 + 3x2 cubic storage; and
(3*9) + (3*4) = 39 cubic storage space
Therefore one of the available resources is not utilized fully and we have unutilized 24 hours of
assembly time.

2. Minimization Problems
Solving minimization problems involve where the objective functions (like cost function) will be
minimum. The constraints are connected to RHS values with > sign. But, in real world problems,
mixes of constraint is also possible. The value of RHS involves the lowest value of the
constraint.

9|Page
The solution space lies above the slant lines and it is not enclosed. It extends indefinitely above
the lines in the first quadrant. This means simply that cost increases without limit as more and
more units are produced. The minimum cost will occur at a point along the inner boundary of the
solution space. The origin and other points below the lines are not in the solution space.
Example
Min Z = 0.1x+0.07y
Subject to:
6x+2y > 18
8x+10y > 40
y>1
x, y > 0
Find the values of x and y which makes the objective function minimum?
Solution

Corner Coordinate Point Value of Objective Function

Point (X, Y) (Z=0.1X + 0.07Y)
A (0, 9) 0.1(0) + 0.07(9) = 0.63
B (25/11, 24/11) 0.1 (25/11) + 0.07 (24/11) = 0.38
C (15/4, 1) 0.1 (15/4) + 0.07 (1) = 0.445

 Slack Versus Surplus

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 hours, the slack value is 100 – [4(9)
+10(4)] = 24.
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.3.2. Graphical Solutions for the Special Cases of LP

i) Unboundedness
Unboundedness occurs when the decision variable increased indefinitely without violating any of
the constraints. 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.
Example:

10 | P a g e
 Max Z = 10X1 + 20X2
Subject to 2X1 + 4X2 > 16
X1 + 5X2 > 15
X1, X2 > 0
Following the above listed steps of graphical solution method, we find the following graph for
the above model:

The shaded area represents the set of all feasible solutions and as can be seen from the graph, the
solution is unbounded.

ii) Infeasibility
In some cases after plotting all the constraints on the graph, feasible area (common region) that
represents all the constraint of the problem cannot be obtained. In other words, 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

iii) Multiple Optimal Solutions

Recall the optimum solution is that extreme point for which the objective function has the largest
value. It is of course possible that in a given problem there may be more than one optimal
solution.
There are two conditions that should be satisfied for an alternative optimal solution to exist:

11 | P a g e
  The given objective function is parallel to a constraint that forms the boundary of the
feasible region. In other words, the slope of an objective function is the same as that of the
constraint forming the boundary of the feasible region; and
 The constraint should form a boundary on the feasible region in the direction of optimal
movement of the objective function. In other words, the constraint should be an active
constraint.
Note: The constraint is said to be an active or binding or tight, if at optimality the left hand side
equals the right hand side. In other words, an equality constraint is always active. An inequality
sign may or may not be active.
Example:
Max Z = 8X1+16X2
Subject to: X1 + X2 < 200 ……. C1
3X1 + 6X2 < 900 ……. C2
X2 < 125 ……. C3
X1, X2 > 0

In the problem above, using extreme point method and solving for values of corner points
simultaneously, 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. One benefit of having multiple optimal solutions is that for
other (perhaps qualitative) reasons, a manager may prefer one of them to the others, even though
each would achieve the same value of the objective function. In practical terms, one of the two
corner points is usually chosen because of ease in identifying its values.
Other corner points are computed by identifying the two corner points and keeping the value of
the objective function constant, where 50 ¿ X1¿ 100 and 100 ¿ X1¿ 125. By selecting one
value for one of the decision variables from the domain, we determine the value for another
decision variable keeping the objective function’s value. Let X1 = 80.

Then, Z = 8X1+16X2  2400 = 8(80) +16X2

16X2 = 1760
12 | P a g e
 X2 = 110

2.3.3. Mix of Constraints

It is only in some cases that the maximization problems consist of constraints connected to the
RHS value with only <. By the same token, constraints of minimization problems are not always
connected to their RHS with>. This is to mean that both maximization and minimization
problems may consist of constraints connected to RHS with a mix of algebraic signs ( <, >, =).
Example
Min Z = 1500x+2400y
Subjected to:
4x+Y>24 …I
2x+3y>42 …II
X+4y>36 …III
X<14 …IV
y<14 …V
Where; x, y>0

Plot the constraints.

2x+3y>42 y
2x+3y=42
If x=0,
2x+3y=42
2(0) +3y=42
2(0) +3y=42 24_(0,24)
y=42/3 IV
y=14
The coordinates (0,14)
If y=0, 18 _ I
2x+3y=42
2x+3(0)=42 A (2.5,14) (14,14)
x=42/2 B V
x=21 (0, 14) E (3, 12)
Constraint III 12 _
X+4y>36 Feasible
X+4y=36 region multiple solution line
If x=0, (0,9) (double lined)
 x+4y=36
 y=36/4 6_ C (14, 5.5)
 y=9
The coordinates (0, 9) D
If y=0, (12,6) II III x
x+4(0) =36 (0, 0)
x =36 (6,0) (14,0) (21,0) (36,0)
13 | P a g e
 Corne Constraints Coordinates Objective Function
r intersected X Y 1500x + 2400y
Points
A I&V 2.5 14 37,350
B I V& V 14 14 54,600
C III & IV 14 5.5 34,200
D II & III 12 6 32,400
E I & II 3 12 33,300

The minimum value of the objective function is 32,400. Therefore, the optimum solution is
found at the corner point D, where constraint II&III are intersected. Hence, optimal solution: x
=12, y = 6.

Important terms in Linear Programming Solution

 Solutions values of decisions variable of linear programming model are called solutions.
 Basic solutions the variables which have zero values are non-basic variables and the
remaining variables which contained non-zero variables are called basic variables. For the
set of simultaneous equations in Q known (P > Q), a solution obtained by setting (p - Q) of
variables equal to zero and solving the remaining P equations in P unknown is as basic
solution.
 Feasible solution the solution which satisfies all the constraints of linear programming
problems is called a feasible solution.
 Basic feasible solution a feasible solution which is also a basic solution is known as a basic
feasible solution.
 Optimal feasible solution a basic feasible solution which optimizes the objective function is
called an optimal feasible solution.
 Degenerate solution a basic solution is said to be degenerate if one or more basic variables
become zero.
 Infeasible solution the solution which does not satisfy all the constraints of linear
programming problem is called infeasible solution.

14 | P a g e
2.4 Simplex Solution Method
The graphical method of solving linear programming problems is a simple way to find a solution
since the optimum solution is searched among the corner points of the solution space. However,
the graphical method is restricted to problems with two decision variables. When the number of
variables and the number of constraints increase, it becomes difficult to visualize the solution
space. As a result, the graphical method cannot be employed successfully in such cases. In order
to avoid this limitation, the simplex method, or iterative or step by step method is efficient
method for solving linear programming problems, which was developed by George [Link] in
1947.
The simplex method is an algebraic procedure that starts with a feasible solution that is not
optimal and systematically moves from one feasible solution to another until an optimal solution
is found. In case of the graphical approach, optimal solution occurs at the extreme points where
the constraints intersect. Solutions where constraints intersect are called basic solutions, and
those satisfying all of the constraints together with non-negativity constraints are called basic
feasible solutions.
Constraints are generally expressed using inequalities either in ‘less than’ or ‘greater than’ or in
mixed form. Thus, constraints are not in standard form, meaning they should be converted into
equalities. To convert the inequality constraint into equality, we introduce slack or surplus
variables. In economic terminology, slack variables represent unused capacity and surplus
variables represent excess amount. The contribution (cost or profit) associated with the slack and
surplus variables are zero.
An inequality of the ‘less than or equal to’ type is transformed into equality by introducing
(adding) a non-negative slack variable, as follows: -
Example:
Non Standard form Standard form
X1 + 2X2 < 6 X1 + 2X2 + S1 = 6
Where; X1 and X2 are decision variables and S 1 is a slack variable, added to the smaller side of
the inequality.
On the other hand, an inequality with ‘greater than or equal to’ type is changed into equality by
subtracting surplus variable as follows:
Example:
Non Standard form Standard form
X1 + 2X2 > 6 X1 + 2X2 - S1 = 6
Where; X1 & X2 are decision variables and S1 is a slack variable, subtracted from the greater
side of the inequality.
As stated above, since both the slack and surplus variables are insignificant with no contribution
in the objective function, they are represented with coefficient of zero in the objective function.

15 | P a g e
To find a unique solution, the number of variables should not exceed the number of equations.
When the number of variables is more than the number of equations, the number of solutions is
unlimited. So as to get a unique solution, we have to set at least (n - m) variables to zero, where n
is the number of variables and m is the number of equalities. Those variables that are set to zero
are called non basic variables indicating they are not in the solution. The variables that are in
solution are called basic variable.
To demonstrate the simplex method, we will use the microcomputer problem with the following
objective function and constraints.
The Microcomputer Problem, which was discussed in graphic approach, can be standardized as:
Max. Z = 60X1 + 50 X2 + 0S1 + 0S2 + 0S3
Subject to 4X1 + 10X2 + S1 = 100
2X1 + X2 + S2 = 22
3X1 + 3X2 + S3 = 39
Where; X1 & X2 are decision variables and S1, S2 & S3 are slack variables.
Here, the number of variables (5) is greater than the number of equations (3). Therefore, the
decision variables are set to zero and we have
X1 = 0, X2 = 0, S1 = 100, S2 = 22, and S3 = 39.
This solution will serve as an initial feasible solution. An initial feasible solution is a first
solution used to generate other basic feasible solutions. The initial basic feasible solution is
obtained by setting all the decision variables to zero. As a result, the initial basic feasible
solution is entirely composed of the slack variables. X 1 & X2 are non-basic variables since they
are not in solution. S1, S2 & S3 are basic variables since they are in solution.
A tableau is a system of displaying the basic feasible solution, the constraints of the standard
linear programming problem as well as the objective function in a tabular form. A tableau is
useful in summarizing the result of each iteration, i.e. the process of moving from one
solution/corner to another solution/corner in order to select the optimal solution.
 Steps of Simplex Solution Method
The solution steps of the simplex method can be outlined as follows:
Step 1. Write the Problem in Standard Form
Characteristics of the problem:
 All constraints are expressed in the form of equalities or equations.
 All right hand sides are non-negative
 All variables are non-negative
Rules to follow while 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
Step 2. Develop an Initial Simplex Tableau
16 | P a g e
Steps in developing initial simplex tableau:
1) List the variables in the model across the top of the tableau
2) Next fill-in the parameters of the model in the appropriate rows and columns
3) Add two columns to the left side of the tableau. The first column is a list of variables called
Basis.
4) The C at the top second column indicates that the values in that column and the values in
the top row are objective function coefficients.
5) The last column at the right is called the quantity column. It refers to the right hand side
values (RHS) of the constraints.
6) There are two more rows at the bottom of the tableau. The first row 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.
7) The last row 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 from the C value in the top row.

Step 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.

Step 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 column entries.
 The row of the leaving variable is called pivot row.
 The number found in the intersection point of pivot column and pivot row is called pivot
element.

Step 5. Drive the Revised Tableau for Improved Solution

 Divide each element of the pivot row (including quantity) by the pivot element to get the
corresponding value in the new tableau. The divided row value is called the replacement
row.
 For each row other than the pivot row;
o New row element = old row element – (row element in pivot column *
corresponding replacement value.)

Step 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 (Cj-Z ≤ 0).

17 | P a g e
  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 2-6 will be repeated again and again until the
optimal solution is obtained!
1. Maximization Linear Programming Problems
Example
Finding the initial Feasible Solution
As discussed above, the initial feasible solution is found by setting the decision variables to zero.
Max Z = 60X1+50X2+0S1+0S2+0S3
Subject to 4X1+10X2+S1 = 100
2X1+ X2+S2 = 22
3X1+ 3X2+S3 = 39
X1, X2 ≥ 0

Initial Simplex tableau

Cj 60 50 0 0 0
Basic V. X1 X2 S1 S2 S3 Quantity
S1 0 4 10 1 0 0 100
S2 0 2 1 0 1 0 22
S3 0 3 3 0 0 1 39
Zj 0 0 0 0 0 0
Cj-Zj 60 50 0 0 0

Interpretation of the Initial Feasible Solution

To be noted first is that the values of each basic variable (variables that are in solution) is
composed of a single 1 and the rest 0’s. This is called a unit vector. Basic variables will have a
unit vector. Moreover, ‘1’ will appear in the same row that the variable appears in. The unit
vector concept will used Linear Programming us in developing subsequent tableaus when we
want to change the list of variables that are in solution.
The Zj row in the quantity column indicates that the value of the objective function is 0.
The values in the Cj-Zj row indicate the net contribution of the variables if one unit of each
variable is added into that solution. For example, the 60 in column X 1 indicates that bringing one
unit of X1 would increase the value of the objective function by $60. The same is true for the X 2
column, i.e. bringing one unit of X2 would increase the value of the objective function by $50.
On the other hand, since the slack variables are at their maximum, their values in the C j-Zj row
are all 0. According to what has been said before, we have the following rule in order to identify
an optimal solution.
A simplex solution in a maximization problem is optimal if the C j-Zj row consists of entirely zeros
and negative numbers, i.e. there are no positive values in the row.

18 | P a g e
So for our case in the initial tableau, we have two positive values under the non-basic variables,
which indicate that further improvement of the solution is possible. As a result, we go for the
optimal solution by developing the second simplex tableau.

Developing the Second Simplex Tableau

In the initial feasible solution, the slack variables form entirely the basic variables and the
decision variables entirely form the non-basic variables. Since further improvement is possible,
one of the decision variables will be brought into the solution and one of the current basic
variables will be leaving the solution. ‘Which non-basic variable should be brought into the
solution and which basic variable should leave the solution?’ is a major concern here.
In answering the first question, the non-basic variable that should enter the solution should be the
one with the highest positive value in the C j-Zj row since bringing that non-basic variable into
the solution would make the highest contribution to the solution (objective function) and result in
the largest profit potential. As a result, the variable with the highest value in the C j-Zj row of the
initial simplex tableau is the X 1 column with a value 60. Therefore, X 1 should enter the basis or
the solution mix. The X1 column is now called the pivot column. The numbers in this column (4,
2, and 3) indicate the amount of the basic variables needed to get one unit of X 1. For example,
the number 4 indicates that 4 units of the first slack are needed to obtain one unit of X1.
Since X1 has the highest profit potential, we need to make as much X 1 units as possible. The
amount of X1 that can be made depends on the values in the pivot column and the amount of
slack available shown under the quantity column. By dividing the values in the pivot column by
their respective values in the quantity column, we can identify the variable that is most limiting.
The values obtained by dividing will be used for determining the variable that should leave the
solution.

Cj 60 50 0 0 0
Basic V. X1 X2 S1 S2 S3 Quantity

S1 0 4 10 1 0 0 100 100/4 = 25
S2 0 2 1 0 1 0 22 22/2 = 11
S3 0 3 3 0 0 1 39 39/3 = 13
Zj 0 0 0 0 0 0
Cj-Zj 60 50 0 0 0

Pivot Column
Pivot Row Pivot Element
In interpreting the ratios obtained by the division, If only the constraint was the first one, we
could make 25 units of X1. But there are also other constraints. Therefore, the one with the
smallest non-negative ratio is the most restrictive since it determines the amount of X 1. In this
particular case, there is only enough of the second constraint to make 11 units of X 1. In making
19 | P a g e
the 11 units of X1, the second resource (S2) will be down to zero indicating that S 2 will leave out
the solution mix. The row of the leaving variable is called the pivot row. The intersection of the
pivot row and the pivot column is called the pivot element.
As a rule, the leaving variable is the one with the smallest non-negative ratio.
If a zero is obtained in the results of division, none of the corresponding variable is needed to
obtain one unit of the entering variable. If a negative value is obtained in the division, bringing
the entering variable into the solution would increase the amount of the basic variable. These
values will not limit the amount of the entering variable. Therefore, there is no need to divide the
quantity column by zero or negative.
Since we have determined the leaving and the entering variables and since the initial feasible
solution can be improved further, we need to develop the second tableau in order to find the
optimal solution. In developing the second tableau, we should compute for revised values of the
constraint equations, the Zj row and the Cj-Zj row and remember that the variables in solution
will have a unit vector, with a value of 1 in the intersection of the column and the row of the
basis, i.e. the pivot element.

To obtain a unit vector in the basis column, we perform elementary row operations resulting in
new row values by either multiplying/dividing all the elements in a row by a constant or
adding/subtracting the multiple of a row to or from another row.
In computing for the new row values from our initial simplex tableau, we first multiply the
second constraint by ½ obtaining the values as follows:
X1 + 1/2X2 + 0S1 + 1/2S2 + 0S3 = 11, which results in making the pivot element 1.
Next, we multiply the above new row values by 4 and subtract it from the first constraint
obtaining the following results:
0X1 + 8X2 + 1S1 + 2S2 + 0S3 = 56.
Then, we multiply the new row values in the pivot row by 3 and subtract it from the third
constraint resulting as follows:
0X1 + 3/2X2 + 0S1 - 3/2S2 + 1S3 = 6.
Having these new row values, we develop the second simplex tableau as shown below.

Second Simplex Tableau

Cj 60 50 0 0 0
Basic V. X1 X2 S1 S2 S3 Quantity
S1 0 0 8 1 -2 0 56
X1 60 1 ½ 0 ½ 0 11
S3 0 0 3/2 0 -3/2 1 6
Zj 60 30 0 30 0 660
Cj-Zj 0 20 0 -30 0

Interpretation of the Second Simplex Tableau

20 | P a g e
The profit obtained at this point of solution is $660. In the Cj-Zj row, we search for the highest
positive value. If there is, it means that we can further improve this solution. Therefore, we have
a positive value in the Cj-Zj row which indicates that this is not the optimal solution. As a result,
we go for the next tableau.

Developing the Third Tableau

Here, we select the entering and the leaving variables. The entering variable is the one with the
highest Cj-Zj row value which is the X 2 column. This means that bringing one unit of X 2 into the
solution increases profit by $20. Therefore, the X 2 will be the entering variable designated as the
pivot column.
To determine the leaving the variable, we divide the values in the pivot column by their
corresponding row values in the quantity column. The result obtained, as shown in the table
below indicates that S3 is the leaving variable with the smallest non-negative ratio. This means
that S3 is the most limiting resource for how much units of X2 can be made.

Cj 60 50 0 0 0
Basic V. X1 X2 S1 S2 S3 Quantity
56/8 = 7
S1 0 0 8 1 -2 0 56
11/(1/2) = 22
X1 60 1 1/2 0 ½ 0 11
6/(3/2) = 4
S3 0 0 3/2 0 -3/2 1 6
Zj 60 30 0 30 0 660
Cj-Zj 0 20 0 -30 0

Pivot Row
Pivot Column Pivot Element
After identifying the entering and the leaving variables, we perform elementary row operations
as follows. To obtain a unit vector with 1 in the pivot element, we multiply the pivot row by 2/3
resulting as follows:
0X1 + 1X2 + 0S1 - 1S2 + 2/3S3 = 4
Then, multiply the above new row values by 8 and subtract it from the first constraint (row)
resulting as follows:
0X1 + 0X2 + 1S1 + 6S2 - 16/3S3 = 24.
For row 2, first multiply the new row values in the pivot row by ½ and subtract it from the
second row resulting as follows:
1X1 + 0X2 + 0S1 + 1S2 - 1/3S3 = 9.
And the third tableau looks like the following.
Third Simplex Tableau
Cj 60 50 0 0 0
Basic V. X1 X2 S1 S2 S3 Quantity

21 | P a g e
 S1 0 0 0 1 6 -16/3 24
X1 60 1 0 0 1 -1/3 9
X2 50 0 1 0 -1 2/3 4
Zj 60 50 0 10 40/3 740
Cj-Zj 0 0 0 -10 -40/3
Interpreting the Third Tableau
All the values in the Cj-Zj row are zero and negative indicating that there cannot be additional
improvement. This makes the third tableau to contain the optimal solution with the following
basic variables:
S1 = 24, X1 = 9, and X2 = 4 producing a maximum profit of $740.
This means that in order to achieve the maximum profit, the company should produce 9 units of
X1 and 4 units of X2 leaving 24 hours of unused resource of the first constraint.
 Maximization Problems with Mixed Constraints
Example:
Assume the following maximization problem with mixed constraints.
Max. Z = 6X1+8X2
Subject to X2 ≤ 4
X1+X2 = 9
6X1+2X2 ≥ 24

In solving for this problem, introducing a slack variable is not acceptable since they represent
unused capacity and there is no unused capacity in = and ≥ constraints. Therefore, for ≥
constraints, we introduce a surplus variable and for both ≥ and = constraints we introduce
artificial variables resulting as follows.
Max Z = 6X1+8X2+0S1+0S3-MA2-MA3
Subject to X2+ S1 = 4
X1+X2+A2 = 9
6X1+2X2-S3+A3 = 24
X1, X2 ≥ 0
Developing the Initial Simplex Tableau
In the initial tableau, we list the variable in the order of decision variable, slack/surplus variables
and finally artificial variables. In this case, the Big-M Method is applied 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.
Similarly, if Z is to be maximized, then a very large negative price (also called penalty) is
assigned to each of these variables.
Initial Simplex Tableau
Cj 6 8 0 0 -M -M
Basic V. X1 X2 S1 S3 A2 A3 Quantity
S1 0 0 1 1 0 0 0 4
22 | P a g e
 A2 -M 1 1 0 0 1 0 9
A3 -M 6 2 0 -1 0 1 24
Zj -7M -3M 0 +M -M -M -33M
Cj-Zj 6+7M 8+3M 0 -M 0 0

Since this is a maximization problem, the entering variable is the one with the maximum C j-Zj
value. Therefore, the variable with the maximum C j-Zj is X1, the decision variable. And the
leaving variable is with the minimum non-negative ratio which is A 3, the artificial variable. Since
this artificial variable is not needed we remove it from the next tableau.

Developing the Second Simplex Tableau

After identifying the entering and the leaving variable, the usual elementary row operations are
performed to obtain a unit vector in the entering variable column. The end result after performing
the row operations is as follows which shows the second tableau.

Second Simplex Tableau

Cj 6 8 0 0 -M
Basic V. X1 X2 S1 S3 A2 Quantity
S1 0 0 1 1 0 0 4
A2 -M 0 2/3 0 1/6 1 5
X1 6 1 1/3 0 -1/6 0 4
Zj 6 2-2/3M 0 -1-M/6 -M 24-5M
Cj-Zj 0 6+2/3M 0 1+M/6 0

Again here, we identify the leaving the entering variables, i.e. the pivot row and the pivot column
respectively. The entering variable with the highest C j-Zj row value is X2 and the leaving variable
with the smallest ratio is S1.

Developing the Third Simplex Tableau

Selecting the entering and leaving variables, we go for obtaining a unit vector in the pivot
column by using the elementary row operations. We get the following third tableau.

Third Simplex Tableau

Cj 6 8 0 0 -M
Basic V. X1 X2 S1 S3 A2 Quantity
X2 8 0 1 1 0 0 4
A2 -M 0 0 -2/3 1/6 1 7/3
X1 6 1 0 -1/3 -1/6 0 8/3

23 | P a g e
 Zj 6 8 6+2/3M -1-M/6 -M 48-7/3
Cj-Zj 0 0 -6-2/3M 1+M/6 0

Similarly, we identify the entering and the leaving variables which are S 3 and A2 respectively
representing the maximum Cj-Zj value and the minimum ratio.
Developing the Fourth Simplex Tableau
Perform elementary row operations usual to have a unit vector in the entering variable column
and you will get the following fourth tableau.
Fourth Simplex Tableau

Cj 6 8 0 0
Basic V. X1 X2 S1 S3 Quantity
X2 8 0 1 1 0 4
S3 0 0 0 -4 1 14
X1 6 1 0 -1 0 5
Zj 6 8 2 0 62
Cj-Zj 0 0 -2 0

This tableau represents the final tableau since we have only zeros and negative values in the C j-Zj
row which indicates that it is the optimal solution. So we have the following results for each of
the variables and the profit obtained.
 X1 = 5, X2 = 4, S3 = 14, and Profit = 62

2. Minimization Linear Programming 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. Similarly, if Z is to be maximized, then a
very large negative cost (also called penalty) is assigned to each of these variables. Following are
the characteristics of Big-M Method:

Example: Assume the following minimization problem.

Min Z = 7X1+9X2
Subject to 3X1+6X2 >= 36
8X1+4X2 > = 64
X1, X2 > = 0
We introduce both surplus and artificial variables into both constraints as follows.
Min Z = 7X1+9X2+0S1+0S2+MA1+MA2
Subject to 3X1+6X2 –S1+A1 = 36

24 | P a g e
 8X1+4X2-S2+A2 = 64
X1, X2 > = 0
So the subsequent tableaus for this problem are shown below. To remind in these tableaus is in
transforming from one tableau to another, we perform elementary row operations to obtain the
unit vector in the pivot column for the entering variable into the solution.
Initial Simplex Tableau
Cj 7 9 0 0 M M
Basic V. X1 X2 S1 S2 A1 A2 Quantity
A1 M 3 6 -1 0 1 0 36
A2 M 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
Second Simplex 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
Third Simplex 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
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: X 1 = 20/3 and X2 = 8/3 and value of objective function is
212/3.
Summary
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

25 | P a g e
 = Add artificial variable (A) -M +M Yes

2.4.1. Special Issues in Simplex Solution

Several special situations which one many encounter during the application of simplex method
are summarized below:
1. Non-feasible Solution/ Infeasibility
A situation with no feasible solution may exist if the problem was formulated incorrectly.
Infeasibility comes about when there is no solution that satisfies all of the problem’s constraints.
In the simplex method, an infeasible solution is indicated by looking at the final tableau
Whenever the optimality criteria is satisfied but still there exist an artificial variable in the basis
or solution mix, this is the indication of infeasibility.

Example: Minimization Case

C 5 8 0 0 M
Basic V. X1 X2 S1 S2 A2 Quantity
X1 5 1 1 -2 3 0 200
X2 8 0 1 1 2 0 100
A2 M 0 0 0 -1 1 20
Z 5 13 2 31-M M 1800 +
C-Z 0 -5 -2 -31 +M 0 200M

Even though all Cj - Zj are positive or 0(i.e. the criterion for an optimal solution in a
minimization case), no feasible solution is possible because an artificial variable (A2) remains
in the solution mix.
2. Unbounded Solution
No finite solution may exist in problems that are not bounded. This means that a variable can be
infinitely large without violating a constraint. In the simplex method, the condition of
unboundedness will be discovered prior to reaching the final tableau. We will note the problem
when trying to decide which variable to remove from the solution mix.
The procedure in unbounded solution is to divide each quantity column number by the
corresponding pivot column number. The row with the smallest positive ratio is replaced. But if
the entire ratios turn out to be negative or undefined, it indicates that the problem is unbounded.
Note: A negative ratio means that increasing that variable would increase resources. A zero ratio
means that increasing the variable would not use any resources.
Example: Maximization case

C 6 9 0 0
Basic V. X1 X1 S1 S2 Quantity
X2 9 -1 1 2 0 30 30/-1 = -30
S2 0 -2 0 -1 1 10 10/-2 = -5

26 | P a g e
 Z -9 9 18 0 270
C-Z 15 0 -18 0

The solution in the above case is not optimal because not all Cj - Zj entries are 0 or negative, as
required in a maximization problem. The next variable to enter the solution should be [Link]
determine which variable will leave the solution, we examine the ratios of the quantity column
numbers to their corresponding numbers in the X1 or pivot column. Since both pivot column
numbers are negative, an unbounded solution is indicated. Note: When unbounded solutions
occur, no outgoing variable will exist.

3. Degeneracy: /Tie for leaving basic variable (key row)/

If there is a tie for the smallest ratio, this is a signal that degeneracy exists. Degeneracy can occur
right in the first (initial tableau). This normally happens when the number of constraints is less
than the number of variables in the Linear Programming model. Such problems can be overcome
by trial and error method. If this is resolved by a proper selection of the key element,
degeneracy can be avoided. The main drawback to degeneracy is the increase in the computation,
which reduces the efficiency of the simplex method considerably.

Example:

C 5 8 2 0 0 0
Basic V. X1 X2 X3 S1 S2 S3 Quantity Ratio
X2 8 ¼ 1 1 -2 0 10 10/1/4 = 40
S2 0 4 0 1/3 -1 1 20 20/4 = 5
S3 0 2 0 2 2/5 0 10 10/2 = 5
Z 2 8 8 16 0 0 80
C-Z 3 0 -6 -16 0 0

Degeneracy could lead to a situation known as cycling, in which the simplex algorithm
alternatives back and forth between the same non-optimal solutions, i.e., it puts a new variable
in, then takes it out in the next tableau, puts it back in, and so on.
One simple way of dealing with the issue is to select either row (S2 or S3 in this case) arbitrary. If
we are unlucky and cycling does occur, we simply go back and select the other row. However,
the number of iterations required to arrive at the optimal solution can be minimized by adopting
the following rule:
 Divide the coefficient of slack variables in the simplex table where degeneracy is
detected by the corresponding positive numbers of the key column in the row, starting
from left to right.
 The row which contains smallest ratio comparing from left to right column wise becomes
the key row.
For the above example:
27 | P a g e
 Column
Row s2 s3
s2 1 0
s3 0 1
Divide the coefficients by the corresponding element of the key column, we obtain the
following:
Column
Row s2 s3

s2 ¼= ¼ 0/4=0

s3 0/2 =0 ½=1/2

Comparing the ratios from left to right column wise until they are not equal, the minimum ratio
occurs for the second row (0). Therefore, s3 is selected to leave the basis.
Note: When there is a tie between a slack and artificial variable to leave the basis, the preference
shall be given to artificial variable to leave the basis and there is no need to apply the procedure
for resolving such cases.
 Two incoming Variables / Or Tie for entering variables/
In order to break this tie, the selection for the key column (entering variable) can be made
arbitrary. However; the number of solution can be minimized by adopting the following rules:
1. If there is a tie between two decision variables, then the selection can be made arbitrary.
2. If there is a tie between a decision variable and a slack (or surplus) variable, then select the
decision variable to enter into basis first.
3. If there is a tie between slack or surplus variable, then selection can be made arbitrary.

4. Multiple Optimum Solution

This situation occurs when there can be infinite number of solutions possible for a given
problem. This situation can be recognized in a simplex method when one of the non-basic
variables in the Cj-Zj, row have a value of zero. This is to mean in the optimal solution when non
basic variable (variable not in the basis) has a zero value in C-Z row, this is the indication of
existence of multiple solution. To obtain the other solution, we will make a non- basic variable
with a zero C-Z value to enter in to the basis and solve in the same way as the one we did in the
previous discussion.
Example: Maximization problem

C 3 2 0 0
Basic V. X1 X2 S1 S2 Quantity
X2 2 3/2 1 1 0 6
S2 0 1 0 ½ 1 3
Z 3 2 2 0 12
C-Z 0 0 -2 0

Max Z=3X1+2X2

28 | P a g e
X1=0, X2=6, S2=3 and Max Z=12 or: X1=3, X2=3/2 and Max Z=12
The Cj - Zj value of the non-basic variable (X1) is 0. Thus, this shows the existence of alternative
optimal solution.

29 | P a g e