NLP Solver - Оптимизация доставки

Автор neft, 14 января 2012, 20:45

0 Пользователи и 1 гость просматривают эту тему.

neft

ЦитироватьПостановка задачи.
Предположим, что компания, где вы работаете, имеет два складских помещения, откуда товар поступает в пять ваших магазинов, разбросанных по всей Москве.
Каждый магазин в состоянии реализовать определенное, известное нам количество товара. Каждый из складов имеет ограниченную вместимость. Задача состоит в том, чтобы рационально выбрать – с какого склада в какие магазины нужно доставлять товар, чтобы минимизировать общие транспортные расходы
Решение
В математике подобные задачи выбора оптимального маршрута по нескольким точкам относят к классу так называемых «транспортных задач» (Vehicle Routing Problems, VRP). И, конечно же, давно разработаны способы их решения. Excel предоставляет пользователю один из них – с помощью мощной надстройки Поиск решения (Solver) в меню Сервис (Tools).
Эта учебная задача для Excel взята отсюда (все подробности там же):
http://planetaexcel.ru/tip.php?aid=186

Решение, полученное в Excel 2010, на скриншоте.

Вопросы простые:
Как эта задача решается с помощью NLP Solver.
И какой в этом случае результат?

Сконвертированный в ODS экселевский файл приложен.


[вложение удалено Администратором]

ape

Пока безусловно ясно лишь одно: нельзя рекомендовать к использованию Exel-2010 в качестве конвертера в *.ods.

neft

Неконвертированный XLS (MS Excel 2003).


[вложение удалено Администратором]

ape

#3
Если Вас интересует, возможно ли решение, то в LibreCalc-3.5.0_beta3 - да, через меню "Сервис - Решатель"
------------------
p.s. Может быть, стоит поправить локализацию с "решатель" на "поиск_решения" по аналогии с МСО?

[вложение удалено Администратором]

neft

Подсказка № 1 (на скриншоте).

SUMPRODUCT(...) (Libreoffice) <=> СУММПРОИЗВ(...) (Excel)

Окно "Решатель" - установка параметров для LibreOffice.

Окно "Поиск решения" - установка параметров для Excel 2003 (приведена для сравнения).

Вопрос № 2 остается: что выдаст в результате "Решатель", если нажать кнопку "Решить"?

"Поиск решения" (Excel) выдает следующий результат: E17 = 33100,00р. (для сравнения).

[вложение удалено Администратором]

ape

Цитата: neft от 15 января 2012, 16:34
Вопрос № 2 остается: что выдаст в результате "Решатель", если нажать кнопку "Решить"?
Может и такой...  ;D

[вложение удалено Администратором]

bormant

#6
Линейный алгоритм даёт следующее решение:
0   80   0   320   400
300   150   150   0   0
Стоимость:  33 100,00р.

ps. С ТС ответ на сакральный вопрос: зачем линейную задачу решать методами NLP (non-linear programming -- нелинейного программирования)?
Автору на яд. Поддержать форум.

neft

#7
Именно так: правильный ответ получается если в "Параметрах" в "механизме решателя" выбрать "... линейный решатель".
А вот оба нелинейных метода не сходятся.

PS. Ответ не менее сакральный: с какой стати линейную задачу нельзя решить нелинейными методами?


[вложение удалено Администратором]

bormant

Цитата: neft от 16 января 2012, 10:59
оба нелинейных метода не сходятся.
с какой стати линейную задачу нельзя решить нелинейными методами?
Каковы параметры алгоритмов, таковы и полученные решения. Задайте соответствующие настройки и дожидайтесь более точного результата.
Автору на яд. Поддержать форум.

ape

Откровенно говоря, не понимаю зачем вообще в поставленной задаче нужны какие-то оптимизаторы. Разве строки, в котрой можно показать убыток\выигрыш при доставке товара (стоимость_2 - стоимость_1) не достаточно для тех, кто не знает арифметических действий и не способен запомнить 5 чисел?

bormant

ape,
готовы написать решение задачи в общем виде? Тогда почему не понимаете?
См. тему Линейное программирование.
Автору на яд. Поддержать форум.

ape

Цитата: bormant от 16 января 2012, 23:12
ape, ... почему не понимаете?
Одна из причин - 3-4 рабочих группы со специфичными желаниями и требованиями пользователей к установленным программным продуктам в качестве дополнительной и неоплачиваемой нагрузки на условно-рабочее и свободное время оставляют слишком мало времени на что-то большее. Например, к углублённому изучению ОфисBasic, который при внешней схожести очень далёк от привычных QBasic_4.5 и VBA_6.

bormant

ape, я не про нагрузку, а про формальное решение транспортной задачи методом линейного программирования. Решение в общем виде, его формальная запись, итеративный характер алгоритма поиска оптимального значения получаются весьма громоздки -- вполне подходящий кандидат на выполнение вычислительной части расширением, а не портянкой рассчитываемых вручную матриц. Писать на каждый случай задачи, решаемой методами линейного программирования по отдельному расширению тоже перебор. Если вам размерность 5х2 кажется до смешного малой -- увеличьте до желаемых пределов.
Другое дело, что математически точное оптимальное решение не всегда нужно, часто оказывается вполне достаточно решения близкого к оптимальному, но полученного с существенно меньшими затратами.
Автору на яд. Поддержать форум.

ape

Цитата: bormant от 17 января 2012, 16:13
- итеративный характер алгоритма поиска оптимального значения получаются весьма громоздки
- вполне достаточно решения близкого к оптимальному, но полученного с существенно меньшими затратами
С Вами не поспоришь: определение размерности массивов, их заполнение, расчёт, сортировка, бесконечное for_to - {if - else - then} - next внутри do - {if - else - then} - loop... - это действительно перебор, когда есть готовое решение.