Диссертация (1150701), страница 15
Текст из файла (страница 15)
Сборник материалов 4-й Международнойнаучно-практической конференции. 18 апреля 2014 г. /Отв. ред. Ю. В.Вертакова. — Курск, 2014. — С. 297–301.80. Плотников П. В. Вопросы моделирования распределенных экономическихсистем / П. В. Плотников // Тренды развития современного общества:управленческие, правовые, экономические и социальные аспекты. Сборникматериалов 4-й Международной научно-практической конференции. 1719 сентября 2014 г. /Отв.
ред. А. А. Горохов. — Курск, 2014. — С. 199–202.81. Кривулин Н. К. О решении задачи размещения Ролса на плоскости с ограничениями / Н. К. Кривулин, П. В. Плотников // Междисциплинарные ис-следования в области математического моделирования и информатики.Материалы 7-й научно-практической internet-конференции.
30-31 марта2016 г. /Отв. ред. Ю. C. Нагорнов. — Тольятти, 2016. — С. 18–22.82. Кривулин Н. К. Исследование задачи размещения Ролса с прямоугольной метрикой на отрезке прямой / Н. К. Кривулин, П. В. Плотников //Материалы 7-й всероссийской научной конференции по проблемам информатики СПИСОК-2017. — СПб., 2017. — С. 522–528.83.
Плотников П. В. Прямое решение минимаксной задачи размещения в прямоугольной области на плоскости с прямоугольной метрикой / П. В. Плотников, Н. К. Кривулин // Вестник Санкт-Петербургского университета.Прикладная математика. Информатика. Процессы управления. — 2018.— Т. 14, № 2.84. Golan J. S.
Semirings and their Applications / J. S. Golan. — Springer Scienceand Business Media, 2013. — 396 p.11385. Macaulay F. S. The algebraic theory of modular systems / F. S. Macaulay. —Cambridge University Press, 1994. — 140 p.86. Noether E. Abstrakter Aufbau der idealtheorie in algebraischen Zahl-und Funktionenkörpern / E. Noether // Mathematische Annalen. — 1927. — Vol. 96,N. 1. — P.
26–61.87. Vandiver H. S. Note on a simple type of algebra in which the cancellationlaw of addition does not hold / H. S. Vandiver // Bulletin of the AmericanMathematical Society. — 1934. — Vol. 40, N. 12. — P. 914–920.88. Kleene S. C. Representation of events in nerve nets and finite automata /S. C. Kleene. — Rand project air force, Santa Monica, CA, 1951. — 102 p.89. De Schutter B.
On the ultimate behavior of the sequence of consecutive powersof a matrix in the max-plus algebra / B. De Schutter // Linear Algebra andits Applications. — 2000. — Vol. 307, N. 3. — P. 103–117.90. Cuninghame-Green R. A. Minimax algebra / R. A. Cuninghame-Green. —Berlin: Springer-Verlag, 1979. — 258 p.91. Gaubert S. Methods and applications of (max,+) linear algebra / S.
Gaubert,M. Plus // Annual Symposium on Theoretical Aspects of Computer Science.– Berlin. — 1997. — P. 261–282.92. Litvinov G. L. Maslov dequantization, idempotent and tropical mathematics:A brief introduction / G. L. Litvinov // Journal of Mathematical Sciences. —2007. — Vol. 140, N.
3. — P. 426–444.93. Литвинов Г. Л. Линейные функционалы на идемпотентных пространствах. Алгебраический подход / Г. Л. Литвинов, В. П. Маслов,Г. Б. Шпиз // Доклады РАН. — 1998. — Т. 363, № 3. — С. 298–300.94. Литвинов Г. Л. Идемпотентная математика и интервальный анализ /Г. Л. Литвинов, В. П. Маслов, А.
Н. Соболевский // Вычислительныетехнологии. — 2001. — Т. 6, № 6. — С. 47–70.11495. Krivulin N. K.Max-plusalgebramodelsofqueueingnetworks/N. K. Krivulin // International Workshop on Discrete Event SystemsWODES’96, University of Edinburgh, UK, Aug. 19-21, 1996. — London:IEE,1996. — Vol. 22, N.
3. — P. 76–81.96. Кривулин Н. К. Применение методов тропической математики для оценкиальтернатив на основе парных сравнений / Н. К. Кривулин, В. А. Агеев,И. В. Гладких // Вестник Санкт-Петербургского университета. При-кладная математика.
Информатика. Процессы управления. — 2017. —№ 1. — С. 27–41.97. Krivulin N. K. Tropical optimization problems with application to projectscheduling with minimum makespan / N. K. Krivulin // Annals of OperationsResearch. — 2017. — Vol. 256, N. 1. — P. 75–92.98. Krivulin N. K. Tropical optimization problems in time-constrained projectscheduling / N. K. Krivulin // Optimization.
— 2017. — Vol. 66, N. 2. —P. 205–224.99. Krivulin N. K. Direct solution to constrained tropical optimization problemswith application to project scheduling / N. K. Krivulin // Computational Man-agement Science. — 2017. — Vol. 14, N. 1. — P.
91–113.100. Кривулин Н. К. Решение задач математического программирования сиспользованием методов тропической оптимизации / Н. К. Кривулин,И. В. Романовский // Вестник Санкт-Петербургского университета.Математика. Механика. Астрономия.
— 2017. — Т. 4, № 3. — С. 448–458.101. Cuninghame-Green R. A. Describing industrial processes with interference andapproximating their steady-state behaviour / R. A. Cuninghame-Green //Journal of the Operational Research Society. — 1962. — Vol. 13, N. 1. —P. 95–100.102. Krivulin N. K. A constrained tropical optimization problem: Complete solutionand application example / N. K. Krivulin // G.
L. Litvinov, S. N. Sergeev(Eds.). Tropical and Idempotent Mathematics and Applications. — Moscow:2014. — P. 163–177.115103. Krivulin N. K. Extremal properties of tropical eigenvalues and solutions totropical optimization problems / N. K. Krivulin // Linear Algebra and itsApplications. — 2015. — Vol. 468. — P. 211–232.104. Weber A. Theory of the Location of Industries / A. Weber.
— University ofChicago Press, Chicago, 1929.105. Hakimi S. L. Optimum locations of switching centers and the absolute centersand medians of a graph / S. L. Hakimi // Operations research. — 1964. —Vol. 12, N. 3. — P. 450–459.106. Eiselt H. A.
Pioneering developments in location analysis / H. A. Eiselt,V. Marianov // Foundations of Location Analysis. — 2011. — P. 3–22.107. Francis R. L. Facility layout and location: an analytical approach / R. L. Francis, L. F. McGinnis, J. A. White.
— Pearson College, 1992. — 592 p.108. Mirchandani P. B. Discrete location theory / P. B. Mirchandani, R. L. Francis.— Chichester : Wiley-Interscience, 1991. — 555 p.109. Daskin M. S. Network and discrete location: models, algorithms, and applications / M. S. Daskin. — Wiley-Interscience, 2011. — 520 p.110.
Drezner Z. Facility location: a survey of applications and methods / Z. Drezner.— New York: Springer, 1995. — 571 p.111. Nickel S. Location theory: a unified approach / S. Nickel, J. Puerto. —Berlin,Heidelberg: Springer, 2005. — 437 p.112. Dearing P. M. A network flow solution to a multifacility minimax locationproblem involving rectilinear distances / P. M. Dearing, R. L. Francis // Trans-portation Science. — 1974.
— Vol. 8, N. 2. — P. 126–141.113. Brimberg J. A note on convergence in the single facility minisum location problem / J. Brimberg, R. Chen // Computers and Mathematics with Applications.— 1998. — Vol. 35, N. 9. — P. 25–31.116114. Ogryczak W. Inequality measures and equitable approaches to location problems / W. Ogryczak // Annals of Operations Research. — 2007. — Vol. 167,N. 1.
— P. 61–86.115. Francis R. L. Letter to the Editor—Some Aspects of a Minimax Location Problem / R. L. Francis // Operations Research. — 1967. — Vol. 15, N. 6. —P. 1163–1169.116. Kolokol’tsovV.N.IdempotentstructuresinoptimizationV. N. Kolokol’tsov // Journal of Mathematical Sciences.
—Vol. 104, N. 1. — P. 847–880./2001. —117Приложение AПрограммная реализация вычисления оптимальной области размещения точечногообъектаВ приложении предложена программная реализация рассмотренных в главе3 задач с использованием языка программирования в среде Rgui 3.4.3 (стандартный графический интерфейс). Выбор языка , среди других программныхсредств по обработке данных, обусловлен его кроссплатформенностью, доступностью (нулевая стоимость) и достаточно высокой скоростью обработки больших объемов данных.A.1Программная реализация решения минимаксной задачи размещения без ограничений на область размещения на языке RНиже представлена программная реализация решения минимаксной задачи размещения точечного объекта на плоскости с прямоугольной метрикой безограничений на допустимую область размещения с использованием результатов, полученных в следствии 11.
В результате работы программы полученографическое изображение с оптимальной областью размещения.# Считывание массива исходных данных(координат точек) из файлаdf <- read.table("С:\\data.txt", header = FALSE, sep = "", dec = ".")118#Введение обозначений для константных величинa<-max(df[,1]-df[,2])b<-max(-df[,1]+df[,2])c<-max(df[,1]+df[,2])d<-max(-df[,1]-df[,2])mu<-max((a+b)/2,(c+d)/2)#Вычисление вектора решенияf <- function(x) c((2*x-1)*mu+(1-x)*(a+c)/2-x*(b+d)/2,(1-x)*(c-a)/2-x*(d-b)/2)#Построение графика с набором исходных координат и решениемi<-min(df[,1],df[,2])-1j<-max(df[,1],df[,2])+1plot(i:j, i:j, type = "n")segments(f(0)[1], f(0)[2], f(1)[1], f(1)[2], lwd=5, col= ’red’)points(df[,1],df[,2])Определим сложность предложенного алгоритма.
Для этого вычислим количество операций, которые должен выполнить процессор для получения результата. Пусть количество заданных точек . Для начала, необходимо выполнить 4 арифметические операции для вычисления величины параметров и 55операции для получения значения целевой функции и оптимальных координатобласти размещения. Таким образом потребуется 4 + 55 операций. Сложностьалгоритма можно считать ().119A.2Программная реализация решения минимаксной задачи размещения с ограничениями в виде отрезкапрямой на языке RНиже представлена программная реализация решения минимаксной задачиразмещения точечного объекта на плоскости с прямоугольной метрикой с ограничениями на допустимую область размещения в виде отрезка прямой линиис использованием результатов, полученных в следствии 14. В результате работы программы получено графическое изображение с оптимальной областьюразмещения.# Считывание массива исходных данных(координат точек) из файлаdf <- read.table("С:\\data.txt", header = FALSE, sep = "", dec = ".")#Введение обозначений для константных величинk<-const #коэффициент наклона прямойq<-const #сдвиг прямой вдлоль вертикальной осиf<-const #левая граница ограниченийg<-const #правая граница ограниченийa<-max(df[,1]-df[,2]+df[,3])+qb<-max(-df[,1]+df[,2]+df[,3])-qc<-max(df[,1]+df[,2]+df[,3])-qd<-max(-df[,1]-df[,2]+df[,3])+q#Вычисление решенияif (abs(k)>1){mu<-max( (a+b)/2,(a*(k+1)+c*(k-1))/(2*k),(b*(k+1)+d*(k-1))/(2*k), (c+d)/2,a+min(f*(k-1),g*(k-1)) ,b-max(f*(k-1),g*(k-1)), c-max(f*(k+1),g*(k+1)),d+min(f*(k+1),g*(k+1)) )f <- function(x) (1-x)*max(-max(-(mu-a)/(k-1),120-(-mu+b)/(k-1)),-max(-(mu-d)/(k+1), -(-mu+c)/(k+1)),f)x*max(-max(-(-mu+a)/(k-1), -(mu-b)/(k-1)),-max(-(-mu+d)/(k+1),-(mu-c)/(k+1)),-g)points(f(0),k*f(0)+q, col="red", lwd=5)abline(q, k)}#Вычисление решенияif (abs(k)<=1){mu<-max( (a+b)/2,(a*(k+1)-d*(k-1))/(2*k), (b*(k+1)-c*(k-1))/(2*k),(c+d)/2, a+g*(k-1) , b-f*(k-1), c-g*(k+1), d+f*(k+1) )f <- function(x) (1-x)*max( (mu-a)/(k-1), (-mu+c)/(k+1),f)x*max( (mu-b)/(k-1),(-mu+d)/(k+1),-g)points(f(0),k*f(0)+q, col="red", lwd=5)abline(q, k)}Определим сложность предложенного алгоритма.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
