Вычислительные тесты по декомпозиционному алгоритму для транспортной задачи

Представлены вычислительные тесты по итеративному методу на основе последовательного пересчета коэффициентов функционала для транспортной задачи. Оптимальное решение получено за три итерации, не использует случая вырождения, совпадает со стандартной программой по методу потенциалов. Использованы стандартные методы теории оптимизации. Алгоритм строит последовательность решений промежуточных одномерных задач, которые не являются допустимыми для исходной задачи. Имеет место монотонный рост по функционалу на псевдорешениях. Получены формулы решений промежуточных двумерных задач с зацепляющимися переменными и последовательно пересчитаны коэффициенты функционалов. Найдено допустимое решение в системе равенств. При отсутствии допустимого решения сформулирована задача о максимальном потоке для транспортных ограничений с запретами. По некоторому правилу сформированы корреспондирующие пары индексов.

Авторы

Гурченков А.А.

Тэги

транспортная задача декомпозиция обобщенные поставщики и потребители.

Тематические рубрики

Общий отдел

Предметные рубрики

В этом же номере:

Определение точек оптимума двух классов двузонных функций, Разработка модели организации процесса патентных исследований на предприятии ракетно-космической отрасли, ...

Резюме по документу**

УДК 519.854 Вычислительные тесты по декомпозиционному алгоритму для транспортной задачи А. <...> А.А. Дородницына РАН, Москва, 119991, Россия 3 МФТИ (государственный университет), Долгопрудный, Московская обл., 141700, Россия Представлены вычислительные тесты по итеративному методу на основе последовательного пересчета коэффициентов функционала для транспортной задачи. <...> Алгоритм строит последовательность решений промежуточных одномерных задач, которые не являются допустимыми для исходной задачи. <...> Получены формулы решений промежуточных двумерных задач с зацепляющимися переменными и последовательно пересчитаны коэффициенты функционалов. <...> При отсутствии допустимого решения сформулирована задача о максимальном потоке для транспортных ограничений с запретами. <...> Методы декомпозиции эффективны во многих оптимизационных задачах со многими переменными и ограничениями [1–16]. <...> В работе [17] представлен итеративный метод решения классической транспортной задачи, в котором последовательно решены задачи с двумя ограничениями из разных групп и с одной связывающей переменной. <...> В алгоритме последовательно пересчитываются коэффициенты целевой функции, затем формулируются одномерные задачи, число которых равно числу ограничений исходной задачи. <...> Полученные решения позволяют найти исходный оптимум или определить систему ограничений на переменные. <...> Допустимые решения этой системы дают оптимальное решение исходной задачи. <...> Если допустимых решений нет (вырождение), то решают задачи о максимальном потоке: находят множество так называемых взаимно удовлетворенных пар, формируют множество обобщенных производителей и потребителей и путем суммирования строят новую исходную задачу с меньшим числом ограничений. <...> А.А. Гурченков, А.П. Тизик, Э.В. Торчинская довательного решения двумерных задач повторяется и алгоритм строит последовательность так называемых псевдорешений с монотонным возрастанием функционала. <...> Здесь <...>

** - вычисляется автоматически, возможны погрешности

Похожие документы:

Похожие документы из РУАЭСТ
|
Похожие документы из Руконт

Вычислительные тесты по декомпозиционному алгоритму для транспортной задачи

Помощь:

Участники: