X hits on this document

417 views

0 shares

0 downloads

0 comments

25 / 63

Irregular Types of Linear Programming Problems

A-25

not part of the basic feasible solution. This means that if some mugs (x2) were produced, we would have a new product mix but the same total profit. Thus, a multiple optimal solu- t i o n i s i n d i c a t e d b y a ( o r ) r o w v a l u e o f z e r o f o r a n o n b a s i c v a r i a b l e . z j - c j c j - z j

0 40

s x

1 1

10 30

0 1

5/4 3/4

1 0

- 1>4 - 1>4

z

j

1,200

40

30

0

10

c j - z j

0

  • 0

    0

  • -

    10

0 s2

Table A-25 The Optimal Simplex Tableau

c j

30

0

x2

s1

40 x1

Basic Variables

Quantity

An alternate optimal solution is determined by selecting the non- basic variable with cj - zj = 0 as the entering variable.

To determine the alternate endpoint solution, let x2 be the entering variable (pivot column) and select the pivot row as usual. This selection results in the s1 row being the pivot row. The alternate solution corresponding to point B in Figure A-5 is shown in Table A-26.

Table A-26

The Alternate Optimal Tableau

c j

30 40

x

2

x

1

Basic Variables

z j

c j - z j

8

0

24

1

Quantity

40 x1

1,200

40

0

1

4/5

-1>5

0

-3>5

2/5

30

0

10

0

0

- 10

30

0

0

x2

s1

s2

An Infeasible Problem Another linear programming irregularity is the case in which a problem has no feasible solution area; thus, there is no basic feasible solution to the problem.

An infeasible problem does not have a feasible solution space.

An example of an infeasible problem is formulated next and depicted graphically in Figure A-6:

maximize Z = 5x1 + 3x2

subject to

x 1 , x 2 Ú 0 x 2 Ú 6 x 1 Ú 4 4 x 1 + 2 x 2 8

The three constraints do not overlap to form a feasible solution area. Because no point satisfies all three constraints simultaneously, there is no solution to the problem. The final simplex tableau for this problem is shown in Table A-27.

An infeasible problem has an artificial variable in the final simplex tableau.

T h e t a b l e a u i n T a b l e A - 2 7 h a s a l l z e r o o r n e g a t i v e v a l u e s i n t h e r o w , i n d i c a t i n g t h a t c j - it is optimal. However, the solution is x2 = 4, A1 = 4, and A2 = 2. Because the existence of artificial variables in the final solution makes the solution meaningless, this is not a real z j

Document info
Document views417
Page views417
Page last viewedSun Dec 11 09:01:47 UTC 2016
Pages63
Paragraphs3770
Words30893

Comments