1.9.1 История развития транспортной задачи

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

Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году.

Впервые высказывание о важности решения задач линейного программирования и, в частности, транспортной задачи было сделано в прошлом веке. Тогда же были предложены методы решения этих задач. У истоков создания теории линейного программирования стоял русский учёный - Л. В. Канторович. Широкое практическое использование этой теории началось после появления вычислительных машин. Это связано с тем, что при реализации методов линейного программирования требуется выполнять многочисленные последовательные арифметические операции. Ошибка в одном действии приводила к неверному результату и поиску верного решения путём повторного утомительного расчёта.