Linear optimization problems on permutations under probabilistic uncertainty: properties and solution

Authors

  • Oleg Oleksiiovych Iemets Полтавський університет економіки і торгівлі, Ukraine
  • Tetiana Mykolaivna Barbolina Полтавський національний педагогічний університет імені В.Г.Короленка, Ukraine

DOI:

https://doi.org/10.20535/SRIT.2308-8893.2016.1.11

Abstract

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.

Author Biographies

Oleg Oleksiiovych Iemets, Полтавський університет економіки і торгівлі

 

Ємець Олег Олексійович

доктор фізико-математичних наук, професор

завідувач кафедри математичного моделювання та соціальної інформатики

тел.  0503047156

поштова адреса 

  м. Полтава-3, а/с 1671, 36003

 

 

 

Tetiana Mykolaivna Barbolina, Полтавський національний педагогічний університет імені В.Г.Короленка

Барболіна Тетяна Миколаївна

кандидат фізико-математичних наук, доцент

завідувач кафедри математичного аналізу та інформатики

 тел. 0503465339

поштова адреса 

пр.Глінки,6а, м.Полтава, 36014

 

 

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.

Published

2016-03-18

Issue

Section

Methods of optimization, optimum control and theory of games