Linear Programming Problem:

Linear programming is a mathematical technique for finding optimal solutions

to problems that can be expressed using linear equations and inequalities. If a real-
world problem can be represented accurately by the mathematical equations of a linear
program, the method will find the best solution to the problem. Of course, few
complex real-world problems can be expressed perfectly in terms of a set of linear
functions. Nevertheless, linear programs can provide reasonably realistic
representations of many real-world problems — especially if a little creativity is
applied in the mathematical formulation of the problem.

“A mathematical method to allocate scarce resources to competing activities in an

optimal manner when the problem can be expressed using a linear objective function
and linear inequality constraints.”

“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.”

A linear programming problem is one in which we have to find optimal value

(maximum or minimum) of a linear function of several variables (called objective
function) subject to certain conditions that the variables are non-negative and
satisfying by a set of linear inequalities with variables, are sometimes called division
variables.

Terms of Linear Programming Problem

There exist specific terms (or terminology) while constructing and solving linear
programming problems. Let us define some of the important terms which we shall be
using here.
1. Objective function: A linear function of the form Z = ax + by, where a and b are
constant, which has to be minimized or maximized is called a linear objective
function.
Consider an example, Z = 175x + 150y.
This is a linear objective function. The variables x and y are called decision
variables.
2. Constraints: The linear inequalities or equations or restrictions on the variables
of LPP (linear programming problem) are called constraints. The conditions x ≥ 0,
y ≥ 0 are called non-negative restrictions.
For example, 5x + y ≤ 100; x + y ≤ 60 are constraints.
3. Optimization problem: A problem which seeks to maximize or minimize a linear
function (say of two variables x and y) subject to certain constraints as determined
by a set of linear inequalities is called an optimization problem. Linear
programming problems are special types of optimization problems.
4. Feasible region: The common region determined by all the given constraints
including non-negative constraints (x ≥ 0, y ≥ 0) of a linear programming problem
 is called the feasible region (or solution region) for the problem. The region other
than feasible is called an infeasible region.
5. Feasible solutions: These are the points within and on the boundary of the
feasible region represent feasible solutions of the constraints. Any point outside
the feasible region is called an infeasible solution.
6. Optimal (or feasible) solution: Any point in the feasible region that gives the
optimal value (maximum or minimum) of the objective function is called an
optimal solution.
7. Standard Form: A LPP in which all constraints are written in equalities.
8. Slack Variable: A variable added to the LHS of “less than or equal to”
constraint to convert the constraint into an equality. Value of slack variable
indicates unused resources.
9. Surplus Variable: A variable subtracted from the LHS of “more than or equal
to” constraint to convert the convert the constraint into an equality. Value of
surplus variable indicates consumption over & above minimum requirements.
10. Simplex Tableau: A table used to keep record of the calculation made at
each iteration.
11. Basis: The set of variables which are not restricted to equal zero in the
current basic solution. The variables which make up the basis are called Basic
variables. The remaining are called non-basic variables.
12. Iteration: The steps performed in simplex method to progress form one
feasible solution to another.
13. Cj Row: A row in the simplex table which contains the coefficients (unit
profit) of the variables in the Objective function.
14. Zj Row: A row in the simplex tables whose elements represent the increase
/ decrease in the value of objective function; if one unit of that variable is brought
into the solution.
15. (Cj-Zj/Zj – Cj Row (Index Row): A row in the simplex table whose elements
represent net contribution / loss per unit if one unit of that variable is brought into
the solution.
16. Key column: The column with the largest positive / negative index
number. It indicates the Entering variable in the Basis.
17. Key row: The row with the smallest positive ratio found by dividing Quantity
column values by Key column values for each row. It indicates the Exiting
variable from the Basis.
18. Key element: The element at the intersection of Key row & Key column.
 In an LPP, the equations or inequalities are of the linear formlike
a11 x1 +a12 x2 + …+ a1n xn = b1
or
a11 x1 + a12 +…+ a1n xn >= b1
or
In general

where aij, bi, and cj are given constants. aij are coefficients ofdecision variables x’s,
bi are constraints values and cj are coefficients associated to objective function z
An example problem in formulated form

PROPERTIES 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.
Let us consider a product mix problem and see the applicability of the above
properties.

Example:

A company manufactures two products X and Y, which require, the following

resources. The resources are the capacities machine M1, M2, and M3. The
available capacities are 50,25,and 15 hours respectively in the planning period.
Product X requires 1 hour of machine M2 and 1 hour of machine M3. Product Y
requires 2 hours of machine M1, 2 hours of machine M2 and 1 hour of machine M3.
The profit contribution of products X and Y are Rs.5/- and Rs.4/- respectively.

The contents of the statement of the problem can be summarized as

follows:

Machines Products Availability in hours

X Y
M1 0 2 50
M2 1 2 25
M3 1 1 15
Profit in Rs. Per unit 5 4
In the above problem, Products X and Y are competing candidates or variables.
Machine capacities are available resources. Profit contribution of products X
and Y are given.
Now let us formulate the model.
Let the company manufactures x units of X and y units of Y. As the profit
contributions of X and Y are Rs.5/- and Rs. 4/- respectively. The objective of the
problem is to maximize the profit Z, hence objective function is:

Maximize Z = 5x + 4y OBJECTIVE FUNCTION.

This should be done so that the utilization of machine hours by products x and
y should not exceed the available capacity. This can be shown as follows:
For Machine M1 0x + 2y 

For Machine M2 1x + 2y  25 LINEAR STRUCTURAL CONSTRAINTS

For machine M3 1x + 1y 

But the company can stop production of x and y or can manufacture any
amount of x and y. It cannot manufacture negative quantities of x and y. Hence we
have write,
Both x and y are  0 NON -NEGATIVITY CONSTRAINT
As the problem has got objective function, structural constraints, and non-
negativity constraints and there exist a linear relationship between the variables and
the constraints in the form of inequalities, the problem satisfies the properties of
the Linear Programming Problem.

Example:

A small business makes 3-speed and 10-speed bicycles at two different

factories. Factory A produces 16 3-speed and 20 10-speed bikes in one day
while factory B produces 12 3-speed and 20 10-speed bikes daily.
It costs $1000/day to operate factory A and $800/day to operate factory B. An
order for 96 3-speed bikes and 140 10-speed bikes has just arrived.
How many days should each factory is operated in order to fill this order at a
minimum cost? What is the minimum cost?
x = # days factory A is operated
y = # days factory B is operated

Minimize Z = 1000x + 800y

Sub to:
16x + 12y ≥ 96
20x + 20y ≥140
x ≥ 0, y ≥ 0

Methods for the solution of a linear programming problem

Linear Programming, is a method of solving the type of problem in which two or
more candidates or activities are competing to utilize the available limited
resources, with a view to optimize the objective function of the problem. The
objective may be to maximize the returns or to minimize the costs. The various
methods available to solve the problem are:
1. The Graphical Method when we have two decision variables in the
problem. (To deal with more decision variables by graphical method will
become complicated, because we have to deal with planes instead of
straight lines. Hence in graphical method let us limit ourselves to two
variable problems.
2. The Systematic Trial and Error method, where we go on giving various
values to variables until we get optimal solution. This method takes too
much of time and laborious, hence this method is not discussed here.
3. The Vector method. In this method each decision variable is considered
 as a vector and principles of vector algebra is used to get the optimal
solution. This method is also time consuming, hence it is not discussed
here.
4. The Simplex method. When the problem is having more than two decision
variables, simplex method is the most powerful method to solve the
problem. It has a systematic programme, which can be used to solve the
problem.
Simplex Method

INTRODUCTION
As discussed earlier, there are many methods to solve the Linear
Programming Problem, such as Graphical Method, Trial and Error method, Vector
method and Simplex Method. Though we use graphical method for solution when
we have two problem variables, the other method can be used when there are more
than two decision variables in the problem. Among all the methods, SIMPLEX
METHOD is most powerful method. It deals with iterative process, which
consists of first designing a Basic Feasible Solution or a Programme and proceed
towards the OPTIMAL SOLUTION and testing each feasible solution for
Optimality to know whether the solution on hand is optimal or not. If not an
optimal solution, redesign the programme, and test for optimality until the test
confirms OPTIMALITY. Hence we can say that the Simplex Method depends on
two concepts known as Feasibility and optimality.
The simplex method is based on the property that the optimal solution to a
linear programming problem, if it exists, can always be found in one of the basic
feasible solution. The simplex method is quite simple and mechanical in nature.
The iterative steps of the simplex method are repeated until a finite optimal
solution, if exists, is found. If no optimal solution, the method indicates that no
finite solution exists.
COMPARISION BETWEEN GRAPHICAL AND SIMPLEX METHODS
1. The graphical method is used when we have two decision variables in the
problem. Whereas in Simplex method, the problem may have any number
of decision variables.
2. In graphical method, the inequalities are assumed to be equations, so as to
enable to draw straight lines. But in Simplex method, the inequalities are
converted into equations by:
(i) Adding a SLACK VARIABLE in maximisation problem and
subtracting a SURPLUS VARIABLE in case of minimisation
problem.
 Example:

Max Z = 12x1+16x2
Sub to
10x1+20x2 ≤ 120
8x1+8x2 ≤ 80
x1,x2 ≥ 0
Introduce non negative slack variables S1 and S2 to convert given LP
problem into standard form.

Max Z = 12x1+16x2 + 0S1+0S2

Sub to

10x1+20x2 + S1 = 120

8x1+8x2 + S2 = 80

x1,x2,S1,S2 ≥ 0

1 1
Cj 2 6 0 0
CB X X S S solutio
j BV 1 2 1 2 n Min ratio
1 2 120/20=
0 S1 0 0 1 0 120 6
0 S2 8 8 0 1 80 80/8=10
Zj 0 0 0 0
Cj- 1 1
Zj 2 6 0 0

1
Cj 12 6 0 0
CB s solutio
j BV x1 x2 s1 2 n Min ratio
1/ 1/2 6/(1/2)=1
16 X2 2 1 0 0 6 2
 0 S2 4 0 -2/5 1 32 32/4= 8
1
Zj 8 6 4/5 0
Cj-
Zj 4 0 -4/5 0

New R2= Old R2- corresponding key element (new Key Row)
8 – 8 (1/2) = 8-4= 4
8 – 8 (1) = 8-8= 0
0 – 8 (1/20) = 0-8/20= -2/5
1 – 8 (0) = 1-0= 1
80 – 8 (6 ) =80- 48= 32

1 1
Cj 2 6 0 0
CB X X solutio Min
j BV 1 2 S1 S2 n ratio
-
16 X2 0 1 1/10 1/8 2
-
12 X1 1 0 1/10 1/4 8
1 1
Zj 2 6 2/5 1
Cj-
Zj 0 0 -2/5 -1

New R1= Old R1- corresponding key element (Key Row)

½ - ½ (1) = 0
1 – ½ (0) = 1
1/20 – ½ (-1/10) = 1/10
0 – ½ (1/4) = -1/8
6 – ½ (8) = 2
X1=8, x2= 2
Max Z = 12X1+16X2
12(8)+16(2) =96+32 =128
 Example:

Max Z = 12x1+16x2
Sub to
10x1+20x2 ≤ 120
8x1+8x2 ≤ 80
x1,x2 ≥ 0
Introduce non negative slack variables S1 and S2 to convert given LP
problem into standard form.

Max Z = 12x1+16x2 + 0S1+0S2

Sub to

10x1+20x2 + S1 = 120

8x1+8x2 + S2 = 80

x1,x2,S1,S2 ≥ 0

Cj 12 16 0 0
CBj BV X1 X2 S1 S2 solution Min ratio
0 S1 10 20 1 0 120 120/20=6
0 S2 8 8 0 1 80 80/8=10
Zj 0 0 0 0
Cj-Zj 12 16 0 0

Cj 12 16 0 0
CBj BV x1 x2 s1 s2 solution Min ratio
16 X2 1/2 1 1/20 0 6 6/(1/2)=12
0 S2 4 0 -2/5 1 32 32/4= 8
Zj 8 16 4/5 0
Cj-Zj 4 0 -4/5 0
 New R2= Old R2- corresponding key element (new Key Row)

8 – 8 (1/2) = 8-4= 4
8 – 8 (1) = 8-8= 0
0 – 8 (1/20) = 0-8/20= -2/5
1 – 8 (0) = 1-0= 1
80 – 8 (6 ) =80- 48= 32

Cj 12 16 0 0
solutio
CBj BV X1 X2 S1 S2 n Min ratio
16 X2 0 1 1/10 -1/8 2
12 X1 1 0 -1/10 1/4 8
Zj 12 16 2/5 1
Cj-Zj 0 0 -2/5 -1

New R1= Old R1- corresponding key element (Key Row)

½ - ½ (1) = 0
1 – ½ (0) = 1
1/20 – ½ (-1/10) = 1/10
0 – ½ (1/4) = -1/8
6 – ½ (8) = 2
X1=8, x2= 2
Max Z = 12X1+16X2
12(8)+16(2) =96+32 =128

Unbounded solution

Under the Simplex Method, an unbounded solution is indicated when there

are no positive values of Replacement Ratio (Minimum ratio) i.e. Replacement ratio
values are either infinite or negative. In this case there is no outgoing variable.
 An unbounded solution of a linear programming problem is a situation where
objective function is infinite. A linear programming problem is said to have
unbounded solution if its solution can be made infinitely large without violating any
of its constraints in the problem. Since there is no real applied problem which has
infinite return, hence an unbounded solution always represents a problem that has
been incorrectly formulated.
Max Z = 2x1+3x2 + 4X3
Sub to
-x1-5x2-9X3 ≤ 2
3x1-x2 +X3 ≤ 10
2x1+3x2-7X3 ≤ 0
x1,x2,X3 ≥ 0
Introduce non negative slack variables S1, S2 & S3 to convert given
LP problem into standard form.
Max Z = 2x1+3x2 + 4X3 +0S1+0S2+0S3
Sub to
-x1-5x2-9X3+S1 =2
3x1-x2 +X3+S2 = 10
2x1+3x2-7X3 +S3= 0
x1,x2,X3,S1,S2,S3 ≥ 0

Cj 2 3 0 0 0
4
CB S S2 solutio
j BV X1 X2 X3 1 S3 n Min ratio
0 S1 -1 -5 -9 1 0 0 2 2/-9
0 S2 3 -1 1 0 1 0 10 10/1=10
0 S3 2 3 -7 0 0 1 0 0/-7
Zj 0 0 0 0 0 0
Cj- 0 0
Zj 2 3 4 0

Cj 2 3 4 0 0 0
CB BV X1 X2 X S S S solutio Min ratio
 j 3 1 2 3 n

- 1 9 92/-
0 S1 26 14 0 0 92 14
4 X3 3 -1 1 0 1 0 10 10/-1
0 S3 23 -4 0 0 7 1 70 70/-4
Zj 12 -4 4 0 4 0
Cj- - 0 -4 Solution is
Zj 10 7 0 0 Unbounded

New R1= Old R1- corresponding key element (new key row)
-1 – (-9) 3 = 26
-5 – (-9) -1 = -14
-9 – (-9) 1 = 0
1 – (-9) 0 = 1
0 – (-9) 1 = 9
0 – (-9) 0= 0
2 – (-9) 10 = 92

New R3= Old R3- corresponding key element (new key row)
2 – (-7) 3 = 23
3 – (-7) -1 = -4
-7 – (-7) 1 = 0
0 – (-7) 0 = 0
0 – (-7) 1 = 7
1 – (-7) 0 = 1
0 – (-7) 10 = 70

Max Z = 4x1+3x2
Sub to
x1 ≤ 5
 x1-x2 ≤ 8
x1,x2 ≥ 0

Introduce non negative slack variables S1, S2 & S3 to convert given

LP problem into standard form.

Max Z = 4x1+3x2 +0S1+0S2

Sub to
x1 +S1 =5
x1-x2 +S2 = 8
x1,x2,S1+S2 ≥ 0

Solutio
Cj 4 3 0 0 Min ratio
n

CBj BV X1 X2 S1 S2

0 S1 1 0 1 0 5 5/1=5

0 S2 1 -1 0 1 8 8/1= 8

Zj 0 0 0 0

Cj-Zj 4 3 0 0

Solutio
Cj 4 3 0 0 Min ratio
n
 CBj BV X1 X2 S1 S2

4 X1 1 0 1 0 5 5/0 = ∞

0 S2 0 -1 -1 1 3 3/-1= -3

No variable is ready
Zj 4 0 4 0
to leave the basis

Solution is
Cj-Zj 0 3 -4 0
Unbounded

New R2= Old R2- corresponding key element (new key row)
1 – 1 (1) = 0
-1 – 1 (0) = -1
0 – 1 (1) = -1
1 – 1(0) = 1
8 – 1 (5) = 3

Multiple Optimal Solutions

The concept of multiple optimal solutions is associated with the linear programming
problems. The multiple optimal solutions will arise in a linear program with more than
one set of basic solutions that can minimize or maximize the required objective
function. Sometimes, the multiple optimal solutions are called the alternative basic
solution.

In case of the simplex method, the presence of multiple optimal solutions is specified
by a condition under which a Decision variable (non-basic variable) in the last
simplex table displays the optimal solution to the problem and the net amount of
contribution is zero.

After reaching the optimality, if at least one of the Decision variable (non-basic
variable) possess a zero value in Cj-Zj the multiple optimal solutions exist.
Max Z = 3X1+6X2
Sub to
X1+X2 ≤ 5
X1+2X2 ≤ 6
X1,X2 ≥ 0
Max Z = 3X1+6X2 + 0S1+0S2
Sub to
X1+X2 +S1 = 5
X1+2X2 +S2 = 6
X1,X2,S1,S2 ≥ 0

Solutio
Cj 3 6 0 0 Min ratio
n

CBj BV X1 X2 S1 S2

0 S1 1 1 1 0 5 5/1= 5

0 S2 1 2 0 1 6 6/2= 3

Zj 0 0 0 0

Cj-Zj 3 6 0 0

Cj 3 6 0 0 Solutio Min ratio

 n

CBj BV X1 X2 S1 S2

0 S1 1/2 0 1 -1/2 2 2/(1/2) = 4

6 X2 1/2 1 0 1/2 3 3/(1/2) = 6

Zj 3 6 0 3

Cj-Zj 0 0 0 -3

New R1= Old R1- corresponding key element (new key row)
1 – 1(1/2) =1/2
1 – 1 (1) = 0
1 – 1 (0) = 1
0 – 1 (1/2) = -1/2
5 – 1 (3) = 2
X1 = 0, X2 = 3

Max Z = 3X1+6X2
Max Z = 3(0)+6(3)
Max Z = 18

Solutio
Cj 3 6 0 0 Min ratio
n

CBj BV X1 X2 S1 S2

3 X1 1 0 2 -1 4

6 X2 0 1 -1 1 1

Zj 3 6 0 3

Cj-Zj 0 0 0 -3
 New R2= Old R2- corresponding key element (new key row)
½ - ½ (1) = 0
1 - ½ (0) = 1
0 - ½(2) = -1
½ - ½(-1) = 1
3 - ½(4) = 1

X1= 4 , X2 = 1

Max Z = 3X1+6X2

Max Z = 3(4) + 6 (1)

Max Z = 18

DEGENERACY

Under Simplex Method, degeneracy occurs, where there is a Tie for the
minimum positive replacement ratio for selecting Leaving variable
(outgoing variable).

Cj 12 16 0 0
CBj BV X1 X2 S1 S2 solution Min ratio
0 S1 10 20 1 0 200 200/20 =10
 0 S2 8 8 0 1 80 80/8 = 10
Zj 0 0 0 0
Cj-Zj 12 16 0 0

Maximize z= 3x1 + 9x2

SUB TO

X1+4X2 ≤ 8
X1+2X2 ≤4
X1,X2 ≥ 0

Maximize z= 3x1 + 9x2 +0S1+0S2

SUB TO

X1+4X2 +S1= 8
X1+2X2 + S2= 4
X1,X2,S1,S2 ≥ 0

Solutio
Cj 3 9 0 0 Min ratio
n

CBj BV X1 X2 S1 S2

0 S1 1 4 1 0 8 8/4= 2

0 S2 1 2 0 1 4 4/2= 2

Zj 0 0 0 0
 Cj-Zj 3 9 0 0

Since min ratio 2 in the last column of above table is not unique,
both the slack variables S1, and S2 may leave the basis. This is an
indication for the existence of degeneracy in the given L.P.
Problem. So we apply the procedure to resolve degeneracy (Tie).
First arrange the column S1 ,S2,X1, X2 in such a way that the initial
identity (basis) matrix appears first. Thus the initial simplex table
becomes.

Solutio
Cj 0 0 3 9 Min ratio
n

CBj BV S1 S2 X1 X2

0 S1 1 0 1 4 8 1/4

0 S2 0 1 1 2 4 0/2= 0

Zj 0 0 0 0

Cj-Zj 0 0 3 9

Which occurs for the second row. Hence S must leave the basic, and the key element is 2 as shown
2

above.

Solutio
Cj 0 0 3 9 Min ratio
n

CBj BV S1 S2 X1 X2

0 S1 1 -2 -1 0 0

9 X2 0 1/2 1/2 1 2
 Zj 0 9/2 9/2 9

Cj-Zj 0 -9/2 -3/2 0

1- 4(0) =1
0 – 4(1/2) = -2
1- 4(1/2) = -1
4- 4(1) = 0
8- 4(2) = 0

X1= 0 X2 = 2
Max Z = 3X1+9X2
Max Z = 3(0)+ 9(2)
MAX Z = 18