(P)
$\min z=x_1+x_2$
subject to :
$
x_1+2x_2 \geq 4$ ( equation 1)
$2x_1+x_2\geq6$ (equation 2)
$-x_1+x_2\leq1$ (equation 3)
$x_1>=0 ,x_2\geq0 $$
$
I'm trying to solve this using two-phase method, please review my answer.
2.) For the problem (P), use
the nonnegative variable $x_3$ for inequality constraint 1 and the nonnegative variable $x_4$ for inequality constraint 2 and the nonnegative variable $x_5$ for inequality 3 then Show the equation standard form of the problem (P).
standard form
$\min u=x_1+x_2$ or $u=-x_1-x_2$ (?)
subject to
$x_1+2x_2-x_3=4 $
$2x_1+x_2- x_4=6 $
$-x_1+x_2+ x_5=1 $
(3) Find all feasible basis
solutions of the equation standard form of the problem (P) obtained in (2).
I'm not sure how to find the feasible basis(?)
\begin{bmatrix}
1 & 2 & -1 & 0 & 0 \\
2 & 1 & 0 & -1 & 0 \\
-1 & 1 & 0 & 0 & 1 \\
\\
\end{bmatrix}
am I right?
(4) from the standard form
matrix that obtain in number 2, Consider the artificial variable (the problem of the first phase) when applying the two-step method, introduced artificial variable $v_1$ and $v_2$. find dictionary for base variable $v_1,v_2,v_5$
dictionary
we input $v_1$ and $v_2$ as artificial variable
$\min u=v_1+v_2$
subject to
$x_1+2x_2-x_3+v_1=4 $
$2x_1+x_2- x_4+v_2=6$
$-x_1+x_2+ x_5=1 $
the reason is that if non-basic variable are all $0$ then the basis variable will produce a feasible solution $(4,6,1)$
5) From problem 4, show the
optimal dictionary
$\min u=10-3x_1-3x_2-x_3-x_4 $
$v_1=4-x_1-2x_2+x_3 $
$v_2=6-2x_1-x_2+x_4$
$x_5=1+x_1-x_2 $
here I need to find the optimal solution that produces z =0 ? until artificial variable =0?
am i right??
6. Use the feasible basis
solution obtained from the optimal dictionary in (5), find the first dictionary from the standard matrix form (P) and optimal solution
of the problem (P),
is this the two-phase ? and solve this using tableau?
how to know if the answer is optimal or not?
to optimize number 4, we need to make sure all artificial variables are 0(?)
I'm confused, I have read about this but I can't seem to understand
Best Answer
(2) It seems you want the standard form of the problem, not necessarily phase 1. In that case, $min z = x_1 +x_2$ which will translate to $z - x_1 - x_2 = 0$ in your simplex tableau.
(3) To start simplex, you start with one initial feasible basis solution. And an easy initial solution is putting the slack variables on the left-hand side (the dictionary that you will get to in part 4). But here that won't work and you need to introduce artificial variables. I think that's the point of the exercise for you to get to this part. If not, remember that you don't need to necessarily start from the origin (what you get by making every variable 0). You just need an initial solution.
(4) You got it.
(5) Goal of phase 1 is that you can hopefully get to the $v_1 + v_2 = 0$. That way you don't need artificial variables, you are now in a feasible corner in your original problem and you can carry on with the primal simplex algorithm as usual.
(6) This is phase 2 of your two-phase method. As I said in (5), you can now just continue with your normal simplex algorithm. The optimality condition is as usual: when you have all non-negative reduced costs in your simplex tableau (remember that the reduced cost of the basic variables are zero).