Nonlinear Opt.: Basic concepts 2: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
Zeile 31: | Zeile 31: | ||
<math> g_i (x) \le 0 for i = 1,...,m | <math> g_i (x) \le 0 for i = 1,...,m | ||
x_j \le 0 for j = 1,...,n<\math> | x_j \le 0 for j = 1,...,n<\math> | ||
− | |||
Version vom 22. Juni 2013, 17:21 Uhr
In a non-linear problem there is either a non-linear objective function and no restrictions or a non-linear objective function and linear/non-linear restrictions or a linear objective function and non-linear restrictions.
Inhaltsverzeichnis
Theory
In contrast to the linear programming where we have the simplex algorithm to solve this there is not an universal algorithm for solving a non-linear problem.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): Restrictions: g_i(x) \begin{Bmatrix} \le \\ = \\ \ge \end{Bmatrix}~0 ~~~~~~(for~ i ~= ~1,...,m)
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x \in W_1 \times W_2 \times ,..., \times W_n , W_j \in \{ \mathbb R_+, \mathbb Z_+, \mathbb B \} ~~~~~~~~~~(for~j = 1,...,n)
In contrast to linear problems, non-linear optimization problems got a non-linear objective function and/or at least one non-linear restriction.
As distinct from integer and combinatorial problems, where integer or binary variables occur, we assume that only (non-negative) real variables occur in non-linear optimization.
The to be minimized objective function can be replaced with the to be maximized objective function and vice versa.
Furthermore, every \ge – restriction can be transformed into a \le – testriction by multiplication with -1. Beyond that, all equations can be replaced by two \le – restrictions.
To simplify the notation, functions g_i consist of the constants b_i, which are designated within the linear optimization:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f_i(x) \le b_i
is transformed into
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g_i(x) := f_i (x)-b_i \le 0
The following notation is assumed to be the notation of a non-linear optimization problem:
maximize F(x) under the restrictions Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): g_i (x) \le 0 for i = 1,...,m x_j \le 0 for j = 1,...,n<\math> == Examples == === Example 1=== <math>f(x) = x^2 - 8x
Step 1: The necessary condition for solving this problem is to derive the function and set this derivative equal to zero.
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f'(x) = 2x - 8 ~~=> ~2x - 8 = 0 ~<=>~ x = 4
Step 2: Now you have to check the sufficient condition; if you have a minimum, the second derivative of the function has to be greater than zero, for a maximum less than zero.
Examples for other algorithms
Example (non-linear objective function, linear restrictions)
Example (non-linear objective function, non-linear restrictions)
Example (linear objective function, non-linear restrictions)
Sources
Internet sources
Literature
- Prof. Dr. Oliver Wendt: Operations Research Script, Summer Term 2013
- Immanuel M. Bomze/W. Grossmann: Optimierung - Theorie und Algorithmen, ISBN:3-411-1509-1
- Kurt Marti/Detlef Gröger: Einführung in die lineare und nichtlineare Optimierung, ISBN:3-790-81297-8
- Wolfgang Domschke/Andreas Drexl: Einführung in Operations Research 6. Auflage ISBN:3-540-23431-4
- Hans Corsten/Hilde Corsten/Carsten Sartor: Operations Research ISBN:9-783800-632022