Check if a linear programme is solvable

We are going to use the feasibility algorithm for a linear programme to do this - lets call this that takes a linear programme and outputs a boolean based on if it is feasible or not.

This uses a corollary of the Weak duality theorem (linear programme) which tells us unbounded linear programmes have infeasible duals. So we will check if the dual linear programme is feasible. For this let be an algorithm to calculate the dual.

Algorithm

bounded_checker(A, b, c):
	Input: A linear programme in standard form specified by A, b, c.
	Output: Whether or not that linear programme is feasible and bounded, infeasible or unbounded.
1. Run feasibility_checker(A, b, c)
	1. If it is not feasible return that it is infeasible
2. Calculate the dual linear programme dual(A,b,c) = A^d, b^d, c^d.
3. Check if the dual is feasible feasibility_checker(A^d, b^d, c^d)
	1. If it is return that the original linear programme is solvable.
	2. If it is not return that the original linear programme is unbounded.