[PYTHON] Maximieren Sie den Restaurantverkauf durch kombinierte Optimierung

Was tun?

Der Besitzer eines florierenden Restaurants voller Reservierungen bat mich, den Umsatz zu maximieren. Wir werden die Kandidaten für einen Tag nach Reservierungen fragen, welche in Ordnung sind und welche storniert werden. Solche Probleme können auch mit Kombinationsoptimierung gelöst werden.

Bei Reservierungen wird davon ausgegangen, dass die Zeit, die Anzahl der Personen und der Stückpreis wie unten angegeben bekannt sind. Es wird angenommen, dass eine Zeile einer Reservierung entspricht, nur [Anzahl der Personen] zur [Startzeit] besucht, über die Zeit der [Reservierungszeit] isst und [Einheitspreis] x [Anzahl der Personen] für die Rückgabe zahlt.

weniger
013222000
111132800
216332800
...............

Über Sitze

Das Restaurant bietet Platz für bis zu 16 Personen, einen Tisch für 2 Personen x 4 Personen und einen Tisch für 4 Personen x 2 Personen. image

Sie können auch den Zwei-Personen-Tisch und den Vier-Personen-Tisch zusammen verwenden. Es gibt 13 Möglichkeiten, sie anzuhängen (im Folgenden als Tabellengruppen bezeichnet). (Nummer ist Tabellennummer)

[0]
[1]
[2]
[3]
[4]
[5]
[0, 1]
[1, 2]
[2, 3]
[4, 5]
[0, 1, 2]
[1, 2, 3]
[0, 1, 2, 3]

Formulierung

$ \ mbox {Ziel} $ $ \ sum_i {\ sum_j {Anzahl der Personen_i Einheitspreis_i x_ {ij}}} $ Gesamtumsatz < / td> weniger Gibt an, ob i $ die Tabellengruppe $ j $ verwendet
$ \ mbox {vorbehaltlich} $ $ \ sum_j {x_ {ij}} \ le 1 ~ \ forall i $ Beliebige Tabellengruppe
$ Anzahl der Plätze in der Tabellengruppe j \ lt Wenn die Anzahl der Reservierungen i $ Anzahl der Limits beträgt
$x_{ij} = 0 ~ \forall i, j$
Es kann immer nur ein Satz gleichzeitig an derselben Tabelle reserviert werden

Die Bedeutung des Index ist jedoch wie folgt.

i: Reservierung j: Tabellengruppe s: Tabelle t: Zeit

Löse mit Python

Erstellen Sie zunächst eine Reservierungstabelle (a) mit Zufallszahlen.

python


import numpy as np, numpy.random as rnd, pandas as pd, matplotlib.pyplot as plt
from pulp import *
def addvar(lowBound=0, count=[0], *args, **kwargs):
    count[0] += 1
    return LpVariable('v%d' % count[0], lowBound=lowBound, *args, **kwargs)
rnd.seed(5)
a = pd.DataFrame([(rnd.randint(10, 17), rnd.choice([1, 2, 2, 3]),
      max(1, min(8, int(rnd.lognormal(1.2, 0.5)))), rnd.randint(10, 16) * 200)
      for _ in range(60)], columns=['Startzeit', 'Reservierungszeit', 'Anzahl der Personen', 'Stückpreis'])
cap = [2, 2, 2, 2, 4, 4] #Anzahl der Sitzplätze pro Tisch
sps = [[0], [1], [2], [3], [4], [5], [0, 1], [1, 2], [2, 3],
       [4, 5], [0, 1, 2], [1, 2, 3], [0, 1, 2, 3]] #Tabellenliste nach Tabellengruppe
ns, nt = len(sps), 19 - 10 #Anzahl der Tabellengruppen, Anzahl der Stunden

Formulieren und lösen.

python


m = LpProblem(sense=LpMaximize) #Mathematisches Modell
p = [[[] for t in range(nt)] for _ in range(6)] #Liste der Variablen nach Zeit und Tabelle
a['Var'] = [[addvar(cat=LpBinary) for j in range(ns)] for i, r in a.iterrows()]
m += lpDot(a.Anzahl der Personen* a.Stückpreis, a.Var.apply(lpSum)) #Zielfunktion(Gesamtumsatz)
for i, r in a.iterrows():
    m += lpSum(r.Var) <= 1 #Beliebige Tabellengruppe
    for j, sp in enumerate(sps):
        if sum(cap[s] for s in sp) < r.Anzahl der Personen:
            m += r.Var[j] == 0 #Anzahl der Personen begrenzt
        for s in sp:
            for t in range(r.Reservierungszeit):
                p[s][r.Startzeit- 10 + t].append(r.Var[j])
for s in range(6):
    for t in range(nt):
        if p[s][t]:
            m += lpSum(p[s][t]) <= 1 #Nur eine Gruppe kann gleichzeitig Reservierungen am selben Tisch annehmen
m.solve()
a['Val'] = a.Var.apply(lambda v: int(value(lpDot(range(1, ns+1), v))))
print('%s %d Menschen%.2f 10.000 Yen' % (LpStatus[m.status],
    sum(a[a.Val > 0].Anzahl der Personen), value(m.objective) / 10000))
>>>
Optimal 8 3 Personen 20.440.000 Yen

Der Umsatz liegt bei über 200.000. Zeigt die erfolgreichen Reservierungen an.

python


print('Zeit Anzahl der Personen Preistabelle')
for i, r in a.iterrows():
    if r.Val:
        print('%2d-%2d %d %d %s' % (r.Startzeit, r.Startzeit + r.Reservierungszeit- 1,
                                    r.Anzahl der Personen, r.Anzahl der Personen * r.Stückpreis, sps[r.Val-1]))
>>>
Zeit Anzahl der Personen Preistabelle
11-11 3 8400 [2, 3]
16-18 3 8400 [5]
13-13 4 11200 [4]
16-17 2 4800 [2]
16-17 4 11200 [4]
12-12 3 7200 [5]
14-15 8 20800 [4, 5]
14-14 2 4800 [2]
10-10 1 3000 [0]
16-18 2 6000 [3]
15-15 8 16000 [0, 1, 2, 3]
11-11 3 8400 [0, 1]
10-10 2 4000 [4]
11-12 4 9600 [4]
16-18 4 8000 [0, 1]
13-13 2 5600 [0]
12-12 6 13200 [1, 2, 3]
10-11 4 8000 [5]
10-10 3 6600 [1, 2]
13-13 4 10400 [5]
13-13 2 6000 [1]
13-13 4 10400 [2, 3]
14-14 2 5200 [3]
14-14 3 7200 [0, 1]

das ist alles

Recommended Posts