Введение 3
Обзор литературы 5
1 Постановка задачи 7
2 Описание методов решения поставленной задачи 11
Заключение 26
Список использованных источников 29
Задача оптимального размещения производства в сети представляет практический интерес в экономике. При планировании развития производства часто возникает необходимость в решении задач оптимального размещения предприятий и складов. Во многих случаях такие задачи являются весьма сложными и требуют применения методов математического моделирования, разработки специальных алгоритмов и программного обеспечения. Исследованию таких задач посвящено множество работ [1]. В качестве критериев может служить множество различных параметров — это усложняет задачу, ведь не всегда понятно какие критерии более важны [2]. Для этой задачи в литературе рассмотрены многие подзадачи. Например:
— Многокритериальная задача размещения пунктов производства одного вида продукции [3];
— В своей публикации [4] я рассматривал алгоритм решения задачи размещения производства нескольких видов продукции;
— Задача о складировании [5];
В данной работе предлагается расширить задачу размещения производств добавлением новых объектов — пунктов хранения продукции(складов), а также применяя альтернативные подходы к принципам оптимальности. Складом будем называть место, где произведенная продукция может храниться, как в промежуточном пункте между производством и пунктами потребления товаров.
В работе рассмотрены различные методы решения многокритериальной задачи размещения, представляющие различные подходы к решению задачи(алгоритм, основанный на методе ветвей и границ, также эвристический алгоритм основанный на идеи генетической селекции множества парето оптимальных решений), выясняются их достоинства, недостатки и ограничения. В рамках данной работы выполнена программная реализация этих методов на языках программирования C++ и PYTHON, позволяющая проверить эффективность и провести более детальное сравнение.
В работе рассмотрена задача многокритериальной оптимизации размещения пунктов производства и складирования. Данная задача рассматривалась в литературе [1], так например в [3] автор рассматривает задачу размещения производств одного вида продукции в сети. Применяя простейшие принципы оптимальности: эгалитарный и утилитарный, автор сводит задачи размещения к задачам о поиске медиан и центров в графе. В той работе, обобщается данная задача: необходимо разместить пункты производства, производящих несколько видов продукции, а также пункты складирования. Были выбраны методы для решения. Первый метод основан на объединении критериев в один и использовании метода ветвей и границ для поиска наименьшего значения полученного обобщенного критерия. Второй базируется на подходе к решению многокритериальных задач с помощью эвристических алгоритмов. Также разработана программная реализация алгоритмов, решающих задачу.
Среднем для генетического алгоритма получается неплохой результат приближенного решения. Можно сказать, что решения полученные генетическим алгоритмом в среднем удалены от множества Парето-оптимальных решений в примерно два раза дальше, чем среднее расстояние между всеми Парето-оптимальными решениями, и примерно в три раза ближе, чем если выбирать размещения случайным образом.
Исследование методов не только показало их применимость к решению задачи, но также и наглядно продемонстрировало различия подходов, определяющих эти методы. Подходы к поиску оптимального размещения разнообразны, и даже в рамках различных методов оптимальности методы решения могут быть различны. Поэтому исследование задачи оптимального размещения может быть продолжено. Можно комбинировать методы использовать приближенные решения полученные на алгоритмом ветвей и границ(прервав его исполнение через некоторое время).
