Theorems

Question 1

The set of all feasible solutions of an LP problem

Answer 1

A convex set

Question 2

Extreme point theorem

Answer 2

if a set of k<=m vectors A1, A2, …, A that are linearly independent can be found such that x1A1+x2A2+…+xkAk=B and all x are >=0, then the point X = (x1, x2, …, xk, 0, …, 0) is an extreme point of the convex set of feasible solutions. The vector X in an n-dimensional vector with the last n-k components equal to 0.

Question 3

Basic feasible solution theorem

Answer 3

If X is an extreme point of k, the column vectors of A that are associated with a positive xi will form a linearly independent set such that at most m of the n xi’s are positive.

Question 4

Objective function theorem

Answer 4

The objective function of the linear programme has its optimum value at an extreme point (corner point) of k.

Question 5

Infinitely many solutions theorem

Answer 5

If the objective function values have an optimum at more than 1 corner point, it takes on the same value at a convex combination of those points.