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 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 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 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
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)
Draw the incidence matrix for the following arrangement
What are the six steps to Prims algorithm (graphically) ?
What are the steps to Prims algorithm (tabular)?
Why are the steps for carrying out Kruskal’s algorithm?
What are the steps for Dijkstra’s algorithm?
