Публикации Использование алгоритма Литтла для решения оптимизационных задач

Всероссийский сборник статей и публикаций института развития образования, повышения квалификации и переподготовки.

Язык издания: русский
Периодичность: ежедневно
Вид издания: сборник
Версия издания: электронное сетевое
Публикация: Использование алгоритма Литтла для решения оптимизационных задач
Автор: Красносельцева Ирина Евгеньевна

ИСПОЛЬЗОВАНИЕ АЛГОРИТМА ЛИТТЛА ДЛЯ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧКрасносельцева Ирина Евгеньевна студентка 3 курса, институт экономики и управления, Самарский национальный исследовательский университет им. С.П. Королёва, г. СамараНа сегодняшний день транспортная логистика играет одну из ключевых ролей в современной экономике. С ускорением темпов производства возрастает интерес к изучению и внедрению новых методов, которые повышают эффективность функционирования транспортных систем.Разработка математических моделей транспортных потоков позволяет существенно сократить временные интервалы поставок, помогая сократить затраты на хранение и тран спортировку грузов, повышая информативность и уровень сервиса организации.В условиях современной рыночной экономики особое внимание уделяется сфере транспортных услуг, расходы на которые составляют значительную долю затрат – 20-40%. В связи с этим оптимизация логистических расходов является актуальной проблемой современного рынка. Поэтому перед современной логистикой встает проблема поиска приемлемого маршрута, по которому транспортируемый объект доставляется в кратчайший срок с минимальными затратами.Изучение логистических процессов зародилось в Древней Греции, где подразумевало под собой "счетное искусство". Первым исследователем Генриху Жомини считал, что в это понятие охватывает ряд важных вопросов, главными из которых были планирование, управление и снабжение. Бурное развитие логистические подходы получили в период Второй мировой войны, когда остро встал вопрос об эффективном взаимодействии оборонной промышленности и тыловых баз снабжения. Постепенно методы транспортировки перешли из военной области в промышленный комплекс. Опыт промышленно развитых стран показывает, что логистике принадлежит стратегически важная роль и в современном бизнесе.При решении конкретной оптимизационной задачи необходимо выбрать математический метод, который приводил бы к конечным результатам с наименьшими затратами или же давал возможность получить наибольшую выгоду. Существует множество методов решения подобных задач[1]:

Методы классического исследования функции, подразумевающие анализ поведения и поиск экстермальных значений;

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

Метод множителей Лагранжа заключается в отыскании условного экстремума с помощью функции. Применяют для решения задач такого же класса сложности, но при наличии ограничений типа равенств на независимые переменные;

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

Методы линейного и нелинейного программирования

Задача коммивояжёра

В своей работе мы бы хотели акцентировать изучение логистических потоков именно на решении оптимизационной задачи коммивояжёра.Точно неизвестно, когда проблему коммивояжера исследовали впервые. В 1954 году была сформулирована в виде задачи дискретной оптимизации и применили для её решения метод отсечений: для некоторой группы городов требуется найти кратчайший маршрут с посещением каждого города один раз и с возвращением в начальную точку маршрута[2].Рассмотрим задачу сформированных транспортных маршрутов в постановке через математическую модель на примере ОАО «Жигулевское пиво».Основными точками реализации продукции ОАО «Жигулевское пиво» являются фирменные магазины завода. Сеть официальной розничной торговли включает в себя шесть точек сбыта. Необходимо совершить поставку кегель (по 50 л) в каждый из фирменных магазинов. Доставка осуществляется на изотермическом фургоне ГАЗ-330210, вместимость которого составляет 50 кегель.Потребности каждого магазина составляет соответственно: 25,11,10,23,12,16 единиц груза. Для решения задачи необходимо составить матрицу транспортных затрат𝑐𝑖𝑗.В данном случае элементами матрицы служат соотношения затрат, включающих километраж, трудовые расходы и время в пути, рассчитанных для транспортной ситуации в г.о. Самара в понедельник 9:00[3]. Необходимо определить маршрут, который охватывает основной склад предприятия и все пункты назначения единожды, а суммарные затраты должны быть сведены к минимуму.Для решения задачи воспользуемся модификацией алгоритма Литтла, который включает в себя следующие этапы [4]:

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

𝑞 =25 + 11 + 10 + 23 + 12 + 1650+ 1 = 2−14 2−933136343 247−486 24446533−24225−43 2453( 26585−63745−) 2−14 0−714−264 01( 033134121 1320−0200100010

Вычисление оценок. Нижней оценкой Н оптимального значения критерия будет сумма вычитаемых минимальных элементов. Эта оценка увеличивается на сумму q минимальных элементов нулевой строки и q минимальных элементов нулевого столбца. Полученная оценка является оптимальным значением критерия задачи. Для вычисления верхней оценки W ищется допустимое решение эвристическим методом: в совокупность

переходов последовательно включаются те коммуникации (i,j), у которых наибольшие характеристики и доставка груза 𝑎𝑗 к которым возможна с учетом грузоподъёмности транспортных средств.𝐻0 = 0 + 2 + 3 + 2 + 2 + 3 + 2 + 0 + 1 + 0 + 0 + 0 + 1 + 0 + 0 = 16−044 01−713−254 011233043411113100−011003−11 1(021020123352−32−)𝑊0 = 16 + 3 = 19

Ветвление и отсев неперспективных подмножеств. Множество решений разбивается на

2 подмножества. Для того выбирается коммуникация (𝑖0, 𝑗0) с наибольшей характеристикой. В одно подмножество включаются все решения, содержащее переход (𝑖0, 𝑗0), в другое – решение, не содержащее этого перехода. Для каждого подмножества корректируются матрицы затрат и находятся оценки сверху и снизу оптимального значения критерия. Отсев неперспективных подмножеств реализуется в соответствии с принципом метода ветвей и границ – если прогноз Н оптимального значения критерия на подмножестве больше достигнутого значения W на каком-либо другом подмножестве. Порождение и отсев подмножеств повторяется до тех пор, пока не останется одно не исключенное множество, на котором достигнуто прогнозное значение W=H. В знаменателе дроби указан прогноз оптимального значения критерия. На множестве верхняя граница 10 вершины совпала с исходной, следовательно, найдено оптимальное решение.Рис. 1. Ветвление подмножествОптимальный план перевозок потребует двух транспортных средств. Минимальные затраты на перемещение составят 18 единиц. По первому маршруту (0,1,4,0) будет перевезено 37 единиц груза, по второму (0,5,2,3,6,0) – 49 единиц.В процессе исследования была рассмотрена специфика транспортной логистики современного общества и влияние математических методов ее регулирования и получены следующие выводы:

Внедрение математических методов в деятельность организации способствует регулированию финансового потока

Снижение транспортных затрат позволяет эффективно перераспределять денежные ресурсы, внедряя излишек в производство достижения НТП, повышая квалификацию трудовых и научных кадров, увеличивая темпы производства, улучшая качество создаваемой продукции

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

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

Математические модели и методы в логистике: учеб. пособ. / В.С. Лубенцова. Под редакцией В.П. Радченко: - Самара. Самар. гос. техн. ун-т, 2008, - 157 с.: ил.

Литл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм для решения задачи о коммивояжере // Экономика и математические методы. 1965. Т. 1. Вып. 1.С. 94–107.

//API Google maps

Костюк Ю.Л., Пожидаев М.С. Приближенные алгоритмы решения сбалансированной задачи k коммивояжеров // Вестник Томского государственного университета. Серия

«Управление, вычислительная техника и информатика», 2008. № 1 (2).С. 106–112.