Subsymbolische Verfahren zur Ressourcenallokation Riezlern, 23.1.2003 Subsymbolische Verfahren zur...

Subsymbolische Verfahren zur Ressourcenallokation Riezlern, 23.1.2003

Subsymbolische Verfahrenzur Ressourcenallokation

Riezlern 23.1.2003

Oliver Wendt

Gliederung

• Anwendungsbeispiele automatisierter Informationsdienstleistungen– e-finance– e-logistics

• Übertragbarkeit der Methoden desYield Management „klassischer“ Dienstleistungen ?

• Ansätze zur heuristischen Bewältigung der Komplexitätsprobleme desNetwork Yield Management– KNN + GA– KNN + Reinforcement Learning

Anwendungsfall 1e-finance

Bayerische Landesbank

1822 und 1822direct

Berliner Volksbank

BBBank

Deutsche Bank

Comdirect

AnwendungspartnerIS Innovative Software AG

• seit 2000 fusioniert mit Teledata GmbH

• europäischer Marktführer für internetbasierte Finanzinformationsdienstleistungen

• ASP (Application Service Provider) für über 100 Banken, Broker, Medienhäuser und Internet-Portale

• ca. 1.600 eFinance-Sites im Internet und Intranet

AnwendungspartnerIS Innovative Software AG

• Augenblicklicher „Serverpark“– ca. 1.200 Linux-Server im Rechenzentrum der

Deutschen Börse– über 200 Mbit Peak-Netzlast (upstream)– 55 Mio. Visits pro Monat

allein für Hauptkunden Comdirect

• Europaweit größter Kunde von C.O.L.T.

Mittelfristziel: individuelles Portfoliomanagement

• Charts der historischen individuellen Portfolioentwicklung

• Risikoanalyse (z.B. Value-at-Risk-Metrikengemäß Kapitaladäquanz nach „Basel 2“)

• Portfoliooptimierung unter Berücksichtigung– vorgegebener Risikostrukturziele– individueller Transaktionskosten– „operativer“ Geschäftsrisiken

Langfristziel:individualisierte wissensintensive

Dienstleistungen durch/für Web Services

Anwendungsfall 2e-logistics

e-logistics

• Ziel: dynamische Tourenplanung und Umplanung mit Kunden-Zeitfenstern

• Prognose der Fahrzeiten von x nach y– tageszeitabhängig– verkehrssituationsabhängig

• typische Antwortzeiten der Time-Distance Web-Services ca. 300ms

Problem für heuristische Suchverfahren

e-logistics

Übertragbarkeit der Methoden des

Yield Management ?

Information als Repetierfaktor ?

• vernachlässigbaren Reproduktionskosten(sog. quasibeliebige Kopierbarkeit)

• „Verbrauch“ von Informationsgütern unkritisch• einfache Vernichtung / Entsorgung

keine Knappheit existierender Information

Einordnung als Repetierfaktor wenig sinnvoll

Information als Potentialfaktor ?

• Konkurrenz der Produktionsprozesse um diese Ressource fehlt bei Informationsprodukten

auch jede Software („logische Maschine“) kann beliebig repliziert werden

Kernproblem liegt nicht in der Konkurrenz um die Ressource Information selbst, sondern in der mittelbaren Konkurrenz um die knappen physischen Träger der Informationsverarbeitung !

–Menschen (Arbeitszeit)–Rechner (CPU / Memory)–Infrastruktur (Netzressourcen / Bandbreite)

Menge aller Verfahren, welche durch eine integrierte Preis- und Kapazitätssteuerung, die richtigen Einheiten eines zukünftig bereitzustellenden Kapazitätstyps dem richtigen Kundentyp so zuordnen, dass der Deckungsbeitrag der Betriebseinheit maximiert wird

[vgl. Belobaba (1989), Vogel (1989)].

Yield Management /Perishable Asset Revenue

Charakteristika YM-geeigneter

Produktionsprozesse[Kimes (1989)]

• hohe Kapazitätsbereitstellungskosten : Kapazität kurzfristig nur zu prohibitiv hohen, sprungfixen Kosten ausweitbar

•variable Grenzkosten einer zusätzlichen Leistungseinheit innerhalb der gegebenen Kapazitäten gering

• Möglichkeit zur Marktsegmentierung•Nichtlagerbarkeit und Verderblichkeit• Produktverkauf vor Produktionsbeginn• hohe Volatilität der Nachfrage

Yield Management /Perishable Asset Revenue

• Airline Industries (Passage & Cargo)

• Hotel- & Tourismus-Gewerbe

• Autovermietungen

• (Bekleidungs- / Modeartikel)

• (Lebensmittel)

Strukturanalogientypischer Dienstleistungen

(physische DL)

Computer

(informationelle DL)

externe Potentialfaktoren

zu beherbergende Gäste zu veredelnde Kundendaten

interne Potentialfaktoren

Hotelzimmer Personal

Memory Systembus Zentralprozessor

Repetierfaktoren Nahrung, Energie, Toilettenartikel Energie

Allokationsproblem Gewinnmaximale Zuweisung von Zeitscheiben der Ressourcen

an die optimale Teilmenge der nachfragenden Gäste

Gewinnmaximale Zuweisung von Zeitscheiben der Ressourcen

an die optimale Teilmenge der angefragten Verarbeitungsaufträge

Prozessstruktur-alternativen

diskret, endlich diskret, abzählbar unendlich (durch Schleifen und Rekursion)

Prozessauswahl-zeitpunkt

ex ante (bei Buchung) „real-time“ im Ausführungsprozess

Verfahren des Yield Management

• Pragmatische / heuristischeLösungsverfahren

– Geschachtelte Kontingentierung– Expected Marginal Seat Revenue

[Belobaba 89]

• Optimale Lösungsverfahren– Stochastische Dynamische Programmierung

auf Basis Markoff’scher Entscheidungsprozesse

StochastischeDynamische

Programmierung

• Sitzplatzkapazität von sechs Sitzplätzen

( Z := { 0, 1, 2, 3, 4, 5, 6 } )

• Sitzplätze können einzeln oder in Gruppen verkauft werden

• keine Unsicherheit über die Anzahl der noch eingehenden Anfragen

StochastischeDynamische

Programmierung

• drei Anfragetypen:

• rückwärts zählender Index k für Anfragen

Wahrschein- lichkeit

angefragte Kapazität

Erlös

F1 0.5 1 „Sitz“ 1 Geldeinheit F2 0.3 2 „Sitze“ 4 Geldeinheiten F3 0.2 3 „Sitze“ 9 Geldeinheiten

Stage 1

i a*(i) V*1(i) Berechnung

0 000 0.00 0.2*0 + 0.3*0 + 0.5*0 1 001 0.50 0.2*0 + 0.3*0 + 0.5*1 2 011 1.70 0.2*0 + 0.3*4 + 0.5*1 3 111 3.50 0.2*9 + 0.3*4 + 0.5*1 4 111 3.50 0.2*9 + 0.3*4 + 0.5*1 5 111 3.50 0.2*9 + 0.3*4 + 0.5*1 6 111 3.50 0.2*9 + 0.3*4 + 0.5*1

Stage 2 (z.B. i=4)

V2(4,000) = (0.2*0+0.3*0+0.5*0) +0.2 V1(4) +0.3 V1(4) +0.5 V1(4) = 3.50

V2(4,001) = (0.2*0+0.3*0+0.5*1) +0.2 V1(4) +0.3 V1(4) +0.5 V1(3) = 4.00

V2(4,010) = (0.2*0+0.3*4+0.5*0) +0.2 V1(4) +0.3 V1(2) +0.5 V1(4) = 4.16

V2(4,011) = (0.2*0+0.3*4+0.5*1) +0.2 V1(4) +0.3 V1(2) +0.5 V1(3) = 4.66

V2(4,100) = (0.2*9+0.3*0+0.5*0) +0.2 V1(1) +0.3 V1(4) +0.5 V1(4) = 4.70

V2(4,101) = (0.2*9+0.3*0+0.5*1) +0.2 V1(1) +0.3 V1(4) +0.5 V1(3) = 5.20

V2(4,110) = (0.2*9+0.3*4+0.5*0) +0.2 V1(1) +0.3 V1(2) +0.5 V1(4) = 5.36

V2(4,111) = (0.2*9+0.3*4+0.5*1) +0.2 V1(1) +0.3 V1(2) +0.5 V1(3) = 5.86

Stage 2 (z.B. i=3)

V2(3,110) = (0.2*9+0.3*4+0.5*0) + 0.2 V1(0) +0.3 V1(1) +0.5 V1(3) = 4.90 aber V2(3,111) = (0.2*9+0.3*4+0.5*1) + 0.2 V1(0) +0.3 V1(1) +0.5 V1(2) = 4.50

Stochastische Dynamische Programmierung

Restwert V*(i) bei optimaler Annahmestrategie

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

verbleibende Zahl N von Anfragen

Annahme wenn: Erlösk + V*k-1(i - Zimmerk) V*k-1( i ).

Eigenschaften der Restwertfunktion V*

• inventory monotonicity– V* steigt monoton mit der Restkapazität i

• time monotonicity– V* steigt monoton mit der der Anzahl verbleibender

Anfragen k

• ABER: Monotonie der PREISE nur, wenn keine Zunahme der Zahlungsbereitschaft über die Zeit !

Beispiel:nichtmonotone Nachfrage

• k > 2

• k <= 2

probability requested capacity

revenue

F1 0.6 1 „seat“ 1 monetary unit F2 0.4 2 „seat“ 4 monetary units F3 0 3 „seat“ 9 monetary units

probability requested capacity

revenue

F1 0.33 1 „seat“ 1 monetary unit F2 0.33 2 „seat“ 4 monetary units F3 0.34 3 „seat“ 9 monetary units

Stochastic Dynamic Programming

expected revenue V*(i) from applying an optimal strategy

0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

remaining number N of requests

Network Yield ManagementDemo

Network Yield Management

Relevanz

• Hohe Relevanz derartiger Verbundeffekte im Informations-Kontext:

– einerseits müssen hier die Ergebnisse der Sub-Services zur Verarbeitung des übergeordneten Service weitergeleitet werden, die ggf. auf anderen Hardware-Komponenten untergebracht sind (Airline-Analogie)

– andererseits beanspruchen viele Service-Aufträge mehrere konsekutive Zeitscheiben einer Ressource(Multi-Day-Analogie zum Hotel-Fall)

„kleiner Trost”:

Viele IV-Prozesse sind glücklicherweise “preemptiv”

“Umzug” der Zwischenergebnisse des IV-Prozesses in ein anderes “Hotel” (anderer Prozessor) möglich

Ausnahmen insbes. bei „humaner“ Weiterverarbeitung:

Audio-Übertragung

Video-Übertragung

Relevanz

Bewältigung der Komplexitätsprobleme des Network

Yield Management

Genetische Algorithmen (+KNN)Reinforcement Learning (+KNN)

Bestimmung der Restwertfunktion bei

Ressourcenkomplementarität

• optimale Lösung:Zustandsraum als Menge aller möglichen Bündel von Verfügbarkeiten aller zu bewertenden Ressourcen! Kombinatorische Explosion

• lineares „Bid-Pricing“ deutlich suboptimal[Weatherford 92], [Talluri / Ryzin 96]

• Repräsentation der multidimensionalen Restwertfunktion mittelsKünstlicher Neuronaler Netze ?

Kombinationsgewinn

• Fall A: Kombinationsgewinn

Typ Wahrschein-lichkeit

AngefragteRess.

Erlös

F1 0.4 11 700 GEF2 0.3 01 300 GEF3 0.3 10 300 GE

Kombinationsgewinn

0 1 2 3 4 5 6 7 8 9 10

s10=s01

s20=s02

s21=s12

Kombinationsverlust

• Fall B: Kombinationsverlust

Typ Wahrschein-lichkeit

AngefragteRess.

Erlös

F1 0.4 11 550 GEF2 0.3 01 300 GEF3 0.3 10 300 GE

Kombinationsverlust

0 1 2 3 4 5 6 7 8 9 10

s10=s01

s20=s02

s21=s12

weight matrix 1

weight matrix 2

x1 x5x2 x3 x4 x10x7x6 x9x8

hidden layer

output layer

Vt(x)= 3200

input layer

Network Yield ManagementKNN als Lösung ?

weight matrix 1

weight matrix 2

x1 x5x2 x3 x4 x10x7x6 x9x8

hidden layer

output layer

input layer

Vt(x)= 2300

Network Yield ManagementKNN als Lösung ?

Aufbau eines Neurons

Transferfunktion

Localmemory

“activate”X1 X2 Xn

y Output signal

Copies of output signal

Input signals

Backpropagation (20000 steps)

MLP-3-5-1

1 2 3 4 5 6 7 8 9 10

verbleibende Anfragen

MLP-3-5-1

1 2 3 4 5 6 7 8 9 10

MLP-3-5-1

1 2 3 4 5 6 7 8 9 10

MLP-3-5-1

1 2 3 4 5 6 7 8 9 10

MLP-3-5-1

1 2 3 4 5 6 7 8 9 10

MLP-3-5-1

1 2 3 4 5 6 7 8 9 10

MLP-3-5-1

1 2 3 4 5 6 7 8 9 10

MLP-3-5-1

1 2 3 4 5 6 7 8 9 10

MLP-3-5-1

1 2 3 4 5 6 7 8 9 10

MLP-3-5-1

1 2 3 4 5 6 7 8 9 10

MLP-3-5-1

1 2 3 4 5 6 7 8 9 10

Training des KNN

• übliche Lernregeln für KNN leider ungeeignet, da Bewertungsfehler nur SIMULATIV abschätzbar

• Finden optimaler Gewichte w* ist somit selbst hochdimensionales stochastisches Parameteroptimierungsproblem

• prädestiniert für Einsatz naturanaloger Verfahren ??? (Evolutionsstrategien / Genetische Algorithmen)

( )* arg max w

ww V ( *) *wV V

Ablauf Genetischer Algorithmen

Crossover-Operatorenfür KNN

Eltern

KNN+GA-Ergebnisse

500.000 Evaluationen

Reinforcement Learning

environment

action a r reward rstate s

Ziel des RL-Agenten: Maximierung der Summe von Reinforcement-Signalen (long run!!)

r8 = 5r 1 =

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ

)]V(s)γV(s[r α)V(s)(sV t1t1tttπ

Temporal-Difference-Learning

Beispiel

r4 = 71.2

Episode 1

r8 = 5r 1 =

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ

Beispiel

r4 = 71.2

Episode 1

r8 = 5r 1 =

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ

Beispiel

r4 = 71.2

Episode 1

r8 = 5r 1 =

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ

Beispiel

r4 = 71.2

Episode 1

= 0.2 0

r8 = 5r 1 =

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ

Beispiel

r4 = 72.48

0.72 0

Episode 2

r8 = 5r 1 =

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ

Beispiel

r4 = 73.78

0.98 0

Episode 3

r8 = 5r 1 =

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ

Beispiel

r4 = 714.9

1.97 0

Episode 20

r8 = 5r 1 =

r3 = 8

r2 = 4

r7 = 2

)(sV tπ

)(sV 1tπ

)(sV 2tπ

Beispiel

r4 = 715.1

1.97 0

Episode 21

TD(0) Reinforcement Learning

(3-Ebenen-MLP)

50.000 Evaluationen 500.000 Evaluationen

Zusammenfassung und Ausblick

Zusammenfassung

• große strukturelle Ähnlichkeiten der Bepreisung von IV-Leistungen und des Yield-Management klassischer Dienstleistungen

• Problem des Network Yield Management muss „gelöst“ werden

• Adaption trotzdem vielversprechender als Anpassung der klassischen betriebswirtschaftlichen Preistheorie

Ausblick

• Einsatz in DISPOWEB-Verhandlungsprotokollen für Softwareagenten

• alternative Zustandsraumkompression(z.B. Growing Neural Gas-Topologie)

• Integration kombinatorischer Auktionen und Bepreisung von Real Options

• Integration nachfrageseitiger interpersoneller Netzeffekte

Kombination YM und Auktionstheorie

• dynamische Bestimmung gewinnmaximierender Preise umfaßt aber ZWEI interdependente Probleme:

– Welcher Anreizmechanismus bringt die Nachfrager dazu, ihre Zahlungsbereitschaft wahrheitsgemäß zu offenbaren?(Auktionstheorie für Leistungsbündel)

– Welcher Nachfrager wird wann mit welchem Ressourcenbündel zu welchem Preis bedient? (YM)

YM / Perishable Asset Revenue Management

production / service

request

Auktionen

request

Generalisierung: Auktionen & YM

Literatur

• Hu, J. / Wellman, M.P.: Multiagent Reinforcement Learning: Theoretical Framework and an Algorithm, Madison 1998

• Kephart, J.O. / Tesauro, G.J.: Pseudo-convergent Q-Learning by Competitive Pricebots, Hawthorne 1999

• Kephart, J.O. / Tesauro, G.J.: Pricing in agent economies using multi-agent Q-Learning, Hawthorne 1999

• McGill, J.I.; van Ryzin G.J.: Revenue Management: Research Overview and Prospects; Transportation Science 33 (1999) S. 233-256.

• Sutton, R.S. : Reinforcement-Learning: An Introduction, Cambridge 1998

• Schwind, M.; Wendt, O.: Dynamic Pricing of Information Products based on Reinforcement Learning: A Yield Management Approach; Proceedings of the 25th Conference on Artificial Intelligence (KI2002); Aachen.

Subsymbolische Verfahren zur Ressourcenallokation Riezlern, 23.1.2003 Subsymbolische Verfahren zur...

Documents

Ressourcenallokation/Mittelverteilung in der ... › sanita › download › Marckmann.pdfaus ethischer Perspektive Georg Marckmann Ludwig-Maximilians-Universität München Institut

Checkliste - Landesportal Sachsen-Anhalt · Eribolus nanus (Zetterstedt, 1838) s 3 Wendt (1993) E. sudeticus Becker, 1910 Incertella albipalpis (Meigen, 1830) sh Wendt (1993) Incertella

Diagnostische Verfahren – Thrombosehaemonk/fuer_studenten/Vorlesungsfolien/32 Thrombose... · THROMBOSE DIAGNOSTISCHE VERFAHREN Bildgebende Verfahren • Phlebographie • Farbkodierte

Therapiemöglichkeiten des hormonrefraktären Prostatakarzinoms · hormonrefraktären Prostatakarzinoms Dr. Gunnar Wendt-Nordahl ... ¾Absetzen der Antiandrogene über mind. 4 Wochen

Teil 2 Identität und Diskurs Allgemein bezeichnet ... · Variable behandeln, ist vor allem den Arbeiten von Alexander Wendt verpflichtet (insbes. Wendt 1999). Da Wendt sich vor allem

Seminar WS 2002/03: Automatisierte Ressourcenallokation Prof. Dr. Wolfgang König: Lehrstuhl für Betriebswirtschaftslehre, insb. Wirtschaftsinformatik und

PRODUKTE VON WENDT LEIDENSCHAFT &P RÄZISION MIT HERZ …

Eutergesundheit. Lenz, 20052 Literatur K. Wendt, H. Bostedt, H. Mielke, H.-W. Fuchs: Euter- und Gesäugekrankheiten. K. Wendt, H. Bostedt, H. Mielke, H.-W

Andreas Wendt, Monika Masłon - zaeb.netzaeb.net/wordpress/wp-content/uploads/2018/04/Wendt_finfin.pdf · Andreas Wendt, Monika Masłon IABC DDR PRL – Gestaltungsübungen für Grundschulkinder

Ringvorlesung: Semantic Web Services Discovery Piotr Wendt Hochschule für Angewandte Wissenschaften Fachbereich e/i Informatik

Technikdialog der Bundesnetzagentur am 24.06.2015 in Kassel: Dr. V. Wendt, Europacable: Teilverkabelung als Lösungsansatz für den Netzausbau in Deutschland

WENDT onlinecatalogue [ENG version] v01-2014

Die neue Enterprise Project Management Strategiedownload.microsoft.com/download/c/c/1/cc12d85c-4043-41a0-9528... · Strategie Effiziente Ressourcenallokation Förderung der Zusammenarbeit

Digitalisierung des Rechnungsverkehrs Elektronische Rechnungen bei der GEWOBA Einsatz des Mareon-Portal Datum:18.05.2015 Referent:Frank Wendt, GEWOBA

Logbuch und QSL-Karte DL7SP OV Überwald – F50 Holger Wendt DL7SP 04/2009

Elizitierung von Versprechern Inga Blome Christina Ellerbrock Christine Wendt

C METALLISCHE WERKSTOFFE - tu-freiberg.de · - 62 - Die wichtigsten Verfahren zur Stahlherstellung sind das Thomas-Verfahren (Windfrischverfahren) Siemens-Martin-Verfahren Sauerstoff-Aufblas-Verfahren

Jugendstück von Marisa Wendt Spielzeit 2017/2018 · 2019-04-30 · Jugendstück von Marisa Wendt Spielzeit 2017/2018 Materialmappe DIE NACHT, IN DER ALLES SH Landestheater SZ 2017/2018

Das 2. Semester der Sozialen Arbeit präsentiert Die Werkstatt Prof. Dr. P.-U. Wendt

Taschenbuch - GBVTaschenbuch der Wirtschaftsinformatik und Wirtschaftsmathematik Herausgegeben von: Wolfgang König, Heinrich Rommelfanger, Dietrich Ohse, Oliver Wendt, Markus Hofmann,