Zwei Lösungsmethoden für nichtkonvexe Programmierungsprobleme

Programmierungen sind ein sehr wirkungsvolles Instrument zur prak tischen Berechnung optimaler wirtschaftlicher Entscheidungen. 1m ein fachsten Fall der linearen Programmierung wird eine lipeare Zielfunk tion bei Geltung linearer Ungleichungen als Nebenbedingung maximiert oder minimiert. Sehr viele 6konomische Probleme lassen sich in diese Form bringen. Leider ist das nicht bei allen m6glich: sehr wichtige Probleme (z. E. viele Investitionsprobleme) fUhren auf nichtlineare Zielfunktionen und nichtlinear-e Ungleichungen als Nebenbedingungen. Es gibt in der Zwischenzeit eine ganze Reihe von Rechenverfahren, die ge statten, von einem beliebigen, zul~ssigen Anfangspunkt ausgehend ite rativ ein lokales Extremum zu berechnen. Leider liegen die Probleme h~ufig so, daE zahlreiche lokale Extrema existieren, w~hrend man natUr lich am globalen Extremum interessiert ist. Bisher hat es nur ein Ver fahren gegeben (das von Orden und Ritter), das fUr einen Spezialfall quadrati scher Formen als Zielfunktion und fUr lineare Ungleichungen als Nebenbedingungen das globale Extrumum in endlich vie len Rechenschritten zu erreichen gestattet. Alle Versuche zur Verallgemeinerung dieses Ver fahrens auf beliebige nichtlineare Zielfunktionen oder nichtlineare Ne benbedingungen sind bisher gescheitert. Hier setzt nun die Arbeit von Herrn Ueing ein. Er entwickelt zwei Ver fahren, die mit tragbarem Rechenaufwand von einem lokalen Extremum zum n~chsten mit einem h6heren Wert der Zielfunktion (bei einer Maximumauf gabe) Uberzugehen gestatten. Das erste Verfahren, dessen allgemeine Idee von mir schon vor einiger Zeit vorgeschlagen wurde. ist sehr allgemein: es verlangt fast keine Einschr~nkungen der Zielfunktionen und der Neben bedingungen.

Klappentext

Programmierungen sind ein sehr wirkungsvolles Instrument zur prak­ tischen Berechnung optimaler wirtschaftlicher Entscheidungen. 1m ein­ fachsten Fall der linearen Programmierung wird eine lipeare Zielfunk­ tion bei Geltung linearer Ungleichungen als Nebenbedingung maximiert oder minimiert. Sehr viele 6konomische Probleme lassen sich in diese Form bringen. Leider ist das nicht bei allen m6glich: sehr wichtige Probleme (z. E. viele Investitionsprobleme) fUhren auf nichtlineare Zielfunktionen und nichtlinear-e Ungleichungen als Nebenbedingungen. Es gibt in der Zwischenzeit eine ganze Reihe von Rechenverfahren, die ge­ statten, von einem beliebigen, zul~ssigen Anfangspunkt ausgehend ite­ rativ ein lokales Extremum zu berechnen. Leider liegen die Probleme h~ufig so, daE zahlreiche lokale Extrema existieren, w~hrend man natUr­ lich am globalen Extremum interessiert ist. Bisher hat es nur ein Ver­ fahren gegeben (das von Orden und Ritter), das fUr einen Spezialfall quadrati scher Formen als Zielfunktion und fUr lineare Ungleichungen als Nebenbedingungen das globale Extrumum in endlich vie len Rechenschritten zu erreichen gestattet. Alle Versuche zur Verallgemeinerung dieses Ver­ fahrens auf beliebige nichtlineare Zielfunktionen oder nichtlineare Ne­ benbedingungen sind bisher gescheitert. Hier setzt nun die Arbeit von Herrn Ueing ein. Er entwickelt zwei Ver­ fahren, die mit tragbarem Rechenaufwand von einem lokalen Extremum zum n~chsten mit einem h6heren Wert der Zielfunktion (bei einer Maximumauf­ gabe) Uberzugehen gestatten. Das erste Verfahren, dessen allgemeine Idee von mir schon vor einiger Zeit vorgeschlagen wurde. ist sehr allgemein: es verlangt fast keine Einschr~nkungen der Zielfunktionen und der Neben­ bedingungen.

Inhalt
Inhaltsangabe.- 1. Einleitung.- 2. Modifizierte Gradientenverfahren.- 2.1 Gedankliche Struktur der Programmierungsprobleme.- 2.2 CRST-Methode.- 2.3 Der lokale Charakter der Gradientenverfahren.- 3. Ein Operatorformalismus Zur Lösung Nichtkonvexer Programmierungsprobleme.- 3.1 Der Grundgedanke des Verfahrens.- 3.2 Erklärung der Hilfsschritte HP1 und HP2.- 3.3 Konstruktion und Anwendung des skalaren Operators H.- 3.4 Konstruktion und Anwendung des Vektoroperators HV.- 3.5 Darstellung des Ergebnisses anhand eines Niveauschemas.- 4. Ein Kombinatorisches Verfahren Zur Lösung Nichtkonvexer Programmierungsprobleme.- 4.1 Der Grundgedanke des Verfahrens.- 4.2 Konstruktion der Durchschnittsbereiche.- 4.3 Berechnung der Lösungsmenge H.- 4.4 Bestimmung des globalen Maximums.- 4.5 Lineare Restriktionen.- 5. Anwendung Des Verfahrens Mit Hilfe Einer Elektronischen Rechenmaschine.- 5.1 Der Aufbau des Rechenmaschinenprogramms.- 5.2 Beispiele.