Maximisez les ventes des restaurants grâce à l'optimisation combinée

Que faire

Le propriétaire d'un restaurant prospère plein de réservations m'a demandé de ** maximiser les ventes **. Nous demanderons aux candidats de réserver pour un jour lesquels sont OK et lesquels sont annulés. Ces problèmes peuvent également être résolus avec Optimisation de combinaison.

Pour les réservations, il est supposé que l'heure, le nombre de personnes et le prix unitaire sont connus comme indiqué ci-dessous. On suppose qu'une ligne correspond à une réservation, ne visite que [nombre de personnes] à [heure de début], mange pendant la durée de [heure de réservation] et paie [prix unitaire] x [nombre de personnes] pour revenir.

Heure de début Heure de réservation Nombre de personnes Prix unitaire
013222000
111132800
216332800
...............

À propos des sièges

Le restaurant peut accueillir jusqu'à 16 personnes, une table pour 2 personnes x 4 et une table pour 4 personnes x 2. image

Vous pouvez également utiliser la table pour deux personnes et la table pour quatre personnes ensemble. Il existe 13 façons de les attacher (ci-après dénommés groupes de tableaux). (Le numéro est le numéro de la table)

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

Formulation

$ \ mbox {objective} $ $ \ sum_i {\ sum_j {nombre de personnes_i prix unitaire_i x_ {ij}}} $ ventes totales < / td>
$ \ mbox {variables} $ $ x_ {ij} \ in \ {0, 1 \} ~ \ forall i, j $ Réservé $ Indique si i $ utilise le groupe de tables $ j $
$ \ mbox {soumis à} $ $ \ sum_j {x_ {ij}} \ le 1 ~ \ forall i $ Tout groupe de table
$ Nombre de places dans le groupe de tables j \ lt Lorsque le nombre de réservation i est $ Nombre limite
$x_{ij} = 0 ~ \forall i, j$
Un seul jeu peut être réservé à la fois à la même table

Cependant, la signification de l'indice est la suivante.

i: Réservation j: groupe de tables s: table t: heure

Résoudre avec Python

Commencez par créer une table de réservation (a) avec des nombres aléatoires.

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=['Heure de début', 'Heure de réservation', 'Nombre de personnes', 'Prix unitaire'])
cap = [2, 2, 2, 2, 4, 4] #Nombre de places par table
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]] #Liste des tableaux par groupe de tableaux
ns, nt = len(sps), 19 - 10 #Nombre de groupes de tables, nombre d'heures

Formulez et résolvez.

python


m = LpProblem(sense=LpMaximize) #Modèle mathématique
p = [[[] for t in range(nt)] for _ in range(6)] #Liste des variables par heure par table
a['Var'] = [[addvar(cat=LpBinary) for j in range(ns)] for i, r in a.iterrows()]
m += lpDot(a.Nombre de personnes* a.Prix unitaire, a.Var.apply(lpSum)) #Fonction objective(Ventes totales)
for i, r in a.iterrows():
    m += lpSum(r.Var) <= 1 #Tout groupe de tables
    for j, sp in enumerate(sps):
        if sum(cap[s] for s in sp) < r.Nombre de personnes:
            m += r.Var[j] == 0 #Nombre de personnes limité
        for s in sp:
            for t in range(r.Heure de réservation):
                p[s][r.Heure de début- 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 #Un seul groupe peut accepter des réservations en même temps à la même table
m.solve()
a['Val'] = a.Var.apply(lambda v: int(value(lpDot(range(1, ns+1), v))))
print('%s %d personnes%.2f 10 000 yens' % (LpStatus[m.status],
    sum(a[a.Val > 0].Nombre de personnes), value(m.objective) / 10000))
>>>
Optimal 8 3 personnes 20.440 000 yens

Les ventes sont supérieures à 200 000. Affiche les réservations réussies.

python


print('Heure Nombre de personnes Tableau des prix')
for i, r in a.iterrows():
    if r.Val:
        print('%2d-%2d %d %d %s' % (r.Heure de début, r.Heure de début + r.Heure de réservation- 1,
                                    r.Nombre de personnes, r.Nombre de personnes * r.Prix unitaire, sps[r.Val-1]))
>>>
Heure Nombre de personnes Tableau des prix
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]

c'est tout

Recommended Posts