2
$\begingroup$

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...

$\endgroup$
2
  • $\begingroup$ first of all, do you need software or mathematical algorithm? $\endgroup$ Commented Dec 11, 2017 at 17:29
  • $\begingroup$ I'm trying to solve the problem by hand. $\endgroup$ Commented Dec 11, 2017 at 17:30

1 Answer 1

Reset to default
1
$\begingroup$

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.}$

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Dec 13, 2017 at 22:39

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.