Методы многокритериальной оптимизации транспортной задачи
Модификация классических методов решения задач многокритериальной оптимизации под особенности транспортной задачи. Составление программного комплекса в среде Visual Studio на языке программирования С# для решения многокритериальной транспортной задачи.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 27.02.2018 |
| Размер файла | 31,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Финансовый Университет при правительстве Российской Федерации, Москва
Методы многокритериальной оптимизации транспортной задачи
А.В.Нуркаева
Аннотация
многокритериальный транспортный программный studio
Статья посвящена разработке решения многокритериальной транспортной задачи. В качестве критериев брались минимальные стоимость перевозок, время перевозок, накладные расходы и максимальный объем перевозок. Классические методы решения задач многокритериальной оптимизации модифицированы и приспособлены под особенности транспортной задачи. В среде Visual Studio на языке программирования С# составлен программный комплекс, позволяющий решать задачу многокритериальной транспортной задачи одним из методов: линейной свертки, главного критерия, уступок или методом гарантированного результата, и сравнивать полученные результаты.
Ключевые слова: четырехкритериальная транспортная задача, метод потенциалов, начальная симплексная таблица, метод главного критерия, метод уступок, лямбда-задача, метод линейной свертки, транспортные перевозки, программная реализация, мультипликативная свертка, метод гарантированного результата
Введение
Развитию транспортных перевозок уделяется много внимания: расширяются транспортные сети, максимизируется их пропускная способность, модернизируются дороги, появляются новые виды транспорта и транспортных средств, автоматизируются процессы погрузки-разгрузки товаров, совершенствуется логистика транспортных перевозок.
Для заказчиков транспортных услуг необходимы решения транспортных задач для осуществления перевозок с минимальными издержками и с большим экономическим эффектом.
К настоящему времени достаточно полно исследована однокритериальная транспортная задача, рассмотрены различные ее постановки, комбинации с другими задачами производства и хранения продукции, найдено и обосновано достаточно методов ее решения, на основе которых разработаны компьютерные приложения решения классических транспортных задач. Для многокритериальных задач описаны лишь направления решения, например, с использованием методов Парето.
Многокритериальная транспортная задача рассмотрена в работах А.В. Золотарюка [1], который, проанализировав процессы транспортных перевозок и факторы, снижающие их эффективность, сформулировал математическую постановку транспортной многокритериальной оптимизационной задачи, и рассмотрел пути ее решения на основе парето-оптимальных методов и с помощью интеллектуального нейросетевого прогнозирования. Также двухкритериальная транспортная задача рассмотрена О.В. Серой [3]. Она разработала итерационный алгоритм и доказала, что полученное решение парето-оптимально. Ю.А. Осыкина и Г.Д. Чернышова [2] рассмотрели многокритериальную транспортную задачу с разрывными функциями и целочисленными переменными.
В данной статье для четырехкритериальной транспортной задачи, сформулированной А.В. Золотарюком, разработан алгоритм решения, который положен в основу работы программного комплекса. Известные стандартные методы решения многокритериальных задач приспособлены к решению транспортной многокритериальной задачи.
Математическая модель четырехкритериальной транспортной модели
Сформулируем математическую постановку задачи многокритериальной оптимизации транспортных перевозок с учетом одного цикла.
Найти оптимальные параметры транспортной сети
;
исходя из условий:
· минимума времени нахождения в пути из исходного в конечный пункт назначения Тпут:
· минимума общей себестоимости перевозки единицы груза Сед:
· максимума общего количества перемещенных грузов Vтр:
· минимума общих накладных расходов при доставке груза Rоб:
.
Решение многокритериальной транспортной задачи
Нормируем полученные критерии:
, ,
, .
Рассмотрим применение метода гарантированного результата, который предполагает максимизацию следующей функции
.
Введя обозначение
получим задачу линейного программирования
при ограничениях
.
Другими словами, нам нужно найти минимальное , при котором существует допустимый план решения задачи. Поиск можно осуществлять разными способами. Во-первых, решением -задачи. Но програмно этот способ реализовать достаточно сложно. Во-вторых, перебирая значения с заданным шагом с 1 до 0, допустим, с шагом 0.01 (так как содержательный смысл - процент, то с точностью до 1 процента). В этом случае задача решается за 101 шаг, а в общем случае, за (1/точность+1) шаг. Но на наш взгляд наиболее эффективно вести перебор методом дихотомии по нижеизложенной схеме. Заметим, что при ограничения принимают вид
.
Но так как нормализованные критерии точно имеют положительные значения, меньшие единицы, то задача имеет допустимое решение. А вот при ограничения с учетом положительности и нормализации принимают вид
и здесь возможны две ситуации:
1) если допустимое решение существует, то оно является идеальным, так как оно минимизирует те критерии, которые нужно минимизировать и максимизирует те критерии, которые нужно максимизировать. Также напомним, что этот случай на практике встречается крайне редко. Как бы там ни было, допустимое решение в данном случае решение оптимально. Задача решена.
2) Если допустимое решение не существует, то применим метод дихотомии. А именно, обозначим , . Требуемую точность обозначим за . Пока находим .
Если при допустимое решение задачи есть, то и продолжаем искать минимальное , при котором существует допустимое решение среди меньших его значений, то есть на отрезке . Если же при допустимого решения не существует, то и продолжаем искать минимальное , при котором существует допустимое решение среди больших его значений, то есть на отрезке .
Количество переборов при использовании данного метода дихотомии - . В случае, если точность равна 1 процент, количество переборов снижается со 101 в случае простого перебора до 8.
Программный комплекс
Создано программное приложение для решения многокритериальной транспортной задачи, описанной в [1], в инструментальной среде Visual Studio Professional 2015. Приложение позволяет воспользоваться одним из четырех методов: методом уступок, линейной свертки, методом главного критерия и гарантированного результата. Метод линейной свертки и первый этап метода уступок позволяют применить метод потенциалов. Остальные этапы метода уступок и метод главного критерия используют обычный симплекс-метод решения задачи линейного программирования. Причем для построения первоначального базисного плана используется построение искусственного базиса. Метод гарантированного результата применяет симплекс-метод только для построения первоначального опорного плана, так как ищет минимальное значение параметра, при котором в принципе решение возможно.
Литература
1. Золотарюк А.В. Математическая модель многокритериальной оптимизации транспортных перевозок. // Инновационные технологии в науке и образовании. 2015. № 1(1). С. 317-320.
2. Осокина Ю.А, Чернышова Г.Д. Многокритериальная транспортная задача с разрывной целевой функцией. // Вестник, серия: системный анализ и информационные технологии. 2008. № 2. С.: 10-12.
3 Серая О.В. Двухкритериальная транспортная задача // Вестник Национального технического университета «Харьковский политехнический институт». НТУ «ХПІ», 2009. №4. - С. 64-68.
4. Боженюк А.В., Герасименко Е.М. Разработка алгоритма нахождения максимального потока минимальной стоимости в нечеткой динамической транспортной сети // Инженерный вестник Дона. 2013, №1. URL: ivdon.ru/magazine/archive/n1y2013/1583.
5. Нечитайло Н.М., Мартемьянов С.В., Панасов В.Л. Транспортная задача по критерию минимума суммарного времени и модификация метода Балинского для её решения // Инженерный вестник Дона. 2016, №1. URL: ivdon.ru/ru/magazine/archive/n4y2016/3796.
6. Dawes R. The robust beauty of improper linear models in decision-making. /In: « Judgement under uncertainty: Heuristics and biases». Cambridge Univ., Press, 1982. - pp. 571-582.
7. McGrimmon K. An overview of multiple objective decision making. /in Multiple criteria, decision-making. Cohrane I., Zeleny M. (Eds). Columbia Univ: South Carolina Press, 1973. pp: 656-667.
8. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. 256 с.
9. Константинова М.А. К вопросу многокритериальной задачи в транспортной логистике // Научное сообщество студентов XXI столетия. Технические науки: сб. ст. по мат. XVIII междунар. студ. науч.-практ. конф. № 3(18). URL: sibac.info/archive/technic/3(18).pdf (дата обращения: 05.05.2017)
10. Емельянов С.В., Ларичев О.И. Многокритериальные методы принятия решений. М.: Знание, 1985. 32 с.
References
1. Zolotaryuk A.V. Innovatsionnye tekhnologii v nauke i obrazovanii. 2015. № 1(1). pp. 317-320.
2. Osokina Yu.A, Chernyshova G.D. Vestnik, seriya: sistemnyy analiz i informatsionnye tekhnologii. 2008. № 2. pp: 10-12.
3 Seraya O.V. Vestnik Natsional'nogo tekhnicheskogo universiteta «Khar'kovskiy politekhnicheskiy institut». NTU «KhPІ», 2009. №4. pp: 64-68.
4. Bozhenyuk A.V., Gerasimenko E.M. Inћenernyj vestnik Dona (Rus), 2013, №1. URL: ivdon.ru/magazine/archive/n1y2013/1583.
5. Nechitaylo N.M., Martem'yanov S.V., Panasov V.L. Inћenernyj vestnik Dona (Rus), 2016, №1. URL: ivdon.ru/ru/magazine/archive/n4y2016/3796.
6. Dawes R. The robust beauty of improper linear models in decision-making. In: «Judgement under uncertainty: Heuristics and biases». Cambridge Univ., Press, 1982. pp: 571-582.
7. McGrimmon K. An overview of multiple objective decision making./In Multiple criteria decision making. Cohrane I., Zeleny M. (Eds). Columbia Univ: South Carolina Press, 1973. pp: 656-667.
8. Podinovskiy V.V., Nogin V.D. Pareto-optimal'nye resheniya mnogokriterial'nykh zadach. [Pareto optimal decision of multicriterial problems] M.: Nauka, 1982. 256 p.
9. Konstantinova M.A. Nauchnoe soobshchestvo studentov XXI stoletiya. Tekhnicheskie Nauki: sb. st. po mat. XVIII mezhdunar. stud. nauch.-prakt. konf. № 3(18). URL: sibac.info/archive/technic/3 (18).pdf (data obrashcheniya: 05.05.2017).
Размещено на Allbest.ru
Подобные документы
Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования.
дипломная работа [2,4 M], добавлен 20.11.2010Особенности решения транспортной задачи распределительным методом и анализ результатов. Построение математической модели, алгоритма. Создание программы для решения транспортной задачи распределительным методом в программной среде Borland Delphi 7.
курсовая работа [1000,7 K], добавлен 23.06.2012Сущность и назначение основных алгоритмов оптимизации. Линейное программирование. Постановка и аналитический метод решения параметрической транспортной задачи, математическая модель. Метод решения задачи об оптимальных перевозках средствами MS Excel.
курсовая работа [465,6 K], добавлен 24.04.2009Методы решения задач линейного программирования: планирования производства, составления рациона, задачи о раскрое материалов и транспортной. Разработка экономико-математической модели и решение задачи с использованием компьютерного моделирования.
курсовая работа [607,2 K], добавлен 13.03.2015Описание математических методов решения задачи оптимизации. Рассмотрение использования линейного программирования для решения транспортной задачи. Применение симплекс-метода, разработка разработать компьютерной модели в Microsoft Office Excel 2010.
курсовая работа [1,5 M], добавлен 24.05.2015Сущность и постановка транспортной задачи для n переменных, их виды, применение и пример решения в MS Excel. Управляющие структуры ветвления Maple языка (if предложение). Решение транспортной задачи в векторных координатах для двух и трёх матриц.
дипломная работа [109,3 K], добавлен 12.01.2011Программа для решения транспортной задачи. Метод потенциалов, его математический смысл и порядок действий по его применению. Математические методы решения транспортных задач. Вычисление стоимости перевозок, расхода топлива, общей прибыли и окупаемости.
курсовая работа [33,7 K], добавлен 20.11.2008Описание алгоритма решения транспортной задачи по планированию перевозки зерна. Ход решения задачи вручную, в программе TORA методом наименьшего элемента, с помощью MS Excel. Разработка программы для решения задачи в общем виде средствами Delphi.
курсовая работа [2,5 M], добавлен 22.11.2012Создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей. Схема алгоритма основной программы. Основные шаги алгоритма решения транспортной задачи. Инструкция по эксплуатации программы и обзор результатов ее выполнения.
курсовая работа [2,0 M], добавлен 12.02.2013Составление программы для расчета начального базиса сбалансированной транспортной задачи, где суммарные запасы поставщиков равны суммарным запросам потребителей. Алгоритм метода потенциалов. Пример решения транспортной задачи методом наименьшей стоимости.
отчет по практике [991,3 K], добавлен 06.12.2013
