1
$\begingroup$

This is the Optimization Problem:

Minimize $C = x_4 + x_5$

Subject to constraints:

$x_1 + x_2 + x_4 = 2$

$2x_1 - x_3 + x_5 = 1$

I converted it to maximization: so my objective function becomes

Maximize $P = -x_4 - x_5 $

=> $x_4 + x_5 + P = 0$

And my tableau becomes:

1 1 0 4 0 | 2 ~ constraint

2 0 -1 0 1 | 1 ~ constraint

0 0 0 1 1 | 0 ~ objective function

Basically, I'm not quite sure how to choose my pivot here, or if I set this up even correctly

$\endgroup$
0
$\begingroup$

I suppose that all variables are positive. Otherwise, the question wouldn't make sense.

Observe that $(x_4,x_5) = (2,1)$ is a basic feasible solution.

Your tableau should be

\begin{array}{l|rrrrr|rr} & x_1 & x_2 & x_3 & x_4 & x_5 & \text{RHS} & \text{ratio}\\ \hline x_4 & 1 & 1 & 0 & \color{red}{1} & 0 & 2 \\ x_5 & 2 & 0 & -1 & 0 & 1 & 1 \\ \hline z & 0 & 0 & 0 & 1 & 1 & 0 \\ \end{array}

Note that the $x_4,x_4$-entry should be $1$ instead of $4$ as the coefficient of $x_4$ in the first constraint is one.

Before starting the simplex method, in the tableau, you have to make the columns representing the current basis ($x_4,x_5$-columns in this case) elementary, subtract the $x_4,x_5$-rows from the $z$-row.

\begin{array}{l|rrrrr|rr} & x_1 & x_2 & x_3 & x_4 & x_5 & \text{RHS} & \text{ratio}\\ \hline x_4 & 1 & 1 & 0 & \color{red}{1} & 0 & 2 & 2/1 = 1 \\ x_5 & 2^* & 0 & -1 & 0 & 1 & 1 & 1/2 = 1/2 \\ \hdashline z & -3^* & -1 & 1 & 0 & 0 & -3 \\ \hline x_4 & 0 & 1^* & 1/2 & 1 & -1/2 & 3/2 & 3/2 \\ x_1 & 1 & 0 & -1/2 & 0 & 1/2 & 1/2 & - \\ \hdashline z & 0 & -1^* & 5/2 & 0 & 3/2 & -3/2 \\ \hline x_2 & 0 & 1 & 1/2 & 1 & -1/2 & 3/2 & - \\ x_1 & 1 & 0 & -1/2 & 0 & 1/2 & 1/2 & - \\ \hdashline z & 0 & 0 & 3 & 1 & 1 & 0 \end{array}

The basic solution $(x_1,x_2) = (1/2,3/2)$ gives the minimum value $0$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.