DOI: https://doi.org/10.20998/2079-0023.2018.22.05

Метод поэлементной многокритериальной композиции оптимальных маршрутов в транспортных сетях

Lev Raskin, Oksana Sira, Yurii Parfeniuk

Анотація


Запропоновано простий метод відшукання оптимальних маршрутів у транспортній задачі лінійного програмування. Задача вирішена із використанням сукупності критеріїв: середня сумарна вартість перевезень, тривалість та надійність виконання плану. Модель задачі – орієнтований граф. Вершинам графа відповідають проміжні пункти на множині магістралей, що з’єднують пункти виробництва і споживання. Дуги, що з’єднують вершини графа, розмічені числами, які задають середню вартість транспортування одиниці продукту через ділянку маршруту, що відповідають дузі, середній тривалості транспортування вздовж цієї ділянки та ймовірності подолання маршруту. Для вирішення задачі запропонована міра ефективності використання ділянок, що має адитивні властивості, тобто міра результату об’єднання двох ділянок дорівнює сумі мір цих ділянок. Міра враховує значення для всіх трьох критеріїв. Описана обчислювальна процедура, що реалізуює метод та не вимагає комбінаторного перебору варіантів і забезпечує можливість швидкого отримання компромісного результату. Процедура заснована на використанні запропонованої спеціальної операції комутації матриць. Ця операція забезпечує можливість розрахунку міри ефективності всіх можливих двокрокового, потім трикрокового і далі k-крокових шляхів. Операція ітераційно триває до тих пір, поки не буде знайдена міра маршруту, що з’єднує початковий пункт із кінцевим. Важливою додатковою перевагою методу є можливість його використання для відшукання ефективних маршрутів в складних транспортних мережах з великою кількістю проміжних пунктів. При цьому, якщо перехід від одного з пунктів в інший може бути здійснений через будь-який проміжний пункт з деякої їх множини, то метод дозволяє знайти найкращий із можливих маршрутів. Розглянуто приклади розв’язання задачі для різних формулювань багатокритеріальної транспортної задачі.

Ключові слова


пошук оптимальних маршрутів; транспортна задача лінійного програмування; багатокритеріальність; модель системи на основі орієнтованого графа; спеціальна операція комутації матриць; адитивна міра врахування сукупності критеріїв

Повний текст:

PDF (Русский)

Посилання


Intriligator М. Matematicheskie metodyi optimizatsii ekonomicheskaya teoriya [Mahematical optimization and economic theory]. Мoscow, Airis–Press Publ., 2002. 564 p.

Ventcel E. S. Issledovanie operatsiy [Operations research]. Мoscow, Vysshaya shkola Publ., 2001. 208 p.

Kuznetcov A. V.,Sakovich V. A., Holod N. I. Vyisshaya matematika. Matematicheskoe programmirovanie [Higher mathematics. Mathematical Programming]. Minsk, Vyshjejshaja shkola Publ., 2001. 351 p.

Raskin L. G. Analiz slozhnyih sistem i elementyi teorii optimalnogo upravleniya [Analysis of complex systems and elements of optimal control theory]. Мoscow, Sovetskoe radio Publ., 1979. – 344 p.

Raskin L. G. Matematicheskie metodyi issledovaniya operatsiy i analiza slozhnyih sistem vooruzheniya PVO [Mathematical methods of investigation of operations and analysis of complex air defense systems]. Kharkov, WIRTA 1988. 177 p.

Raskin L. G., Sira O. V. Nechetkaya matematika [Fuzzy Mathematics]. Kharkov, Parus Publ., 2008. 352 p.

Ehrgott M. Multicriteria Optimizahion. Springer Publ., 2005. 323 p.

Steuer R. E. Multiple Criteria Optimizahion. New York, John Wiley Publ., 1986. 546 p.

Sira O. V., Klimeko T. A.,Samorodov V. B. Vyibor kriteriya optimizatsii v zadache upravleniya mnogonomenklaturnyimi zapasami [Selection of optimization criterion in the multinomenclature inventory management problem]. Vestnik Har'kovskogo nacional'nogo avtomobil'no-dorozhnogo universiteta i Severo-Vostochnogo nauchnogo centra Transportnoj akademii Ukrainy: sb. nauch. tr. [Bulletin of the Kharkov National Automobile and Highway University and the North-Eastern Scientific Center of the Transport Academy of Ukraine: Sat. sci. tr.]. Kharkov, KhNADU Publ., 2009.Vol. 45.P. 31–34.

Zubarev V. V., Kovtunenko A. P. Raskin. L. G. Matematicheskie metodyi otsenki i prognozirovaniya tehnicheskih pokazateley ekspluatatsionnyih svoystv radiotehnicheskih sistem [Mathematical methods estimation and forecasting technical indicators of operational properties of radio engineering systems]. Кiev, NAU Publ., 2005. 184 p.

Sobol I. M., Vyibor optimalnyih parametrov v zadachah s mnogimi kriteriyami [Choice of optimal parameters in tasks with many criteria]. Мoscow, Drofa Publ., 2006. 175 p.

Pawlak Z. Rough sets. International Journal of Information and Computer Sciences. 1982, vol. 11, no. 5, p. 341–356.

Pawlak Z. Rough Sets approach to knowledge–based decision support. European Journal of Operational Research. 1997, vol. 99. no. 1, p. 48–57.

Slowinski R., Vanderpooten D. A generalized definition of rough approximations based on similarity. IEEE Transactions on Knowledge and data Engineering. 2000, vol. 12, no. 2, p. 331–336.

Alefeld G., Herzberger, J. Introduction to Interval Computations. New York, Academic Press Publ., 1983. 352 р.

Hansen E. Global Optimization Using Interval Analysis. New York, Marcel Dekker Publ., 1992. 230 р.

Zadeh L. A. Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Systems. 1978, vol. 1, p. 3–28.

Kaufman A., Gupta M. Introduction to Fuzzy Arithmetic: Theory and Applications. New York, VN Reinhold Publ., 1985. 334 p.

Dubois D., Prade H. Possibility Theory: an Approach to Computerized Processing of Uncertainty. New York, Plenum Press Publ., 1988. 263 p. (Rus. ed.: Dubois D., Prade H. Teoryia vozmozhnostei. Prylozhenye k predstavlenyiuznanyi v ynformatyke. Moscow, Radyo i sviaz Publ., 1990. 286 p.).

Liu B., Zhao B. Stochastic Programming and Fuzzy Programming. Beijing, Tsinghua University Press Publ., 1998. 312 p.

Raskin L., Sira O. Method of solving fuzzy problems of mathematical programming. Eastern–european journal of enterprise technologies. 2016, vol 5, no. 4 (83), p. 23–28.

Raskin L., Sira O. Fuzzy models of rough mathematics. Eastern– European Journal of Enterprise Technologies. 2016, vol. 6, issue 4, p. 53–60.


Пристатейна бібліографія ГОСТ