Über eine gewisse klasse von optimierungsproblemen

This article was downloaded by: [University of Kiel]On: 26 October 2014, At: 03:08Publisher: Taylor & FrancisInforma Ltd Registered in England and Wales Registered Number: 1072954 Registered office: Mortimer House,37-41 Mortimer Street, London W1T 3JH, UK

Mathematische Operationsforschung und Statistik.Series OptimizationPublication details, including instructions for authors and subscription information:http://www.tandfonline.com/loi/gopt19

Über eine gewisse klasse von optimierungsproblemenReinhard Thron aa Akademie der Landwirtschaftswissenschaften der DDR , Institut für Landschaftsforschungund Naturschutz der , Halle/Saale, Nemverk, DDR - 402Published online: 27 Jun 2007.

To cite this article: Reinhard Thron (1980) Über eine gewisse klasse von optimierungsproblemen, MathematischeOperationsforschung und Statistik. Series Optimization, 11:1, 61-69, DOI: 10.1080/02331938008842632

To link to this article: http://dx.doi.org/10.1080/02331938008842632

PLEASE SCROLL DOWN FOR ARTICLE

Taylor & Francis makes every effort to ensure the accuracy of all the information (the “Content”) contained in thepublications on our platform. However, Taylor & Francis, our agents, and our licensors make no representationsor warranties whatsoever as to the accuracy, completeness, or suitability for any purpose of the Content. Anyopinions and views expressed in this publication are the opinions and views of the authors, and are not theviews of or endorsed by Taylor & Francis. The accuracy of the Content should not be relied upon and should beindependently verified with primary sources of information. Taylor and Francis shall not be liable for any losses,actions, claims, proceedings, demands, costs, expenses, damages, and other liabilities whatsoever or howsoevercaused arising directly or indirectly in connection with, in relation to or arising out of the use of the Content.

This article may be used for research, teaching, and private study purposes. Any substantial or systematicreproduction, redistribution, reselling, loan, sub-licensing, systematic supply, or distribution in anyform to anyone is expressly forbidden. Terms & Conditions of access and use can be found at http://www.tandfonline.com/page/terms-and-conditions

Math Operat lousrorsch. Statist., her O p t l ~ n i m t ~ o u , Yol. 11 (1960) SO I , 61-69

Uber eine gewisse Klasse von Optinlieritngsprohlemenl

Zusammenlussut~g: Durch Optii~lieiurlgzproblrnlr fulgrnder I'orri~ ldsuc.11 sicti Xufgabrn aus der Praxis oder innermathematische Fragestellungen behancleln: mas(e(k) - k f E ) , E ist Rlne Mengr geordneter Paare (Aw. KO) mlt h' Halbmodul, h', GK, e : E - [El. jEj ist die Aiange Lie1 ,&Y~ivdelis'kiasbrl~ L c ~ u ~ i i r i i e i u r ~ iil E Ciefi~~iertrzi Bqu;- valenzrelation. e ordnet jedem Element aus E die von ihm erzeagte Xquivalenzklasse aus [El zu. I n [Ej eslstiert elne gewisae Halhorclnungsr~lat~on. Mlt H~lfe rtcr hornolog~schen 4 lgeh,v v i r r l r = t w = n n t v ~ndirgr= Dptir~~~litritshrr(i~>gi~ny n n y q ~ h ~ n

In der trorliegenden k b e i t merden Opt~mierunp~sprol~lem~e hetrachtet, die durch Aufgaben aus der Praws oder durch innermathematische Fragestellungen der folgenden Art gekennzeichnet sind wie etma:

(1) I n einem Produktionsbetrieb lassen sich zur Herstellung eines Produktes verschiedenartige maschinelk Systeme S , T, . . . gleicher Produktionsleistung ver- venden. Ein Tei1s:ystem s eines maschinellen Systems S kann nun in den: Sinne

den Ehrinnr Te;l=-rrct~m~n des SvytgK~y S L l l I B ~ h ~ n g i g sein, daB PS ~ ~ i ~ l ~ Auf- ""6" ' ""J """"""

gabe im Produkiioi~sprozeB 01iiie &e Hi& derjenigen Teilsysteme erWlt, die e3 nicht seibst enthalt. (Soist es durc'naus mogiich, dai3 das Teiisystem s ein Zwisciie~i- produkt auch dann weiter produziert, obwohl bei anderen maschinellen Teilsyste- men von 8 eine Produktionsstorung vorliegt.) Die dem Produktionsbetrieb zur Verfiigung stehenden maschinellen Systeme S, T, . . . konnen sich hinsichtlich der Unabhangigkeit ihrer Teilsysteme unterscheiden. Das kann sich zum Beispiel in der jeweiligen Anzahl der zu den maschinellen Systemen S , T, . . . gehorenden unabhangigen Teilsysteme au13ern. Daruber hinaus konnen sich d e unabhangigen Teilsysteme durch ihre GroBe, das heiBt in der Anzahl der in ihnen enthaltenen Teilsysteme, unterscheiden.FurdenProduktionsproze13 sinddiejenigen maschinellen Systeme yon besonderer Bedeutung, die moglichst viele und groBe unabhangige

Auszug aus der Dissertation des Verfassers, Padagogische Hochschule ,.N. B. Krups- kaja" Halle 1977.

2 Institut fiir Landschaftsforschung und Naturschutz der Akademie der Landmirtschafts- missenscllaften der DDR, DDR - 402 Halle/Saale, Neun-erk 4.

Dow

nloa

ded

by [

Uni

vers

ity o

f K

iel]

at 0

3:08

26

Oct

ober

201

4

Teilsysteme enthalten. Denn diese maschinellen Systeme gewahrleisten am be- sten, daB auch bei der Storung eines ihrer Teilsysteme grol3e Teile des maschinei- len Systems ihre Aufgaben im ProduktionsprozeB weiter erfiillen kijnnen. Hieraus ergiht sich die Frage nach einer Nethode zur Bestirnnlung derjenipen maschinellen Spsienw, die hinsichtlich der Trnahhangigkeit der jeweiligen Teilsysteme die giin- stigsten Produktionscoraussetzungen bieten.

(4) Es sei V das System der kotmexen, abgeschlossenen I'ielecke mit endlieher Eckenzahl einer E u a ~ ~ i s c h e n Ebene.

(2-1) Die Vielecke aus V konnen s ~ c h hinsichtlich der Konl-esitat ~hre r Tell- mengen unterscheiden. Wie laljt slch V nacil dem Zutreffen der Eiqenschaft der Konvesitat auf die jeweils zu einem Vieleck gehorenden Teilmengen praordnen3, und tvelche Elemente aus V sind maximal beziidich dieser Praordnung?

(2.2) Die Rander der Vielecke aus V konnen sich hinsichtlich der StreckenfZjr- migkeit ihrer Teilmengen unterscheiden. (Em Punkt sei ebenfaiis als Strecke an- W Q P I I P I ~ f Wip 1aRt rich V nach r l ~ m Zntreff~n d ~ r Streckenformigkeit auf die je- C

weils zu dem Rand emes V~elecks gehorenden Teilmengen praordnert, unrl welche Ejemeiite G; $' ;inri ;r;GsimaX ?3czcg$oh 3eser Pr&2r+uz,v 2

6 '

Alle diese Fragest~llungen kcjnnen ah Optimierungsprol~leme der folgenden Ge- stalt aufgefafit werden : Sla./t bestimme die Xenge mau (e(k) : E E E}, d . h. die Xenge der maximalen Elemente au.s {e(k) : kc E}, wobei gilt: E ist eine JIenge geordneter Paare ( K , KO) , wobei K ein Eaibmodui, cias hei3t eine kommutative HaibgruPpe, isi and K o s K gilt. In E ist die folgende :iquivalenzrelatlon erklart : Zwei Elemente ( K , KO) und (L, Lo) aus E' sind genau dann aquivalent, wenn ein Isomorphismus von K auf L existiert, wobei KO auf Lo abgebildet wird. In der Xenge [El der ~~quivalenzklassen beziig- hch der eben hetirachteten AqnivaIenzrelatinn 1ai3t sich eine Halhordnungsrelation einfiihren. Die von den Pasren ( K , KG) und (L. Lo) erzeugten A&quivalenzklassen [K, K,,] z d [I;, L,,: stehec r , I?e!stix, das %!3t [-KT _TiG! -=[I+ &j, x v ~ n q ein Iso- morphismus von K auf L existiert, wobei KO in Lo abgebildet tvird, es jedoch kei- nen entsprechenden Isomorphismus von L auf K gibt. Es ist e : E -- [El diejenige Abbildung, die jedem Element aus E die Ton ihm erzeugte Bquivalenzklasse zu- ordnet.

Fur diese Klasse von Optimierungsproblemen wird eine notwendige Optimali- tatsbedingung angegeben, sofern die Elemente ( K , KO) aus E einer zusatzlichen Bedmgung, der sogenannten A-Bedmgung, geniigen.

Formulierung der Fragestellungen als Optimierungsprobleme :

Zu (I): Es seien S , T, . . . weiterhin die betrachteten maschinellen Systeme, K, L , . . . die Mengen der jeweiligen Teilsysteme und KO, Lo, . . . die Mengen der unabhangigen Teilsysteme von S, T, . . .

3 Eine PrBordnung ist reflexiv und transitiv.

Dow

nloa

ded

by [

Uni

vers

ity o

f K

iel]

at 0

3:08

26

Oct

ober

201

4

Dabei sirid K , L, . . . Halbmoduln beziiglich derjenigen Operation, &e jeclem Paar von Teilsystemen das aus den beiden Teilsystemen bestehende Teilsystem zuord- net. Der JIenge (8, T, . . .) el~t~spricht somit eine Menge E von Paaren (R, KO) , (L , Lo), . . . Weil nun ciie Unahhangigkeit (ley Teilsysterne \-on S , T , . . . durch die jeweils zugehorigen Mengen h',, LC,, . . . gegehen wird, ist es naheliegend, eine Klassifizierung der Jlenge (S, T, . . .) hinsichtiich der 1;nabhgngigkeit der ent,- ~~rechen3e1-1 Teilspsteine iiiittels der Jleiige E wie f d g t diirclizufiihreii: Der &ui- vaienz zweier Eiemente (I<, I<,,) und j i , Lo) auu 1-7 eritspricili die gieiche U n a b hangigkeit der Teils~st~eme der zugehdrigen maschinellen Systeme S uncl T.

Die Halbordnung in [El definiert eine Praordnung in (8, T, . . .) nach der Un- abhangigkeit der jeweils zugehorigen Teilsysteme vnn 8, T , . . .

Zur Bea,nttvortung der Fragestellung ist das Optimierunqsproblem P, der Be- i.tlmmunv 0 d~ ---- Yenge ma,\. ( e ( k ) : k r E ) ~ 1 1 liisen.

Zrr (2.1): E s seien u, v, . . . die betrachtetcn Vielecke, .K(uj, K i v ) , . . . &e je~bxiljgeii F u L e ~ ~ m i ~ w g a ~ ~ K O ( z ~ ) Kg(27). . . . die JIenge der konl-even Teilmengen von u , a, . . . Dahei sinci

- K(u) , l i jv) , . . . Halhmoduln heziigiich der Jlengenverelnignng ais Operat~on. Uer 31enge Tf entspric!~t nun eine Menge E ron Paaren ( K ( u ) , JCI,(zi.)), (K (v ) , Ki,(v)) , . . . Eine Klassifizierung Ton V llinsici~tlich der Konvesitat cler Teilmengen cler Viel- ecke aus V tvird mittels der Menge E wie folgt durcl~gefuhrt :

Der AquivaIenz zweier Paare (K(u) , K"(ZL)) , ( K ( z ' ) , K o ( v ) ) entspricht clas gleiche Zutreffen der Konvesitat auf die Teiimengen der Vieiecke ZL und 2;.

Die Halbordnung in [El definjert eine Praorclnung in V nach dem Zutreffen der Konvexitat auf ciie jeweils zu einem Vieleck gehorenden Teilmengen.

Also ist die Fragestellung anf clas Optimierungsprol~lem cler Eestimmung der Xenge mnlv ( e (k ) : k E 3: zuriickgefiihrt.

Zu (5.9): E s seien 12. F.. . . die Rander cler hetrachteten Vielecke zc, u. . . . , K G ) . . . die jeweiligen Potenzmengen der Rander, I ( I , ) . . . die Mengen streckenforiniger Teilmengen von ii, C, . . . Dabei sind Ii(ii.), K(,?), : . . Halbmoduln beziiglich der Mengenvereinigung als Operation. Der Xenge V entspricht wiederum eine Menge E von Paaren (K(i i ) , li,(fi)), ( K ( o ) , Ro(E)), . . . Eine Klassifizierung von V ilinsichtlich der Strecken- formigkeit der Teilmengen der Rander der Vielecke aus V mird mittels der Menge E wie folgt durchgefiihrt :

Der &pivalenz zweier Paare ( K ( G ) , Ko(ii)) , (K(B), K,,(B) ) entspricht das gleiche Zutreffen der St.reckenformigkeit auf &e Teilmengen der Rander der Cielecke ?L

und v. Die Halbordnung in [El definiert eine Praordnung in V nach dem Zutreffen der Streckenformigkeit auf die jeweils zu einem Rand eines Vielecks gehorenden Teilmengen. Durch das Optimierungsproblem P,., der Bestimmung der Menge m a s { e ( k ) : kc E) wird somit die Frage beantwortet,. Bei der Herleitung der not-

Dow

nloa

ded

by [

Uni

vers

ity o

f K

iel]

at 0

3:08

26

Oct

ober

201

4

wendigen 6ptimalit%tsbedingung fiir dejenigen Optimierungsprobleme, bei denen die Elemente aus E der A-Bedingung geniigen, wird wie folgt vorgegangen: Zu- nachst werden die (K, KO) aus E mit Mitteln der homoiogischen Algebra (vgl. [I], [4]) beschrieben :

Jedem Paar ( K , wird eine Folge yon gewissen Moduln, Homologie~nodulr~ genannt, zugeordnet. An Hand von Beispieieri wird gezeigt, daij versehiedenen Paaren nicht noiwendig oerschiedene Polgen von Homologicrnnduln entsprechen . Eiieraus foigt, daa im aligerneiiieii miiteis der H o ~ i o g e ~ o d n n m iiot~ve-elidige Bedingungen - - dafiir angegeben - - werden kbnnen, daB einem Element aus E eine ge- wisse Eigenschaft zukommt, also auch, daI3 ein Paar optimales Element a m E kt,. Ein Zusammenhang zwischen der Beschreibung der Elemente a m IZ und der Ah- bildung e : E .--[El ist dadurch gegeben, daI3 zu aquivalenten Paaren solche Folgen

r - - - " L ~ gehBren, hei denen d ie entsnrechenden Homoloc~iemoduln isomorph qind Stehen jedoch &e von den Paaren erzeugt,en Aquivalenzklassen in Relation

zueinander, so existieren gewisse hornorr~orpiie Abbildungen vuil deli Homologie- moduln der einen Folge in die entsprechenden Homologiemoduln der anderen Folge. Hieraus ergibt sich eine notwendige Optimalitatsbedingung fur das Opti- . . m i e r u n g s ~ r ~ b l e m ~ filnrcichende ~ ~ ~ t i m , z i i t ~ t s i ~ c t c i i n g ~ ~ n g e n foigen aus o n q p

Grunden im allgemeinen nicht. Zur Uberprufung der notwendigen 0ptimalit~;ts- bedingung 1a13t sich eine direkte Zerlegung fur die der Beschreibung der Paare ( K , KO) dienenden Homologiemoduln heranziehen, die gewisse Informationen uber die Eigenschaften der betrachteten Paare iiefert. ljariiber hinaus existieren Ver- schwindungssBtzp fijr direkt,e Snmmanden. Auf die direkte Zerlegung und die Verschwindungss&tze wird in der vorliegenden Arbeit nicht eingegangen. (Siehe hierzn [ 5 ] . )

AbschlieBend sei bemerkt, dal3 die Herleitung der notwendigen Optimalitats- bedingung mit Mitteln der homologischen Algebra ein dem Charakter der betrach- teten Optimierungsprobleme angepaWtes Vorgehen kt,.

1. Die A-Bediagung

I n diesem Abschnitt werden solche Oprimierungsprobleme betrachtet, bei denen die Elemente aus E einer sogenannten A-Bedingung geniigen.

Zunachst wird der Begriff des Hauptideab eingefuhrt : Es sei K ein Halbmodul. Fur jedes x aus K ist x: - . =(x+ y : ~ E K ) das durch x erzeugte Hauptideal bezuglich K.

Dann lautet die A-Bedingung fur (K, KO) aus E wie folgt: Zu jedem z aus K existiert ein xo aus K mit xo&x_. Fur alle x aus K und alle xo aus KO mit xogx existiert - - ein xi aus KO mit zosxhcz und ,

- - {g: X & ~ S ~ _ , z ~ K ~ } = ( x ~ } . -

Zu jedem (K, KO) aus E, das der A-Bedingung geniigt, gibt es eine Menge S

Dow

nloa

ded

by [

Uni

vers

ity o

f K

iel]

at 0

3:08

26

Oct

ober

201

4

aller Operatoren s auf I< in Ii,,, fiir &e giit : Piir ulle z aus I< sind d,ie Beziehwzgen s ( x ) G z vnd {;_ : s ( s ) G z G z , zi I<,> = ( s (x ) ] crfiillt. - - -

ES hestehell enge Zusarnmenliange zwisetien den Eigenschaft,en yon Hiillen- operatoren auf einer halbgeordneten Wenge und den Operatoren aus X jvgl. [3]),

. . Der fo]geiide SZtz (aielle [3j) zeigt, dl;. L~yu~~a~enzk~as : ; t i l~a~~3C;rdi ;k i~lg

in [Ej d I irch Operatorenmengen beschreiben 1,513t. Hierauf basiert wesent,lich die notwendig Ci:,tima!it5-the&ngung fiir Optimierungsprol-)leme mit A-Reclingi~ng.

Satz 1: Es seien (I<, K,,) zcnd (L, L,,) nus E. Weiter sei fur diese Elernexte nus E die A- Bedinpig erfullt. 2 5 7 ~ ( K , K,,) gehorc d i e Operutore?z:r,enge 8, zcnd zzc ( L , L,,) qehore die Oper~to+mn~e~ye T Dnrv qi7f .

Bus [I<, K,] -=EL, L,,] folgt die Existem eincs Isornorphissnus f con K auf L, so da,O es firr ~-l?!c .?: F̂.I qtnd n7le _c cyorc pin f awe T n) i f f ( c f r \ ) s f ( f ( r ) ) giht

-- Aus [ I i , KO] = [L L,] folgt die Bzisfenz eines I somorph i sm~~ f vonli auf L, so dap

es fur nlle a a m I< 11vd alle s c12cs S ezn t mcs T ?nit f ( s ( x ) ) = t ( J ( x ) ) gibt. - -

Zur A-Bedingunp - . bei den Problcmen PI, P,,l, Zu P,: Fur die ti<, Koj aus 15 ist die A-3edingung erfiiiit. Dies 'uedeuiet, daB zt i

jedem maschinellen System z ein kleinstes unab1Gngiges ~nascliinelles System x, existiert, worin x enthalten ist.

Zu P2,1: Fiir die ( l i ( z c ) , Ii,,(zc)) aus E ist die A-Bedingung ebenfalls erfullt. Dies bedeutet hier, da13 zu jeder Teilmenge xszc eine kleinste Bonvexe Menge x,, &e

TY.... konvexe nutle von x , existiert mit x s x , ~ z c . Zu P2,?: Fur ( K ( u ) , Ko(C)) aus E ist die A-Bedingung nicht erfiillt. Denn ist u

ein Vieleck und x die Menge seiner Ecken, so gibt es keine Strecke xo mit x s x o . Um jedoch auch fiir das Optimierungsproblem P,~2 die notwendige Optimalitgts- bedingung iiberpriifen zu konnen, wird das Optimierungsproblem Pz, der Be- t i m m i ~ n g der Menge max {e(k) : k c E*) betrachtet. Hierzu sei

R ( u ) : = A(.iZ) U ( Z L ) ist ebenfalls ein Halbmodul beziiglich der Mengenvereinigung, und es gilt Ko(a) U {u) = : & ( u ) s x ( u ) . Weiter erfullt jedes (R(u), .&(u)) aus E* die A-Eedingung. Denn zu jeder Menge x mit x S fi oder x = u existiert eine kleinste Strecke x,,SG mit x s x 0 , oder es ist x s x , , mit xo=u. Die zu einem ( I f ( u ) , Ifo(.))

gehorende Operatorenmenge S enthalt genau einen Operator ,s, der jedem x aus X ( u ) die konvexe HuIle s(x) von x zuordnet, falls diese in R,(u) enthalten ist. An- derenfalls ist s(x) =zc.

E s 1a13t sich zeigen, dai3 eine eineindeutige Aljbildung von max ( e ( k ) : kc E ) auf max { e ( k ) : kc E*) existiert. Also wird durch die notwendige Optimalitatsbedin- gung fur das Problem Pz, auch eine notwendige Optimalitatsbedingung fur das Problem P,., gegeben.

5 Optimization, Val. 11, Ro. 1

Dow

nloa

ded

by [

Uni

vers

ity o

f K

iel]

at 0

3:08

26

Oct

ober

201

4

2. Eine notwendiqe Optimalitatsbedingung fiir Optimierun~sprobleme mit A-Bedingung

Nunmehr wird fur Optimierun,vsprobleme - mit -4-Kedngung eine notmendipe Optimalitatsbe&npi~g hergeleitet. Dies geschieht mit Hilfsmitteln aus der homo- logischen Algebra. Hierzu ist es zunachst notwendig, einige grundlegende Defi- nitionen (vgl. [ I ] , [4]) anzugehen, auf die sich die welteren Betrachtungen be- ziehel:.

Znnachst werden Kettenkonzple.~.~ eingeflihrt : Ein Kettenkomplez C ist eine Folge

($7, 1 d l do ~ " C q + , ' P , - + P A +cz -0

von Xoduln C, und Homomorphismen d, rnit d,d,+, = 0.

Von einem Kettenkomplex ausgehend werden Zyklen und Rdnder definiert : Es - . fl -: - Trn4.+-%l----l---

t.lll I~cu~c;~,~xullLplc.~ Fdr jedc natarlicke Zah! ,; I;?cLDt der S a x des Ffsxrt

morphismus d, : C,-C,-, der JIodul Z, der q-dimensionab;~ Zyklen von C und cias Biici des Homomorpilismus Z,,, : i',,, -C, der Modui E, der q-6~tnenswnai:en. Riinder yon C.

Wegen d,d,+, = 0 gilt B,SZ,. Somit esistiert der Faktormodul Z,/B,. Fur jede naturliche Zahl p heil3t der Faktormodul H,(C) : =Z,/B, der q-dimensionale Ho?~aologiemodul von C. --

N U ~ werden spezieiie Kettenkompiexe bemachtet, mit deren Hilfe eine not- wendige Optimalitatsbedingung fur Optimierungsprohleme mit A-Bedingung for- muliert wird. Zunachst gehort zu jeder Menge X und jeder naturlichen Zahi q ein Modul A,(X), der wie folgt charakterisiert ist (vgl. [I]): A,(X) wird von den for?nalen Produkten q,z, . . . x, mit (q,, . . . , z,)&X erzeugt, zcobei die riefinierende Gleichuq - ,." A.

u g . . . ."&ALI1 . . . Z,+,",, . . . 2,s,l"L . . . z,=O fk- + b T * l + l *

besteht, falls xo . . . xi,,xi . . . x, aus x, . . . z,xi,, . . . x, dzmh Vertauschzmg vo?z xi mit xi,, hervorgeht .

Nun werden spezielle Untermoduln der A, (X) betrachtet. Hierzu sei ( K , K O ) ein die A-Bedingung erfiillendes Element aus E. S sei die zu ( K , KO) gehorende Ope- ratorenrnenge. Weiter sei X eine Teilmenge von K . Dann existiert fur jede na- tiirliche Zahl q ein Untermodul D,(X) von A , ( S ) , der wie folgt definiert ist: Es i.st D o ( X ) = Ao(X) .

Par jede naturliche Zahl q mit 1 ~p wird D,(X) ?ion genau denjenigen Produkten xo . . . x, aus A q ( X ) erzeugt, fur die gilt: Es ist xo . . . Zi . . . x,ED,-,(X) fur alle nutarlichen Zahlen i mit 0 s i ~ q , falls xo . . . Z i . . . x, = x o . . . xi-,xi+, . . . x, gilt und es gibt eine naturliche Zahl i rnit 0 s i s q, so dab ein s aus S existiert mit

s ( x ~ + . . .+2i+. . .+zq) e t (xo+. . .+xi+. . .+x,)

fur alle t am S.

Dow

nloa

ded

by [

Uni

vers

ity o

f K

iel]

at 0

3:08

26

Oct

ober

201

4

Wegen D,(X)gB,(X) esistiert der Faktormodul ,4,(X),'D,(X), der ?nit C,(X) hezeichnet wird. Bei jeder R.estklasse 4 aus C,(X) sei im folgenden st,ets u ein Repriisentant aus A , ( X ) . Es gibt einen Kettenkomplex C ( 9 ) mit Moduln C,(X) ~ n d mit Homomorphismen d, : C,(X) -C,-,(-Y), die folgende Eigenschaft hahen (vg!. [I!):

Fiir jede nntii~liche Zahl g and Bedes xi, . . . x, aus C , ( X ) gilt dy(xO . . . z*) -

Satz 2: Gegeben sex ezn ~piinzierz~t~ysproble.r~b, bei dew, uik Elen~er~ie aeis E der A- Bed,ingz~ng geniigen.

1st nun ( L , L,,) ein optimales Element aus B, so folgt, (la@ [L, L,,] nzit einem belie- bigcrr, [I<, ATo] a , i c ~ e iE j .iiii.ue,i=y&=hCar is; diiP &?; deriirt-~ei. jsni~-a7p~i;iiiiij j van K m?lf L esi,&er.t, dab jede Tehenge S von K e-ine Teilmenge Y von L und einen Non~,omorphisnz~~s f: : a,( C(X)) - H,(C( Y ) ) fur jede natiirlich Zahl p induziert,

.wobei far jede Restklasse z,,. . . x,+ B , (X ) aus W,(C(Y)) die 13ezzt.hung f,!(xo. . . s,+

+ f?,fs)) . . . j ( rv ) f Bq( Y ! 2i.l:; ~ c & i ByjX) bzgc. Re( F) der Unf;~r?n,od7d

der Rasrzder von C,,S) bzw. C,(Y) ist.

3. ZUP Losung der Probieme P,,, und E&

Zu P,., : Zur Los~ung des Optimierungsproblems P,., wird zunachst gezeigt, daG fi.ir alle ( K ( u ) , I<&)) und ( hT (v )? Ko(v)) aus E die ~quivalenzklassen [K(u) , K&u)] und [ K ( v ) , I<O(v)] unvergleiuhl~ar aind: Aidernfalls gibt es zwei Klassen [K(u ) , K,(u)] und [K(v) , K,(v)j mit jK(zc), K , (u~] c [ K ( v j , Ko(v)]. Somit gibt es einen isomor~kismus j tcjn Kjibj arif z'i<.iij iiiii f jRO( .~ j j 5 lTiOi~).

Durch f werden nun aber alle nichtkonveuen Eiemente aus K(u) auf nichtkon- vexe Elemente aus K(v) abgebildet. Denn ein nichtkonvexes Element z aus K ( u ) ist dadurch charakterisiert, daG es ein konveves Element z aus K(u) gibt mit

Z = Z ~ U Z ~ , ~ , n ~ ~ + ' o , z , n x + o , ~ ? n x + o , ~ , n z , n x = o ,

wobei z , und z2 konvexe Teilmengen von z sind. Nach Anwendung von f folgt hieraus

f ( z ) = f ( z i ) u f ( z J , f ( z J n f ( z r ) * @ , f ( z l ) n F o , f ( z 2 ) n ip) +O , ~ ( 2 , ) n j ( z , ) n f ( ~ ) = o

wegen der Operationstreue von f . Wegen z l , z2 , z E KO(u) gilt f ( z , ) , f ( z 2 ) , f ( 5 ) E KO(v). Mithin ist f(x) nichtkonvex, und hieraus folgt fiir den Isomorphismus f die Be-

ziehung f(Ko(u))=KO(v) im Widerspruch zu [K(u ) , K,(u)] -=[K(v), K,(v)]. Also sind die ~quivalenzklassen [K(u ) , K,(u)] und [K(v) , Ko(v)] unvergleichbar.

Somit gilt max { e ( k ) : k c E ) = E, und die notwendige Optimalitatsbedingung

Dow

nloa

ded

by [

Uni

vers

ity o

f K

iel]

at 0

3:08

26

Oct

ober

201

4

Satz 2 ist erfullt. Diese Beclingung besagt hier, daW es zu zwei t'ielecken ZL . z: m ~ t verschiedener Eckenzahl keine eineindeutige Abbildung von z~ auf v g ~ b t , bei der die konvexen Teilmengen von Z L auf die Ironr-exen Teilmengen ron v abgebildet tverdeil.

Zu Pz,: Zur Losung dieses Ciptimierungsprobiems sei bemerkt, cia6 fiir aiie (R(u), RO(~b)) und ( X ( u ) , xo(a)) aus E* genau darm [ ~ ( z L ) , Ri,(u)] -=[R(v), JTo(u)] gilt, ijiielr?, die Eckertzahl van v ue ine r 81s &i: E&enz&! Ton ~6 ;st.

Fiir das Optimierungsproblem ergibt sich d a m die Lijsung max { e ( k ) : kc E*) = = ( [ R ( u ) , R,(u)]), wobei Z L ein beliebiges Dreieck nus V ist, Es gilt namlich, da8 al!e Aquivalenzklassen, die zu Dreiecken gehdren, gleich sind. Fur die Menge Eo der optimalen EIemente gilt somit Eo= [R(u), Ro(u)] .

Nun wird die notwendige Optimalitatsbeding~mg uberpruft. Zur Definition einer Teilmenge X von R(u) betrachte man das zugehiirige Vieieck zc rnit dell Eckpur~k- ten Pljtt,j, P2( t~j , . . . , LDn(zij xiid den Seiten PI(%) P,(u), P:(u) P>j~i), . . . . P,&) P,,(u) 2 P,(u) Pl(zc) . Die Menge Y bestehe tlus abzahlbar unendlich rielen Elementen zi am R(zt), wobei -. 1. de Zi I,aa1~We;6e versetieden seien. Dabe; sei jedes ti eii-xe Tei!mei-,ge -v-c;n =, i;ia

genau einen inneren Punkt einer Seite von ZG enthalt. Dariiher llinaus sollen die folgenden Beziehungen gelten :

zn-22 zn- l , Z n , Z n + i > . . . C - Pl(u) P2(u) , z n - k S P k - l ( ~ ) P k ( 2 1 )

fur alle nat.iirlichen Zahlen k mit 3 ~k s n . Eezuglich der Elemente ( x ( u ) , Z,(u)) aus E* ergeben sich die folgeiiden Homo!ogiemodu!n:

fur alie natiirlichen - Zahien q mit 3 sq. n-2

,_.-L.- ,--A 1 , .__ Y,-,A,, " rl. A," ,,,,,,, -Labl l !L u l L . z n " = 3. L"UU<U Ub.3 AL"uuL .3 u-i & ~ L A U < , L L , , . . '

Zahlen. Der Exponent (% i2) ist ein MaB fur das Zutreffe? der ~treckenfhrmig-

keit auf die ~ e i l m e n ~ e n des kandes des n-Ecks PL. Mit wachsendem n verringert sich also .das Zutreffen quadratisch.

Neben dem Paar ( ~ ( Z L ) , Z,(U)) wird nun noch ein Paar ( R ( v ) , Zo(v)) betrachtet, wobei v ein m-Eck mit m e n ist. Dann gibt es einen Isomorphismus f von x ( u ) auf R(v) mit f ( l i i ' , (~))&R~(v) , da13 in ~bere ins t immung mit Satz 2 f i i r jede na- turliche Zahl q ein Epimorphismus f,* : EI,(C(X)) - H,(C( Y ) ) existiert, wobei

Y = f ( X ) ist. Fur die zugehorigen Exponenten gilt ("; 2, =-(m;2). 1st insbeson-

dere m=n, so gilt fur jede natiirliche Zahl q die Beziehung H,(C(X)) = H,(C(Y)).

Fur die Exponenten ist (n 2 2 , = (m % ') .

Dow

nloa

ded

by [

Uni

vers

ity o

f K

iel]

at 0

3:08

26

Oct

ober

201

4

i'brr rine grwisse Klasse Y O I ~ Opt i rn i~ ' r t ingsproble~~~e~l 69

Die notwendige Ol~tirnalit i tsl~e&ngung beschreibt a l n o i n Farm einer ganz-

zahligen, strengmonotonen Eunktion p ( n ) = ()'i2) drr Eekenznhl das Zu-

treffen der Streckenformigkeit suf &r Te!lmengen rler Rsnde, rles hetrachteten >:-&'a 31

[ I ] FR-mz, W. : Topologir 11. Rerli~i 1966. [2] KREKO, B.: Optimirnmg. Rrrlin 1974. [3] KUROS, A. G.: Vorlesungrn iiber allgelneina Algebra. Lripzig 1964. [4] =ADO, T. untl P. V. REICHELDERFER: Continuot~s trarlsfonnations in ~ttlalysis. Berlin,

C+bt+,ifigc.~~, _FT_ei,!e!herg 1955 [5] THROY, R.: i h e r 11as Zutreffen oiner Eigenschaft r i w r 3Ienge a11f (lie Eleinentr Jer

Pott.nzmenge. Erscht:i~lt in: Beitrage zur Xig&rrt unti Cro!netsit: ii ji080j.

Summary

Problems of practict. ant1 i n ~ i ~ r ~ n a t l ~ e l n ; ~ t i c a i quesrions can be rrgardwi as programifling probInns of the following forrn : nms {e(k): k EE), E is a set of pairs (K, with a commu- tative srmigroup I< a1111 Ii,,Ck'. [El is the set of ec~uivalence-classes rrferring to an eclui- valencc: n,l;ztion in E. e : E -[El. The image of k EE under e is an eynivalenct*-class producer1 by k. I n [El rsists :< par-tia! or!leririg. Egr nwa.ns of homological algrbra i~ nrcmsary con- ilition of optirnality \\-ill be stntr1.1.

Eeceive1.1 Octobrx 197s; revise11 April 1979.

Dow

nloa

ded

by [

Uni

vers

ity o

f K

iel]

at 0

3:08

26

Oct

ober

201

4