Розробка евристики для вирішення загальної транспортної задачі
DOI:
https://doi.org/10.15587/1729-4061.2021.243735Ключові слова:
транспортна задача, правило гойдалки, лінійне програмування, транспортний симплекс-методАнотація
Транспортна задача добре відома і широко застосовується. Для цієї добре вивченої задачі існують дуже ефективні методи вирішення. Ці методи включають формулювання транспортної задачі у вигляді лінійної програми з подальшим використанням ефективних методів, таких як симплекс-метод або алгоритми внутрішніх точок.
Ще одним ефективним методом вирішення як задачі про призначення, так і загальної транспортної задачі є Угорський метод. Задача про призначення є окремим випадком транспортної задачі, в якій всі точки пропозиції і попиту рівні 1. Кожну транспортну задачу можна перетворити на задачу про призначення, оскільки рядки і стовпці можна розділити таким чином, щоб кожна точка пропозиції і кожна точка попиту дорівнювали 1.
Транспортний симплекс-метод – це ще один спосіб, що також використовується для вирішення загальної транспортної задачі. Цей метод також називається модифікованим методом розповсюдження (МОДИ). Для використання цього підходу потрібне вихідне рішення, і чим ближче вихідне рішення до оптимального, тим менше ітерацій потрібно для досягнення оптимальності.
Четвертий метод вирішення транспортних задач – мережевий симплекс-метод, який на даний момент є найшвидшим. На жаль, всі ці методи вирішення транспортних задач носять послідовний характер і дуже важко піддаються розпаралелюванню, що ускладнює ефективне використання наявної технології масового паралелізму. Необхідний ефективний метод вирішення транспортної задачі, який легко піддається розпаралелюванню. Для вирішення загальної транспортної задачі в роботі представлений метод гойдалки. Це розширення методу гойдалки для вирішення задачі про призначення. Рухи гойдалки можуть виконуватися незалежно, що робить запропонований метод більш перспективним, ніж доступні методи вирішення транспортних задач
Посилання
- Conte, D., Grossi, G., Lanzarotti, R., Lin, J., Petrini, A. (2021). Analysis of a parallel MCMC algorithm for graph coloring with nearly uniform balancing. Pattern Recognition Letters, 149, 30–36. doi: https://doi.org/10.1016/j.patrec.2021.05.014
- Kumar, S., Munapo, E., Nyamugure, P. (2021). An Insight into the Characteristic Equation for an Integer Program. International Journal of Mathematical, Engineering and Management Sciences, 6 (2), 611–620. doi: https://doi.org/10.33889/ijmems.2021.6.2.037
- Kline, A., Ahner, D., Hill, R. (2019). The Weapon-Target Assignment Problem. Computers & Operations Research, 105, 226–236. doi: https://doi.org/10.1016/j.cor.2018.10.015
- Liu, Y., Tu, Y., Zhang, Z. (2021). The row pivoting method for linear programming. Omega, 100, 102354. doi: https://doi.org/10.1016/j.omega.2020.102354
- Castro, J., Nasini, S. (2021). A specialized interior-point algorithm for huge minimum convex cost flows in bipartite networks. European Journal of Operational Research, 290 (3), 857–869. doi: https://doi.org/10.1016/j.ejor.2020.10.027
- Rabbani, Q., Khan, A., Quddoos, A. (2019). Modified Hungarian method for unbalanced assignment problem with multiple jobs. Applied Mathematics and Computation, 361, 493–498. doi: https://doi.org/10.1016/j.amc.2019.05.041
- Taha, H. A. (2017). Operations Research: An Introduction. Harlow, United Kingdom: Pearson.
- Singh, G., Singh, A. (2021). Extension of particle swarm optimization algorithm for solving transportation problem in fuzzy environment. Applied Soft Computing, 110, 107619. doi: https://doi.org/10.1016/j.asoc.2021.107619
- Holzhauser, M., Krumke, S. O., Thielen, C. (2017). A network simplex method for the budget-constrained minimum cost flow problem. European Journal of Operational Research, 259 (3), 864–872. doi: https://doi.org/10.1016/j.ejor.2016.11.024
- Micheli, G., Weger, V. (2019). On Rectangular Unimodular Matrices over the Algebraic Integers. SIAM Journal on Discrete Mathematics, 33 (1), 425–437. doi: https://doi.org/10.1137/18m1177093
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2021 Elias Munapo
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.
