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

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

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

Пусть имеется ${\displaystyle m}$ пунктов производства некоторого однородного продукта и ${\displaystyle n}$ пунктов его потребления. Для каждого пункта производства ${\displaystyle i=1,2,...,m}$ и для каждого пункта потребления ${\displaystyle j=1,2,...,n}$ заданы следующие величины: объём производства ${\displaystyle a_{i}}$ в пункте производства ${\displaystyle i}$, объём потребления ${\displaystyle b_{j}}$ в пункте потребления ${\displaystyle j}$, затраты на перевозку единицы продукта ${\displaystyle c_{ij}}$ от пункта производства ${\displaystyle i}$ до пункта потребления ${\displaystyle j}$. Предполагается, что суммарное производство равно суммарному потреблению: ${\displaystyle \sum _{i=1}^{m}a_{i}=\sum _{j=1}^{n}b_{j}}$. Требуется составить план перевозок, позволяющий полностью вывезти продукты всех производителей, полностью обеспечивающий потребности всех потребителей и дающий минимум суммарных затрат на перевозку. Обозначим как ${\displaystyle x_{ij}}$ объёмы перевозок от поставщика ${\displaystyle i}$ до потребителя ${\displaystyle j}$.[3]

${\displaystyle \sum _{j=1}^{n}x_{ij}=a_{i}}$, ${\displaystyle i=1,2,...,m}$

${\displaystyle \sum _{i=1}^{m}x_{ij}=b_{j}}$, ${\displaystyle j=1,2,...,n}$

${\displaystyle \sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}\rightarrow \min }$

Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году[4]. Прогресс в решении проблемы был достигнут во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем[5]. Поэтому иногда эта проблема называется транспортной задачей Монжа — Канторовича.

Классическую транспортную задачу можно решить симплекс-методом, но в силу ряда особенностей её можно решить проще (для задач малой размерности).

Условия задачи располагают в таблице, вписывая в ячейки количество перевозимого груза из ${\displaystyle A_{i}}$ в ${\displaystyle B_{j}}$ груза ${\displaystyle X_{ij}\geqslant 0}$, а в маленькие клетки — соответствующие тарифы ${\displaystyle C_{ij}}$.

• Транспортная задача
• Алгоритмы нахождения максимального потока
• http://kb.mista.ru/article.php?id=859 Решение транспортной задачи в 1С:Предприятие 8.2

• Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. — М.: Наука, 1969. — 368 с.