Operational Research Notes Flashcards
Types of sorting
Selection sort
* Each iteration, find the next smallest item in the unsorted list and swap it into the sorted list.
* By exchanging its position with the item on the far-left of the unsorted list.
Insertion sort
* Start with the unsorted list, and the left-most value in the sorted list.
* Each iteration, move the separator one to the right to include the next unsorted value.
* Then compare with each value to the left in turn, swapping places through the sorted list until that value is in position.
How to identify optimality, feasibility, and degeneracy in the simplex method
Optimal: yes, if there are no negative reduced costs.
Feasible: yes, if all constraints are met.
Degenerate: yes, if at least one basic variables is zero.
Worst/Best case linear programming problems
For a new variable, n = [min|max] r
:
if minimising r, n <= r
if maximising r, n >= r
New constraint: n free
Pivot in the simplex method
Pivot on the row that minimises b(i) / a(i,s) = basic var. / col. value