Scribd
Upload
4 views3 pages

Linerar Programinng Problem

The document presents a seminar on the Theory of Linear Programming Problems, focusing on the graphical solution method. It explains how to identify the optimum solution at the vertices of the solution space and discusses methods for maximizing or minimizing the objective function. An example illustrates the graphical method, showing that multiple optimal solutions can exist along a line segment between extreme points.

Uploaded by

sawantamruta39
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views3 pages

Linerar Programinng Problem

The document presents a seminar on the Theory of Linear Programming Problems, focusing on the graphical solution method. It explains how to identify the optimum solution at the vertices of the solution space and discusses methods for maximizing or minimizing the objective function. An example illustrates the graphical method, showing that multiple optimal solutions can exist along a line segment between extreme points.

Uploaded by

sawantamruta39
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Name :- Kale Aditya Vikas

Roll NO :- BS242045
Class:- TYBSC(CS)
Subject:- Operations Research

Seminar Presentation
Topic :-Theory of Linear Programming Problem

Sub Topic :-Graphical Solution to Linear inear


Programming Problem (L.P.P.)
Draw the lines corresponding to equalities which outline the solution space. It
can be shown that the optimum solution always exists and exists at, at least
one of the vertices, i.e. extreme point of the solution space. To locate the
optimum solution, two methods are used :
(i) Compute the value of objective function at all the vertices (extreme
points) and select the one which gives optimum value of objective
function as solution point.
(ii) Draw a line of profit in feasible region. Move it parallel to itself away
from the origin, if the objective function is maximization type till it
passes through farthest vertex of the solution space.
The co-ordinates of this vertex give optimum solution of the problem. If the
problem is of minimization type then profit line is to be moved parallel to
itself closer to the origin till it passes through nearest extreme point of
solution space to origin.
The corresponding co-ordinates give optimum solution. If the optimum
solution exist at only one extreme point, it is an unique solution.
If the profit line is parallel to a side of a convex set which bounds solution
space and if the corresponding two extreme points give same optimum
solution.
The problem has alternative optimum solution, then in such case, the
problem has optimum solution rather at each and every point on the line
segment joining these extreme points is an optimum solution of the
problem.
Hence in this case there are infinitely many optimum solutions.

Example :-
Problem: 1
Q. Solve the following L.P.P. by graphical method :
Max : Z = x1 + 2x2
Subject to x1 + 2x2 ≤ 20
x1 + x2 ≤ 12
x1 ≥ 0, x2 ≥ 0.

Solution :
The feasible region is given by ABCD as shown in Extreme points are
A (0, 0), B (0, 6), C (2, 4), D (5, 0). The value of Z at extreme points :
ZA = 0
ZB = 1 × 12 + 2 × 0 = 12
ZC = 1 × 4 + 2 × 8 = 20
ZD = 1 × 0 + 2 × 10 = 20
Thus, the maximum of Z = 20 occurs at C and D.
There are infinitely many points on line segment CD and each of them provide
optimum solution.
In some cases, the problem does not possess an optimal solution but it is
possible to find better feasible solution by continuously improving the objective
function value.
If the improvement continues indefinitely, it possesses unbounded solution.

You might also like