Method of Solving a L.P.P.

They are:
a) Graphical (Geometrical) method
b) Simplex (algebraic) method.
Graphical (Geometrical) method
In an LPP when the number of decision variables is two, the problem can be solved by graphical
method.
1) Formation of the problem: The problem is expressed in the form of a mathematical model.
Here, the objective function and the constraints are written down.
2) Graphically plotting the constraints. The constraints are graphically represented. To start with,
the inequalities are written as equalities. Every equation is represented by a straight line and
then, the area indicating the inequality is identified. The Non-negative restrictions are satisfied
in the first quadrant.
3) Identification of the region of feasible solutions: The common region between various
constraints and non-negativity restrictions is identified. This is the region of feasible solutions.
The corner points of this region are identified.
4) Finding the optimal solution: The values of Z at the various corner points of the region of the
feasible solutions are calculated. The Optimum (Maximum or minimum) Z among these values
is noted. Corresponding solution is the optimal solution.
Note: While finding the corner points, if greater accuracy is needed, the ordinates may be
obtained by algebraically solving the corresponding equations .

1) Solve the following L.P.P graphically

Maximize Z= 2000x + 1000y
S.T. x+y 400

8x + 5y 2600

and x o, y o
Solution:

15
 Equation Putting x = 0 Putting y = 0 Points (x,y) on the
Corresponding y is Corresponding x is
line

X=0 Y- axis
Y=0 X- axis

Corner Points Z=

2) Solve the following L.P.P graphically

Maximize Z= 400x + 1000y
S.T. 12x + 6y 6000

4x + 10y 4000

2x + 13y 1800

and x o, y 0
Solution:

Equation Putting x = 0 Putting y = 0 Points (x,y) on the

Corresponding y is Corresponding x is
line

16
 X=0 Y- axis
Y=0 X- axis

Corner Points Z=

3) Solve the following L.P.P graphically

Maximize Z= 5x + 8y
S.T. 12x + 2y 42

x + 3y 12

x+y 10

and x o, y o
Solution:

Equation Putting x = 0 Putting y = 0 Points (x,y) on the

Corresponding y is Corresponding x is
line

17
 X=0 Y- axis
Y=0 X- axis

Corner Points Z=

4) Solve the following L.P.P graphically

Maximize Z= 5x + 8y
S.T. 12x + 2y 42

x + 3y 12

x+y 10

and x 0, y 0
Solution:

Equation Putting x = 0 Putting y = 0 Points (x,y) on the

Corresponding y is Corresponding x is
line

X=0 Y- axis
Y=0 X- axis

Corner Points Z=

18
5) Solve the following L.P.P graphically
Maximize Z= 5x + 8y
S.T. 12x + 2y 42

x + 3y 12

x+y 10

and x 0, y 0
Solution:

Equation Putting x = 0 Putting y = 0 Points (x,y) on the

Corresponding y is Corresponding x is
line

X=0 Y- axis
Y=0 X- axis

Corner Points Z=

19
6) Solve the following L.P.P graphically
Maximize Z= 3x + 4y
S.T. 5x + 8y 80

x 2

y 8

and x 0, y 0

and x 0, y 0
Solution:

Equation Putting x = 0 Putting y = 0 Points (x,y) on the

Corresponding y is Corresponding x is
line

X=0 Y- axis
Y=0 X- axis

Corner Points Z=

7 Solve the following L.P.P graphically

Maximize Z= x + 1.50y
20
 S.T. 2x + 4y 3

100x + 40y 50

10 x + 30y 10

and x 0, y 0
Solution:

Equation Putting x = 0 Putting y = 0 Points (x,y) on the

Corresponding y is Corresponding x is
line

X=0 Y- axis
Y=0 X- axis

Corner Points Z=

8) Solve the following L.P.P graphically

Maximize Z= 5000x + 7000y

S.T. 100x + 120y 5000

200x +120y 6000

200x + 400y 14000

21
 and x 0, y 0
Solution:

Equation Putting x = 0 Putting y = 0 Points (x,y) on the

Corresponding y is Corresponding x is
line

X=0 Y- axis
Y=0 X- axis

Corner Points Z=

9) Solve the following L.P.P graphically

Maximize Z= 40,000x + 50,000y

S.T. 1000x + 1500y 20,000
x 1
y 5

and x 0, y 0

Equation Putting x = 0 Putting y = 0 Points (x,y) on the

Corresponding y is Corresponding x is
line

22
 X=0 Y- axis
Y=0 X- axis

Corner Points Z=

10) Solve the following L.P.P graphically

Maximize Z= 6x + 14y
S.T. 5x + 4y 60

3x +7y 84

x+y 18

and x 0, y 0

Equation Putting x = 0 Putting y = 0 Points (x,y) on the

Corresponding y is Corresponding x is
line

23
 X=0 Y- axis
Y=0 X- axis

Corner Points Z=

SIMPLEX ALGORITHEM
(a) Maximization Problems:

1) Solve the following LPP using Simplex Method:

Z max = 6X1 + 8X2
Subjected to: 30X1 +20X2 ≤ 300
5X1 + 10X2 ≤ 110
X1 X2 ≥ 0
Solution:

CONTRIBUTION PER UNIT

COST COMPONENT BASIC SOLUTION
VARIABLE VARIABLE

24
Formula:
New Row Element = (Element in old row) - [{Intersectional element of old row} x
{Corresponding elements in replacing row}]
Pivotal element

CONTRIBUTION PER UNIT

COST COMPONENT BASIC SOLUTION
VARIABLE VARIABLE

25
 CONTRIBUTION PER UNIT
COST COMPONENT BASIC SOLUTION
VARIABLE VARIABLE

26
 CONTRIBUTION PER UNIT
COST COMPONENT BASIC SOLUTION
VARIABLE VARIABLE

27
 CONTRIBUTION PER UNIT
COST COMPONENT BASIC SOLUTION
VARIABLE VARIABLE

28
2) Solve the following LPP using Simplex Method:
Z max = 500X1 + 600X2 + 1200X3
Subjected to: 2X1 +4X2 + 6X3 ≤ 160
3X1 + 2X2 +4X3 ≤ 120
X1 , X2 X3 ≥ 0
Solution:

CONTRIBUTION PER UNIT

COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

29
Formula:
New Row Element = (Element in old row) - [{Intersectional element of old row} x
{Corresponding elements in replacing row}]
Pivotal element

CONTRIBUTION PER UNIT

COST COMPONENT BASIC SOLUTION
VARIABLE VARIABLE

30
 CONTRIBUTION PER UNIT
COST COMPONENT BASIC SOLUTION
VARIABLE VARIABLE

31
 CONTRIBUTION PER UNIT
COST COMPONENT BASIC SOLUTION
VARIABLE VARIABLE

32
 CONTRIBUTION PER UNIT
COST COMPONENT BASIC SOLUTION
VARIABLE VARIABLE

33
3) Solve the following LPP using Simplex Method:
Z max = 10X1 + 5X2
Subjected to: 4X1 +5X2 ≤ 100
5X1 + 2X2 ≤ 80
X1 X2 ≥ 0
Solution:

CONTRIBUTION PER UNIT

COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

34
Formula:
New Row Element = (Element in old row) - [{Intersectional element of old row} x
{Corresponding elements in replacing row}]
Pivotal element

CONTRIBUTION PER UNIT

COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

35
 CONTRIBUTION PER UNIT
COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

36
 CONTRIBUTION PER UNIT
COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

37
 CONTRIBUTION PER UNIT
COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

38
4) Solve the following LPP using Simplex Method:
Z max = 5X1 + 10X2 + 8X3
Subjected to: 3X1 +5X2 + 2X3 ≤ 60
4X1 + 4X2 +4X3 ≤ 72
2X1 + 4X2 +5X3 ≤ 100
X1 X2 X3 ≥ 0
Solution:

CONTRIBUTION PER UNIT

COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

39
Formula:
New Row Element = (Element in old row) - [{Intersectional element of old row} x
{Corresponding elements in replacing row}]
Pivotal element

CONTRIBUTION PER UNIT

COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

40
 CONTRIBUTION PER UNIT
COST COMPONENT BASIC SOLUTION
VARIABLE VARIABLE

41
 CONTRIBUTION PER UNIT
COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

42
 CONTRIBUTION PER UNIT
COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

43
5) Solve the following LPP using Simplex Method:
Z max = 30X1 + 40X2 + 20X3
Subjected to: 10X1 +12X2 + 7X3 ≤ 10,000
7X1 + 10X2 +8X3 ≤ 8000
X1 + X2 +X3 ≤ 1000
X1 X2 X3 ≥ 0
Solution:

CONTRIBUTION PER UNIT

COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

44
 Formula:
New Row Element = (Element in old row) - [{Intersectional element of old row} x
{Corresponding elements in replacing row}]
Pivotal element

CONTRIBUTION PER UNIT

COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

45
 CONTRIBUTION PER UNIT
COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

46
 CONTRIBUTION PER UNIT
COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

47
 CONTRIBUTION PER UNIT
COST BASIC SOLUTION
COMPONENT VARIABLE VARIABLE

48
 DUALITY

Associated with any LPP is another LPP, called its Dual. The first way of starting Linear

Programming Problem is called the Primal of the problem. The second way of starting the
same problem is called the dual. In other words each LP maximising problem has its
corresponding dual, a minimising problem. Similarly each Lp minimising problem has its
corresponding dual, a maximising problem.
Rules for Constructing the Dual Problems

1) If the objective of the one problem is to maximise, the objective of the other is to minimise.
2) The maximisation problem should have all ≤ constraints and minimisation should have ≥
constraints. If in maximisation case any constraints is ≥ type, it can be multiplied by -1 and signs
can be got revised. Similarly if in a minimisation cases any problem has got ≤ it should be multiplied
by -1 and signs can be got reversed.
3) The number of Primal decisions variables equals the number of dual constraints and the number
of primal constraints equals the number of dual variables.
4) If the inequalities are ≤ type than in the dual problem, they are ≥ type and vice versa.

Write the dual for the following problems.

1) Max Z = 50x1 + 120 x2

Subject to : 2x1 + 4x2 ≤ 80

49
 3x1 + x2 ≤ 60
x1, x2 ≥ 0

2) Minimise Z = 40X1+200X2
Subject to: 4X1 + 40 X2 ≥ 160
3X1 + 10 X2 ≥ 60
8X1 + 10 X2 ≥ 80
X1, X2 ≥ 0

3) Min Z = X1 + X2
Subject to 2X1 + X2 ≥ 2
-X1 – X2 ≥ 1
X1, X2 ≥ 0

50
4) Min Z = X1 + X2
Subject to 2X1 + X2 ≥ 4
X1 + 7X2 ≥ 7
X1, X2 ≥ 0

5) Minimise Z = 40x1+ 200x2

Subject to 4x1 + 40x2 ≥ 160
3x1 + 10 x2 ≥ 60
8x1 + 10x2 ≥ 80
x1 , x2 ≥ 0

51
52