Modelling with Algorithms

Question 1

How to choose a pivot : normal simplex

Answer 1

1. Pivot column is column with most negative value in the objective row
2. Pivot row is row with smallest (non negative ÷ positive) ratio test result

Question 2

How to choose a pivot : two-stage simplex

Answer 2

1. Pivot column is column with the most positive value in the Q row
2. Pivot row is row with smallest (non negative ÷ positive) ratio test result (same as normal simplex)

Question 3

How to tell that first stage is completed?

Answer 3

• Feasible since Q=0
• Optimal since there are no positive entries in the objective row for non-artificial variables

Question 4

What is an independent float?

Answer 4

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.

Question 5

Use an appropriate cut to show that X is the maximum flow

Answer 5

• 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

Question 6

What is an algorithm?

Answer 6

A finite sequence of operations for carrying out a procedure of solving a problem (should be unambiguous and deterministic)

Question 7

What is a critical activity?

Answer 7

One for which any increase in its duration results in a corresponding increase in the minimum completion time of the whole project

Question 8

What is the total float?

Answer 8

The maximum amount of time an activity can be delayed without increasing the minimum completion time of the entire project

Question 9

What is a heuristic method?

Answer 9

A method that usually finds a good solution, although not necessarily the optimal solution

Question 10

What is it called when the flow through an arc equals its maximum capacity?

Answer 10

The arc is saturated

Question 11

Which arcs can be included in the objective function for a network flow LP solver?

Answer 11

Any set of arcs that all the flow must go through

Question 12

What must you say when defining Q?

Answer 12

Q is the objective to the minimised

Question 13

What’s the dream outcome of a matching problem?

Answer 13

Maximal matching