MASSACHUSETTS INSTITUTE OF TECHNOLOGY

MASSACHUSETTS INSTITUTE OF TECHNOLOGY

15.053 ? Introduction to Optimization (Spring 2005)

Recitation 5 - Solutions

Problem 1

a) Adding to the objective coefficient for x3 would result in the following final tableau:

z

x1

x2

x3

s1

s2

RHS

1

8

1

-

0

2

16

0

2

2

0

1

-1

4

0

6

1

1

0

1

8

Adding times the second constraint to the objective row, we obtain:

z

x1

x2

x3

1

8+6

1+

0

0

2

2

0

0

6

1

1

s1

s2

RHS

0

2+ 16+8

1

-1

4

0

1

8

In order for this tableau to remain optimal, it must be that objective coefficients are still positive, or

8 + 6 >= 0, 1 + >= 0, 2 + >= 0. The most stringent of these is >= -1

b) Adding to the objective coefficient for x1 would result in the following final tableau:

z

x1

x2

x3

s1

s2

RHS

1

8-

1

0

0

2

16

0

2

2

0

1

-1

4

0

6

1

1

0

1

8

In order for this tableau to remain optimal, it must be that objective coefficients are still positive, or 8- 0.... Or 8.

c) We know from lecture that when we add to the first constraint, we have the following final tableau:

Page 1 of 4

z

x1

x2

x3

s1

s2

RHS

1

8

1

0

0

2

16

0

2

2

0

1

-1

4+

0

6

1

1

0

1

8

For the current final tableau to stay feasible we therefore need -4.

d) We note that increasing the RHS does not affect the optimal function value, therefore the objective value is unchanged when we increase the RHS of constraint 1.

2. True/False a) Yes, for example consider a problem with more constraints than there are variables. b) Yes, true, because every solution on the line segment joining them is also optimal c) No, consider maximize x subject to x 1, x 0, y 0. d) No, but every LP in standard form does! e) Yes, we move from one corner point to another. f) Yes, (recall a corner point is always feasible). g) It is possible that this is true, but we need more conditions!! For the current solution to be feasible we need e 0. Also we need to make sure the alternative solution exists ? therefore we need e>0 (the first row always wins the min ratio ? no matter the value of f ). h) False, if this tableau is obtained during the simplex algorithm, then it will be feasible (simplex never leaves the feasible set). On the other hand if this was an "arbitrary" tableau then the tableau could represent a infeasible problem (consider the case when e ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download