Modelling With Algorithms

Question 1

What is an objective function?

Answer 1

The main formula which will maximise or minimise (usually to do with profits)

Question 2

Formulate this problem and solve for the objective function and regional inequalities

Answer 2

Question 3

Answer 3

Question 4

Find the solution

Answer 4

Question 5

Answer 5

Question 6

Answer 6

Question 7

Answer 7

Question 8

Why might a two stage simplex method be required?

Answer 8

Question 9

Also write into initial tableaux form

Answer 9

Question 10

What would happen is one of the constraints were an equality

Answer 10

Convert it into two inequalities

Question 11

Answer 11

Question 12

what is “standard linear programming form” ?

Answer 12

when the problem is formulated in terms of non negative variables as a linear objective to be maximised subject to linear constaints, each of which is less than or equal to a non-negative constant

Question 13

question

Answer 13

Question 14

what is the feasible region?

Answer 14

a set of points that satisfy all the constraints

Question 15

what are non basic variables?

Answer 15

when at least two of the vraiables in the equation are equal to 0. Including slack variables

Question 16

what are basic variables?

Answer 16

the value of the other variables when the rest are 0

Question 17

what is an integer linear programming problem?

Answer 17

• when the optimal solutuions have integer values

‘with x and y integers’

Question 18

what are the steps to choosing a pivot?

Answer 18

1. choose pivot column where the entry in the objcetive row is most negative
2. do ratio test on this column
3. choose pivot row of smallest value from the ratio test (not negative)

Question 19

How do you carry out an iteration?

Answer 19

1. each entry in pivot row is divided by value of pivot element
2. the other rows are replaced by

current row ± multiple of pivot row
3. carry on iterations until there are no more negative values in the objective function , then th optimal solution has been found

Question 20

Answer 20

use subsitution

Question 21

when would you have to use two stage simplex method?

Answer 21

• when there is a > = symbo,l
• the function included minimisng

Question 22

what are the steps to two stage simplex method augmented form?

Answer 22

• as usual slack variables are added to <= constraints
• non negative surplus variable is minus from the >= constraint
• non negative atricifical variable is also added
• all the arificial variables then make an objective function which must be minimised

Question 23

what are the steps to minimising iterations?

Answer 23

1. choose the most positive value from the minimised object function row
2. do ratio test
3. choose smallest row for pivital row
4. complete iteration
5. repeat until there are no more positive values in the minimised objective function row

Question 24

what is a graph?

Answer 24

no axis, just a diagram made up of edges and vertices

Question 25

what are nodes/ vertices?

Answer 25

circles

Question 26

what are edges /arcs?

Answer 26

lines connecting the dots

Question 27

what is the degree/order of a vertex?

Answer 27

how many lines are coming out of that circle

Question 28

what is a connected graph?

Answer 28

it is possible to go from any vertex to any other vertex

Question 29

what is the relationship between the total order and the number of vertices?

Answer 29

* total order =12 * number of arcs = 6 | total order will always be an even number

Question 30

what is a loop?

Answer 30

an edge that starts and finishes at the same vertex Order of a loop =2

Question 31

what is a simple graph?

Answer 31

one with no loops and no multiple edges between two vertices

Question 32

what is a complete graph?

Answer 32

one where every vertex is connected to every other vertex by an edge

Question 33

How many arcs are in K(n)?

Answer 33

(n*n-1)/2

Question 34

what is a digraph?

Answer 34

a graph where at least one edge has direction associated with it

Question 35

what is a bipartite graph?

Answer 35

where the nodes are in two distinct sets. Each edge connects a emeber of the first set to a member in the second set. Points do not connect with any point within it’s own set

Question 36

what is an incidence matrix?

Answer 36

shows the arrangment of edges between each node

Question 37

what is isomorphism?

Answer 37

same number of nodes and orders of each node | between2 graphs

Question 38

what is a trail?

Answer 38

a sequence of joined up edges, such that no edge is repeated | nodes can be used more than once

Question 39

what is a path?

Answer 39

a sequenece of edges such that the end vertex on one edge is the dtart of the next. No vertex can be visited more than once

Question 40

what is a cycle?

Answer 40

a closed path- where the first and last node are the same

Question 41

what is a tree?

Answer 41

a simple connected graph with the minimum number of arcs. (If a single arc is removed it will no longer be a connected graph)

Question 42

what is a spanning tree? | of graph G

Answer 42

a graph which contains all the vertcies of graph G and is also a tree

Question 43

# Q: How many arcs are there in a tree with 10 nodes?

Answer 43

n-1 10-1=9

Question 44

A simple connected graph G, has 8 vertices. * what is the minimum number of edges that G could have? * what is the maximum number of edges that G could have?

Answer 44

* minimum: 7 * maximum: (complete graph)

Question 45

what is a eulerian/ traversible graph?

Answer 45

possible to make a trail that * uses all edges once * starts and ends at the same vertex | no nodes with odd degree

Question 46

what is a semi eulerian/ traversable graph?

Answer 46

possible to make a trail * uses all edges once * starts and ends at difference vertices | will have exactly two odd nodes- start and end point

Question 47

what is a network?

Answer 47

a value (weight) is added to each arc

Question 48

Answer 48

Question 49

Draw the incidence matrix for the following arrangement

Answer 49

Question 50

Answer 50

Question 51

What are the six steps to Prims algorithm (graphically) ?

Answer 51

Question 52

Answer 52

Question 53

What are some common errors in doing prims algorithm graphically?

Answer 53

* not starting from specific node given in the question * forming a cycle by accident * not looking at all the connected vertices * not showing working out of each edge * not stating the total weight

Question 54

What are the steps to Prims algorithm (tabular)?

Answer 54

Question 55

What are some common errors when doing Prims Algorithm (tabular)

Answer 55

* not deleting a row * not looking down on all the avaible rows * not recording edges and weights * not showing working out * not stating the total weight of MST

Question 56

Answer 56

Question 57

What is a greedy algorithm?

Answer 57

it maximises the immediate rewards without considering future choices/consequences

Question 58

Why are the steps for carrying out Kruskal’s algorithm?

Answer 58

Question 59

What are the common errors in kruskals algorithm?

Answer 59

* not listing the order of arcs * accidentally forming cycles (constnatly look at the graph)

Question 60

Why can kruskals algorithm not be used in tabular form?

Answer 60

no way of knowing when cycle will be made | ∴ cannot be used by computers

Question 61

Answer 61

Question 62

Answer 62

Question 63

What are the steps for Dijkstra’s algorithm?

Answer 63

Question 64

Answer 64