0
$\begingroup$

(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

$\endgroup$
3
  • 1
    $\begingroup$ hi. welcome to Stackexchange. it would be better if you write the variable with index ($x_{1}, x_{2}$) instead of $x1, x2$ and what does $4..1$ means? $\endgroup$ Commented Apr 19, 2019 at 18:48
  • $\begingroup$ Please do proper formatting of your question, especially the equations and the problem formulation. $\endgroup$ Commented Apr 19, 2019 at 19:11
  • 1
    $\begingroup$ im sorry i new, is it ok now? $\endgroup$ Commented Apr 19, 2019 at 19:35

1 Answer 1

Reset to default
0
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ thankyou for the answer. i would like to know the reason why we have to introduce x1 and x2 as artificial variable for this problem. and also suppose i have $\begin{array}{l} u=10−3x_1−3x_2+x_4+x_3\\ 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 \end{array}$ which variable will be departing and entering variable? here, i choose x1 because it is negative in the objective function u , but the ratio in v1 is 4, in v2 is 3, and in x5 is 1, should i choose x5 as departing variable? thanks!! $\endgroup$ Commented Apr 24, 2019 at 12:12
  • $\begingroup$ You add artificial variables $v_1, v_2$ so that you can get your identity matrix for the initial basis. Look at the matrix you got in (3) and you see there is no identity matrix there. About the departing and entering variables: in phase 1, your tableau should look like what you have in (4), $min u=v_1+v_2$. Also, keep in mind you do the pivot operations on the positive elements. You don't choose $x5$ since it's -1. Therefore, $v2$ which has the ratio of 3 is the departing. Check this link for a better understanding of 2-phase:maths.qmul.ac.uk/~ffischer/teaching/opt/notes/notes8.pdf $\endgroup$ Commented Apr 24, 2019 at 14:05
  • $\begingroup$ thankyou so much!! is this because if i choose $4-x_1 \geq 0$ constrain is 4, and $6-2x_1 \geq 0$ constrain is 3, so i can minimize u to 1 when all the non basic variable is 0 while for x5 $1+x_1 \geq 0$ means $x_1 \geq -1$ so u will be 13(?) $\endgroup$ Commented Apr 24, 2019 at 16:25
  • $\begingroup$ Yeah, that's right. You are trying to find the maximum amount you can increase a variable before any constraint is violated. So, the min of ${4/1, 6/2}=3$. You can see that if you choose 4, then $6-2*4 <0$ which violates the constraint and with -1, your rhs will become negative and makes it an infeasible basis. If these explanations help, please don't forget to upvote and accept the answer :) $\endgroup$ Commented Apr 24, 2019 at 16:40
  • $\begingroup$ thankyou so much but i still have some doubt, for x1 can you please show which rhs become negative? and also what is the reason we cant use negative element as pivot? in question 3 i was asked to find all basic feasible solutions, i though it can be found by inverse matrix $Ax=b$ so $x=A^{-1}b$, but it means i need to find inverse of 3x3 matrix, what is the correct approach(?) thankyou so much!!! $\endgroup$ Commented Apr 24, 2019 at 18:20

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.