Сущность метода заключается в том, что на каждом шаге заполняется левая верхняя (северо-западная) клетка оставшейся части таблицы, причем максимально возможным числом: либо полностью выносится груз из Аi, либо полностью удовлетворяется потребность Вj. Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj. В заключении проверяют, удовлетворяют ли найденные компоненты плана Х_ijгоризонтальным и вертикальным уравнениям.

Построим опорный план.

Исходная транспортная таблица:

Построение второй транспортной таблицы

Магазин В1 подал заявку на 20 кроватей, но со склада А1 мы можем перевести 15 кроватей, ещё 5 кроватей мы перевезём со склада А2. Спрос для магазина В1 удовлетворён. Рассмотрим магазин В2. В него необходимо доставить 12 кроватей - доставим их со склада А2.

На складе А2 осталось 8 кроватей. Выделим из них пять для магазина В3. На складе А2 осталось 3 кровати. Выделим их на магазин В3, но потребности магазина ещё не удовлетворены, поэтому выделим ему со склада А3 ещё пять кроватей. Осталось 15 кроватей, столько, сколько требуется в магазин В5.

Построенный план является допустимым, так как все заявки удовлетворены, все запасы израсходованы.

Проверим, является ли полученный план опорным: количество ячеек с ненулевыми перевозками равно m+n-1 = 7.

Опорный план: Х₁₁ = 15, Х₂₁ = 5, Х₂₂ = 12, Х₂₃ = 5, Х₂₄ = 3, Х₃₄ = 5, Х₃₅ = 15. Все остальные X_ij = 0.

F = 1*15+5*5+1*12+2*5+3*3+4*5+3*15 = 136

Метод наименьшего элемента

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

Построим опорный план.

Исходная транспортная таблица:

Построение второй транспортной таблицы

Находим в таблице наименьшую стоимость перевозки – это 0 в клетке A1B2. Записываем в этой клетке значение 12 (наименьшее из сумм по строке и столбцу).

Теперь вычеркиваем второй столбец, уменьшив сумму в первой строке на 12.

Находим следующую наименьшую по стоимости ячейку – их несколько, например, A1B1. Присваиваем ей значение 3, а сумму по столбцу заменяем на 17.

Вычеркиваем первую строку.

Выбираем ячейку A3B3, присваиваем ей значение 5. Вычеркиваем третий столбец. Сумму по третьей строке заменяем на 15.

Выбираем ячейку A2B5, записываем в ней 15, уменьшаем вторую строку на 15 и вычеркиваем пятый столбец.

Выбираем ячейку A3B1, присваиваем ей 15. Уменьшаем первый столбец на 15 и вычеркиваем третью строку.

Ячейке A2B1 присваиваем 2 и вычеркиваем первый столбец. Сумму по второй строке заменяем на 8.

Ячейке A2B4 присваиваем 8 и вычеркиваем четвертый столбец.

Опорный план построен.

Х₁₁ = 3, Х₁₂ = 12, Х₂₁ = 2, Х₂₄ = 8, Х₂₅ = 15, Х₃₁ = 15, Х₃₃ = 5.

Все остальные Х_ij = 0.

F = 3*1+0*12+5*2+3*8+3*15+5*1 = 147

Найдём теперь оптимальный план для данной задачи.

Для этого воспользуемся методом потенциалов.

2. Метод потенциалов решения транспортных задач

Соотношения

определяют систему из m+n-1 линейных уравнений с m+n известными, имеющую бесчисленное множество решений; для её определённости одному неизвестному присваивают произвольное значение (обычно альфа равное 0), тогда все остальные неизвестные определяются однозначно.

Критерий оптимальности

Если известны потенциалы решения Х0 транспортной задачи и для всех незаполненных ячеек выполняются условия α_i+β_j ≤ C_ij, то Х0 является оптимальным планом транспортной задачи.

Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличивались.

Цикл перерасчёта таблицы – это последовательность ячеек, удовлетворяющая условиям:

1. Одна ячейка пустая, все остальные занятые.

2. Любые две соседние ячейки находятся в одной строке или в одном столбце.

3. Никакие три соседние ячейки не могут быть в одной строке или в одном столбце.

Пустой ячейке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".

Для перераспределения плана перевозок с помощью цикла перерасчёта сначала находят незаполненную ячейку (r, s), в которой αr+βs > Crs, и строят соответствующий цикл; затем в минусовых клетках находят число X = min(X_ij). Далее составляют новую таблицу по следующему правилу:

4. В плюсовых клетках добавляем Х.

5. Из минусовых клеток вычитаем Х.

6. Все остальные клетки вне цикла остаются без изменения.

Получим новую таблицу, дающую новое решение Х, такое, что F (X₁) ≤ F (X₀); оно снова проверяется на оптимальность через конечное число шагов, обязательно найдем оптимальный план транспортной задачи, ибо он всегда существует.

Найдём оптимальный план для рассмотренной выше задачи. В качестве опорного плана возьмем план, полученный с помощью метода "минимального элемента" Х₁₁ = 3, Х₁₂ = 12, Х₂₁ = 2, Х₂₄ = 8, Х₂₅ = 15, Х₃₁ = 15, Х₃₃ = 5. Все остальные элементы равны 0.

Составим систему уравнений для нахождения потенциалов решения, найдем сумму соответствующих потенциалов для каждой свободной ячейки и пересчитаем тарифы (стоимости) для каждой свободной ячейки.

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

X = min(2, 12) = 2

Строим следующую транспортную таблицу.

Проверим полученный план на оптимальность. Теперь ячейка A1B2 не заполнена.

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

X = min(15, 10, 15) = 10

Строим следующую транспортную таблицу.

Проверим построенный план на оптимальность.

Полученный план является оптимальным. Х₁₁ = 15, Х₂₂ = 12, Х₂₄ = 8, Х₂₅ = 5, Х₃₁ = 5, Х₃₃ = 5, Х₃₅ = 10. Все остальные Х_ij = 0.

F = 1*15+1*12+3*8+3*5+4*5+1*5+3*10 = 121

Транспортная задача - это математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов с минимизацией затрат на перемещение.

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

· решение транспортной задачи методом потенциалов (рассмотрен в данной статье)

· решение транспортной задачи с использованием симплекс метода.

Решение задачи методом потенциалов происходит в несколько этапов:

1. Определение опорного решения.

2. Применение к найденному опорному решению самого метода потенциалов.

3. Проверка единственности решения.

Определение опорного плана, в свою очередь, можно выполнить несколькими способами. Мы рассмотрим два из них:

· метод северо-западного угла

· метод минимальных стоимостей

(не путать с методами решения самой транспортной задачи!!!)