Формулировка транспортной задачи

ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Однородный груз сосредоточен у т поставщиков в объемах a ₁, a ₂,..., а_т. Данный груз необходимо доставить п потребителям в объемах b ₁, b ₂,..., b_n. Известны с_ij, i = 1, 2,..., m, j = 1, 2,..., п — стоимости перевозки единицы груза от каждого i -го поставщика каждому j -му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков будут вывезены полностью, запросы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.

Исходные данные транспортной задачи обычно записываются в таблице:

bj ai	b 1	b 2	…	bn
a 1	с 11	с 12	…	с 1 n
a 2	с 21	с 22	…	с 2 n
…	…	…	…	…
ат	ст 1	ст 2	…	стn

Исходные данные задачи могут быть представлены также в виде вектора запасов поставщиков А = (a ₁, a ₂,..., а_т), вектора запросов потребителей В = (b ₁, b₂,..., b_n) и матрицы стоимостей

.

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

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