Answer to Question #267102 in Algebra for Tarurendra Kushwah

Question

Solve the following quadratic programming problem(Wolf’s method)

Maximize         Z = 2x₁+x₂-x₁²,

Subject to        2x₁+3x₂ ≤ 6,

                          2x₁+x₂ ≤ 4,

               x₁, x₂≥ 0

Answer 1

Step-1 :

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate.

$2x_1+3x_2+s_1=6\\2x_1+x_2+s_2=4$

The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate.

$Z'-2x_1-2x_2+x_3=0$

$2x_1+3x_2+s_1=6\\2x_1+x_2+s_2=4$

Now represent the new system of constraint equations in the matrix form

$\begin{bmatrix} 1 & -2&-1&1&0&0 \\ 0 & 2&3&0&1&0\\0 & 2&1&0&0&1 \end{bmatrix}\begin{bmatrix} Z'\\ x_1\\x_2\\x_3\\s_1\\s_2 \end{bmatrix}=\begin{bmatrix} 0 \\ 6\\4 \end{bmatrix}$

$or\\$ $\begin{bmatrix} -1 & -c \\ 0 & A \end{bmatrix}\begin{bmatrix} z \\ x \end{bmatrix}=\begin{bmatrix} 0\\ b \end{bmatrix}\geq0$

$where e=β_0,a_3=β_1,a_4=β_2$

$Step\ 2:The\ basis \ matrix\ B_1\ of\ order (2+1)=3 can\ be\ expressed\ as\\ \beta_1=\begin{bmatrix} \beta_0 & \beta_1&\beta_2 \\ \end{bmatrix}=\begin{bmatrix} 1 & 0&0\\ 0& 1&0\\0 & 0&1 \end{bmatrix}$

Iteration=1 : Repeat steps 3 to 5 to get new solution

Step-3: To select the vector corresponding to a non-basic variable to enter into the basis, we compute

$c_k-z_k=Max\lbrace{(c_j-z_j)>0;j=1,2}\rbrace$

$=Max\lbrace{-(1^{st}\ row\ of\ \beta_1^{-1})(Columns\ a_j\ not\ in\ basis)}\rbrace$

$=max\lbrace-\begin{bmatrix} 1 & 0&0 \end{bmatrix}\begin{bmatrix} 2 & -1& 1 \\ 2 & 3& 0\\2 & 1& 0 \end{bmatrix}\rbrace$

$=Max\lbrace-\begin{bmatrix} -2 & -1 &1 \end{bmatrix}\rbrace\\ =Max\lbrace\begin{bmatrix} 2 & 1 &-1 \end{bmatrix}\rbrace\\ =2 (correspnds\ to\ c_1-z_1)$

Thus, vector $x_1$ is selected to enter into the basis, for k=1

Step-4: To select a basic variable to leave the basis, we compute $y_k$ for k=1, as follows

$y_1=\beta_1^{-1}a_1=\begin{bmatrix} 1 & 0&0\\ 0& 1&0\\0 & 0&1 \end{bmatrix}\begin{bmatrix} -2\\ 2\\2 \end{bmatrix}=\begin{bmatrix} -2\\ 2\\2 \end{bmatrix}and\ X_B=\begin{bmatrix} 0\\ 6\\4 \end{bmatrix}$

Now, calculate the minimum ratio to select the basic variable to leave the basis

$\frac{x_{\beta r}}{y_{rk}}=min\lbrace\frac{x_{\beta i}}{y_{ik}},y_{ik}\gt0\rbrace\\$

$=min\lbrace \frac{6}{2},\frac{4}{2}\rbrace\\=min\lbrace3,2\rbrace$

$=2(corresponds\ to \frac{x_{\beta 2}}{y_{21}} )$

Thus, vector $S_2$ is selected to leave the basis, for r=2

The table with new entries in column $Y_1$ and the minimum ratio

The table solution is now updated by replacing variable $S_2$ with the variable $X_1$ into the basis.

For this we apply the following row operations in the same way as in the simplex method

The improved solution is

Iteration=2 : Repeat steps 3 to 5 to get new solution

Step-3: To select the vector corresponding to a non-basic variable to enter into the basis, we compute

$c_k-z_k=Max\lbrace{(c_j-z_j)>0;j=1,2}\rbrace$

$=Max\lbrace{-(1^{st}\ row\ of\ \beta_1^{-1})(Columns\ a_j\ not\ in\ basis)}\rbrace$

$=max\lbrace-\begin{bmatrix} 1 & 0&1 \end{bmatrix}\begin{bmatrix} 0 & -1& 1 \\ 0 & 3& 0\\1 & 1& 0 \end{bmatrix}\rbrace$

$=Max\lbrace-\begin{bmatrix} -1 & 0 &1 \end{bmatrix}\rbrace\\ =Max\lbrace\begin{bmatrix} -1 & 0 &-1 \end{bmatrix}\rbrace$

$Since\ all\ Z_j-C _j≥0$

$Hence, optimal\ solution\ is\ arrived\ with\ value\ of\ variables\ as :\\ x_1=2,x_2=0,x_1^{2}=0$

$Max Z=4$