Вычислительные тесты по декомпозиционному алгоритму для транспортной задачи
Авторы: Гурченков А.А., Тизик А.П., Торчинская Э.В.
Опубликовано в выпуске: #5(29)/2014
DOI: 10.18698/2308-6033-2014-5-1293
Раздел: Информационные технологии
Представлены вычислительные тесты по итеративному методу на основе последовательного пересчета коэффициентов функционала для транспортной задачи. Оптимальное решение получено за три итерации, не использует случая вырождения, совпадает со стандартной программой по методу потенциалов. Использованы стандартные методы теории оптимизации. Алгоритм строит последовательность решений промежуточных одномерных задач, которые не являются допустимыми для исходной задачи. Имеет место монотонный рост по функционалу на псевдорешениях. Получены формулы решений промежуточных двумерных задач с зацепляющимися переменными и последовательно пересчитаны коэффициенты функционалов. Найдено допустимое решение в системе равенств. При отсутствии допустимого решения сформулирована задача о максимальном потоке для транспортных ограничений с запретами. По некоторому правилу сформированы корреспондирующие пары индексов.
Литература
[1] Миронов A.A., Цурков В.И. Approximation and Decomposition by Extremal Graphs. Журнал вычислительной математики и математической физики, 1993, т. 33, № 2, с. 34-39
[2] Миронов А.А., Цурков В.И. Транспортные и сетевые задачи с минимаксным критерием. Журнал вычислительной математики и математической физики, 1995, т. 35, № 1, с. 141-147
[3] Миронов А.А., Цурков В.И. Наследственно минимаксные матрицы в моделях транспортного типа. РАН. ТиСУ, 1998, № 6, с. 67-73
[4] Миронов А.А., Цурков В.И. Transport-Type Problems with a Criterion. Автоматика и телемеханика, 1995, № 12, с. 109-118
[5] Миронов А.А., Цурков В.И. Наследственно минимаксные матрицы в моделях транспортного типа. РАН. ТиСУ, 1998, № 6, с. 89-96
[6] Миронов А.А., Цурков В.И. Транспортные задачи с минимаксным критерием. Докл. РАН, 1996, т. 346, № 2, с. 342-347
[7] Миронов А.А., Цурков В.И. Network Models with Fixed Parameters in Coupling Nodes. 2. Изв. РАН. ТиСУ, 1993, № 6, с. 3-14
[8] Mironov A.A., Levkina T.A., Tsurkov V.I. Minimax Estimations of Expectates of Arc Weights in Integer Networks with Fixed Node Degrees. Applied and Computational Mathematics, 2009, vol. 8, no. 2, pp. 216-226
[9] Cheburakhin I.F., Tsurkov V.I. On the Complexity of Realization of Symmetric Zhegalkin Polynomials. Applied and computational mathematics, 2010, vol. 9, no. 2, pp. 198-219
[10] Averbakh I., Lebedev V., Tsurkov V. Nash Equilibria Solutions in The Competitive Salesmen Problem on a Network. Applied and Computational Mathematics, 2008, vol. 7, no. 1, pp. 54-65
[11] Mironov A.A., Tsurkov V.I. Open Transportation Models with a Minimax Criterion. DokladyMathematics, 2001, vol. 64, no 3, pp. 374-377
[12] Mironov A.A., Tsurkov V.I. A Triplanar Transportation Problem with a Minimax Criterion. Doklady Mathematics, 1996, vol. 54, no. 3, pp. 972-975
[13] Чебурахин И.Ф., Цурков В.И. Оптимизация и автоматизация синтеза симметрических комбинационных автоматов на основе базовых матричных кристаллов. Мехатроника, автоматизация, управление, 2009, № 7, с. 19-29
[14] Чебурахин И.Ф., Цурков В.И. Специальная реляционная база данных для оптимизации и автоматизации синтеза комбинационных автоматов. Мехатроника, автоматизация, управление, 2010, № 9, с. 7-13
[15] Чебурахин И.Ф., Цурков В.И. Синтез дискретных логических устройств обработки информации на основе теории агентов. Мехатроника, автоматизация, управление, 2011, № 3, с. 27-34
[16] Tsurkov V. Aggregation in a Branch Manufacturing Problem and Its Extension. Proc. 13th IFAC Symp. Information Control Problems in Manufacturing, Moscow, 2009, pp. 310-312
[17] Тизик А.П., Цурков В.И. Метод последовательной модификации функционала для решения транспортной задачи. Автоматика и телемеханика, 2012, № 1, с. 148-158
[18] Соколов А.А., Тизик А.П., Цурков В.И. Итеративный метод для транспортной задачи с дополнительными пунктами производства и потребления и квадратичным штрафом. Изв. РАН. ТиСУ, 2013, № 4, с. 88-98
[19] http://math.semestr.ru/transp/index.php