Транспортная задача с промежуточными пунктами

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Транспортная задача с промежуточными пунктами

Н.Н. Пашков

Аннотация

В работе обсуждается актуальность разработки универсальной математической модели в матричной форме записи транспортной задачи с промежуточными пунктами и предложен аналитический метод её решения.

Ключевые слова: универсальная математическая модель, транспортная задача с промежуточными пунктами, матричная форма записи, аналитический метод решения задачи.

Annotation

The paper discusses the relevance of the development of a universal mathematical model in the matrix form of recording the transport problem with intermediate points and proposes an analytical method for its solution.

Key words: universal mathematical model, transport problem with intermediate points, matrix notation, analytical method for solving the problem.

Пашков Николай Николаевич

Доктор технических наук, профессор кафедр «Логистические транспортные системы и технологии» и «Цифровые технологии управления транспортными процессами»

Российский университет транспорта, Россия, Москва

Pashkov Nikolay Nikolaevich

Doctor of Technical Sciences, Professor of the departments "Logistic transport systems and technologies" and "Digital technologies for managing transport processes"

Russian University of Transport, Russia, Moscow

Ссылка для цитирования:

Пашков, Н. Н. Транспортная задача с промежуточными пунктами / Н. Н. Пашков // Цифровая трансформация транспорта: проблемы и перспективы: материалы Национальной научно-практической конференции, посвященной 125-летию РУТ (МИИТ), Москва, 29 сентября 2021 года. - Москва: Российский университет транспорта, 2021. - С. 140-146.

Введение

Одно практическое важное применение классической транспортной задачи связано с доставкой товара от источника к стоку по маршруту, проходящему через промежуточные пункты. Задачу выбора плана перевозок товаров от источников к стокам с минимальными транспортными затратами, с учетом потребностей промежуточных пунктов, в исследовании операций называют транспортной задачей с промежуточными пунктами (ТЗ с ПП) [1].

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

- запасами в сети розничной торговли,

- потоками электроэнергии разветвленных сетей электроснабжения,

- трафиком телекоммуникационных сетей,

- порожним парком подвижного состава транспортной сети, и т.п.

В основе решения ТЗ с ПП лежит классическая транспортная задача [2, 3]. Известны различные частные постановки ТЗ с ПП, которые требуют предварительного разделения всех пунктов на три класса: поставщики, хранилища, промежуточные пункты. Такие постановки требуют достаточно трудоемкого предварительного анализа и сортировки исходных данных.

Рассмотрим универсальную постановку ТЗ с ПП, не требующую классификации и сортировки пунктов отправления и назначения на источники, хранилища и стоки.

Постановка классической транспортной задачи

На заданном полигоне транспортной сети требуется составить план перевозок грузов с минимальной общей стоимостью транспортной работы. Введем следующие обозначения:

- запас груза в пункте отправления ();

- потребность груза в пункте назначения ();

- стоимость доставки единицы груза из пункта в пункт .

Обозначим через планируемое количество единиц груза для перевозки из пункта в пункт .

В принятых обозначениях:

В простейшем случае должны выполняться следующие очевидные условия:

Математическая модель классической транспортной задачи

Требуется найти минимальное значение целевой функции :

при условиях:

Матричная модель транспорной задачи с промежуточными пунктами

Поставим в соответствие транспортной сети связный граф - без изолированных вершин, петель и кратных ребер, - множество вершин (пунктов отправления и назначения), - множество ребер (участков путей сообщения). В классической транспортной задаче через обозначено планируемое количество единиц груза для перевозки из пункта в пункт по участку . Для формулировки ТЗ с ПП в матричной форме предположим, что любой из пунктов транспортной сети может быть и источником, и стоком.

Обозначим через матрицу инциденций графа:

Условия инцидентности всех вершин и ребер графа запишутся в виде:

С учетом введенных обозначений матричная математическая модель ТЗ с ПП следующая. Требуется найти минимальное значение целевой функции :

при условиях:

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

Численный пример решения ТЗ с ПП

Пусть полигон транспортной сети задан связным графом (рисунок 1).

Рисунок 1 - Граф полигона транспортной сети.

На рис. 1 использованы следующие графические обозначения:

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

- вершина графа (пункт отправления или назначения) и её порядковый номер; число вершин

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

- ребро графа, число над ребром - вес ребра (длина участка), число под ребром - порядковый номер ребра, число ребер .

Исходные численные данные ТЗ с ПП представлены в таблицах 1 и 2.

Таблица 2. Стоимость доставки (расстояния) между пунктами

Представим исходные данные ТЗ с ПП в форме обозначенных в модели (5) - (6) матриц.

Матрица инциденций вершин и ребер:

Вектор длин ребер графа:

Транспонированные векторы начального и конечного распределения запасов:

Решение ТЗ с ПП симплекс-методом, встроенным в надстройку Solver табличного процессора MS Excel, представлено в таблице 3.

Таблица 3. Решение (план перевозок) ТЗ с ПП симплекс-методом

Минимальная транспортная работа, найденная симплекс-методом, т·км.

Аналитическое решение системы уравнений (6) алгебраическим методом [4, 5]:

где - пседвообратная матрица инциденций :

дает следующий вектор грузовых потоков:

где знак «-» указывает направление потока.

Численное значение целевой функции ТЗ с ПП (5):

Очевидно, что план перевозок, найденный алгебраическим методом, дает меньшее значение целевой функции ТЗ с ПП, в сравнении с решением задачи симплекс-методом.

Заключение

Таким образом, универсальная математическая постановка ТЗ с ПП в матричной форме записи, без различения и сортировки пунктов на источники и стоки, дает точное оптимальное решение.

Список литературы

транспортная задача математическая модель

1. Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов / Под ред. В.С. Зарубина, А.П. Крищенко. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2000. - 436 с.

2. Юдин Д.Б., Гольштейн Е.Г. Задачи линейного программирования транспортного типа. - М.: Наука, 1969. - 383 с.

3. Ху Т. Целочисленное программирование и потоки в сетях. - М.: Издательство МИР, 1974. - 520 с.

4. Пашков Н.Н. Транспортная логистика (линейное программирование): Учебное пособие / Н.Н. Пашков. - М.: Прометей, 2020. - 202 с.

5. Нутович В.Е. Современные транспортно-логистические технологии доставки грузов: Монография / В.Е. Нутович, Н.Н. Пашков, О.Н. Ларин, А.П. Кузнецов, Н.Ю. Лахметкина, И.В. Щелкунова, Т.И. Каширцева, В.Л. Коновалов, К.В. Ивлиева. - М.: РУСАЙНС, 2021. - 108 с.

Размещено на Allbest.ru