|
|
|
A Level Mathematics D2 Revision NotesTSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > A Level Mathematics D2 Revision Notes
Game TheoryNetworksCritical Path AnalysisIf you have certain tasks that need to be completed, say planning for a D2 exam. Certain tasks have to be completed before you go on to start another, for example you need to buy the revision quide before you can revise from it. Once you have your list of activities, you need to fill in a presedence table, which contains the activities and which other activity it depends on. If there is an activity that does not depend on any thing else then it can start at any time. After you have completed your presedence table you are ready to draw an activity network (including nodes representing events and arcs representing activities). Start with a node that represents the start of the project (called the source node), add arces for each activity that can start at any time (don't worry about the exact position of each arc, as you might have to redraw a neat copy of the whole network at the end). Then add nodes for the end of any of the arcs which have another activity depending on it, then add another arc starting at that node. To make your life easier, add lables with the duration of each activity next to each arc, s you go along drawing the arcs. Linear ProgrammingMatching and allocation1) Bipartite Graphs and Matching Augmentation Algorithm They are the graphs that have a set of right nodes and a set of left nodes. The nodes on one side of the the graph (e.g. left) can't join up to each other. This means that the nodes on the left have arcs going only to the right and the nodes on the right have arcs only going to the left. Google the image of a bipartite graph to reinforce what I've said. For a bipartite graph, initially you are given a certain matching, where the nodes on the left match up to nodes on the right. Some times this matching can be improved (a better combination can be found). Most of the times you are given a question a bit like this one below: Alan, Brad, Ciara and Dave have to pick one colour of out Pink, Green, Yellow and Red. Alan would prefer Green or Red. Brad would prefer Yellow or Green. Ciara prefers Pink, Green or Yellow. Dave only wants red. Finally, a teacher decides that Alan gets Red, Brad gets Yellow and Ciara gets Green. This leaves Dave with Pink which he didn't want initially. Can this matching be improved? In this case, you put the A,B,C and D nodes on the left and the P,G,Y and R nodes on the right and then you draw arcs according to what they initially wanted in a bipartite graph - this shows the possible matchings. Once you've drawn the arcs to what they initially wanted, highlight those arcs that signify what the teacher gave them. In the case above, Dave didn't get Red so leave don't draw a node from D to P. This is known as an incomplete initial matching. To improve the matching follow the algorithm below - 1) Let all the arcs from the possible matchings go from left to right and all the arcs showing the incomplete matching from right to left. 2) Start from the unmatched node on the left and try to follow the arcs to reach the unmatched node on the right where arcs in the possible matchings go from left to right and arcs in the initial incomplete matching go from right to left. 3) Pick the shortest path following Step 2. This is the alternating path. 4) If there is an arc in the alternating path that was in the initial incomplete matching, pick the other arc in the possible matchings that goes out of that particular node. If there isn't a node going common to the arc in the alternating path covered by the initial incomplete matching, leave it like that. 5) Repeat step 4 for any other nodes that might be like the above. And you should have a final complete matching. 2) Hungarian Algorithm This is a MINIMISING problem for ALLOCATION problems. So take away the numbers accordingly. But at the end if you have to find the final cost etc. remember to add the number you took away intially, back again at the end. This only works for square arrays (matrices) so add a dummy row accordingly which is the largest element (number) in the array (matrix). Follow the algorithm below- 1) Reduce rows and then reduce columns (most of the times the question will which one to reduce first but if they don't say it, reduce the rows first and then the columns) Here take away the lowest value in the row or column away from each element in that row or column. If 0 is the lowest value, leave it like that because taking 0 away from each element is not going to change it. 2) You will get 0s so cover all the 0s with the least number of lines. 3) Add the least uncovered element (number in the array) to the zeros. 4) Take away the least uncovered element (number in the array) from EVERY element in the array. 5) Repeat this till you get enough 0s in each row and column. 6) Pick the 0s in a way that it's the only 0 in it's row or column. That should be your allocation done. Transportation Problems |
|
||||||||||||||||
