- 106 -

ANHANG I: ZUR NUMERISCHEN LOSUNG DES VERALLGEMEINERTEN ZEITPLANUNGSPROBLEMS

Verzichtet man auf die Forderung (A7: 'i=" VieM), so erhalt man folgende Verallgemeinerung des in Abschn. 2 behandelten Planungsproblems: Gegeben sind zwei positive Vektoren

Parametern (d 1 , ... ,dm) und ('l"""m) sowie der durch letzteren erklarte Raum Z der zulassigen Anlieferplane

Z : = {zeIRm: O<z.<,., VieM} - + = 1 1

Mit der Gesamtbestandsfunktion

( I. 1)

lautet die Zielsetzung

( I. 2) i nf: zeZ

sup{s(t,z)} -. c(~) te IR+ -

von den

Besitzen die Elemente von ~ ein endliches (kleinstes) gemein­sames Vielfaches 1)

so ist

S(t+A.T,~) , \fte[O,T>, V\eIN, VzeZ

und es gilt

max{s(t,z)} tee -

VzeZ G .- !O,T>

Ferner ist mit

(T /T i) =: r i e IN , V i eM

zih := zi+(h-1)"i ' h=l,2, ... ,r i ' VieM

R := {(i,h)eMxIN: z'hee}, IRI = r = \~ 1 r. 1 ' , L1= 1

1) Es wird hier Rationalitat der 'i verlangt; aus praktischer Sicht ist jedoch ohnehin (scharfer) Ganzzahligkeit zu for­dern: ,eIN m.

- 107 -

auch

( I. 3) c (z) max{s(t,z)} tee -

max {s(zih'z)} (i ,h)eR -

"'zeZ

wobei zih den Zeitpunkt der h-ten Anlieferung einer Bestell­menge des Guts ieM in dem Intervall e bezeichnet und zi wie schon bisher h=1 impliziere.

Offenbar gilt nun s(zih,~)=s(zi,h+l'~) dann und nur dann, wenn die Summe aller in dem Intervall <zih,zi,h+lJ zugehenden Be­schaffungsmengen gerade gleich TiOEdj' dem Abgang wahrend die­ses Intervalls, ist. Das verallgemeinerte Problem zeichnet sich jedoch gerade dadurch aus, daB diese Bedingung i.a. nicht fUr alle 1) h=I,2, ... ,r i -l und fUr alle ieM erfUllt sein kann, da r 1#r 2# ... #r m oder zumi ndes t mi n{ r i} < max{ r i}' Demzufol ge existiert i.a. auch kein Plan zeZ mit der in Abschn. 2 bewie­senen Optimalitatsbedingung

(I. 4) S(z'h'z) = c(~) , V(i,h)eR 1 -

und da keine andere analytische Beziehung zwischen den s(z'h'z) 1 -

anstelle von (1.4) als hinreichende Bedingung fUr ein Optimum angegeben werden kann, mUssen die GroBen

( I. 5)

(I.3')

S(zih' ,~) := max {s(zih'~)} , VieM l<h<r. ==1

c(~) = l!1ax{s(zih' ,~)} 1eM

auf numerischem Wege, d.h. mit (1.1), berechnet und iterativ verbessert werden. Die hierfUr erforderlichen Definitionen und Beziehungen fUhren wir in Abschn. 1.1 ein; es folgt ein Nachweis zur Existenz optimaler Plane ~*eZ und die Entwicklung einer notwendigen Optimalitatsbedingung. In Abschn. I.3 geben wir schlieBlich eine untere Schranke fUr c(~l) an.

1) Man kann Vektoren ~ und ~ so konstruieren, daB (1.4) erfUllt ist. Die hierfUr zu machenden Voraussetzuhgen sind jedoch so speziell, daB darauf hier nicht eingegangen werden soll.

- 108 -

1.1 Definitionen

1m Hinblick auf die erforderliche iterative Verbesserung be­stimmter Ausgangslosungen ~eZ ist es wUnschenswert, neben der konstitutiven Form (1.1) auch eine mutative Beziehung zu haben, die im einzelnen erkennen laBt, welche Auswirkungen eine Ande­rung ~zk#O, keM, auf die Zeitreihe s(zih'~) haben wird. In Anlehnung an (D2.1) wird man zwar nur solche ~zk als zulassig

ansehen, die -zk~~zk<Tk erfUllen und somit

zkeIO,Tk> => zkHZk =: ZkelO,Tk>

gewahrleisten. Da aber zu jedem ~zke<-Tk,-zk> stets ein aqui­valentes ~zke<O'Tk-zk>' namlich ~zk:=-zk-~zk' angegeben werden kann, betrachten wir i~ weiteren jedes ~zke<-Tk'O>, keM, als zulassig und erklaren hierzu folgende Teilmengen von R:

(I.6a)

(I.6b)

(I.6c)

Rkh .- {(i ,1)eR: zkh~zil<zkh} Vhe{l, ... ,r k}

Rk := Rk1 + ... +R kr ' Rk := Rk1 +·· .+R kr k k

Damit ist RkUR k die Indexmenge aller von dem Obergang zkh~zkh' h=1,2, ... ,r k, "betroffenen" Anlieferzeitpunkte 1 ) zihee. Der Grund fUr die Unterscheidung zwischen Rkh und Rkh ergibt sich aus der Erlauterung folgender Differenzengleichungen, die -fUr~' := (zl, ... ,zk, ... ,zm) - alle durch ~zke<-Tk'O> hervor­gerufenen Anderungen der Zeitreihe s(z.h'z) erschopfend be-

l -schreiben:

(I.7a)

(I.7b)

(1. 7 c) 5 (z. h' z') 1 -

h = 1,2, ... ,r k

1) Zu beachten ist, daB immer (k,h)eR kh , also niemals Rkh=~'

was fUr Rkh nicht zutrifft.

- 109 -

Zur Erlauterung: Zunachst ist klar, daB mit fizke<-Tk'O> der Anteil von keM an s(t,~), Skt' fUr alle te{lz kh ,zkh>,h=I, ... ,r k} urn (fizkdk+xk)<x k VE zunimmt, fUr alle Ubrigen tee hingegen urn IfiZkldk VE fallt, vgl. Abb. 1.1; hieraus werden (I.7b,c) sofort verstandlich, wenn man berUcksichtigt, daB Rkh={(i,l)eR: zile

[zkh,zkh>}' Vhe 1, ... ,r k ' und daB (I.7c) fUr alle Zil¢{ Iz kh , zkh>,h=1,2, ... ,r k}, i#k, gilt.

o

, " , ,

" , "­ , ,

',I ~~ ______ ~~~L-______ ~~~ ___ t

Abbildung 1.1: Auswirkung von llzk<O auf Skt

FUr die Werte S(zkh'~') wird die aus Zkh€!zkh,zkh> resultierende Erhohung urn (fizkdk+x k) VE durch zkheRkh und den dadurch veran­laBten Abzug von xk in eine Minderung urn !llzk!d k VE verwandelt. Zugleich muB jedoch dem durch die Vorverlegung aller zkh urn !fizkl ZE urn ~zkl'l:dj VE verringerten GesamtabfluB Rechnung ge­tragen werden. Endlich sind in (I.7a) noch alle Sprungstellen

anderer Anteile Sit' ieM:i#k, Uber den Intervallen <zkh,zkh l zu berUcksichtigen, und nach Definition ist gerade Rkh={(i,l)eR:

zile<Zkh,zkhj}, h=I,2, ... ,r k·

Man denke sich eine Funktion f:R ... IN, die jedem Tupel (i,h)eR genau eine Zahl a(i ,h)e{1,2, ... ,r} umkehrbar eindeutig zuord­net. Bezeichnet man dann die durch die natUrliche Ordnung der Zahlen a(i ,h) erklarte Reihenfolge der Elemente (i ,h)eR als Ordnung von R, (R), und die Menge aller (R) mit {rPr}, so kann man in Anlehnung an (02.4) definieren:

- 110 -

(DI.I) Ein Plan zeZ heiBe schwach vertragZich mit (R), wenn

a(i,h) < a(j,l) => zih ~ Zjl ' V(i,h),(j,l)eR

Die Teilmenge aller mit festem (R)e{rPr} schwach ver­traglichen Plane sei mit Z(R) bezeichnet.

(DI.2) Ein Plan ~(R)ez(R) heiBe effizient bezugZich (R) oder (R)-effizient, wenn

~(~(R)) ~ ~(~) , V~eZ1R)

Mit (1.5), S. 107, und

( I. 8)

definieren wir ferner

(DI.3) Ein Plan zeZ heiBe vom Rang v, wenn die Bedingungen

(1.9) s(zih' ,~) = ~(~)

(1.10) Uih , = {(i,h')}

von genau v Elementen ieM erfUllt sind, v=O,I, ... ,m. Ein Plan vom Rang v=m heiBe BasisZosung.

Basislosungen besitzen also die (1.4) vergleichbare Eigenschaft

(1.4') S(z'h"Z) 1 -

1.2 Basislosungen

~(~) , VieM

Die folgenden AusfUhrungen sollen zeigen, daB zu jedem Planungs­problem mit T<oo stets eine nichtleere, endliche Menge von Basis­losungen existiert. Aus dem Beweis hierzu ergeben sich zugleich Aussagen Uber die endliche Konvergenz iterativer Verfahren zur Erzeugung von Basislosungen sowie eine notwendige Bedingung fUr die Optimal itat des Plans z~eZ mit ~(~f) ~c(~), VzeZ.

- 111 -

Urn die Darstellung zu vereinfachen, fUhren wir folgende Teil­mengen von Z zusatzlich ein:

ZB die Menge der Basislosungen ~eZ ZE die Menge der (R)-effizienten Plane ~eZ, Y(R)e{rPr}

SATZ 1.1

Zu jedem Planungsproblem mit T<oo existiert mindestens eine Basislosung: ZB # ~

Diese Behauptung folgt unmittelbar aus dem weitergehenden

HILFSSATZ 1.1.1

Sei ~eZ vom Rang v<m; dann existiert stets ein ~'eZ vom Rang (v+1) mit c(~') < c(~).

den wir durch Konstruktion beweisen: Die Existenz von Planen zeZ vom Rang v~l darf vorausgesetzt werden, da 1) T<oo ; fUr einen solchen Plan sei VcM die Teilmenge der ieM, deren Tupel (i ,h') den Bedingungen (1.9) und (1.10) genUgen, l~IVI=v<m, und keM: k~V, so daB entweder

oder

i(Zkh' ,~) < c(~) ,

jedenfalls aber fUr

die strenge Ungleichung

g(zkh'~) := max {g(zkh'~)} < c(~) l~h~rk

erfUllt sein muB, wobei fUr genUgend nahe bei Null gewahlte 6Z k<0 offenbar Rkh=U kh , Yhe{1,2, ... ,r k} und mit ~'=(zl" .. ,zk+6Zk' ... ,zm) auch

1) Man setze etwa Zl=O; dann gibt es bei T<oo immer ein £>0, so daB ein durch zi :=(i-1)"£, YieM, erklarter Plan z die Eigen­schaft c(~)=s(zm1'~) und Um1 ={(m,1)}, ~ v~l. besitzt.

- 112 -

Nun existiert zu jedem ieV immer ein hi e{1,2, ... ,r k} derart, daB zih,<zkh.<zih,+Tk' woraus mit s(zih' ,!)=c(!), YieV, folgt

1

=>

Also genUgt

(1.11)

g(Zkh'!) > c(!) - TkoIJ=l dj + Xk

g(Zkh'!) - c(!)

\~ 1 d. l.J= J

der Forderung -Tk<nzk<O fUr die GUltigkeit der Beziehungen (1.7), und man findet mit (1.7a)

(1.12a) S(Z~h't) = i(zkh,!)+nzkdk+xk-nzkI~=ldj-. E Xi (l,l)eR kh

S(Zkh,!)+6Z kdk+X k-(g(Zkh'!)-C(!))-. E Xi (l,l)eR kh

~ g(zkh'!) - g(zkh'!) + c(!) + 6z kdk

~ c(!) + 6z kdk < c(!) , h=1,2, ... ,r k

Weiter gilt mit (1.7b)

(I.12b) i(Zih,z1 = i(zih'!) + 6z kdk + xk

~ c(z) + 6z kdk < c(!) , V(i,h)eR~

denn: Nach Definition von (k,h) und nach Konstruktion {I.II) ist

g(Zkh'!) - Vo(Edj-d k) ~ c(!) - Vo(Edj-d k)

fUr alle ve[6z k,O> und alle he{I,2, ... ,r k}, und da

(i,h)eR~lcR~ ~> (zih-zkl) =: V'e[6Z k,O>

gilt zunachst fUr z+.- (zl, ... ,zkH', ... ,zm)

- 113 -

- + - +-s(zih'~ ) - s(zkl+IJ',~ ) < c(~) + v'.d k

Da aber bereits

- + -s(zih'~ ) = s(zih'~) + V'.d k + xk

gilt auch (I.12b). SchlieBlich hat man

g(zkh'~) - c (~) - xk => zih,-zkh. < < lIz k

1 I~=l dj

=> I i eV => (i,h')~Rk [ J

so daB mit (I.7c) auch

(I.12c) 5 ( z . h' ,z') 1 -

Mit (1.12) ist gesichert: Die durch (1.11) modifizierte Losung

~':=(zl, ... ,zk+llzk, ... ,zm) besitzt die Eigenschaft

(1.13)

Gilt nun fUr das mit (1.11) konstruierte lIz k auch Rkfi=~' so ist Rkfi = Ukfi und daher

(1.12a')

d.h. V:=V+k, und ~' besitzt einen Rang groBer/gleich (v+1). Falls Rkh ~ ~, gilt

(I.12a Ol )

so daB C (~')

< c (~) =>

=>

1st dann V=V, so kann man zu Zl wie oben zu zein lIZ j , jeM, bilden, mit dem die Losung abermals verbessert wird, vgl. (1.13), etc. Da s(t,~) nach Voraussetzung T<oo nur r<oo Sprungstellen

- 114 -

aufweist, mu6 eine endliehe Zahl von Wiederholungen dieses Vorgangs zu einem Bestellplan mit einem Rang gro6er/gleieh (v+1) fUhren, w.z.z.w.

Damit ist aueh Satz 1.1 bewiesen und gezeigt:

KOROLLAR 1.1.1

Zu jeder Losung ~eZ vom Rang v<m existiert eine bessere Basislosung ~'eZB:

~~ZB => 3~' eZ B: c(~') < c(~)

Hieraus leitet man weiter ab:

KOROLLAR 1.1.2

Falls eine optimale Losung ~·eZ existiert, ist diese stets aueh Basislosung, ~·ezB:

=>

Nun gilt trivial

H1LFSSATZ 1.2.1

Die Menge der (R)-effizienten Losungen ist endlieh: IZEI < 00

denn naeh Voraussetzung T<oo gilt r<oo, also aueh l{rPr}l<oo und somi t I ZE I <00.

HILFSSATZ 1.2.2

Jede Basislosung ist (R)-effizient: ZB ~ ZE

Beweis: Sei ~EZB; dann ist - vgl. (I.6)-die Existenz' eines lIZk~O, keM, mit RknRk ~ 0 und z':=(z1, ... ,Zk+llZk, ... ,zm) be­reits hinreiehende Bedingung fUr (R') ~ (R). Wegen der Gegen­laufigkeit von (I.7a) und (I.7e) ist die Existenz eines solehen lIz k jedoeh gerade notwendige Bedingung fUr c(~' )<c(~). Also

- 115 -

sind ct~') < cC~J und (R') = (R) fUr alle ~eZB widersprUchlich; mithin ist ~eZB auch (R)-effizient: ~eZB ~ ~eZE' w.z.z.w.

Aus diesen beiden Hilfssatzen folgt unmittelbar

SATZ 1.2

Die Menge der BasisHisungen ist endlich: IZBI < 00

und hieraus schlieBlich

KOROLLAR 1.2.1

T<oo ist hinreichende Bedingung fUr die Existenz einer optimalen Losung ~·ezB'

Ziel numerischer Losungsverfahren muB also die (wirtschaftliche) Erzeugung von Basislosungen sein. Damit wird sichergestellt, daB die bis zum Abbruch der Suche gefundene beste Losung zu­mindest potentiell optimal und nicht mehr trivial verbesserungs­fahig ist. Die wesentlichen Grundlagen fUr die Entwicklung solcher Verfahren sind in dem Beweis zu Hilfssatz 1.1.1 ent-ha lten.

Die Parallelen zwischen den Ergebnissen von Abschn. 2 und 1.2 sind offensichtlich; vgl. insbesondere (1.4) und (1.4') sowie die Aussagen von Satz 2.2 und Hilfssatz 1.2.2. Zu der Permu­tationsindifferenz des Satzes 2.3 existiert jedoch fUr das verallgemeinerte Problem keine Parallele. Das Gegenbeispiel in Tab. 1.1 zeigt, daB es nicht einmal moglich ist, die Aussage von Hilfssatz 1.2.2 auf (M)-Effizienz von ~eZB zu erweitern: Die Forderungen (M') = (M), c(~') < c(~), ~,~' eZB' sind nicht widersprUchlich, d.h. es konnen zu einer Permutation (M) durch­aus mehrere Basislosungen unterschiedlicher Qualitat existie­ren; andererseits scheint i.a. die weitaus Uberwiegende Mehr­zahl aller (R)-effizienten Losungen ~eZE nicht in ZB enthalten und somit bereits von vornherein suboptimal zu sein.

- 116 -

Tabelle 1. 1: ~,~' eIB: c(~')<c(~) 1\ (11' )=(M)

1 2 3 4 l: . 1.-

Ti 20 10 12 15

di 25 30 25 20 100

xi 500 300 300 300 1. 400

Dieses Problem besitzt u. a. die Basislosungen

z = (0,3,10,11) mit c(~) = 1. 060

z'= (0,6,7,9) mit c(~' ) = 1. 035

1.3 Abschatzung zu c(~*)

Da sich das verallgemeinerte Problem i .a. nur naherungsweise ("suboptimal") losen 1 aBt, interessieren t~aBstabe, an hand derer die Qualitat einer gegebenen Losung abgeschatzt werden kann. Einen Ausdruck reZativer Qualitat haben wir bereits mit dem Konzept der Basislosung eingefUhrt: Ein Plan ~eIB kann, ein­fach ausgedrUckt, "nicht ohne weiteres" verbessert werden. In Form einer Schranke soll nun auch ein (konservatives) MaB fUr die absoZute Qualitat einer Losung angegeben werden, d.h. wir interessieren uns fUr eine moglichst groBe Iahl Y mit

min{max{s(t,z)}} > Y zel tee -

bzw., cf. (1.1), mit

max {min n~-1 d.·(z·h- z .) modT.}} ~ L~-1 xJ' - Y zel (i,h)eR J- J 1 J J - J-

benotigen also eine Abschatzung zu (zih-Zj) mod Tj' Sei nun wieder T<oo, zel und i ,jeM. Dann gilt

(1.14)

denn mit

is t

=>

und mit

- 117 -

(Zj,T+I- Zi) modTi = Zj,T+l - zih

(zih-Zj) mOdTj + (Zj,T+l-zi) modT i = Tj

folgt (I.14).

Vereinfacht man mit der Definition 1)

( 1. 15) a ., : = mi n {( Z . h - Z .) mod T . } lJ l<h<r.l J J

= = 1

die Schreibweise, so ergibt sich aus (1.15) fUr den einfachsten Fa1l 2) (m=2)

(I.16 )

und aus

min {I~ . (i ,h)eR J=1

(I.14)

a12 ~ T2 - a21

a21 ~ Tl - a 12

so daB (1.16) ein Supremum vom Wert min{H I2 ,H 21 } besitzt:

I d1 H12 := d2"a 12 ,: d1"(Tl-a I2) => a12 = Tl"Cf1+Ci2 =>

(LI7a)

=>

1) Wegen (zih-zi) mod Ti = 0, \lhelN, ist aii=O, \lieM. 2) Wegen aii=O entfallen a.d.r.S. von (1.16) die Summanden d1"a 11

und d2"a 22 .

- 118 -

(Lllb)

In Matrizenschreibweise:

(Lllc)

Da mit (1.14) nur einzelne Terme, nicht aber deren Summen abge­schatzt werden konnen, ergibt sich bereits fUr m=3 eine wesent­lich veranderte Situation: Durch (1.15) ist fUr jedes Paar

i,jeM:ilj ein zih erklart, das zwar (zih-Zj) mOdTj Uber {l, ... ,r i } minimiert, nicht aber den Term 1)

(1.15)

den man mit (1.14) zu

( 1. 14 I )

abschKtzt. Da ein Kriterium fUr die "optimale" Wahl eines zihee

mit simultanem Bezug auf (Zih-Zk) modTk und (Zih-Zj) mOdTj fehlt bzw. nur durch - an dieser Stelle unzweckmaBige - Einbeziehung der "Gewichte" di , dj , dk geschaffen werden konnte, muB

(1.18) min {I~ 1 d,,(z'h- z ,) modT.} (i,h)eR J= J 1 J J

anders als in (1.16) durch ein System von m·(m-l) Ungleichungen abgeschatzt werden:

( 1. 16 I )

< min { dj,a ij + dk,a ijk

dj,a ikj + dk,a ik

1) FUr das weitere, vgl. u. (1.1gb), sei vereinbart: aij=aijj

- 119 -

Mit (1.14') liefern die reehten Seiten von (1.16') folgendes System:

d1 d2 d3

Hll 0 0 0

H12 0 a 12 T3-a 31 ( i = 1 )

H13 0 T2- a2l a 13

H21 a21 0 T3-a 32

(L17e') H22 0 0 0 ( i = 2 )

H23 T1- a 12 0 a23

H31 a31 T2- a 32 0

H32 Tl -a 13 a32 0 ( i =3 )

H33 0 0 0

Als allgemeine Abschatzung zu (1.18) bildet man also

(L19a) \fieM:

(L19b) < minn:~_l do.a ok o} keM J- J 1 J kFi

wobei dureh die reehten Seiten (I.19b) analog zu (I.17e') nunmehr allgemein m quadratische Teilmatrizen w~m), ;=1,2, ... ,m, erklart sind, die in ihrer Gesamtheit mit W(m) bezeiehnet seien.

Nun gilt aber (1.19) fUr aZZe Plane ~eZ, wahrend wir eine Zahl suehen, die urn einen mogliehst kleinen Betrag groBer ist als

(L19a') max{min{ min n~~-l dJo,(zih-zJo) mOdTJo}}} zeZ ; eM l<h<r ° J-

==1

- 120 -

also etwa ein Supremum zu

(1.1gb') min { min {L~-1 do'a ok o}} ieM keM:k#i J- J 1 J

Oa ganze Zeilen des aus wi m) , ... ,w~m) zusammengesetzten Glei­chungssystems W(m) ~ (1.1gb) nicht simultan abgeschatzt werden konnen, bedienen wir uns der verallgemeinerten paarweisen Ab­schatzung (Io17a,b), die mit

/I To -

1

die Form do, do

T i ,_l __ J • Y i • j eM: i # j di+d j

( 1.20)

haben und die Elemente der Matrix W(m) bilden, deren erste Teilmatrix wi m) folgendes Aussehen hat:

d1 d2 d3 d4

Hll 0 0 0 0

H12 0 T1'd 1 T3'd 1 T4'd 1

d1+d 2 d1+d 3 d1+d 4

H13 0 T2'd 1 T I,d 1 T4'd 1

d1+d 2 d1+d 3 d1+d 4

H14 0 T2,d I T3'd i T I,d 1

dl +d 2 d1+d 3 dl +d 4

HIm 0 T2'd 1 T3'd i T4'd 1

d1+d 2 dl +d 3 d1+d4

Mit (I. 20) ist W(m) Zeile fUr Zeile nicht kleiner als die einer beliebigen Losung abgeleitete l1atri x ~J(m); forma 1 :

dm

0

Tm'd 1

d1+dm

Tm'd 1

d1+d m

Tm'd 1

dl+d m

T I'd m

d1+d m

aus

- 121 -

~ Hik ' Vi,keM:i~k

Damit gilt aber auch

max{min{ min n:~-1 dJ,,{zih-zJ') mOdT J.}}} < zeZ ieM l<h<r. J-- ==,

<

und mit

max{min{ min {L~-1 d,,{z·h-z.) modT.}}} zeZ ieM l<h<r. J- J , J J - ==,

,m x. - min{max{s(t,z)}} L J'=1 J zeZ tee -

sow;e

d.· d. x. - T •• _' __ J

J J di+dj

d. x.' (1 _ -'-)

J d;+d j

d. x .• _J_ J di+d j

folgt schlieBlich:

SATZ 1.3

FUr die optimale Losung z*eZ des verallgemeinerten Problems mit T<oo gilt

(1. 21)

>

FUr das in Tab. 1.1 angegebene Zahlenbeispiel liefert (1.21) die Schranke Y=980, so daB man die Losung ~'=(O,6,7,9) mit c{~' )=1.035 als annahernd optimal bezeichnen darf.

- 122 -

AN HANG II: OPTIMIERUNG BEl SIMULTANEN KAPAZITXTS- UND BUDGETRESTRIKTIONEN - ZAHLENBEISPIEL

FUr ein Planungsproblem seien die Daten in Tab. 11.1 bekannt.

Tabelle 11. 1 : Zahlenbeispiel

di(VE) Di (VE) bi(GE) Bi (GE) C 1 i C2 i Pi(GE/VE)

1 50 5.000 300 30.000 500 0,20 6,00 2 200 20.000 100 10.000 300 0,15 0,50 3 100 10.000 250 25.000 400 0,10 2,50 4 150 15.000 50 5.000 200 0,30 0,33

500 50.000 700 70.000 1. 400 ( B 100 ZE )

Ohne BerUcksichtigung von Restriktionen findet man hierfUr

mit (L2);

mit (L3);

ID = 32.500 IB = 46.786 nit = 2,027 K(nit.U)= 5.675 ~r(nit) = 16.033 ~r(n*) = 23.081

* ~ = (2,45; 1,58; K.(~*) = 5.587 cF(~*) = 28.080

1,77; 1,94)

1m weiteren werden zunachst die Randwerte a1=Ib Idb und a2=bd IdI ermittelt (Abschn. 11.1) und anschlieBend optimale und Naherungs­losungen fUr verschiedene reprasentative Tupel (e'C)eIR~ nach (L2) und (L3) berechnet (Abschn. 11.2). Grundlage der AusfUhrun­gen sind die Definitionen und Ergebnisse von Abschn. 3.4.3.

Mit B=100, ID=32.500 und IB=46.786 sowie (2.10"), S. 35, kann

- 123 -

man bereits angeben

dI = ~(1) = 325 Ib = ~(1) = 467,86

Die fUr die Berechnung von db und bd, vgl. S. 68f, mal3geblichen Daten aus Tab. 11.1 sind in hierfUr geeigneter Form in Tab. 11.2 zusammengestellt.

Tabelle 11.2: Daten zur Berechnung von ( bd , db)

di Vi = d. Ir.d. 1 J.

bi IIi b;lr.b j

1 50 7170 300 30170

2 200 28170 100 10170

3 100 14170 250 25170

4 150 21170 50 5170

500 1 700 1

Von der Struktur v(~) -c mit

e ty.~!OI) ) eO (1) Ix!

verl angt man

(11.1) S(v.,v(~» = c(v(~» 1 -c -c ~(1) , 'dieM

(11.2) e(v(~» -c W(O'.Y.~~»

(11.3) e(v(~» c min {max{w(t,v(M»}}

(M)e{mPm} te~ -c

Es wurde bereits ausgefUhrt, vgl. S. 67f, daB diese Bedingungen widerspruchsfrei sind. (11.1) zeichnet genau m! bezUglich der Kapazitatsrestriktion optimale Strukturen aus; mit (11.2) wird diese Klasse auf jene (m-1)! Strukturen verringert, fUr die das Maximum der impZizierten Zeitreihe w(.) auf den Zeitpunkt t=O fallt; unter diesen gibt es (mindestens) eine Struktur mit minimalem implizierten Maximum, die in der durch (11.3) ausge­zeichneten Klasse enthalten ist. Bei der Berechnung von Ix! werden

- 124 -

die Eigenschaften (11.1) und (11.2) durch Konstruktion gesichert, wahrend (11.3) durch Enumeration zu etablieren ist.

FUr beliebige Permutationen (M)e{mPm} ist (11.1) dann erfUllt, wenn

(ILl')

wobei die Summationsreihenfolge durch (M) bestimmt, d.h. v(M) -c mit U~) vertraglich - vgl. (D2.4) - ist: :!.~M)ev(M)' Zur Siche-rung von (11.2) bzw. aquivalent

W(D,:!.~M)) ~ W(t,:!.~M)) , Vte<O,T> (hier: =1)

verlangt man ferner

(11.2')

l:Jh'_ l b. -b. - , h ' 1

l:~= 1 bh

> VjeM

wodurch die Menge der zulassigen Partitionen auf diejenigen be­grenzt wird, die den Bedingungen

(11.4)

(11.5) ( d a l: hm _ 1 If. = l: mh _ 1 \j. = 1 ) -'h -'h

genUgen. Hieraus ergibt sich, daB in dem obigen Zahlenbeispiel die optimale Ordnung (M) nur mit i 1=1 oder i 1=3 beginnen kann, wobei i 2=2 oder i 2=4 sein muB:

(M) v U1) e(v(M)) -c -c

1 - 2 - 3 - 4 0 4/10 6/10 9/10 535 1 - 2 - 4 - 3 0 4/10 9/10 7/10 600

1 - 4 - 2 - 3 0 7/10 9/10 3/10 610 1 - 4 - 3 - 2 0 9/10 5/10 3/10 530 'l

3 - 2 - 4 - 8/10 4/10 0 7/10 565 3 - 4 - 2 - 1 8/10 7/10 0 3/10 575

- 125 -

Da keine weiteren Permutationen mit den Eigenschaften (11.4) und (11.5) existieren, findet man aus dieser Liste

• (FJ) 0 9 5 3 ( M) = (1, 4 , 3 , 2) ; ~c = (TO ' TO ' TO ' TO")

e(v(Fl)) = IxI = 530 -c

=> a2 = lxI/dl 530/325 1,6308

FUr die Ermittlung von v (4) e gel ten die obigen AusfUhrungen und

Beziehungen analog, und man findet

(M) v (~1) -e c(~~M))

2 - 1 - 4 - 3 6/14 0 12/14 7/14 382,14 2 - 1 - 3 - 4 6/14 0 11/14 12/14 428,57

2 - 3 - 1 - 4 11/14 0 5/14 12/14 403,57

4 - 3 - 1 - 2 11/14 13/14 5/14 0 410,71

4 - 1 - 2 - 3 6/14 8/14 13/14 0 378,57 4 - 1 - 3 - 2 6/14 13/14 11/14 0 435,71

Also is t

(M) (4,1,2,3) ; v(M) 6 8 13 0 (14 ' 14 ' 14 ' 14) = -e

c(v(M)) -e = ell = 378,57

=> a l = Ib /ell = 467,86 / 378,57

11.2 Optimierung mit (e,c)

Mit ni!=2,027 ist ,i!=B/n*=49,33 und daher

'V * * e(,) ,·Ib 23.081 'Y i! it c(, ) = , ·eII = 16.033

1,236

26.147 18.676

i!

- 126 -

Wir ermitteln nunmehr optimale bzw. Naherungslosungen fUr fol­gende Tupel von Beschrankungswerten:

(a) (e,c) > (~(Tit) , CO(Tit »

(b) (e,c): _ "'( it) C ~ C T

( c) (e,c): "'it_Oit e(T )<e<e (T ) "'it_Oit C(T }<c<c (T )

1m Fall (a) liegt eine aktive Restriktion nicht vor; im Fall (b) dominiert eine starke Kapazitatsrestriktion, wahrend im Fall (c) eine harmonische Ausstattung mit Lagerraum und Finanz­mitteln vorliegt.

II.2(a) Inaktive Restriktionen

Wegen bCO(T it } ist yit:=y~M}. t1an findet also mit (L2):

(Ba.l)

=>

~(Tit) = Ib OT it = 23.081

CO(T It } = db OT It = 18.676

iiit = nit, K(iiltoll) = K(nltoll} = 5.675

FUr die Berechnung einer vergleichbaren Losung mit Hilfe des statischen Modells ist (L3) zunachst in der Weise zu erweitern, daB beide Restriktionen als schwache Ungleichungen explizit eingefUhrt werden l }. Bezeichnet dann vI den Multiplikator der Kapazitatsbeschrankung und v2 den der Budgetrestriktion, so lauten die KUHN/TUCKER-Bedingungen fUr eine optimale Losung des erweiterten Problems in kompakter Form2):

1

(11.6) IJ=1 -it m OJ m [2Clj r c Xj I j =1 _it I'- 1 ~

nj J- p.oC2.-2vl-2v20P' -J J J

1

IJ=1 -it

Ij=1 Bi

Ij= 1 2Cl. :2

(11.7) p.o[ J )~e Yi ii~ J p.oC2.-2vl-2v20P. -

J J J J

1) Zur Formulierung des erweiterten Modells, zur Ableitung der folgenden KUHN/TUCKER-Bedingungen, und zum Beweis der Ein­deutigkeit des durch diese erklarten stationaren Punkts vgl. etwa GUE/THOMAS (1968, S. 49ff).

2} Die Nichtnegativitatsbedingungen iij~o, YjeM, erUbrigen sich hier wegen (11.8), S.u.

- 127 -

(11.8) ~1 ~ 0, ~2 ~ 0

Aus diesen Bedingungen ist (wieder durch Probieren) die opti­male Losung zu berechnen. Solange nur einer der beiden Multi­plikatoren von Null verschieden, d.h. nur eine der beiden Be­schrankungen aktiv, ist, bereitet dies keine Schwierigkeiten. Sind jedoch beide Multiplikatoren simultan so zu bestimmen, daB (11.6) und (11.7) als Gleichungen (aktive Restriktionen) gel ten, so ist diese Aufgabe manuell kaum mehr zu bewaltigen 1).

Ein Tupel, das der Voraussetzung (a) entspricht, ist etwa (e,e) = (25.296 , 18.840). HierfUr findet man mit (11.6) bis (11.8), der modifizierten Losung (L3'),

(Ba.2) ~1

1

2

3 4

-0,036

-* ni

3,010 2,530 2,615 2,752

10,907

~2 -0,045

-* -* Yi xi

9.967 1. 661 3.952 7.905 9.560 3.824 1. 817 5.450

25.296 18.840

II.2(b) Dominante Kapazitatsrestriktion

KC!J.*) 5.904

Der Voraussetzung (b) entspricht u.a. das Tupel (e,e) = (27.700 , 15.100). Wegen a>a 2 gilt hier v*:=v(~), und man findet mit (L2): -c

(Bb. 1) n . - IDle = 2,152 T'-. - Bin = 46,468

~(T) = e ; eO(1) 1'txl = 24.628 < e => n*:=max{n*,n} = n K (n*'11) = 5.684

Aus einer Verminderung der Lagerkapazitat urn 5,8% gegenUber ~(T*) ergibt sich also ein Lagerkostenzuwachs von 0,15% gegenUber K(n*.ll).

1) Aus diesem Grunde treten hier und im weiteren fUr (e,c) keine glatten Zahlen auf - diese Werte wurden retrograd errechnet, urn groBere Rundungsfehler zu vermeiden.

- 128 -

1m Vergleich hierzu liefert (L3') folgende Werte:

(Bb. 2) III

1

2

3

4

-0,152

-* n i

2,744 3,555 2,632 3,893

12,824

112

-* Yi

10.933 2.813 9.498 1. 284

24.528

= 0 K(~*) = 6.241

-* xi

1. 822 5.625 3.800 3.853

15.100

Erachtet man die Lagerkosten dieser Losung als zufriedenstellend, K = K(~*) 6.241, so liefert die invertierte Losung (L2')

(Bb.3) 'V n(K) 3,1567 'V B/'il = 31,6786 n . - = T . -

und eO(~) = 16.790 mit ~(~) = 10.296 oder ~(~) = 14.821 mit con) = 11. 99 3

II.2(c) Harmonische Restriktionen

Offenbar erfUllt folgende Losung des statischen Modells die Voraussetzung (c):

(B c. 1) III -0,055 112 -0,042 K(~*) 6.003

-* -* -* n. Yi xi 1

1 3,002 9.993 1. 666 2 2,745 3.643 7.287 3 2,658 9.404 3.763 4 3,186 1. 568 4.708

---11,591 24.612 17.424

- 129 -

Sei also (e,e) = (24.612 , 17.424), so daB ein substitutiver Anlieferplan erforderlich wird. Bessere der beiden einseitigen

Strukturen ist wegen

e/db = 45,55 < 46,44 = e/txf

offen bar v(M) mit der Extremallosung -c

-. T +

2,15 => K(n+.ll) = 5.684

so daB durch Ermittlung einer optimalen substitutiven Struktur maximal

K(n+.ll) - K(n*.ll) 9 GE ;:; 0,15%

pro Planperiode eingespart werden konnen. Gesucht ist nun eine substitutive Struktur v* mit

( II. 9) e e

min{~ , ~} -. e (~) c (~ )

- * -T -> (T )

FUr die angenommenen Beschrankungswerte ist a=e/e=I,4125. Geht (M) man dann von der besseren einseitigen Struktur v als Anfangs--c

losung aus, so is t \1egen

(0 9 5 3 v (~1) ~ = , TO , TO TO) = -c

+ txf 530 + dI = 325 e (~) = = , c (~) = + + 1,6308 => e (~)/c (~) = a2 > a

zunachst e+(~) bestimmend fUr T, und entsprechend (11.9) sucht man ein v* mit

24.612

49,33 wobei

Nach Konstruktion von v(~) ist nun -c

498,9256

* T = T => K(ri.U) = K(n*.U)

- 130 -

FUhrt man dann ein 8v 1>0 bzw. aquivalent (aber mit unverander­tem Bezugspunkt v1=v 1=0)

8V 2 = 8V 3 = 8V 4 -8v 1

ein, so ist - + ~m + w(O,y') = e (y) - 8V 1°L.j=2 bj < e (y)

und

wobei c + (y' ) > + c (y) A

Aus dem Ziel

(11.10) e + (y' ) 1 efT *

ergibt sich

* + e Toe (y) -8V 1 =

*I4 T j=2 bj 0,0776

und man prUft leicht nach, daB fUr diesen spezifischen Wert - + w(O,y') = e (y'),

das Maximum der Zeitreihe w(o) also weiterhin an der Stelle t=O liegt. Die resultierende Struktur

y' = (0 ; 0,8224 ; 0,4224 ; 0,2224)

ist also effizient; ferner genUgt sie mit e+(y' )=498,9256 und c+(y' )=328,88 zwar nicht den Anforderungen fUr bedingte Optimalitat (bezUglich v(~)),

(11.11) + + e (y')/c (y') = a ere

vermittelt aber wegen ErfUllung der Eigenschaft (11.10) eine mit ~=T· global optimale Losung, in der weder enoch c eine wirksame (aktive) Restriktion darstellen.

- 131 -

Das allgemeine Verfahren zur Berechnung (bedingt) optimaler substitutiver Strukturen laBt sich folgendermaBen beschreiben: Man reduziert schrittweise das oder die e+(~) definierenden lokalen Maxima w(v.,v) - und damit zugleich die entsprechenden

1 -

s(vi ,~) -, wodurch die in M komplementaren w(Vj'~) und S(Vj'~)

- und damit zugleich c+(~) - erhoht werden. Dadurch findet eine zunehmende Plafondierung der maximalen w(v. ,v) und zu-

1 -

gleich eine zunehmende Differenzierung der s(v.,v) statt: 1 -

Die Zahl der ieMw' - +

~'w := {ier·,: w(v i ,~)=e (~)}

nimmt im gleichen MaBe zu, wie die der jeM s '

Ms := {ier'l: sty· ,v)=c+(v)} 1- -

abnimmt, da nach Definition der effizienten Struktur stets gilt

i~Mw => ier,s' i~Ms => ieMw

Die Lange jedes einzelnen Schrittes ist dabei immer entweder

durch den Obergang eines jeMs in die Teilmenge Mw oder

durch ErfUllung der Forderung (3.39) fUr bedingte oder (3.40) fUr absolute (globale) Optimalitat

bestimmt. Da bei vollstandiger Plafondierung der ursprUnglich impZizierten Zeitreihe w(.) Uber m Zwischenschritte die nicht­substitutive und daher auch nichtoptimale Struktur v(~) erreicht -e wUrde, folgt hieraus zusammen mit den Ergebnissen des Abschn. 3.4.3.2, daB jede einseitige Ausgangslosung ~~M) in hochstens m Schritten in eine bedingt oder absolut optimale Struktur UberfUhrt werden kann. Dasselbe gilt, bei sinngemaB umgekehrter BegrUndung, auch fUr alle Ausgangslosungen v(M). -e

- 132 -

LITERATURANGABEN

Andler, K.; Rationalisierung der Fabrikation und optimale

LosgrB~e, Dissertation Stuttgart 1927

Bamberg, G. und A.G. Coenenberg; Betriebswirtschaftliche Entscheidungslehre, MUnchen: Vahlen 1974

Beckmann, M.; "A Lagrangian Multiplier Rule in Linear Activity Analysis and Some of its Applications", Cowles Commission Discussion Paper: Economics No. 2054, (unpubl.) Nov. 5, 1952

Brown, R.G.; StatisticaZ Forecasting for Inventory Control,

New York: McGraw-Hi 11 1959

Buffa, E.S. and W. Taubert; Production-Inventory Systems: Planning and ControZ, 2nd ed., Homewood (Ill.): Irwin 1972

Churchman, C.W., R.l. Ackoff, and E.L. Arnoff; Introduction to Operations Research, New York: Wiley 1957

Dellmann, K.; "Ein heuristisches Modell zur gewinnmaximalen Seriengr~Ben und Seriensequenzplanung" in: Zeitschrift fur Betriebswirtschaft, 44. Jg., Heft 8 (Marz 1974), S. 139-158

Elsner, H.; "Produktions- und Lagerplanung in Saisonunter­nehmen" in: Zeitschrift fur Betriebswirtschaft, 39. Jg. (1969), S. 163-186

Garfinkel, R. and G. Nemhauser; Integer Programming, New York: Wiley 1972

- 133 -

Groch1a, E.; Grundlagen der Materialwirtschaft (Das material­

wirtschaftliche Optimum im Betrieb) , 2. Auf1., Wiesbaden: Gabler 1973

Gue, R.L. and M.E. Thomas; Mathematical Methods in Operations

Research, New York: Macmillan 1968

Hadley, G. and T.M. Whitin; Analysis of Inventory Systems,

Englewood Cliffs (N.J.): Prentice-Hal11963

Harris, F.; "Operations and Costs" in: Factory Management

Series, Chicago: Shaw 1915 (S. 48-52)

Hochstadter, D.; Stochastische Lagerhaltungsmodelle, Lecture Notes in Operations Research and Mathematical Econom­ics, Bd. 10, Berlin: Springer 1969

Johnson, L.A. and D.C. Montgomery; Operations Research in

Production Planning, Scheduling, and Inventory Control,

New York: Wiley 1974

Kirsch, W., 1. Bamberger, E. Gabe1e und H.K. Klein; Betriebs­

wirtschaftliche Logistik (Systeme, Entscheidungen,

Methoden) , Wi esbaden: Gab1 er 1973

Klemm, H. und M. Mikut; Lagerhaltungsmodelle (Theorie und

Anwendung), Berlin: Verlag Die Wirtschaft 1972

K1ingst, A.; Optimale Lagerhaltung, WUrzburg: Physica 1971

KUnzi, H.P. und W. Kre11e; Nichtlineare Programmierung,

Berlin: Springer 1962

Magee, J.F. and D.M. Boodman; Production Planning and Inven­

tory Control, 2nd ed., New York: McGraw-Hi 11 1967

Maxwell, W.L.; "The Scheduling of Economic Lot Sizes" in: Naval Research Logistics Quarterly, vol. 11 (1964) pp. 89-124

- l34 -

Miller, D.W. and M.K. Starr; Executive Decisions and

Operations Research, 2nd ed., Englewood Cliffs (N.J.): Prentice-Hall 1969

Moore, F.G. and R. Jablonski; Production Control, 3rd ed., New York: McGraw-Hi 11 1969

Plossl, G.~J. and O.H. Wight; Production and Inventory Control­

Principles and Techniques, Englewood Cliffs (N.J.): Prenctice-Hall 1967

Polya, G.; How to Solve It, Garden City (N.Y.): Doubleday 1957

Popp, W.; Einfuhrung in die Theorie der Lagerhaltung,

Lecture Notes in Operations Research and Mathematical Economics, Bd. 7, Berlin: Springer 1968

Pressmar, D.B.; "Stationare Planung und Losgri:iBenanalyse" in: Zeitschrift fur Betriebswirtschaft, 44. Jg., Heft 11 (Nov. 1974), S. 729-748

Pyhrr, P.A.; Zero-Base Budgeting (A Practical Management Tool

for Evaluating Expenses), New York: Wiley 1973

Reichmann, Th.; Die Abstimmung von Produktion und Lager

ders.

bei saisonalem Absatzverlauf, Beitrage zur betriebs­wirtschaftlichen Forschung, Bd. 29, Ki:iln: West­deutscher Verlag 1968a

"Die Bestimmung des optimalen Produktionsplans bei mehrstufigen Fertigungsprozessen in Saisonunterneh­men" in: Zeitschrift fur Betriebswirtschaft, 38. Jg. (1968 b),S.683-700

Riggs, J.L.; Production Systems: Planning, Analysis, and Control, New York: Wiley 1970

- 135 -

Roos, B.: Entwicklung und numepische UbepppUfung eines

einfachen Zeplegungsalgopithmus,

Dipl.-Arbeit, Univ. Karlsruhe (TH) 1975

Ryshikow, J.I.: Lagephaltung, Berlin: Akademie Verlag 1973

Schneewei S, H.; Entscheidungskpitepien bei Risiko, Berl in: Springer 1967

Stefanic-Allmayr, K.; "Die gUnstigste Bestellmenge beim Einkauf" in: SpapwiPtschaft, Zeitschpift fUp wipt­

schaftlichen Betpieb, Wien 1927, S. 504-508

Wagner, H.M. and T.M. Whitin; "Dynamic Version of the Economic Lot Size Formula" in: Management Science, vol. 5 (1958), pp.89-96

Wagner, H.M.; ppinciples of Opepations Reseapch, With Applica­

tions to Managepial Decisions, Englewood Cliffs (N.J.): Prentice-Hall 1969

Wiest, J.D.; "Heuristic Programs for Decision Making" in : Hapvapd Business Review, vol. 44, no. 5 (Sept.fOct., 1966), pp. 129-143

Vaughn, D.E., R. Norgaard, and H. Bennett; Financial Planning

and Management, Pacific Palisades (Cal.): Goodyear Publ. Co. 1972

Veinott, A.F., jr.; "Optimal Policy for a Multi-Product, Dynamic, Nonstationary Inventory Problem" in: Management Science, vol. 12, no. 3 (Feb., 1965), pp. 206-222

Band 42

Band 43

Band 44

Band 45

Band 46

Band 47

Westdeutscher Verlag

Die »braune Reihe« Die Schriftenreihe "Beitrage zur betriebswirtschaft­lichen Forschung" dient vornehmlich der VerOffent­lichung von besonders qualifizierten Arbeiten des wissenschaftlichen Nachwuchses, ohne dabei bestimmte Schulen oder Richtungen der Betriebswirtschaftslehre zu bevorzugen. Die Reihe ist zwar in erster Linie der wissenschaftlichen Forschung verpflichtet, kann aber auch der betrieblichen Praxis wertvolle Anregungen geben.

Frank Wenzel

Entscheidungsorientierte Informationsbewertung 1975. 216 S. Folieneinband

A /fred Luhmer

MaschineUe Produktionsprozesse Ein Ansatz dynamischer Produktions- und Kostentheorie. 1975. VIII, 208 S. Folieneinband

Arno Mahlert

Die Abschreibung in der entscheidungsorientierten Kostenrechnung 1976.247 S. Folieneinband

Gunter Franke

SteUen- und Personalplanung 1977.184 S. Folieneinband

Hermann Simon

Preisstrategien fur neue Produkte 1976.312 S. Folieneinband

Karl Inderfurth

Zur Giite linearer Entscheidungsregeln in Produktions-Lagerhaltungs-ModeUen 1977. IV, 204 S. Folieneinband