1
$\begingroup$

I have the following problem: \begin{align}\min&\quad3x_1+5x_2+3x_3-2x_4+3x_5\\\text{s.t.}&\quad x_1+x_2+x_3+x_4\geq3\\&\quad3x_1+x_2+5x_3+x_4-2x_5\geq6\\&\quad x_1+2x_3-x_4\geq2\\&\quad x_1,x_2,x_3,x_4,x_5\geq0.\end{align}

My attempt: A hint is given that the first constraint can be taken as complicating constraint and the rest as easy constraints. Then, I thought maybe I could proceed taking the dual of last two constraints as I think it is impossible to proceed in primal. I named the dual variables as $w_1$ and $w_2 $, got the following program. \begin{align}\max&\quad6w_1+2w_2\\\text{s.t.}&\quad3w_1+w_2\leq3\\&\quad w_1\leq5\\&\quad5w_1+2w_2\leq3\\&\quad w_1-w_2\leq-2\\&\quad-2w_1\leq3\\&\quad w_1,w_2\geq0\end{align}

I found their values as $w_1=3/2$ & $w_2=0$ graphically. Then I thought getting into the subproblem $\max\{(wA-c)x+\alpha\}$ to use the dual values I obtained, but I don't have the $\alpha$ value which corresponds to the row zero of lambda one.

How do you think I should proceed?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.