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

1.

Лабораторная работа № 2
ТРАНСПОРТНЫЕ ЗАДАЧИ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

2.

Формулировка классической транспортной
задачи
• Транспортная задача — это математическая задача линейного программирования
специального вида о поиске оптимального распределения однородных объектов
из аккумулятора к приемникам с минимизацией затрат на перемещение. Для
простоты понимания рассматривается как задача об оптимальном плане
перевозок грузов из пунктов отправления в пункты потребления, с минимальными
затратами на перевозки.
• Для классической транспортной задачи выделяют два типа задач: критерий
стоимости (достижение минимума затрат на перевозку) или расстояний и
критерий времени (затрачивается минимум времени на перевозку). Под
термином «транспортная задача» подразумевается широкий круг задач с единой
математической моделью, которые относятся к задачам линейного
программирования и могут быть решены оптимальным методом. Однако
специальный метод решения транспортной задачи существенно упрощает ее,
поскольку транспортная задача разрабатывалась для минимизации стоимости
перевозок.

3.

Классическая транспортная задача линейного программирования
формулируется следующим образом. Имеется m пунктов отправления А1, А2,
... , Am, в которых сосредоточены запасы какого-то однородного товара (груза)
в количестве соответственно а1, а2, ..., аm единиц. Кроме того, имеется n
пунктов назначения В1, В2, ..., Вn, подавших заявки соответственно на b1, b2, ...,
bn , единиц товара.
Предполагается, что сумма всех заявок равна сумме всех запасов:

4.

Известна стоимость cij перевозки единицы товара от каждого пункта
отправления Ai, до каждого пункта назначения Вj. Таблица (матрица)
стоимостей перевозки cij задана: