Решение транспортной задачи
Транспортная задача является специальной задачей линейного программирования.
Суть ее заключается в следующем. Есть m поставщиков грузов А1, А2, …, Аm и n потребителей B1, B2, …, Bn этих грузов. Известны запасы грузов у поставщиков а1, а2, …, аm и потребности в этих грузах b1, b2, …, bn соответственно, а также тарифы перевозок сij.

Требуется:

  1. Все запасы изъять.
  2. Все потребности удовлетворить.
  3. Чтобы стоимость доставки грузов была минимальной.

 

Математическая модель задачи следующая:
Математическая модель задачи

Как видим, математическая модель записана в каноническом виде, так как в ней присутствует условие равновесия (2), но это идеальный случай. Чаще всего можно столкнуться со следующим:

  1. запасы превышают потребности и тогда приходится вводить фиктивного потребителя с нулевым тарифом;
  2. потребности превышают запасы – вводят фиктивного поставщика с нулевым тарифом.

 

Почему тарифы равны нулю? Вывод очевиден – надо следовать критерию задачи.
Более подробную информацию по теории транспортной задачи можно посмотреть в учебниках по исследованию операций либо математическому программированию.
 

Любая задача ЛП, в том числе и транспортная задача, решается в два этапа.
Сначала находят опорный план, затем его подвергают анализу и в конечном итоге находят оптимальный план. Для транспортной задачи существуют и прямые методы – это распределительный метод, дельта-метод и метод дифференциальных рент. Но независимо от применяемого математического метода полученное решение проверяют на оптимальность с помощью метода потенциалов.
 

Вывод: метод потенциалов универсален и всегда дает оптимальное решение.
 

Рассмотрим задачу: имеются три поставщика грузов и три потребителя этих грузов. Запасы грузов составляют 150, 100 и 300 ед., потребности в них равны 100, 250 и 200 ед. соответственно. Тарифы перевозок также известны:
Тарифы перевозок

Найти оптимальный план доставки этих грузов.
 

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

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

Для решения задачи составляется таблица перевозок:

 Таблица перевозок 

Правила заполнения таблицы несложные. Заполнение начинают с левой верхней клетки, в которую записывают грузопоставку исходя из наличия груза и потребности в нем. Наличие груза у поставщика А1 составляет 150 ед. а потребность потребителя В1 в грузе равна 100 ед. Запишем этот груз полностью, а остаток 50 ед. запишем следующему потребителю, третью ячейку вычеркнем, так как весь груз у первого поставщика изъят:

 tz_table2 

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

 tz_table3 

Как видим, при распределении грузов тарифы не учитывались. Расходы на доставку грузов составляют:
f = 3×100 + 2×50 + 1×100 + 3×100 + 3×200 = 1400 у.е.
 

Найдем опорный план методом минимального элемента с учетом тарифов перевозок и сравним решения. Составим такую же таблицу перевозок, но вот порядок заполнения будет отличен от предыдущего случая:

 tz_table4 

Грузопоставки начнем вписывать в клетку, которая имеет наименьший тариф. Если таких клеток несколько, то начинать записывать можно в любую из них. Минимальный тариф в таблице равен единице, а так как таких клеток три, то выберем первой например ячейку А1В3. Размер грузопоставки определяется исходя из наличия груза у поставщика и потребности потребителя. Наличие груза у первого поставщика равно 150 ед., потребность равна 200 ед. Мы забираем весь груз у А1 и записываем:

 tz_table5 

Заполняем следующую клетку с тарифом, равным единице:
 tz_table6 

Оставшиеся клетки с одинаковым тарифом последовательно заполняем:

 tz_table7 

Вычислим транспортные расходы:
f = 1×100 + 3×50 + 1×150 + 3×250 = 1150 у.е.
Как видим, опорный план, полученный методом минимального элемента, дает лучший результат, чем диагональный способ.
 

После того, как получено допустимое решение, его надо проверить на оптимальность с помощью метода потенциалов. Перед проверкой убеждаемся, что число заполненных клеток равно соотношению m+n-1. В нашей таблице их 3+3-1=5.
 

Признак оптимальности: решение оптимально, если во всех свободных клетках выполняется неравенство: αi + cij ≥ βj, где αi и βj – потенциалы, cij – тарифы перевозок. Вычислим αi и βj с помощью выше указанного неравенства:

 tz_table8 

Принято считать, что α1 всегда равно 0. Если не сделать это допущение, то задача не будет иметь решение. Вычисления остальных значений потенциалов производят по базовым (заполненным) клеткам:
α1 = 0
β1 = 3 + 0 = 3
β2 = 2 + 0 = 2
α2 = 2 — 1 = 1
α3 = 2 — 3 = -1
β3 = -1 + 3 = 2
 

Проверку на оптимальность делают по свободным клеткам с помощью этого же неравенства:
А1В3: 0 + 1 ≥ 2 – нет
А2В1: 1 + 1 ≥ 3 – нет
А2В3: 1 + 4 ≥ 2 – да
А3В1: -1 + 2 ≥ 3 – нет
 

В результате проверки мы выявили три недостаточные клетки. Находим цикл пересчета:

цикл пересчета – это ход ладьи по базовым клеткам с чередованием знаков «+» и «-», начиная с недостаточной клетки и замыкаясь в ней же.

 tz_table9 

В клетках с минусовыми отметками выбирает минимальное число. В нашем случае это число равно 100. Пересчет делают следующим образом: где стоит знак «-» это число отнимают, а где «+» то прибавляют. Значения, не входящие в цикл пересчета переписывают без изменений. Получает таблицу, в которой соотношение m+n-1 не выполняется, и поэтому выбираем клетку с минимальным тарифом и, проставляя в ней ноль, считаем ее условно базовой:

 tz_table10 

Вначале транспортные расходы составляли 1400 у.е. Считаем сейчас:
f2 = 2×100 + 2×150 + 1×100 + 3×200 = 1200 у.е.
Уменьшение этого показателя говорит о том, что мы на верном пути.
 

Полученное решение снова проверяем на оптимальность:

 tz_table11 

Проверка выявляет одну недостаточную клетку, для которой находим цикл пересчета:
А1В1: 0 + 3 ≥ 0 – да
А1В3: 1 + 0 ≥ 1 – да
А2В1: 1 + 1 ≥ 0 – да
А3В2: -2 + 3 ≥ 2 – нет
 

В отрицательных клетках из двух значений выбираем число 150, которое отнимаем, где знак «-» и прибавляем где знак «+»:

 tz_table12 

Транспортные расходы:
f3 = 2×100 + 3×150 + 1×100 + 1×150 + 3×50 = 1050 у.е.
 

Проверяем снова на оптимальность и убеждаемся, что найден оптимальный план:
А1В1: 0 + 3 ≥ 0 – да
А1В2: 0 + 2 ≥ 1 – да
А2В1: 0 + 1 ≥ 0 – да
А2В3: 0 + 4 ≥ 1 – да
 

Ответ: f = 1050 у.е.
             Ответ
 

Успехов! И помните, что Решатель всегда готов Вам помочь с решением транспортной задачи и не только! Заявку можно оставить здесь или заполнив форму наверху страницы.
 

Читайте также: Линейное программирование. Симплекс-метод.
 
 

Решение задач на заказ

К нам можно обратиться за решением задач по данной дисциплине. Наши специалисты подробно распишут решение в короткие сроки.
Узнать цену работы можно на странице заказа.