Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
Decision Year 2
A-Level Further Maths- Edexcel
| Question | Answer |
|---|---|
| What is a planar graph? | A graph which can be drawn so that no two vertices overlap |
| What are the steps of the planarity algorithm? | Redraw the graph so that a Hamiltonian cycle is edges of a polygon. Draw all other edges. Select 1 of those edges and label it I. Label those that cross I, O (if they themselves do not cross). Label those that cross all of O, I. If all labelled -> planar |
| How do we treat a network with >4 odd nodes, when trying to find shortest routes? | The question will give restrictions making it only 4. We consider the 3 pairs of possible odd nodes it creates |
| Whats the difference between classical traveling salesman problem and the practical one? | Classical- each vertex visited EXACTLY once. Practical- each vertex visited AT LEAST once. |
| What is the triangle inequality? | longest side ≤ sum of other two sides |
| How do we gain an upper bound for the practical travelling salesman problem? [2 ways] | Minimum spanning tree method. (find minimum spanning tree, upper bound = weight x2) OR nearest neighbour algorithm (choose vertex, select nearest vertex that hasnt been visited, then return to start. upper bound = tour with smallest length (try all nodes) |
| How do we gain a lower bound for the classical travelling salesman problem? | Remove each vertex in turn. Find a residual minimum spanning tree and add the missing vertex using its 2 shortest connecting arcs. Largest weight = lower bound. IF HAMILTONIAN THEN OPTIMAL |
| How do we formulate a simplex problem? | Write the constraints as normal and replace every ≤ with a slack and an =. With maximise P=(something) make this P-(something)=0 |
| How do we solve a simplex problem? | Select column of most negative no. in objective row. Divide each total value by no. in the pivot column and select smallest. Make value in column 1. Take away multiples row by row so value in column is 0 for all but one. Cont until no - in objective row |
| How do we use the simplex method to minimise P? | Set P = -Q and maximise Q. (Afterwards don't forget to take - the answer) |
| How do we apply simplex to integer values? | Test 4 options of integers around the optimal solution. |
| What do we do to ≥ constraints? | x+y≥4 -> x+y-s+a=4. We then make a second objective of maximising I where I=-(a1+a2+...). We then use two-stage simplex method (or big M which is different) |
| How do you carry out the two-stage simplex method? | Formulate a table with the constraints and two things which need maximising (P and I). Begin with focusing on I. Keep going until I is 0. If not then it is not possible. Then delete I and all a values. Continue as normal |
| What is M in the big M method? | Some arbitrary large number (which forces a values towards 0) |
| How do we formulate the big M method? | With the objection function P=x+y+z, we make it P=x+y+z-M(a1+a2+...). Substitute a1. a2... We then rearrange so all variables are to one side. |
| How do we carry out the big M method? | Choose most negative as you would and strive to get all values involving M be under a1, a2... As soon as the artificial variables (and no others) involve M, delete them. Continue as normal |
| How do you draw a resource histogram? | Draw a graph with one grid representing one worker working for one period of time. Fill in each of the activities starting from the earliest time possible. Take into account no. of workers. |
| How to we minimise number of workers using resource histogram (resource levelling)? | Shift workers around so the graph is as flat as possible. |
| How do you create a scheduling diagram? | Give one worker the critical path. Next, go task by task and give them to first available worker. If there is a choice of activities for a worker, give them the one with the lowest late time. |
| What do we use Floyd's algorithm for? | Finding the shortest distance between every pair of vertices |
| What two tables are used for Floyd's algorithm? | One which says the shortest distance and one which says which nodes it goes via. |
| How do we apply Floyd's? | Write direct distances in the table (use infinity if there is no connection). Then focus on the table node by node. If a route is shorter if it goes via that node, then replace the value. Use iterations = no. nodes |
Created by:
XanderMoore
Popular Math sets