Современные подходы к решению многокритериальных
Международная
публикация
ART 53563
А.
А. ЕвсееваБиблиографическое описание статьи для цитирования:
Евсеева
А.
А.,
Красникова
Д.
А.,
Казаков
А.
А. Современные подходы к решению многокритериальных // Научно-методический электронный журнал «Концепт». –
2013. – Т. 3. – С.
2801–2805. – URL:
http://e-koncept.ru/2013/53563.htm.
Аннотация. В данной статье рассматривается систематизация получения оптимальных решений в многокритериальных транспортных задачах. Раскрывается смысл применения математических и имитационных моделей при решении транспортных задач в настоящее время.
Ключевые слова:
математические модели, транспортные задачи, оптимальные решения, многокритериальные задачи
Текст статьи
Евсеева Анна АнатольевнаКандидат экономических наук, доцент кафедры «Организация перевозок и управление на транспорте», Саратовский государственный технический университет имени Гагарина Ю.А., г. Саратов.annaevseeva@mail.ru
Красникова Дарья АндреевнаКандидат экономических наук, доцент кафедры «Организация перевозок и управление на транспорте», Саратовский государственный технический университет имени Гагарина Ю.А., г. Саратов.dasha747@yandex.ru
Казаков Александр Александровичстуденттретьего курса специальности «Организация перевозок и управления на транспорте», Саратовского государственного технического университета имениГагаринаЮ.А., г.Саратовkasa0805@yandex.ru
СОВРЕМЕННЫЕ ПОДХОДЫ К РЕШЕНИЮМНОГОКРИТЕРИАЛЬНЫХ ТРАНСПОРТНЫХ ЗАДАЧАннотация.В данной статьерассматривается систематизация получения оптимальных решений в многокритериальных транспортных задачах.Раскрывается смысл применения математических и имитационных моделей при решениитранспортных задачв настоящее время.
Ключевые слова.Транспортные задачи, математические модели, оптимальные решения, многокритериальные задачи.В современных нестабильных условиях функционирования производственные предприятия испытывают определенные трудности в управлении производственными процессамии процессами транспортировки, как сырья, так и готовой продукции. Это связано с несколькими причинами, такими как:
искажение информациив процессе еепередач;
сложная организационная структура допускает противоречивые команды;
неопределенностьв направлениидеятельности и отсутствие навыковработы.При транспортировке продукциивозникает много серьезных ошибок. Типичными недостатками являются ошибки при передаче информации (неподходящие маршруты, неуместная скорость,возникновение материального ущерба во время перевозок, невнимание и т.д.).
Рис. 1. Организационная схема производственной компанииВербальная модель представляет собой, как мы знаем, краткое словесное описание проблемы с использованием технических терминовсоответствующей области. Вербальные модели в задачах исследования операций обычно содержат список данных по умолчанию, описание априорных заключенийобискомомрешении, ограничения и решения вопроса о приемлемости критериев качества.Постановка задачи в форме словесноймодели обычнопредставляет собойне один вид деятельности, анесколько раз циклически повторяющийся процесс постепенного совершенствования и доработки. При этом, модель адаптирована в соответствии с данными, известными заранееиновыми, полученнымис учетом замечаний экспертов к предыдущей версии и, наконец, принимая вовниманиевозможности математических методов и вычислительной техники нужно времядля получениярешения.
Каждый цикл как правилосодержит:1. Определение множества решений(с результатом обработки информации или материалов)2. Созданиеограничений(например, условия допустимости решения)3. Формулировку критериев качества(краткое описание оптимального решения)4. Указание, с учётом данных, полученных в пунктах с 1 по 3, информации, необходимойдля определения наиболее рационального решения.В данном контексте в качестве примера можно рассматривать задачу развозагруз по сети магазинов, находящейся на улицах города, используя грузовые автомобили. Решение задачисостоит в поиске оптимального маршрутадоставкигрузов.При формулированииограниченийнеобходимо убедиться, что непропущеноникаких существенных лимитов, и наоборот, чтоне включенынеуместныеили ненужные. В нашем случаеиспользуется ограничение,вытекающее из требованияДиректорЗаместитель по производствуЗаместитель по финансовым вопросамОтдел по строительству и развитиюЭкономический отделЛогистический отделОтдел снабженияОтдел продажСклад сырья1 складпромежуточный склад2 складсклад продуктовчтопоставкагруза должна осуществляться вовсе магазины без повторных заездов. Дополнительнымиограничениямимогут служитьи другие требования(например, часы работы).Критерий качества,асоответственно, егоколичественное выражениеможет быть представлено в виде целевой функциисозданияи оценкиразличных аспектов перехода от субкритериев к интегральномукритерию. В нашем примере рассматриваютсятакиеограничениякак:минимальное времяработытранспортного средства, скоростьдоставкигруза вмагазиныили наименьшийрасход топлива. Очевидно, что в конкретной ситуации, эти критерии могут конфликтовать. Выбор интегральногокритерия, следовательно, не должен быть заранее решен. В каждом конкретном случае интегральныйкритерий может видоизменятьсяв зависимости от требований клиентаи накладываемых ограничений[1].В качестве исходных данных рассмотрим маршруттранспортного средства, общийобъемагрузов, погруженных в кузов, скоростной режим транспортного средства с учетом загруженности дорог в городеи т.д.Математическая модель в данном случае является словесной модельюв математических терминах, с использованием математических символов. Еёсозданиетребует хорошего знания моделируемых процессов и математических средств, которые доступны на данном этапе. Создание математической модели часто бывает сложным, выбор может быть неоднозначным, так как не существует и однозначныхметодов отбора.Рассмотрим используемые на современном этапе математические модели и методы решения задач в области транспорта. Можно выделитьтакие фазы решения как:обработка, настройка и тестирование программы, расчет, его толкование и применение, возможностьреализации с учетом ресурсов, которые доступны (аппаратное и программное обеспечение), а также спецификапроблемы.Из вышесказанного ясно, в решениипоставленной задачинеобходимо пройти несколько этапов,вкоторых задача последовательно разделяется на несколько подзадач. Единственнымспособом являетсясистематический подход, когда происходитразработкаединой методологии для решения задач оптимизации,сформулированныхв транспортных системах. Такая общая методология включает в себя:• описание проблемы и соответствующие методы оптимизации,
• реализациюалгоритмовоптимизации с помощьюкомпьютерных технологий;
• подготовкуисходных данных и выводрезультатов
• работу и управление оператора связис вычислительной системой,
• возможность использования искусственного интеллекта.Результатыиспользуются всистемахподдержки принятия решений, то есть в качестве основы для планирования и управления транспортными процессами. Эти данныемогут быть использованы для решения задачв реальном времени в качестве основы для принятия долгосрочных плановых решений. Определение и создание единой методологиидля решения оптимизационных задач, сформулированных в транспортных системах(а не в движении), позволит повысить производительность транспортных систем за счет ускорения процесса решения поставленных задач. В связи с созданием модели (словеснойили математической) можностолкнуться струдностями на этапе разработкисоответствующих критериев оптимальности. Кроме того, многиепрактическиезадачипредставлены вмногокритериальной форме.Такиетребования к продукции, как легкость, прочностьи дешевизнане могут быть удовлетворены одновременно с высшей степенью качества. Улучшение любых двух из этих свойствбудутухудшать третье.Другим примером могутбыть требования в видебыстрогопроизводства и высокого качества, низкой цены, удобства доступактранспортным услугамконкретного города или региона. Решениемногокритериальных задачвпервые предложилв 1896 году итальянский экономист и социолог В.Парето (1848 1923). Им было введено понятие «оптимальноерешение» это решение, в котором любой параметрможет быть улучшен только за счет деградации другого[2]. Предположим, что возможно решение X, то есть решение, которое удовлетворяет всем условиям работы и оценивается по нескольким количественным показателям или субкритериямK1(X), ..., Kn(X). Исходя из этого, критерии всегда могутбыть определены«лучшим»решением, котороебудет соответствовать максимальному значению каждого критерия.Тогдарешение X'доминируетнадрешением X", когда для всех рассматриваемых субкритериев:K1(X')
≥K1(X"),…,Kn(X')≥Kn(X") (1)
и когда по крайней мере одно из этих неравенств оказывается равнымn, этогоне происходит. Стоит отметить отношениядоминирования,такие как X'� X"; Два решения X' иX'' для которых они не действуютилиX' > X'' илиX''> 'X, назовем взаимным недоминированием. Совокупность всех решений, к которым нет решения, которое будет доминировать, мы называем недоминированныммножеством, и каждый элемент множества недоминированиямы называем Паретооптимальнымрешением.Пример, иллюстрирующий понятия, введенных только в случае двух критериев K1а К2представлен на рисунке 2.Множество пар значений K1(X),К2(Х) для всех допустимых решений Xпоказанокак областьK, включая границы. Часть границы соответствующих паретооптимальным решениям указано жирнойлинией, включая точки А, В и D, опуская точку C. Именно на этих участках не может произойти увеличениеодногоиз критериев без увеличениявторого.
Рис. 2 Паретооптимальный набор двухкритериев
Другой возможный подход к многокритериальной оптимизации можно рассмотретьнаследующем примере.При движениина машине известна(хотя бы приблизительно) зависимость расхода топлива отвыбраннойскорости, S = F (V), л/км. Потреблениев связи ссопротивлениемвоздуха возрастает с увеличением скорости. С другой стороны, необходимо принимать во внимание стоимость потерянного времени участников перевозки.Еслиизвестна общая стоимостьпроезда пассажиров, которая рассчитывается по среднечасовой платеС1руб/ч и если C2это цена за 1 литр топлива, и если транспортное расстояние dкм, то расходы на транспортировкуЗ(V), которые зависят от средней скорости, могут быть выражены в виде: З(v) = C1+ C2f(v)d. (2)В результате минимизации функции получаем,что оптимальная средняя скорость движения, формально не зависит от расстояния d. В действительности, сама функция F (V) зависитот выбранного конкретного маршрута.
Следует обратитьвнимание, что в дополнение к вербальной и математической модели также могут быть использованы другие типы моделей. Например, физические модели могут представлять масштабные модели автомобилей, имитационные модели могут имитировать транспортные потоки в виде случайных процессов, сгенерированных компьютером. В целомихможно использовать везде, где подсистемы исследованных транспортныхсистем обладают хаотическим поведением. Возможность и степень использования всех видов моделейоснована нахарактереи спецификетранспортной системы, которая подлежит исследованию. В последнее время особоевнимание уделяетсяприменению математических и имитационных моделейна транспорте,и несколькоменьшее вниманиеспециальным математическим методам. Эта тенденция является неизбежным следствием бурного развития компьютерных технологий,когда ихскорость и пропускная способность позволяет в режиме реального времени точно решать очень объемные задачитакими универсальными методами как целочисленное и линейноематематическоепрограммирование. В результате этой тенденции несколько снижается интереск специальным методампоиска, которые ранее были необходимы для решениязадачподобных масштабовпри использованиименее мощных компьютеров.
Ссылки на источники1)ЛукинскийВ.С. //Модели и методы теории логистики, 2009. 288 с.2)Подиновский В.В., Ногин В.Д. Паретооптимальные решения многокритериальных задач, 1982. 256 c.
EvseevaAnnaA.PhD,AssociateProfessorof"OrganizationofTransportationandTransportManagement", SaratovStateTechnical University named afterYuriGagarin, Saratovannaevseeva@mail.ru
Krasnikova Darya A.PhD,Associate Professor of "Organization of Transportation and Transport Management", Saratov StateTechnical University named afterYuriGagarin, Saratovdasha747@yandex.ruKazakov Alexander A.Thirdyear studentmajoring"Organization of Transportation and Transport Management", Saratov StateTechnical University named afterYuriGagarin, Saratovkasa0805@yandex.ru
Abstract.This article examines the systematization optimal solutions in multiobjective transportation problems. Reason of usingmathematical and simulation models in solving transport problems.
Keywords.
Transportation problems, mathematical models, optimal solutions, multicriteria problems.
Красникова Дарья АндреевнаКандидат экономических наук, доцент кафедры «Организация перевозок и управление на транспорте», Саратовский государственный технический университет имени Гагарина Ю.А., г. Саратов.dasha747@yandex.ru
Казаков Александр Александровичстуденттретьего курса специальности «Организация перевозок и управления на транспорте», Саратовского государственного технического университета имениГагаринаЮ.А., г.Саратовkasa0805@yandex.ru
СОВРЕМЕННЫЕ ПОДХОДЫ К РЕШЕНИЮМНОГОКРИТЕРИАЛЬНЫХ ТРАНСПОРТНЫХ ЗАДАЧАннотация.В данной статьерассматривается систематизация получения оптимальных решений в многокритериальных транспортных задачах.Раскрывается смысл применения математических и имитационных моделей при решениитранспортных задачв настоящее время.
Ключевые слова.Транспортные задачи, математические модели, оптимальные решения, многокритериальные задачи.В современных нестабильных условиях функционирования производственные предприятия испытывают определенные трудности в управлении производственными процессамии процессами транспортировки, как сырья, так и готовой продукции. Это связано с несколькими причинами, такими как:
искажение информациив процессе еепередач;
сложная организационная структура допускает противоречивые команды;
неопределенностьв направлениидеятельности и отсутствие навыковработы.При транспортировке продукциивозникает много серьезных ошибок. Типичными недостатками являются ошибки при передаче информации (неподходящие маршруты, неуместная скорость,возникновение материального ущерба во время перевозок, невнимание и т.д.).
Рис. 1. Организационная схема производственной компанииВербальная модель представляет собой, как мы знаем, краткое словесное описание проблемы с использованием технических терминовсоответствующей области. Вербальные модели в задачах исследования операций обычно содержат список данных по умолчанию, описание априорных заключенийобискомомрешении, ограничения и решения вопроса о приемлемости критериев качества.Постановка задачи в форме словесноймодели обычнопредставляет собойне один вид деятельности, анесколько раз циклически повторяющийся процесс постепенного совершенствования и доработки. При этом, модель адаптирована в соответствии с данными, известными заранееиновыми, полученнымис учетом замечаний экспертов к предыдущей версии и, наконец, принимая вовниманиевозможности математических методов и вычислительной техники нужно времядля получениярешения.
Каждый цикл как правилосодержит:1. Определение множества решений(с результатом обработки информации или материалов)2. Созданиеограничений(например, условия допустимости решения)3. Формулировку критериев качества(краткое описание оптимального решения)4. Указание, с учётом данных, полученных в пунктах с 1 по 3, информации, необходимойдля определения наиболее рационального решения.В данном контексте в качестве примера можно рассматривать задачу развозагруз по сети магазинов, находящейся на улицах города, используя грузовые автомобили. Решение задачисостоит в поиске оптимального маршрутадоставкигрузов.При формулированииограниченийнеобходимо убедиться, что непропущеноникаких существенных лимитов, и наоборот, чтоне включенынеуместныеили ненужные. В нашем случаеиспользуется ограничение,вытекающее из требованияДиректорЗаместитель по производствуЗаместитель по финансовым вопросамОтдел по строительству и развитиюЭкономический отделЛогистический отделОтдел снабженияОтдел продажСклад сырья1 складпромежуточный склад2 складсклад продуктовчтопоставкагруза должна осуществляться вовсе магазины без повторных заездов. Дополнительнымиограничениямимогут служитьи другие требования(например, часы работы).Критерий качества,асоответственно, егоколичественное выражениеможет быть представлено в виде целевой функциисозданияи оценкиразличных аспектов перехода от субкритериев к интегральномукритерию. В нашем примере рассматриваютсятакиеограничениякак:минимальное времяработытранспортного средства, скоростьдоставкигруза вмагазиныили наименьшийрасход топлива. Очевидно, что в конкретной ситуации, эти критерии могут конфликтовать. Выбор интегральногокритерия, следовательно, не должен быть заранее решен. В каждом конкретном случае интегральныйкритерий может видоизменятьсяв зависимости от требований клиентаи накладываемых ограничений[1].В качестве исходных данных рассмотрим маршруттранспортного средства, общийобъемагрузов, погруженных в кузов, скоростной режим транспортного средства с учетом загруженности дорог в городеи т.д.Математическая модель в данном случае является словесной модельюв математических терминах, с использованием математических символов. Еёсозданиетребует хорошего знания моделируемых процессов и математических средств, которые доступны на данном этапе. Создание математической модели часто бывает сложным, выбор может быть неоднозначным, так как не существует и однозначныхметодов отбора.Рассмотрим используемые на современном этапе математические модели и методы решения задач в области транспорта. Можно выделитьтакие фазы решения как:обработка, настройка и тестирование программы, расчет, его толкование и применение, возможностьреализации с учетом ресурсов, которые доступны (аппаратное и программное обеспечение), а также спецификапроблемы.Из вышесказанного ясно, в решениипоставленной задачинеобходимо пройти несколько этапов,вкоторых задача последовательно разделяется на несколько подзадач. Единственнымспособом являетсясистематический подход, когда происходитразработкаединой методологии для решения задач оптимизации,сформулированныхв транспортных системах. Такая общая методология включает в себя:• описание проблемы и соответствующие методы оптимизации,
• реализациюалгоритмовоптимизации с помощьюкомпьютерных технологий;
• подготовкуисходных данных и выводрезультатов
• работу и управление оператора связис вычислительной системой,
• возможность использования искусственного интеллекта.Результатыиспользуются всистемахподдержки принятия решений, то есть в качестве основы для планирования и управления транспортными процессами. Эти данныемогут быть использованы для решения задачв реальном времени в качестве основы для принятия долгосрочных плановых решений. Определение и создание единой методологиидля решения оптимизационных задач, сформулированных в транспортных системах(а не в движении), позволит повысить производительность транспортных систем за счет ускорения процесса решения поставленных задач. В связи с созданием модели (словеснойили математической) можностолкнуться струдностями на этапе разработкисоответствующих критериев оптимальности. Кроме того, многиепрактическиезадачипредставлены вмногокритериальной форме.Такиетребования к продукции, как легкость, прочностьи дешевизнане могут быть удовлетворены одновременно с высшей степенью качества. Улучшение любых двух из этих свойствбудутухудшать третье.Другим примером могутбыть требования в видебыстрогопроизводства и высокого качества, низкой цены, удобства доступактранспортным услугамконкретного города или региона. Решениемногокритериальных задачвпервые предложилв 1896 году итальянский экономист и социолог В.Парето (1848 1923). Им было введено понятие «оптимальноерешение» это решение, в котором любой параметрможет быть улучшен только за счет деградации другого[2]. Предположим, что возможно решение X, то есть решение, которое удовлетворяет всем условиям работы и оценивается по нескольким количественным показателям или субкритериямK1(X), ..., Kn(X). Исходя из этого, критерии всегда могутбыть определены«лучшим»решением, котороебудет соответствовать максимальному значению каждого критерия.Тогдарешение X'доминируетнадрешением X", когда для всех рассматриваемых субкритериев:K1(X')
≥K1(X"),…,Kn(X')≥Kn(X") (1)
и когда по крайней мере одно из этих неравенств оказывается равнымn, этогоне происходит. Стоит отметить отношениядоминирования,такие как X'� X"; Два решения X' иX'' для которых они не действуютилиX' > X'' илиX''> 'X, назовем взаимным недоминированием. Совокупность всех решений, к которым нет решения, которое будет доминировать, мы называем недоминированныммножеством, и каждый элемент множества недоминированиямы называем Паретооптимальнымрешением.Пример, иллюстрирующий понятия, введенных только в случае двух критериев K1а К2представлен на рисунке 2.Множество пар значений K1(X),К2(Х) для всех допустимых решений Xпоказанокак областьK, включая границы. Часть границы соответствующих паретооптимальным решениям указано жирнойлинией, включая точки А, В и D, опуская точку C. Именно на этих участках не может произойти увеличениеодногоиз критериев без увеличениявторого.
Рис. 2 Паретооптимальный набор двухкритериев
Другой возможный подход к многокритериальной оптимизации можно рассмотретьнаследующем примере.При движениина машине известна(хотя бы приблизительно) зависимость расхода топлива отвыбраннойскорости, S = F (V), л/км. Потреблениев связи ссопротивлениемвоздуха возрастает с увеличением скорости. С другой стороны, необходимо принимать во внимание стоимость потерянного времени участников перевозки.Еслиизвестна общая стоимостьпроезда пассажиров, которая рассчитывается по среднечасовой платеС1руб/ч и если C2это цена за 1 литр топлива, и если транспортное расстояние dкм, то расходы на транспортировкуЗ(V), которые зависят от средней скорости, могут быть выражены в виде: З(v) = C1+ C2f(v)d. (2)В результате минимизации функции получаем,что оптимальная средняя скорость движения, формально не зависит от расстояния d. В действительности, сама функция F (V) зависитот выбранного конкретного маршрута.
Следует обратитьвнимание, что в дополнение к вербальной и математической модели также могут быть использованы другие типы моделей. Например, физические модели могут представлять масштабные модели автомобилей, имитационные модели могут имитировать транспортные потоки в виде случайных процессов, сгенерированных компьютером. В целомихможно использовать везде, где подсистемы исследованных транспортныхсистем обладают хаотическим поведением. Возможность и степень использования всех видов моделейоснована нахарактереи спецификетранспортной системы, которая подлежит исследованию. В последнее время особоевнимание уделяетсяприменению математических и имитационных моделейна транспорте,и несколькоменьшее вниманиеспециальным математическим методам. Эта тенденция является неизбежным следствием бурного развития компьютерных технологий,когда ихскорость и пропускная способность позволяет в режиме реального времени точно решать очень объемные задачитакими универсальными методами как целочисленное и линейноематематическоепрограммирование. В результате этой тенденции несколько снижается интереск специальным методампоиска, которые ранее были необходимы для решениязадачподобных масштабовпри использованиименее мощных компьютеров.
Ссылки на источники1)ЛукинскийВ.С. //Модели и методы теории логистики, 2009. 288 с.2)Подиновский В.В., Ногин В.Д. Паретооптимальные решения многокритериальных задач, 1982. 256 c.
EvseevaAnnaA.PhD,AssociateProfessorof"OrganizationofTransportationandTransportManagement", SaratovStateTechnical University named afterYuriGagarin, Saratovannaevseeva@mail.ru
Krasnikova Darya A.PhD,Associate Professor of "Organization of Transportation and Transport Management", Saratov StateTechnical University named afterYuriGagarin, Saratovdasha747@yandex.ruKazakov Alexander A.Thirdyear studentmajoring"Organization of Transportation and Transport Management", Saratov StateTechnical University named afterYuriGagarin, Saratovkasa0805@yandex.ru
Abstract.This article examines the systematization optimal solutions in multiobjective transportation problems. Reason of usingmathematical and simulation models in solving transport problems.
Keywords.
Transportation problems, mathematical models, optimal solutions, multicriteria problems.
