Лекция: Комбинаторные аукционы

У аукциониста имеется множество объектов, выставленных на аукцион, а покупатели дают заявки, составляющие множество Заявка имеет вид где ‑ множество запрашиваемых объектов, а ‑ предлагаемая цена. Задача определения победителя аукциона состоит в помечивании заявок как выигравших или проигравших, максимизирующем сумму цен принятых заявок при ограничении, что каждый объект ставится в соответствие не более, чем одной заявке. Комбинаторный аукцион – частный случай рассмотренной выше задачи об упаковке.

Сформулируем модель в виде задачи ДО с бинарными переменными:

при ограничениях