\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:
Im Prinzip müssen nebenstehende Möglichkeiten
also insgesamt $2^4 = 16$ Möglichkeiten untersucht werden.
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.
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
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:
$\lambda _1=0, \lambda_2>0$
$\lambda _1>0, \lambda_2=0$
$\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:
$\lambda _1=0, \lambda_2>0$
$\lambda _1>0, \lambda_2=0$
$\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.