You are Here: Home >< Maths

# D2 6th June 2013 Watch

1. (Original post by Arsey)
If one of those cuts is a min cut, then the max flow must be the smaller of the two.

Just looking at it, C1 is 40, so that is the max flow.

you need to look at the flow pattern, again using the conservation condition.

the total capacity into F is 16 which means the max flow of FG is also 16, this in turn means the max flow into G is 24 meaning the max flow of GT is 24.

The max capacity into H is 16, so the max flow of HT is also 16.

Given that we know max flow is 40, then GT has to be 24.

d)
The max capacity into D is 24 but only 21 can leave from D, this means the max flow into is also 21.

AC has to be 8 otherwise the max flow is impossible. So the maximum flow of AD is 12.

If AD is 12, DB has to be 9 (to make 21) but DB could be 10 meaning that AD could also be 11 (to make 21). So AD must be 11 or 12.

This in turn means that SA must be 19 or 20.
Thankyou very much
What do you think may come up that hasn't come up before ?
2. (Original post by knowledgecorruptz)
Wait, how would you do it without crossing anything out?

Like this... although it never turns out as I imagine

(Original post by NiceToMeetYou)
The markscheme just states the 2 routes used, and with part D wanting you to label a flow digram showing the max flow I don't know how you're expected to do it all in your head
It really is a mess
Unless they're just after the route you used and the flow it has increased. Maybe the diagram is just for our benefit? I hope it is that way, because then I can make a mess of the diagram and not have to worry. Although there is still a question of, how on earth do they read the original values that they ask you to fill in prior to the labelling procedure :s
3. (Original post by sacheeen)
Hi, is the mark scheme value for this cut wrong? C2 given by the mark scheme is 45 but I found a value of 42. Any ideas?Attachment 223399
No, it is definitely 45

remember you are finding the CAPACITY of the cut, ignore the flows.

ET - 7
DF - 5
BF - 8
GT -25

are all the cuts flowing towards the sink = 45
4. (Original post by smith50)
Thankyou very much
What do you think may come up that hasn't come up before ?
If I could predict the future I wouldn't be here now

I don't think anything will come up that hasn't come up before. However, they could ask you to tabulate the LP GT question (I cannot see them ever asking to then follow through with Simplex).

LP max allocation question.

GT question where there is a stable solution. GT where they ask you to find the best strategy for player B after going through the well diagram method for player A.

I wouldn't be surprised if short cuts appeared on the TS question.

An initial degenerate solution when using the NWC method on transportation.

My money would be on a minimax, maximum (easier) dynamic programming question.

I wouldn't be surprised if super source / super sink makes an appearance. Also on flows maybe a sink that is in the middle of the network.

With all that been said, the new international papers mean that two papers will be written side by side. So it is likely one will have NN, the other will have short cuts. One will have LP on GT, the other LP on allocation or transportation. etc

As long as we get the next instalment of agent goodie, I will be happy.
5. (Original post by Arsey)
If I could predict the future I wouldn't be here now

I don't think anything will come up that hasn't come up before. However, they could ask you to tabulate the LP GT question (I cannot see them ever asking to then follow through with Simplex).

LP max allocation question.

GT question where there is a stable solution. GT where they ask you to find the best strategy for player B after going through the well diagram method for player A.

I wouldn't be surprised if short cuts appeared on the TS question.

An initial degenerate solution when using the NWC method on transportation.

My money would be on a minimax, maximum (easier) dynamic programming question.

I wouldn't be surprised if super source / super sink makes an appearance. Also on flows maybe a sink that is in the middle of the network.

With all that been said, the new international papers mean that two papers will be written side by side. So it is likely one will have NN, the other will have short cuts. One will have LP on GT, the other LP on allocation or transportation. etc

As long as we get the next instalment of agent goodie, I will be happy.
Well diagram method? Could you explain what that is please? Can't say I've heard of it before :s

I wouldn't mind LP on GT, free marks once you have the layout nailed (as with all other LP questions really).
6. (Original post by Hamburglar)

Like this... although it never turns out as I imagine

Unless they're just after the route you used and the flow it has increased. Maybe the diagram is just for our benefit? I hope it is that way, because then I can make a mess of the diagram and not have to worry. Although there is still a question of, how on earth do they read the original values that they ask you to fill in prior to the labelling procedure :s
if you have to complete the labelling diagram, the marker will have to look at what you have crossed out. That said, if you get the correct flow augmenting paths and correct flow pattern, I think they will just assume the labelling was done correctly.

The only time you ever have to do it by inspection is if you only need to increase it by a very small amount, where only 1 path is necessary. Once you get very good at them, you really don't need the labelling procedure, unless it is one with about 5 or 6 augmenting paths.

The number one source of confusion in flows is an augmenting path that actually reduces the flow of one arc to increase the overall flow.

There was also one question in which an arc was saturated but if you used did your min cut through it, the min cut was wrong. The reason was that is was saturated in the direction of sink to source through the cut! Very hard.
7. (Original post by Arsey)
No, it is definitely 45

remember you are finding the CAPACITY of the cut, ignore the flows.

ET - 7
DF - 5
BF - 8
GT -25

are all the cuts flowing towards the sink = 45
Oops, silly mistake! Thank you.

Will you be posting an unofficial mark scheme?
8. (Original post by Hamburglar)
Well diagram method? Could you explain what that is please? Can't say I've heard of it before :s

I wouldn't mind LP on GT, free marks once you have the layout nailed (as with all other LP questions really).
All LP questions should be gift marks, simple memory test. Absolutely no understanding is required.

The well diagram is the one where you have two vertical axes and then normally 3 intersecting lines.

You have to draw one on almost every single GT question.
9. (Original post by sacheeen)
Oops, silly mistake! Thank you.

Will you be posting an unofficial mark scheme?

I will also smash out the International solutions on Friday all being well.
10. (Original post by Arsey)
if you have to complete the labelling diagram, the marker will have to look at what you have crossed out. That said, if you get the correct flow augmenting paths and correct flow pattern, I think they will just assume the labelling was done correctly.

The only time you ever have to do it by inspection is if you only need to increase it by a very small amount, where only 1 path is necessary. Once you get very good at them, you really don't need the labelling procedure, unless it is one with about 5 or 6 augmenting paths.

The number one source of confusion in flows is an augmenting path that actually reduces the flow of one arc to increase the overall flow.

There was also one question in which an arc was saturated but if you used did your min cut through it, the min cut was wrong. The reason was that is was saturated in the direction of sink to source through the cut! Very hard.
Ah okay thanks. I suppose I should strike a line through the old numbers then or something to show the examiner that I'm updating the route, instead of doing it the text-book way where there is just a sea of numbers. On some of the more recent papers I agree, it can just be done by inspection really (especially when the bottlenecks are close to the source) but the question says, use the labelling procedure, so I just stick to it really.

(Original post by Arsey)
All LP questions should be gift marks, simple memory test. Absolutely no understanding is required.

The well diagram is the one where you have two vertical axes and then normally 3 intersecting lines.

You have to draw one on almost every single GT question.
Ahh so that's what it is called, thanks.
11. (Original post by Arsey)

I will also smash out the International solutions on Friday all being well.
Oh yeah Arsey, I was just wondering what you suggest we should do for a GT question from player B's perspective?

Should we transpose the matrix and then do it as we would normally? Or should we do it as standard from player B's perspective, where we right down equations for V(B) but with a negative sign in front?

I've never done a question like that and can see it coming up, so I'm not sure what the mark scheme wants. Thanks
12. (Original post by Hamburglar)
Oh yeah Arsey, I was just wondering what you suggest we should do for a GT question from player B's perspective?

Should we transpose the matrix and then do it as we would normally? Or should we do it as standard from player B's perspective, where we right down equations for V(B) but with a negative sign in front?

I've never done a question like that and can see it coming up, so I'm not sure what the mark scheme wants. Thanks
depends on the question, if you have to find the best strategy for player B right from the start then I would certainly advise transposing the matrix.

However, if you have already found the best strategy for A, then you will be able to discard on of the lines for what B plays in the well diagram, meaning you could delete a column and just solve simultaneously.
13. anyone did the june 2009 paper, i got the answer to the dynamic programming question but im not sure why they used scheme 1 as stage one, heres a link to the paper https://e8c8970d-a-dbffc5af-s-sites....attredirects=0

normally the last row in the table is the first stage , but in here they used the first row as stage one. look at the question , you will get what i mean.
14. Hi I wonder if anyone can tell me... When doing a transportation LP problem should your constraints be <= because I saw one MS where it was just =. Thanks!
15. (Original post by Arsey)
If I could predict the future I wouldn't be here now

I don't think anything will come up that hasn't come up before. However, they could ask you to tabulate the LP GT question (I cannot see them ever asking to then follow through with Simplex).

LP max allocation question.

GT question where there is a stable solution. GT where they ask you to find the best strategy for player B after going through the well diagram method for player A.

I wouldn't be surprised if short cuts appeared on the TS question.

An initial degenerate solution when using the NWC method on transportation.

My money would be on a minimax, maximum (easier) dynamic programming question.

I wouldn't be surprised if super source / super sink makes an appearance. Also on flows maybe a sink that is in the middle of the network.

With all that been said, the new international papers mean that two papers will be written side by side. So it is likely one will have NN, the other will have short cuts. One will have LP on GT, the other LP on allocation or transportation. etc

As long as we get the next instalment of agent goodie, I will be happy.
Agent Goodie was in one of the old spec papers as well (the june 2007 one). So he's actually been trying defeat Evil Dr. Fiendish for a while now!
16. Hey arsey,

Was wondering if you had any tips for labelling the stage, state, action and destination in a DP question

Also in transportation, does a degenerate solution only occur when demand and supply are met in a single cell?

On a side note, are you also going to be posting an unoffical markscheme for M2?

Posted from TSR Mobile
17. (Original post by ChelseaSam)
Hi I wonder if anyone can tell me... When doing a transportation LP problem should your constraints be <= because I saw one MS where it was just =. Thanks!
I think thats usually the case. I think ive seen the situation you're talking about and in that case i believe they stated that all units must be transported so there had to be an equal sign. If not then they introduced slack variables. Hope that makes some sense

Posted from TSR Mobile
18. If they don't put him in this summers paper, I'll be close to tears

Posted from TSR Mobile
19. What is happening in last part of question, i have attached ms aswell, does anyone understand???
Attached Images

20. (Original post by JayJay95)
I think thats usually the case. I think ive seen the situation you're talking about and in that case i believe they stated that all units must be transported so there had to be an equal sign. If not then they introduced slack variables. Hope that makes some sense

Posted from TSR Mobile
Thank you! Big help

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: June 11, 2013
Today on TSR

### How to stand out in an Oxbridge interview

What makes you memorable?

### A pregnant woman visits me every night

Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• Poll
Useful resources

Can you help? Study help unanswered threadsStudy Help rules and posting guidelinesLaTex guide for writing equations on TSR

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest
• ## See more of what you like on The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

• The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE