X hits on this document

482 views

0 shares

0 downloads

0 comments

24 / 63

A-24

Module A

The Simplex Solution Method

These special types include problems with more than one optimal solution, infeasible problems, problems with unbounded solutions, problems with ties for the pivot column or ties for the pivot row, and problems with constraints with negative quantity values.

Multiple Optimal Solutions Consider the Beaver Creek Pottery Company example with the objective function changed as follows:

Z = 40x1 + 50x

2

to

Z = 40x1 + 30x2 maximize Z = 40x1 + 30x 2

subject to

x 1 , x 2 Ú 0 4 x 1 + 3 x 2 1 2 0 x 1 + 2 x 2 4 0

Alternate optimal solutions have the same Z value but different variable values.

The graph of this model is shown in Figure A-5. The slight change in the objective function makes it now parallel to the constraint line, 4x1 + 3x2 = 120. Therefore, as the objective function edge moves outward from the origin, it touches the whole line segment BC rather than a single extreme corner point before it leaves the feasible solution area. The endpoints of this line segment, B and C, are typically referred to as the alternate optimal solutions. It is understood that these points represent the endpoints of a range of optimal solutions.

Figure A-5

Graph of the Beaver Creek Pottery Company example with multiple optimal solutions

x2

40

1 x = 24

1 x = 30

2 x =8

2 x =0

Z = 120

Z = 120

Point B

Point C

30

20

A

10

B

0

10

20

C 30

40

x1

For a multiple optimal solution the cj - zj (or zj - cj) value for a nonbasic variable in the final tableau equals zero.

The optimal simplex tableau for this problem is shown in Table A-25. This corresponds to point C in Figure A-5.

The fact that this problem contains multiple optimal solutions can be determined from t h e r o w . R e c a l l t h a t t h e r o w v a l u e s a r e t h e n e t i n c r e a s e s i n p r o f i t p e r u n i t f o r t h e v a r i a b l e i n e a c h c o l u m n . T h u s , v a l u e s o f z e r o i n d i c a t e n o n e t i n c r e a s e i n p r o f i t a n d n o n e t l o s s i n p r o f i t . W e w o u l d e x p e c t t h e b a s i c v a r i a b l e s , a n d t o h a v e z e r o t h e y c a n n o t b e e n t e r values because they are part of the basic feasible solution; they are already in the solution so e d a g a i n . H o w e v e r , t h e c o l u m n h a s a v a l u e o f z e r o a n d i t i s c j - z j x 2 c j - z j x 1 , s 1 c j - z j c j - z j c j - z j

Document info
Document views482
Page views482
Page last viewedTue Jan 17 17:20:39 UTC 2017
Pages63
Paragraphs3770
Words30893

Comments