\begin{eqnarray*} \max \ u(x_1, x_2) \\ a_{11}x_1 + a_{12}x_2 &\le &b_1\\ a_{21}x_1 + a_{22}x_2 &\le &b_2 \end{eqnarray*} In diesem Fall müssen die Nebenbedingungen in Form von Ungleichungen geschrieben werden, da im Optimum in der Regel eine Nebenbedingung nicht als Gleichung erfüllt ist; nur im Schnittpunkt $(e)$ der beiden Restriktionsgeraden sind beide Nebenbedingungen streng erfüllt. Außerdem müssen Nichtnegativitätsbedingungen erfüllt sein: \begin{equation*} x_1, x_2 \ge 0 \end{equation*}

Zwei lineare Beschränkungen
Ferner wird angenommen, dass die beiden linearen Beschränkungsgeraden nicht parallel zueinander verlaufen und ihren Schnittpunkt im positiven Quadranten haben. Andernfalls würde jeweils nur eine Beschränkung greifen. Ohne Beschränkung der Allgemeinheit wird angenommen, dass die zur ersten Nebenbedingung gehörende Beschränkungsgerade steiler fällt als die zur zweiten Nebenbedingung gehörende. Damit ergibt sich: \begin{equation}\label{eq:26} {b_1\over a_{11}} < {b_2 \over a_{21}} \qquad {b_1\over a_{12}} > {b_2 \over a_{22}} \qquad (26) \end{equation}

Daraus ergibt sich auch, dass alle $a_{ij} > 0$.

Als Lagrangefunktion ergibt sich: \begin{equation*} L =u(x_1,x_2) + \lambda_1(b_1 - a_{11}x_1 - a_{12}x_2) + \lambda_2(b_2- a_{21}x_1 - a_{22}x_2)\\ \end{equation*} Die Optimalitätsbedingungen lauten:
  1. $ {\partial L\over \partial x_1} = {\partial u\over \partial x_1} - a_{11}\lambda_1 - a_{21}\lambda_2 \le 0 $

    $ {\partial L\over \partial x_2} = {\partial u\over \partial x_2} - a_{12}\lambda_1 - a_{22}\lambda_2 \le 0 $
  2. $ {\partial L\over \partial \lambda_1} = b_1 - a_{11}x_1 - a_{12}x_2 \ge 0 $

    $ {\partial L\over \partial \lambda_2} = b_2 - a_{21}x_1 - a_{22}x_2 \ge 0 $
  3. $ x_1, x_2,\lambda_1, \lambda_2 \ge 0$
  4. Bedingungen vom komplementären Schlupf:

    $x_1 {\partial L\over \partial x_1} = 0, \qquad x_2 {\partial L\over \partial x_2} = 0,\qquad \lambda_1 {\partial L\over \partial\lambda_1} = 0,\qquad \lambda_2 {\partial L\over \partial\lambda_2} \ = 0$

Vorüberlegung:
  1. Im Prinzip müssen nebenstehende Möglichkeiten also insgesamt $2^4 = 16$ Möglichkeiten untersucht werden.
  2. Gibt es im positiven Quadranten einen zulässigen Punkt und ist die Nutzenfunktion monoton, so kann $x_1=0, x_2=0$ kein Maximum sein.
  3. Ist $\lambda_1=0$ und $\lambda_2=0$, so ist wegen der Bedingungen vom komplementären Schlupf ${\partial L\over \partial \lambda_1}>0 \text{ und } {\partial L\over \partial \lambda_2} > 0$. Das wiederum bedeutet, dass keine der Nebenbedingungen als Gleichung erfüllt ist. Ist die Nutzenfunktion monoton, so ist das nicht optimal.
     
 $x_1$   $x_2$   $\lambda_1$   $\lambda_2$
   0   0   0   0
  0   0   0   $>$0
  0   0   $>$0   0
  0   0   $>$0   $>$0
  0   $>$0   0   0
  0   $>$0   0   $>$0
  0   $>$0   $>$0   0
  0   $>$0   $>$0   $>$0
  $>$0   0   0   0
  $>$0  0   0   $>$0
  $>$0  0   $>$0   0
  $>$0  0   $>$0   $>$0
  $>$0  $>$0   0   0
  $>$0  $>$0   0   $>$0
  $>$0  $>$0   $>$0   0
  $>$0  $>$0   $>$0   $>$0
  1. Somit bleiben als sinnvolle Möglichkeiten vorläufig nebenstehende neun Möglichkeiten übrig, die jetzt nacheinander untersucht werden.
$x_1$ $\quad x_2$ $\quad \lambda_1$ $\quad \lambda_2$
Fall a ${\partial L\over \partial x_1} < 0 \Rightarrow\Biggl\{$ $0$ $>0$ $0$ $>0$
$0$ $>0$ $>0$ $0$
$0$ $>0$ $>0$ $>0$
 
Fall b ${\partial L\over \partial x_2} < 0 \Rightarrow\Biggl\{$ $>0$ $0$ $0$ $>0$
$>0$ $0$ $>0$ $0$
$>0$ $0$ $>0$ $>0$
 
Fall c $>0$ $>0$ $0$ $>0$
 
Fall d $>0$ $>0$ $>0$ $0$
 
Fall e $>0$ $>0$ $>0$ $>0$

Fall a: ${\partial L\over \partial x_1} < 0$
Wegen der Bedingung vom komplementären Schlupf ($x_1{\partial L\over\partial x_1} = 0$) gilt $x_1=0$. Damit ergibt sich für die Nebenbedingung des Optimierungsproblems: \begin{eqnarray} \label{eq:47}\underbrace{a_{11}x_1}_{=0} + a_{12}x_2 \le b_1 \Rightarrow a_{12}x_2 \le b_1 \Rightarrow x_2 \le {b_1 \over a_{12}} \qquad (47)\\ \label{eq:48}\underbrace{a_{21}x_1}_{=0} + a_{22}x_2 \le b_2 \Rightarrow a_{22}x_2 \le b_2 \Rightarrow x_2 \le {b_2 \over a_{22}} \qquad (48) \end{eqnarray} Nach der Annahme in (26) lassen sich (47), (48) wie folgt zusammenfassen: \begin{equation} x_2 \le {b_2 \over a_{22}} \end{equation} Für den Fall a sind folgende Möglichkeiten für $\lambda_1, \lambda_2$ zu untersuchen:
  1. $\lambda _1=0, \lambda_2>0$
  2. $\lambda _1>0, \lambda_2=0$
  3. $\lambda _1>0, \lambda_2>0$

Möglichkeit a1: $\lambda _1=0, \lambda_2>0$
Da $\lambda_2>0$, folgt aus der Bedingung vom komplementären Schlupf: \begin{eqnarray*} {\partial L\over \partial \lambda_2} = b_2 - \underbrace{a_{21}x_1}_{=0} - a_{22}x_2 &=& 0\\ \Rightarrow b_2 - a_{22}x_2 &=& 0\\ \Rightarrow x_2 &=& {b_2 \over a_{22}} \end{eqnarray*} In diesem Fall liegt das Maximum des Optimierungsproblems bei: $x_1 =0, \quad x_2 = {b_2 \over a_{22}},\quad \lambda_1 = 0,\quad \lambda_2 > 0$

Dies entspricht einer Randlösung, bei der die zweite Nebenbedingung greift.

Möglichkeit a2: $\lambda _1>0, \lambda_2=0$
Da $\lambda_1>0$, folgt aus der Bedingung vom komplementären Schlupf: \begin{eqnarray*} {\partial L\over \partial \lambda_1} = b_1 - \underbrace{a_{11}x_1}_{=0} - a_{12}x_2 &=& 0\\ \Rightarrow b_1 - a_{12}x_2 &=& 0\\ \Rightarrow x_2 &=& {b_1 \over a_{12}} \end{eqnarray*} Bei Gültigkeit der Annahme aus (26) (${b_1 \over a_{12}} > {b_2 \over a_{22}}$) verletzt $x_2 = {b_1 \over a_{12}}$ jedoch die zweite Nebenbedingung, welche für $x_1 = 0$ bedeutet dass $x_2 \le {b_2 \over a_{22}}$ (vgl. (48)).

Diesen Zusammenhang kann man sich anhand der Abbildung \ref{fig:KuhnTuckerSystem} klar machen: dort ist erkennbar, dass bei $x_1 = 0$ und $x_2 = {b_1 \over a_{12}}$ die zweite Nebenbedingung (Beschränkungsgerade dargestellt durch die blaue Linie) verletzt wird.

$\Rightarrow x_1 =0, \quad x_2 = {b_1 \over a_{12}},\quad \lambda_1 > 0,\quad \lambda_2 = 0$ ist nicht zulässig.

Möglichkeit a3: $\lambda _1>0, \lambda_2>0$
\begin{eqnarray*} \text{Aus $\lambda_1>0$ folgt: } {\partial L\over \partial \lambda_1} = b_1 - \underbrace{a_{11}x_1}_{=0} - a_{12}x_2 &=& 0\\ \Rightarrow x_2 &=& {b_1 \over a_{12}}\\ \text{Gleichzeitig gilt:}\hspace{4.7cm}\\ \text{Aus $\lambda_2>0$ folgt: } {\partial L\over \partial \lambda_2} = b_2 - \underbrace{a_{21}x_1}_{=0} - a_{22}x_2 &=& 0\\ \Rightarrow x_2 &=& {b_2 \over a_{22}} \end{eqnarray*} Da laut (26) ${b_1 \over a_{12}} > {b_2 \over a_{22}}$, sind dies offensichtlich zwei unterschiedliche Werte für $x_2$. Somit gibt es keinen Punkt, in welchem gilt $x_1 =0,\quad \lambda_1 > 0,\quad \lambda_2 > 0$.

Fall b: ${\partial L\over \partial x_2} < 0$
Analog zu Fall a bedeutet ${\partial L\over \partial x_2} < 0 \Rightarrow x_2 = 0$: \begin{eqnarray} \label{eq:49} x_1 &\le& {b_1 \over a_{11}} \qquad (49)\\ \label{eq:50} x_1 &\le& {b_2 \over a_{21}} \qquad (50) \end{eqnarray} Insgesamt gilt also: \begin{equation*} x_1 \le {b_1 \over a_{11}} \end{equation*} Für den Fall b sind folgende Möglichkeiten für $\lambda_1, \lambda_2$ zu untersuchen:

  1. $\lambda _1=0, \lambda_2>0$
  2. $\lambda _1>0, \lambda_2=0$
  3. $\lambda _1>0, \lambda_2>0$
Möglichkeit b1: $\lambda _1=0, \lambda_2>0$
Da $\lambda_2>0$, folgt aus der Bedingung vom komplementären Schlupf: \begin{eqnarray*} {\partial L\over \partial \lambda_2} = b_2 - a_{21}x_1 - \underbrace{a_{22}x_2}_{=0} &=& 0\\ \Rightarrow x_1 &=& {b_2 \over a_{21}} \end{eqnarray*} Bei Gültigkeit der Annahme aus (26) (${b_1 \over a_{11}} < {b_2 \over a_{21}}$) verletzt $x_1 = {b_2 \over a_{21}}$ jedoch die erste Nebenbedingung, welche für $x_2 = 0$ bedeutet, dass $x_1 \le {b_1 \over a_{11}}$ (vgl. (49)).

$\Rightarrow x_1 = {b_2 \over a_{21}}, \quad x_2 = 0,\quad \lambda_1 = 0,\quad \lambda_2 > 0$ ist nicht zulässig.

Möglichkeit b2: $\lambda _1>0, \lambda_2=0$
Da $\lambda_1>0$, folgt aus der Bedingung vom komplementären Schlupf: \begin{eqnarray*} {\partial L\over \partial \lambda_1} = b_1 - a_{11}x_1 - \underbrace{a_{12}x_2}_{=0} &=& 0\\ \Rightarrow x_1 &=& {b_1 \over a_{11}} \end{eqnarray*} In diesem Fall liegt das Maximum des Optimierungsproblems bei: $x_1 = {b_1 \over a_{11}}, \quad x_2 = 0, \quad \lambda _1>0,\quad \lambda_2=0$.

Dies entspricht einer Randlösung, bei der die erste Nebenbedingung greift.

Möglichkeit b3): $\lambda _1>0, \lambda_2>0$ \begin{eqnarray*} \text{Aus $\lambda_1>0$ folgt: } {\partial L\over \partial \lambda_1} = b_1 - a_{11}x_1 - \underbrace{a_{12}x_2}_{=0} &=& 0\\ \Rightarrow x_1 &=& {b_1 \over a_{11}}\\ \text{Gleichzeitig gilt:}\hspace{4.7cm}\\ \text{Aus $\lambda_2>0$ folgt: } {\partial L\over \partial \lambda_2} = b_2 - a_{21}x_1 - \underbrace{a_{22}x_2}_{=0} &=& 0\\ \Rightarrow x_1 &=& {b_2 \over a_{21}} \end{eqnarray*} Analog zu Fall a3) verletzt $x_1 = {b_1 \over a_{11}} = {b_2 \over a_{21}} $ die Annahme aus (26), welche besagt, dass ${b_1 \over a_{11}} < {b_2 \over a_{21}}$. Somit gibt es keinen Punkt, in welchem gilt $x_2 =0,\quad \lambda_1 > 0,\quad \lambda_2 > 0$.

Fall c: $x_1 >0, x_2 > 0, \lambda_1 = 0, \lambda_2 > 0$
\begin{equation*} \left.\begin{aligned} x_1 > 0 \Rightarrow {\partial L\over \partial x_1} = {\partial u\over \partial x_1} - \underbrace{a_{11}\lambda_1}_{=0} - a_{21}\lambda_2 = 0 &\Rightarrow& {\partial u\over \partial x_1} = a_{21}\lambda_2\\ x_2 > 0 \Rightarrow {\partial L\over \partial x_2} = {\partial u\over \partial x_2} - \underbrace{a_{12}\lambda_1}_{=0} - a_{22}\lambda_2 = 0 &\Rightarrow& {\partial u\over \partial x_2} = a_{22}\lambda_2 \end{aligned} \right\} \Rightarrow \begin{aligned} {{\partial u\over \partial x_1}\over {\partial u\over \partial x_2}} = {a_{21}\over a_{22}} \end{aligned} \end{equation*} \begin{eqnarray*} \lambda_1 = 0 \Rightarrow {\partial L\over \partial \lambda_1} = b_1 - a_{11}x_1 - a_{12}x_2 &\ge& 0\\ \lambda_2 > 0 \Rightarrow {\partial L\over \partial \lambda_2} = b_2 - a_{21}x_1 - a_{22}x_2 &=& 0 \text{ d.h. zweite Nebenbedingung greift} \end{eqnarray*} Somit ergibt sich im Fall c eine innere Lösung, wobei das Maximum auf der Geraden liegt, die zur zweiten Nebenbedingung gehört.

Fall d: $x_1 >0, x_2 > 0, \lambda_1 > 0, \lambda_2 = 0$
\begin{equation*} \left.\begin{aligned} x_1 > 0 \Rightarrow {\partial L\over \partial x_1} = {\partial u\over \partial x_1} - a_{11}\lambda_1 - \underbrace{a_{21}\lambda_2}_{=0} = 0\\ x_2 > 0 \Rightarrow {\partial L\over \partial x_2} = {\partial u\over \partial x_2} - a_{12}\lambda_1 - \underbrace{a_{22}\lambda_2}_{=0} = 0 \end{aligned} \right\} \Rightarrow \begin{aligned} {{\partial u\over \partial x_1}\over {\partial u\over \partial x_2}} = {a_{11}\over a_{12}} \end{aligned} \end{equation*} \begin{eqnarray*} \lambda_1 > 0 \Rightarrow {\partial L\over \partial \lambda_1} = b_1 - a_{11}x_1 - a_{12}x_2 &=& 0\text{ d.h. erste Nebenbedingung greift}\\ \lambda_2 = 0 \Rightarrow {\partial L\over \partial \lambda_2} = b_2 - a_{21}x_1 - a_{22}x_2 &\ge& 0 \end{eqnarray*} Somit ergibt sich im Fall d eine innere Lösung, wobei das Maximum auf der Geraden liegt, die zur ersten Nebenbedingung gehört.

Fall e: $x_1 >0, x_2 > 0, \lambda_1 > 0, \lambda_2 > 0$ \begin{eqnarray*} \lambda_1 > 0 \Rightarrow {\partial L\over \partial \lambda_1} = b_1 - a_{11}x_1 - a_{12}x_2 &=& 0\hbox{ d.h. erste Nebenbedingung greift}\\ \lambda_2 > 0 \Rightarrow {\partial L\over \partial \lambda_2} = b_2 - a_{21}x_1 - a_{22}x_2 &=& 0\hbox{ d.h. zweite Nebenbedingung greift} \end{eqnarray*} Somit liegt das Maximum im Schnittpunkt der beiden zu den Nebenbedingungen gehörenden Beschränkungsgeraden.

In diesem Punkt ist das durch die beiden Beschränkungsgeraden beschriebene lineare Gleichungs\-system erfüllt: \begin{eqnarray*} a_{11}x_1 + a_{12}x_2 = b_1\\ a_{21}x_1 + a_{22}x_2 = b_2 \end{eqnarray*} bzw. in Matrizenschreibweise: \begin{equation*} \begin{pmatrix} a_{11}&a_{12}\\ a_{21}&a_{22} \end{pmatrix} \begin{pmatrix}x_1 \\ x_2\end{pmatrix} = \begin{pmatrix}b_1 \\ b_2\end{pmatrix} \end{equation*} Mit Hilfe der Cramerschen Regel erhält man folgende Werte für $x_1, x_2$ als Lösung dieses Gleichungssystems:

\begin{equation*} \begin{matrix} x_1 &= &{\begin{vmatrix}b_1 &a_{12}\cr b_2 &a_{22}\end{vmatrix}\over \begin{vmatrix}a_{11} &a_{12}\cr a_{21} &a_{22}\end{vmatrix}} \cr \cr\cr x_2 &= &{\left\vert\begin{matrix}a_{11} &b_1\cr a_{21} &b_2\end{matrix}\right\vert\over \left\vert\begin{matrix}a_{11} &a_{12}\cr a_{21} &a_{22}\end{matrix}\right\vert} \end{matrix}\end{equation*} Somit ergibt sich im Fall d eine innere Lösung, wobei das Maximum im Schnittpunkt der beiden zu den Nebenbedingungen gehörenden Beschränkungsgeraden liegt.

Zusammenfassung
Insgesamt ergeben fünf der 16 Möglichkeiten zulässige Lösungen, nämlich: Fall a1), Fall b2), Fall c, Fall d und Fall e.