Competition - post a photo you've taken of nature >>

Need some last minute help with D1!

Ok so i've basically taught myself most of this tonight.

I have a few problems though:

Objective lines - How do I make them with some profits.
Dummy Activity and what is significant about them
Early time late time things
Route inspection algorithm - Can't find a good explenation and I did one but then got confused with the whole repeated arcs thing
Bipartrite graphs - What does this whole x-4=h-(blablabla) even mean

Thanks.

Anyone?

Original post by SkyPlus

1. Objective Lines:

The general rule is to pick the profit to be a multiple of the coefficients to the x and y values. So for example if it's P=5x+3y, make P 15, which is a multiple of both 5 and 3. You can have any multiple for example 15, 30, 45, etc. However make sure you pick P so that you can draw the objective line within the graph. What I mean is don't pick P to be so small that the objective line will be tiny (the mark scheme normally has a minimum which you can use).

2. Dummy Activity: Two reasons to have a dummy activity.

i) You have two activities X and Y. X can't start without A B and C, whereas Y can't start without A, B, C and D. On the network/graph you would have X starting from the node where A, B and C all end on. However from that node you would have a dummy taking you to another node where D ends up on. This would allow for Y to start directly after the dummy (A, B and C) and D.

ii) Another reason to have a dummy is because two activities can't have the same start and finish times (can't have both activities starting and finishing on the same nodes).

3. Early and late times:

Early time is the earliest an activity can start. This is worked out by going left to right on the graph/network.

For example an activity C can't start until both A and B end. A takes 4 hrs and B takes 6 hrs. Early start time for C would be 6 since it can't start until both A and B have finished, which at the latest is 6. So you always add on the duration of the most weighted activity directly preceding.

Late time is the latest an activity can start. You work this out by going right to left on the graph/network. So you start from the end activity and work yourself backwards to the start in a similar fashion as the early start time.

For example Activity D and E start from the same node (both ending in different nodes so no need for a dummy). D lasts for 7 hrs and E lasts for 4 hrs and the activities following the D and E both have late times of 14. You would then use 14-7 as the late start time rather than 14-4.

4. Route inspection Algorithm:

There are 3 different types.

i) The graph is to be completely traversable, (so you can start from A and finish in A) - You have to make sure that all the vertices have an even valency. So if 4 vectors A, B, C and D have an odd valency, repeat arcs that have the lest weight.

So that's, AB + CD, or AC + BD or AD + BC. Pick the one that has the least weight. You might notice that there is more than one arc connecting some of the vertices, for example AB could actually be arc AF and then FD. So be careful with that.

Once you have picked the arcs to repeat you just add the weighting to the weight of the whole network.

ii) The second type of question could be where it asks you to start from A and finish in D. So this means that A and D should remain odd, while C and B should be repeated to make them even. Just add the weight of CB to the graph.

iii). The third type asks you to start from anywhere and finish anywhere else. This means that you have to start from an odd vector and finish at another odd vector. So pick the arcs with the least weight. For example if it's BD, you would repeat BD and start from either A and finish at C (A and C have to remain odd vectors).

5. Bipartite graphs: The question gives you a bipartite graph with all the possible pairing from set x to set y. It also gives you an initial pairing and you have to start from the initial pairing and end with a complete pairing where every vector in set x is matched with a vector in set y.

You do that by first going through an alternating path.

So for example on the initial matching, A isn't matched with any activity, whereas everyone else is. So you would start with A and finish until you get to an activity not paired with anyone.

e.g. Alternating path => A-1=B-2=C-3

This means that A can be paired with 1, but 1 is paired with B. B can be paired with 2 instead but 2 is being paired with C. And C can be paired with 3, which isn't paired with anyone. So now all you have to do is show a changed path.

Changed path => A=1-B=2-C=3

This means that now A will be paired with 1. B with 2 and C with 3. The dashes represent not paired but could be paired and the equal sign represents currently paired from the initial matching. Once you have shown the changed path, you then draw a bipartite with the new matchings. You continue this until there is a complete matching.

Hope all this helps. Best of luck tomorrow.

Reply 3

Implication

Original post by SkyPlus

Objective lines - How do I make them with some profits.

What exactly do you mean? How do you draw them?

Original post by SkyPlus

Dummy Activity and what is significant about them
Dummies either:
-show that one activity is distinct from another and is represented uniquely in terms of events i.e. if you would otherwise have two activity arcs joining the same pair of vertices
-show that activity X depends on activity Y when there are other activites that depend on activity X AND something else

Original post by SkyPlus

Early time late time things
Early times- the earliest time it is possible to start an activity and finish in the minimum time
Late time- the latest time it is possible to start an activity and finish in the minimum time

The early time of an event is the LATEST of all the possible times to get to that event.

The late time of an event is the lowest of all possible times to get back to that event from the END vertex.

Original post by SkyPlus

Route inspection algorithm - Can't find a good explenation and I did one but then got confused with the whole repeated arcs thing

-every arc must be traversed twice
-to do this "without repeating" and starting and finishing in the same place, the valencies of all nodes must be even
-to do this without repeating and starting and finishing in difference places, the only odd vertices can be the start and finish points

So, if we want to minimise the total distance we travel, we must minimise the distance we must repeat. So, we find the shortest combination of paths that joins enough odd vertices to make enough of them even in valency. We then repeat those paths.

Original post by SkyPlus

Bipartrite graphs - What does this whole x-4=h-(blablabla) even mean

X-4=H-5=Y represents the path X4H5Y, where - represents an arc NOT IN the matching and = represents an arc IN the matching

It's not perfect, I'm sorry, but it's the best I can do for now. Sat here memorising definitions for D1 myself haha.

Need some last minute help with D1!

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you