CHAPTER TWO - LINEAR PROGRAMMING

Linear Programming is a mathematical process that has been developed to help

management in decision making involving the efficient allocation of scares resources to
achieve a certain objective. The term programming used to identify this technique does not
refer to computer programming but rather to a predetermined set of mathematical steps used
to solve a problem.
In general, linear programming models help managers determine solutions (i.e., make
decisions) for problems that will achieve some objective in which there are restrictions, such
as limited resources or a recipe or perhaps production guidelines. For example, you could
actually develop a linear programming model to help determine a breakfast menu for yourself
that would meet dietary guidelines you may have set, such as number of calories, fat content,
and vitamin level, while minimizing the cost of the breakfast. Manufacturing companies
develop linear programming models to help decide how many units of different products they
should produce to maximize their profit (or minimize their cost), given scarce resources such
as capital, labor, and facilities.
LP is a method for choosing the best alternative from a set of feasible alternatives
To apply LP, the following conditions must be satisfied:
a. Objective Function: Is the goal or objective of a management, stated as an intent to
maximize or to minimize some important quantity such as profits or costs.
b. Constraints: Are limitations or restrictions imposed by the problems. And constraints
include:
1. 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:
 Plant capacity, Raw materials availability, Labor power, Market demand, etc
2. Non-negativity constraints: Are constraints that require the decision variables not to take
on negative values
c. Linearity
The Objective Function and the constraints must be linear in nature in order to have a Linear
Programming Problems (LPP)
d. Feasible alternative
There should be a series of feasible alternative course of action available to the decision-
making determined by resource constraints. Thus, we have to choose the best alternative

1
Linear Programming Problems can be solved by using:
i. The Geometric method called” Graphical Method”
ii. The Algebraic method called” Simplex Method”
2.1. FORMULATION OF LP
In formulating linear programming model, the model developer / Analyst should consider the
assumptions and components of the model.
Assumptions in linear programming problems include:
 Linearity
 Certainty
 Divisibility
 Non-negativity
The basic components of an LP Model are the following:
 Decision variable
 Objective function
 Constraints
Decision variables: are the variables whose values are unknown and are searched Decision
variables are mathematical symbols that represent levels of activity.

Objective function is a linear mathematical relationship that describes the objective of the
firm in terms of the decision variables. The objective function always consists of either
maximizing or minimizing some value (e.g., maximization of the profit or minimization of the
cost of producing radios). The objective function is a linear relationship that reflects the
objective of an operation.

Constraints: The model constraints are also linear relationships of the decision variables;
they represent the restrictions placed on the firm by the operating environment. The
restrictions can be in the form of limited resources or restrictive guidelines. For example, only
40 hours of labor may be available to produce radios during production. The actual numeric
values in the objective function and the constraints, such as the 40 hours of available labor,
are parameters. Parameters are numerical values that are included in the objective functions
and constraints.

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.

2
Example:
Max.Z  50 X 180 X 2
St :
X 12 X 2 32
X 12 X 2 82
X1, X 2  0

2.2. GRAPHICAL SOLUTION

To use the graphic method, the following steps are needed:
1. Identify the problem
i.e.: The decision variables, the objective function and the constraints
2. Draw a graph including all the constraints and identify the feasible region
3. Obtain a point on the feasible region that optimizes the objective function-Optimal
solution
4. Interpret the results
 Graphical LP is a two-dimensional model.
A Maximization Problem
==>Maximize Z with inequalities of constraints in < form
Example: 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 and $250 from 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.
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 (x1) model b (x2) Maximum Available hrs.
Labor hr. 2 1 40
Machine hr. 1 3 45
Marketing hr. 1 0 12
Profit $300 $250

Solution
1. Formulation of mathematical modeling of LPP
Max Z=300X1 +250X2

3
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 ==> (40, 0) and (20, 0)
X1 +3X2= 45==> (0, 15) and (45, 0)
X1 = 12==> (12, 0)
X1, X2 =0
2X1 +X2 = 40

X2
X1=0
40 X1=12

B
X1 +X2 = 45

15
oo
Feasible C (12, 11)
Region X2=0
X1
D
A 12 20 45
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 point
7. Interpret the result
Corners Coordinates MaxZ=300 X1
+250X2
A (0, 0) $0
B (0, 15) $3750
C (12, 11) $6350
D (12, 0) $3600

4
Interpretation:
12 units of product A and 11 units of product B should be produced so that the total profit will
be $6350.
Exercise:
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
3labor-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.
Let X1 =The No of REGULAR tents produced per week.

5
 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 :
X 12 X 2 32 ……….Cutting department constraint
LPP Model
X 14 X 2 82
……….Assembly department constraint
X 2  12
X1, X 2  0
……….Demand constraint

Corners Coordinates MaxZ=50 X1 +800X2

A o (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.

B Minimization Problem
==>Minimize Z with inequalities of constraints in > form
Example:
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

6
 Solution
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_______

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
X1, 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
X2
X1 =0
A (0, 20/3)

Feasible Region

B (2.5, 3.33)
X2 =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
Then X1 = 2.5, X2 =3.33 and Min Z= 162.5

7
2.3. SPECIAL CASES IN GRAPHICS METHODS
1. Redundant Constraint
If a constraint when plotted on a graph doesn’t form part of the boundary making the feasible
region of the problem that constraint is said to be redundant.
Example:
A firm is engaged in producing two products A and B .Each unit of product A requires 2Kg of
raw material and 4 labor-hrs for processing. Where as each unit of product B requires 3Kg of
raw materials and 3hrs of labor. Every unit of product A requires 4 hrs for packaging where as
B needs 3.5hrs. Every week the firm has availability of 60Kg of raw material, 96 labor-hours
and 105 hrs in the packaging department.
[1 unit of product A sold yields $40 profit and 1 unit of B sold yields $35 profit.
Required:
a. Formulate this problem as a LPP
b. Find the optimal solution
Solution
__________________________________________________________________
Products Resource available
Resources A B per week
__________________________________________________________________
Raw materials (Kg) 2 3 60
Labor (hr) 4 3 96
Packaging (hr) 4 3.5 105
Profit per unit $40 $35

Let X1 =The No of units of product A produced per week

X2 =The No of units of product B produced per week
a. LPP Model

Max.Z  40 X 135 X 2
St :
2 X 13 X 2 60
4 X 13 X 2 96
4 X 1  3.5 X 2  105
X1, X 2  0

8
X2

(0, 32)

Labor: 4X1 +3X2 = 96

(0, 30)
Packaging: 4X1 +3.5X2 = 105
(0, 20) C (18,8)
Raw material: 2X1 +3X2 = 60
FR
X1
A (0, 0) D (24, 0) (26, 0) (30, 0)

 The packaging hr is redundant.

Corners Coordinates MinZ=40 X1 + 35X2

A (0, 0) 0
B (0, 20) 700
C (18, 8) 1000
D (24, 0) 960
X1 =18
X2=8 and
MinZ= 1000

Interpretation:
The company should produce and sale 18 units of product A and 8 units of product B per
week so as to get a maximum profit of 1000.
 By this production plan the entire raw material will be consumed.
 2X1 +3X2 <60
2(18) +3(8) =60
60=60==> No idle or unused raw material
 4X1 +3X2 <96
4(18) +3(8) <96
96=96 ==>the entire labor hour will be consumed
 4X1 +3.5X2 <105
100<105==>There is to be idle or unused capacity of 5hrs in the packaging department.
Note: The packaging hour’s constraint does not form part of the boundary making the feasible
region. Thus, this constraint is of no consequence and is therefore, redundant. The inclusion
or exclusion of a redundant constraint does not affect the optimal solution of the problem.

9
2. Multiple optimal Solutions
/Alternative optimal solutions/
-This is a situation where by a LPP has more than one optimal solution.
Multiple optimal Solutions will be found if two corners give optimal solution, then the line
segment joining these points will be the solution.
==>We have unlimited number of optimal solution without increasing or decreasing the
objective function.
Example:
The information given below is for the products A and B.
_____________________________________________________________________
Machine hours per week Maximum available
Department Product A Product B per week
_________________________________________________________________

Cutting 3 6 900
Assembly 1 1 200
Profit per unit $8 $16
_____________________________________________________________________
Assume that the company has a marketing constraint on selling products B and therefore it
can sale a maximum of 125units of this product.
Required:
a. Formulate the LPP of this problem
b. Find the optimal solution
Solution:
Let X1 =The No of units f product A produced per week
X2 =The No of units f product B produced per week
a. The LPP Model of the problem is:

Max.Z  8 X 116 X 2
St :
3 X 16 X 2 900
X 1 X 2 200
X 2  125
X1, X 2  0

10
 X2
X1=0
(0, 200)

(0,150) C (50, 125) X2=125 Marketing equation

B (0, 125)
D (100,100)
Cutting: 3X1+6X2=900

FR X2=0

A (0, 0) X1
(300,0)

Corners Coordinates MaxZ=8 X1 + 16X2

A (0, 0) 0
B (0, 125) 2000
C (50, 125) 2400
D (100, 100) 2400
E (200, 100) 1600
Interpretation:
Both C and D are optimal solutions. Any point on the line segment CD will also lead to the
same optimal solution.
==>Multiple optimal solutions provide more choices for management to reach their
objectives.
3. Infeasible Solution
A solution is called feasible if it satisfies all the constraints and the constraints and non-
negativity condition. However, it is sometimes possible that the constraints may be
inconsistent so that there is no feasible solution to the problem. Such a situation is called
infeasibility.
Example:
MaxZ=20X1+30X2
St:
2X1+X2< 40
4X1+X2< 60
X1 > 30
X1, X2 > 0

11
 Solution:

X2 X1=0
(0, 60) X1=30
4X1+X2= 60
(0, 40)

2X1+X2= 40
X2=0
X1
(15, 0) (20, 0) (30, 0)

Note:
-In the above graph, there is no common point in the shaded area.
-All constraints cannot be satisfied simultaneously and there is no feasible solution to the
problem.
4. Unbounded Solution
When the value of decision variables in LP is permitted to increase infinitely without
violating the feasibility condition, then the solution is said to be unbounded .Here, the
objective function value can also be increased infinitely. However, an unbounded feasible
region may yield some definite value of the objective function.
Example Min.Z=3X1+2X2
St:
X1-X2>1
X1+X2>3
X1, X2 > 0
X2

A(0,3) Unbounded

Feasible Region X1-X2=1

B (2, 1)
X1+X2=3

X1

12
Note here that the two corners of the region are A(0,3) and .B(2,1).The value of MaxZ(A)=6
and MaxZ(B)=8. But there exist number of points in the shaded region for which the value of
the objective function is more than 8.For example, the point (10, 12) lies in the region and the
function value at this point is 70 which is more than 8.
Remark:
An unbounded solution does not mean that there is no solution to the given LPP, but implies
that there exits an infinite number of solutions.
2.4 LINEAR PROGRAMMING APPLICATIONS
There are a wide range of problems that lend themselves to solutions by linear programming

techniques. This section briefly describes some of those problem types. The discussion is not

meant to be all inclusive. Rather, its purpose is to give you an indication of the importance of

LP techniques for managerial decision making and apparent diversity of situations to which

linear programming can be applied.

 Product Mix
Organizations often produce similar products or offer similar services that use the same

resources (for example, labor, equipment time, materials). Because of limits in the amounts of

these resources that are available during any time period, a decision must be concerning how

much of each product or service to produce or make availability during the time period that

will be consistent with the goals of the organization. The basic question that can be answered

using linear programming is: What mix of output (or service) will maximize profit (revenue,

etc) given the availability of scarce resources? Illustration one described in this unit is an

example of a product mix problem.

 Diet Problems
This type of problem usually involves the mixing of raw materials or other ingredients to

obtain an end product that has certain characteristics. For instance, food processors and

dieticians generally are concerned with meeting dietary needs in food products. There may be

specific requirements pertaining to nutrients, calories, sodium content, and so on. The general

13
question to be answered by linear programming is: What mix of inputs (eg. different food

problem.

 Blending Problems
Blending problems are very similar to a diet problems. In fact, diet and blending problems

could be lumped into the same category. Strictly speaking, though, blending problems have an

additional requirement: to achieve a mix that has a specific consistency, as illustrated in the

next example.

 Portfolio Selection
These problems generally involve allocating a fixed dollar amounts (eg., $100,000) among a

variety of investments, such as bonds, stocks, real estate and so on. Usually the goal is to

maximize income or total return. The problems taken an added dimension when certain other

requirements are specified (for example, no more than 40% of the portfolio can be invested in

bonds).

2.5 SIMPLEX METHOD

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 1940’s 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 solution each time until the optimal solution is reached at.
Note:
The simplex method starts with a corner that is in the solution space or feasible region and
moves to another corner of the solution space improving the value of the objective function
each time until optimal solution is reached at the optimal corner.
2.5.1 MAXIMIZATION PROBLEMS
 Maximize Z with inequalities of constraints in “< “form
Step 1
Formulate LPP Model

14
Step 2
Standardize the problem
i.e Convert constraint inequality into equality form by introducing a variable called Slack
variable.
Slack Variables:
A sack variable(s) is added to the left hand side of a < constraint to covert the constraint
inequality in to equality. The value of the slack variable shows unused resource. A slake
variable emerges when the LPP is a maximization problem.
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.
Step 3
Obtain the initial simplex tableau
To represent the data, the simplex method uses a table called the simplex table or the simplex
matrix.
==> In constructing the initial simplex tableau, the search for an optimal solution begins at the
origin. Indicating that nothing is produced;
Thus, first assumption, No production implies that x1 =0 and x2=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.
Or: basic variables are variables that are in the basic solution. Basic variables have 0 values in
the Cj-Zj row.
b. Non-basic variables are variables with zero solution values.
Or: non-basic variables are variables that are out of the solution.

==>if we have n=5 variables (x1 , x2, s1, s2, and s3) and m=3 constraints (Labor, machine and
marketing 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

15
Initial simplex tableau EXAMPLE

Solution quantity
variables column
Real or decision
Basic or Solution
variable column
Profit per unit
column

column
Cj 300 250 0 0 0 Profit per unit row
X1 X2 S1 S2 S3
SV Q

R1
0 S1 2 1 1 0 0 40

Constraint R2
0 S2 1 3 0 1 0 45
equation rows
0 S3 1 0 0 0 1 12
R3
Zj 0 0 0 0 0 0 Gross Profit row
Cj - Zj 300 250 0 0 0
Net Profit row
/Indicator row/
Step 4:
Choose the “incoming” or “entering” variables
Note:
The entering variable is the variable that has the most positive value in the Cj - Zj row also
called as indicator row. Or the entering variable is the variable that has the highest
contribution to profit per unit.
a. X1 in our case is the entering variable
b. The column associated with the entering variable is called key or pivot column ( X1
column in our case )
Step 5:
Choose the “leaving “or “outgoing” variable
==> In this step, we determine the variable that will leave the solution for X1 (or entering
variable)
Note:
 The row with the minimum or lowest positive (non-negative) replacement ratio shows the
variable to leave the solution.

Replacement Ratio (RR) = Solution Quantity (Q)

Corresponding values in pivot column

16
Note: RR>0

 The variable leaving the solution is called leaving variable or outgoing variable.
 The row associated with the leaving variable is called key or pivot row (s3 row in our case)
 The element that lies at the intersection of the pivot column and pivot row is called pivot
element(No 1 in our case)
Step 6:
Repeat step 3-5 till optimum basic feasible solution is obtained.
Or: repeat step 3-5 till no positive value occurs in the Cj - Zj row.
Note:
 Divide each element of the pivot row by the pivot element to find new values in the key or
pivot row.
 Perform row operations to make all other entries for the pivot column equal to zero.
Example:
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.1 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
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:
Let X1= the No of bottles of punch A produced.
X2= the No of bottles of punch B produced.

 LPP Model
Max Z=4X1 +3X2
St:
20X1 +10X2 < 230 Orange Constraint
5X1 +15X2 < 120 Grape Constraint
X1, X2 > 0 Non-negativity constraint
 Standard form

17
 Max.Z=4x1 +3x2 + 0 s1 +0 s2
St:
20 x1+3x2 + 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 simplex tableau

Cj 4 3 0 0

SV X1 X2 S1 S2 Q

0 S1 20 10 1 0 230

0 S2 5 15 0 1 120
Zj 0 0 0 0 0
Cj - Zj 4 3 0 0

2nd simplex tableau

Cj 4 3 0 0

SV X1 X2 S1 S2 Q

4 X1 1 1/2 1/20 0 11.5

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

Zj 4 2 1/5 0 46
Cj - Zj 0 1 -1/5 0

18
 Cj 4 3 0 0

SV X1 X2 S1 S2 Q

4 X1 1 0 3/50 -1/25 9

0 X2 0 1 -1/50 2/25 5
Zj 4 3 0.12 0.08 51
Cj - Zj 0 0 - 0.12 -0.08

Optimal simplex tableau

X1= 9 bottles of punch A
X2= 5 bottles of punch B
s1 =0
s2 =0 MaxZ=$51

2.5.2 MINIMIZATION PROBLEMS

 Minimize Z with inequalities of constraints in “> “form
There are two methods to solve minimization LP problems:
1. Direct method/Big M-method/
 Using artificial variables
2. Conversion method
 Minimization by maximizing the dual
 Surplus Variable (-s):
 A variable inserted in a greater than or equal to constraint to create equality. It
represents the amount of resource usage above the minimum required usage.
 Surplus variable is subtracted from a > constraint in the process of converting
the constraint to standard form.
 Neither the slack nor the surplus is negative value. They must be positive or
zero.
Example:
1. 2x1+x2 < 40 ==>is a constraint inequality
x1= 12 and x2= 11==> 2x1+x2+s = 40 ==>2(12)+11+s = 40
==> s=5 unused resource
2. 5x1+3x2 < 45
x1= 12 and x2= 11==> 5x1+3x2+s = 45 ==>5(12)+3(11)+s = 45

19
 ==> s=0 unused resource (No idle resource)
3. 5x1+2x2<20
x1= 4.5 and x2= 2==> 5x1+2x2- s = 20 ==>5(4.5)+2(2)-s = 20
==> s=6 unused resource
4. 2x1+x2 >40
x1= 0 and x2= 0(No production)==> 5x1+2x2- s = 20 ==>5(4.5)+2(2)-s = 20
==> s=-6(This is mathematically unaccepted)
Thus, in order to avoid the mathematical contradiction, we have to add artificial variable (A)

 Artificial variable (A):

Artificial variable is a variable that has no meaning in a physical sense but acts as a tool to
create an initial feasible LP solution.
Note:
Type of constraint To put into standard form
< --------------------------------------------- Add a slack variable
= ---------------------------------------------Add an artificial variable
> ---------------------- Subtract a surplus variable and add a slack variable

1. Big M-method
/Charnes Penalty Method/
The Big-M Method is a method 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.

Following are the characteristics of Big-M Method:

a. High penalty cost (or profit) is assumed as M
b. M is assigned as a coefficient to artificial variable A in the objective function Z.
c. Big-M method can be applied to minimization as well as maximization problems with the
following distinctions:
i. Minimization problems
-Assign +M as coefficient of artificial variable A in the objective function Z
ii. Maximization problems:
- Assign–M as coefficient of artificial variable A in the objective function Z
d. Coefficient of S (slack/surplus) takes zero values in the objective function Z

20
e. For minimization problem, the incoming variable corresponds to the highest negative
value of Cj-Zj.
f. Solution is optimal when there is no negative value of Cj-Zj.(For minimization case)

Example:
1. Minimize Z=25x1 +30x2
Subject to:
20x1+15x2 > 100
2x1+ 3x2 > 15
x1, x2 > 0
Solution
Step 1
Standardize the problem
Minimize Z=25x1 +30x2 +0s1+0s2 +MA1+MA2
Subject to:
20x1+15x2- s1+A1 = 100
2x1+ 3x2 –s2+A2 = 15
x1, x2 , s1, s2 ,A1 ,A2 > 0
Step 2
Initial simplex tableau
The initial basic feasible solution is obtained by setting x1= x2= s1= s2=0
No production, x1= x2= s1=0==>20(0) +15(0) - 0+A1 = 100 ==> A1 = 100
x1= x2= s2=0==>0(0)+3(0) - 0+A2 =15==> A2 = 15
Initial simplex tableau

Cj 25 30 0 0 M M

SV X1 X2 S1 S2 A1 A2 Q RR

M A1 20 15 -1 0 1 0 100 100/20=5
Note:
M A2 2 3 0 -1 0 1 15 15/2=7.5

Zj 22M 18M -M -M M 115 M

Cj - Zj 25 -22M 30- 18M M M 0

21
Once an artificial variable has left the basis, it has served its purpose and can therefore be
removed from the simplex tableau. An artificial variable is never considered for re-entry into
the basis.
2nd Simplex Tableau

Cj 25 30 0 0 M

SV X1 X2 S1 S2 A2 Q

25 X1 1 3/4 -1/20 0 0 5

M A2 0 3/2 1/10 -1 1 5 R’1=R1/20

25 75/4+3/2M -5/4+1/10M -M 125+5

Zj
M M
0 45/4-3/2M 5/4-1/10 M M
Cj - Zj
0

3rd Simplex Tableau

Cj 25 30 0 0

SV X1 X2 S1 S2 Q

25 X1 1 0 -1/10 1/2 5/2

30 X2 0 1 1/15 -2/3 10/3

Zj 25 30 -1/2 -15/2 162.5 R’’1=R’1-3/4 R’’2

Cj - Zj 0 0 1/2 15/2

Cj - Zj > 0==>Optimal solution is reached

X1=5/2
X2=10/3 and MinZ=162.5

Note: As long as an “A” variable is available in the solution variable column, the solution is
infeasible.

22
3.3. SPECIAL CASES IN SIMPLEX METHOD
1. 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.
Example: If the equation is max Z:

Cj

SV X1 X2 S1 S3 Q

Zj
Cj - Zj 5 2 5 0

In such a case,X1 is the entering variable

2. Infeasibility
A situation with no feasible solution may exist if the problem was formulated improperly.
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 .In it, all Cj - Zj row entries will be the proper sign to imply optimality, but an
artificial variable (A) will still be in the solution mix.
Example: Minimization case

Cj 5 8 0 0 M

SV X1 X2 S1 S2 A2 Q

5 X1 1 1 -2 3 0 200

8 X2 0 1 1 2 0 100
M A2 0 0 0 -1 1 20
Zj 5 8 -2 31-M 1,800+200M
Cj - Zj 0 0 2 M-31

23
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.
3. Unbounded Solutions
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.
Example: Maximization case

Cj 6 9 0 0

SV X1 X2 S1 S2 Q RR

9 X2 -1 1 2 0 30

0 S2 -2 0 -1 1 10 30/-1=-30

Zj -9 9 18 0 270
Cj - Zj 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
X1.To 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.
 No unbounded solutions, no outgoing variable will exist.

24
 4. Degeneracy
/Tie for leaving basic variable (key row)

5 8 2 0 0 0
Cj

SV X1 X2 X3 S1 S2 S3 Q RR

8 X2 1/4 1 1 -2 0 0 10

0 S2 4 0 1/3 -1 1 0 20
10/1/4=40
0 S3 2 0 2 2/5 0 1 10

Zj 2 8 8 16 0 80

Cj - Zj 3 0 -6 -16 0

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 objective function. Problem can be overcome by
trial and error method.
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.
Remark
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.

25
5. Multiple Optimal Solutions
Multiple optimal solutions exist when non-basic variable contains zero on its Cj - Zj row.

Example:
Maximization problem

Cj 3 2 0 0

SV X1 X2 S1 S2 Q

2 X2 3/2 1 1 0 6

0 S2 1 0 1/2 1 3
3 2 2
Zj 12
0
Cj - Zj 0 0 -2
0
MaxZ=3X1+2X2

X1=0, X2=6, S2=3 and MaxZ=12 or: X1=3, X2=3/2 and MaxZ=12

The Cj - Zj value of the Non-basic variable (X1) is 0.Thus, there is alternative optimal
solution.

26