Метод потенциалов для решения транспортной задачи с промежуточными пунктами
Статья: The potential method for solving the transportation problem with transit points
Содержание
Введение
Транспортная задача линейного программирования в настоящее время широко используется во многих теоретических работах и имеет практическое применение в транспорте и промышленности. Её область применения простирается от классической задачи перевозки товаров от фабрик до магазинов до задачи маршрутизации трафика в Интернете и локальных сетях.
Цель транспортной задачи — поиск наиболее эффективных маршрутов перевозки товаров, исключающих слишком длительные, встречные и повторяющиеся перевозки. Объектом исследования являются материальные и соответствующие им финансовые и информационные потоки, связанные с различными видами промышленной и коммерческой деятельности.
Классическая форма транспортной задачи рассматривает перевозку одного или нескольких товаров из пунктов отправления в пункты назначения.
Транспортная модель и её варианты используются для создания наиболее экономически эффективного плана транспортировки товара из ряда пунктов (например, фабрик, складов) в пункты доставки (например, магазины, склады).
Транспортную задачу можно решить методом потенциалов, который модифицирует симплекс-метод таким образом, что вычислительные процедуры становятся более эффективными.
Сетевая постановка задачи часто используется для решения транспортной задачи с транзитными пунктами. Сетевая модель не разделяет товары на пункты отправления и пункты потребления — все пункты равноправны, но производству задаётся положительное число, а потреблению — отрицательное. Транспортировка осуществляется по определённой сети, где дуги могут соединять любые точки. В сетевой модели транспортной задачи методы решения основаны на идеях Форда и Фулкерсона.
Таким образом, возникает необходимость в поиске более эффективной вычислительной процедуры для решения транспортной задачи с транзитными пунктами, сложность которой позволяла бы автоматизировать решение для больших объёмов данных.
1. Постановка задачи
2. Критерий оптимальности
Теорема 1
Доказательство:
3. Условия разрешимости
4. Эквивалентная задача
5. Критерий оптимальности эквивалентной задачи
Теорема 2
Доказательство:
6. Условия разрешимости эквивалентной задачи.
7. Метод потенциалов для решения ТЗПП
Заключение
В данной статье описываются исходная постановка транспортной задачи с промежуточными пунктами, эквивалентная ей задача и критерии оптимальности.
Приведены также доказательство критериев оптимальности, метод решения, аналогичный методу потенциалов (без использования сетевой модели), и пример решения.
Предлагаемый метод решения является модифицированной версией метода потенциалов и, следовательно, обладает его преимуществами по сравнению с симплекс-методом и сетевыми методами, в частности, меньшей вычислительной сложностью и отсутствием необходимости моделирования сложных сетевых систем. Однако узкая форма постановки задачи сужает её область применения, что делает предлагаемый метод эффективным только в случаях, когда практические условия могут быть сведены к описанной форме транспортной задачи.
Список литературы
1. Д. Б. Юдин, Э. Г. Гольштейн, Линейное программирование. М., 1963. С.775.
2. Э. Г. Гольштейн, Д. Б. Юдин, Задачи линейного программирования транспортного типа. М., 1969. С.383.
3. Форд Л. Р., Фулкерсон Д. Р., Решение транспортной задачи, Госстатиздат, М., 1963. С.72.
