Оптимизируйте назначение мест на мероприятии с помощью ограничений Corona

Вы можете подойти к этому как к задаче целочисленного линейного программирования, определяемой следующим образом:

let P = the set of people groups, people group i consists of p_i people;
let T = the set of tables, table j has t_j places;
let x_ij be 1 if people from people group i are placed at table j, 0 otherwise
let M be a large penalty factor for empty seats
let N be a large penalty factor for splitting groups

     // # of free spaces = # unavailable - # occupied
     // every time a group uses more than one table,
     // a penalty of N * (#tables - 1) is incurred
min  M * [SUM_j(SUM_i[x_ij] * t_j) - SUM_i(p_i)] + N * SUM_i[(SUM_j(x_ij) - 1)]

     // at most one group per table
s.t. SUM_i(x_ij) <= 1 for all j

     // every group has enough seats
     SUM_j(x_ij * t_j) = p_i for all i

     0 <= x_ij <= 1

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

ILP являются NP-сложными, поэтому без правильных решателей это может быть невозможно выполнить с помощью Google Apps. У меня нет опыта в этом, поэтому, боюсь, я не могу вам помочь. Но есть несколько способов уменьшить пространство поиска.

Один из них - через что-то, что называется генерацией столбцов. Здесь проблема разбита на две части. Сложная основная задача - это ваш главный исследовательский вопрос, но вместо всего пространства решений он пытается найти оптимум из разных кандидатских назначений (или столбцов).

Затем цель состоит в том, чтобы определить подзадачу, которая рекомендует эти новые потенциальные решения, которые затем включаются в основную проблему. Сила хорошей подзадачи в том, что ее следует свести к более простой модели, такой как Ранец или Дейкстра.