Operational Research Notes

Question 1

Types of sorting

Answer 1

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.

Question 2

How to identify optimality, feasibility, and degeneracy in the simplex method

Answer 2

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.

Question 3

Worst/Best case linear programming problems

Answer 3

For a new variable, n = [min|max] r:
if minimising r, n <= r
if maximising r, n >= r
New constraint: n free

Question 4

Pivot in the simplex method

Answer 4

Pivot on the row that minimises b(i) / a(i,s) = basic var. / col. value