2

I have a linear programming problem that already has the slack variables defined and is in convenient matrix form. There are no artificial variables. I've been told that $x_1$ and $x_3$ are basic variables, and I've been asked to determine whether that set of basic variables is feasible or optimal for the problem.

Thankfully, all of the problems give exactly one basic variable for each constraint, so I don't need to try to guess at interior point solutions / guess which basic variables will resolve to zero.

I'm not giving the problem, because the specific problem doesn't matter- what I need to know is the process by which I can determine whether a given set of basic variables would lend themselves to a feasible, optimal, or infeasible solution. I know how to find an optimal solution using the simplex method (in tabular or matrix form), but I have no idea how to complete this problem. I'm sure it's a relatively simple algorithm, but I'm not seeing it.

(I'm also not giving the problem because it's homework, and because I'm not sure it would be the best example for learning the algorithm.)

Parthian Shot
  • 131

1 Answers1

0

This may not be the fastest way, but after thinking about it for a bit...

If I extract the $B$ matrix (the coefficients of basic variables within the constraint equations), $b$ column vector (the constraint values), and $c_B$ (the coefficients of basic variables in the objective function), I can entirely construct a new (smaller) problem from them. In other words, I can just remove all the nonbasic variables and see if the resulting problem is solvable.

For example, if I had:

maximize: $x_1 - 2x_2 + 4x_3 - 7x_4$

s.t. $9x_1 - 3x_2 + x_3 + s_1 = 4\\ x_2 + x_4 + s_2 = 17\\ x_1, x_2, x_3, x_4, s_1, s_2 \ge 0$

And I wanted to test whether the basis $x_1, x_3$ would work, I'd simply remove all the other variables from the problem (because, being nonbasic, they'd all evaluate to zero in the end) and solve:

maximize: $x_1 + 4x_3$

s.t. $9x_1 + x_3 = 4\\ 0 = 17\\ x_1, x_3 \ge 0$

Now, in this particular case, clearly the result's infeasible because it immediately led to the contradiction $0 = 17$. But even assuming I don't notice that obvious contradiction, I can still discover the feasibility of this new problem by solving it (by, for example, adding an artificial variable for each constraint, then solving using the big M or simplex method). Any solution to this new problem will necessarily also be feasible in the original problem, and similarly if the solution to this new problem is infeasible, than it's infeasible for the original problem, and vice versa.

To determine whether the solution I've come up with is optimal for the larger problem, I'd simply need to take the final $B$ matrix and $c_B$ to generate the rest of the tabular form of the original, larger problem and, if all the coefficients of the nonbasic variables in the objective function are $\ge 0$ I know I have an optimal solution.

Parthian Shot
  • 131