Question

How to determine all the basic solutions of an optimization problem, and classify them as feasible or infeasible?

As an example,

Maximize z= 2x₁ + 3x₂

Subject to:

x₁ + 3x₂ <= 6

3x₁ + 2x₂ <= 6

x₁ + x₂ >= 0

Some solutions are (2,0), (0,2), (0,0), (6/7, 12/7), but are there more solutions? And how do you tell if they are infeasile/feasible? Would you need to graph it?

Answer 1

The basic solutions are the solutions which solve any of the constraints. However, feasible solutions are which satisfy all constraints.
So the basic solutions are all the points that lie on the lines

However out of this the feasible ones are that also satisfy the constraints, so to do that find the intersecting points on the lines

X1 = 6/7

X2 = 22/7

So feasible solutions are the points that lie on either of the line but within the following range

So from our process above we find 4 points of interest. these are actually the extreme points that satisfy our constraints. (This will be a lot more clear in the graph)
We have

(0,0), (0,2), (2,0), (6/7, 12/7)
When we put all these points in the objective function, we find that the maximum value occurs
at X2 = 12/7, X1 = 6/7 then z= 48/7
we will just plot the graph and make things clear now