How to choose a pivot : normal simplex
- Pivot column is column with most negative value in the objective row
- Pivot row is row with smallest (non negative ÷ positive) ratio test result
How to choose a pivot : two-stage simplex
- Pivot column is column with the most positive value in the Q row
- Pivot row is row with smallest (non negative ÷ positive) ratio test result (same as normal simplex)
How to tell that first stage is completed?
- Feasible since Q=0
- Optimal since there are no positive entries in the objective row for non-artificial variables
What is an independent float?
The maximum amount of time an activity can be delayed without delaying the early start of the succeeding activities, and without being affected by the allowable delay of any predecessor activity.
Use an appropriate cut to show that X is the maximum flow
- The capacity of the cut that splits the vertices into the sets {S,..}{T,…} is X therefore min. cut <= X
- But max flow >= X
- By the maximum flow-minimum cut theorem the maximum
flow is equal to the minimum cut and so therefore the
maximum flow through the system is X
What is an algorithm?
A finite sequence of operations for carrying out a procedure of solving a problem (should be unambiguous and deterministic)
What is a critical activity?
One for which any increase in its duration results in a corresponding increase in the minimum completion time of the whole project
What is the total float?
The maximum amount of time an activity can be delayed without increasing the minimum completion time of the entire project
What is a heuristic method?
A method that usually finds a good solution, although not necessarily the optimal solution
What is it called when the flow through an arc equals its maximum capacity?
The arc is saturated
Which arcs can be included in the objective function for a network flow LP solver?
Any set of arcs that all the flow must go through
What must you say when defining Q?
Q is the objective to the minimised
What’s the dream outcome of a matching problem?
Maximal matching
