На производстве минимизируют отходы, издержки, затраты, длину маршрутов, время изготовления, брак, да много чего ещё. Самое обидное, что и зарплату тоже
В реальном производстве трудно представить изоморфную задачу, поскольку даже с невестами минимизация количества пар приводит к возрастанию напряжённости. Да и мнение девушек тоже надо учитывать.
Минимизация нужна тогда, когда влюблённость в девушек (перенесённая в производственные термины) является для молодого человека навязанной и обременительной.
На самом деле есть целый ряд задач, упрощенно сводящихся к "невестиной" схеме: Есть некоторое количество объектов двух видов. Между ними возникают паразитные связи. При установлении легальной связи между двумя объектами все паразитные, связанные с ними, уничтожаются. Задача: уничтожить паразитные связи, установив минимальное количество легальных.
Обычно существуют веса рёбер, стоимость установления легальной связи и прочие ограничения, да и задача решается в динамике. А теория, как правило, рассматривает идеальную модель без всяких неприятных неожиданностей. Хотя работает в достаточно стабильных, но огромных системах, где интуиция Петровича уже не срабатывает.
несколько клеток закрашены красным цветом. Требуется поставить на красные клетки минимальное число ладей, чтобы они били все красные клетки (считаем, что ладья бьёт клетку, на которой стоит).