ДЕКОМПОЗИЦИОННЫЙ ПОДХОД НА ОСНОВЕ БРОУНОВСКОЙ ИТЕРАЦИИ ДЛЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, ГДЕ ВСЕ БАЗИСНЫЕ МАТРИЦЫ ЯВЛЯЮТСЯ М-МАТРИЧНЫМИ

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Предложена новая схема решения задачи линейного программирования. Основным свойством, отличающим рассматриваемую задачу, является то, что базисные подматрицы ее матрицы состоят только из М-матриц. Основываясь на возможности, создаваемой этим свойством, матричная игра с той же структурой и размером, что и ее матрица, сопоставляется с данной задачей, и показана возможность построения оптимального базиса задачи путем частичного выполнения броуновской итерации, приводящей к оптимальной стратегии второго игрока. Таким образом, мы разбиваем решение задачи на выполнение конечного числа броуновских итераций. Показаны области применения схемы решения. Схему иллюстрирует числовой пример. Также показана возможность замены игровой матрицы на матрицу из целых элементов. Это свойство позволяет точно выполнять броуновскую итерацию. Библ. 38.

Об авторах

Р. Г Хамидов

Бакинский Государственный Университет

Автор, ответственный за переписку.
Email: shekhamidov@gmail.com
Баку, Азербайджан

М. М Муталлимов

Институт прикладной математики, Бакинский Государственный Университет; Институт информационных технологий, Министерство Науки и Образования Азербайджана; Азербайджанский технический университет

Email: mmutallimov@yahoo.com
Баку, Азербайджан; Баку, Азербайджан; Баку, Азербайджан

Ф. А Алиев

Институт прикладной математики, Бакинский Государственный Университет; Институт информационных технологий, Министерство Науки и Образования Азербайджана

Email: f_aliev@yahoo.com
Баку, Азербайджан; Баку, Азербайджан

Список литературы

  1. Tsurkov V.I. Decomposition in large scale problems. Moscow: Nauka, 1981.
  2. Tsurkov V.I. Dynamic problems of large dimension. Moscow: Nauka, 1988.
  3. Abade J.M., Williams A.C. Dual and parametric methods in decomposition. Recent advances math. program. N.Y. Mc. Graw-Hill, 1963.
  4. Belenkiy V.Z. On problems of mathematical programming with a minimal points // RAS USSR. 1968. V. 183. № 1. P. 15–19.
  5. Benders J.C. Partitioning procedures for solving mixed variables programming problems // Numer. math. 1962, № 4, P. 238–252.
  6. Berger U. Fictions Play in 2 × n Games // Journal of Economic Theory. 2005. V. 120. P. 139–154.
  7. Brown G.W. Iterative solutions of game by fictions play. In Activity Analysis of Productions and allocation, T.C. Koopmans (ED). New York: Wiley, 1951.
  8. Champolle A., Pock T. A first – order primal – dual algorithm for convex problems with application in imaging // Journal of mathematical imaging and vision. 2011. V. 40. I. 1. P. 120–145.
  9. Dantzig G.B. Wolfe P. Decomposition algorithm for linear programs // Econometrica. 1961. V. 29. I. 4. P. 767–778.
  10. Dantzig G.B., Wolf P. Decomposition algorithm for linear programming // Mathematics. 1964. V. 8. I. 1. P. 73–79.
  11. Dantzig G.B. Wolfe P. Decomposition principle for linear programs // Oper. Res. 1960. V. 8, I. 1. P. 101–111.
  12. Gale D. Theory of linear economic models. New York: McGraw-Hill. 1960.
  13. Geoffrion A.M. Relaxation and the dual method in mathematical programming. Working paper 135. Western management science institute. Los Angeles: University of California. 1968.
  14. Gilpin A., Pena J., Sandholm T. First – order algorithm with 0(ln(1/2)) convergence for ε – equilibrium in two – person zero – sum games // Mathematical programming. 2012. V. 133. I. 1. P. 279–298.
  15. He B. and Yuan X. Convergence analysis of primal – and dual algorithm for a saddle – point problem: from construction perspective // SIAM Journal and Imagines Sciences. 2012. V. 5. I. 1. P. 119–149.
  16. Hui – Min Li., Ke – Cun Zhang. A decomposition algorithm for solving large – scale quadratic programming problems // Applied mathematics and computations. 2006. V. 173. I. 1 P. 394–403.
  17. Kornai I., Liptak T. Planning on two levels // Application of mathematics in economic studies. 1965. V. 3.
  18. Krishna V., Sjostrom T. On the convergence of fictions play // Math. Operations Res. 1998. V. 23. P. 479–511.
  19. Lasdon L. Optimization of large systems. Moscow: Nauka,1975.
  20. Lin T., Ma S., Ye Y., Zang S. An Alternating Direction Method of Multipliers algorithm – based interior – point method for large – scale linear programming // Optimization Method and Software. 2021. V. 36. No. 2–3. P. 389–424.
  21. Malitsky Y., Pock T. A first – order primal dual algorithm with line search // SIAM Journal an Optimization. 2018. V. 28. No. 1. P. 411–432.
  22. Meerov M.V. Research and optimization of multivariable control systems. Moscow: Nauka, 1986.
  23. Nachbar J. “Evaluationary” Selection Dynamics in Games. Convergence and limit properties // International Journal of Game Theory. 1990. V. 19. P. 59–89.
  24. Owen G. Game theory. M., Moscow: MIR, 1971.
  25. Pervozvanskaya T.N., Pervozvanskiy A.A. Algorithm search for optimal distribution of centralized resources. Proceedings of AS USSR. Technical Cybernetics, 3, 55–67 (1966).
  26. Robinson J. An iterative method of solving a game // Annals of Mathematics. 1951. V. 54. P. 296–301.
  27. Rosen J.B. Convex partition programming, in recent advances in mathematical programming. New York: McGraw-Hill, 1963.
  28. Shchennikov B.A. Aggregation methods for solving a system of linear equations // RAS USSR. 1967. V. 173. № 4. P. 781–784.
  29. Volkonsky V.A. Optimal planning in conditions of large dimension. Iterative methods and the principled decomposition // Economical and mathematical method. 1965. V. 1. No. 2. P. 195–219.
  30. Qiao D., Wang X.K., Wang J.Q., Li L. Maximum entropy-based method for extracting the underlying probability distributions of Z-number // Applied and Computational Mathematics. 2024. V. 23. No. 2. P. 201–218.
  31. Aliev F.A., Hajiyeva N.S., Mutallimov M.M., Velieva N.I., Namazov A.A. Algorithm for solution of linear quadratic optimization problem with constraint in the form of equalities on control // Applied and Computational Mathematics. 2024. V. 23. No. 3. P. 404–414.
  32. Ozbay H., Srikant R. Yuskei S. Preface of the special issue: control, teams, and games // Applied and Computational Mathematics. 2024. V. 23. No. 3. P. 281–281.
  33. Hamidov S.I. Effective trajectories of economic dynamics models on graphs // Applied and Computational Mathematics. 2023. V. 22. No. 2. P. 215–224.
  34. Aliev F.A., Hajiyeva N.S. Discrete linear quadratic optimization problem with constraints in the form of equalities on control action // TWMS J. App. and Eng. Math. 2024. V. 14. No. 4. P. 1466–1472.
  35. Aliev F., Hajiyeva N., Velieva N., Mutallimov M., Tagiyev R. Constructing Optimal Regulator for Discrete Linear Quadratic Optimization Problem with Constraints on Control Action // Proceedings of the 9 th International Conference on Control and Optimization with Industrial Applications (COIA 2024). 2024. P. 194–197.
  36. Aliev F.A., Jamalbayov M.A., Valiyev N.A., Handajiyeva N.S. Computer model of pump–well–reservoir system based on the new concept of imitational modeling of dynamic systems // International Applied Mechanics. 2023. V. 59. No. 3. P. 352–362.
  37. Aliev F., Mutallimov M., Hajiyeva N., Velieva N., Abbasov A., Ismayilov N.A. Optimal Regulators for Multipoint Problems of Dynamic Systems // Proceedings of the 9 th International Conference on Control and Optimization with Industrial Applications (COIA 2024). 2024. P. 332–335.
  38. Aliev F., Hajiyeva N., Velieva N., Mutallimov M., Tagiyev R. Constructing Optimal Regulator for Discrete Linear Quadratic Optimization Problem with Constraints on Control Action, Proceedings of the 9 th International Conference on Control and Optimization with Industrial Applications (COIA 2024). 2024. P. 194–197.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2025

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».