Hey all, this is what I have made so far: Please read the end of my notes.
Got some questions/unceratinites in bold/ underlined so clarity on them would be great!
DECISION 2 EDEXCEL – MY NOTES
Daniel Baldwin
Allocation Problems :
Helpful info from SPECIFICATION :
•Cost matrix size will never exceed 5x5.
•Modification of method to deal with a maximum profit allocation.
•Formulation as a linear programming problem.
REMEMBER WITH MATRICES THEY ARE REALLY CONFUSING.
•R comes before C – rows before columns.
THE METHOD:
•If it is a maximizing problem, all values must be made negative.
•Maximizing is the same as minimizing the negative.
•Subtract every number from the largest number in the table.
•It is an N x M matrix. If N does not equal M then a dummy must be implemented.
•IF THERE IS A DASH IN THE TABLE, for maximizing problems place a zero and for minimizing, place a number twice as large.
•Every value in the dummy row/ column is zero.
•Reduce all rows firstly via taking off the smallest value from every number in each row.
•Now using the same method repeat, however, this time reduce the columns.
•Now, see if you can draw a line through each zero and if this is equal to the number of rows, you can stop. Example, if it is a 4x4 matrix then you know it is complete when you can draw a MINIMUM of 4 lines through.
•The next steps requires to change the values of the matrix to obtain an optimal solution.
•Look at the uncovered elements (no lines over them) and find the smallest value.
•Subtract this value off every single uncovered element.
•At points of intersection I.e those where 2 lines overlap, you add the value of the smallest number to it. •Now see the minimum number of lines you can draw. If it equals N, then you can assign each variable on the left column to the top row by looking at the zeros.
Formulate as a linear programming solution:
•Let xi,j = worker in row I does task j
•Xi,j = 1 if task j is allocated
•Xi,j = 0 if task j is not allocated
•I€(Columns) J€(Rows)
•Objective is either Minimize or Maximize some variable.
•The objective adds every number in the matrix up.
•The sum of each column and row must equal 1.
Feel relatively confident on this topic - 10/10
Transportation problems – Helpful INFO from the SPECIFICATION:
•Will never exceed 4x4 matrix
•Dummy locations and degeneracy are required
•Formulation as a linear programming problem.
If supply>demand then introduce a dummy.
METHOD – ISOSS – Initial, shadow, optimal, stepping stone
•Initial solution = values in matrix must equal supply/demand values.
•Number of cells used should always be 1 less than N + M
•If not, arbitrarily input a zero – this is degeneracy.
•Shadow costs – assign X1,1 as 0.
•USE the cost table and look at costs associated with those values in the NWC method
. •After shadow costs, account for uncovered elements (improvement indices)
•Improvement index <0 then it is not optimal.
•Improvement indices = Uncovered element – source cost – demand cost
•Chose the most negative index and assign it theta.
•The position off this most negative value is the entering cell.
•Follow the X's.
•Now let theta equal the smallest value ( x – Theta) and this is now assigned the exiting cell.
•Substitute this value of theta into the other values in the stepping stone.
I HATE IT WHEN THEY DO SOME OF IT FOR YOU IN QUESTIONS, IT CONFUSES ME. ALSO, SAY IF YOU HAD TO DO 2 ITERATIONS, IS IT THE EXACT SAME METHOD REPEATING EXCLUDING DOING THE INITIAL SOLUTION?
Formulation as a linear programming problem:
•Let xi,j = number transported from row I to column J
•I€(Columns) J€(Rows)
•xi,j ≥ 0 •Minimize C – this is our objective function.
•Do all demand constraints and all supply constraints. For example, If you have a 4x4 matrix where 1 row is demand and 1 row is supply, you have a 3x3 of included values therefore you should have 6 constraints.
•The constraints for minimizing will be less than/ equal to.
•You should ignore the coefficients and just have the variables.
Confidence = 7/10 - Not 100% sure about inequalities/ signs in this one. Some examples it is equal to, others less than/ equal to.
Travelling salesman:
Classical - each vertex is visited only once
Practical - each vertex is visited at least once
Walk - finite sequence of edges where the end of one edge is the start of the next
Tour - A walk that visits every vertex & returns to its starting vertex
Upper bound = any tour that works and is determined by: 1) Minimum spanning tree weight multiplied by 2. Shortcuts can be done via inspection. 2) Nearest Neighbour
•Choose a starting vertex
•Move to the nearest unvisited vertex
•Repeat step 2 until all vertices have been visited
•Return to the start vertex Lower bound is determined by:
•Take our network of nodes and arcs, remove one point and then find the minimum spanning tree for the residual sets of points and then finally rejoin the point via using the least weighted arcs.
•Residual spanning tree + 2 arcs of least weight in the original spanning tree. Best upper bound = smallest value. Best lower bound = largest value.
Seem to do alright at them but am not that confident. 8/10 Hopefully past papers soon will help.
Game Theory – Helpful Info:
•2 person game – A game involving only 2 participants.
•Zero sum game – Where one players gain is equal to another players loss (for every strategy)
•We always encounter zero sum games – we look at it from A's point of view.
•Transposing matrix for B's point of view – Line Y=-x symmetry | Multiply all numbers by –1. Rows become columns and columns become rows x –1.
•Stable solution implies row maxmin= column minimax.
•Dominance – Matrix can be reduced due to a players strategy being useless. If a row/column beats every aspect off another row/column then that one can be eliminated. For B the smallest values are the best!!!!!
•Play safe strategy = Each player is trying to make their worst outcome as good as possible.
•Look for minimum values in each row.
•Maximize this value – worst case scenario is that they gain the largest value and this is called the maximin value.
•Look for maximum values in each column.
•Find the smallest of those values – this is called the minimax.
•Row maximin = Column minimax then we have a stable solution/strategy in which case there is no point in A and B changing their strategies.
Plot the simplified equations on a graph whereabouts probability is on the x-axis and gain is on the y-axis. Probability is between 0 and 1. The point of highest intersection is the solution - it cannot exceed the feasible region.
Formulation as a linear programming problem:
•Can't use negative values. Add some value larger than the most negative value in the table.
•Let the value of the new game be V= v+n
•P1 = probability that A plays strategy I, P2 = plays strategy 2 etc
•Objective is to maximize P = V subject to constraints ≤0
•V - (µP1 + ΩP2 + πP3) ≤ 0 for each column.
•P1, P2, P3 ≥ 0
Gone through this one briefly, quite confident with it so not fully explained.
Favourite topic = 10/10
Network Flows - Source to sink.
•We want to maximize the flow.
•The idea of a cut is that we can divide the set of points into 2 distinct different sets.
•Divides the nodes into source set and the sink set. •Cut capacity looks at arcs which are going from the source set to the sink set.
•But if a line is going from the sink set to the source set then that one is not included in the cut capacity.
•To calculate cut capacity simply add capacities of those going from the source to sink set. •
If there are multiple sources / sinks, simply use super source or super sink.
•There must be no restrictions anywhere.
•The capacity of the arcs must be sufficient to feed the arcs coming out of the sources/sinks.
Method – Start of at any feasible network – often given in the question
•From this start point, see if you can improve the flow by using flow augmenting paths. > 0 possibilty of change.
•Flow has circles around their values.
Initial flow – look at arcs coming out of S or coming in to T.
•Saturated implies you cannot increase the value of the flow – 0 value going forward.
. •When looking at flow augmenting paths, find a route which goes from S to T which is larger than 0 and then look at the smallest number. The smallest number is what you can increase the backward facing arrows by, but decrease the forward facing arrows.
•Totals should always remain the same.
Questions which say "Prove that this is a maximal flow" easiest way
•Cut capacity is the same as flow. •Look at paths which are saturated as the cut will always pass these.
Confidence = 5/10
STILL QUITE WEAK AT THIS TOPIC FOR THE AUGMENTING PATHS - PAST PAPER GRIND?
Simplex:
Theory behind it:
Graphically with linear programming problems, you always start at zero and move around each of the vertices of the feasible region in turn until you have found the maximum. The algorithm is essentially moving around the constraints and trying each vertex to find the optimal solution – very helpful considering it could get extremely complicated graphically.
I have gotten much better at these and I think you just need to do examples. I do not like formulating one of these tables though - got to practise that.
Confidence = 8/10 due to the formulating ones.
Updated = 10/10 Did 5 questions on it. Doubt the formulation type question will appear.
Dynamic Programming:
No notes on this / have not looked on it! GRIND THESE QUESTIONS OUT?
Did a question and it seemed logical - Confidence =3/10
Please feel free to assist me / alter my notes / help me out! Very disheartened with how D1 and FP1 have gone so need a big show in this one. I think I will start memorising all my notes today, then over the weekend do as many past papers as I can. I will then do Solomon papers and mark each one. Should be enough by Wednesday?