Методы решения транспортных задач

Перейдем к решению задачи.

Так как транспортная задача является задачей линейного программирования, то её можно решать симплекс-методом, но в силу своей особенности её можно решить гораздо проще.

Условия задачи удобно располагать в таблице, вписывая в ячейки количество перевозимого груза из Аi в Bj груза X_ij ≥ 0, а в маленькие клетки – соответствующие тарифы C_ij.

Наша задача заполнить все клетки числами x_ij (количеством перевозимого товара) так, чтобы их сумма по строкам была равна а_i, по столбцам -b _j. Затем эти числа умножаем на стоимости перевозок C_ij и складываем. И эта сумма должна принимать минимальное значение.

Решение задачи разбивается на два этапа:

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

2. Нахождение оптимального решения путем последовательных операций.

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

1. Опорный план транспортной задачи можно найти, используя метод "северо-западного угла" или метод "минимального элемента".

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

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

Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы аi и не удовлетворятся все потребности bj.

(9 слайд)

Задача: Фирма должна отправить некоторое количество компьютеров с трёх складов в пять магазинов. На складах имеется соответственно 15, 25 и 20 компьютеров, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 15 компьютеров. Стоимость перевозки одного компьютера со склада в магазин приведены в таблице.