# Linear programming: how to determine if the basic solution is feasible or infeasible?

I have the primal and dual problem (with slack/excess variables)

Primal

min $$x_{1}+3x_{2}$$

s.b. $$x_{1}+w_{1}=3$$

$$x_{2}-w_{2}=2$$

$$x_{1}+2x_{2}-w_{3}=6$$

$$x_{1},x_{2},w_{1},w_{2},w_{3} \geq 0$$

Dual

max $$-3y_{1}+2y_{2}+6y_{3}$$

s.b. $$-y_{1}+y_{3}+z_{1}=1$$

$$y_{2}+2y_{3}+z_{2}=3$$

$$y_{1},y_{2},y_{3},z_{1},z_{2} \geq 0$$

I have found the basic solutions for (x,w), and the complementary solution for (y,z). Is it correct when determining whether or not the solution is feasible/infeasible, I only have to look at the solution and see if it fulfil the constraints?

For example I have the solution (x,w)=(3,0,0,-2,-3) and the complimentary (y,z)=(-1,0,0,0,3). Both infeasible as there are negative values, and the last constraint in both primal and dual has to be $$\geq 0$$

Am I on the right track? The rest of my solutions is, if the primal is feasible, then the dual is infeasible (except the optimal solution (x,w)=(2,2,1,0,0) and (y,z)=(0,0,0,1,1) both feasible)

• Welcome to Math.SE! I have tried to improve your question by fixing typo. It is possible that I unintentionally changed the meaning of your question. Please proofread the question to ensure this has not happened. – GNUSupporter 8964民主女神 地下教會 Feb 25 '19 at 20:05

Is it correct when determining whether or not the solution is feasible/infeasible, I only have to look at the solution and see if it fulfill the constraints?

Yes, to be clear, all constraints need to be satified by the basic solution.

Am I on the right track?

I don't think so. First and foremost, you've mistaken the first dual constraint. It should be $$-y_1+y_3+z_1=-1.\tag{cross out this equation}$$ The $$-1$$ in the RHS of the first dual constraint corresponds to the coefficient of $$x_1$$ in the objective function.

You need either feasibility or optimality (objective function row nonnegative in the simplex tableau) to start the simplex algorithm, but you've both primal and dual infeasible solutions $$(x,w)=(3,0,0,-2,-3)$$ and $$(y,z)=(-1,0,0,0,3)$$ respectively. Since dual feasibility corresponds to primal optimality, you have neither primal optimality nor primal feasibility.

except the optimal solution (x,w)=(2,2,1,0,0) and (y,z)=(0,0,0,1,1) both feasible

The first primal constraint $$-x_1-w_1 = 3$$ can never be satisfied as long as the decision variables are nonnegative. Therefore, the primal LP has no optimal BFS. By the Strong Duality Theorem, the dual LP also has no optimal BFS.

Your proposed primal optimal BFS is correct. To see why, continue reading.

Your proposed dual optimal BFS is incorrect since the second dual constraint is not satisfied. By inspection, $$(y,z) = (0,1,1,0,0)$$ is a BFS which gives the objective function value $$8$$. Verify that your proposed primal optimal BFS $$(x,w)=(2,2,1,0,0)$$ also gives the objective function value $$8$$. Therefore, by the Weak Duality Theorem, $$(y,z) = (0,1,1,0,0)$$ is an optimal BFS for the dual LP.

if the primal is feasible, then the dual is infeasible

The feasibility of the primal LP alone tells you nothing about that of the dual. To invoke the Strong/Weak Duality Theorem, you need both feasibility and boundedness.

In this question, rewrite the first dual constraint as $$y_1 \ge y_3+1$$ and observe that the coefficient of $$y_1$$ is positive. Therefore, with suitable $$y_2,y_3 \ge 0$$ satisfying the second dual constraint, we can take $$y_1$$ to be arbitrarily large to satisfy the first one. Therefore, the dual LP is unbounded.