Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
79 Cards in this Set
- Front
- Back
|
In flows what's S? |
The source |
|
|
In flows what's T? |
Sink |
|
|
How are flows notated in diagrams? |
They are Circled |
|
|
When an edge has capacity 4 and flow 4 what is it? |
Saturated |
|
|
What 3 things needed for feasible flow? |
|
|
|
In flows, what do cuts count? |
Capacity |
|
|
What do u do if edges in cuts go from sink to source? |
Not count it bc it should always goes from source to sink |
|
|
What's the bottleneck theorem? |
Max flow = min cut |
|
|
Labeling procedure for flows? |
|
|
|
What's a super source or super sink? |
If a diagram has multiple sources/sink then they are all connected to the super |
|
|
How to find cuts with min/max capacities? |
|
|
|
How do u deal with restricted vertices? |
Split them into 2 vertices (V1, V2) 1 is entry 1 is exit |
|
|
What's the instructions for Hungarian algorithm? |
1. Find the smallest number in each row and take away from that row.
2. Now find the smallest number in each column and take away from that column
3. Cover all zeroes by using as few vertical and horizontal lines
4. Circle the smallest non crossed out number and add for cross and take away for empty
5. Repeat this untill you have optimal number of lines |
|
|
What do u need to remember when doing hungarian? |
Put whether you need to augment or if it's optimal |
|
|
What does the Hungarian algorithm do? |
Minimises |
|
|
How do we change Hungarian from minimise to maximise? |
Subtract all the numbers in the matrix by the largest number to form a new matrix |
|
|
How do we sort out restricted verticies? |
Replace it with 2 verticies labeled V1 and V2 linked by an edge with the capacity of the restriction |
|
|
In dynamic programming what is a vertex called? |
A state |
|
|
In dynamic programming what is an edge called? |
An action |
|
|
In dynamic programming what is a stage of a vertex |
The maximum number of actions required to get to the end state |
|
|
What is dynamic programming? |
Working backwards to find the best solution - usually in a table |
|
|
How do we actually dynamically program? |
**** KNOWS |
|
|
What do we do when a Hungarian matrix is not square? |
Add dummy values into the row/coloum and proceed as normal - must be the highest number |
|
|
What do we need to do to turn something into a simplex problem |
Add slack variables - turn inequalities into equations |
|
|
What do we need to make sure when adding slack variables? |
That It's < |
|
|
What actually is the simplex algorithm |
1. Edit the constraints by adding slack variables and changing < to = 2. Rearrange the profit equation to = 0 3. Write a table with the column headings as all the variables from the equations. Make sure the profit equation coefficients go in the first row 4. Find the pivot equation by looking for the most negative value in the profit row 5. Find the pivot row by dividing the 'value' (end column) of each row by the number in the corresponding pivot row 6. Circle the number that intercepts the pivot row and column and write down the pivot row and column 7. Using this pivot, row reduce the table to contain 0's in the pivot column for all the rows 8. If all the values in the top row are negative then you have reached an optimal solution. If not do it again. 9. Every column with more than 1 non zero value has its variable set to 0. 10. Wtf |
|
|
In simplex, which row is always unaltered |
Pivot row |
|
|
In simplex, which row is always unaltered |
Pivot row |
|
|
How do we minimise in simplex ? |
Make P = -Q and max Q |
|
|
When does game theory apply? |
When it's a zero sum game |
|
|
What does zero sum mean |
Player 1 gain + player 2 gain = 0 |
|
|
What are the assumptions of game theory |
1. Each player has complete knowledge of all strategies 2. Choices are made simultaneously 3. Both players play sensibly |
|
|
What's a payoff matrix |
A table representing the possible outcomes of each possible pair of decisions |
|
|
What's a play safe strategy |
The option which gives the player the best of the worst possible outcome |
|
|
How do we find the play safe strategy |
1. Pick the minimum number in each row for A (write the minimum values as a column next to the matrix) and then find the max value 2. Pick the max number for player B in each column then pick the minimum value |
|
|
What's a stable solution |
When row maximin = column minimax |
|
|
What's a saddle point? |
The intersection of the play safe strategies |
|
|
When do mixed strategies apply? |
When there is no stable solution |
|
|
When do mixed strategies apply? |
When there is no stable solution |
|
|
When is a strategy dominated? |
When the outcome of another strategy is always better |
|
|
How do we find a mixed strategy for 2x2 matrixes ? |
1. Write the probability next to the matrix 2. Write down the probability of a player playing a strategy (4p + 5(1-p)) 3. Do this for the other strategy and solve simultaneously |
|
|
How do we find a mixed strategy for 2x2 matrixes ? |
1. Write the probability next to the matrix 2. Write down the probability of a player playing a strategy (4p + 5(1-p)) 3. Do this for the other strategy and solve simultaneously |
|
|
How do we find a mixed strategy for 2x2 matrixes ? |
1. Write the probability next to the matrix 2. Write down the probability of a player playing a strategy (4p + 5(1-p)) 3. Do this for the other strategy and solve simultaneously |
|
|
How do we find mixed strategies for 2x3 matrixes |
Do everything normally but then draw a H graph. Draw all the probability equations on the graph and find the highest point under all 3 graphs. Solve this point simultaneously. |
|
|
What is critical path analysis |
A way to analyse complex projects |
|
|
Whats the notation look like for critical path analysis |
|
|
|
How do u calculate earliest start time (EST) |
maximum(EST of previous activity + duration of previous activity) |
|
|
How do we calculate latest finish time (LFT) |
minimum(LFT of the following activity - duration of the following activity) |
|
|
How do we find slack / float in critical path analysis |
LFT - (EST + duration) |
|
|
How do we find critical path in critical path analysis |
Path of EST + duration = LFT |
|
|
What's the capacity of a cut |
The sum of the edges which cross the cut from source to sink |
|
|
What's an important thing to remember when rewriting the profit function? |
Keep constants to the right |
|
|
What is the y axis of the H graph? |
Points of the players strategies |
|
|
Where is the solution in the H graph? |
The highest point under all 3 graphs |
|
|
What's a cascade / Gantt chart? |
Shows which activities are taking place at what time |
|
|
What is a resource histogram? |
Shows the number of resources required at different times |
|
|
How to do simplex 2.0 |
1. Write all info in a table. With variables at the top eg P, x y z r s t ,value. Placing the profit row at the top. Make sure to write R¹ R² etc next to each row.
2. Find the most negative value in the profit row. This is your pivot column.
3. Divide the 'value' in the last column by each corresponding number in the pivot column.
4. Find the smallest positive answer and this is your pivot row.
5. Circle the number where the pivot row and column row intercept .
6. Aim to make all the other numbers in the pivot column 0 by using the pivot row and the row in question eg 4R¹ - 3R² = 0
7. When all the values in the top row is positive you have an optimal solution! 8. Every column with more than 1 non zero value has its variable set to 0. For the rest divide the number in the value column by the number in the variable column |
|
|
If there are 3 strategies in a mixed game what are the probabilities? |
p q 1-p-q |
|
|
What's the format for cuts? |
|
|
|
When doing min/max network what do the inflow and black flow have to equal? |
The difference between the minimum capacity and max capacity |
|
|
How do u find maximin in dynamic programming? |
Minimises the total value for each state and maximise it |
|
|
What does simplex algorithm do? |
Maximises |
|
|
How does the play safe strategy look like on a matrix? |
|
|
|
Make sure you draw all the possible tasks in a gantt chart |
Ok |
|
Where do we put the **** if we want an optimal strategy for Rodger? |
At the side then work out for C¹ C² C³ |
|
|
In dynamic programming if they ask for minimax or maximin then it may not be cumulative |
|
|
|
What's an important physics rule to remember with path analysis histograms? |
If a task overhangs then it falls to the ground |
|
|
What should you do when you have found the optimum solution in Hungarian? |
Circle the matchings (0's) |
|
|
What do u do when doing a mixed strategy and one row/column is dominated? |
Ignore that row in the mixed strategy . Delete it |
|
|
What's the value of a matrix? |
Sum of pixi basically. It's the expected value (average) |
|
|
How should a mixed strategy H diagram look like? |
|
|
|
How should you write the strategies for a mixed game at the end? |
|
|
|
Proper define zero sum game in words |
|
|
|
How to draw Gantt charts |
1. Do the critical path(s) at the bottom. (They have no slack so no dotted lines) 2.draw the other paths with the slack as dotted lines |
|
|
How to interpret final tableus |
1. Look at each variables column 2. If a variable has only 1 non-zero number in the column then the answer is that number/value of row |
|
|
How to find mixed strategy for guy whose matrix it is (on right hand side) |
Put the probabilities on LHS e.g. p and 1-p and then solve for the guy at top |
|
|
How do u find the value of a mixed game |
Once u found p and/or q sub them back into any expected gains (lines on the H graph) |
|
|
What's different between doing dynamic programming and finding a maximum or minimum and finding a maximin or minimax |
Maximin/minimax - the calculation isn't cumulative, instead u find the max/min between the current action and the value of the action you are headed to. |
|
|
If u add a fake field in Hungarian can u use it at the end? |
No |
