# Linear Program without simplex method

I want to find the "optimal set of solutions" of the linear program

$$\max \quad 3x_1 + 6x_2 + 2x_3$$ such that $$3x_1 + 4x_2 + 2x_3 \leq 200$$ $$x_1 + 3x_2 + 2x_3 \leq 100$$ $$x_j \geq 0, \quad j = 1, 2, 3$$

WITHOUT using the simplex method knowing that the problem has an optimal solution with basic variables $x_1$ and $x_2$. So I tried the following: write the dual problem, and we have that, in a step of the simplex that we have $x_1$ and $x_2$ as basic variables, we know that the coefficients of the slack variables would be a solution for the dual problem, and then would use it to calculate the optimal solution for the primal problem in this basis. But that doesn't count as using the simplex method? And even worse, we don't really have any explicit method of finding all solutions without the simplex method, do we?

This is so confusing...

• first of all, do you need software or mathematical algorithm? – dato datuashvili Dec 11 '17 at 17:29
• I'm trying to solve the problem by hand. – B. Chinaski Dec 11 '17 at 17:30

## 1 Answer

Hint: The dual program is

$$\begin{array}{}\texttt{min} \quad 200y_1+100y_2\\ \\ 3y_1+y_2\geq 3 \\ 4y_1+3y_2\geq 6 \\ 2y_1+2y_2\geq 2 \\ \\ y_1,y_2 \geq 0\end{array}$$

This program can be solved graphically. See here how it works.

Finally you apply the complementary slackness theorem to obtain the solution of the primal problem:

$x_j^*\cdot z_j^*=0 \ \forall \ \ j=1,2, \ldots , n$

$y_i^*\cdot s_i^*=0 \ \forall \ \ i=1,2, \ldots , m$

$s_i^* \text{ are the optimal values of the slack variables of the primal problem.}$

$z_j^* \text{ are the optimal values of the slack variabales of the dual problem.}$

• Thank you, @callculus, I hadn't studied about Complementary Slackness when you answered, so I couldn't understand by that time how simple it was. – B. Chinaski Dec 13 '17 at 22:39