Zusammenfassung

Wir beschreiben verschiedene Wirkungsweisen der Preisb¨ undelung, er¨ ortern die Modellierung des Optimal Bundle Pricing-Problems als gemischt-Lineares Programm nach Hanson und Martin, und stellen unser Vorgehen bei der Implementierung dieses Verfahrens als Java-Programm unter Verwendung des LP-Solvers Ampl/Cplex vor.

Inhaltsverzeichnis

1  Aufgabenstellung  3

2  Theorie der Preisb undelung  4

2.1  Qualitative Wirkungsmechanismen  4

2.2  Absch opfung von Konsumentenrente  4

2.3  Entscheidungsempfehlung  9

3  Formulierung des Optimal Bundle Pricing-Problems als gemischt-  

lineares  Programm  11

3.1  Das Modell  11

3.2  Variablen und Parameter  12

3.3  Gleichungen  13

3.4  Implementierung  14

4  Entwicklung von BundleOpt  16

4.1  Wahl der Programmiersprache  16

4.2  Wahl des Solvers  16

4.3  Alternative Vorgehensweisen  18

4.4  Grafische Benutzeroberfl ache  19

4.5  Programmier-Schnittstellen  20

4.6  Sensitivit atsanalyse  23

5  Praktischer Einsatz  25

5.1  Datenbeschaffung  25

5.1.1  Bestimmung der individuellen Maximalpreise  26

5.2  Rechenaufwand  27

5.3  Ausblick  28

A  Optimal Bundle-Pricing-Problem als GLP/LP  29

A.1  LP-Relaxation  31

B  Gemischt-Lineares Programm im AMPL-Format  32

B.1  Eingabedatei  32

B.2  Ausgabedatei  35

C  Versuchdaten von Hanson/Martin  37

1

Abbildungsverzeichnis   

2.1  Reservationspreisraum bei Einzelverkauf  6

2.2  Optimale Preisstrategie bei Einzelverkauf  7

2.3  Reservationspreisraum bei reiner Preisb undelung  7

2.4  Optimale Preisstrategie bei reiner Preisb undelung  9

4.1  Daten- und Kontrollfl usse  18

4.2  Screenshot: BundleOpt in Aktion  21

4.3  Screenshot: Ausgabe-Dialog f ur Sensitivit ats-Analyse  23

4.4  Screenshot: Ausgabe-Dialog f ur multiple Sensitivit ats-Analyse  24

2

Kapitel 1

Aufgabenstellung

Immer h¨ aufiger trifft man in den verschiedensten Bereichen der Wirtschaft auf Angebote, bei denen verschiedene - ansonsten meist einzeln erh¨ altliche Produkte - im Paket zu einem Preis angeboten werden. Dies wird als Preisb¨ undelung (bundle pricing) bezeichnet.

Ein h¨ aufig zitiertes Beispiel in diesem Zusammenhang sind hier die sog. Sparmen¨ us der Fast-Food-Kette McDonald’s, die verschiedene Produkte (ein Getr¨ ank, einen Hamburger, . . . ) zu einem gegen¨ uber der Summe der ¨ ublichen

Einzelpreise um ca. 15% g¨ unstigeren Preis enthalten (vgl. [3]). Aber auch im Dienstleistungssektor ist diese Form der Preisdifferenzierung anzutreffen, so z.B. bei Pauschalreisen, bei denen der Flug, die Unterbringung und ein Mietwagen in einem Paket angeboten werden.

Man kann sogar soweit gehen, G¨ uter und Dienstleistungen als B¨ undel zu definieren, die sich praktisch nicht weiter zerlegen lassen. So kann man z.B. einen PKW als als B¨ undel aus den Komponenten Transport und Luxus auffassen. Es stellt sich nun die Frage, warum Anbieter diese Angebotsstrategie w¨ ahlen - m¨ ogliche Gr¨ unde hierf¨ ur er¨ ortern wir in Kapitel 2 der vorliegenden Ausarbeitung. In Kapitel 3 dann stellen wir einen Algorithmus vor, der unter Ber¨ ucksichtigung von Preisb¨ undelung eine optimale Preispolitik errechnet, Kapitel 4 schließlich beschreibt unser konkretes Vorgehen bei der Implementierung dieses Verfahrens in Java, im letzten Kapitel betrachten wir die bei der praktischen Anwendung auftretenden Probleme.

3

Kapitel 2

Theorie der Preisb ¨ undelung

2.1 Qualitative Wirkungsmechanismen

Da Preisb¨ undelung in der Praxis so h¨ aufig anzutreffen ist, stellt sich nat¨ urlich die Frage, warum diese Form der Preisgestaltung f¨ ur vorteilhaft gehalten wird. Direkt einsichtig sein d¨ urfte, daß sich mittels Preisb¨ undelung economies of scale (Erfahrungskurveneffekte) und economies of scope (Verbundeffekte) realisieren lassen.

Einige Firmen nutzen die B¨ undelung Ihrer Produkte auch zum Erreichen einer Monopolstellung oder zum Errichten von Markteintrittschranken; ein oft zitiertes Beispiel ist das Tabelliermaschinen-Monopol der Firma IBM mitte der 30er Jahre, das diese auch auf Lochkarten (hier gab es viele Anbieter) ausweiten wollte, indem sich der K¨ aufer einer Tabellier-Maschine verpflichten mußte, auch Lochkarten bei IBM zu erstehen ([15]).

Synergie-Effekte k¨ onnen ein weiterer m¨ oglicher Vorteil der Produktb¨ undelung sein, z.B. ein besonders einfacher und stabiler Datenaustausch zwischen den einzelnen Modulen des Microsoft Office-Paktes, was mit Programmen verschiedener Hersteller vielleicht nicht gegeben ist.

Dar¨ uber hinaus gibt es aber noch einen weiteren, vielleicht nicht so direkt einsichtigen quantitativen Mechanismus, n¨ amlich die effizientere Absch¨ opfung der Konsumentenrente, womit wir uns im n¨ achsten Abschnitt besch¨ aftigen.

2.2 Absch¨ opfung von Konsumentenrente

Im folgenden entwickeln wir ein einfaches Model mit einem monopolistischen Anbieter von zwei Produkten und zwei Konsumenten A und B. Von den beiden Konsumenten seien die Reservationspreise r ki f¨ ur beide G¨ uter bekannt; diese geben an, wieviel der Konsument h¨ ochstens f¨ ur das Gut i zu zahlen bereit ist, weshalb in der Literatur auch die Bezeichnungen Maximalpreis, Prohibitivpreis oder Vorbehaltspreis zu finden sind (vgl. [5]). Ist der

4

tats¨ achlich vom Monopolisten f¨ ur das Gut festgelegte Preis kleiner oder gleich diesem Reservationspreis, so konsumiert der Nachfrager genau eine Einheit des Gutes. Eine evtl. Preisdifferenz zwischen der Zahlungsbereitschaft und dem tats¨ achlichen Preis bezeichnen wir als Konsumentenrente (consumer surplus) s: s ki = r ki − p i k ∈ {A, B}, i ∈ {1, 2} (2.1)

Wir gehen selbstverst¨ andlich davon aus, daß die Reservationspreise jeweils uber den Grenzkosten f¨ ur die Herstellung des jeweiligen Gutes liegen. Außerdem ¨

ersteht ein Konsument h¨ ochstens eine Mengeneinheit eines Gutes. Auch werden wir vorerst die Produktionskosten vernachl¨ assigen, wir nehmen die Reservationspreise also als kostenbereinigt an.

Verdeutlichen wir uns dies an einem Zahlenbeispiel mit folgenden Reservationspreisen:

Die optimale Preispolitik f¨ ur den Anbieter w¨ are nat¨ urlich Preisdiskriminierung: er verlangt von jedem Konsumenten einen Preis genau in der H¨ ohe seines Reservationspreises. Allerdings werden solche Daten nicht vorliegen (h¨ ochstens uber die statistische Verteilung der Zahlungsbereitschaft innerhalb bestimmter ¨

Marktsegmente), außerdem gibt es Gesetze, die ein solches Vorgehen untersagen (z.B. in den USA der Robinson-Patman-Act von 1936, vgl. [2] und [11]). Aus diesen Gr¨ unden heraus wird sich also der Monopolist auf einen Preis p ^∗ i pro Gut festlegen m¨ ussen.

In unserem Beispiel kommen hierf¨ ur h¨ ochstens die verschiedenen Reservationspreise in Frage. W¨ urde der Anbieter n¨ amlich f¨ ur Gut i einen Preis

p ^∗ i > max{r Ai , r Bi } (2.2)

festelegen, so w¨ urde er auf keinen Fall etwas verkaufen. Mit einem Preis

p ^∗ i < min{r Ai , r Bi } (2.3)

w¨ urden nicht das volle Erl¨ ospotential ausgesch¨ opft. Ein Preis P ∗ i

mit w¨ urde zwar A vom Kauf abhalten, dabei aber unn¨ otigerweise eine Konsumentenrente in H¨ ohe von s Bi = r Bi − p ^∗ (2.5)

i

erm¨ oglichen (hierbei gelte o.B.d.A. r Ai < r Bi ). Im Rahmen unseres Models sind also als potentieller Preis f¨ ur ein Gut nur zwei Werte sinnvoll: p ^∗ i ∈ {r Ai , r Bi } (2.6)

Ein solcher Preisvektor teilt unsere Konsumenten in vier verschiedene Gruppen ein (vgl. Abbildung 2.1):

5

• Konsumenten, deren Reservationspreise f¨ ur beide G¨ uter kleiner als die festgelegten Preise sind, kaufen kein Gut (Feld A)

• Konsumenten, deren Reservationspreise f¨ ur beide G¨ uter gr¨ oßer-gleich als die festgelegten Preise sind, kaufen beide G¨ uter (Feld D)

• Konsumenten, bei denen nur der Reserverationspreis f¨ ur Gut 1 gr¨ oßergleich den festgelegten Preisen ist, kaufen nur Gut 1 (Feld B)

• Konsumenten, bei denen nur der Reservationspreis f¨ ur Gut 2 gr¨ oßer-gleich den festgelegten Preisen ist, kaufen nur Gut 2 (Feld C)

Abbildung 2.1: Reservationspreisraum bei Einzelverkauf

Mit den bisherigen Daten sind also folgende vier Preiskombinationen zu betrachten:

Die optimale Preisstrategie ist also (p ^∗ 1 , p ^∗ 2 ) = (5, 4) mit einem Gesamtgewinn von 14 GE (vgl. Abbildung 2.2).

Bisher haben wir aber noch nicht die M¨ oglichkeit einer (reinen) Preisb¨ undelung in Betracht gezogen: hierbei bieten wir beide G¨ uter nur noch im Paket zu einem Preis p ^∗ B an. Durch ein solches Angebot teilen wir die Konsumenten in zwei verschiedene Gruppen (vgl. 2.3).

6

r 2

6 5 4 3 2 1 0

Abbildung 2.2: Optimale Preisstrategie bei Einzelverkauf

Abbildung 2.3: Reservationspreisraum bei reiner Preisb¨ undelung

7

Ein Konsument ist jeweils bereit, f¨ ur das B¨ undel die Summe seiner Reservationspreise ¹ f¨ ur die einzelnen Komponenten des B¨ undels zu bezahlen: r kB = r k1 + r k2 k ∈ {A, B} (2.7)

Die Gerade mit Steigung m = −1 im Bild stellt die Menge aller Konsumenten dar, deren Summe der Reservationspreise dem Preis des B¨ undels genau entspricht. Die Preisb¨ undelung teilt die potentiellen Konsumenten also in zwei Gruppen ein:

• Konsumenten, deren kumulierte Zahlungsbereitschaften kleiner als der festgelegte B¨ undelpreis sind (also unterhalb der Diagonalen liegen), verzichten auf das B¨ undel (Feld A)

• Konsumenten, deren kumulierte Zahlungsbereitschaften gr¨ oßer-gleich als der festgelegte B¨ undelpreis ist, kaufen das B¨ undel (Feld B) Die beiden Konsumenten haben f¨ ur dieses B¨ undel B folgende Reservationspreise:

Gem¨ aß den obigen Ausf¨ uhrungen zu den sinnvollen Wahlm¨ oglichkeiten des Preisniveaus kommen hier also wieder nur zwei Werte f¨ ur das B¨ undel in Frage:

p ^∗ B ∈ {7.5, 9} (2.8)

Diese beiden Strategien versprechen folgende Erl¨ ose:

Die gewinnmaximale Strategie p ^∗ B = 7.5 (vgl. Abbildung 2.4) bei Preisb¨ unde-

lung ist somit sogar vorteilhafter als die beim Einzelverkauf (hier war das Ergebnis nur 14 GE).

Dies l¨ aßt sich damit erkl¨ aren, daß (in diesem Fall) mittels der B¨ undelung die Konsumentenrente effektiver abgesch¨ opft werden kann. Beim Einzelverkauf hat Konsument B nur Gut 1 gekauft, wobei er hierf¨ ur aber durchaus noch s B1 = 1.5 GE mehr bezahlt h¨ atte (vgl. 2.2). Durch die Preisb¨ undelung wird diese ¨ ubersch¨ ussige Zahlungsbereitschaft zus¨ atzlich auf die Zahlungsbereitschaft f¨ ur Gut 2 umgelenkt, wodurch ihm der Monopolist jetzt beide G¨ uter verkaufen

- quasi zum durchschnittlichen Reservationspreis - kann. Eine weitere m¨ ogliche Strategie w¨ are noch, das B¨ undel und die Einzelprodukte gleichzeitig anzubieten; man spricht dann von gemischter B¨ undelung. Im vorliegenden Fall w¨ urde man mit dem Preisvektor

¹ bei Synergieeffekten k¨ onnte er auch bereit sein, mehr zu bezahlen

8

r B

7 6 5 4 3 2 1 0

Abbildung 2.4: Optimale Preisstrategie bei reiner Preisb¨ undelung

(p ^∗ 1 , p ^∗ 2 , p ^∗ B ) = (6.5, 4, 9)

einen Gesamtgewinn von 9 + 6.5 = 15.5 erzielen, also noch mehr als bei der reinen B¨ undelung.

In der Regel wird man bei der gemischten B¨ undelung fordern:

p ^∗ 1 + p ^∗ 2 > p ^∗ (2.9)

B

Das B¨ undel soll also preiswerter sein als die Einzelbestandteile, weil der Konsument sich das B¨ undel sonst selbst billiger zusammenstellen kann. Abweichen von dieser Forderung wird man h¨ ochstens bei sehr weitreichenden Synergie-Effekten, z.B. einer Briefmarkensammlung: die einzelnen Marken f¨ ur sich alleine sind f¨ ur den Sammler kaum von Wert, erst die komplette Serie ist interessant.

2.3 Entscheidungsempfehlung

Wie oben gezeigt, kann Preisb¨ undelung im Vergleich zu einer herk¨ ommlichen Preisstrategie also zus¨ atzliche Gewinne erm¨ oglichen. Wann genau aber ist eine Form der Preisb¨ undelung vorteilhaft?

Leider kann hier keine allgemeing¨ ultige Entscheidungsregel gegeben werden. In der herk¨ ommlichen Literatur (z.B. [2]) werden auch nur sehr kleine Beispiele (mit z.B. 2 G¨ utern) betrachtet, wie man in der Praxis mit z.B. n = 20 Produkten eine Entscheidung treffen kann, bleibt offen. Bei [15] findet man folgende allgemeine Tendenzaussagen:

9

• Haben die Nachfrager generell f¨ ur ein Gut eine hohe Preisbereitschaft, f¨ ur das andere aber eine geringe, dann ist der herk¨ ommliche Einzelverkauf vorteilhaft

• Wenn die Preisbereitschaft f¨ ur beide Einzelprodukte hoch ist, dann ist die reine B¨ undelung vorteilhaft

• Wenn am Markt sowohl Nachfrager mit extremen als auch solche mit ausgewogenen Pr¨ aferenzen zu finden sind, dann ist die gemische B¨ undelung vorteilhaft

Wie man in der Praxis die optimale Preispolitik unter Ber¨ ucksichtigung von B¨ undelung findet, bleibt hiermit allerdings offen. Diese L¨ ucke versucht [1] zu schließen, indem mittels Linearer Programmierung ein praxistaugliches Vorgehen vorgeschlagen wird. Die Implementierung dieses Verfahren ist Gegenstand der vorliegenden Arbeit.

10

Kapitel 3

Formulierung des Optimal

Bundle Pricing-Problems

als gemischt-lineares

Programm

Bis zur Ver¨ offentlichung des Aufsatzes Optimal Bundle Pricing von Hanson und Martin im Jahre 1990 ([1]) war praktisch kein operationalisierbarer Ansatz zur quantitativen Behandlung der Preisb¨ undelung innerhalb der Preispolitik verf¨ ugbar.

Hanson/Martin formulieren hierbei dieses Problem zun¨ achst innerhalb eines Modells als gemischt-lineares-Programm (GLP):

3.1 Das Modell

Das verwendete Modell geht von einem gewinnmaximierenden monopolistischen Unternehmen aus, der n verschiedenen Produkte (Komponenten) anbietet, f¨ ur welche er die Preise festlegen kann, wobei allerdings Preisdiskriminierung - also der Verkauf des gleichen Gutes bzw. B¨ undels an verschiedene Kosumentensegmente zu unterschiedlichen Preisen - nicht gestattet ist. Im weiteren werden noch folgende Pr¨ amissen getroffen:

• Die Konsumenten maximieren ihren Nutzen in Form der Konsumentenrente; kauft ein Konsument ¨ uberhaupt nichts, so ist seine Konsumentenrente aber gleich null 1

• Die maximale Zahlungsbereitschaft f¨ ur alle Komponenten/B¨ undel ist f¨ ur alle Konsumentengruppen bekannt

¹ ohne diese Annahme w¨ urde der Konsument nie etwas kaufen; selbst wenn ein Gut zum Preis 0 angeboten w¨ urde, w¨ are der Konsument zwischen Kauf und Nicht-Kauf indifferent

11

• Ein Konsument kann einzelne Komponenten eines B¨ undels ohne Kosten entsorgen, wenn er sie nicht ben¨ otigt

• Ein Konsument kann sich aus einzelnen B¨ undeln/Komponenten ohne weitere Transaktionskosten ein anderes B¨ undel zusammenstellen

• Die Herstellungskosten eines B¨ undels B i , das eine Teilmenge eines anderes B¨ undels B j ist, darf dessen Herstellungskosten nicht ¨ uberschreiten

• Eine zweite Mengeneinheit eines Gutes hat keinen Nutzen f¨ ur einen Konsumenten, auch ein Weiterverkauf ist ausgeschlossen

3.2 Variablen und Parameter

Wir gehen von M Marktsegmenten und n Produkten (Komponenten) aus, so daß sich als Zahl der m¨ oglichen B¨ undel B ⁱ L = 2 ⁿ − 1

ergibt - wir verbieten also das leere B¨ undel: B i = ∅. Folgende Eingangsgr¨ oßen (Parameter) ben¨ otigen wir f¨ ur unsere Berechungen:

• Die Gr¨ oße der einzelnen Marktsegmente k ∈ M : N k

• Die Reservationspreise der einzelnen Marktsegmente k ∈ M f¨ ur alle m¨ oglichen B¨ undel i ∈ L: R ki

• Die Kosten des Monopolisten, um ein B¨ undel i ∈ L dem Marktsegment k ∈ M anzubieten: c ^ki Als Entscheidungsvariablen verwenden wir:

• Die Preise f¨ ur die einzelnen B¨ undel i ∈ L: p i

• Die Konsumentenrente f¨ ur jedes Marktsegment k ∈ M : s k

• Eine bin¨ are Entscheidungsvariable θ ki ∈ {0, 1}, die genau dann den Wert 1 hat, wenn das Marktsegment k ∈ M das B¨ undel i ∈ L w¨ ahlt. Dar¨ uber hinaus gibt es noch folgende Hilfsvariablen:

• Die Konsumentenrente f¨ ur das Marktsegment k, wenn dieses sich f¨ ur B¨ undel i entscheidet: s ki

• Der Preis p ki , zu dem B¨ undel i dem Segment k angeboten wird; wegen des Verbotes des Preisdiskriminierung muß nat¨ urlich f¨ ur die optimale L¨ osung p k1i0 = p k2i0 gelten, wenn beide Segmente das gleich gleiche B¨ undel i ⁰ w¨ ahlen, die scheinbar m¨ oglichen unterschiedlichen Preise dienen nur der Modellierung

• Den Deckungsbeitrag pro an Marktsegment k abgesetztes B¨ undel i: z ki

12

3.3 Gleichungen

Mit diesen Variablen und Parametern k¨ onnen wir nun das gemischt-lineare-Programm (GLP) formulieren. Die einzelnen (Un-)Gleichungen werden der einfacheren Interpretation wegen dabei nicht unbedingt in Standardform wiedergeben - das komplette GLP in Standardform ist im Anhang A (ab Seite 29ff) aufgelistet.

Ziel des Monopolisten ist es, den erzielten Gesamtdeckungsbeitrag zu maximieren: hierzu summieren wir einfach die Deckungsbeitr¨ age ¨ uber alle Marktsegmente k und alle B¨ undel i auf und gewichten sie mit der Gr¨ oße des jeweiligen Marktsegmentes, was zu folgender Zielfunktion f¨ uhrt:

Die Nutzenmaximierung der einzelnen Konsumenten formulieren wie folgt: s k ≥ R ki − p i (3.2)

Der Nutzen soll also mindestens der Konsumentenrente entsprechen. Um die Preissubadditivit¨ at zu erzwingen, berechnen wir f¨ ur jedes B¨ undel i die Indexmengen I, f¨ ur die gilt:

Mit Hilfe dieser Mengen I k¨ onnen wir dann die eigentliche Bedingung formulieren:

Befinden sich in zwei B¨ undeln j 1 , j 2 ∈ I gleiche Komponenten (also B j1 ∩ B j2 = ∅), so fallen die eine Einheit ¨ ubersteigenden Komponenten unter den

Tisch, da in einer (Vereinigungs-) Menge Elemente nicht mehrfach vorhanden sein k¨ onnen. Dies deckt sich mit der Pr¨ amisse, daß die zweite Mengeneinheit eines Gutes dem Konsumenten keinen Nutzen stiftet. Fordern wir zus¨ atzlich f¨ ur die Menge I B i0 ∩ B i1 = ∅ ∀i 0 , i 1 ∈ I, i 0 = i 1 (3.5)

so k¨ onnen wir eine Menge an redundanten Ungleichungen vermeiden. Ist n¨ amlich z.B. p {a,b} > p {a} + p {b} (3.6)

verboten, so folgt hieraus unmittelbar auch ein Verbot von

da bei dieser Gleichung der letzte Summand auf der rechten Seite gr¨ oßergleich dem bei der vorherigen Gleichung ist.

Die n¨ achsten beiden Ungleichungen verhindern die oben beschriebene Preisdiskrimierung:

Die Verwendung von ˜ R entspricht hierbei dem sog. Big M-Trick zum Ausschalten von Ungleichungen in bestimmten F¨ allen. Da p ki nie den gr¨ oßten Reservationspreis ˜ R ¨ ubersteigen kann (siehe hierzu die Erkl¨ arungen in Kapitel 2.2 auf Seite 5), erf¨ ullt p ki = 0 dann diese Ungleichung. Weiter definieren wir noch die St¨ uckdeckungsbeitr¨ age z ki = p ki − c ki · θ ki (3.10)

sowie die Konsumentenrente pro Segment und B¨ undel: s ki = R ki · θ ki − p ki (3.11)

Letztere addieren wir segmentweise:

Um nur den Kauf eines einzelnen Gutes pro Marktsegment zu erlauben, fordern wir noch:

Da f¨ ur die einzelnen Kaufentscheidungen

θ ki ∈ {0, 1} (3.14)

gilt, kann so nur ein θ ki0 pro Segment k gesetzt sein. Zum Schluß noch einige Nichtnegativit¨ atsbedingungen: p i , p ki , s ki ≥ 0 (3.15)

3.4 Implementierung

Die konkrete Formulierung aller Gleichungen f¨ ur das Optimal-Bundle-Pricing-Problem ist schon f¨ ur kleine (z.B. n = 2, M = 2) recht m¨ uhsam. Wir hatten deshalb im Rahmen des Seminars die Aufgabe, ein Programm zur Automatisierung dieses Vorgangs zu entwicklen.

14

Hieraus ist die Java-Applikation BundleOpt entstanden. Ausgew¨ ahlte Aspekte bei der Implementierung werden im n¨ achsten Kapitel skizziert.

15

Kapitel 4

Entwicklung von

BundleOpt

4.1 Wahl der Programmiersprache

Wir haben uns f¨ ur die Programmiersprache Java entschieden, vor allem weil eine graphische Benutzeroberfl¨ ache zu implementieren war, und mit der Java- Bibliothek Swing einesehr leistungsf¨ ahige - von der Entwicklungsumgebung unabh¨ angige Bibliothek - zur Verf¨ ugung steht. Zudem stehen diese Produkte kostenlos zur Verf¨ ugung.

Zwar wird oft die schwache Performanz von Java - besonders wenn große Datenmengen bewegt werden m¨ ussen, wenn also h¨ aufig dynamisch Speicher an-gefordert und mittels automatischer Garbage Collection wieder frei geben wird - beklagt, dies spielt aber f¨ ur unsere Zwecke keine Rolle, schon alleine deswegen, weil die eigentlichen numerischen Berechnungen (die L¨ osung des GLP mittels Simplex-/Branch-and-Bound-Algorithmus) von externen Programmen (n¨ amlich Ampl und den damit angesteuerten Solvern, siehe n¨ achster Abschnitt) vorgenommen wird. BundleOpt erstellt lediglich eine Batchdatei im Ampl-Format mit dem GLP (das allerdings schon f¨ ur kleine Probleminstanzen sehr umfangreich werden kann), ruft Ampl auf und parst danach die Datei mit der L¨ osung, um diese darzustellen

4.2 Wahl des Solvers

Zum L¨ osen der GLP setzen wir Ampl ([12]) ein: dabei handelt es sich um einen Interpreter f¨ ur mit der Modellierungssprache Ampl ¹ formulierte Optimierungsprobleme. Ampl l¨ ost die Probleme aber nicht selbst, sondern ruft einen der kompatiblen Solver auf, z.B. Cplex, Minos oder LpSolve. Dank dieses Vorgehens muß man ein Problem nur einmal mit Ampl formulieren und kann es dann mit verschiedenen Solvern l¨ osen. Aufgrund der verschiedenen Implementierungen k¨ onnen die Genauigkeiten der Ergebnisse von Solver zu Solver wegen

¹ Ampl ist ein Akronym f¨ ur A Mathematical Programming Language

16

Rundungsfehlern u.¨ a. doch erhebliche Unterschiede aufweisen. Der AMPL-Interpreter selbst ist ein einfaches Kommandozeilentool ² , welches f¨ ur alle wichtigen Rechnerplattformen verf¨ ugbar ist. Man kann mit Ampl im Dialogbetrieb arbeiten, es ist aber auch m¨ oglich, alle Befehle in einer Batch-Datei zu speichern und Ampl dann mit dem Shell-Kommando

ampl batchdatei.txt

aufzurufen. Ein vollst¨ andiges Beispiel einer solchen Batchdatei ist in Anhang B zu finden (Seite 32ff). Mittels einer in dieser Batch-Dabei spezifizierten Option kann man AMPL auch dazu veranlassen, alle Ausgaben in eine Log-Datei zu schreiben (vgl. Anhang B.2, Seite 35ff f¨ ur ein Beispiel). Der Aufruf eines Shell-Kommandos mit Java ist dank der Klasse Runtime denkbar einfach: Process p;

p = Runtime.getRuntime().exec( "ampl " + amplBatchFileName );

Ein Runtime-Objekt repr¨ asentiert die aktuelle Laufzeitumgebung; da es hiervon nur eine Instanz geben kann, ist diese Klasse als Singleton implementiert. Der so erzeugte Ampl-Prozess schreibt seine Ausgaben auch auf die Standard-Ausgabe stdout, was wir mit folgenden Codesegment auslesen, da dieser Prozess sonst abst¨ urtzt: BufferedReader in = new BufferedReader( new InputStreamReader ( p.getInputStream() ) ); while ( (str = in.readLine() ) != null) {

//System.out.println( str ); }

Durch dieses Vorgehen wird auch sichergestellt, daß der prim¨ are BundleOpt- Prozessauf den Ampl-Subprozess wartet.

Da wir Ampl seine Ausgaben in eine Log-Datei schreiben lassen, verarbeiten wir die so eingelesen Zeilen nicht wirklich. Das Vorgehen ¨ uber die Log-Datei

erschien uns wegen der einfacheren Fehlersuche vorteilhaft, da man so das Ergebnis der Berechnungen als Text-Datei vorliegen hat und nicht erst umst¨ andlich mit dem Java-Debugger jdb abfragen muß.

Das Zusammenspiel zwischen den verwendeten Komponenten wird in Zeichnung 4.1 noch einmal verdeutlicht:

1. BundleOpt erstellt die Batch-Datei mit dem Modell/den Daten

2. BundleOpt weist Ampl an, die Batch-Datei auszuf¨ uhren

² mit Ampl Plus steht auch ein Windows-Programm zur Verf¨ ugung, das allerdings nicht zum kostlosen Download im Internet bereitsteht

17

3. Ampl liest die Batch-Datei ein

4. Ampl ruft den in der Batch-Datei spezifizierten Solver auf (z.B. Cplex)

5. Das Ergebnis der Berechnung wird in die entsprechende Datei geschrieben

6. BundleOpt erh¨ alt die R¨ uckmeldung ¨ uber die Beendigung der Berechnung

7. BundleOpt parst die Ergebnis-Datei und visualisiert die Ergebnisse

4.3 Alternative Vorgehensweisen

Grunds¨ atzlich w¨ are es auch m¨ oglich gewesen, einen in Java implementierten LP-Solver zu verwenden. Wir haben hier den Solver aus den OR-Objects der Firma DRA Systems und die Java-Portierung von LPSolve 2.0 in die engere Auswahl genommen.

Der OR-Objects-Solver kann leider keine GLP l¨ osen, auch wenn die Schnittstelle die Formulierung solcher zulassen w¨ urde. Ansonsten ist aber eine kosten-

18

freie Version verf¨ ugbar, die auch keine Beschr¨ ankung bzgl. der Anzahl der Variablen und/oder Constraints kennt.

LPSolve von Michel Berkelaar ist ein Solver unter der GNU Lesser General Public License, es ist also der vollst¨ andige Quellcode vorhanden, man hat sogar das ausdr¨ uckliche Recht, ¨ Anderungen vorzunehmen und den so (hoffentlich) verbesserten Code weiter zu verbreiten. Im Gegensatz zu der herk¨ ommlichen GNU Gerneral Public License darf eine solche Bibliothek sogar unter bestimmten Bedingungn in kommerzielle Anwendung eingebaut werden. LPSolve kann auch GLP l¨ osen, es gibt keine Beschr¨ ankungen hinsichtlich der Problemgr¨ oße. Leider erwies sich diese Bibliothek als sehr instabil. Zudem ist die Programmschnittstelle sehr unkomfortabel und bei der Programmierung wurde gegen sonst ubliche Konventionen verstoßen. ¨

Weiter haben wir in Betracht gezogen, eine Solver-Bibliothek f¨ ur C/C++- Programmezu verwenden. Dank dem Java Native Interface (JNI) kann man aus Java-Programmen heraus auch C/C++-Programme und Bibliotheken aufrufen. Dies ist allerdings programmiertechnisch mit erheblichem Aufwand verbunden ([9]), zudem w¨ are hierbei auch die plattformunabh¨ angig verloren gegangen, da C/C++-Programme meist nicht so ohne weiteres portierbar sind.

4.4 Grafische Benutzeroberfl¨ ache

Bei der Implementierung von Grafischen Benutzeroberfl¨ achen in Java stehen grunds¨ atzlich die beiden Bibliotheken Awt (Abstract Window Toolkit) und Swing zu Verf¨ ugung (Vgl. auch [10]).

Awt stellt sog. schwergewichtige Komponenten (Widgets) bereit: es wird also auf die vom jeweiligen Betriebssystem gebotenen Komponenten (Buttons, Labels, . . . ) zur¨ uckgegriffen. Da Java und damit auch awt-Programme unter verschiedenen Plattformen (Windows, Linux, Unix, Mac, . . . ) ohne Neu¨ ubersetzung lauff¨ ahig sein sollen, muß sich die awt-Bibliothek auf die Komponenten beschr¨ anken, die auf allen unterst¨ utzen Plattformen zur Verf¨ ugung stehen - diese Schnittmenge ist nat¨ urlich recht eingeschr¨ ankt. Weiter tritt noch das Problem auf, daß gleiche Komponenten auf verschiedenen Plattformen leicht unterschiedliches Aussehen haben, so daß es bei Portierungen zu unsch¨ onen ¨ Uberraschungen kommen kann.

Die neuere Swing-Klassen gehen daher einen anderen Weg: alle Komponenten werden von dieser Bibliothek selbst gezeichnet, es wird also nicht auf schon vom jeweiligen Betriebssystem zur Verf¨ ugung gestellte Komponenten zur¨ uck gegriffen. Dadurch ist gew¨ ahrleistet, daß ein Programm auf allen Plattformen gleich aussieht. Zudem ist so der Art der Komponenten keine Grenze gesetzt, Swing stellt eine wesentlich m¨ achtigere und besser konfigurierbare Palette von Komponenten zur Verf¨ ugung, weshalb wir uns auch f¨ ur diese Library entschieden haben.

Im praktischen Einsatz wird man wohl mehrere Datens¨ atze haben, diese und die entsprechenden Ergebnisse auf einen Blick miteinander vergleichen wol-

19

len. Wir haben deshalb BundleOpt als sog. MDI (Multi Document Interface)- Applikationerstellt: hierbei werden von einem ¨ ubergeordneten Hauptfenster im

Prinzip beliebig viele Dokumentenfenster verwaltet (siehe 4.2). Wir haben jeweils einen Fenstertyp f¨ ur die Eingabedaten und einen f¨ ur die Ergebnisse der Berechnung, wobei jedes dieser Unterfenster wiederum einen eigenen Kartenreiter hat, mit dem zwischen den verschiedenen Ansichten (eine f¨ ur die Eingabe der Reservationspreise, eine f¨ ur die Eingabe der Kostenstruktur, . . . ) umgeschaltet werden kann.

Programmtechnisch betrachtet handelt es sich bei dem Hauptfenster um eine Instanz der Klasse JFrame - diese enth¨ alt eine Instanz der Klasse JDesktopPane, welche die eigentliche Arbeitsfl¨ ache f¨ ur die Darstellung der Unterfenster ist. Die Unterfenster selbst sind von JInternalFrame abgeleitet.

4.5 Programmier-Schnittstellen

Das Klassendesign wurde so festgelegt, daß eine getrennte Entwicklung des grafischen Frontends f¨ ur die Eingabe, Visualisierung und Verwaltung der Ein/Ausgabedaten und des eigentlichen Algorithmus zum Formulieren, L¨ osen und Auswerten m¨ oglich war. Der Datenaustausch zwischen diesen beiden Teilen erfolgt ausschließlich ¨ uber Objekte der beiden Klassen InputData und OutputData. Die Klasse InputData enth¨ alt Member-Variablen mit den Eingangs-Parametern f¨ ur den Algorithmus sowie zus¨ atzlichen Steueranweisungen:

package bundleOpt.algo;

public class InputData implements java.io.Serializable {

public String fileName=null; public static final int MIXED_INTEGER_MODE = 0; public static final int LP_RELAX_MODE_WITH_TIGHTENING_CONSTRAINTS = 1;

public static final int LP_RELAX_MODE_WITHOUT_TIGHTENING_CONSTRAINTS = 2; public String problemName;

public int mode; // one of the three constants above

public int _M,

public int[] _N; // N[k] is number of customers in segment k public double[][] _R, // R[k][i]: Reservation-Price of segment k for bundle i

// Constructor

public InputData (int n, double[][] R, double[][] c, int[] N) // ... public String toString () // ... };

Die Klasse OutputData enth¨ alt das geparste Ergebnis der Berechnungen zur Darstellung durch das GUI: package bundleOpt.algo;

public class OutputData implements java.io.Serializable {

public double[][] _pAux, _sAux, _zAux; public double[] _p, _s;

public double[][] _theta; // ’double’ because of LP-Relax public int[][] _bundles; public String _message; public static final int OPTIMAL_SOLUTION_FOUND = 0;

public static final int NO_OPTIMAL_SOLUTION_FOUND = 1; public static final int SOLVER_ERROR = 2; // ampl not found public int error_code; };

Beide Klassen implementieren das Marker-Interface ³ Serializable, um eine einfache Speicherung dieser Objekte zu erm¨ oglichen:

// ...

ObjectOutputStream s = new ObjectOutputStream( new FileOutputStream( strFileName) ); s.writeObject(serialObjekt); s.flush(); s.close(); // ...

³ Ein sog. Marker-Interface hat keinerlei Konstanten oder (abstrakte) Methoden, deren Implementierung erforderlich w¨ are; es dient lediglich der Markierung der Objekte einer Klasse

22

Das Laden so gespeichert Objekte funktionert analog unter Verwendung der entsprechend Klassen f¨ ur Input-Streams. Die zu serialisierenden Objekte d¨ urfen nat¨ urlich nur Member-Variablen vom Typ generischer Klassen aufweisen oder von ebenfalls serialisierbaren Klassen.

Ein Nachteil der Serialisierung sollte allerdings nicht verschwiegen werden: hat man serialisierte Objekte vorliegen und ¨ andert die zugrundeliegende Klasse (f¨ ugt also z.B. eine Membervariable hinzu), so kann man auf die gespeicherten Daten nicht mehr ohne weiteres zugreifen.

Alternativ w¨ are noch eine Speicherung der Daten mittels XML denkbar gewesen: damit w¨ aren die Daten auch f¨ ur Menschen lesbar und problemlos von anderen Applikationen - z.B. zur Aufbereitung f¨ ur html-Darstellungen - nutzbar.

4.6 Sensitivit¨ atsanalyse

Bei der Modellierung von Optimierungsproblemen beruhen die verwendeten Eingangsparameter oftmals nur auf ungenauen Sch¨ atzungen - dies trifft im besonderen Maße auch auf das vorliegende Programm zu (vgl. dazu 5.1 ab Seite 25). Es ist deshalb sinnvoll zu untersuchen, in welchem Maße die L¨ osung von einzelnen Eingangsparametern abh¨ angig ist; hierzu dient die sog. Sensitivit¨ atsanalyse. BundleOpt kann eine einfache Sensitivit¨ atsanalyse f¨ ur alle L · M Reservationspreise durchf¨ uhren (siehe Abbildung 4.3): es wird hierbei jeweils sukzessive ein Reservationspreis um 10 % erh¨ oht/erniedrigt, um dann den neuen Zielfunktionswert mit sonst unver¨ anderten Daten zu berechnen. Ergibt sich hierbei z.B., daß ein h¨ oherer Reservationspreis f¨ ur ein bestimmtes B¨ undel innerhalb eines Marktsegments zu einem deutlich h¨ oheren Gesamtergebnis f¨ uhren w¨ urde, kann man evtl. Werbemaßnahmen in Betracht ziehen, um den Reservationspreis f¨ ur das betreffende Segment-B¨ undel-Paar tats¨ achlich zu erh¨ ohen.

Abbildung 4.3: Screenshot: Ausgabe-Dialog f¨ ur Sensitivit¨ ats-Analyse Wir haben noch eine zweite Form der Sensitivit¨ ats-Analyse implementiert: dabei werden aus allen Reservationspreisen mehrmals jeweils zwei zuf¨ allig aus-

23

gesucht, um 10 % erh¨ oht und der sich daraus ergebende Zielfunktionswert berechnet (vgl. Abbildung 4.4).

Abbildung 4.4: Screenshot: Ausgabe-Dialog f¨ ur multiple Sensitivit¨ ats-Analyse

24

Kapitel 5

Praktischer Einsatz

Wir haben die Korrektheit von BundleOpt anhand einiger einfacher 2-G¨ uter-Beispiele verifiziert (z.B. das Zahlenbeispiel in Kapitel 2.2 ab Seite 5, die Beispiele aus [2] und [15]). F¨ ur alle diese Beispiele ist die optimale L¨ osung auch durch manuelles Nachrechnen herleitbar.

Interessant ist dar¨ uber hinaus aber auch die Frage der Datenbeschaffung f¨ ur die praktische Anwendung.

5.1 Datenbeschaffung

Grunds¨ atzlich ben¨ otigen wir f¨ ur den Einsatz von BundleOpt folgende Daten:

• Die verschiedenen Marktsegmente

• Die Gr¨ oßen der einzelnen Marktsegmente

• Die variablen St¨ uck-Kosten, um eine ME eines B¨ undels i f¨ ur Marktsegment k zu produzieren

• Die individuellen maximalen Zahlungsbereitschaften der einzelnen Marktsegmente f¨ ur die einzelnen B¨ undel

Wir sehen uns also mit recht anspruchsvollen Informationsanforderungen konfrontiert; dem gegen¨ uber steht allerdings auch ein beachtliches Gewinnsteigerungspotential.

Die St¨ uckkosten sollten anhand der Kosten- und Leistungsrechnung einer Unternehmung recht leicht zu bestimmen sein, f¨ ur die Bestimmung der Marktsegmente kommen die herk¨ ommlichen Methoden der numerischen Taxonomie in Betracht (Clusteranalyse).

Recht problematisch ist aber die Bestimmung der Reservationspreise:

25

5.1.1 Bestimmung der individuellen Maximalpreise

Konsumentenbefragung

Die naheliegenste M¨ oglichkeit zur Bestimmung der individuellen maximalen Zahlungsbereitschaften ist nat¨ urlich die einer direkten Befragung potentieller Konsumenten. Allerdings ist dieses unter Reliabilit¨ ats- und Validit¨ atsaspekten betrachtet recht bedenklich ([7]):

• Es k¨ onnte zu taktischem Verhalten der Befragten kommen: sie nennen bewußt einen niedrigeren Preis in der Hoffnung, die zuk¨ unftige Preisfestsetzung des Anbieters in ihrem Sinne beeinflussen zu k¨ onnen

• Die direkte Frage nach der Preisbereitschaft bewirkt eine zu starke Fokusierung des Befragten auf den Preis alleine; in der Realit¨ at wird er den Preis eher im Zusammenhang mit anderen Nutzenaspekten abw¨ agen

• Aus Prestigegr¨ unden k¨ onnte ein Proband auch eine ¨ uberh¨ ohte Zahlungsbereitschaft bekunden, sie bleibt bei einer reinen Befragung ja auch ohne direkte konkrete Auswirkungen Expertenbefragung

Statt potentieller Konsumenten kann man auch eine Gruppe von ausgew¨ ahlten Experten befragen, wie hoch sie die Zahlungsbereitschaft f¨ ur ein bestimmtes Produkt sch¨ atzen, doch sind die mittels dieser Vorgehensweise gewonnen Ergebnisse genauso fragw¨ urdig. Vickrey-Auktion

Eine weitere M¨ oglichkeit stellen sog. Vickrey ¹ -Auktionen dar ([5], [6]): die Bieter schreiben hierzu gleichzeitig ihre Gebote in verdeckter Form nieder (deshalb ist diese Auktionsform auch unter Begriffen wie second-price-sealed-bid-auctions oder undercover auctions bekannt ([14])), der Zuschlag erh¨ alt der Bieter mit dem h¨ ochsten Gebot zum Preis des zweith¨ ochsten Gebot. Man kann sich leicht ¨ uberlegen, daß es f¨ ur einen Bieter i die beste Strategie ist, ein Gebot in der tats¨ achlichen H¨ ohe seiner maximalen Zahlungsbereitschaft R ⁰ i abzugeben. W¨ urde er - aus

welchen Erw¨ agungen heraus auch immer - auf die Idee kommen, ein niedrigeres Gebot R ⁻ i abzugeben (R ⁻ i < R 0

Bieter j zu einem Preis p ⁻ ∈ (R −

reit gewesen, diesen Preis zu bezahlen, h¨ atte aber trotzdem nicht den Zuschlag erhalten. Gibt er ein Gebot R + i h¨ oher als seine tats¨ achliche Zahlungsbereitschaft ab (R ⁺ i ), so muß er damit rechnen, zu einem Preis p ⁺ ∈ (, R ⁺ > R

⁰ i

Gut kaufen zu m¨ ussen, also jenseits seiner tats¨ achlichen Zahlungsbereitschaft ² . Man kann diese Form der Auktion zur Feststellung der maximalen Zahlungsbereitschaft heranziehen: die Probanden m¨ ussen sich vertraglich verpflichten, ggf. das Gut tats¨ achlich zum ermittelten Preis abzunehmen; sie werden dar¨ uber

¹ nach William Vickrey (Wirtschafts-Nobelpreis 1996)

² im ung¨ unstigsten Fall liegt das zweith¨ ochste Angebot also gerade die kleinst-m¨ ogliche

Biet-Stufe (z.B. 0,01 DM) unter R +

i

26

uber die obigen ¨ hinaus aber auch ¨ Uberlegungen unterrichtet, so daß man davon

ausgehen kann, wirklich Gebote in H¨ ohe der tats¨ achlichen Zahlungsbereitschaft zu erhalten.

Dieser Form der Reservationspreismessung ist noch recht neu, weshalb wir keine f¨ ur unseren Zwecke brauchbaren Daten in der Literatur finden konnten (in [5] selbst wird das Verfahren anhand der Versteigerung von verschiedenen Mobilfunkttrarifen unter Studenten beurteilt - die B¨ undelung von sich gegenseitig ausschließenden Komponenten macht leider keinen Sinn, ganz abgesehen von der mangelnden Information ¨ uber die variablen St¨ uckkosten). Die mittels

Vickrey-Auktion ermittelten Werte weichen auch deutlich von denen anderer Verfahren ab (die ermittelten Maximalpreise sind niedrigerer als die mittels direkter Preisbefragung festgestellten), so daß eine weitere Untersuchung dieses vielversprechenden Ansatzes notwendig erscheint. Problematisch bei diesem Verfahren ist auch, daß man reale Komponenten/B¨ undel tats¨ achlich im Verlauf der Auktion verkaufen muß, was je nach Wert dieser G¨ uter erhebliche Kosten verursachen kann. Conjoint-Analyse

In [7] wird die Befragung mittels Conjoint-Analyse f¨ ur die vorliegende Problemstellung als am geeignetsten empfohlen.

Unter dem Begriff der Conjoint Analyse werden in der Marketing-Forschung eine ganze Gruppe von Methoden zusammengefaßt, mit deren Hilfe Nutzenbewertungen von durch mehreren Attributen (Farbe, Form, Gestalt, . . . ) sich auszeichnende Objekte (meist fiktive Neuprodukte, sog. Stimuli oder Konzepte) auf Nutzenbeitr¨ age einzelner Merkmalsauspr¨ agungen zur¨ uckgef¨ uhrt werden k¨ onnen. Eine dieser Merkmalsauspr¨ agungen kann auch der Preis sein, so daß mittels einer speziellen Form der Conjoint-Analyse die maximale Zahlungsbereitschaft ermittelt werden kann.

5.2 Rechenaufwand

Im wesentlichen basieren die Berechnungen des implementierten Verfahren auf der L¨ osung eines Linearen Programms, wobei erfahrungsgem¨ aß die Anzahl der Rechenschritte etwa linear mit der Zahl der Nebenbedingungen und sogar etwas geringer als linear mit der Zahl der Entscheidungsvariablen ansteigt ([8], Seite 160).

Im Modell von Hanson/Martin w¨ achst die Anzahl der betrachteten B¨ undel in Abh¨ angigkeit von der Anzahl der Einzelkomponenten allerdings exponentiell: L = 2 ⁿ − 1

Da wir f¨ ur jedes B¨ undel i ∈ L und f¨ ur jedes Marktsegment k eine eigene Entscheidungsvariable θ ki ben¨ otigen, haben wir insgesamt einen exponentiell wachsenden Rechenaufwand. Bei z.B. n = 20 Komponenten - eine f¨ ur die praktische Anwendung sicher nicht zu hoch gegriffene Zahl - h¨ atten wir schon ¨ uber

1 Million m¨ oglicher B¨ undel zu betrachten.

27

Hanson/Martin erw¨ ahnen, daß man Probleme mit etwa 4 Komponenten und etwa 10 Segmenten mit vertretbaren Zeitaufwand (wenige Minuten Rechenzeit) l¨ osen kann. Da uns f¨ ur Ampl/Cplex nur eine eingeschr¨ ankt lauff¨ ahige Studenten-Version zur Verf¨ ugung stand, konnten wir leider die Leistungsgrenze f¨ ur einen heutigen PC nicht ermitteln, wir sch¨ atzen aber, daß diese bei etwa 6 Komponenten liegen d¨ urfte.

In der Regel d¨ urften die f¨ ur eine praktische Anwendung vorliegenden Modellparameter auch eher Sch¨ atzungen sein, so daß man auf eine mehrfache L¨ osung des Problems mit leicht modifizieren Eingangsdaten (Sensitivit¨ atsanalyse) nicht verzichten wollen wird und deshalb h¨ ochstens eine Rechenzeit von wenigen Minuten in Kauf nehmen wird.

5.3 Ausblick

In [1] wird noch eine modifizierte Variante des hier vorgestellen Algorithmuses beschrieben: hierbei versucht man den mit der Anzahl der Einzelkomponenten exponentiell wachsenden Rechenaufwand dadurch zu beschr¨ anken, daß man nur eine Teilmenge E aller m¨ oglichen B¨ undel betrachtet: E ⊆ {1, . . . , L}

Man l¨ ost das etwas umformulierte Problem dann f¨ ur die Menge der B¨ undel i ∈ E und ver¨ andert die Menge E anhand zweier weiterer als LP formulierter Unterprobleme.

Wie man allerdings den Ausgangszustand der Menge E bestimmen soll, wird nicht erw¨ ahnt, denkbar w¨ are hier aber eine reine Zufallsauswahl oder die Anwendung von Verfahren wie der Best-In oder Part-Worth-Based-Greedy-Heuristik. Dieses Verfahren ist jedoch nicht so allgemein formuliert wie das von uns implementierte: die Reservationspreise und Grenzkosten m¨ ussen additiv sein, zudem muß eine der Komponenten einen erheblich h¨ oheren Nutzenbeitrag als die restlichen stiften; diese Hauptkomponente k¨ onnte z.B. ein PKW sein, die Nebenkomponenten sind die verschiedenen optionalen Sonderausstattungsmerkmale (Klima-Anlage, Automatik, . . . ).

28

Anhang A

Optimal

Bundle-Pricing-Problem als

GLP/LP

Im folgenden geben wir das komplette GLP/LP zum direkten Optimal Bundle-Pricing-Problem aus [1] in leicht modifizierter Form wieder (Seite 159, Gleichungen (1) bis (11)), so wie wir es bei der Implementierung vorausgesetzt haben. Weiter sind die einzelnen Nebenbedingungen der ¨ Ubersichtlichkeit wegen in standardisierter Form dargestellt, also

≤

a i1 x 1 + a i2 x 2 + . . . + a in x n b i

≥

f¨ ur Ungleichungen bzw. a i1 x 1 + a i2 x 2 + . . . + a in x n = b ⁱ f¨ ur Gleichungen.

Die verwendeten Variablen im Einzelnen sind in Kapitel 3.2 (Seite 12) erkl¨ art, dort wird auch auf die Bedeutung der einzelnen Gleichungen eingegangen.

Zielfunktion

Konsumentenrente (Consumer surpluss)

Preis-Subadditivit¨ at (Price subadditivity)

wobei die Indexmenge I so zu bestimmen ist, daß gilt:

Einzelpreis I (Single Price Schedule)

p i − p ki + ˜ Rθ ki ≤ ˜ R (A.5)

mit

Einzelpreis II

p ki − p i ≤ 0 i = 1, . . . , L k = 1, . . . , M (A.7) Einzelkauf I (Single purchase)

z ki − p ki + c ki θ ki = 0 i = 1, . . . , L k = 1, . . . , M (A.8) Einzelkauf II

s ki − R ki θki + p ki = 0 i = 1, . . . , L k = 1, . . . , M (A.9) Einzelkauf III

Einzelkauf IV

Vorzeichenbeschr¨ ankungen

p i , p ki , s ki ≥ 0 i = 1, . . . , L k = 1, . . . , M (A.12) Ganzzahligkeit

A.1 LP-Relaxation

Will man die LP-Relaxation dieses GLP l¨ osen (also Bedingung A.13 durch 0 ≤ θ ki ≤ 1

ersetzen) um eine obere Schranke f¨ ur den Zielfunktionswert zu erhalten, so sollte man noch folgende zus¨ atzliche Nebenbedingungen (tightening constraints) verwenden:

^L −s k + (R ki θ ji − p ji ) ≤ 0 k = 1, . . . , L j = 1, . . . , M (A.14) i=1

Die LP-Relaxation wird hierzu zu einer sch¨ arferen oberen Schranke. F¨ ur das GLP sind diese Bedingungen jedoch redundant, sollte also dann nicht verwendet werden, da sie nur zu unn¨ otigem Rechenaufwand f¨ uhren.

31

Anhang B

Gemischt-Lineares

Programm im

AMPL-Format

B.1 Eingabedatei

Das folgende Listing stellt eine vollst¨ andige von BundleOpt erzeugte Batch-Datei f¨ ur AMPL dar. Nach der Definition der Variablen und Gleichungen schließt sich ein Teil mit Steueranweisungen an (Wahl des Solvers, Umleitung der Ausgabe in eine Log-Datei). Einleitend werden in Form von Kommentarzeilen die Eingangsparameter f¨ ur das Modell noch einmal aufgef¨ uhrt. Besonders wichtig ist hierbei die Zuordnung der Bundle-Indices zu den einzelnen Komponenten-Teilmengen. Intern erzeugt BundleOpt diese durch das Hochz¨ ahlen eines bin¨ aren Index-Vektors. F¨ ur n = 3 (mit den Komponenten {a, b, c}) und dem Vektor (γ a , γ b , γ c ) sieht dies wie folgt aus: i = 1 : (1, 0, 0) ⇒ B 1 = {a} i = 2 : (0, 1, 0) ⇒ B 2 = {b} i = 3 : (1, 1, 0) ⇒ B 3 = {a, b} i = 4 : (0, 0, 1) ⇒ B 4 = {c} . . .

Dadurch erhalten wir eine eindeutige Reihenfolge der einzelnen Teilmengen, auch wenn man vielleicht f¨ ur die ersten n B¨ undelmengen erwarten w¨ urde, daß diese nur aus der entsprechenden Einzelkomponente besteht (B 1 = {a}, B 2 = {b}, B 3 = {c}, . . . ). # Input-File for ampl, created by BundleOpt # Time of creation: Wed Jun 27 01:50:09 CEST 2001 # Problem-name: easyExample # Number of components: 2 # Number of bundles: 3

32

# Number of market-segments: 2 # Number of consumers in market-segment no 1 : 1 # Number of consumers in market-segment no 2 : 1 # Reservation-Prices for market-segment 1 : 5.0 4.0 9.0 # Reservation-Prices for market-segment 2 : 6.5 1.0 7.5 # Costs for suppling bundles to market-segment 1 : 0.0 0.0 0.0 # Costs for suppling bundles to market-segment 2 : 0.0 0.0 0.0

# Bundle No 1: # Bundle No 2: # Bundle No 3: # Solve-Mode: Mixed-Integer

var p1; var p2; var p3;

var s1; var s2;

var z1_1; var z1_2; var z1_3; var z2_1; var z2_2; var z2_3; var p1_1; var p1_2; var p1_3; var p2_1; var p2_2; var p2_3; var s1_1; var s1_2; var s1_3; var s2_1; var s2_2; var s2_3; var t1_0 binary; var t1_1 binary; var t1_2 binary; var t1_3 binary; var t2_0 binary; var t2_1 binary; var t2_2 binary; var t2_3 binary;

maximize profit: 1*z1_1 + 1*z1_2 + 1*z1_3 + 1*z2_1 + 1*z2_2 + 1*z2_3; # Consumer surplus (2) subject to ConsumerSurplus1: p1 + s1 >= 5.0; subject to ConsumerSurplus2: p2 + s1 >= 4.0; subject to ConsumerSurplus3: p3 + s1 >= 9.0; subject to ConsumerSurplus4: p1 + s2 >= 6.5; subject to ConsumerSurplus5: p2 + s2 >= 1.0; subject to ConsumerSurplus6: p3 + s2 >= 7.5; # Price subaddivity (3)

subject to PriceSubadditivity1: p3 - p1 - p2 <= 0; # Single Price Schedule I (4)

subject to SinglePriceScheduleI1: p1 + 9.0*t1_1 - p1_1 <= 9.0; subject to SinglePriceScheduleI2: p2 + 9.0*t1_2 - p1_2 <= 9.0; subject to SinglePriceScheduleI3: p3 + 9.0*t1_3 - p1_3 <= 9.0; subject to SinglePriceScheduleI4: p1 + 9.0*t2_1 - p2_1 <= 9.0; subject to SinglePriceScheduleI5: p2 + 9.0*t2_2 - p2_2 <= 9.0; subject to SinglePriceScheduleI6: p3 + 9.0*t2_3 - p2_3 <= 9.0; # Single Price Schedule II (5)

33

subject to SinglePriceScheduleII1: p1_1 - p1 <= 0; subject to SinglePriceScheduleII2: p1_2 - p2 <= 0; subject to SinglePriceScheduleII3: p1_3 - p3 <= 0; subject to SinglePriceScheduleII4: p2_1 - p1 <= 0; subject to SinglePriceScheduleII5: p2_2 - p2 <= 0; subject to SinglePriceScheduleII6: p2_3 - p3 <= 0; # Single purchase I (7)

subject to SinglePurchaseI1: z1_1 - p1_1 + 0.0 * t1_1 = 0; subject to SinglePurchaseI2: z1_2 - p1_2 + 0.0 * t1_2 = 0; subject to SinglePurchaseI3: z1_3 - p1_3 + 0.0 * t1_3 = 0; subject to SinglePurchaseI4: z2_1 - p2_1 + 0.0 * t2_1 = 0; subject to SinglePurchaseI5: z2_2 - p2_2 + 0.0 * t2_2 = 0; subject to SinglePurchaseI6: z2_3 - p2_3 + 0.0 * t2_3 = 0; # Single purchase II (8)

subject to SinglePurchaseII1: s1_1 - 5.0 * t1_1 + p1_1 = 0; subject to SinglePurchaseII2: s1_2 - 4.0 * t1_2 + p1_2 = 0; subject to SinglePurchaseII3: s1_3 - 9.0 * t1_3 + p1_3 = 0; subject to SinglePurchaseII4: s2_1 - 6.5 * t2_1 + p2_1 = 0; subject to SinglePurchaseII5: s2_2 - 1.0 * t2_2 + p2_2 = 0; subject to SinglePurchaseII6: s2_3 - 7.5 * t2_3 + p2_3 = 0; # Single purchase III (9)

subject to SinglePurchaseIII1: s1_1 + s1_2 + s1_3 - s1 = 0; subject to SinglePurchaseIII2: s2_1 + s2_2 + s2_3 - s2 = 0; # Single purchaseIV (10)

subject to SinglePurchaseIV1: t1_0 + t1_1 + t1_2 + t1_3 = 1; subject to SinglePurchaseIV2: t2_0 + t2_1 + t2_2 + t2_3 = 1; # Not-Negative-Constraints (11) subject to NotNegative1: p1 >= 0; subject to NotNegative2: p2 >= 0; subject to NotNegative3: p3 >= 0; subject to NotNegative4: p1_1 >= 0; subject to NotNegative5: p1_2 >= 0; subject to NotNegative6: p1_3 >= 0; subject to NotNegative7: p2_1 >= 0; subject to NotNegative8: p2_2 >= 0; subject to NotNegative9: p2_3 >= 0; subject to NotNegative10: s1_1 >= 0; subject to NotNegative11: s1_2 >= 0; subject to NotNegative12: s1_3 >= 0; subject to NotNegative13: s2_1 >= 0; subject to NotNegative14: s2_2 >= 0; subject to NotNegative15: s2_3 >= 0;

34

# --------- solver-commands -------------option solver cplex; solve;

option log_file ’easyExample.sol.txt’; display solve_message; print ’Decision-Variables’; display p1, p2, p3, s1, s2,

t1_0, t1_1, t1_2, t1_3, t2_0, t2_1, t2_2, t2_3; print ’Aux-Variables’; display z1_1, z1_2, z1_3, z2_1, z2_2, z2_3, s1_1, s1_2, s1_3, s2_1, s2_2, s2_3, p1_1, p1_2, p1_3, p2_1, p2_2, p2_3; print ’Wed Jun 27 01:50:09 CEST 2001’;

Damit die Bezeichner der zweidimensionalen Variablen eindeutig sind, m¨ ussen die beiden Indices durch Underscores (_) getrennt sein, z.B. p1_11 f¨ ur Segment k = 1, B¨ undel i = 11 - p111 hingegen w¨ are nicht eindeutig, es k¨ onnte auch Segment k = 11, B¨ undel i = 1 gemeint sein.

B.2 Ausgabedatei

AMPL legt das Ergebnis der Berechnungen in der Datei bundle1.sol.txt ab, f¨ ur die hier betrachtete Probleminstanz sieht diese wie folgt aus: solve_message = ’CPLEX 7.0.0: optimal integer solution; objective 15.5\ 18 MIP simplex iterations\ 0 branch-and-bound nodes’ Decision-Variables p1 = 6.5 p2 = 4 p3 = 9 s1 = 0 s2 = 0 t1_0 = 0 t1_1 = 0 t1_2 = 0 t1_3 = 1 t2_0 = 0 t2_1 = 1 t2_2 = 0 t2_3 = 0 Aux-Variables z1_1 = 0

35

z1_2 = 0 z1_3 = 9 z2_1 = 6.5 z2_2 = 0 z2_3 = 0 s1_1 = 0 s1_2 = 0 s1_3 = 0 s2_1 = 0 s2_2 = 0 s2_3 = 0 p1_1 = 0 p1_2 = 0 p1_3 = 9 p2_1 = 6.5 p2_2 = 0 p2_3 = 0 Wed Jun 27 01:50:09 CEST 2001

36

Anhang C

Versuchdaten von

Hanson/Martin

Wir haben einen der beiden Autoren von [1] angeschrieben und sind so in den Besitz der Quelltexte von 19 Original-Modellierungsdateien f¨ ur Versuchsreihen zur Erprobung des Algorithmuses gekommen.

Die Modelle sind in LINGO formuliert, aber auch ohne Kenntnisse dieser Sprache kann man die ben¨ otigten Eingangsparameter ablesen (Segmentgr¨ oßen, Reservationspreise und St¨ uckkosten).

Leider liegen uns keine Angaben dar¨ uber vor, von welcher Gestalt die 4 betrachteten Komponenten (A, B, C, D) sind, laut der Beschreibung in [1] kann allerdings davon ausgegangen werden, daß es sich dabei um folgende vier Dienstleistungen handelt:

• Putzservice

• Wasch-/B¨ ugelservice

• Erledigung von Lebensmitteleink¨ aufen

• Zubereiten von Mahlzeiten

Hanson/Martin haben die Reservationspreise durch direkte Befragungen in zwei MBA-Klassen (36 bzw. 38 Studenten) gewonnen (zur Kritik an dieser Vorgehensweise vgl. 26 in Kapitel 5.1.1).

MODEL:

SETS:

BUNDLE/ NULL, A, B, C, D, AB, AC, AD, BC, BD, CD, ABC, ABD, ACD, BCD, ABCD/ : P; CUST/ 1..10/ : NCUST, SU;

LINK1(CUST, BUNDLE) : PR, RESPR, MCOST, TH, RV, SL; ENDSETS

MAX = @SUM( LINK1(K,J) | K#LE# NUMCUST #AND# (J #LE# NUMPROD #AND# J #GE# 2) : NCUST(K)*RV(K,J) );

37

@FOR( CUST(K) | K #LE# NUMCUST : @SUM( BUNDLE(J) | J #LE# NUMPROD : TH(K,J) ) = 1 ); ! SELF SELECTION CONSTRAINTS; @FOR( CUST(K) | K #LE# NUMCUST : @FOR( BUNDLE(I) | I #LE# NUMPROD #AND# I #GE# 2 : SU(K) > RESPR(K,I) - P(I) + (1. - TH(K, I))*PREM ; ) ); ! TIGHTEN A BIT; @FOR( CUST(K) | K #LE# NUMCUST : @FOR( CUST(J) | J #LE# NUMCUST : SU(K) > @SUM( BUNDLE(I) | I #GE# 2 : RESPR(K,I)*TH(J,I) - PR(J,I) ); ) ); @FOR( CUST(K) | K #LE# NUMCUST : SU(K) = @SUM( LINK1(K,J) : SL(K,J) ) ; ); @FOR( CUST(K) | K #LE# NUMCUST : @FOR( BUNDLE(I) | I #LE# NUMPROD #AND# I #GE# 2: RV(K,I) = PR(K,I) - MCOST(K,I)*TH(K,I); SL(K,I) = RESPR(K,I)*TH(K,I) - PR(K,I); PR(K,I) < P(I); PR(K,I) > P(I) - BIGM*(1 - TH(K,I)); )); @FOR( CUST(K) | K #LE# NUMCUST : SL(K,NULL) = 0; ); @FOR( LINK1 :@GIN(TH);) ; ! DEFINE BIGM ; BIGM = @MAX(LINK1 : RESPR); ! SUBADDITIVITY CONSTRAINTS; P(AB) < P(A) + P(B); P(AC) < P(A) + P(C) ; P(BC) < P(B) + P(C) ; P(ABC) < P(AB) + P(C); P(ABC) < P(AC) + P(B); P(ABC) < P(BC) + P(A); P(AD) < P(A) + P(D); P(BD) < P(B) + P(D); P(CD) < P(C) + P(D); P(ABD) < P(AB) + P(D); P(ABD) < P(AD) + P(B); P(ABD) < P(BD) + P(A); P(ACD) < P(AC) + P(D); P(ACD) < P(AD) + P(C); P(ACD) < P(CD) + P(A); P(BCD) < P(BC) + P(D); P(BCD) < P(BD) + P(C); P(BCD) < P(CD) + P(B); P(ABCD) < P(AB) + P(CD); P(ABCD) < P(AC) + P(BD); P(ABCD) < P(AD) + P(BC); P(ABCD) < P(ABC) + P(D); P(ABCD) < P(ABD) + P(C); P(ABCD) < P(ACD) + P(B);

38

P(ABCD) < P(BCD) + P(A); P( 1) = 0.0; PREM = 5.0; DATA:

NCUST = 10, 1, 1, 8, 1, 10, 1, 1, 1, 4; RESPR =

0,35,21.5,14,18.2,47.5,43.7,44.5,29.5,33,26.8,59,60.50,55,43,69, 0,150,30,10,20,160,155,155,40,50,25,170,170,170,70,170, 0,50,40,30,40,90,80,90,70,80,70,120,130,120,110,160, 0,45.63,21.25,20,23.13,62.5,63.13,65,42.5,43.75,41.25,81.88,83.13 82.5,66.25,102.63 0,40,20,0,0,45,0,0,0,0,0,45,45,0,0,45 0,29,11,8.5,8.5,38,36,34.75,18,17,16,44.5,43.5,41.5,26.5,50, 0,50,60,30,30,70,80,70,70,70,80,70,80,70,70,100, 0,35,30,20,8,60,40,40,35,35,65,75,70,45,75,70, 0,45,35,20,40,65,55,70,55,70,55,60,70,70,65,80, 0,19.5,11.25,3,3,27.5,21.25,21.25,12.5,12.5,5.25,31.25,28.75, 25,21.25,33.75; MCOST =

0,25,15,20,15,35,45,40,35,30,35,55,50,60,50,70, 0,25,15,20,15,35,45,40,35,30,35,55,50,60,50,70, 0,25,15,20,15,35,45,40,35,30,35,55,50,60,50,70, 0,25,15,20,15,35,45,40,35,30,35,55,50,60,50,70, 0,25,15,20,15,35,45,40,35,30,35,55,50,60,50,70, 0,25,15,20,15,35,45,40,35,30,35,55,50,60,50,70, 0,25,15,20,15,35,45,40,35,30,35,55,50,60,50,70, 0,25,15,20,15,35,45,40,35,30,35,55,50,60,50,70, 0,25,15,20,15,35,45,40,35,30,35,55,50,60,50,70, 0,25,15,20,15,35,45,40,35,30,35,55,50,60,50,70; NUMCUST = 10; NUMPROD = 16; ENDDATA END

39

Literaturverzeichnis

Wissenschaftliche Publikationen:

[1] Ward Hanson, R. Kipp Martin, Optimal Bundle Pricing, Management Science, Volume 36 (1990 I), Seite 155-174

[2] William James Adams, Janet L. Yellen,

Commodity Bundling And The Burden Of Monopoly, Quarterly Journal of Economics, Volume 40 (1976), Seite 475-498

[3] Georg W¨ ubker,

Sonderangebotspolitik und Preisb¨ undelung, Zeitschrift f¨ ur betriebswirtschaftliche Forschung (zfbf), Band 1999 II (Jahrgang 51), Seite 693-713

[4] Thorsten Olderog, Bernd Skiera,

The Benefits Of Bundling Strategies, Schmalenbach Business-Review (sbr), April 2000, Seite 137-159

[5] Bernd Skiera, Inken Revenstorff,

Auktionen als Instrument zur Erhebung von Zahlungsbereitschaften, Zeitschrift f¨ ur betriebswirtschaftliche Forschung (zfbf), Band 1999 I (Jahrgang 51), Seite 224-242

[6] Ralf Reichwald, Michael Hermann, Florian Bieberbach, Auktionen im Internet, Das Wirtschaftsstudium (Wisu), Ausgabe 4/2000, Seite 542-552

40

B¨ ucher: [7] Georg W¨ ubker,

Preisb¨ undelung: Formen, Theorie, Messung und Umsetzung, Dissertation, Verlag Th. Gabler, 1998,

[8] Klaus Neumann, Martin Morlock,

Operations Research, Carl Hanser Verlag, 1993

Technische Literatur:

[9] Michael H¨ artefelder, Kaffee mit Vitamin C: Java-Programme mit C aufwerten c’t, Heft 20, Jahrgang 2000, Seite 242ff

[10] Gerhard Wilhelms,

Java Professionell, MITP, 1999

Nachschlagewerke:

[11] Gabler, Wirtschaftslexikon,

1984

Internet-Quellen:

[12] http://www.ampl.com

[13] http://www.ilog.com/products/cplex/

[14] http://www.undercover.ricardo.de

[15] Roman Brandtweiner,

Report Internetpricing, Methoden der Preisfindung im Internetzeitalter, Kurzfassung im Internet: http://www.symposion.de/ecommerce/ip 07.htm

41