Розробка методу лінеаризації квадратичної задачі про призначення

Автор(и)

DOI:

https://doi.org/10.15587/1729-4061.2021.225311

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

квадратична задача про призначення, постановка Купманса-Бекмана, лінійна двійкова форма

Анотація

У статті представлено новий дієвий метод лінеаризації квадратичної задачі про призначення. У літературі існує величезна кількість методів, які використовуються для лінеаризації квадратичної задачі про призначення. У всіх цих лінійних формулюваннях значно збільшується як кількість змінних, так і кількість лінійних обмежень. Квадратична задача про призначення (КЗП) є добре відомою задачею, в якій множина об'єктів призначається множині розташувань таким чином, що витрати є функцією відстані і потоку між об'єктами. У цій задачі витрати пов'язані з розміщенням об'єкта в певному місці. Мета полягає в тому, щоб звести до мінімуму призначення кожного об'єкта певному місцю. Існує три основні категорії методів вирішення квадратичної задачі про призначення. До цих категорій відносяться евристичні методи, обмежуючі методи і точні алгоритми. Евристичні швидко дають майже оптимальні рішення квадратичної задачі про призначення. П'ять основних типів евристичних методів включають методи побудови, методи обмеженого перерахування, методи поліпшення, методи імітації відпалу і генетичні алгоритми. Для кожної сформульованої КЗП може бути розрахована нижня межа. Існують межі Гілмора-Лоулера, межі власних значень і межі, засновані на переформулюваннях в якості методів обмеження. Існує чотири основні класи методів для точного вирішення квадратичної задачі про призначення, а саме динамічне програмування, методи січних площин, методи гілок і меж і гібриди останніх двох. КЗП знаходить застосування в проводці задньої панелі комп'ютера, плануванні лікарень, дизайні мішені для гри в дартс, дизайні клавіатури типу друкарської машинки, виробничих процесах, плануванні і т. д. Перевагою методу, запропонованого в даній статті, є те, що в результаті процесу лінеаризації кількість лінійних обмежень збільшується тільки на одиницю

Біографія автора

Elias Munapo, North West University

PhD, Professor of Operations Research

Department of Statistics and Operations Research

School of Economics and Decision Sciences

Посилання

  1. Munapo, E. (2012). Reducing the number of new constraints and variables in a linearised quadratic assignment problem. AFRICAN JOURNAL OF AGRICULTURAL RESEEARCH, 7 (21). doi: https://doi.org/10.5897/ajarx11.073
  2. Koopmans, T. C., Beckmann, M. (1957). Assignment Problems and the Location of Economic Activities. Econometrica, 25 (1), 53. doi: https://doi.org/10.2307/1907742
  3. Drezner, Z. (2008). Extensive experiments with hybrid genetic algorithms for the solution of the quadratic assignment problem. Computers & Operations Research, 35 (3), 717–736. doi: https://doi.org/10.1016/j.cor.2006.05.004
  4. Yang, X., Lu, Q., Li, C., Liao, X. (2008). Biological computation of the solution to the quadratic assignment problem. Applied Mathematics and Computation, 200 (1), 369–377. doi: https://doi.org/10.1016/j.amc.2007.11.016
  5. Adams, W., Johnson, T. (1994). Improved linear programming-based lower bounds for the quadratic assignment problem. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 43–75. doi: https://doi.org/10.1090/dimacs/016/02
  6. Ramakrishnan, K. G., Resende, M. G. C., Ramachandran, B., Pekny, J. F. (2002). Tight QAP bounds via linear programming. Series on Applied Mathematics, 297–303. doi: https://doi.org/10.1142/9789812778215_0019
  7. Cela, E. (1998). The quadratic assignment problem: theory and algorithms. In Combinatorial Optimization. Springer, 287. doi: https://doi.org/10.1007/978-1-4757-2787-6
  8. Nagarajan, V., Sviridenko, M. (2009). On the Maximum Quadratic Assignment Problem. Mathematics of Operations Research, 34 (4), 859–868. doi: https://doi.org/10.1287/moor.1090.0418
  9. Abdel-Basset, M., Manogaran, G., Rashad, H., Zaied, A. N. H. (2018). A comprehensive review of quadratic assignment problem: variants, hybrids and applications. Journal of Ambient Intelligence and Humanized Computing. doi: https://doi.org/10.1007/s12652-018-0917-x
  10. Billionnet, A., Elloumi, S. (2001). Best reduction of the quadratic semi-assignment problem. Discrete Applied Mathematics, 109 (3), 197–213. doi: https://doi.org/10.1016/s0166-218x(00)00257-2
  11. Casares, P. A. M., Martin-Delgado, M. A. (2020). A quantum interior-point predictor–corrector algorithm for linear programming. Journal of Physics A: Mathematical and Theoretical, 53 (44), 445305. doi: https://doi.org/10.1088/1751-8121/abb439
  12. Al-Rabeeah, M., Munapo, E., Al-Hasani, A., Kumar, S., Eberhard, A. (2019). Computational Enhancement in the Application of the Branch and Bound Method for Linear Integer Programs and Related Models. International Journal of Mathematical, Engineering and Management Sciences, 4 (5), 1140–1153. doi: https://doi.org/10.33889/ijmems.2019.4.5-090
  13. Djeumou Fomeni, F., Kaparis, K., Letchford, A. N. (2020). A cut-and-branch algorithm for the Quadratic Knapsack Problem. Discrete Optimization, 100579. doi: https://doi.org/10.1016/j.disopt.2020.100579
  14. Taha, H. A. (2017). Operations Research: An Introduction. Pearson Education.
  15. Arbib, C., Pınar, M. Ç., Rossi, F., Tessitore, A. (2020). Codon optimization by 0-1 linear programming. Computers & Operations Research, 119, 104932. doi: https://doi.org/10.1016/j.cor.2020.104932
  16. Munapo, E. (2016). Second Proof That P=NP. EngOpt 2016. Program of the Conference.
  17. Munapo, E. (2021). The Traveling Salesman Problem. Research Advancements in Smart Technology, Optimization, and Renewable Energy, 88–109. doi: https://doi.org/10.4018/978-1-7998-3970-5.ch006
  18. Han, B., Li, Y., Geng, S. (2017). 0–1 Linear programming methods for optimal normal and pseudo parameter reductions of soft sets. Applied Soft Computing, 54, 467–484. doi: https://doi.org/10.1016/j.asoc.2016.08.052
  19. Kodama, A., Nishi, T. (2017). Petri net representation and reachability analysis of 0–1 integer linear programming problems. Information Sciences, 400-401, 157–172. doi: https://doi.org/10.1016/j.ins.2017.03.014
  20. Demiröz, B. E., Altınel, İ. K., Akarun, L. (2019). Rectangle blanket problem: Binary integer linear programming formulation and solution algorithms. European Journal of Operational Research, 277 (1), 62–83. doi: https://doi.org/10.1016/j.ejor.2019.02.004
  21. Bakhshi–Jafarabadi, R., Sadeh, J., Soheili, A. (2019). Global optimum economic designing of grid-connected photovoltaic systems with multiple inverters using binary linear programming. Solar Energy, 183, 842–850. doi: https://doi.org/10.1016/j.solener.2019.03.019

##submission.downloads##

Опубліковано

2021-04-30

Як цитувати

Munapo, E. (2021). Розробка методу лінеаризації квадратичної задачі про призначення. Eastern-European Journal of Enterprise Technologies, 2(4 (110), 54–61. https://doi.org/10.15587/1729-4061.2021.225311

Номер

Том 2 № 4 (110) (2021): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2021 Elias Munapo

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.