X hits on this document

504 views

0 shares

26 / 63

The Simplex Solution Method

Figure A-6 Graph of an infeasible problem

x2

12

x1 = 4

10

8

C

6

x2 = 6

4

B

4x1 + 2x2 = 8

2

• 0

A

2

4

6

8

10

12

x1

x A A

2 1 2

4 4 2

2 1 -2

1 0 0

1/2 0 -1>2

0 -1 0

0 0 -1

0 1 0

0 0 1

z

j

12 - 6M

6+M

3

3>2 + M>2

M

M

-M

-M

c -z

j

j

-1 - M

0

-3>2 - M>2

-M

-M

0

0

s o l u t i o n . I n g e n e r a l , a n y t i m e t h e ( o r ) r o w i n d i c a t e s t h a t t h e s o l u t i o n i s o p t i - z j - c j c mal but there are artificial variables in the solution, the solution is infeasible. Infeasible problems do not typically occur, but when they do they are usually a result of errors in defin- ing the problem or in formulating the linear programming model. j - z j

The Final Simplex Tableau for

Basic

5

3

0

0

0

-M

-M

an Infeasible Problem

j c

Variables

Quantity

x1

x2

s1

s2

s3

A1

A2

Table A-27

3

• -

M

• -

M

In an unbounded problem the objective function can increase indefinitely because the solution space is not closed.

An Unbounded Problem In some problems the feasible solution area formed by the model constraints is not closed. In these cases it is possible for the objective function to increase indefinitely without ever reaching a maximum value because it never reaches the boundary of the feasible solution area.

An example of this type of problem is formulated next and shown graphically in Figure A-7:

maximize Z = 4x1 + 2x2

subject to

x 1 , x 2 Ú 0 x 2 2 x 1 Ú 4

 Document views 504 Page views 504 Page last viewed Fri Jan 20 02:01:59 UTC 2017 Pages 63 Paragraphs 3770 Words 30893