Необходимые и достаточные условия существования решений у распределительной задачи с ограничениями

Феликс Майорович Кемпер

ПРЕПРИНТ

Эта статья является препринтом и не была отрецензирована.
О результатах, изложенных в препринтах, не следует сообщать в СМИ как о проверенной информации.

Необходимые и достаточные условия существования решений у распределительной задачи с ограничениями

Ф. М. Кемпер

2025-01-10

https://doi.org/10.24108/preprints-3113117

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

Ссылка для цитирования:

Кемпер Ф. М. 2025. Необходимые и достаточные условия существования решений у распределительной задачи с ограничениями. PREPRINTS.RU. https://doi.org/10.24108/preprints-3113117

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

1. Форд Л., Фалкерсон Д. Потоки в сетях, пер. с англ. Москва:ИЛ, 1966. 278с.

2. Ху Т. Целочисленное программирование и потоки в сетях. Москва:Мир, 1974. 520с.

3. Филлипс Д., Гарсия-Диас А. Методы анализа сетей, пер. с англ. Москва:Мир, 1984. 496с.

4. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 3-е изд. Москва:Вильямс, 2013. 1328с.

5. Berge C. Graphs. Amsterdam, Elsevier Science Publishers, 1991. 413p.

6. Ahuja R.K., Magnanti T.L., Orlin J.B. Network Flows : Theory, Algorithms, and Applications. NY, Prentice Hall, 1993. 846p.

7. Берж К. Теория графов и ее применение, пер. с франц. Москва:ИЛ, 1962. 320с.

8. Родионов В.В. Параметрическая задача о кратчайших расстояниях. Ж. вычисл. матем. и матем. физ. 1968. Т.8. №5. С.1173-1177.

9. Швецов В.И. Алгоритмы распределения транспортных потоков. Автоматика и телемеханика. 2009. №10.

10. Гасникова Е.В., Гасников А.В., Ярмошик Д.В. и др. О многостадийной транспортной модели и достаточных условиях ее потенциальности. Математическая теория игр и её приложения. 2023. Т.15. №2. С.3-17.

11. Йенсен П., Барнес Д. Потоковое программирование, пер. с англ. Москва:Радио и связь, 1984. 392с.

12. Лотоцкий В.А., Мандель А.С. Модели и методы управления запасами. Москва:Наука, 1991. 188с.

13. Малашенко Ю.Е., Новикова Н.М. Модели неопределенности в многопользовательских сетях. Москва:Эдиториал УРСС, 1999. http://www.ccas.ru/depart/malashen/papper/pp.htm

14. Боженюк А.В., Герасименко Е.М. Разработка алгоритма нахождения максимального потока минимальной стоимости в нечеткой динамической транспортной сети. Инженерный вестник Дона. 2013. №1. http://www.ivdon.ru/ru/magazine/archive/n1y2013/1583

15. Колесников К.Г., Масалкин А.А., Москвин Б.В. Параметрическая оптимизация информационного обмена в сети связи с динамически изменяющейся структурой.

16. Труды военно-космической академии имени А.Ф. Можайского. 2019. №668. С.31-36.

17. Черников С. Н. Линейные неравенства. Москва:Наука, ГРФМЛ, 1968. 488с.

18. Hoffman A.J. Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. Combinatorial Analysis, edited by R. Bellman and M. Hall, pp.113-128. Providence, American Mathematical Society, 1960. 311p.

19. Lawler E.L. Combinatorial Optimization: Networks and Matroids. NY, Holt, Rinehart and Winston, 1976. 374p.

20. https://github.com/Gilbert00/TransportNet

21. Даффин Р., Питерсон Е., Зенер К. Геометрическое программирование, пер. с англ. Москва:Мир, 1972. 311с.

ПРЕПРИНТ

ИНФОРМАЦИЯ