Decision Maths Knowledge Flashcards
For a linear programming problem with slack variables, what are the basic variables?
Slack variables
What is the total float of an activity between i and j?
Float = late j - early i - duration
In flow charts, what does each box shape represent?
Pill shape - start/end
Rectangle - instruction
Diamond - Decision
How does bubble sort work?
Compare first two values, if in order, leave them, if notm swap them
Move onto 2nd and 3rd values until pass completed
List in order when a pass is completed with no swaps
How does quick sort work?
Select the middle value in the list as the pivot, move values to either side based on order
Middle value now in correct place
Select pivots for each side and repeat
What are the three bin packing algorithms?
First fit
First fit decreasing
Full bin
How does the first fit algorithm work for bin packing?
Take the items in the order given
Place each item in the first available bin that can take it (starting from bin 1)
What is the advantage and the disadvantage for the first fit algorithm for bin packing?
Advantage: Quick to implement
Disadvantage: Not likely to lead to a good solution
How does the first fit decreasing algorithm work for bin packing?
Sort the items into descending order
Apply the first fit algorithm to the reordered list
What are the advantages and the disadvantage for the first fit decreasing algorithm for bin packing?
Advantages: Fairly good solution & easy to implement
Disadvantages: May not get optimal solution
How does the full bin algorithm work for bin packing?
Use observation to find combinations that will fill a bin, pack these first
Any remaining are packed using first fit
What is the advantage and the disadvantage for the first fit decreasing algorithm for bin packing?
Advantage: Good solution
Disadvantage: Difficult when considering lots of items
What do the entries in an adjacency matrix show?
Describes the number of arcs joining the corresponding vertices
What value is obtained from an undirected loop in an adjacency matrix, and why?
2
Because it can be travelled in either direction
What do the entries in a distance matrix represent?
The weight of each arc joining the corresponding vertices
Outline the planarity algorithm
Identify a Hamiltonian cycle
Draw a polygon matching the Hamiltonian cycle
Draw edges inside the polygon to match those not represented by the polygon
List all edges inside the polygon
Choose any unlabelled edge and label it I for inside
Any that cross this inside edge label O for outside
Repeat for unlabelled edges
Planar if no edges cross
What is a minimum spanning tree?
A spanning tree such that the total length of its arcs is as small as possible
Outline Kruskal’s algorithm
Sort all arcs into ascending order of weight
Select the arc of least weight to start the tree
Consider the next arc: if it forms a cycle, reject it, if not, add it to the tree
Repeat until all vertices are connected
Outline Prim’s algorithm
Choose any vertex to start the tree
Select an arc of least weight that joins a vertex already in the tree to one not in the tree
Repeat until all vertices are connected
What are the three differences between Prim’s and Kruskal’s?
Prim’s consider vertices, Kruskal’s considers edges
Kruskal’s the graph is not always connected
Prim’s can be drawn from a distance matrix
What does Dijkstra’s algorithm find?
The shortest path between two nodes through a network
What does Floyd’s algorithm find?
The shortest path between every pair of vertices in a network
When using Floyd’s, what is put in place of there being no direct route between two vertices?
An infinity sign
What is the route inspection algorithm (Chinese postman) used to find?
Shortest route in a network that traverses every arc at least once and returns to its starting point
Outline route inspection algorithm
Identify vertices of odd degree
Consider all possible pairings of these vertices
Select the pairing that has the least sum
Add a repeat of the necessary arcs to the network
What is the best upper bound for travelling salesman?
Lowest possible value
What is the best lower bound for travelling salesman?
Highest possible value
How is the upper bound found for travelling salesman using minimum spanning trees?
Find the minimum spanning tree for the network using Prim’s or Kruskal’s
Double the minimum spanning tree
Seek shortcuts to bypass repeats
Use shortcut that reduces upper bound by the most
How is the lower bound found for travelling salesman?
Remove a vertex Find the residual minimum spanning tree Add to the RMST the two shortest arcs that reconnect the removed vertex Repeat for removing every vertex Highest value is the best lower bound
How is the upper bound found for travelling salesman using nearest neighbour?
Select each vertex in turn as a starting point
Go to the nearest vertex which has not been visited yet
Repeat until all vertices have been visited and return to start vertex using the shortest route (forming a tour)
Select lowest value
What is the feasible region?
The region of a graph that satisfies all the constraints of a linear programming problem
How do you solve a linear programming problem?
Find the point in the feasible region which maximises or minimises the objective function`
How can the optimal solution be found using a ruler?
Have a graph displaying the constraints and feasible region
Move a ruler parallel to the objective function
If maximising, last value in feasible region is optimal solution (reverse for minimising)
How can the optimal solution be found using the vertex method?
First find the co-ordinates of each vertex of the feasible region
Evaluate the objective function at each of these points
Select the vertex that gives the optimal value of the objective function
How do you formulate a linear programming problem?
Define decision variables
Write down the objective
Write down the constraints
How can inequalities be transformed into equations?
Slack variables
How would ‘x + y +2z =< 20’ be transformed into an equation?
x + y + 2z + r = 20
Where r is the slack variable
What does the simplex method allow you to do?
Determine if a particular vertex, on the edge of the feasible region is optimal
Decide which adjacent vertex you should move to in order to increase the value of the objective function
If the objective function is to minimise ‘P = 3x - y’, how would you rearrange this to input into a simplex tableau?
Define Q as -P
So Q = -3x + y
Q + 3x - y = 0
When the optimal solution to the problem is found and it is not an integer, but an integer solution is required, how would you find the best point?
Test the four integer points around the optimal solution against the constraints and objective function
Best answer fits constraints and maximises objective function
How are constraints transformed to equations when there are >= constraints?
Use the example ‘x + y + z >= 10’
Requires a surplus variable and an artificial variable
Transform to: ‘x + y + z - s1 + a1 = 10’
s1 is the surplus variable
a1 is the artificial variable
When artificial variables are introduced, what must be done to the simplex tableau?
New objective function I
I = -(a1 + a2 …)
When is there a feasible solution, when artificial variables are involved?
I = 0
If there is a feasible solution for two stage simplex, what must be done in the second stage?
Use the simplex method again, with the previous tableau as the starting point
Removing the I row, and the artificial variables
In the Big-M method of simplex, what is M?
An arbitrarily large method
What is the purpose of the M, in the Big-M method?
Drive the artificial variables to 0
Outline the Big-M method of simplex
Introduce a slack variable for each =< constraint
Introduce a surplus variable and an artificial variable for each >= constraint
For each artificial variable, subtract M lots of them from the objective function
Eliminate the artificial variables from your objective function so only non-basic variables remain
Formulate an initial tableau and apply simplex method
What does a precedence table show?
Which activities must be completed before others are started
For an activity network, what are represented by the arcs and nodes?
Activities by arcs
Completion of activities (called events) by nodes
What is the first node also called?
Source node
What is the last node also called?
Sink node
What are the two reasons for the use of a dummy activity?
To prevent a delay in starting an activity
Every activity must be uniquely represented in terms of its events
How can the length of time of an activity be displayed on an activity network?
Weight of the arc
What is the early event time?
The earliest time of arrival at the event allowing for the completion of the preceding activities
What is the late event time?
The latest time that the event can be left without extending the time needed for the project
How are early event times calculated?
Starting from 0 at the source node and working towards the sink node (called the forward pass)
How are late event times calculated?
Starting from the sink node and working backwards towards the source node (called the backward pass)
When is an activity critical?
If any increase in its duration would result in an increase in the duration of the whole project
What is the critical path?
A path from the source node to the sink node which entirely follows critical activities
How do you work out if an activity is critical?
Float = 0
What is total float (definition and equation) of an activity?
The amount of time that its start may be delayed without affecting the duration of the project
Total float = latest finish time - duration - earliest start time
What does a Gantt (cascade) chart provide?
A graphical way to represent the range of possible start and finish times for all activities on a single diagram
Using a Gantt chart, where would you take the 10th day to be?
Midpoint between 9 and 10
What are the rules for workers?
No worker can carry out more than one activity simultaneously
Once a worker has started an activity, they must finish it
Once a worker has finished an activity, they immediately become available to start another activity
What is used to show the number of workers that are active at any given time?
Resource histogram
What is it called to adjust the start and finish times of activities to account for constraints on resources?
Resource levelling
For a scheduling diagram, what are the tips?
Always use the first available worker
If there is a choice of activities for a worker, assign the one with the lowest value for its late time
What is the lower bound for the number of workers?
Smallest integer greater than or equal to:
Sum of all activity times / critical time of the project
