Linear Programming Problems

&
Solution by Graphical and Algebraic Methods

December 20, 2022

Characteristics of LPPs

I Both Constraints and Objective Function(s) are Linear in nature i.e. no higher
order of decision variables
I Both decision variables and constraint-objective functions are deterministic in
nature
I Decision variables can be of continuous, discrete or mixed types
I Search space is Convex in nature
Assumptions of Linear Programming Problems (LPPs)

I Linearity:
Assumptions of Linear Programming Problems (LPPs)

I Linearity:
I Objective Function(s) and Constraint(s) both are linear
I Contribution of different decision variables will be additive or subtractive in nature - No
interaction term
I Suppose Z = 3x1 + 4x2 , e.g. x1 = 2, x2 = 2 =⇒ Z = 14, x1 = 3, x2 = 2 =⇒ Z = 17 and
so on
Assumptions of Linear Programming Problems (LPPs)

I Linearity:
I Objective Function(s) and Constraint(s) both are linear
I Contribution of different decision variables will be additive or subtractive in nature - No
interaction term
I Suppose Z = 3x1 + 4x2 , e.g. x1 = 2, x2 = 2 =⇒ Z = 14, x1 = 3, x2 = 2 =⇒ Z = 17 and
so on
I Proportionaility:
Assumptions of Linear Programming Problems (LPPs)

I Linearity:
I Objective Function(s) and Constraint(s) both are linear
I Contribution of different decision variables will be additive or subtractive in nature - No
interaction term
I Suppose Z = 3x1 + 4x2 , e.g. x1 = 2, x2 = 2 =⇒ Z = 14, x1 = 3, x2 = 2 =⇒ Z = 17 and
so on
I Proportionaility:
I The contribution of each activity to the value of the objective function and constraint
function RHS value is proportional to the level of activity of a particular decision
valriable
I Suppose, if the contribution of x1 towards profit is 10x1 then the level of contributions
towards profit by x1 will be proportional to its level of activity.
I For x1 = 1, contribution is 10, x1 = 2, contribution is 20 and so on
Assumptions of Linear Programming Problems (LPPs)

I Divisibility:
Assumptions of Linear Programming Problems (LPPs)

I Divisibility:
I Decision variables are allowed to assume any value including non-integer values
unless otherwise stated, satisfying the functional and geometric constraints
I Level of activity of any decision variable may go to fractional level
Assumptions of Linear Programming Problems (LPPs)

I Divisibility:
I Decision variables are allowed to assume any value including non-integer values
unless otherwise stated, satisfying the functional and geometric constraints
I Level of activity of any decision variable may go to fractional level
I Certainty:
I The values assigned to any parameter or decision variable are known to be
deterministic in nature i.e. no uncertainty is considered
Framework of Graphical Method

I Convert all the inequality constraints into equality

Framework of Graphical Method

I Convert all the inequality constraints into equality

I Identify the direction of feasible region in space based on direction of inequalities
Framework of Graphical Method

I Convert all the inequality constraints into equality

I Identify the direction of feasible region in space based on direction of inequalities
1. Any constraint will divide the region into two parts R1 and R2
2. Take any point in either in R1 or R2 and see whether that point staisfies the inequality
or not
Framework of Graphical Method

I Convert all the inequality constraints into equality

I Identify the direction of feasible region in space based on direction of inequalities
1. Any constraint will divide the region into two parts R1 and R2
2. Take any point in either in R1 or R2 and see whether that point staisfies the inequality
or not
I Identify the common region (Feasible Region) based on constraints and their
directions
I Assume the objective function as a line(Iso-profit Line) and traverse it over the
feasible region
1. Traverse the objective function line towards away from zero in case of maximization
2. Traverse the objective function line towards zero in case of minimization
I Evaluate all the corner points of Feasible Region for Objective Function value and
select the point with best Objective Function value as optimal point
Draw Feasible Region

Set I:

5x1 + 10x2 ≤ 50
8x1 + 2x2 ≥ 16
3x1 − 2x2 ≥ 6
x1 , x2 ≥ 0
Draw Feasible Region
Identify the common regions:
10x2

(0, 8)

x1
-2 0 2 4 6 8 10 12
(2, 0)
-2

-4
Draw Feasible Region
Identify the common regions:
10x2

(0, 8)

8x 1 +
2
2x 2 =
x1
16

-2 0 2 4 6 8 10 12
(2, 0)
-2

-4
Draw Feasible Region
Identify the common regions:
10x2

(0, 8)

6
(0, 5)

8x 1 +
2
2x 2 =
x1
16

-2 0 2 4 6 8 10 12
(2, 0) (10, 0)
-2

-4
Draw Feasible Region
Identify the common regions:
10x2

(0, 8)

6
(0, 5)

8x 1 +
5x
2 1 +1
0x
2x 2 = 2 =
50
x1
16

-2 0 2 4 6 8 10 12
(2, 0) (10, 0)
-2

-4
Draw Feasible Region
Identify the common regions:
10x2

(0, 8)

6
6

=2
2x
(0, 5)

−
1
8x 1 +

3x
5x
2 1 +1
0x
2x 2 = 2 =
50
x1
16

-2 0 2 4 6 8 10 12
(2, 0) (10, 0)
-2
(0, −3)
-4
Draw Feasible Region
Identify the common regions:
10x2

(0, 8)

6
6

=2
2x
(0, 5)

−
1
8x 1 +

3x
5x
2 1 +1
0x
2x 2 = 2 =
50
x1
16

-2 0 2 4 6 8 10 12
(2, 0) (10, 0)
-2
(0, −3)
-4
Draw Feasible Region
Identify the common regions:
10x2

(0, 8)

6
6

=2
2x
(0, 5)

−
1
8x 1 +

3x
5x
2 1 +1
0x
2x 2 = 2 =
50
x1
16

-2 0 2 4 6 8 10 12
(2, 0) (10, 0)
-2
(0, −3)
-4
Draw Feasible Region
Identify the common regions:
10x2

(0, 8)

6
6

=2
2x
(0, 5)

−
1
8x 1 +

3x
5x
2 1 +1
0x
2x 2 = 2 =
50
x1
16

-2 0 2 4 6 8 10 12
(2, 0) (10, 0)
-2
(0, −3)
-4
Draw Feasible Region
Identify the common regions:
10x2

(0, 8)

6
6

=2
2x
(0, 5)

−
1
8x 1 +

3x
5x
2 1 +1
0x
2x 2 = 2 =
50
x1
16

-2 0 2 4 6 8 10 12
(2, 0) (10, 0)
-2
(0, −3)
-4
Draw Feasible Region
Depending on the directions of constraints the feasible region is:
10x2

(0, 8)

6
6

2 =
2x
(0, 5)

−1
8x 1 +

3x
5x
2 1 +
10x
2x 2 =
2 =5
0
16
x1
-2 0 2 4 6 8 10 12
(2, 0) (10, 0)
-2
(0, −3)
-4
Draw Feasible Region

Set II:

8x1 + 3x2 ≤ 48
8x1 + 7x2 ≥ 56
x2 ≥ 4x1
x1 , x2 ≥ 0
Draw Feasible Region
Identify the common regions:
x2
16
(0, 16)

14

8x 1
+
3x 2
10

=4
8
(0, 8)

(7, 0)
x1
-2 0 2 4 6 8 10
(6, 0)
Draw Feasible Region
Identify the common regions:
x2
16
(0, 16)

14

8x 1
+
3x 2
10

=4
8
(0, 8)

8x
1
+
7x
2

2
=
56
(7, 0)
x1
-2 0 2 4 6 8 10
(6, 0)
Draw Feasible Region
Identify the common regions:
x2
16
(0, 16)

14

8x 1
+
3x 2
10

=4
8
(0, 8)

4x1
6

x2 =

8x
1
+
7x
2

2
=
56
(7, 0)
x1
-2 0 2 4 6 8 10
(6, 0)
Draw Feasible Region
Identify the common regions:
x2
16
(0, 16)

14

8x 1
+
3x 2
10

=4
8
(0, 8)

4x1
6

x2 =

8x
1
+
7x
2

2
=
56
(7, 0)
x1
-2 0 2 4 6 8 10
(6, 0)
Draw Feasible Region
Identify the common regions:
x2
16
(0, 16)

14

8x 1
+
3x 2
10

=4
8
(0, 8)

4x1
6

x2 =

8x
1
+
7x
2

2
=
56
(7, 0)
x1
-2 0 2 4 6 8 10
(6, 0)
Draw Feasible Region
Identify the common regions:
x2
16
(0, 16)

14

8x 1
+
3x 2
10

=4
8
(0, 8)

4x1
6

x2 =

8x
1
+
7x
2

2
=
56
(7, 0)
x1
-2 0 2 4 6 8 10
(6, 0)
Draw Feasible Region
Identify the common regions:
x2
16
(0, 16)

14

8x 1
+
3x 2
10

=4
8
(0, 8)

4x1
6

x2 =

8x
1
+
7x
2

2
=
56
(7, 0)
x1
-2 0 2 4 6 8 10
(6, 0)
Draw Feasible Region
Identify the common regions:
x2
16
(0, 16)

14

8x 1
+
3x 2
10

=4
8
(0, 8)

4x1
6

x2 =

8x
1
+
7x
2

2
=
56
(7, 0)
x1
-2 0 2 4 6 8 10
(6, 0)
Draw Feasible Region
So, the feasible region is identified as:
x2
16
(0, 16)

14

8x 1
+
3x 2
10

=4
8
(0, 8)

4x1
6

x2 =

8x
1
+
7x
2

2
=
56
(7, 0)
x1
-2 0 2 4 6 8 10
(6, 0)
Example I

Let’s consider the following problem

Example I

Let’s consider the following problem

max Z = 6x1 + 5x2

subject to,
x1 + x2 ≤ 5
3x1 + 2x2 ≤ 12
x1 , x2 ≥ 0
Example I, Contd.
8 x2

6
(0, 6)

3x 1
(0, 5)

+
2x 2
4

=
12
(2, 3)
Feasible

x1
2 Region

+
x2
=
5
0 (5, 0)
x1
-2 (0, 0) 0 2 4 6 8
Example I, Contd.
8 x2

6
(0, 6)

3x 1
(0, 5)

+
2x 2
4

=
12
(2, 3)
Feasible

x1
2 Region

+
x2
=
5
z=

(5, 0)
6x 1

0
x1
+

-2 (0, 0) 0 2 4 6 8
5x 2
Example I, Contd.
8 x2

6
(0, 6)

3x 1
(0, 5)

+
2x 2
4

=
12
(2, 3)
Feasible

x1
2 Region

+
z=

x2
=
6x 1

5
+
5x 2
0 (5, 0)
x1
-2 (0, 0) 0 2 4 6 8
Example I, Contd.
8 x2

6
(0, 6)

3x 1
(0, 5)

+
2x 2
4

=
12
(2, 3)
Feasible

x1
z=
2 Region

+
6x 1

x2
=
+

5
0 5x 2 (5, 0)
x1
-2 (0, 0) 0 2 4 6 8
Example I, Contd.
8 x2

6
(0, 6)

3x 1
(0, 5)

+
2x 2
4

=
12
(2, 3)
Feasible

x1
2 Region

+
z=

x2
=
6x 1

5
+
5x 2
0 (5, 0)
x1

=
25
-2 (0, 0) 0 2 4 6 8
Example I, Contd.
8 x2

6
(0, 6)

3x 1
(0, 5)

+
2x 2
4

=
12
(2, 3)
Feasible

x1
2 Region

+
z=

x2
=
6x 1

5
+
5x 2
0 (5, 0)
x1

=
24
-2 (0, 0) 0 2 4 6 8
Example I, Contd.
8 x2

6
(0, 6)

3x 1
(0, 5)

+
2x 2
4

=
12
(2, 3)
Feasible

x1
2 Region

+
z=

x2
=
6x 1

5
+
5x 2
0 (5, 0)
x1

=
27
-2 (0, 0) 0 2 4 6 8
Example II

Solve the following LPP using Graphical Method.

max Z = 10x1 + 15x2

subject to, 2x1 + x2 ≤ 26
2x1 + 4x2 ≤ 56
x1 − x2 ≥ −5
x1 , x2 ≥ 0
Example II, Contd. x
2
28

24

20

2x 1
+
16

x2 =
26
12 (6, 11)
−
5 (8, 10)
=
x2

8
−

2x
x1

1 +4
x2 =
( 0, 5) Feasible Region 56
4

( 0, 0) (13, 0)
0 x1
-6 -2 2 6 10 14 18 22 26
Example II, Contd. x
2
28

24

20

2x 1
+ x2
16

=2
6
12 (6, 11)
−
5 (8, 10)
=
x2

8
−

2x
x1

1 +4
x2 =
( 0, 5) Feasible Region 56
4
z=
10
x1
+
(0, 0) 15x (13, 0)
0 2 x1
-6 -2 2 6 10 14 18 22 26
Example II, Contd. x
2
28

24

20

2x 1
+ x2
16

=2
6
12 (6, 11)
−
5 (8, 10)
=
x2

8
−

2x
x1

1 +4
x2 =
( 0, 5) z Feasible Region 56
=
4 10
x1
+
15
x2
( 0, 0) (13, 0)
0 x1
-6 -2 2 6 10 14 18 22 26
Example II, Contd. x
2
28

24

20

2x 1
+ x2
16

=2
6
12 (6, 11)
−
5 (8, 10)
=
x2

8
−

z= 2x
x1

10 1 +4
x1 x2 =
( 0, 5) Feasible Region
+ 56
15
4 x 2

( 0, 0) (13, 0)
0 x1
-6 -2 2 6 10 14 18 22 26
Example II, Contd. x
2
28

24

20

2x 1
+ x2
16

=2
6
12 (6, 11)
−
5 (8, 10)
=
x2

8
−

2x
x1

1 +4
x2 =
( 0, 5) 1 Feasible Region 56
0 x1
4 +
15
x2
=
75
( 0, 0) (13, 0)
0 x1
-6 -2 2 6 10 14 18 22 26
Example II, Contd. x
2
28

24

20

2x 1
+ x2
16

=2
6
12 (6, 11)
−
5 (8, 10)
=
x2

8
−

10 2x
x1

x1 1 +4
+ Region x2 =
( 0, 5) Feasible
15 56
x2
4 =
13
0
( 0, 0) (13, 0)
0 x1
-6 -2 2 6 10 14 18 22 26
Example II, Contd. x
2
28

24

20

2x 1
+ x2
16

=2
6
12 (6, 11)
−
5 (8, 10)
=
x2

8 10
−

x1 2
+ x1 + 4
x1

15
( 0, 5) Feasible Region x2 x2 = 5
= 6
22
4 5

( 0, 0) (13, 0)
0 x1
-6 -2 2 6 10 14 18 22 26
Example II, Contd. x
2
28

24

20

2x 1
+ x2
16

=2
6
12 (6, 11)
−
5 (8, 10)
=
x2

8 10
−

x1 2x
+ 1+
x1

15 4x
( 0, 5) Feasible Region x2 2 =
=
23 56
4 0

( 0, 0) (13, 0)
0 x1
-6 -2 2 6 10 14 18 22 26
Example III, Contd.

Solve the following LPP using Graphical Method.

min Z = 20x1 + 40x2

subject to, −3x1 + 4x2 ≤ 12
2x1 + 3x2 ≥ 12
2x1 − x2 ≥ −2
x1 ≤ 4
x2 ≥ 2
x1 , x2 ≥ 0
Example III, Contd.
x2

6 C

x1 = 4
4 B Feasible Region

A
12 2x
= 1 +

−2
4x 2 3x
+ 2 2 = D
x2 =
x 1 E 12 x2 = 2
−3
1 −
2x

O
0 x1
-4 -3 -2 -1 0 1 2 3 4 5 6 7
Example III, Contd.
x2

6 C

x1 = 4
4 B Feasible Region

A
12 2x
= 1 +

2
4x 2 3x
+ 2 =− 2 = D
x 1 E 12 x2 = 2
−3
2
−x

Z=
20x
1
2x

O 1 +
0 x140x
2 =
-4 -3 -2 -1 0 1 2 3 4 5 6 7 140
Excercise-I

Solve the LPP graphically

max Z = 6x1 + 5x2

subject to
3x1 + x2 ≤ 160
x1 ≤ 40
x2 ≤ 130
x1 ≥ 80
x1 , x2 ≥ 0
Excercise-II

Solve the LPP graphically

max Z = 5x1 + 7x2

subject to
2x1 − x2 ≤ −1
−x1 + 2x2 ≤ −1
x1 , x2 ≥ 0
Excercise-III

Solve the LPP graphically

min Z = 15x1 + 30x2

subject to
x1 + 2x2 ≥ 10
2x1 − 3x2 ≤ 6
x1 + x2 ≥ 6
x1 , x2 ≥ 0
Excercise-IV

Solve the LPP graphically

max Z = 8x1 + 16x2

subject to
x1 + x2 ≤ 200
3x1 + 6x2 ≤ 900
x2 ≤ 125
x1 , x2 ≥ 0
Excercise-V

Solve the LPP graphically

max Z = 20x1 + 30x2

subject to
2x1 + x2 ≤ 40
4x1 − x2 ≤ 20
x1 ≥ 30
x1 , x2 ≥ 0
Excercise-VI

Solve the LPP graphically

max Z = 10x1 + 20x2

subject to
2x1 + 4x2 ≥ 16
x1 + 5x2 ≥ 15
x1 , x2 ≥ 0
Limitations of Graphical Method

I Graphical Method can accomodate 2 decision variables only

Limitations of Graphical Method

I Graphical Method can accomodate 2 decision variables only

I Visualization will be difficult in problems with more than 2 decision variables
System of Equations
I A System of Equations is identified by number of equations and number of
unknowns
System of Equations
I A System of Equations is identified by number of equations and number of
unknowns
I A System of Equations can be mathematically represented as,

a11 x1 + a12 x2 + . . . + a1p xp = b1

a21 x1 + a22 x2 + . . . + a2p xp = b2
. . . + . . . + aij xj + . . . = bi
am1 x1 + am2 x2 + . . . + amp xp = bm
System of Equations
I A System of Equations is identified by number of equations and number of
unknowns
I A System of Equations can be mathematically represented as,

a11 x1 + a12 x2 + . . . + a1p xp = b1

a21 x1 + a22 x2 + . . . + a2p xp = b2
. . . + . . . + aij xj + . . . = bi
am1 x1 + am2 x2 + . . . + amp xp = bm

This can be written in matrix form as

Ax = b

A ∈ Rm×p , x ∈ Rp×1 and b ∈ Rm×1

Algebraic Method I

Let’s consider the following problem

max Z = 6x1 + 5x2

subject to,
x1 + x2 ≤ 5
3x1 + 2x2 ≤ 12
x1 , x2 ≥ 0
Algebraic Method II

Convert the inequality constraints into equality constraints

Algebraic Method II

Convert the inequality constraints into equality constraints

The modified problem becomes,
Algebraic Method II

Convert the inequality constraints into equality constraints

The modified problem becomes,

Constraints are :
x1 + x2 + s1 = 5
and
Algebraic Method II

Convert the inequality constraints into equality constraints

The modified problem becomes,

Constraints are :
x1 + x2 + s1 = 5
and
3x1 + 2x2 + s2 = 12
Algebraic Method II

Convert the inequality constraints into equality constraints

The modified problem becomes,

Constraints are :
x1 + x2 + s1 = 5
and
3x1 + 2x2 + s2 = 12

Here, s1 and s2 are two new variables with nonnegative restrictions i.e. s1 , s2 ∈ R+
Algebraic Method II

Convert the inequality constraints into equality constraints

The modified problem becomes,

Constraints are :
x1 + x2 + s1 = 5
and
3x1 + 2x2 + s2 = 12

Here, s1 and s2 are two new variables with nonnegative restrictions i.e. s1 , s2 ∈ R+
The objective function becomes
Algebraic Method II

Convert the inequality constraints into equality constraints

The modified problem becomes,

Constraints are :
x1 + x2 + s1 = 5
and
3x1 + 2x2 + s2 = 12

Here, s1 and s2 are two new variables with nonnegative restrictions i.e. s1 , s2 ∈ R+
The objective function becomes

max Z = 6x1 + 5x2 + 0s1 + 0s2

Algebraic Method III

The problem becomes

Algebraic Method III

The problem becomes

max Z = 6x1 + 5x2 + 0s1 + 0s2 (1)

Algebraic Method III

The problem becomes

max Z = 6x1 + 5x2 + 0s1 + 0s2 (1)

subject to
Algebraic Method III

The problem becomes

max Z = 6x1 + 5x2 + 0s1 + 0s2 (1)

subject to
x1 + x2 + s1 + 0s2 = 5 (2)
Algebraic Method III

The problem becomes

max Z = 6x1 + 5x2 + 0s1 + 0s2 (1)

subject to
x1 + x2 + s1 + 0s2 = 5 (2)
3x1 + 2x2 + 0s1 + s2 = 12 (3)
Algebraic Method III

The problem becomes

max Z = 6x1 + 5x2 + 0s1 + 0s2 (1)

subject to
x1 + x2 + s1 + 0s2 = 5 (2)
3x1 + 2x2 + 0s1 + s2 = 12 (3)
x1 , x2 , s1 , s2 ≥ 0
Algebraic Method III

The problem becomes

max Z = 6x1 + 5x2 + 0s1 + 0s2 (1)

subject to
x1 + x2 + s1 + 0s2 = 5 (2)
3x1 + 2x2 + 0s1 + s2 = 12 (3)
x1 , x2 , s1 , s2 ≥ 0

Equality constraints ≡ System of Equations with 4 unknowns and 2 equations

Algebraic Method III

The problem becomes

max Z = 6x1 + 5x2 + 0s1 + 0s2 (1)

subject to
x1 + x2 + s1 + 0s2 = 5 (2)
3x1 + 2x2 + 0s1 + s2 = 12 (3)
x1 , x2 , s1 , s2 ≥ 0

Equality constraints ≡ System of Equations with 4 unknowns and 2 equations

Aim is to solve the solve the system of equations and find Z for those solutions and
select the maximum
Algebraic Method IV

How many solutions are possible

Algebraic Method IV

How many solutions are possible = p Cm

Algebraic Method IV

How many solutions are possible = p Cm

I In this case, 4 C2 different solutions are possible

Algebraic Method IV

How many solutions are possible = p Cm

I In this case, 4 C2 different solutions are possible

I With two equations we can solve for two variables only
Algebraic Method IV

How many solutions are possible = p Cm

I In this case, 4 C2 different solutions are possible

I With two equations we can solve for two variables only
I Equate these variables to any number and create a solution - Infinite number of
solutions
Algebraic Method IV

How many solutions are possible = p Cm

I In this case, 4 C2 different solutions are possible

I With two equations we can solve for two variables only
I Equate these variables to any number and create a solution - Infinite number of
solutions
I Restricting ourselves only to 4 C2 possibilities, so equate those number of variables
to zero only
Algebraic Method V
I For the above problem 6 solutions are possible
Algebraic Method V
I For the above problem 6 solutions are possible
I Fix x1 = 0 and x2 = 0, then s1 = 5 and s2 = 12 −→ Z = 0
Algebraic Method V
I For the above problem 6 solutions are possible
I Fix x1 = 0 and x2 = 0, then s1 = 5 and s2 = 12 −→ Z = 0
I Fix x1 = 0 and s1 = 0, then
Algebraic Method V
I For the above problem 6 solutions are possible
I Fix x1 = 0 and x2 = 0, then s1 = 5 and s2 = 12 −→ Z = 0
I Fix x1 = 0 and s1 = 0, then

x2 = 5 from equation 2
2x2 + s2 = 12 from equation 3
Algebraic Method V
I For the above problem 6 solutions are possible
I Fix x1 = 0 and x2 = 0, then s1 = 5 and s2 = 12 −→ Z = 0
I Fix x1 = 0 and s1 = 0, then

x2 = 5 from equation 2
2x2 + s2 = 12 from equation 3

So, x1 = 0 and x2 = 5, s1 = 0 and s2 = 2 −→ Z = 25

Algebraic Method V
I For the above problem 6 solutions are possible
I Fix x1 = 0 and x2 = 0, then s1 = 5 and s2 = 12 −→ Z = 0
I Fix x1 = 0 and s1 = 0, then

x2 = 5 from equation 2
2x2 + s2 = 12 from equation 3

So, x1 = 0 and x2 = 5, s1 = 0 and s2 = 2 −→ Z = 25

I Fix x1 = 0 and s2 = 0 then
Algebraic Method V
I For the above problem 6 solutions are possible
I Fix x1 = 0 and x2 = 0, then s1 = 5 and s2 = 12 −→ Z = 0
I Fix x1 = 0 and s1 = 0, then

x2 = 5 from equation 2
2x2 + s2 = 12 from equation 3

So, x1 = 0 and x2 = 5, s1 = 0 and s2 = 2 −→ Z = 25

I Fix x1 = 0 and s2 = 0 then

x2 + s1 = 5 from equation 2
2x2 = 12 from equation 3
Algebraic Method V
I For the above problem 6 solutions are possible
I Fix x1 = 0 and x2 = 0, then s1 = 5 and s2 = 12 −→ Z = 0
I Fix x1 = 0 and s1 = 0, then

x2 = 5 from equation 2
2x2 + s2 = 12 from equation 3

So, x1 = 0 and x2 = 5, s1 = 0 and s2 = 2 −→ Z = 25

I Fix x1 = 0 and s2 = 0 then

x2 + s1 = 5 from equation 2
2x2 = 12 from equation 3

So, x1 = 0 and x2 = 6, s1 = −1 and s2 = 0 −→ Z = 30

Algebraic Method VI
I Fix x2 = 0 and s1 = 0, then
Algebraic Method VI
I Fix x2 = 0 and s1 = 0, then

x1 = 5 from equation 2
3x1 + s2 = 12 from equation 3
Algebraic Method VI
I Fix x2 = 0 and s1 = 0, then

x1 = 5 from equation 2
3x1 + s2 = 12 from equation 3

So, x1 = 5 and x2 = 0, s1 = 0 and s2 = −3 −→ Z = 30

Algebraic Method VI
I Fix x2 = 0 and s1 = 0, then

x1 = 5 from equation 2
3x1 + s2 = 12 from equation 3

So, x1 = 5 and x2 = 0, s1 = 0 and s2 = −3 −→ Z = 30

I Fix x2 = 0 and s2 = 0 then
Algebraic Method VI
I Fix x2 = 0 and s1 = 0, then

x1 = 5 from equation 2
3x1 + s2 = 12 from equation 3

So, x1 = 5 and x2 = 0, s1 = 0 and s2 = −3 −→ Z = 30

I Fix x2 = 0 and s2 = 0 then

x1 + s1 = 5 from equation 2
3x1 = 12 from equation 3
Algebraic Method VI
I Fix x2 = 0 and s1 = 0, then

x1 = 5 from equation 2
3x1 + s2 = 12 from equation 3

So, x1 = 5 and x2 = 0, s1 = 0 and s2 = −3 −→ Z = 30

I Fix x2 = 0 and s2 = 0 then

x1 + s1 = 5 from equation 2
3x1 = 12 from equation 3

So, x1 = 4 and x2 = 0, s1 = 1 and s2 = 0 −→ Z = 24

Algebraic Method VI
I Fix x2 = 0 and s1 = 0, then

x1 = 5 from equation 2
3x1 + s2 = 12 from equation 3

So, x1 = 5 and x2 = 0, s1 = 0 and s2 = −3 −→ Z = 30

I Fix x2 = 0 and s2 = 0 then

x1 + s1 = 5 from equation 2
3x1 = 12 from equation 3

So, x1 = 4 and x2 = 0, s1 = 1 and s2 = 0 −→ Z = 24

I Fix s1 = 0 and s2 = 0 then
Algebraic Method VI
I Fix x2 = 0 and s1 = 0, then

x1 = 5 from equation 2
3x1 + s2 = 12 from equation 3

So, x1 = 5 and x2 = 0, s1 = 0 and s2 = −3 −→ Z = 30

I Fix x2 = 0 and s2 = 0 then

x1 + s1 = 5 from equation 2
3x1 = 12 from equation 3

So, x1 = 4 and x2 = 0, s1 = 1 and s2 = 0 −→ Z = 24

I Fix s1 = 0 and s2 = 0 then

x1 + x2 = 5 from equation 2
3x1 + 2x2 = 12 from equation 3
Algebraic Method VI
I Fix x2 = 0 and s1 = 0, then

x1 = 5 from equation 2
3x1 + s2 = 12 from equation 3

So, x1 = 5 and x2 = 0, s1 = 0 and s2 = −3 −→ Z = 30

I Fix x2 = 0 and s2 = 0 then

x1 + s1 = 5 from equation 2
3x1 = 12 from equation 3

So, x1 = 4 and x2 = 0, s1 = 1 and s2 = 0 −→ Z = 24

I Fix s1 = 0 and s2 = 0 then

x1 + x2 = 5 from equation 2
3x1 + 2x2 = 12 from equation 3

So, x1 = 2 and x2 = 3, s1 = 0 and s2 = 0 −→ Z = 27

Algebraic Method VII

Solutions x1 x2 s1 s2 Z = 6x1 + 5x2

1 0 0 5 12 Z=0
2 0 5 0 2 Z = 25
3 0 6 −1 0 Z = 30
4 5 0 0 −3 Z = 30
5 4 0 1 0 Z = 24
6 2 3 0 0 Z = 27
Algebraic Method VII

Solutions x1 x2 s1 s2 Z = 6x1 + 5x2

1 0 0 5 12 Z=0
2 0 5 0 2 Z = 25
3 0 6 −1 0 Z = 30
4 5 0 0 −3 Z = 30
5 4 0 1 0 Z = 24
6 2 3 0 0 Z = 27

How many of these solutions are feasible???

Algebraic Method VII

Solutions x1 x2 s1 s2 Z = 6x1 + 5x2

1 0 0 5 12 Z=0
2 0 5 0 2 Z = 25
3 0 6 −1 0 Z = 30
4 5 0 0 −3 Z = 30
5 4 0 1 0 Z = 24
6 2 3 0 0 Z = 27

How many of these solutions are feasible???

I Check whether all the constraints are satisfied or not

Algebraic Method VII

Solutions x1 x2 s1 s2 Z = 6x1 + 5x2

1 0 0 5 12 Z=0
2 0 5 0 2 Z = 25
3 0 6 −1 0 Z = 30
4 5 0 0 −3 Z = 30
5 4 0 1 0 Z = 24
6 2 3 0 0 Z = 27

How many of these solutions are feasible???

I Check whether all the constraints are satisfied or not

I Though solutions 3 and 4 produce maximum but they are not feasible
Algebraic Method VII

Solutions x1 x2 s1 s2 Z = 6x1 + 5x2

1 0 0 5 12 Z=0
2 0 5 0 2 Z = 25
3 0 6 −1 0 Z = 30
4 5 0 0 −3 Z = 30
5 4 0 1 0 Z = 24
6 2 3 0 0 Z = 27

How many of these solutions are feasible???

I Check whether all the constraints are satisfied or not

I Though solutions 3 and 4 produce maximum but they are not feasible
I Leave aside the infeasible solutions and select the best among the feasible ones
Algebraic Method VII

Solutions x1 x2 s1 s2 Z = 6x1 + 5x2

1 0 0 5 12 Z=0
2 0 5 0 2 Z = 25
3 0 6 −1 0 Z = 30
4 5 0 0 −3 Z = 30
5 4 0 1 0 Z = 24
6 2 3 0 0 Z = 27

How many of these solutions are feasible???

I Check whether all the constraints are satisfied or not

I Though solutions 3 and 4 produce maximum but they are not feasible
I Leave aside the infeasible solutions and select the best among the feasible ones
I Solution 6 is the best i.e. x1 = 2, x2 = 3 =⇒ Z = 27
Few Key Points on the Solutions

I Optimal solution will be best candidate solution(s) from the set of Feasible
Solutions
Few Key Points on the Solutions

I Optimal solution will be best candidate solution(s) from the set of Feasible
Solutions
I There are as many variables in the solutions existing(non-zero in this case) as the
number of constraints
Few Key Points on the Solutions

I Optimal solution will be best candidate solution(s) from the set of Feasible
Solutions
I There are as many variables in the solutions existing(non-zero in this case) as the
number of constraints
I Suppose a solution s1 = 1 and s2 = 1 then x1 = 3 and x2 = 1 with Z = 23, which is a
feasible one but inferior solution then we can see this point (3, 1) is an interior point
of the fasible region =⇒ It is enough to evaluate the corner points of feasible region
Few Key Points on the Solutions

I Optimal solution will be best candidate solution(s) from the set of Feasible
Solutions
I There are as many variables in the solutions existing(non-zero in this case) as the
number of constraints
I Suppose a solution s1 = 1 and s2 = 1 then x1 = 3 and x2 = 1 with Z = 23, which is a
feasible one but inferior solution then we can see this point (3, 1) is an interior point
of the fasible region =⇒ It is enough to evaluate the corner points of feasible region
I The feasible solutions are nothing but the Corner Points of feasible region and same
in number - Verify
Limitations of Algebraic Method

I Requires evaluation of all p Cm basic solutions in order to obtain the optimal solution
Limitations of Algebraic Method

I Requires evaluation of all p Cm basic solutions in order to obtain the optimal solution
I Some solutions are infeasible but can not be apprehended by observing
Limitations of Algebraic Method

I Requires evaluation of all p Cm basic solutions in order to obtain the optimal solution
I Some solutions are infeasible but can not be apprehended by observing
I No guiding principle on which solution point to be evaluated next
Limitations of Algebraic Method

I Requires evaluation of all p Cm basic solutions in order to obtain the optimal solution
I Some solutions are infeasible but can not be apprehended by observing
I No guiding principle on which solution point to be evaluated next

Is there any better process of finding optimal solutions???