Answer to Question #267102 in Algebra for Tarurendra Kushwah

Question #267102

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

Maximize         Z = 2x1+x2-x12,

Subject to        2x1+3x2 ≤ 6,

                          2x1+x2 ≤ 4,

               x1, x2≥ 0


1
Expert's answer
2021-11-19T01:24:48-0500

Step-1 :

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


2x1+3x2+s1=62x1+x2+s2=42x_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.

Z2x12x2+x3=0Z'-2x_1-2x_2+x_3=0

2x1+3x2+s1=62x1+x2+s2=42x_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

[121100023010021001][Zx1x2x3s1s2]=[064]\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}

oror\\ [1c0A][zx]=[0b]0\begin{bmatrix} -1 & -c \\ 0 & A \end{bmatrix}\begin{bmatrix} z \\ x \end{bmatrix}=\begin{bmatrix} 0\\ b \end{bmatrix}\geq0


wheree=β0,a3=β1,a4=β2where e=β_0,a_3=β_1,a_4=β_2


Step 2:The basis matrix B1 of order(2+1)=3can be expressed asβ1=[β0β1β2]=[100010001]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

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


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


=max{[100][211230210]}=max\lbrace-\begin{bmatrix} 1 & 0&0 \end{bmatrix}\begin{bmatrix} 2 & -1& 1 \\ 2 & 3& 0\\2 & 1& 0 \end{bmatrix}\rbrace


=Max{[211]}=Max{[211]}=2(correspnds to c1z1)=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 x1x_1 is selected to enter into the basis, for k=1


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


y1=β11a1=[100010001][222]=[222]and XB=[064]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


xβryrk=min{xβiyik,yik>0}\frac{x_{\beta r}}{y_{rk}}=min\lbrace\frac{x_{\beta i}}{y_{ik}},y_{ik}\gt0\rbrace\\

=min{62,42}=min{3,2}=min\lbrace \frac{6}{2},\frac{4}{2}\rbrace\\=min\lbrace3,2\rbrace


=2(corresponds toxβ2y21)=2(corresponds\ to \frac{x_{\beta 2}}{y_{21}} )


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


The table with new entries in column Y1Y_1 and the minimum ratio






The table solution is now updated by replacing variable S2S_2 with the variable X1X_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


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


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


=max{[101][011030110]}=max\lbrace-\begin{bmatrix} 1 & 0&1 \end{bmatrix}\begin{bmatrix} 0 & -1& 1 \\ 0 & 3& 0\\1 & 1& 0 \end{bmatrix}\rbrace


=Max{[101]}=Max{[101]}=Max\lbrace-\begin{bmatrix} -1 & 0 &1 \end{bmatrix}\rbrace\\ =Max\lbrace\begin{bmatrix} -1 & 0 &-1 \end{bmatrix}\rbrace


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


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


MaxZ=4Max Z=4



Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog