Linear optimization problems on permutations under probabilistic uncertainty: properties and solution
DOI:
https://doi.org/10.20535/SRIT.2308-8893.2016.1.11Abstract
Authors study properties of linear optimization problems under probabilistic uncertainty while defining a problem based on the linear order on the set of discrete random variables. Properties of unconditional problem are established whose coefficients of the goal function or multiset's elements (but not both simultaneously) are discrete random variables. Based on properties of the solution of an unconditional problem with deterministic coefficients, we prove solution's properties for the problem with the goal function's coefficients as discrete random variables. The scheme of the branch and bound method for solving the linear optimization problems on permutations under probabilistic uncertainty is proposed as well as rules of branching and truncation of sets.References
Sergienko I.V. Modeli i metody reshenija na EVM kombinatornyh zadach optimizatsii / Y.V. Serhyenko, M.F. Kaspshytskaja. — K. : Nauk. dumka, 1981. —288 s.
Zgurovskij M.Z. Prinjatie reshenij v setevyh sistemah s ogranichennymi resursami / M.Z. Zhurovskyj, A.A. Pavlov. — K.: Nauk. dumka, 2010. —573 s.
Sergienko I.V. Klassifikatsija prikladnyh metodov kombinatornoj optimizatsii / I.V. Sergienko, L.F. Guljanitskij, S.I. Sirenko // Kibernetika i sistemnyj analiz. — 2009. — № 5. — S. 71–83.
Ctojan Ju.H. Teorija i metody evklidovoyi kombinatornoyi optymizatsiyi / Ju.H. Ctojan, O.O. Yemets'. — K.: In-t system. doslidzhen' osvity, 1993. — 188 s. — Available at: http://dspace.puet.edu.ua/handle/123456789/487.
Emets O.A. Kombinatornaja optimizatsija na razmeschenijah / O.A. Emets, T.N. Barbolyna. — K.: Nauk. dumka, 2008. — 159 s. — Available at: http://dspace.puet.edu.ua/handle/123456789/473.
Sergienko I.V. Primenenie metodov stohasticheskoj optimizatsii dlja issledovanija transformatsionnyh protsessov v ekonomike / I.V. Sergienko, M.V. Mihalevich // Systemni doslidzhennja ta informatsijni tekhnolohiyi. — 2004. — № 4. — S. 7–29.
Ermol'ev Ju.M. Stohasticheskie modeli i metody v ekonomicheskom planirovanii / Ju.M. Ermol'ev, A.I. Jastremskij. — M.: Nauka. Gl. red. fiziko-matem. lit-ry, 1979. — 256 s.
Naumov A.B. Issledovanie zadachi stohasticheskogo linejnogo programmirovanija s kvantil'nym kriteriem / A.B. Naumov, C.B. Ivanov // Avtomatika i telemehanika. — 2011. — № 2. — S. 142–158.
Marti K. Stochastic Optimization Methods.–Springer-Verlag Berlin Heidelberg / K.Marti. — 2008. — 340 p.
Perepelitsa V.A. Diskretnaja optimizatsija i modelirovanie v uslovijah neopredelennosti dannjah / V.A. Perepelitsa, F.B. Tebueva. — M.: Akademija estestvoznanija. — 2007. — 151 s.
Tebueva F. B. Prinjatie reshenij v diskretnyh zadachah optimizatsii na grafah s nechetkimi vesami / F.B. Tebueva // Gornyj informatsionno-analiticheskij bjulleten'. — 2008. —№ 6. — S. 373–391.
Seraja O.V. Nechetkaja zadacha kommivojazhera / O.V. Seraja // Matematicheskoe modelirovanie. — 2007. — № 2 (17). — S. 13–15.
Seraja O.V. Stohasticheskaja zadacha kommivojazhera / O.V. Seraja, L.V. Bachkir // Vestn. Nats. tehn. un-ta "Har'kovskij politehnicheskij institut". Serija: Informatika i modelirovanie. — 2006. — № 40. —S. 169–173.
Nikolova E. Approximation algorithms for reliable stochastic combinatorial optimization / E. Nikolova // Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer–Berlin: Heidelberg, 2010. — P. 338–351.
Stojan Ju.G. Optimizatsionnaja zadacha razmeschenija pravil'nih interval'nyh mnogougol'nikov / Ju.G. Stojan, T.E. Romanova, Ju.A. Sysoeva // Dokl. NAN Ukrainy. — 1998. — № 9. — S. 114–120.
Grebennik I.V. Otobrazhenie interval'nyh kombinatornyh mnozhestv v evklidovo prostranstvo / I.V. Grebennik, T.E. Romanova // Problemy mashinostroenija. — 2002. — 5. — № 2. — S. 87–91.
Grebennik I.V. Klassy interval'nyh kombinatornyh optimizatsionnyh zadach geometricheskogo proektirovanija / I.V. Grebennik, T.E. Romanova, S.B. Shehovtsov // Iskusstvennyj intellekt. — 2005. — № 3. — S. 18–24.
Yemets' O.O. Rozv'jazuvannja zadach kombinatornoyi optymizatsiyi na nechitkykh mnozhynakh / O.O. Yemets', O.O. Yemets'. — Poltava: PUET, 2011. — 239 s. — Available at: http://dspace.uccu.org.ua/handle/123456789/352.
Sergienko I.V. Zadachi optimizatsii s interval'noj neopredelennost'ju: metod vetvej i granits / I.V. Sergienko, O.A. Emets, A.O. Emets // Kibernetika i sistemnyj analiz. — 2013. — № 5. — S. 38–50.
Emets O.A. Ob optimizatsionnyh zadachah s verojatnostnoj neopredelennost'ju / O.A. Emets, T.N. Barbolina // Dop. NAN Ukrayiny. — 2014. — № 11. — S. 40–45.
Yemets' O.O. Pobudova i doslidzhennja matematychnoyi modeli zadachi dyrektora zi stokhastychnymy parametramy / O.O. Yemets', T.M. Barbolina // Visn. Cherkas'koho un-tu. Serija: Prykladna matematyka. Informatyka. — 2014. — № 18 (311). — S. 3–11.
Barbolina T.M. Rozv'jazuvannja linijnykh bezumovnykh optymizatsijnykh zadach na rozmishchennjakh z imovirnisnoju nevyznachenistju / T.M. Barbolina, O.O. Yemets' // Materialy VI Vseukr. nauk.-prakt. konf. za mizhnarodnoju uchastju "Informatyka ta systemni nauky" (m. Poltava, 19–21 berez. 2015 r.). — Available at: http://dspace.puet.edu.ua/handle/123456789/2384.
