Сетевое издание
Международный студенческий научный вестник
ISSN 2409-529X

КЛАССИЧЕСКАЯ ТРАНСПОРТНАЯ ЗАДАЧА, РЕШЕННАЯ МЕТОДОМ ПОТЕНЦИАЛОВ

Лозгачёв И.А. 1 Корепанов М.Ю. 1
1 ФГБОУ ВПО «Уральский государственный горный университет»
1. Попов, А.Г. Автомобильные грузовые перевозки / А.И. Афанасьев, Ю.Г. Закаменных. – Е., 2012. – 195 с.
2. Грузовые автомобильные перевозки / А.В. Вельможин, В.А. Гудков, Л.Б. Миротин, А.В. Куликов. – М., 2007. – 559 с.
3. Электронный ресурс [http://www.ati.su/].

Решением этой проблемы впервые заинтересовался Гаспар Монж в 1781 году. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем. И решение этой проблемы (задачи) до сих пор стоит перед поставщиками и потребителями, заинтересованными в оптимизации транспортных процессов на предприятиях. А транспортные процессы, как известно, неотъемлемая часть почти любого производства.

Транспортная задача (задача Монжа – Канторовича) для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. В зависимости от способа представления условий транспортной задачи она может быть представлена в сетевой (схематичной) или матричной (табличной) форме. Транспортная задача может так же решаться с ограничениями и без ограничений. Но в общем виде представляет собой поиск оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение [2]. Условия задачи можно представить следующим образом:

1) Каждый ГОП должен дать потребителям столько продукции, сколько у него есть.

2) Каждый потребитель должен получить столько, сколько ему требуется.

3) Необходимо найти такой вариант плана перевозок, чтобы транспортная работа была минимальной

1. Метод потенциалов

Метод потенциалов линейного программирования применяется при решении задач, связанных с распределением на транспортной сети грузопотоков: закрепление потребителей грузов за поставщиками, распределение парка подвижного состава по АТП, закрепление маршрутов работы подвижного состава за АТП и других задач.

Для решения транспортной задачи воспользуемся методом потенциалов. Запись и решение транспортной задачи методом потенциалов выполняется в таблично-матричной форме.

2. Расстояние между грузопотребителями и грузообразующими пунктами и их потребности

Для решения задачи обозначим через Xij количество тонн груза, которое должно быть перевезено от i-го поставщика j-потребителю. Тогда математическая модель задачи выразится системой уравнений (1.1), а целевая функция, представляющая собой сумму произведений расстояний на соответствующий объем перевозок (Qij) груза в тоннах, уравнением (1.2).

bezs43.wmf; (1.1)

bezs44.wmf (1.2)

Для начала необходимо составить базисный план, он должен быть допустимым, содержать bezs45.wmf загруженных клеток, чтобы загруженные клетки были расположены в порядке вычеркиваемой комбинации.

Таблица 1

Исходные данные

ris19.tiff

Таблица 2

Базисный план (северо-западный угол)

ris20.tiff

При составленном базисном плане закрепления поставщиков за потребителями, транспортная работа составит:

bezs46.wmf т×км.

Лучший способ составления базисного плана – способ «наименьшего элемента»:

Таблица 3

Базисный план (по наименьшему элементу в столбце)

ris21.tiff

bezs47.wmf т×км.

3. Потенциалы строк и столбцов. Математическая постановка метода

Потенциалы загруженных и свободных клеток таблицы:

bezs48.wmf,

bezs49.wmf,

где Ui – значение потенциала строки; Vj – значение потенциала столбца; Aij – потенциалы загруженных клеток; Eij – потенциалы свободных клеток; bezs50.wmf.

4. Правила построения контура

1) Замкнутая ломаная линия, образованная прямыми отрезками, углы соединений между которым равны 90°.

2) Все углы контура, кроме одного находятся в загруженных клетках.

3) Знаки в углах контура чередуются. Первый знак «+» ставится в пустой клетке.

Далее определяется наименее загруженная клетка, занятая отрицательным углом контура. Количество груза, указанное в этой клетке, отнимается из всех клеток, занятых отрицательными углами контура, и прибавляется во все клетки контура с положительными углами. Составляется новый план распределения.

Таблица 4

План перевозок №1

ris22.tiff

bezs51.wmf т×км.

Таблица 5

Оптимальный план перевозок

ris23.tiff

bezs52.wmf т×км.

Повторяем итерацию до тех пор, пока не будет соблюден ряд следующих условий:

1) Потенциалы загруженных клеток равны 0.

2) Потенциалы незагруженных клеток имеют положительное значение.

3) Транспортная работа минимальна.

Для достижения оптимального плана перевозок с наименьшей транспортной работой потребовалось совершить 5 итераций (5 планов перевозок).

При таком плане перевозок все ГОП и грузополучатели будут удовлетворены, при этом будет затрачена минимальная транспортная работа.

5. Заключение

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

В практике планирования ГАП также встречаются особые виды транспортных задач – модели с несбалансированным спросом и предложением, модели с запрещенными корреспонденциями, модели с обязательными корреспонденциями, которые так же решаются с помощью этого метода, но с некоторыми особенностями.

Для упрощения и автоматизации вычислений в Excel существует надстройка Поиск решения (Solver), которая, в частности, помогает решать транспортные задачи.


Библиографическая ссылка

Лозгачёв И.А., Корепанов М.Ю. КЛАССИЧЕСКАЯ ТРАНСПОРТНАЯ ЗАДАЧА, РЕШЕННАЯ МЕТОДОМ ПОТЕНЦИАЛОВ // Международный студенческий научный вестник. – 2016. – № 3-1. ;
URL: https://eduherald.ru/ru/article/view?id=14699 (дата обращения: 29.03.2024).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1,674