[go: up one dir, main page]
Scribd
Upload
9 views14 pages

Lecture 4. Convexity and Graphical Method - Special Cases

The document discusses alternative optimal solutions in linear programming (LP), where multiple feasible solutions yield the same optimal objective function value. It also addresses infeasible solutions, where no feasible region exists, and unbounded optimum scenarios, where the objective function can increase indefinitely. The presence of unbounded solutions typically indicates missing constraints in the problem formulation.

Uploaded by

krrishj2112
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
9 views14 pages

Lecture 4. Convexity and Graphical Method - Special Cases

The document discusses alternative optimal solutions in linear programming (LP), where multiple feasible solutions yield the same optimal objective function value. It also addresses infeasible solutions, where no feasible region exists, and unbounded optimum scenarios, where the objective function can increase indefinitely. The presence of unbounded solutions typically indicates missing constraints in the problem formulation.

Uploaded by

krrishj2112
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
You are on page 1/ 14

Alternative Optimal Solutions.

In some LP
problems there may exist more than one
feasible solution whose objective function
values equal the optimal value of the linear
program. In such cases, all these feasible
solutions are optimal solutions, and the
linear program is said to have alternative or
multiple optimal solutions.
The feasible region is ABCDE. The objective
function lines drawn for Z =10 coincides
with side BC of the feasible region. Thus,
the corner-point feasible solutions x1=10,
x2 = 0 (B), x1= 2, x2 = 4 (C), and all other
feasible points on the line BC are optimal
solutions.
Infinitely many alternative optimal solutions

The level curves for z(x1, x2) = 18x1 + 6x2 are


parallel to one face of the polygon boundary of
the feasible region. Moreover, this side contains
the points of greatest value for z(x1, x2) inside
the feasible region. Any combination of (x1, x2)
on the line 3x1+x2 = 120 for x1 ∈ [16, 35] will
provide the largest possible value z(x1, x2) can
take in the feasible region S.
Infeasible solution.

There is no blue region–i.e., all the regions are gray


indicating that the constraints are not satisfiable. If the
feasible region is empty, then no solution exists.
Unbounded Optimum.
It is possible for some LP problems not to have an optimal solution.
In other words, it is possible to find better feasible solutions
improving the objective function values continuously. In this case,
moving farther away from the origin increases the objective
function x1 + 2x2, and maximum Z would be infinite. In cases where
no finite maximum exists, the linear program is said to have an
unbounded optimum.
It is inconceivable for a practical problem to have an unbounded
solution, since this implies that one can make infinite profit from a
finite amount of resources! If such a solution is obtained in a
practical problem, it usually means that one or more constraints
have been omitted inadvertently during the initial formulation of
the problem. These constraints w
Unbounded

we can make z(x1, x2) as large as we want and


still find a point in the feasible region that will
provide this value. Hence, the largest value z(x1,
x2) can take when (x1, x2) are in the feasible
region is +∞. That is, the problem is
unbounded.

You might also like