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

  • 15 дек. 2013 г.
  • 842 Слова
Транспортная задача (задача Монжа - Канторовича) - математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора кприемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами наперевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP.
Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общемуобъёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).
Постановка задачи

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

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