Метод наименьших стоимостей.

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

Рассмотрим каждый из этих методов подробнее.

Методом северо-западного угла исходную матрицу перевозок начинают заполнять с левого верхнего угла. В магазин В ₁ отправляем с первой базы груз в количестве 20 т, так как потребность этого магазина составляет 20 т, а запас товара на базе 50 т. Потребность магазина В ₁ в этом случае удовлетворена полностью, а на первой базе осталось груза 30 т. Поэтому оставшийся товар на первой базе (30 т) отправляют во второй магазин В ₂, имеющий потребность в 60 т груза. Оставшуюся потребность магазина В ₂ (30 т) удовлетворяют, перевозя груз со второй базы А ₂. На базе А ₂ остался груз 60 т – его отправляют в магазин В ₃ (30 т) и в В ₄ (30 т). Потребность магазина В ₄ и В ₅ удовлетворится с базы А ₃.

Матрица перевозок примет вид таблицы 7.

Таблица 7

	B 1	B 2	B 3	B 4	B 5	Запасы (ai)
А 1
А 2
А 3
Потребности (bj)

 

В таблице число заполненных клеток равно 7. Их число должно быть m+n – 1 = 3 + 5 – 1 = 7, то есть 7=7. Следовательно, имеем невырожденный опорный план.

Найдем стоимость перевозок в полученном плане:

руб.

Методом наименьшей стоимости заполнение матрицы перевозок начинается с клетки, имеющей наименьший тариф (с клетки А ₂ В ₄). В этом случае потребность магазина В ₄ составляет 50 т, а запас на базе А ₂ 90 т. Поэтому в эту клетку следует отправить 50 т. Затем заполняем клетку А ₂ В ₁, имеющей тариф 5, – 20 т. Следующая клетка с наименьшим тарифом А ₃ В ₅. Туда отправляем 40 т. и т.д. Получим таблицу 8.

Таблица 8

	B 1	B 2	B 3	B 4	B 5	Запасы (ai)
А 1	-			-	-
А 2		-			-
А 3	-		-	-
Потребности (bj)

 

Число заполненных клеток 7. Их число должно быть
m+n – 1 = 3 + 5 – 1 = 7. Следовательно, полученный опорный план невырожденный.

Стоимость перевозок в полученном плане:

руб.

При применении метода наименьшей стоимости стоимость перевозки получилась меньше по сравнению с методом северо-западного угла.

 

5.3. Распределительный метод решения
транспортной задачи

 

Определение. Циклом пересчета в транспортной задаче называется замкнутый многоугольник, одна из вершин которого совпадает со свободной клеткой, для которой образуется цикл, а остальные – заполненными. Вершины соединяются замкнутой ломаной линией, отрезки которой образуют угол 90°. Любой цикл имеет четное число вершин, каждую из которых отмечают знаком. Свободной клетке, для которой выбран цикл, приписывается знак +, остальные знаки чередуются.

На рис. 2 дан пример цикла пересчета. В его вершинах указаны номера строк и столбцов клеток, в которых лежат эти вершины.

Рис. 2. Цикл транспортной задачи для клетки (А ₁ В ₅) таблицы 7.

 

Свободной клетке, с которой начинается цикл, т.е. клетке (А ₁ В ₅), присваивают знак +, затем знаки чередуются.

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

Подсчитаем алгебраическую сумму стоимостейАСС свободной клетки (А ₁ В ₅) транспортной задачи, заданной таблицей 7.

АСС(1.5) = 13 + (-8) + 12 + (-4) + 13 + (-22) = +4.

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

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

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

1. Находим минимальное из чисел, лежащих в отрицательных вершинах цикла. Обозначим это число D.

2. К числам в положительных вершинах прибавляют D, из чисел в отрицательных вершинах вычитают D.

3. Значения неизвестных клеток старой таблицы (матрицы перевозок), в которых не находились вершины цикла пересчета, переписываются в новую таблицу без изменения. Матрица тарифов остается постоянной.

Приведенный метод решения транспортной задачи называется распределительным методом.

 

Алгоритм распределительного метода решения
транспортной задачи

 

Пусть имеется исходное базисное решение транспортной задачи.

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

2. Если среди алгебраических сумм стоимостейАСС есть отрицательные, то план не оптимальный и следует перейти к пункту 3.

Если все АСС неотрицательные, то данное базисное решение является оптимальным. Подсчитывают оптимальное значение стоимости перевозок.

3. Среди всех алгебраических сумм стоимостей(АСС) выбирают наибольшую по величине отрицательную АСС и соответствующую ей свободную клетку матрицы перевозок.

4. Для свободной клетки, найденной в п.3, составляют цикл пересчета. Производят сдвиг, преобразовав свободную клетку в базисную. Получают новое базисное решение. Записывают его в таблицу перевозок.

5. Возвратиться к пункту 1 алгоритма.