Файл: пензенский государственный университет политехнический институт.docx

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Диссертация

Дисциплина: Не указана

Добавлен: 30.11.2023

Просмотров: 193

Скачиваний: 4

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

СОДЕРЖАНИЕ

Содержание

Введение

Основные положения, выносимые на защиту:

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

Анализ моделей и алгоритмов решения задач о назначениях

Анализ эквивалентных преобразований моделей задач о назначениях

Выводы

Модель и алгоритм решения задачи с приоритетными назначениями

Выводы

Алгоритм решения простейшей линейной многокритериальной задачи о назначениях Многообразие многокритериальных задач в сочетании с отсутствием единого принципа оптимальности порождает огромное число методов их решению. Использование того или иного подхода к решению конкретной задачи может оказать существенное влияние на трудоемкость вычислений. Это относится особенно к специальным классам задач, для которых при скалярном критерии качества разработаны эффективные алгоритмы, использующие специфику ограничений и критериальной функции. Одной из таких задач является задача о назначениях.В основе подавляющего большинства методов решения многокритериальных задач лежит понятие веса критерия, характеризующего его сравнительную важность. Наиболее распространенные методы решения многокритериальных задач основаны на свертке набора исходных целевых функций (с учетом их веса) в один обобщенный скалярный критерий [71]. Такой подход позволяет получить оптимальное по Парето решение и при этом характеризуется вычислительной эффективностью. Использование свертки обеспечивает возможность применения для решения многокритериальной задачи о назначениях специально разработанные для однокритериального случая методы – венгерский и метод Мака.Свертка частных критериев разного смыслового содержания не позволяет интерпретировать значение взвешенного обобщенного критерия, поэтому в общем случае использование операторов свертки требует предварительного нормирования матриц затратСl,l 1, k, т.е. приведения их к единой безразмерной шкале. Часто используемый способ нормирования – минимакс-нормализация.Предлагается следующий алгоритм решения простейшей многокритериальной линейной задачи о назначениях (70) – (75). Нормировать матрицы затрат Сl, l 1, k: cl clсl ijmin . c  cijl maxlmin Составить целевые функции безразмерными коэффициентами: f1(X), f2 (X),..., fk(X) с n nlfl(X)  сijxij, l 1, ki1 j1 Составить вектор   (1, 2,..., k)весовых коэффициентов относительной важности целевых функцийf1(X), f2 (X),..., fk(X) ,l 0 , l 1.k, l 1. В том случае, если все критерии имеют одинаковуюl1 важность,l 1, l 1.k. Составить скалярную целевую функция (обобщенный критерий) g(X)   ) ,( f1(X), f2 (X),..., fk(X),где  – оператор свертки. Перейти к однокритериальной задаче о назначениях вида g(X)  min, (76) n xij 1, j 1, n,i1 (77) n xij 1, i 1, n,j1 (78) xij{0,1}, i, j 1, n. (79) Решить задачу (76) – (79) венгерским методом или методом Мака. Результатом является получение решения, оптимального по Парето. Решая задачу многократно и с изменением весовых коэффициентов, можно получить множество Парето-оптимальных решений. Вид свертки в каждом конкретном случае отражает приемлемую для ЛПР форму компромисса между частными критериями. Наиболее часто используемыми свертками являются линейная свертка, мультипликативная свертка и свертка на основе отклонения от идеальной точки. 1   ...   8   9   10   11   12   13   14   15   ...   21

Решение простейшей линейной многокритериальной задачи о назначениях с использованием свертки на основе отклонения от идеальной точки Под идеальной точкой в многокритериальной задаче о назначениях вида (71) – (76) понимают такой векторF*(X)  Rk, компоненты которого являются минимумами целевых функцийf1(X), f2 (X),..., fk(X) по отдельности, т.е.fl*(X)  min fl(X),XDl 1, k. В практических задачах идеальная точка является недостижимой [73]. Свертка на основе идеальной точкиF*(X)имеет вид: g(X)  (F(X), F*(X)) , где  – некоторая метрика вRk. Наиболее часто используются взвешенная чебышевская метрика g(X)  maxlfl(X)  fl* l (80) и взвешенная евклидова метрика kg(X)  ( fl(X)  fl*)2.l1 (81) Предлагается следующий алгоритм составления обобщенного скалярного критерия на основе идеальной точки: составить kоднокритериальных задач о назначениях вида n nlfl(X)  cijxij min,i1 j1n (82)  xij 1, j 1, n,i1n (83)  xij 1, i  1, n,j1 (84) xij{0,1}, i, j 1, n, (85) гдеl 1,k; найти X * – оптимальное решение l-й задачи вида (82) – (84) и lfl*  fl(X*) , l 1, k; lсоставить вектор F*(X)  ( f*, f*,..., f*) , гдеfl*  fl(X*) , l 1, k;1 2 k lсоставить свертку на основе отклонения от идеальной точки по формуле (80) или (81). Разработана программа для нахождения решения многокритериальной линейной задачи о назначениях с использованием свертки на основе отклонения от идеальной точки средствами математического пакета Mathcad, полный текст которой представлен в приложении E. На рисунке 20 приведены результаты применения свертки на основе отклонения от идеальной точки к многокритериальной задаче о назначениях, исходные данные которой совпадают с исходными данными задачи, решенной с использованием линейной свертки: Рисунок 20 – Результаты решения многокритериальной линейной задачи о назначениях с использованием свертки на основе отклонения от идеальной точки На рисунке 20 представлены матрица X – оптимальное по Парето решение, полученное с использованием чебышевской метрики, и матрица Y – оптимальное по Парето решение, полученное с использованием евклидовой метрики. Также программа находит для каждого оптимального по Парето решения значения соответствующего ему критериального вектора. Применяя алгоритм многократно с изменением весовых коэффициентов, можно построить множество точек Парето. Выбор конкретного решения из множества Парето-оптимальных осуществляется ЛПР.Следует отметить, что в некоторых прикладных задачах ЛПР за идеальную точку может принять реальное решение, соответствующее некоторым принятым стандартам или планируемым значениям. 1   ...   10   11   12   13   14   15   16   17   ...   21

Модель и алгоритм решения многокритериальной задачи о назначениях с целевыми функциями противоположного направления

Модель и алгоритм решения многокритериальной открытой задачи о назначениях Обобщим открытую задачу о назначениях на случай многокритериальности. Математическая модель такой задачи в предположенииm nимеет вид:

Модель и алгоритм решения многокритериальной задачи с порядком назначений Обобщим задачу с порядком назначений на случай многокритериальности. Математическая модель такой задачи имеет вид:nn f1(X)  c1 x min,(121) ijiji1 j1… nn k(X)  ckx min,n (122)  xij 1,n j 1, n, (123)  xij 1, i  1, n, (124) {0,1}, i1, n, j 1, n, , i1, n, j h1, n, j*  1, h. (126) f xij гдеP {1,2,.., h}пр.(i, j)  (i, j*)– подмножество индексов работ, распределяемых в первую очередь.В главе 2 показано, что однокритериальная задача с порядком назначений эквивалента совокупности двух последовательно решаемых задач – открытой и с недопустимыми назначениями. Аналогично, многокритериальная задача с порядком назначений эквивалента совокупности двух последовательно решаемых задач – многокритериальной открытой задаче и многокритериальной задаче с недопустимыми назначениями. Следовательно, можно описать алгоритм решения многокритериальной задачи с порядком назначений. Нормировать матрицы затрат Сl, l 1, k: cl clсl ijmin . c  cijl maxlmin Найти размер штрафа Ml 2n. Построить математическую модель назначения на работы из множества P :

Выводы

Заключение

Список использованных источников

, основанные на эквивалентных преобразованиях задач о назначениях.

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

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

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

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

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

Список использованных источников





  1. Карманов, В. Г. Математическое программирование / В. Г. Карманов. – М.: ФИЗМАТЛИТ, 2004. – 264 с.

  2. Банди, Б. Основы линейного программирования / Б. Банди. – М.: Радио и связь, 1989. – 176 с.

  3. Хыдырова, Г. Д. Математическая модель задачи о назначениях и возможности ее использования при принятии управленческих решений / Г. Д. Хыдырова, А. Ю. Душкина, А. Г. Савина // Научные записки ОрелГИЭТ. – 2014. – № 1 (7). – С. 305 – 310.

  4. Малюгина, О. А. Использование задачи о назначениях при решении проблемы формирования штатов / О. А. Малюгина, Г. Д. Чернышова // Вестник Факультета прикладной математики, информатики и механики. – 2010. – № 8.– С. 141 – 148.

  5. Кордюков, Р. Ю. Модель и алгоритмизация оптимизационной задачи о назначениях в условиях дополнительных ограничений / Р. Ю. Кордюков, Р. В. Допира, А. В. Иванова, Ф. Н. Абу-Абед, Д. В. Мартынов // Программные продукты и системы. – 2016. – № 2 (114). – С. 16 – 22.

  6. Кордюков, Р. Ю. Метод оптимизации размещения гос- оборонзаказа на предприятиях оборонно-промышленного комплекса

/ Р. Ю. Кордюков // Научный вестник ОПК России. – 2015. – № 2. – С. 70 – 73.

  1. Эддоус, М. Методы принятия решений / М. Эддоус, Р. Стэнсфилд. – М.: Аудит, ЮНИТИ, 1997. – 590 с.

  2. Коркишко, Н. М. Приближенные алгоритмы решения некоторых многоиндексных задач о назначениях : автореферат дис. … канд. физ.-мат. наук.: 01.01.09 – Новосибирск, 2003. – 20 с.

  3. Misevicius, A. A tabu search algorithm for the quadratic assignment problem / A. Misevicius // Computational optimization and applications. – 2005. – Vol. 30. – pp. 95 – 111.

  4. Burkard, R. E. Assignment problems / R. E. Burkard, M. Dell'Amico,

S. Mortello. – Philadelphia: SIAM, 2009. – 402 p.

  1. Farahani, R. Z. Facility location: Concepts, models, algorithms and case studies / R. Z. Farahani, M. Hekmatfar. – Heidelberg: Physica-Verlag, 2009. – 543 p.

  2. Qela, E. The quadratic assignment problem: Theory and algorithms. – Dordrecht: Kluwer Academic Publishers, 1998. – 287 p.

  3. Glover, F. Tabu search – Part I / F. Glover // ORSA J. Comput. – 1989. – Vol. 1. – pp. 190 – 206.

  4. Glover, F. Tabu search - Part II / F. Glover // ORSA J. Comput. 1990. – Vol. 2. – pp. 4 – 32.

  5. Гуляницкий, Л. Ф. Об одном подходе к использованию вероятностного моделирования в схеме генетического алгоритма / Л. Ф. Гуляницкий, О. Я. Турчин // Компьютерная математика: материалы Межд. конф. по индуктивному моделированию. – Львов: ГНИИ информационной инфраструктуры, 2002. – Т. 2. – C. 275 – 281.

  6. Гуляницкий, Л. Ф. Метаэвристический метод деформаций для решения задач комбинаторной оптимизации / Л.Ф. Гуляницкий // International Conference «Knowledge – Dialogue – Solutions». 2007 [Электронный ресурс]. URL: http://www.foibg.com/conf/ITA2007/KDS2007/PDF/KDS07- Hulyanitskiy.pdf (дата обращения: 22.05.2020).

  7. Ahuja R. K. A survey of very large-scale neighborhood search techniques / R. K. Ahuja, O. Ergun, J. B. Orlin, A. P. Punnen // Discrete Applied Mathematics, 2002. – Vol. 123. – pp. 75 – 102.

  8. Каширина, И. Л. Генетический алгоритм решения квадратичной задачи о назначениях специального вида / И. Л. Каширина // Вестник ВГУ. – 2003. – №1. – С. 128 – 131.

  9. Fleurent, C. Genetic hybrids for the quadratic assignment problem /

C. Fleurent, J. A. Ferland // Quadratic Assignment and Related Problems, DIMACS Series, 1994. – Vol. 16. – pp. 173 – 187.

  1. Holland, J. H. Adaptation in Natural and Artificial Systems

/ J. H. Holland. –Michigan: The MIT Press, 1992. – 232 p.

  1. Штовба, С.Д. Муравьиные алгоритмы / С.Д. Штовба // Exponenta Pro. Математика в приложениях. – 2003. – №4. – С. 70 –75.

  2. Colorni, A. The ant system: Optimization by a colony of cooperating agents / A. Colorni, M. Dorigo, V. Maniezzo // IEEE transactions on systems, man, and cybernetics. – 1996. – Vol. 26. – pp. 29 – 41.

  3. Каширина, И. Л. Применение растущей нейронной сети для решения квадратичной задачи о назначениях / И.Л. Каширина // Вестник ВГУ. Серия: Системный анализ и информационные технологии. – 2007. –

№ 1. – С. 52 – 55.

  1. Лагздин, А. Ю. Построение и анализ алгоритмов решения квадратичной задачи о назначениях на сетях : диссертация ... канд. физ.-мат. наук : 05.13.18 – Омск, 2012. – 103 с.

  2. Метельский, Н. Н. Методы локальной оптимизации для задачи размещения двудольных графов / Н. Н. Метельский // Журнал вычислительной математики и математической физики, 1994. – Т. 24. – № 9. – С. 1428 – 1432.

  3. Забудский, Г. Г. Полиномиальные алгоритмы решения квадратичной задачи о назначениях на сетях / Г. Г. Забудский, А. Ю. Лагздин

// Журнал вычислительной математики и математической физики. – 2010. – Т. 50. – №11. – С. 2052 – 2059.

  1. Забудский, Г. Г. Динамическое программирование для решения квадратичной задачи о назначениях на дереве / Г. Г. Забудский, А. Ю. Лагздин // Автоматика и телемеханика. – 2012. – № 2. – С. 141 – 155.

  2. Burkard, R. E. On the biquadratic assignment problem

/ R. E. Burkard, E. Cela, B. Klinz // Quadratic Assignment and Related Problems, DIM ACS Series. – 1994. – Vol. 16. – pp. 117 – 146.

  1. Burkard, R. E. Heuristics for biquadratic assignment problems and their computational comparison / R. E. Burkard, E. Cela // European Journal of Operational Research, 1995. – Vol. 83. – pp. 283 – 300.

  2. Богданова, Е. Л. Оптимизация в проектном менеджменте: линейное программирование: учебное пособие / Е. Л. Богданова, К. А. Соловейчик, К. Г. Аркина. – СПб.: Университет ИТМО, 2017. – 165 с.

  3. Агальцов, В. П. Математические методы в программировании

/ В. П. Агальцов, И. В. Волдайская. – М.: ИНФРА-М,
2006 г. – 224 с.

  1. Derigs, U. An augmenting path method for solving linear bottleneck assignment problems / U. Derigs, U. Zimmermann // Computing, 1998. – Vol. 19. – pp. 285 – 295.

  2. Глебов, Н. И. Об одном обобщении минимаксной задачи о назначениях / Н. И. Глебов // Дискретный анализ и исследование операций. – 2004 . – № 1 – С. 36–43

  3. Серая, О. В. Минимаксная проблема назначения / О. В. Серая // Восточно-Европейский журнал передовых технологий. – 2009. – № 3/3 (39). – С. 8 – 11.

  4. Коган, Д. И. Концепции и алгоритмы решения многокритериальных модификаций задачи о назначениях / Д. И. Коган, Ю. С. Федосенко, Д. А. Хандурин // Вестник Волжской государственной академии водного транспорта. – 2017. – №53. – С. 25 – 36.

  5. Медведев, С. Н. О нечѐткой задаче о назначениях

/ С. Н. Медведев, Т.М. Леденева // Вестник Белгородского государственного технического университета им. В. Г. Шухова. – 2012. – № 2. – С. 154 – 157.

  1. Медведев, С. Н. Нахождение области устойчивости интервальной задачи о назначениях / С. Н. Медведев // Вестник Воронежского государственного технического университета. – 2011. – № 10. – С. 51 – 54.

  2. Попов, В.П. Интервальный подход к оптимизации решения многокритериальной задачи о назначениях / В.П. Попов, И.В. Майорова // Прикладная информатика. – 2015. – № 10. – С. 122 – 131.

  3. Salehi, K. An approach for solving multi-objective assignment problemwith interval parameters / K. Salehi // Management Science Letters. – 2017. – Vol. 4. – pp. 2155 –2160.

  4. Steuer, R. E. Algorithms for linear programming problems with interval objective function coefficients / R. E. Steuer // Mathematics of Operations Research. – 1981. – Vol. 6. – pp. 222 – 248.

  5. Mraz, F. On supremum of the solution faction in linear programs with interval coefficients / F. Mraz // Research Report. – 1993. – Vol. 2. – pp. 182 – 196.

  6. Kumar, A. Assignment and Travelling Salesman Problems with Coefficients as LR Fuzzy Parameters / A. Kumar, A. Gupta // International Journal of Applied Science and Engineering. – 2012. – Vol. 10(3). – 155 – 170.

  7. Кочкаров, Р. А. Многокритериальная задача о назначениях на предфрактальном графе / Р. А. Кочкаров // Новые информационные технологии в автоматизированных системах. – 2014. – № 1. – С. 319 – 328.

  8. Каширина, И. Л. Генетический алгоритм решения многокритериальной задачи о назначениях / И. Л. Каширина, Б. А. Семенов // Информационные технологии. – 2007. – № 5. – С. 62 – 68.

  9. Медведева, О. А. Решение задачи о назначениях с дополнительным требованием / О. А. Медведева, А. Ю. Полетаев // Вестник Воронежского государственного университета. – 2016. – № 1. – С. 77 – 81.

  10. Frieze, A. Efficient Algorithms For Three-Dimensional Axial and Planar Random Assignment Problems / A. Frieze , G. Sorkin // Random Struct. Algorithms. – 2015. – № 46/1. – pp. 160–196.

  11. Дичковская С. А. Исследование полиномиальных алгоритмов решения многокритериальной трехиндексной планарной задачи о назначениях / С. А. Дичковская, М. К. Кравцов // Вычислительная математика и математическая физика. – 2007. – № 47/6. – С. 1029 – 1038.

  12. Медведева, О. А. Модели и алгоритмы решения многокритериальных задач о назначениях с дополнительными ограничениями : диссертация ... канд. физ.-мат. наук : 05.13.18 – Воронеж, 2013. – 159 с.

  13. Scarelli, А. A multicriteria assignment problem / А. Scarelli, S. C. Narula // Journal of Multi-Criteria Decision Analysis. – 2002. № 11(2).

pp. – 65 – 74.

  1. Кожухаров, А. Н. Многокритериальная задача о назначениях / А. Н. Кожухаров, О. И. Ларичев // Автоматика и телемеханика. – 1987. – № 7. – С. 71–88.

  2. Никонов, О. Я. Математические методы решения многокритериальной задачи о назначениях / О. Я. Никонов, О. А. Подоляка, А. Н. Подоляка, Е. В. Скакалина // Вісник Харківського національного автомобільно-дорожнього університету – 2011. – № 5. – С. 103 – 112.

  3. Медведева, О. А. Задача о назначениях с возможностью обучения

// Вестник Санкт-Петербургского университета. – 2013. – № 1. – С. 85 – 94.

  1. Муха, В.С. Решение открытой задачи назначения стандартным симплекс-методом / В.С. Муха // Доклады Белорусского государственного университета информатики и радиоэлектроники. – 2014. – № 6 (84). – С. 104 –107.

  2. Близнова, О.В. Логическое моделирование систем с последовательно-параллельной структурой : автореферат дис. канд. техн.

наук : 05.13.18. – Саратов, 2014. – 15 с.

  1. Pusztaszeri, J. F. Tracking elementary particles near their primary vertex: A combinatorial approach / J. F. Pusztaszeri, P. E. Rensing, T. M. Liebling

// Journal of Global Optimization. – 1996. – Vol. 9. – P. 41 – 64.

  1. Alighanbari, M. Cooperative task assignment of unmanned aerial vehicles in adversarial environments / M. Alighanbari, J.P. How // Proceedings of the American Control Conference. – 2005. Vol. 7. – P. 4661 – 4666.

  2. Гимади, Э. Х. Об асимптотически точном алгоритме решения одной модификации трѐхиндексной планарной задачи о назначениях / Э. Х. Гимади, Ю. В. Глазков // Дискретный анализ и исследование операций. – 2007. – №.1. – С. 442 – 452.

  3. Balas, E. An algorithm for the three-index assignmentproblem / E. Balas, M. J. Saltzman // Operations Research. – 1991. – № 39. – P. 150–161.

  4. Magos, D. Tabu search for the planar three-index assignment problem

/ D. Magos // Journal of Global Optimization. – 1996. – №

Смотрите также файлы