КЛАССИЧЕСКАЯ ТРАНСПОРТНАЯ ЗАДАЧА, РЕШЕННАЯ МЕТОДОМ ПОТЕНЦИАЛОВ - Студенческий научный форум

VIII Международная студенческая научная конференция Студенческий научный форум - 2016

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

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

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

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

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

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

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

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

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

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

Таблица 1.1 «Исходные данные»

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

(1.1)

(1.2)

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

Таблица 1.2 «Базисный план (северо-западный угол)»

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

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

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

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

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

,

где — значение потенциала строки; — значение потенциала столбца; — потенциалы загруженных клеток; — потенциалы свободных клеток; .

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

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

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

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

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

Таблица 1.4 «План перевозок №1»

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

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

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

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

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

Таблица 1.5 «Оптимальный план перевозок»

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

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

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

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

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

Литература

1. Попов, А.Г. Автомобильные грузовые перевозки / А.И.Афанасьев, Ю.Г.Закаменных. — Е., 2012. — 195 с.

2. Грузовые автомобильные перевозки / А.В.Вельможин, В.А.Гудков, Л.Б.Миротин, А.В.Куликов. — М., 2007. — 559 с.

3. Электронный ресурс [http://www.ati.su/]

Просмотров работы: 1321