Введение 3
1 Постановка задачи 5
2 Связь критериев с типовыми задачами на графах 7
3 Описание алгоритмов, решающих задачу 16
4 Применение алгоритмов на практике 20
Заключение 25
Список использованных источников 29
А Программный код реализации алгоритмов 30
Б Программный код реализации тестов 42
Задача оптимального размещения производства в сети представляет практический интерес в экономике. При планировании развития производства часто возникает необходимость в решении задач оптимального размещения предприятий. Во многих случаях такие задачи являются весьма сложными и требуют применения методов математического моделирования, разработки специальных алгоритмов и программного обеспечения. Исследованию таких задач посвящено множество работ [1]. В качестве критериев может служить множество различных параметров — это усложняет задачу, ведь не всегда понятно какие критерии более важны. Чаще всего рассматриваются задачи размещения пунктов производства одного вида продукции, а в качестве критериев оптимальности, которые следует минимизировать, берутся расстояния от пунктов производства до пунктов потребления. В качестве принципа оптимальности, согласующего эти критерии, ранее рассматривались оптимумы по Парето, сумма расстояний, максимум из расстояний. Оптимизация по принципу минимума суммы сводится к задаче о поиске медиан графа, а оптимизация по принципу минимума максимума — к задаче о поиске центров графа [2]. Также в [2] рассматриваются А—центидантные постановки задачи, совмещающие задачи о минимизации максимума и суммы критериев.
Подобные задачи являются задачами целочисленного линейного программирования, для которых возможны различные алгоритмы точного и приближенного решения. Алгоритмы поиска медиан и центров, преимущественно основанные на методе ветвей и границ, рассмотрены в [3].
В данной работе ставится многокритериальная задача, которая обобщает задачу из [2]: имеется несколько видов продукции, каждый из которых необходим в пунктах потребления, необходимо разместить несколько групп заводов, производящих различные виды продукции.
В работе рассмотрены различные методы решения многокритериальной задачи размещения, представляющие различные подходы к задаче (алгоритм, основанный на методе ветвей и границ, также алгоритм, базирующийся на алгоритме для поиска р-центров), выясняются их достоинства, недостатки и ограничения. В рамках данной работы выполнена программная реализация этих методов на языке программирования C++, позволяющая проверить эффективность и провести более детальное сравнение.
В работе рассмотрена задача многокритериальной оптимизации размещения пунктов производства. Данная задача рассматривалась в литературе [1], так например в [2] автор рассматривает задачу размещения производств одного вида продукции в сети. Применяя простейшие принципы оптимальности: эгалитарный и утилитарный, автор сводит задачи размещения к задачам о поиске медиан и центров в графе. В той работе, обобщается данная задача, на размещение пунктов производства, производящих несколько видов продукции. Были выбраны методы для решения, а также разработана программная реализация алгоритмов, решающих задачу. Для утилитарного принципа оптимальности хорошо подходит алгоритм, основанный на методе ветвей и границ, также в ряде случаев задачу можно свести к задаче ЦЛП. Что касается эгалитарного принципа, то для него был предложен алгоритм, основанный на поиске mr центров.
Для обоих методов написана программная реализация на языке C++ и проведено тестирование на наборах сгенерированных задач с различными параметрами. Был проведен анализ их работы на различных входных данных, сделаны выводы о скорости и эффективности работы алгоритма. Так оба алгоритма работают быстро при количестве вершин Р 6 25 и количестве различных видов продукции N{1,3,5,7,9}. Однако при увеличении Р, скорость алгоритмов существенно снижается.
Исследование методов не только показало их применимость к решению задачи, но также и наглядно продемонстрировало различия подходов, определяющих эти методы. Однако подходы к поиску оптимального размещения разнообразны, и даже в рамках различных методов оптимальности методы решения могут быть различны. Поэтому исследование задачи оптимального размещения может быть продолжено. Можно брать различные принципы оптимальности, искать Парето-оптимальные решения [7] поставленной задачи, оптимизировать использование памяти и скорость выполнения алгоритмов, реализованных в рамках данной работы. Также можно рассмотреть возможность размещения производств на дугах графа.
