DOI: https://doi.org/10.15587/1729-4061.2015.36753

Application of interval mathematical models of optimization placement problems of geometric objects

Людмила Григорівна Євсеєва

Abstract


At present, the methods of mathematical modeling of real objects and processes play an important role in developing systems, aimed at processing geometric information. Such systems are based on mathematical models of real world objects, optimization methods and theory of building intelligent systems. The research is focused on the applied aspects of interval mathematical modeling in a geometric design.

The classification of implementations of the interval mathematical model of the basic interval optimization placement problem, many implementations of which covers a broad class of scientific and applied placement problems, according to the type of classification of mathematical programming problems was performed.

Various types of interval mappings of interval mathematical models in Euclidean space for the transition from the optimization problem in interval space to an equivalent optimization problem in Euclidean space were constructed.

The method for solving the interval optimization problem in  as the two-criteria optimization problem in Euclidean space  was further developed.

New science-based developments in the theory of geometric design and interval geometry provide a solution to the important applied problem of accounting errors in modeling and solving optimization problems of geometric design.

The proposed tools for mathematical modeling and solving interval optimization placement problems were used in developing computer programs: "PackingofIntervalParallelepipeds", "PackingofIntervalPolygons", "Simulation of alloy properties".


Keywords


geometric design; interval geometry; interval mathematical model; optimization

References


Stoyan, Yu. G., Yakovlev, S. V. (1986). Matematicheskie modeli i optimizatsionnye metody geometricheskogo proektirovaniia. Kiev: Naukova dumka, 268.

Kantorovich, L. V., Zalgaller, V. A. (1951). Raschet racional'nogo raskroja promyshlennyh materialov. Lenizdat, 197.

Kantorovich, L. V. (1939). Matematicheskie metody organizacii i planirovanija proizvodstva. Lviv: Izd-vo LGU, 68. (vosproizvedeno v sb. «Primenenie matematiki v jekonomicheskih issledovanijah». Moscow, Socjekgiz, 1959).

Kantorovich, L. V. (1940). Ob odnom jeffektivnom metode reshenija nekotoryh klassov jekstremal'nyh zadach. Dokl.AN SSSR, 23 (J5 3), 212–215.

Stoyan, Yu. G., Pankratov, A. V. (2001). Local Optimization Method in Placement Problems of Polygons. Dopovіdі NAN Ukrayni. Ser. A, 9, 98–10.

Yemets, O. A., Yevseeva, L.-G., Romanova, N. G. (2001). A Mathematical Interval Model of a Combinatorial Problem of Packing of Color Rectangles. Cybernetics and Systems Analysis, 37 (3), 408–414.

Chugaj, A. M. (2005). Reshenie zadachi upakovki krugov v vypuklyj mnogougol'nik s pomoshh'ju modificirovannogo metoda suzhajushhihsja okrestnostej. Radiojelektronika i informatika, 1, 58–63.

Stoyan, Y., Yas’kov, G. (2004). A mathematical model and a solution method for the problem of placing various-sized circles into a strip. European Journal of Operational Research, 156 (3), 590–600. doi:10.1016/s0377-2217(03)00137-1

Stoyan, Y., Yaskov, G. (1998). Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints. International Transactions in Operational Research, 5 (1), 45–57. doi:10.1016/s0969-6016(98)00003-3

Dowsland, K. A., Gilbert, M., Kendall, G. (2006). A local search approach to a circle cutting problem arising in the motor cycle industry. Journal of the Operational Research Society, 58 (4), 429–438. doi:10.1057/palgrave.jors.2602170

Dowsland, K. A., Herbert, E. A., Kendall, G., Burke, E. (2006). Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems. European Journal of Operational Research, 168 (2), 390–402. doi:10.1016/j.ejor.2004.04.030

Burke, E. K., Kendall, G., Whitwell, G. (2004). A New Placement Heuristic for the Orthogonal Stock-Cutting Problem. Operations Research, 52 (4), 655–671. doi:10.1287/opre.1040.0109

Burke, E. K., Hellier, R. S. R., Kendall, G., & Whitwell, G. (2010). Irregular Packing Using the Line and Arc No-Fit Polygon. Operations Research, 58(4-part-1), 948–970. doi:10.1287/opre.1090.0770

Milenkovic, V. (1999). Translational polygon containment and minimal enclosure using mathematical programming. International Transactions in Operational Research, 6 (5), 525–554. doi:10.1016/s0969-6016(99)00007-6

Oliveira, J. F., Gomes, A. M., Ferreira, J. S. (2000). TOPOS – A new constructive algorithm for nesting problems. OR Spektrum, 22 (2), 263. doi:10.1007/s002910050105

Scheithauer, G., Stoyan, Y. G., Romanova, T. Y. (2005). Mathematical Modeling of Interactions of Primary Geometric 3D Objects. Cybernetics and Systems Analysis, 41 (3), 332–342. doi:10.1007/s10559-005-0067-y

Moore, R. E. (1966). Interval analysis. N.Y.: Prentice-Hall, 400.

Kaucher, E. (1980). Interval Analysis in the Extended Interval Space IR. Fundamentals of Numerical Computation (Computer-Oriented Numerical Analysis). Computing Supplementum, 2, 33–49. doi:10.1007/978-3-7091-8577-3_3

Markov, S. M. (1992). Extended interval arithmetic involving infinite intervals. Mathematica Balkanika, 6, 269–304.

Hansen, E. R. (1992). Bounding the Solution of Interval Linear Equations. SIAM Journal on Numerical Analysis, 29(5), 1493–1503. doi:10.1137/0729086

Alefeld, G., Hertsberger, Yu. (1987). Vvedenie v interval'nye vychisleniia. Moscow: Mir, 356.

Kalmykov, S. A., Shokin, Yu. I., Yuldashev, Z. H. (1986). Metody interval'nogo analiza. Novosibirsk: Nauka, 224.

Shary, S. P. (1994). Solving the tolerance problem for interval linear equations. Interval Computations, 2, 6–26.

Stoyan, Yu. G. (2006). Vvedennia v іnterval'nu heometrіiu. Kharkiv: KhNURE, 98.

Stoyan, Yu. G. (1996). Metricheskoe prostranstvo tsentrirovannyh intervalov. Doklady NAN Ukrainy. Ser. A, 7, 23–25.

Stoyan, Yu. G. (1996). Interval'nye otobrazheniia. Dopovіdі NAN Ukrayni, 10, 57-63.

Stoyan, Yu. G., Romanova, T. E. (1998). Account of errors in optimization placement problem. Problemy mashinostroeniia, 1 (2), 31–41.

Romanova, T. E. (2000). Interval'noe prostranstvo InsR. Doklady NAN Ukrainy, 9, 36–41.

Yevseeva, L. G. (2014). Means for building of mathematical models of optimization placement problems in the interval spaces. Technology audit and production reserves, 6/3(20), 66–73.

Grebennik, I. V., Evseeva, L. G., Romanova, T. E. (2004). Osnovnaja optimizacionnaja zadacha geometricheskogo proektirovanija v interval'nom vide. Radiojelektronika. Informatika. Upravlenie, 2, 68–72.

Yevseeva, L. G. (2008). Matematicheskaia model' i metod resheniia zadachi upakovki interval'nyh parallelepipedov. Doklady NAN Ukrainy, 2, 48–53.

Stoyan, Yu. G., Pankratov, O. V., Yevseeva, L. G. (2008). A. s. № 24827 Ukrayna. Kompiuterna programa “Packing of Interval Parallelepipeds”. Appl. 01.04.2008.

Yevseeva, L. G., Chugai, A. N. (2007). Zadacha upakovki interval'nyh tsilindrov v interval'nuiu prizmu. Sistemi upravlіnnia, navіgatsіi ta zviazku. Kiyv, 121–128.

Yevseeva, L. G., Yas'kov, G. N. (2010). Primenenie interval'nogo modelirovaniia v poroshkovoi metallurgii. Radіoelektronnі і kompiuternі sistemi, 7 (48), 95–98.

Stoyan, Yu. G., Yevseeva, L. G., Yas'kov, G. N. (2009). A. s. № 27362 Ukrayna. Kompiuterna programa “Imitatsionnoe modelirovanie svoistv splava”. Appl. 30.12.2008.

Pankratov, O. V., Yevseeva, L. G. (2008). A. s. № 25506 Ukrayna. Kompiuterna programa “Packing of Interval Polygons”. Appl. 12.07.2008.


GOST Style Citations


Стоян, Ю. Г. Математические модели и оптимизационные методы геометрического проектирования [Текст] / Ю. Г. Стоян, С. В. Яковлев. – Киев: Наукова думка, 1986. – 268 с.

Канторович, Л. В. Расчет рационального раскроя промышленных материалов [Текст] / Л. В. Канторович, В. А. Залгаллер. – Лениздат, 1951 – 197 с.

Канторович, Л. В. Математические методы организации и планирования производства [Текст] / Л. В. Канторович. – в сб. «Применение математики в экономических исследованиях». – Изд-во ЛГУ, 1939. – 68 с.

Канторович, Л. В. Об одном эффективном методе решения некоторых классов экстремальных задач [Текст] / Л. В. Канторович // Доклады АН СССР. – 1940 – Т. 23, J5 3. – С. 212–215.

Stoyan, Yu. G. Local Optimization Method in Placement Problems of Polygons [Text] / Yu. G. Stoyan, A. V. Pankratov // Доповіді НАН України. – 2001. – № 9. – P. 98–103.

Yemets, O. A. A Mathematical Interval Model of a Combinatorial Problem of Packing of Color Rectangles [Text] / O. A. Yemets, L.-G. Yevseeva, N. G. Romanova // Cybernetics and Systems Analysis. – 2001. – Vol. 37, Issue 3. – P. 408–414.

Чугай, А. М. Решение задачи упаковки кругов в выпуклый многоугольник с помощью модифицированного метода сужающихся окрестностей [Текст] / А. М.Чугай // Радиоэлектроника и информатика. – 2005. – № 1. – С. 58–63.

Stoyan, Y. A mathematical model and a solution method for the problem of placing various-sized circles into a strip [Text] / Y. Stoyan, G. Yas’kov // European Journal of Operational Research. – 2004. – Vol. 156, Issue 3. – P. 590–600. doi: 10.1016/s0377-2217(03)00137-1

Stoyan, Y. Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints [Text] / Y. Stoyan, G. Yaskov // International Transactions in Operational Research. – 1998. – Vol. 5, Issue 1. – P. 45–57. doi:10.1016/s0969-6016(98)00003-3

Dowsland, K. A. A local search approach to a circle cutting problem arising in the motor cycle industry [Text] / K. A. Dowsland, M. Gilbert, G. Kendall // Journal of the Operational Research Society. – 2006. – Vol. 58, Issue 4. – P. 429–438. doi: 10.1057/palgrave.jors.2602170 

Dowsland, K. A. Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems [Text] / K. A. Dowsland, E. A. Herbert, G. Kendall, E. Burke // European Journal of Operational Research. – 2006. – Vol. 168, Issue 2. – P. 390–402. doi: 10.1016/j.ejor.2004.04.030 

 Burke, E. K. A new placement heuristic for the orthogonal stock-cutting problem [Text] / E. K. Burke, G .Kendall, G. Whitwell // Operations Research. – 2004. – Vol. 52, Issue 4. – P. 655–671. doi: 10.1287/opre.1040.0109 

Hellier, R. Irregular Packing Using the Line and Arc No-Fit Polygon [Text] / R. Hellier, G .Kendall, G. Whitwell // Operations Research. – 2010. – Vol. 58, Issue 4. –P. 948–970. doi: 10.1287/opre.1090.0770 

Milenkovic, V. J. Translational polygon containment and minimal enclosure using mathematical programming [Text] / V. J. Milenkovic, K. Daniels // International Transactions in Operational Research. – 1999. – Vol. 6, Issue 5. – P. 525–554. doi:10.1111/j.1475-3995.1999.tb00171

Oliveira, J. F. TOPOS – A new constructive algorithm for nesting problems [Text] / J. F. Oliveira, A. M. Gomes, J. S. Ferreira // OR Spektrum. – 2000. – Vol. 22, Issue 2. – P. 263–284. doi: 10.1007/s002910050105 

Scheithauer, G. Mathematical modeling of interactions of primary geometric 3D objects [Text] / G. Scheithauer, Yu. Stoyan, T. Romanova // Cybernetics and Systems Analysis. – 2005. – Vol. 41, Issue 3. – P. 332–342. doi: 10.1007/s10559-005-0067-y 

Moore, R. E. Interval analysis [Text] / R. E. Moore. – N.Y.: Prentice-Hall, 1966. – 400 p.

Kaucher, E. Interval Analysis in the Extended Interval Space IR [Text] / E. Kaucher // Fundamentals of Numerical Computation (Computer-Oriented Numerical Analysis). Computing Supplementum. – 1980. – Vol. 2. – P. 33–49. doi:10.1007/978-3-7091-8577-3_3

Markov, S. M. Extended interval arithmetic involving infinite intervals [Text] / S. M. Markov // Mathematica Balkanika. – 1992. – Vol. 6. – P. 269–304.

Hansen, E. Bounding the solution of interval linear equations [Text] / Е. Hansen // SIAM Journal on Numerical Analysis. 1992. Vol. 29, Issue 5. P. 1493–1503. doi: 10.1137/0729086 

Алефельд, Г. Введение в интервальные вычисления [Текст] / Г. Алефельд, Ю. Херцбергер. – М.: Мир, 1987. – 356 с.

Калмыков, С. А. Методы интервального анализа [Текст] / С. А. Калмыков, Ю. И. Шокин, З. Х. Юлдашев. – Новосибирск: Наука, 1986. – 224 с.

Shary, S. P. Solving the tolerance problem for interval linear equations [Text] / S. P. Shary // Interval Computations. – 1994. – Vol. 2. – P. 6–26.

Стоян, Ю. Г. Введення в інтервальну геометрію [Текст]: навч. пос. / Ю. Г. Стоян. – Х.: ХНУРЕ, 2006. – 98 с.

Стоян, Ю. Г. Метрическое пространство центрированных интервалов [Текст] / Ю. Г. Стоян // Доклады НАН Украины. Сер. A. – 1996. – № 7. – С. 23–25.

Стоян, Ю. Г. Интервальные отображения [Текст] / Ю. Г. Стоян // Доповіді НАН України. – 1996. – № 10. – С. 57–63.

Стоян, Ю. Г. Account of errors in optimization placement problem [Текст] / Ю. Г. Стоян, Т. Е. Романова // Проблемы машиностроения. – 1998. – Т. 1, № 2. – С. 31–41.

Романова, Т. Е. Интервальное пространство InsR [Текст] / Т. Е. Романова // Доклады НАН Украины. – 2000. – № 9. – С. 36–41.

Євсеєва, Л. Г. Засоби побудови математичних моделей задач оптимізаційних розміщення в інтервальних просторах [Текст] / Л. Г. Евсеева // Технологический аудит и резервы производства. – 2014.– Т. 6, № 3 (20). –С. 66–73.

Гребенник, И. В. Основная оптимизационная задача геометрического проектирования в интервальном виде [Текст] / И. В. Гребенник, Л. Г. Евсеева, Т. Е. Романова // Радиоэлектроника. Информатика. Управление. – 2004. – № 2. – С. 68–72.

Евсеева, Л. Г. Математическая модель и метод решения задачи упаковки интервальных параллелепипедов [Текст] / Л. Г. Евсеева // Доклады НАН Украины. – 2008. – № 2. – С. 48–53.

А. с. № 24827 Україна. Комп’ютерна програма “Packing of Interval Parallelepipeds” [Текст] / Стоян Ю. Г., Панкратов О. В., Євсеєва Л. Г. – заявл. 01.04.08; опубл. 25.06.08.

Евсеева, Л. Г. Задача упаковки интервальных цилиндров в интервальную призму [Текст] / Л. Г. Евсеева, А. Н. Чугай // Системи управління, навігації та зв’язку. – Київ, 2007. – С. 121–128.

Евсеева, Л. Г. Применение интервального моделирования в порошковой металлургии [Текст] / Л. Г. Евсеева, Г. Н. Яськов // Радіоелектронні і комп’ютерні системи. – 2010. – № 7 (48). – С. 95–98.

А. с. № 27362 Україна. Комп’ютерна програма “Имитационное моделирование свойств сплава” [Текст] / Стоян Ю. Г., Євсеєва Л. Г., Яськов Г. Н. – заявл. 30.12.08; опубл. 23.01.09.

А. с. № 25506 Україна. Комп’ютерна програма “Packing of Interval Polygons” [Текст] / Панкратов О. В., Євсеєва Л. Г. – заявл. 12.07.08; опубл. 28.08.08.







Copyright (c) 2015 Людмила Григорівна Євсеєва

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN (print) 1729-3774, ISSN (on-line) 1729-4061