X hits on this document

364 views

0 shares

0 downloads

0 comments

26 / 63

A-26

Module A

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 info
Document views364
Page views364
Page last viewedSun Dec 04 12:29:50 UTC 2016
Pages63
Paragraphs3770
Words30893

Comments