T 2 Annewandte Mathematik

ANGEWANDTE MATHEMATIK

1. ALLGIEMEINES

ZAMM 60, T '2 - T 9 (1970)

N-Stufen-Max-Min-Optimierung in konvexen kompakten Bereichen des R"

Von F. BEHRINaER

Einleitung Es soll uber einige Ergebnisse berichtet werden, die in der kiirzlich an der Technischen Hochschule Miinchen unter der Anleitung von Herrn Prof. Dr. J. HEINHOLD, Direktor des Instituts fiir Angewandte Mathematik, angefertigten Doktordissertation ,,BEBRIN~RJR : uber die Optimale Skalierung gewisser Differentialgleichungs- systeme mit Anwendung auf den Analogrechner und den Digital Differential Analyzer"j im folgenden [Diss.] genannt, zu finden sind. Auf Beweise wird hier nicht eingegangen. Auch sollen die Ergebnisse selbst teilweise nur angedeutet werden; nur soweit, wie notig, um fiir die erwiihnte Arbeit [Diss.] Interesse zu erwecken.

Problomherkunft Sei ~ ( 1 ) := ( ~ ~ ( 1 ) ~ . . . , ~ ~ ( 1 ) ) in [0, TI, mit T endlich reell, reellwertige Liisung des Differentialgleichungssysterna

i1(1) = PI(.)

= Pfl(4 9

wobei die P&) von 1 unnbhiingigu n-djmensionalo Polynome in (zl, . . . , zfl) seien. Bekannt seien die maximalen Betrage der Komponenten des LBsungsvektors :

mf: = max (zf(t)( . 1 C 10, TI

Zur Losung auf dem Analogrechner wird es im allgemeinen notig sein, den Ldsungsvektor durch Einfiihrung von Skalenfaktoren in einen vorgegebenen (durch die Referenzspannung bestimmten) Rechenbereich zu zwin- gen. Dies geschieht gewohnlich und am einfachsten durch den Ansate

mit den neuen Variablen yf(t), fiir die dann gilt yr(t): = af zr(4 0 <at < 00

Fiihrt man diese Skalierung in dem oben erwiihnten Differentialgleichungssystem durch und lBst links nach den y g ( t ) auf, so erhalt man rechts in den einzelnen Polynomgliedern als Koeffizienten Ausdriicke von der

Gestalt a' a, wobei a der urspriingliche Koeffizient des betreffenden Gliedes sein soll. a?. . .a? Aus technischen Griinden (besobriinkte Potentiometereinstellbarkeit usw.) ist es beim Analogrechner im

allgemeinen nicht miiglich, Koeffizienten beliebig groD oder beliebig klein zu machen. Interessiert man sich also fiir eiie optimale Skalierung, die die GrbBen mral moglichst groD werden liiDt (optimale Aussteuerung der Rechenelemente), so wird man verniinftigerweise Nebenbedingungen von der Gestalt

ansetzen . I n [Diss.] wird die fia.ge der Nebenbedingungen niiher er6rhrt. Dort wird luch das fiir die optimale

Skalierung anzusetzende Optimierungskriterium in Breite ciiskutiert und unter anderem der Vorschlag ver- teidjgt, das Skalierungsproblem in folgender Form zu stellen &

Bestimme ein 8k&nfaktor-n;!CupeJ (El , , . . , 8,) am dem geeignet zu wiihknden zuk9eigen Bereich S derart,

(q iil, . . . , m, in) =iexico-niie;x (1 - min (m, a*, . . . , m,, a,,), . . . , n - min (% al, . . . , mnn an)) . a s s ,

Hierbei bedeute lexioo-max dis lqdko&apb9he Maximum des in der zugehbrigen Klammer stehenden Vektors und 1 -min (q q, .*. . , m,4&,), 2-min (ml al, . . . , m, a,) usw. bedeute die kleinste, zweitkleinste usw. Komponente des Vektors (mj al, . . -. , m, a,).

* A

T 3 -~ Allgemeinea

$%cwrlo der N-Stufen-Max-Min-Optimierung Uof'flhrten Oberlegungen berechtigen zur Untersuchung des folgenden allgemeiner gehaltenen

1 1*t*u b I e m 1 (N - S t u f e n - Max - M i n - 0 p ti mi er u ng s pro b 1 em) $fir hgendwie normierte lineare Raum a.ller n-Tupel reeller Zahlen iiber dem Korper R der reellen

' I , mit Q nichtleer, konvex, abgeschlossen (in bezug auf die norminduzierte Topologie) und kom- beschriinkt naoh oben.

-t { ~(z)} eine Abbildung von Q i n R", erkliirt durch y(z) : = (y,(z), . . . , y&)) : = (1 -min (z,, , , , a - min (q, . . . , x,,)) fur alle z E Q. IruCu dss Optimierungsproblem :

IPI ai c U so, dap y(Z) = lexico-max y(z) ist. o f Q 1 W d gezeigt, daD dieses Problem eine Losung mit eindeutig bestimmtem Losungspunkt hat.

lrd in [Diss.] geeeigt, daD das Problem 1 einer Folge von n Einstufenproblemen iiquivalent ist, oT8h folgendermaDeii lautet :

b 1 u m 2 (Ein s t u f e n -Max - Min - 0 p t i mi e r u n g s pro b 1 em e r s t e r S t u f e) Untl 0 wie in Problem 1. Das Optimierungsproblem laute :

P a U eo, dap min (itl, . . . , Z,,) = max min (zl, . . . , 5,) ist . G f B

rd euniichst gezeigt, daD die Menge der Liisungspunkte des Problems 2 nichtleer (hierzu w i x eu sein), konvex, abgeschloseen und beschritnkt nach obsn ist. 11 Irbsungspunkte hat also dieselben Eigenschaften wie die Menge Q der zulllssigen Punkte u auliissiger Bereich einer zweiten Optimierungsstufe dienen, auf der das Maximum der

Omponenten der zullissigen Punkte gesucht wird. rC nur, die Gesamtheit der Menge der optimalen Punkte des Problems 2 zu charakterisieren,

r Mathematischen Optimierung geben sich jtt im allgemeinen mit der Auffindung eines dsungspunktes eufneden. kterisierung der gesamten Menge der Ldsungspunkte des Problems 2 gelingt mit Hilfe

[Djss.] wurde er bezeichnet als

Elhln v o m Hom'einsamen Index : rrri ]'rollern 2. Sei Q' die Menge der Losungspnkte und W der fisulzgswert. Dann gibt es tndee" i c { I , . . . , n} derart, da@ z( = W fiir aZk. (q, . . . zn) E Q'.

tlllW auuh ftir alle weiteren Stufen. nlrp Hntrtcr wird in [Diss.] bewiesen, daD die Menge Q' der optimalen Punkte des Problems 2

,,#@raalnrrrmo I t ~ d ~ x ' ' ist (genauer : irgendein ,,gemeinsamer Index", denn es

M&%JMln-Optimierung weiter bis eur n-ten Stufe durohzuziehen. kWaw Varfbhron zur Auffindung eines ,,gemeinsamen Index"

en darauf, nicht- "gemeinsame" otwendigerweise ,,gemeinsamer

umeinsamun Index" aufbauend wird denn in [Diss.] ein

1 angegeben fur den Fall,

Optimierung zuruckfiihren. Die Technik dieser ltheoretischen Problemen oder Problemen des

ung. Dee erwiihnte ALGOL-Programm lost mroblemen herkdmmlicher Art.

dessen Existenz.

tation, auf den sich der vorliegende Vortrag bezieht, wird

&en, Inst. f . Angewandte Mathematik 1*