Answer to Question #271086 in Operations Research for Tarurendra Kushwah

Question

Write the Kuhn-Tucker conditions for the following problems and obtain the optimal solution:

Minimize                    Z= 2x₁+3x₂-x₁²- 2x₂²

Subject to      x₁+3x₂ ≤ 6,

 5x₁+2x₂ ≤ 10,

               x₁, x₂≥ 0

Answer 1

1) $g_{i}(x^*)-b_{i}$ is feasible for $i=1,2....m$

Where $g_{i}(x^*)$ is optional value

Writing the equation in residue form

$f)x)=2x_{1}+3x_{2}-x_{1}^2-2x_{2}^{2}$

$g_1(x)=x_1+3x_2-6$

$g_2(x)=5x_1+2x_2-10$

Applying the Kuhn-Tucker conditions (Optimality Condition)

2)

$\begin{pmatrix} \frac { \partial\>f}{\partial\>x_1} \\\\ \frac{\partial\>f}{\partial\>x_2} \end{pmatrix}$ $+\lambda1$ $\begin{pmatrix} \frac{\partial\>g_1}{\partial\>x_1} \\\\ \frac{\partial\>g_1}{\partial\>x_2} \end{pmatrix}$ $+\lambda2$ $\begin{pmatrix} \frac{\partial\>g_2}{\partial\>x_1} \\\\ \frac{\partial\>g_2}{\partial\>x_2} \end{pmatrix}=0$

$2-2x_1+\lambda_1+5\lambda_2=0......(1)$

$3-4x_2+3\lambda_1+2\lambda_2=0.....(2)$

Feasibility condition

$x_1+3x_2\le6$ $......(3)$

$5x_1+2x_2\le10\>\>......(4)$

Complimentary slackness property

$\lambda_1(x_1+3x_2-6)=0$ $....(5)$

$\lambda_2(5x_1+2x_2-10)=0\>.....(6)$

Non-negativity constraints

$\lambda_1\ge0,\>\>\lambda_2\ge0\>\>.....(7)$

Case (i)

$\lambda_1=0,\lambda_2=0$

From (1) and(2), $2-2x_1=0\implies\>x_1=1$

$3-4x_2=0\implies\>x_2=\frac{3}{4}$

Point $(1,\frac{3}{4})$ is a KKT point

Case (ii)

$\lambda_1=0,\lambda_2\ne0$

Using (1),(2) and (6)

$2-2x_1+5\lambda_2=0$

$3-4x_2+2\lambda_2=0$

$5x_1+2x_2-10=0$

$x_1=\frac{2+5\lambda_2}{2},\>\>x_2=\frac{3+2\lambda_2}{4}$

$5(\frac{2+5\lambda_2}{2})+2(\frac{3+2\lambda_2}{4})=0$

$54\lambda_2=14$

$\lambda_2=\frac{7}{27}$

$x_1=\frac{2+5(\frac{7}{27})}{2}=\frac{89}{54}$

$x_2=\frac{3+2(\frac{7}{27})}{4}=\frac{95}{108}$

This could be a KKT point

Case(iii)

$\lambda_1\ne0,\lambda_2=0$

$2-2x_1+\lambda_1=0$

$3-4x_2+3\lambda_1=0$

$x_1+3x_2-6=0$

$x_1=\frac{2+\lambda_1}{2}$ $x_2=\frac{3+3\lambda_1}{4}$

$\frac{2+\lambda_1}{2}+\frac{3(3+3\lambda_1)}{4}=6$

$\implies\>\lambda_1=1$

Substituting in $x_1$ and $x_2$

$x_1=\frac{3}{2},\>\>x_2=\frac{3}{2}$

But $5x_1+2x_2=10.5$

This violate ......(4)

$\therefore(\frac{3}{2},\frac{3}{2})$ is not a KKT point.

Case (iv)

$\lambda_1\ne0,\>\lambda_2\ne0$

$2-2x_1+\lambda_1+5\lambda_2=0\>......(i)$

$3-4x_2+3\lambda_1+2\lambda_2=0\>....(ii)$

$x_1+3x_2=6\>.....(iii)$

$5x_1+2x_2=10\>.....(iv)$

Solving (iii) and (iv)

$5x_1+15x_2=30$

$5x_1+2x_2=10$

$\implies13x_2=20$

$x_2=\frac{20}{13}$

$x_1=\frac{18}{13}$

Substituting $x_1$ and $x_2$ in (i) and (ii)

$\lambda_1+5\lambda_2=\frac{10}{13}$

$3\lambda_1+2\lambda_2=\frac{41}{13}$

Solving

$3\lambda_1+15\lambda_2=\frac{30}{13}$

$3\lambda_1+2\lambda_2=\frac{41}{13}$

$\lambda_2=\frac{-11}{169},\>\lambda_1=\frac{185}{169}$

$\lambda_2<0$

This violates (7)

$z=2x_1+3x_2-x_1^2-2x_2^2$

Substituting point $(1,\frac{3}{4})$

$z=2(1)+3(\frac{3}{4})-(1)^2-2(\frac{3}{4})^2$

$=2.125$

Substituting point $(\frac{89}{54},\frac{95}{108})$

$z=2(\frac{89}{54})+3(\frac{95}{108}-(\frac{89}{54})^2-2(\frac{95}{108})^2$

$=1.671296$

Minimum $z=1.671296$

at point $(\frac{89}{54},\frac{95}{108})$