Едыгаров И.А.
ЗАДАЧИ С ТРАНСПОРТНОЙ ИНТЕРПРЕТАЦИЕЙ ИЗ РАЗНЫХ КЛАССОВ СЛОЖНОСТИ *
Аннотация:
в работе рассмотрены хорошо известные задачи: транспортная задача и задача коммивояжёра, относящиеся к разным классам сложности, но объединённые транспортной проблематикой, точнее, имеющую ясную транспортную интерпретацию. Несмотря на то, что они хорошо известны в исследовании операции, в логистической учебной литературе их приводят редко
Ключевые слова:
транспортная задача, задача коммивояжёра, класс сложности, задача линейного программирования, метод потенциалов
УДК 519.6
Едыгаров И.А.
старший преподаватель кафедры прочности конструкции (ПК)
Казанский национальный исследовательский технический университет
(г. Казань, Россия)
ЗАДАЧИ С ТРАНСПОРТНОЙ ИНТЕРПРЕТАЦИЕЙ
ИЗ РАЗНЫХ КЛАССОВ СЛОЖНОСТИ
Аннотация: в работе рассмотрены хорошо известные задачи: транспортная задача и задача коммивояжёра, относящиеся к разным классам сложности, но объединённые транспортной проблематикой, точнее, имеющую ясную транспортную интерпретацию. Несмотря на то, что они хорошо известны в исследовании операции, в логистической учебной литературе их приводят редко.
Ключевые слова: транспортная задача, задача коммивояжёра, класс сложности, задача линейного программирования, метод потенциалов.
Задача Монжа — Канторовича или, просто, транспортная задача относиться к классу сложности P и не вызывает сложности по вычислительной реализации. Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году. Прогресс в решении проблемы был достигнут в СССР математиком и экономистом Леонидом Канторовичем, который в последствии получил Нобелевскую премию.
Имеется m пунктов отправления груза и объемы отправления по каждому пункту а1, а2, а3, …, аm. Известна потребность в грузах b1, b2, …, bn по каждому из n пунктов назначения. Задана матрица стоимостей доставки единицы груза по каждому варианту cij (i= 1, 2, …, m, j = 1, 2, …, n).
Необходимо рассчитать оптимальный план перевозок, т.е. определить, сколько груза должно быть отправлено из каждого I-го пункта отправления (от поставщика) в каждый j-й пункт назначения (до потребителя).
Данные представлены в общем виде в Таблице1:
Таблица 1. Формулировка задачи в табличном виде.
|
Потребители
Поставщики
|
B1 |
B2 |
B3 |
B4 |
Запасы (объемы отправления) |
|
А1 |
c11 x11 |
c12 x11 |
…………. |
c1n x11 |
a1 |
|
A2 |
c21 x21 |
c22 x22 |
…………. |
c2n x2n |
a2
|
|
………… |
|
|
…………. |
|
|
|
Am |
cm1 xm1 |
cm2 xm2 |
…………. |
cmn xmn |
am |
|
Потребность |
b1 |
b2 |
…………. |
bn |
|
Транспортная задача называется закрытой, если суммарный объем отправляемых грузов
() равен суммарному объему потребности в этих грузах по пунктам назначения ():
Если такого равенства нет, т.е. потребности выше запасов и наоборот, то задачу называют открытой.
Математическая модель задачи следующая:
Все грузы из I-х пунктов должны быть отправлены, т.е. =ai, i=1,2,…,m
Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:
=bj, j=1,2,…,n
Суммарные объемы отправления должны равняться суммарным объемам назначения:
Должно выполняться условие не отрицательности переменных xij≥0, I=1,2,…,m, j=1,2,…,n
Перевозки необходимо осуществлять с минимальными транспортными издержками (функция цели):
Обычно решается методом потенциалов [1], так как он использует внутреннюю структуру задачи и более оптимален чем симплексный метод например.
Алгоритм метода потенциалов включает следующие этапы:
Списанная процедура повторяется несколько раз (итераций) пока не будет найдено оптимальное решение. Вычислительный алгоритм для каждой итерации не меняется.
В том случае, если транспортная задача является открытой, ее можно привести к закрытому виду, вводя фиктивного потребителя или поставщика, записав на него излишки и присвоив ему стоимость перевозок cij = 0.
Другая известная транспортная задача – задача бродячего торговца или задача коммивояжёра, в англоязычной литературе используется сокращение TSP (travelling salesman problem), относится к классу NP-трудных задач и является трудно вычислительной и уже при относительно небольшом числе городов. Это задача отыскания минимального гамильтонова цикла в графе (Рис. 1.):
При количестве городов больше Она не может быть решена даже оптимальным перебором, например динамическим программированием Беллмана, никакими теоретически мыслимыми компьютерами за реальное время.
Её можно сформулировать как задачу дискретного программирования [2] в виде модели:
Где -матрица расстоянии между городами, а
Естественно, на практике приходится решать задачи, в формулировке которых присутствует вероятность или многовариантность или и то и другое [3].
В задаче, если к узлам в качестве свойства приписать некоторую вероятность рi существования этого узла (0 ≤ pi ≤ 1), а такое происходит, когда пункты назначения, т.е. узлы, дислоцируются не постоянно, модель приобретает вид:
А если для переезда из одного пункта в другой, существуют варианты, например, с помощью различных видов транспортных средств (автомобильный, железнодорожный или авиационный). Каждый вариант характеризуется временем переезда и стоимостными затратами, то требуется определить маршрут коммивояжера, которому соответствует минимальный максимум времени переезда из города в город, а суммарные затраты не превышают заданной величины. Такая многовариантная задача коммивояжера уже относится к классу минимаксных задач и имеет следующую модель:
здесь - номер варианта переезда из i-го города в j-й, , - время и стоимостные затраты, связанные с переездом из i-го города в j-й, соответствующие -му варианту, C - допустимые суммарные затраты.
СПИСОК ЛИТЕРАТУРЫ:
Номер журнала Вестник науки №12 (69) том 5 ч. 2
Ссылка для цитирования:
Едыгаров И.А. ЗАДАЧИ С ТРАНСПОРТНОЙ ИНТЕРПРЕТАЦИЕЙ ИЗ РАЗНЫХ КЛАССОВ СЛОЖНОСТИ // Вестник науки №12 (69) том 5 ч. 2. С. 152 - 158. 2023 г. ISSN 2712-8849 // Электронный ресурс: https://www.вестник-науки.рф/article/12171 (дата обращения: 19.05.2024 г.)
Вестник науки СМИ ЭЛ № ФС 77 - 84401 © 2023. 16+