ТРАНСПОРТНАЯ ЗАДАЧА

ТРАНСПОРТНАЯ ЗАДАЧА

- один из наиболее важных частных случаев общей задачи линейного программирования. Содержательно Т. з. формулируется следующим образом.
Пусть в пунктах A1, А2, . . ., А т производится нек-рый однородный продукт, причем объем производства лого продукта в пункте А i составляет а i единиц, i=1, . . ., т. Произведенный в пунктах производства продукт должен быть доставлен в пункты потребления B1, В2, . . ., В n, причем объем потребления в пункте В j составляет bj единиц продукта. Предполагается, что транспортировка готовой продукции возможна из любого пункта производства в любой пункт потребления и транспортные издержки, приходящиеся на перевозку единицы продукта из пункта Ai в пункт Bj, составляют cij денежных единиц. Задача состоит в организации такого плана перевозок, при к-ром суммарные транспортные издержки были бы минимальными.
Формально задача ставится следующим образом. Пусть xij - количество продукта, перевозимого из пункта Ai в пункт Bj. Требуется определить совокупность из тп величин х ij, удовлетворяющих условиям

и обращающих в минимум линейную форму

Группа ограничений (1) связана с тем обстоятельством, что объем вывезенного из каждого пункта производства продукта в точности равен объему произведенного в этом пункте продукта, а объем ввезенного в пункт потребления продукта в точности соответствует его потребности. При этих ограничениях необходимым и достаточным условием для разрешимости Т. з. является выполнение условия баланса

Специфическими для Т. з. являются следующие два обстоятельства: а) каждое из переменных xij входит в два уравнения системы (1); б) все коэффициенты при переменных xij принимают лишь два значения 0 или 1. Условия а) и б) позволили разработать для решения Т. з. алгоритмы, существенно более простые, чем симплексный метод, к-рый является одним из основных методов решения задач линейного программирования.
Наиболее известными из этих алгоритмов являются метод потенциалов и т. н. венгерский метод. Метод потенциалов - это метод последовательного улучшения плана (перевозок) с использованием второй теоремы двойственности для проверки оптимальности [1]. Венгерский метод - это метод последовательного построения допустимого плана, к-рый автоматически оказывается оптимальным. В основе венгерского алгоритма лежит метод чередующихся цепей [2].
Известны следующие два обобщения классич. Т. з., являющиеся отражением встречающихся на практике ситуаций. Открытая модель Т. э.- это Т. з. с нарушенным условием баланса (2), что означает либо превышение объема производства над объемом потребления, либо наоборот. Такая задача сводится к классич. Т. з. путем введения фиктивного пункта производства (или потребления) с мощностью производства (или потребления), равной разности объемов производства и потребления.
Много индексные транспортные задачи при сохранении общей проблемы минимизации транспортных издержек учитывают неоднородность груза (продуктов производства) и неоднородность транспортных средств.
За рубежом Т. з. иногда наз. проблемой Хичкока.

Лит.:[1] Гольштейн Е. Г., Юдин Д. В., Задачи линейного программирования транспортного типа, М., 1969; [2] Оре О., Теория графов, пер. с англ., М., 1968; [3] Емеличев В. А., Ковалев М. М., Кравцов М. К., Многогранники. Графы. Оптимизация, М., 1981.
В. К. Леонтьев.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Нужна курсовая?

Полезное


Смотреть что такое "ТРАНСПОРТНАЯ ЗАДАЧА" в других словарях:

  • Транспортная задача — (задача Монжа  Канторовича)  математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.[1][2] Для… …   Википедия

  • транспортная задача — Совокупность всех компонентов, которые должны быть обеспечены и задействованы для осуществления транспортного обслуживания Игр, включая предоставление услуг в объеме, необходимом для удовлетворения потребности в транспортном обслуживании, с… …   Справочник технического переводчика

  • Транспортная задача — [trans­portation problem] одна из наиболее распространенных задач математического программирования (обычно линейного). В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы… …   Экономико-математический словарь

  • Транспортная задача —         задача о наиболее рациональном плане перевозок однородного продукта из пунктов производства в пункты потребления. Пусть имеется m пунктов производства некоего однородного продукта A1, …, Ai, …, Am и n пунктов его потребления B1, …, Bj, … …   Большая советская энциклопедия

  • производственно-транспортная задача — Такая оптимизационная задача, при которой одновременно с установлением объема производства на отдельных предприятиях определяется и оптимальная схема размещения заказов (т.е. прикрепления поставщиков к потребителям). Она имеет особое значение для …   Справочник технического переводчика

  • Транспортная логистика — Транспортная логистика  это система по организации доставки, а именно по перемещению каких либо материальных предметов, веществ и пр. из одной точки в другую по оптимальному маршруту. Одно из основополагающих направлений науки об управлении… …   Википедия

  • ЗАДАЧА О ПЕРЕВОЗКАХ С ПРОМЕЖУТОЧНЫМИ ПУНКТАМИ — обобщенная транспортная задача, когда для каждого пункта потребления составляется уравнение материального баланса. З.о п.с п.п. можно представить в сетевом виде. Она является прикладной задачей линейного программирования …   Большой экономический словарь

  • Транспортная система — Транспортная система  транспортная инфраструктура, транспортные предприятия, транспортные средства и управление в совокупности. Единая транспортная система обеспечивает согласованное развитие и функционирование всех видов транспорта с целью… …   Википедия

  • Задача Транспортная — См. Задача о кратчайшем пути Словарь бизнес терминов. Академик.ру. 2001 …   Словарь бизнес-терминов

  • ЗАДАЧА, ТРАНСПОРТНАЯ — задача о наиболее рациональном плане перевозок однородного продукта из пункта производства в пункт потребления …   Большой экономический словарь


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»