Важным частным случаем задачи линейного программирования является транспортная задача.

Постановка задачи: Пусть имеется m поставщиков и n потребителей. Мощность поставщиков и спросы потребителей, а так же затраты на перевозку груза для каждой пары «поставщик – потребитель» заданы таблицей.

Найти объемы перевозок каждой пары «поставщик – потребитель» так, чтобы: мощности всех поставщиков были реализованы; спросы всех потребителей были удовлетворены; суммарные затраты на перевозку были бы максимальны.

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

ü система ограничений есть система уравнений, то есть задача ЛП в каноническом виде;

ü коэффициенты при неизвестных системы ограничений равны единицы или нулю;

ü каждая переменная входит в систему ограничений два раза: один раз в систему ограничений поставок, второй раз – в систему ограничений спроса.

Математическая модель транспортной задачи.

Пусть хij – количество груза, перевозимого с i-го в j-й пункт.

Целевая функция:

Система ограничений:

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

Сбалансированная ТЗ:

Несбалансированная ТЗ:

Для сбалансированной ТЗ ограничения принимают вид равенств, то есть получаем m+n ограничений, в которых все переменные линейно зависимы. В результате допустимое решение сбалансированной ТЗ может быть получено, если заполнять клетки транспортной таблицы таким образом, чтобы сумма перевозок в каждой строке должна быть равна запасам ai, а сумма перевозок в каждом столбце равна соответствующей заявке вj. Вариантов заполнения транспортной таблицы множество, поэтому искомым решением является то из допустимых решений, для которых общая стоимость перевозок будет минимальной.