Моделирование комбинаторной оптимизации? проблема

Question

Мне не удалось сопоставить эту проблему с какой-то канонической, и я хотел бы, чтобы некоторые руководства создали / использовали алгоритм и решили его.Описание выглядит следующим образом:

---

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

InitialOrder = { C1, J1, T1 } with C1, J1, T1 being integer non-negative numbers.

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

InitialPrice = C1 * Pc + J1 * Pj + T1 * Pt with Pc, Pj, Pt being rational positive numbers

Кафетерий имеет также «меню завтрака», состоящее из комбинаций стандартных элементов

full breakfast = coffee + juice + toast
normal breakfast = coffee + toast
bread breakfast = 2 toast

Выбор этих меню дешевле, чем выбор каждого компонента отдельно, поэтому у нас есть

Pf < Pc + Pj + Pt
Pn < Pc + Pt
Pb < 2 * Pt
with Pf, Pn, Pb being rational positive numbers

Люди хотят сгруппировать начальный заказ в меню, чтобы минимизировать общую сумму расходов.Тогда

FinalOrder = { C2, J2, T2, F, N, B } with C2, J2, T2, F, N, B integer non-negative numbers

, и у нас будет FinalPrice <= InitialPrice as </p>

FinalPrice = C2 * Pc + J2 * Pj + T2 * Pt + F * Pf + N * Pn + B * Pb with Pc, Pj, Pt, Pf, Pn, Pb as rational positive numbers

Все цены (Pc, Pj, Pt, Pf, Pn и Pb) известны заранее.

---

Пожалуйста, знаете ли вы, какой подход я должен использовать, чтобы построить алгоритм минимизации FinalPrice для данного InitialOrder?Не стесняйтесь спрашивать любые дополнительные детали, которые вам нужны.

Заранее спасибо.

Answer 1

Это выглядит как Линейное целочисленное программирование проблема.

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

Например, в вашем примере это будет (я предполагаю, что ваша реальная проблема сложнее, чем ваш пример: -))

Свернуть

C2 * Pc + J2 * Pj + T2 * Pt + F * Pf + N * Pn + B * Pb

(Умножьте Pc и т. Д. На подходящее целое число, чтобы сделать их целыми числами, если необходимо)

С учетом ограничений, которые

   C2 + F + N = C1
   T2 + F + N + 2B = T1
   J2 + F = J1

В общем случае целочисленное программирование является NP-сложным, но, учитывая небольшой размер проблемы и ограничения, стандартные методы решения, вероятно, могут быстро решить ее для вас.

Надеюсь, это поможет.

Answer 2

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

Answer 3

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

Однако, как говорит Морон, для решения любой большой проблемы вам понадобится ILP.