|
|
|
|
||
|
:: July 13th, There has been a problem with your homework. The homework
will be posted latest by the afternoon of July 14th :: July 14th, HW1
Part 1 is posted :: July 21st, HW1 Part 2 is posted, and due date for both parts
is :: July 21st, 1st Exam is on :: July 21st, REMINDER! Proofs for Theorem 1.2, 1.3 and 1.4 are still part
of your HW1 :: July 23rd, IMPORTANT! HW1 Part 2 Question 1 part d has been removed
from your homework :: July 25th,
PRACTICE QUESTIONS, Exercises 1.1, # 3, 5, 9 Exercises 1.5,
# 1, 3, 7 Exercises 2.1,
# 3, 9, 15, 17 Exercises 2.2, # 1, 5 Exercises 2.3, # 1, 3, 5 :: July 25th, HW1
Answers, I’m not posting them up, exam is more similar to the practice
questions above :: July 31st,
IMPORTANT, 2nd Exam is on :: July 31st, HW2
Part 1 is posted,
and is due on :: August 3rd, HW2
Part 2 is posted,
and is due on :: August 13th, I’ll be at RUTCOR between :: August 13th, MAXIMAL FLOW PROBLEM: Whenever you’re creating a new set Ni,
you’re checking for two conditions. Let’s saythat you’re at
node k. You check for two things: 1)
Are there positive dkj values? It doesn’t matter if
the arc is in the right direction or not 2)
If there’s a node j, such that dkj > 0, you label
the node j in the same manner, even if the arc is in the opposite direction So,
by only focusing on positive dkj values, disregarding the arc
directions, the rest is handled in the same manner. Here’s
why this is true… The
excess capacities in the opposite direction take on positive values as you
start sending flow through a path. The excess capacities in the opposite
direction are keeping track of how much flow you can send back through that
particular arc. Because this algorithm is an iterative procedure, it
doesn’t necessarily mean that once you assign a flow through an arc,
you’ll always want to keep it that way. This phenomena of creating a
path, with a reverse arc in it, allows you to send some of the existing
flow(your excess capacities in the opposite direction) back to a node, and
redistribute it from that point on. For
example, on page 362, figure 5.29, the flow on arc (2,5) is 5 units and the
flow on arc (2,6) is 2 units. With the new assignment as in figure 5.30, the
flow on arc (2,5) becomes 3 units, and those 2 units taken away are in stead
sent through arc (2,6), increasing the flow thorough it to 4. As
I’ve said before, updating the values and carrying on steps is the
same. The only difference is that, this procedure causes you to increase the
excess capacity of forward arc, where as you always used to increase the
excess capacity of the backward arc. LET ME KNOW IF YOU HAVE TROUBLE… |
|
|||
|
|
|
|
|
|
