2.098/6.255/15.093  Optimization Methods

Dear all,

In 7.10(f), increasing c56 will affect potentials of both node 5 and node 1. We need to calculate the reduced costs of arcs (5,2) and (1,4). Please see the updated solution for details. Sorry for the confusion.

Best,

Andy

Hi All,

for the exam, we will use the following splitting of the class:

E51-325:  last names  A-L

E51-315: last names M-Z

Regards,

Jorge Vera.

Dear all,

The original title of this message is Properties of positive definite, negative definite, semi-definite, indefinite matrix. But Stellar complained the title is too long. So truncated as "useful" which they indeed are.

I uploaded this file because some students asked about their properties. I thought it may be useful to put things together. The uploaded file is under recitation session with that long name.

cheers,

Andy

Dear all,

Here comes a correction to BT Ex 7.10 (d): there are 9 flow conservation constraints, but only 8 of them are linearly independent (i.e. not all of them are linearly independent.) So the argument needs to use the structure of this network more explicitly. Please see the solution for details.

Also, in Recitation note 12, page 3, theorem 2 (Gordon), in the first system, it should be clear that some lambda_i must be positive (otherwise, the system is always feasible with solution \lambda_i=0 for all i). So I added a constraint sum of \lambda_i's equals to one.

Sorry for the confusion and good luck to tomorrow's exam starting at 1:30pm in E51-325 and E51-315. The classroom assignment will be announced soon.

See you tomorrow,

Andy

Dear all,
Sorry for spamming your mailbox. I added a solution to BT Ex 7.8 in Problem 1. It is quite an interesting problem actually. The first guess would be the optimal cost increases when some supply and demand increase, because all arc costs are positive. Actually this is not the case. We came up with a counterexample that shows the optimal cost can decrease, not only that, it can decrease as much as you want, i.e. the new optimal cost can be arbitrarily small comparing with the original optimal cost even though more flow is sending through the network! (Similar paradoxical situation also appears in some game theory related network problem.)
--Andy
ps. I accidentally deleted the original homework assignment as you might have noticed =( I will upload it when I get a copy. Sorry about it.