x Turn on thread page Beta
 You are Here: Home >< Maths

D2 6th June 2013 watch

1. (Original post by smith50)
Sorry why BE not any other arc?
Smith
BE is an arc that is included in the minimum cut, and the other two are not.

Consider the other 2 arcs - when the flow is at a maximum, these arcs are not saturated. Therefore increasing their capacity would be pointless because it would not fill up anyway. The "bottleneck" is at BE, because this arc is included in the minimum cut and the other two are not. Since this arc is saturated when the flow in the network is maximised, if you increase the capacity of this arc, you increase the flow through the network.

Hope this helps
2. do we have to use x11 x12 x13 x21.............. as the decision variable????? or can we use ie. Xcv Xcn Xcm......???
Attached Images

3. (Original post by Hamburglar)
BE is an arc that is included in the minimum cut, and the other two are not.

Consider the other 2 arcs - when the flow is at a maximum, these arcs are not saturated. Therefore increasing their capacity would be pointless because it would not fill up anyway. The "bottleneck" is at BE, because this arc is included in the minimum cut and the other two are not. Since this arc is saturated when the flow in the network is maximised, if you increase the capacity of this arc, you increase the flow through the network.

Hope this helps
Hey but it says that cf is part of the minimum cut

Smith
4. (Original post by smith50)
Hey but it says that cf is part of the minimum cut

Smith
Ah :s I was just looking at the original diagram and assumed it wasn't.

I'm not sure to be honest, sorry. I hope somebody here can help
5. What should I do in Allocation if maximisation and incomplete data happen at same time? (there is one in June 2010, not quite understand about the mark scheme)
6. (Original post by deansun)
What should I do in Allocation if maximisation and incomplete data happen at same time? (there is one in June 2010, not quite understand about the mark scheme)
Forget the incomplete thing first. Alter to make it a maximisation matrix. And then just proceed as usual by making the incomplete slot a huge value.
7. (Original post by Hamburglar)
Classical = Visiting each vertex only once. Practical = Visiting each vertex at least once. If you have a classical problem, then you also have a practical problem.

The reason it gets converted to a classical problem is because the algorithms used visit each vertex only once. Nearest neighbour starts at a vertex, visits every other vertex once only and returns to the start.

However, finding a lower bound by using RMST + 2 smallest arcs doesn't give you a classical problem - that is why they say it is not a viable solution. This is also why when dealing with inequalities, it is strict with respect to the lower bound, but inclusive of the upper bound.

Hope this helps
Hammy this isn't quite correct.

Firstly NN doesn't necessarily give you a solution to the classical problem. You need to watch out for questions where you are finding NN from a table of least distances (most common type of qu). For example, the table might indicate A to B; however, when comparing to the network A to B in the table might very well be A to B via C.

Your reasoning in the second part isn't complete either. The RMST method will only give a viable solution to the classical problem if it forms a cycle, this then would be the' optimal solution. You could consider it to give a solution to the practical problem, however the weight would change as arcs would need to be repeated.
8. (Original post by Arsey)
Hammy this isn't quite correct.

Firstly NN doesn't necessarily give you a solution to the classical problem. You need to watch out for questions where you are finding NN from a table of least distances (most common type of qu). For example, the table might indicate A to B; however, when comparing to the network A to B in the table might very well be A to B via C.

Your reasoning in the second part isn't complete either. The RMST method will only give a viable solution to the classical problem if it forms a cycle, this then would be the' optimal solution. You could consider it to give a solution to the practical problem, however the weight would change as arcs would need to be repeated.
Ah thanks for the correction on the first bit. I forgot that the table of least distances involves indirect routes.

As for the second part, I made a post a bit later I think about how that method gives a viable solution when you get a tour. However, that is pretty rare I think because the spanning tree would have to be really simple, with the shortest arcs connecting in just the right way.

Thanks for clearing it up
9. (Original post by knowledgecorruptz)
Forget the incomplete thing first. Alter to make it a maximisation matrix. And then just proceed as usual by making the incomplete slot a huge value.
Thanks, and also in maximisation we must subtract the largest number in matrix or any number larger than the largest is all fine? Because the one in June 2010 the mark scheme subtracts 30 rather than 27(the largest number in matrix)
10. (Original post by deansun)
Thanks, and also in maximisation we must subtract the largest number in matrix or any number larger than the largest is all fine? Because the one in June 2010 the mark scheme subtracts 30 rather than 27(the largest number in matrix)
Either. You reduce rows and columns afterwards anyway so it makes no difference.
11. (Original post by deansun)
What should I do in Allocation if maximisation and incomplete data happen at same time? (there is one in June 2010, not quite understand about the mark scheme)
you should first subtract every element from the largest value (ignore the empty cell).

In the new matrix put a value into the empty cell that is at least twice the largest value.

You cannot do the second step first as the whole point is to maximise. If you make the empty cell very big initially then it is likely it will be picked in the solution.

does that make sense?
12. Make sure you know how to formulate an a linear programming problem which requires a maximum solution. It has never been asked but certainly could be.
13. (Original post by Arsey)
Make sure you know how to formulate an a linear programming problem which requires a maximum solution. It has never been asked but certainly could be.
Surely you'd just change it to Maximise P = 13x + 23x + etc.?
14. (Original post by smith50)
Hey but it says that cf is part of the minimum cut

Smith
no it doesn't, look again, it says BC OR! CF

Both BC and CF are saturated, so you can complete the min cut passing through either.
15. (Original post by knowledgecorruptz)
Surely you'd just change it to Maximise P = 13x + 23x + etc.?
no, you do not. I think if the question was asked 90% of candidates would answer it that way.

You have to answer it as you would a normal Max allocation question.

You first subtract every element from the largest value in the table. Next, you answer it as every other LP minimising question.
16. (Original post by Knoyle quiah)
Can someone please post all the real life examples for each topic, ie. travelling salesman????????

someone else asked for a real life example of TS. Seriously? It must be the easiest one to put into context, just give an example of a travelling salesman (NOT POSTMAN!). I put an example in a post in this thread.

Examples of minimax and maximin are more complicated. Just memorise an example of each. I put an example on my sheet of definitions, which is also attached to one of my posts in this thread.
17. (Original post by Knoyle quiah)
do we have to use x11 x12 x13 x21.............. as the decision variable????? or can we use ie. Xcv Xcn Xcm......???

Yes you can. However, I would advise you learn summation notation, it is soooo much quicker.
18. (Original post by Arsey)
no it doesn't, look again, it says BC OR! CF

Both BC and CF are saturated, so you can complete the min cut passing through either.
I don't understand these two questions could you help please:

P.S - How do you know which are can be increased in flow ?

Thanks,
Smith
19. (Original post by Arsey)
Yes you can. However, I would advise you learn summation notation, it is soooo much quicker.
Could you explain how to read the summation notation? I haven't a clue how it works/how to read it and as a result am reluctant to read it (don't have a teacher to ask either)
20. (Original post by Hamburglar)
Aw, returned

Yeah, although I haven't seen any game theory linear programming or even transportation linear programming come up before in terms of simplex. Usually the simplex stuff is it's own isolated question. But who knows, we could be the first :s
Simplex could only come up on a GT question. One which had 3 or more strategies for the player the game is in terms of.

You should make sure you can formulate the problem into a simplex tableau though. I very much doubt you will ever be asked to then complete the simplex procedure to find a solution.... it takes too long and is quite tedious. It has only ever been asked once, in a year that the mark for 100ums was very low.

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

Any tips for freshers...

who are introverts?

More snow?!

Discussions on TSR

• Latest
Poll
Useful resources
Discussions on TSR

• Latest

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