Questions Wrong

Question 1

How would you modify a network to let prims find a solution with some particular arcs?

Answer 1

• make those arcs lower than all the rest around their node

Question 2

How to layout worst case

Answer 2

In worst case, total number of comparisons in the first n-1 passes is = 1 + 2 + 3 + 4 + … (n-1)
Sum = 0.5n(n-1)
= quadratic

Question 3

Explain purpose of ‘minimise’ objective function 2 marks

Answer 3

‘(Insert objective function)’ is the total cost of transporting all the required stock, calculated by finding sum

We wish total cost of transporting all required stock to be as small as possible, so ‘minimise’ is used

Question 4

Transportation problem - explain purpose of one of the ‘subject to’ lines

Answer 4

The line ‘_’. Constrains the total stock that can be shipped from supplier _ to each of the depots until the _ stock is cleared

Question 5

Interpret output to give solution to transportation problem

E.g. - value, AW = 9.00000

Answer 5

AW = 9

Question 6

For transportation problems

Answer 6

Check units of pounds - e.g. hundreds of pounds

Question 7

In a simplex q, what significance does the surplus variable have related to the range of constraint

Answer 7

Surplus variable imply the level that the constraint is being under used, so the size of the s = added potential range which wouldn’t affect final solution

Question 8

Explain why in the worst case, both packing algorithms have the same order of complexity

Answer 8

For both, each number has to be compared with all previous numbers/ bins before bein placed in a new on

Question 9

How to work out minimum number of workers needed

Answer 9

Total hours/ minimum completion time

Question 10

For cascade diagram

Answer 10

Add a third column on table for the time interval for each Activity

Question 11

To make a 3D LP into 2D

Answer 11

Rearrange for z = and substitute values into all constraints as well as objective function

Question 12

Why is first fit an example of an heuristic algorithm

Answer 12

Heuristic can find solution efficiently but no guarantee it will be optimal

Question 13

Why can’t simplex algorithm sometimes not be applied to solve the LP problem

Answer 13

If objective function = minimise, gotta switch up the vibe

Let -P = Q and maximise

Question 14

Explain why two of shortest path LP formulation = 1

Answer 14

• indicator variables take value of 1 if corresponding arc is in shortest path, 0 otherwise
• two constraints = 0 to signify that one arc out of A and one arc into G must be in the shortest path

Question 15

Explain why many constraints = 0 in shortest path LP formulation

Answer 15

• consider both cases of a vertex being either in or not in the shortest path
• if in, flow in = 1, flow out = 1, so 1-1 = 0
• if out, flow in = 0, flow out = 0, so 0-0 = 0

Question 16

What needs to be changed in the formulation of shortest path when a vertex is added

Answer 16

• add flow in and flow out to objective function
• add an additional constraint equation for its own flow in and flow out
• add flows in and flows out for the nodes it is connected to’s constraint equation.

Question 17

When given two cuts, what can u deduce about the max possible flow through the system

Answer 17

Less than or equal to the lower one

Question 18

Purpose of demand constraint in transportation problem

Answer 18

The line constrains the total amount sent to depot x, to _ - the demand at X

Question 19

Effect of an increase in supply on objective function

Answer 19

No effect

Question 20

Effect on an increase in supply constraint in a transportation problem to the constraints

Answer 20

The four stock constraints require <oe inequalities
- demand constrains require >oe inequalities

Question 21

Explain how the tableau of the 2 stage simplex first stage shows been completed

Answer 21

Feasible since Q = 0
Optimal as All values in the top row negative.

Question 22

If djikstras via a node

Answer 22

Start FROM that node.

E.g. g to j via D, start at D, and then (D->G) + (D->J)

Question 23

Significance of non zero independent float

Answer 23

IF is the max amount of time an activity can be delayed.

Activity can be delayed by size of IF without affecting the project completion time

Question 24

Constants in objective function

Answer 24

Ignore those yutes RHS is always 0

Question 25

When using full bin method

Answer 25

Try get as many full boxes as possible, and the remaining few are horrid with spare capacity

Question 26

For CPA If x is the weight of an arc, it must be

Answer 26

LESS THAN the weight of any other arc out of the corresponding node, otherwise it would be selected.

Question 27

When finding shortest path from djikstras

Answer 27

After using algorithm, work backwards to find the route

Question 28

When solving simplex graphically

Answer 28

RTQ - is the context integer solutions, i.e how many tents to build? - then use integer coordinates surrounding optimal point

Question 29

Show that the algorithms gives real root to x d.p

Answer 29

If 3d.p for example, test for f(2.9985) and f(2.9995)

Question 30

Critical paths have

Answer 30

0 float, their duration perfectly matches the timings for start and end of node

Question 31

If reducing 3d to 2d, check the

Answer 31

Positivity constraints, sub in for z>0 as this will give another line g

Question 32

Explain why a flow chart is an algorithm

Answer 32

The flow chart contains a finite sequence of operations for solving the problem of ….