Wir betrachten folgendes Maximierungsproblem in drei Variablen,
mit zwei Nebenbedingungen in Form von Ungleichungen und mit
Nichtnegativitätsbedingungen:
\begin{equation}\label{eq:6}
\begin{split}
y = f(x_1, x_2, x_3) &\longrightarrow \max\\
g^1(x_1, x_2, x_3) &\le r_1\\
g^2(x_1, x_2, x_3) &\le r_2\\
x_1, x_2, x_3 &\ge 0
\end{split}
\end{equation}
Durch Einführung von Dummy-Variablen (Schlupfvariablen, englisch
slack $s_1$, $s_2$ können die Nebenbedingungen in
Gleichungen umgeformt werden.
\begin{equation}\label{eq:7}
\begin{split}
y = f(x_1, x_2, x_3) &\longrightarrow \max\\
g^1(x_1, x_2, x_3) + s_1 &= r_1\qquad\qquad (+)\\
g^2(x_1, x_2, x_3) + s_2 &= r_2\\
x_1, x_2, x_3, s_1, s_2 &\ge 0
\end{split}
\end{equation}
Berücksichtigt man die Nichtnegativitätsbedingungen vorläufig
nicht, so kann zu (+) folgende Lagrangebedingung
aufgestellt werden:
\begin{equation}\label{eq:8}
\begin{split}
L^* = L(x_1,x_2,x_3,s_1,s_2,\lambda_1,\lambda_2) = f(x_1, x_2,
x_3) &+
\lambda_1(r_1 - g^1(x_1,x_2,x_3)- s_1)\\
&+\lambda_2(r_2 - g^2(x_1,x_2,x_3) - s_2) \qquad(8)
\end{split}
\end{equation}
Daraus ergeben sich die Bedingungen erster Ordnung
\begin{equation}\label{eq:9}
{\partial L^*\over \partial x_1} = {\partial L^*\over
\partial x_2} = {\partial L^*\over \partial x_3} = {\partial
L^*\over \partial \lambda_1} = {\partial
L^*\over\partial\lambda_2} = {\partial L^*\over \partial s_1} =
{\partial L^*\over \partial s_1} = 0 \qquad (9)
\end{equation}
Wie in Abschnitt \ref{chap:ch1-sec:MitNebenbedingungenLagrange}
gesehen, ist die Lagrangefunktion die Übertragung einer Funktion
unter Nebenbedingungen in eine uneingeschränkte Funktion. Wir
können also auf die Funktion (8) bezüglich der
Nichtnegativitätsbedingungen die obigen Überlegungen, also
insbesondere das Ergebnis \eqref{eq:5} anwenden.
Wir bekommen
\begin{alignat}{3}
\label{eq:10a}{\partial L^*\over \partial x_j} &\le 0 \qquad x_j &\ge 0 \qquad x_j{\partial L^*\over \partial x_j} &= 0\qquad (8a) \\
\label{eq:10b}{\partial L^*\over \partial s_i} &\le 0 \qquad s_i &\ge 0 \qquad s_i{\partial L^*\over \partial s_i} &= 0\qquad (8b) \\
\label{eq:10c}{\partial L^*\over \partial\lambda_i} &= 0 \qquad (8c) &&
\end{alignat}
mit $i=1,2, \qquad j = 1,2,3.$
Als nächstes wollen wir die Schlupfvariable $s_i$ eliminieren.
Nach $s_i$ abgeleitet ergibt die Lagrangefunktion aus (8):
\begin{equation*}
\frac{\partial L^*}{ \partial s_i} = - \lambda_i
\end{equation*}
Somit kann (10b) als
\begin{equation}\label{eq:34} \lambda_i \ge 0,
\qquad s_i \ge 0, \qquad \lambda_is_i = 0\end{equation}
geschrieben werden.
Gemäß (10c) gilt $0 = {\partial L^*\over
\partial\lambda_i} = r_i - g^i(x_1,x_2,x_3)- s_i$ also $s_i = r_i
- g^i(x_1,x_2,x_3)$.
Damit kann \eqref{eq:34} umgeformt werden zu:
\begin{equation*}\lambda_i \ge 0,
\qquad r_i - g^i(x_1,x_2,x_3) \ge 0,\qquad \lambda_i\left( r_i -
g^i(x_1,x_2,x_3)\right) = 0\end{equation*}
Als Ergebnis bekommen wir für (10a), (10b)} und
(10c) folgendes System ohne Schlupfvariable
\begin{alignat}{4}
\label{eq:11a}{\partial L^*\over \partial x_j} = {\partial f\over
\partial x_j} - \left(\lambda_1 {\partial g^1\over \partial x_j} +
\lambda_2 {\partial g^2\over \partial x_j}\right) &\le 0, &\quad
x_j &\ge 0,&\quad x_j{\partial L^*\over \partial x_j} &= 0 \qquad (11a)\\
\label{eq:11b}r_i - g^i(x_1,x_2,x_3) &\ge 0, &\quad \lambda_i &\ge
0, &\quad\lambda_i\left( r_i - g^i(x_1,x_2,x_3)\right) &= 0 \qquad (11b)
\end{alignat}
\eqref{eq:11a} und \eqref{eq:11b} stellen die so genannten
Kuhn-Tucker-Bedingungen des Maximierungsproblems \eqref{eq:6} dar.
Die soeben abgeleiteten Bedingungen können auch direkt aus einer
Lagrangefunktion $L$ gewonnen werden, bei der die
Ungleichheitsbeziehungen und die Nichtnegativitätsbedingungen
nicht explizit geschrieben werden:
%
\begin{equation}
L = f(x_1,x_2,x_3) + \lambda_1 \left(r_1 - g^1(x_1,x_2,x_3)\right)
+ \lambda_2 \left(r_2 - g^2(x_1,x_2,x_3)\right) \qquad (12)
\end{equation}
Die Kuhn-Tucker-Bedingungen (des zu maximierenden Problems) erhält
man dann folgendermaßen:
- Die partiellen Ableitungen nach $x_j$ werden negativ (Null
eingeschlossen) gesetzt:
\begin{equation*}
{\partial L\over \partial x_j} \le 0
\end{equation*}
- Die partiellen Ableitungen nach $\lambda_i$ werden positiv
(einschließlich Null) gesetzt:
\begin{equation*}
{\partial L\over \partial \lambda_i} \ge 0
\end{equation*}
- Nichtnegativitätsbedingungen werden den Variablen $x_j$ und
$\lambda_i$ auferlegt.
- Die Bedingungen vom komplementären Schlupf werden eingeführt.
Damit bekommt man
\begin{alignat}{5}
\label{eq:12a}{\partial L\over \partial x_j} = {\partial f\over
\partial x_j} - \left(\lambda_1 {\partial g^1\over\partial x_j} + \lambda_2
{\partial g^2\over \partial x_j}\right) &\le 0, &\quad x_j &\ge 0,
&\quad x_j \cdot {\partial L\over \partial x_j} &= 0 \qquad (12a)\\
\label{eq:12b}{\partial L\over\partial \lambda_i} = r_i - g^i(x_1,
x_2, x_3)&\ge 0, &\quad \lambda_i &\ge 0, &\quad \lambda_i\cdot
{\partial L\over \partial \lambda_i} &= 0 \qquad (12a)
\end{alignat}
Dieses System entspricht der Bedingung in \eqref{eq:11a},
\eqref{eq:11b}.