Максимизируйте вкус вашей пиццы

Придайте вашей пицце максимальный вкус

“`html

Многие люди обожают пиццу, и их предпочтения варьируются от острой и веганской до вегетарианской, рыбоедной, мясной, махиавеллической или просто классической для любителей сыра.

Представьте себе задачу, с которой сталкивается владелец пиццерии, когда ему нужно угодить самым разным вкусам клиентов, разбросанным от горчичного соуса до сладкого бекона. Чтобы решить эту проблему, он привлек ученого-данных (DS) со знанием SQL. К счастью, DS разделял его глубокую любовь к пицце, как предписывает должностная инструкция.

Задача DS заключалась в создании решения, и вот что они придумали: на графике ниже изображены предпочтения 50 клиентов по отношению к 20 разным ингредиентам пиццы. Данные анонимизированы, чтобы обеспечить сохранность конфиденциальных предпочтений клиентов относительно ананаса или чеснока в пицце.

Возьмем, например, клиента 0, который предпочитает пепперони, ананас и чеснок, но не любит рикотту, бекон и лук. Этот ценный клиент остается безразличным к остальным ингредиентам. Поэтому, если меню включает предпочитаемые элементы (зеленым) и исключает нежелательные (красным), удовлетворение клиента сохраняется.

Теперь, когда предпочтения клиентов стали известны ученому по данным (DS), следующий шаг – определить математическую постановку задачи. Этот этап является ключевым компонентом принятия решений.

Цель: Максимизировать удовлетворенность клиентов, оптимизируя количество довольных клиентов.

Ограничения: Обеспечить выполнение всех требований, понимая, что работа с требовательным клиентом похожа на обращение с горьким фруктом, который требует сладости, однако может оставить кислый привкус.

Переменные: Используйте бинарные переменные для обозначения выбора ингредиентов (Xe) и удовлетворенных клиентов (Uc).

{(0, 'L'): {2, 10, 13, 18}, (0, 'D'): {5, 8, 16}, (1, 'L'): set(), (1, 'D'): set(), (2, 'L'): set(), (2, 'D'): {0, 2, 4, 18}, (3, 'L'): {12, 13, 14}, (3, 'D'): set(), (4, 'L'): {15}, (4, 'D'): {4, 5, 6, 18}, (5, 'L'): {0, 8}, (5, 'D'): {6}, (6, 'L'): {0, 13, 14, 17}, (6, 'D'): {4, 7, 10}, (7, 'L'): {1, 6, 10, 14}, (7, 'D'): {15}, (8, 'L'): {3, 7, 18}, (8, 'D'): {4, 5, 9, 15}, (9, 'L'): {10, 15}, (9, 'D'): {8, 14, 18, 19}, (10, 'L'): set(), (10, 'D'): {7, 14, 16}, (11, 'L'): {1, 2, 12}, (11, 'D'): {3, 10}, (12, 'L'): {5, 10, 13}, (12, 'D'): {19}, (13, 'L'): {1, 8, 14, 16}, (13, 'D'): {4, 12}, (14, 'L'): {0, 10, 12}, (14, 'D'): set(), (15, 'L'): {4}, (15, 'D'): {11}, (16, 'L'): set(), (16, 'D'): {3, 8, 10, 17}, (17, 'L'): {0, 11, 17, 18}, (17, 'D'): {6, 19}, (18, 'L'): {17}, (18, 'D'): {9, 11, 19}, (19, 'L'): {4, 7, 11}, (19, 'D'): set(), (20, 'L'): {5, 8, 15, 16}, (20, 'D'): {2, 11}, (21, 'L'): set(), (21, 'D'): {0, 6, 10, 13}, (22, 'L'): {2, 5, 7, 17}, (22, 'D'): {1, 3, 18}, (23, 'L'): {3, 13}, (23, 'D'): {4, 8, 12}, (24, 'L'): {8}, (24, 'D'): {3, 5, 17, 19}, (25, 'L'): {0, 7, 9, 10}, (25, 'D'): {2, 6, 19}, (26, 'L'): {10, 18}, (26, 'D'): {3, 4, 7}, (27, 'L'): {3, 6}, (27, 'D'): {7, 9, 16}, (28, 'L'): {7, 17}, (28, 'D'): set(), (29, 'L'): set(), (29, 'D'): {4, 6}, (30, 'L'): set(), (30, 'D'): {0, 4, 5, 19}, (31, 'L'): {5, 8, 18}, (31, 'D'): {0, 12, 13}, (32, 'L'): {8}, (32, 'D'): {0, 7}, (33, 'L'): set(), (33, 'D'): {0, 2, 12}, (34, 'L'): set(), (34, 'D'): {3, 15}, (35, 'L'): set(), (35, 'D'): set(), (36, 'L'): {7}, (36, 'D'): {0, 19}, (37, 'L'): {6}, (37, 'D'): {5, 13, 15, 19}, (38, 'L'): {7, 9, 16, 18}, (38, 'D'): {3}, (39, 'L'): {10, 13, 17}, (39, 'D'): {15}, (40, 'L'): {9, 15}, (40, 'D'): {8, 10, 18, 19}, (41, 'L'): {0, 5}, (41, 'D'): {14, 16}, (42, 'L'): {4, 13}, (42, 'D'): set(), (43, 'L'): {4, 8, 16}, (43, 'D'): {6, 7, 10}, (44, 'L'): {0, 12}, (44, 'D'): {3, 5, 8, 9}, (45, 'L'): {2, 10}, (45, 'D'): set(), (46, 'L'): {2, 5, 9, 12}, (46, 'D'): set(), (47, 'L'): set(), (47, 'D'): set(), (48, 'L'): {4, 7, 13}, (48, 'D'): {1}, (49, 'L'): {0, 15}, (49, 'D'): {2, 4, 12, 13

Python код

import networkx as nx
import matplotlib.pyplot as plt
список_ингредиентов_пиццы = [
    'Сыр моцарелла',
    'Томатный соус',
    'Пепперони',
    'Грибы',
    'Зеленый перец',
    'Лук',
    'Черные оливки',
    'Колбаса',
    'Бекон',
    'Ветчина',
    'Ананас',
    'Халапеньо',
    'Свежий базилик',
    'Чеснок',
    'Оливковое масло',
    'Пармезанский сыр',
    'Рикотта',
    'Шпинат',
    'Вишневые помидоры',
    'Анчоусы'
]
plt.figure(figsize=(12,6))
for c in customers:
  X= [c for e in elements]
  Y= [e for e in elements]
  plt.scatter(X,Y, c='grey', s=20, alpha=0.4)
  x= [c for e in data[c,'L'] ]
  y= [e for e in data[c,'L'] ]
  plt.scatter(x,y, c='g', s=50)
  x= [c for e in data[c,'D'] ]
  y= [e for e in data[c,'D'] ]
  plt.scatter(x,y, c='r', s=50)
  plt.xticks(list(customers),rotation=90, fontweight='bold')
plt.yticks(list(elements), список_ингредиентов_пиццы, fontweight='bold')
plt.ylabel('Ингредиенты', fontweight='bold')
plt.xlabel('Клиенты', fontweight='bold')
plt.tight_layout()
имя_файла = 'base_pizza.png'
plt.savefig(имя_файла)# Загрузить файл
files.download(имя_файла)
plt.show()

%pip install ortools
from ortools.sat.python import cp_model

def main():
    model = cp_model.CpModel()
    X = {e:model.NewBoolVar(f"x_{e}") for e in elements}
    Sc = {c:model.NewBoolVar(f"S_{c}") for c in customers}
    for c,v in Sc.items():
        for e in data[c,'L']:
            model.Add(v <= X[e])
        for e in data[c,'D']:
            model.Add(v <= 1 - X[e])
    
    expressions = [v for s,v in Sc.items()]
    model.Maximize( cp_model.LinearExpr.Sum(expressions))
    
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

Результаты симуляции:

Выбранные ингредиенты, включая ветчину, обозначены горизонтальными линиями, а довольные клиенты - вертикальными золотыми линиями. Например, клиент 1 - легкий клиент, не имеющий специфических предпочтений или не нравящихся ингредиентов, в то время как клиент 28 имеет два предпочитаемых ингредиента (зеленым цветом) и никаких нежелательных ингредиентов (красным цветом).

Общая ценность целевой функции равна 17. Если вы заинтересованы в коде на Python, вы можете найти его в репозитории GitHub. Пожалуйста, найдите его в разделе комментариев, так как LinkedIn ограничивает публикации со ссылками. Все ссылки равны, но некоторые ссылки более равны.

Полное игнорирование нежелательных ингредиентов:

Если игнорируются предпочтения по ингредиентам и ограничить количество разрешенных ингредиентов до 10, то результаты будут следующими:

28 довольных клиентов.

Терпимость к одному нежелательному ингредиенту:

если ограничить количество разрешенных ингредиентов до 10, то результаты будут следующими:

21 довольный клиент.

Терпеть, если количество нравящихся ингредиентов больше, чем нежелательных ингредиентов:

если ограничить количество разрешенных ингредиентов до 10, то результаты будут следующими:

27 довольных клиентов.

Я понимаю, что это упрощенный сценарий, и в реальных пиццериях учитывается множество других факторов и ограничений, поэтому расслабьтесь и наслаждайтесь своей пиццей.

Эта проблема вдохновлена практической задачей google-hash-code-2022.

Github: https://github.com/OptimizationExpert/Pyomo

Наслаждайтесь!