Modelling With Algorithms Flashcards
What is an objective function?
The main formula which will maximise or minimise (usually to do with profits)
Formulate this problem and solve for the objective function and regional inequalities
Find the solution
Why might a two stage simplex method be required?
Also write into initial tableaux form
What would happen is one of the constraints were an equality
Convert it into two inequalities
what is “standard linear programming form” ?
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
what is the feasible region?
a set of points that satisfy all the constraints
what are non basic variables?
when at least two of the vraiables in the equation are equal to 0. Including slack variables
what are basic variables?
the value of the other variables when the rest are 0
what is an integer linear programming problem?
- when the optimal solutuions have integer values
‘with x and y integers’
what are the steps to choosing a pivot?
- choose pivot column where the entry in the objcetive row is most negative
- do ratio test on this column
- choose pivot row of smallest value from the ratio test (not negative)
How do you carry out an iteration?
- each entry in pivot row is divided by value of pivot element
- 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
use subsitution
when would you have to use two stage simplex method?
- when there is a > = symbo,l
- the function included minimisng
what are the steps to two stage simplex method augmented form?
- 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
what are the steps to minimising iterations?
- choose the most positive value from the minimised object function row
- do ratio test
- choose smallest row for pivital row
- complete iteration
- repeat until there are no more positive values in the minimised objective function row
what is a graph?
no axis, just a diagram made up of edges and vertices
what are nodes/ vertices?
circles
what are edges /arcs?
lines connecting the dots
what is the degree/order of a vertex?
how many lines are coming out of that circle
what is a connected graph?
it is possible to go from any vertex to any other vertex
what is the relationship between the total order and the number of vertices?
- total order =12
- number of arcs = 6
total order will always be an even number
what is a loop?
an edge that starts and finishes at the same vertex
Order of a loop =2
what is a simple graph?
one with no loops and no multiple edges between two vertices
what is a complete graph?
one where every vertex is connected to every other vertex by an edge
How many arcs are in K(n)?
(n*n-1)/2
what is a digraph?
a graph where at least one edge has direction associated with it
what is a bipartite graph?
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
what is an incidence matrix?
shows the arrangment of edges between each node
what is isomorphism?
same number of nodes and orders of each node
between2 graphs
what is a trail?
a sequence of joined up edges, such that no edge is repeated
nodes can be used more than once
what is a path?
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
what is a cycle?
a closed path- where the first and last node are the same
what is a tree?
a simple connected graph with the minimum number of arcs. (If a single arc is removed it will no longer be a connected graph)
what is a spanning tree?
of graph G
a graph which contains all the vertcies of graph G and is also a tree
Q:
How many arcs are there in a tree with 10 nodes?
n-1
10-1=9
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?
- minimum: 7
- maximum: (complete graph)
what is a eulerian/ traversible graph?
possible to make a trail that
* uses all edges once
* starts and ends at the same vertex
no nodes with odd degree
what is a semi eulerian/ traversable graph?
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
what is a network?
a value (weight) is added to each arc
Draw the incidence matrix for the following arrangement
What are the six steps to Prims algorithm (graphically) ?
What are some common errors in doing prims algorithm graphically?
- 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
What are the steps to Prims algorithm (tabular)?
What are some common errors when doing Prims Algorithm (tabular)
- 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
What is a greedy algorithm?
it maximises the immediate rewards without considering future choices/consequences
Why are the steps for carrying out Kruskal’s algorithm?
What are the common errors in kruskals algorithm?
- not listing the order of arcs
- accidentally forming cycles (constnatly look at the graph)
Why can kruskals algorithm not be used in tabular form?
no way of knowing when cycle will be made
∴ cannot be used by computers
What are the steps for Dijkstra’s algorithm?
