D2 6th June 2013

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

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

Smith

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)

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.

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)

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)

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.

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

Smith

Surely you'd just change it to Maximise P = 13x + 23x + etc.?

Can someone please post all the real life examples for each topic, ie. travelling salesman????????

do we have to use x11 x12 x13 x21.............. as the decision variable????? or can we use ie. Xcv Xcn Xcm......???

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.

Yes you can. However, I would advise you learn summation notation, it is soooo much quicker.

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