LP модельный вопрос ... давно со школы - PullRequest
6 голосов
/ 17 февраля 2011

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

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

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

Я помню, что в школе достаточно, чтобы япроблема линейного программирования ... но все, что я могу вспомнить об этом классе, было то, насколько запутанным он был.

Ответы [ 2 ]

2 голосов
/ 18 февраля 2011

Расширяя мой комментарий выше, эта проблема сильно зависит от точной структуры стоимости доставки.Предположим, что стоимость доставки линейна с (потенциально) ненулевым постоянным членом.А именно, стоимость доставки = C + Rw, где C и R - константы, а w - вес заказа.Затем оказывается, что оптимальное решение простое: сгруппируйте каждый товар, где скидка меньше C, в один заказ и закажите каждый товар, где скидка больше C, отдельно (оставлено для читателя в качестве упражнения).В вырожденном случае, когда C = 0, вы просто разместите отдельный заказ для каждого элемента.

С другой стороны, если стоимость доставки имеет более пороговую структуру - например, если весотгрузка меньше, чем B, тогда стоимость составляет C1, но если она больше, чем B, тогда стоимость составляет C2 - ситуация становится формой проблемы полной упаковки NP.Здесь я должен отметить, что только потому, что ситуация имеет форму NP-полной проблемы, вы не должны сразу терять надежду.Для многих реальных ситуаций существует хорошая эвристика, и вполне возможно, что диапазон реальных входных данных ограничивает проблему управляемыми экземплярами.

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

2 голосов
/ 17 февраля 2011

Это не обычное линейное программирование, это целочисленное линейное программирование.Первый из них разрешим в O ( n ²), второй - NP-hard.

Какой-то вариант алгоритма ветвления и ограничения должен быть применим к вашей программе.Если вам не хочется реализовывать это самостоятельно, доступны следующие библиотеки: GLPK, COIN-OR и CPLEX.

...