Транспортная задача

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом.

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

Различают два типа транспортных задач: по критерию стоимости и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).

Обозначим количество груза, имеющегося на каждой из баз (запасы), соответственно ,а общее количество имею­щегося в наличии груза–:

; (9)

заказы каждого из потребителей (потребности) обозначим соот­ветственно, а общее количество потребностей –:

, (10)

Тогда при условии мы имеемзакрытую модель, а при условии – открытую модель транспортной задачи.

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

План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок:

Переменные означает количество груза, перевозимого с базыпотреби­телю: совокупность этих величин образует матрицу(матрицу перевозок).

Очевидно, переменные должны удовлетворять условиям: