Постановка и типы транспортных задач

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

Рассмотрим такую задачу.

Имеется поставщиков А_i и n потребителей . Количество груза, находящегося у поставщика , будем обозначать через . Количество груза, необходимое потребителю - через . Дана матрица тарифов (издержек или транспортных расходов).

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

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

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

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

Математическая модель задачи выглядит так:

Система ограничений содержит m+n уравнений переменными.

Если суммарный объем груза поставщиков равен суммарному спросу потребителей, то есть

то это транспортная задача с закрытой моделью.

А если , то это транспортная задача с открытой моделью.

Равенство является необходимым и достаточным условием совместности ограничений задачи.

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

Дата добавления: 2014-01-04