Транспортная задача. Задача отличается определенностью экономической характеристики, особенностью матема­тической формы, наличием специфических методов решения

Задача отличается определенностью экономической характеристики, особенностью матема­тической формы, наличием специфических методов решения. Транспорт­ная задача относится к классу распределительных задач. Она может использоваться не только для планирования перевозок, но и для реше­ния задач о рациональном размещении производства, об оптимальном использовании кадров, о назначениях и т.п.

Особенности транспортной задачи:

· производится однотипная продукция;

· ограничения задаются в виде равенств;

· каждая переменная входит в два ограничения;

· коэффициенты при переменных в ограничениях равны единице;

· число линейно независимых ограничений равно (m + n – l),

где m - число поставщиков, n - число потребителей.

Целевая функция (минимизация транспортных расходов)

Ограничения по запасам поставщиков

Ограничения по заявкам потребителей

Условие неотрицательности переменных

Индексные переменные

Условные обозначения:

i - число поставщиков;

j - число потребителей;

Е - целевая функция;

- запасы 1-го поставщика;

- заявка j-ro потребителя;

- количество продукции, перевозимой от i-го поставщика к j-му потребителю по оптимальному плану.

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

Метод потенциалов включает два этапа: нахождение опорного решения; нахождение оптимального решения.

Для нахождения опорного решения применяют метод северо-западного угла, метод минимального элемента или метод последовательного приближения. Опорное решение отвечает ограничениям, но не минимизирует целевую функцию.

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

Для базисных клеток должно соблюдаться условие . Для свободных клеток вводят фиктивные стоимости перевозок .

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