{"id":344279,"date":"2023-01-21T09:01:36","date_gmt":"2023-01-21T09:01:36","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=344279"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=344279","title":{"rendered":"<span>\u0417\u0430\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 (TSP) \u0442\u043e\u0447\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u2014 \u043c\u0435\u0442\u043e\u0434 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f (Integer programming)<\/span>"},"content":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/3b9\/a7e\/2f5\/3b9a7e2f5a53d783f2fe3028be2ac514.png\" width=\"800\" height=\"440\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3b9\/a7e\/2f5\/3b9a7e2f5a53d783f2fe3028be2ac514.png\"\/><figcaption><\/figcaption><\/figure>\n<blockquote>\n<p><em>\u0412\u0441\u0435 \u043f\u0443\u0442\u0438 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b: \u043e\u043d\u0438 \u0432\u0435\u0434\u0443\u0442 \u0432 \u043d\u0438\u043a\u0443\u0434\u0430. \u041d\u043e \u0443 \u043e\u0434\u043d\u0438\u0445 \u0435\u0441\u0442\u044c \u0441\u0435\u0440\u0434\u0446\u0435, \u0430 \u0443 \u0434\u0440\u0443\u0433\u0438\u0445 \u2014 \u043d\u0435\u0442. \u041e\u0434\u0438\u043d \u043f\u0443\u0442\u044c \u0434\u0430\u0435\u0442 \u0442\u0435\u0431\u0435 \u0441\u0438\u043b\u044b, \u0434\u0440\u0443\u0433\u043e\u0439 \u2014 \u0443\u043d\u0438\u0447\u0442\u043e\u0436\u0430\u0435\u0442 \u0442\u0435\u0431\u044f.<\/em><\/p>\n<p><em>&#8212; \u041a\u0430\u0440\u043b\u043e\u0441 \u041a\u0430\u0441\u0442\u0430\u043d\u0435\u0434\u0430<\/em><\/p>\n<\/blockquote>\n<p>\u0417\u0434\u0440\u0430\u0432\u0441\u0442\u0432\u0443\u0439\u0442\u0435 \u0443\u0432\u0430\u0436\u0430\u0435\u043c\u044b\u0435 \u0434\u0430\u043c\u044b \u0438 \u0433\u043e\u0441\u043f\u043e\u0434\u0430, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043d\u0435 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0435 \u043b\u0438\u0447\u043d\u043e\u0441\u0442\u0438. \u0425\u043e\u0440\u043e\u0448\u0435\u0439 \u044d\u043f\u043e\u0445\u0438.<\/p>\n<p>\u041c\u044b \u0441 \u0432\u0430\u043c\u0438 \u0443\u0436\u0435 \u043f\u0440\u043e\u0431\u043e\u0432\u0430\u043b\u0438 \u0440\u0435\u0448\u0430\u0442\u044c \u0442\u043e\u0447\u043d\u043e \u0437\u0430\u0434\u0430\u0447\u0443 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0451\u0440\u0430 \u043c\u0435\u0442\u043e\u0434\u043e\u043c <a href=\"https:\/\/habr.com\/ru\/post\/701458\/\" rel=\"noopener noreferrer nofollow\">\u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f<\/a> \u0438 \u043c\u0435\u0442\u043e\u0434\u043e\u043c <a href=\"https:\/\/habr.com\/ru\/post\/708072\/\" rel=\"noopener noreferrer nofollow\">\u0432\u0435\u0442\u0432\u0435\u0439 \u0438 \u0433\u0440\u0430\u043d\u0438\u0446<\/a>, \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043d\u0435 \u043f\u043b\u043e\u0445, \u043d\u043e \u0441\u043b\u0430\u0431\u043e\u0432\u0430\u0442.<\/p>\n<p>\u0412 \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u043f\u043e\u0441\u0442\u0430\u0440\u0430\u044e\u0441\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e <strong>\u0442\u043e\u0447\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435<\/strong> \u0431\u043b\u0438\u0436\u0435, \u0447\u0435\u043c \u043f\u0440\u0438\u043d\u044f\u0442\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c.<\/p>\n<p>\u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0435\u0442\u043e\u0434 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0447\u0430\u0441\u0442\u043d\u044b\u043c \u0441\u043b\u0443\u0447\u0430\u0435\u043c \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432 \u0441\u0432\u043e\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0434\u043a\u043b\u0430\u0441\u0441\u043e\u043c \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f.<\/p>\n<p>\u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u00a0&#8212; \u044d\u0442\u043e \u043e\u0431\u043b\u0430\u0441\u0442\u044c \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438, \u0440\u0430\u0437\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u044e\u0449\u0430\u044f \u0442\u0435\u043e\u0440\u0438\u044e, \u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043c\u043d\u043e\u0433\u043e\u043c\u0435\u0440\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0441 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c\u0438.<\/p>\n<p>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c: <\/p>\n<ul>\n<li>\n<p>\u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u043c\u0438 (\u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0438\u043b\u0438 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0442\u043e\u0440\u043d\u0430\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f (\u043c\u0435\u0442\u043e\u0434 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u0432\u0435\u0442\u0432\u0435\u0439 \u0438 \u0433\u0440\u0430\u043d\u0438\u0446 \u043c\u043e\u0436\u043d\u043e \u043e\u0442\u043d\u0435\u0441\u0442\u0438 \u0441\u044e\u0434\u0430))<\/p>\n<\/li>\n<li>\n<p>\u043b\u0438\u043d\u0435\u0439\u043d\u044b\u043c\u0438 (\u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0438\u043b\u0438 \u043d\u0435\u043f\u0440\u0435\u0440\u044b\u0432\u043d\u044b\u043c\u0438)<\/p>\n<\/li>\n<li>\n<p>\u043d\u0435\u043b\u0438\u043d\u0435\u0439\u043d\u044b\u043c\u0438<\/p>\n<\/li>\n<\/ul>\n<p>\u041d\u043e \u0438 \u0441\u0430\u043c\u0430 \u0446\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c:<\/p>\n<ul>\n<li>\n<p>\u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 (Linear programming, LP)<\/p>\n<\/li>\n<li>\n<p>\u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u043e\u0439 (Quadratic programming,\u00a0QP)<\/p>\n<\/li>\n<li>\n<p>\u0434\u0440\u0443\u0433\u043e\u0439 \u043d\u0435\u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 (Conic optimization, \u0434\u0440.)<\/p>\n<\/li>\n<\/ul>\n<p>\u0412 \u0434\u0430\u043d\u043d\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u0435 \u043d\u0430\u0441 \u0431\u0443\u0434\u0435\u0442 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043e\u0432\u0430\u0442\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435, \u0433\u0434\u0435 \u0446\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u044b \u043b\u0438\u043d\u0435\u0439\u043d\u043e.<\/p>\n<p>\u0412 \u0441\u0432\u043e\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043e\u0442 \u0442\u043e\u0433\u043e \u043a\u0430\u043a\u043e\u0439 \u0442\u0438\u043f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f, \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c:<\/p>\n<ul>\n<li>\n<p>\u0411\u0443\u043b\u0435\u0432\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 (Binary integer programming, PIB)<\/p>\n<\/li>\n<li>\n<p>\u0426\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0435 (\u0432\u0441\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435, Integer programming, IP)<\/p>\n<\/li>\n<li>\n<p>\u0421\u043c\u0435\u0448\u0430\u043d\u043d\u043e\u0435 (\u0447\u0430\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u0430\u044f, Mixed-integer programming, MIP)<\/p>\n<\/li>\n<li>\n<p>\u041b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 (\u0432\u0441\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u043a\u0430\u043a \u043d\u0435 \u0446\u0435\u043b\u044b\u0435, \u043d\u0435\u043f\u0440\u0435\u0440\u044b\u0432\u043d\u044b\u0435 \u2013 continuous, LP)<\/p>\n<\/li>\n<\/ul>\n<p>\u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043a\u043b\u0430\u0441\u0441\u0430 \u0437\u0430\u0434\u0430\u0447 \u0435\u0441\u0442\u044c \u0441\u0432\u043e\u0438 \u043c\u0435\u0442\u043e\u0434\u044b, \u0447\u0430\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u0441\u0435\u043a\u0430\u0435\u0442\u0441\u044f, \u0447\u0430\u0441\u0442\u044c \u0438\u043c\u0435\u0435\u0442 \u0441\u0432\u043e\u0438 \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f. \u042f \u043d\u0435 \u0431\u0443\u0434\u0443 \u0437\u0430\u043e\u0441\u0442\u0440\u044f\u0442\u044c \u0432\u0430\u0448\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043d\u0430 \u044d\u0442\u043e\u043c. \u041c\u0435\u043d\u044f \u0432 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u0435\u0442 \u043f\u0440\u0438\u043a\u043b\u0430\u0434\u043d\u0430\u044f \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c\u043e\u0441\u0442\u044c \u0432 \u0440\u0430\u0431\u043e\u0442\u0435. <\/p>\n<p>\u041f\u043e\u044d\u0442\u043e\u043c\u0443, \u0435\u0441\u043b\u0438 \u0432\u0441\u0435 \u0441\u0438\u043b\u044c\u043d\u043e \u0443\u043f\u0440\u043e\u0441\u0442\u0438\u0442\u044c, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0432\u044b\u0432\u043e\u0434: \u0447\u0435\u043c \u0431\u043e\u043b\u0435\u0435 \u043d\u0435\u043f\u0440\u0435\u0440\u044b\u0432\u043d\u044b \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435, \u0442\u0435\u043c \u043b\u0435\u0433\u0447\u0435 \u043d\u0430\u0439\u0442\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 (Linear programming \u043b\u0435\u0433\u0447\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0447\u0435\u043c Mixed-integer \u0438 Integer programming)<\/p>\n<p>\u041d\u043e \u0442\u0430\u043a \u043a\u0430\u043a \u0432 \u043d\u0430\u0448\u0435\u0439 \u0436\u0438\u0437\u043d\u0438 \u043c\u043d\u043e\u0433\u0438\u0435 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u044b \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0442\u0440\u0443\u0434\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043f\u043e\u043a\u0443\u043f\u043a\u0443 1,25 \u0430\u0432\u0442\u043e\u043c\u043e\u0431\u0438\u043b\u044f, \u0438\u043b\u0438 \u0440\u0430\u0437\u0431\u0438\u0442\u044c 0,5 \u044f\u0439\u0446\u0430), \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043c\u0435\u0442\u043e\u0434 \u0440\u0435\u043b\u0430\u043a\u0441\u0430\u0446\u0438\u0438 (\u0430\u043f\u043f\u0440\u043e\u043a\u0441\u0438\u043c\u0430\u0446\u0438\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u0441\u043e\u0441\u0435\u0434\u043d\u0435\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u043e\u0439, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043b\u0435\u0433\u0447\u0435 \u0440\u0435\u0448\u0438\u0442\u044c).<\/p>\n<p>\u0422\u043e \u0435\u0441\u0442\u044c, \u0437\u0430\u0434\u0430\u0447\u0430 \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u043d\u0435 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u0430\u044f (\u0438\u043b\u0438 \u043d\u0435 \u0431\u0438\u043d\u0430\u0440\u043d\u0430\u044f), \u0430 \u0437\u0430\u0442\u0435\u043c \u043a \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u044b\u043c \u0434\u0430\u043d\u043d\u044b\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044e\u0442\u0441\u044f \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0442 \u0437\u0430\u0434\u0430\u0447\u0443 \u043a \u0436\u0435\u043b\u0430\u0435\u043c\u043e\u043c\u0443 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0443.<\/p>\n<hr\/>\n<p>\u041f\u0440\u0435\u0436\u0434\u0435 \u0447\u0435\u043c \u043c\u044b \u043f\u0435\u0440\u0435\u0439\u0434\u0451\u043c \u043d\u0435\u043f\u043e\u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443, \u0441\u043a\u0430\u0436\u0435\u043c \u043f\u0430\u0440\u0443 \u0441\u043b\u043e\u0432 \u0437\u0430 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u0439.<\/p>\n<p>\u0420\u0435\u0448\u0430\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u044f \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 Python, \u043a\u0430\u043a \u043e\u0447\u0435\u043d\u044c \u0443\u0434\u043e\u0431\u043d\u043e\u043c \u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435 \u043f\u0440\u043e\u0442\u043e\u0442\u0438\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u043f\u0440\u043e\u0435\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0441 \u0431\u043e\u043b\u044c\u0448\u0438\u043c \u043d\u0430\u0431\u043e\u0440\u043e\u043c \u0432\u043d\u0435\u0448\u043d\u0438\u0445 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a \u0440\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u0438\u044f.<\/p>\n<p>\u0414\u043b\u044f \u043d\u0430\u0448\u0438\u0445 \u0446\u0435\u043b\u0435\u0439 \u043a\u0440\u043e\u043c\u0435 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 \u043c\u043e\u0434\u0443\u043b\u0435\u0439 \u043d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c (solver) \u0437\u0430\u0434\u0430\u0447 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e (IP) \u0438\u043b\u0438 \u0441\u043c\u0435\u0448\u0430\u043d\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f (MIP). \u041f\u043e\u0434\u043e\u0439\u0434\u0451\u0442 \u043b\u044e\u0431\u043e\u0439 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u044b\u0439 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c.<\/p>\n<p>\u0412 \u0441\u0432\u043e\u0438\u0445 \u0438\u0437\u044b\u0441\u043a\u0430\u043d\u0438\u044f\u0445 \u044f \u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u043b \u0442\u0440\u0438 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0445 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0438 IP\/MIP: PuLP, CVXPY \u0438 SciPy.<\/p>\n<ol>\n<li>\n<p>PuLP &#8212; \u0434\u0430\u0436\u0435 \u0438\u0437 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u044f \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u044d\u0442\u043e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u0435\u0434\u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0430 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u0421\u0440\u0435\u0434\u0438 \u0438\u043d\u044b\u0445 \u0430\u043b\u044c\u0442\u0435\u0440\u043d\u0430\u0442\u0438\u0432 \u043e\u043d\u0430 \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u0438\u0437\u043c\u043e\u043c, \u043f\u0440\u043e\u0441\u0442\u0430 \u0434\u043b\u044f \u043e\u0441\u0432\u043e\u0435\u043d\u0438\u044f \u043d\u043e\u0432\u0438\u0447\u043a\u0430\u043c\u0438, \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u043e\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e \u043f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0442\u044c \u0432\u043d\u0435\u0448\u043d\u0438\u0435 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0438.<\/p>\n<\/li>\n<li>\n<p>CVXPY &#8212; \u044d\u0442\u043e \u0432\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u044b\u0439 \u0432 Python \u044f\u0437\u044b\u043a \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u043c \u043a\u043e\u0434\u043e\u043c \u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447 \u0432\u044b\u043f\u0443\u043a\u043b\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438. \u0412 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 PuLP, \u043c\u043e\u0436\u0435\u0442 \u0440\u0435\u0448\u0430\u0442\u044c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438. \u0421\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0431\u043e\u043b\u0435\u0435 \u0431\u043e\u0433\u0430\u0442\u044b\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b \u0438 \u043f\u0440\u0438\u043b\u0438\u0447\u043d\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u043f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0435\u043c\u044b\u0445 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0435\u0439. \u041e\u0434\u043d\u0430\u043a\u043e, \u043a\u0430\u043a \u043c\u043d\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c CVXPY \u0441\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441 \u043e\u0434\u043d\u043e\u0442\u0438\u043f\u043d\u044b\u043c\u0438 \u0437\u0430\u0434\u0430\u0447\u0430\u043c\u0438 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c PuLP \u043d\u0430 \u0442\u0435\u0445 \u0436\u0435 \u0432\u043d\u0435\u0448\u043d\u0438\u0445 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044f\u0445 (\u043f\u043e \u043a\u0440\u0430\u0439\u043d\u0435\u0439 \u043c\u0435\u0440\u0435, MIP) \u0438 \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u0435\u043d \u0434\u043b\u044f \u0438\u0437\u0443\u0447\u0435\u043d\u0438\u044f. \u0415\u0441\u043b\u0438 \u0432\u0430\u043c \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0432\u044b\u043f\u0443\u043a\u043b\u0430\u044f \u0446\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u0442\u043e \u044f \u0431\u044b \u0435\u0433\u043e \u0434\u043b\u044f \u0434\u0430\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043d\u0435 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u043e\u0432\u0430\u043b.<\/p>\n<\/li>\n<li>\n<p>SciPy &#8212; \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430 \u0434\u043b\u044f \u044f\u0437\u044b\u043a\u0430 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f Python \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u043c \u043a\u043e\u0434\u043e\u043c, \u043f\u0440\u0435\u0434\u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u043d\u0430\u044f \u0434\u043b\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u043d\u0430\u0443\u0447\u043d\u044b\u0445 \u0438 \u0438\u043d\u0436\u0435\u043d\u0435\u0440\u043d\u044b\u0445 \u0440\u0430\u0441\u0447\u0451\u0442\u043e\u0432. \u041d\u0430\u0441 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u0435\u0442 \u0435\u0451 \u043c\u043e\u0434\u0443\u043b\u044c optimize \u2013 \u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0430 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438. \u0421\u043a\u0430\u0436\u0443 \u0441\u0440\u0430\u0437\u0443, \u044d\u0442\u043e \u0432\u0435\u0441\u044c\u043c\u0430 \u0441\u043b\u043e\u0436\u043d\u044b\u0439 \u043f\u043e\u0434\u0445\u043e\u0434, \u043d\u043e \u0441\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0445 \u043e\u043f\u0435\u043d\u0441\u043e\u0440\u0441\u043d\u044b\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u0441\u0430\u043c\u044b\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439, \u0447\u0442\u043e \u044f \u043d\u0430\u0448\u0451\u043b.<\/p>\n<\/li>\n<\/ol>\n<p>\u0412 \u043f\u0440\u0438\u043c\u0435\u0440\u0430\u0445 \u043a \u0441\u0442\u0430\u0442\u044c\u0435 \u0431\u0443\u0434\u0443 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u0440\u044b \u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c PuLP, \u0447\u0442\u043e\u0431\u044b \u0432\u0430\u043c \u043b\u0435\u0433\u0447\u0435 \u0431\u044b\u043b\u043e \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f. <\/p>\n<p>\u041d\u0438\u0436\u0435 \u0431\u0443\u0434\u0443\u0442 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u044b \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0445 \u0438 \u0441\u043c\u0435\u0448\u0430\u043d\u043d\u044b\u0445 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439, \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c\u044b\u0445 \u0434\u043b\u044f \u043d\u0430\u0448\u0438\u0445 \u0446\u0435\u043b\u0435\u0439.<\/p>\n<p>\u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043c \u0441\u0430\u043c <a href=\"https:\/\/github.com\/coin-or\/pulp\" rel=\"noopener noreferrer nofollow\">PuLP <\/a>\u043e\u043d \u0441\u043e\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0441\u043e \u0432\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u044b\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0435\u043c CBC \u043e\u0442 COIN-OR Foundation, \u0438\u043c\u0435\u0435\u0442 \u043d\u0435\u043f\u043b\u043e\u0445\u0443\u044e \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c.<\/p>\n<pre><code class=\"powershell\">pip install pulp<\/code><\/pre>\n<p><a href=\"https:\/\/www.scipopt.org\/)\" rel=\"noopener noreferrer nofollow\">SCIP<\/a> &#8212; \u0442\u0430\u043a \u0436\u0435 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u044b\u0439 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c, \u043d\u043e \u0434\u043b\u044f \u0434\u0430\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e\u043d \u043c\u0435\u043d\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437\u043e\u0447\u0430\u0440\u043e\u0432\u0430\u043b. \u042d\u0442\u043e \u043d\u0435 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u0447\u0442\u043e \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u043f\u043b\u043e\u0445, \u043a\u0430\u043a \u043f\u043e \u043c\u043d\u0435 \u043e\u043d \u0443\u0441\u0442\u0443\u043f\u0430\u0435\u0442 CBC \u0432 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438.<\/p>\n<p><a href=\"https:\/\/www.ibm.com\/products\/ilog-cplex-optimization-studio\" rel=\"noopener noreferrer nofollow\">CPLEX <\/a>\u2013 \u043a\u043b\u0430\u0441\u0441\u043d\u044b\u0439 \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0439 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u043e\u0442 IBM. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043a\u043e\u043c\u044c\u044e\u043d\u0438\u0442\u0438 \u0432\u0435\u0440\u0441\u0438\u044f \u043d\u0435 \u0434\u043b\u044f \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043c\u043e\u0436\u0435\u0442 \u0440\u0435\u0448\u0430\u0442\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0435 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0434\u043e 1000 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0438 1000 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 (\u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u044b n&lt;=45)<\/p>\n<pre><code class=\"powershell\">pip install cplex docplex<\/code><\/pre>\n<p><a href=\"https:\/\/www.gurobi.com\/solutions\/gurobi-optimizer\/\" rel=\"noopener noreferrer nofollow\">GUROBI <\/a>&#8212; \u0435\u0449\u0451 \u043e\u0434\u0438\u043d \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0439 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043a\u043e\u043c\u044c\u044e\u043d\u0438\u0442\u0438 \u0432\u0435\u0440\u0441\u0438\u044f \u043d\u0435 \u0434\u043b\u044f \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043c\u043e\u0436\u0435\u0442 \u0440\u0435\u0448\u0430\u0442\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0435 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0434\u043e 2000 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 (\u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u044b n&lt;=63)<\/p>\n<pre><code class=\"powershell\">pip install gurobipy<\/code><\/pre>\n<p><a href=\"https:\/\/www.fico.com\/en\/products\/fico-xpress-optimization\" rel=\"noopener noreferrer nofollow\">Xpress <\/a>&#8212; \u0442\u0430\u043a \u0436\u0435 \u0445\u043e\u0440\u043e\u0448\u0438\u0439 \u043f\u0440\u043e\u043f\u0440\u0438\u0435\u0442\u0430\u0440\u043d\u044b\u0439 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c.<\/p>\n<p>\u041a\u043e\u043c\u044c\u044e\u043d\u0438\u0442\u0438 \u0432\u0435\u0440\u0441\u0438\u044f \u043d\u0435 \u0434\u043b\u044f \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f, \u043c\u043e\u0436\u0435\u0442 \u0440\u0435\u0448\u0430\u0442\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0435 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0434\u043e 5000 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 + \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 (\u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u044b ~n&lt;=98)<\/p>\n<pre><code class=\"powershell\">pip install xpress<\/code><\/pre>\n<p>\u0417\u0434\u0435\u0441\u044c \u043d\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0442\u0430\u043a \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u044b \u0441\u0441\u044b\u043b\u043a\u0438 \u043d\u0430 \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0435 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0438, \u0442\u0430\u043a \u043a\u0430\u043a \u043e\u043d\u0438 \u0441\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0441 \u0442\u043e\u0439 \u0436\u0435 \u0437\u0430\u0434\u0430\u0447\u0435\u0439 \u0432 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043d\u0430 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u043c \u043d\u0430\u0431\u043e\u0440\u0435 \u0434\u0430\u043d\u043d\u044b\u0445. \u0423 CPLEX \u0438 GUROBI \u0435\u0441\u0442\u044c \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0441\u043a\u0430\u0447\u0430\u0442\u044c \u0431\u0435\u0441\u043f\u043b\u0430\u0442\u043d\u0443\u044e \u0430\u043a\u0430\u0434\u0435\u043c\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043b\u0438\u0446\u0435\u043d\u0437\u0438\u044e. \u0422\u0430\u043a \u043a\u0430\u043a \u044f \u043d\u0435 \u044f\u0432\u043b\u044f\u044e\u0441\u044c \u0443\u0447\u0430\u0441\u0442\u043d\u0438\u043a\u043e\u043c \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0441\u043a\u043e\u0439 \u0434\u0435\u044f\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u043c\u043d\u0435 \u044d\u0442\u043e\u0442 \u043f\u0443\u0442\u044c \u0437\u0430\u043a\u0430\u0437\u0430\u043d, \u043d\u043e \u0441\u043e\u0433\u043b\u0430\u0441\u0438\u0442\u0435\u0441\u044c, \u043f\u043e\u0434\u0445\u043e\u0434 \u043a\u043e\u043c\u043f\u0430\u043d\u0438\u0439 \u043f\u043e\u0434\u043a\u0443\u043f\u0430\u0435\u0442, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u0448\u044c \u043d\u0430 \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0435 \u0446\u0435\u043d\u043d\u0438\u043a\u0438.<\/p>\n<hr\/>\n<p>\u041f\u0435\u0440\u0435\u0439\u0434\u0451\u043c \u043a \u0441\u0430\u043c\u043e\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443.<\/p>\n<ol>\n<li>\n<p>\u0428\u0430\u0433<\/p>\n<\/li>\n<\/ol>\n<p>\u0412\u043e\u0437\u044c\u043c\u0451\u043c \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u0443\u044e \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438 \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430 \u043d\u0430 5 \u0432\u0435\u0440\u0448\u0438\u043d:<\/p>\n<pre><code>[[ 0 14  3 13  8]  [14  0 16  2  7]  [ 3 16  0 14 10]  [13  2 14  0  6]  [ 8  7 10  6  0]]<\/code><\/pre>\n<p>\u041d\u0430\u0439\u0434\u0451\u043c \u0434\u043b\u044f \u043d\u0435\u0451 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0413\u0430\u043c\u0438\u043b\u044c\u0442\u043e\u043d\u043e\u0432 \u0446\u0438\u043a\u043b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f PuLP.<\/p>\n<pre><code class=\"python\">import pulp as pl # \u0421\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u043c\u043e\u0434\u0435\u043b\u044c \u0437\u0430\u0434\u0430\u0447\u0438 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f - \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0434\u043b\u0438\u043d\u0443 \u043f\u0443\u0442\u0438 model = pl.LpProblem(name=\"tsp\", sense=pl.LpMinimize) # \u041f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c solver = pl.PULP_CBC_CMD(msg=False) # \u0417\u0430\u0432\u043e\u0434\u0438\u043c \u043c\u0430\u0441\u0441\u0438\u0432 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 x = [pl.LpVariable(name=f'x_{i:02}_{j:02}', cat='Binary') for i in range(n) for j in range(n)] # \u0423\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c \u0446\u0435\u043b\u0435\u0432\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e model += pl.lpSum([matrix[i][j] * x[i * n + j if i &lt; j else j * n + i] for i in range(n) for j in range(n) if i &lt; j]) # \u0412\u043d\u043e\u0441\u0438\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043c\u043e\u0434\u0435\u043b\u0438 for i in range(n):     model += pl.lpSum([x[i * n + j if i &lt; j else j * n + i] for j in range(n) if i != j]) == 2<\/code><\/pre>\n<p>\u0415\u0441\u043b\u0438 \u0441\u0435\u0439\u0447\u0430\u0441 \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u043c\u043e\u0434\u0435\u043b\u044c, \u0442\u043e \u043e\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u0442\u044c \u0442\u0430\u043a: <\/p>\n<pre><code class=\"python\">tsp: MINIMIZE 14*x_00_01 + 3*x_00_02 + 13*x_00_03 + 8*x_00_04 + 16*x_01_02 + 2*x_01_03 + 7*x_01_04 + 14*x_02_03 + 10*x_02_04 + 6*x_03_04 + 0 SUBJECT TO _C1: x_00_01 + x_00_02 + x_00_03 + x_00_04 = 2 _C2: x_00_01 + x_01_02 + x_01_03 + x_01_04 = 2 _C3: x_00_02 + x_01_02 + x_02_03 + x_02_04 = 2 _C4: x_00_03 + x_01_03 + x_02_03 + x_03_04 = 2 _C5: x_00_04 + x_01_04 + x_02_04 + x_03_04 = 2 VARIABLES 0 &lt;= x_00_01 &lt;= 1 Integer 0 &lt;= x_00_02 &lt;= 1 Integer 0 &lt;= x_00_03 &lt;= 1 Integer 0 &lt;= x_00_04 &lt;= 1 Integer 0 &lt;= x_01_02 &lt;= 1 Integer 0 &lt;= x_01_03 &lt;= 1 Integer 0 &lt;= x_01_04 &lt;= 1 Integer 0 &lt;= x_02_03 &lt;= 1 Integer 0 &lt;= x_02_04 &lt;= 1 Integer 0 &lt;= x_03_04 &lt;= 1 Integer<\/code><\/pre>\n<p>x_[i]_[j] \u2013 \u044d\u0442\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u0442\u0432\u0435\u0447\u0430\u0435\u0442 \u0437\u0430 \u0442\u043e, \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0434\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u0438\u043b\u0438 \u043d\u0435\u0442 (1 \/ 0).<\/p>\n<p>14 * x_[i]_[j] \u2013 \u044d\u0442\u043e \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430 \u0438\u0437 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438.<\/p>\n<p>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0433\u043e\u0432\u043e\u0440\u044f\u0442 \u043d\u0430\u043c \u043e \u0442\u043e\u043c, \u0447\u0442\u043e \u0432 \u043a\u0430\u0436\u0434\u0443\u044e \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0434\u043e\u043b\u0436\u043d\u043e \u0432\u0435\u0441\u0442\u0438 \u0440\u043e\u0432\u043d\u043e \u0434\u0432\u0430 \u043f\u0443\u0442\u0438, \u043f\u043e \u043e\u0434\u043d\u043e\u043c\u0443 \u043c\u044b \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u043c \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0443, \u0430 \u043f\u043e-\u0434\u0440\u0443\u0433\u043e\u043c\u0443 \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u0439\u0442\u0438.<\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u0442\u0438\u0432 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c<\/p>\n<pre><code class=\"python\">status = model.solve(solver)  for v in model.variables():         print(f'{v.name} = {round(v.value())}') print(f'Minimum path = {round(model.objective.value())}')<\/code><\/pre>\n<p>\u043f\u043e\u043b\u0443\u0447\u0438\u043c:<\/p>\n<pre><code class=\"python\">x_00_01 = 0 x_00_02 = 1 x_00_03 = 0 x_00_04 = 1 x_01_02 = 0 x_01_03 = 1 x_01_04 = 1 x_02_03 = 1 x_02_04 = 0 x_03_04 = 0 Minimum path = 34<\/code><\/pre>\n<p>\u041d\u0430\u043c \u043e\u0441\u0442\u0430\u0451\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0442\u043e\u0431\u0440\u0430\u0437\u0438\u0442\u044c \u043d\u0430 \u0433\u0440\u0430\u0444\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u0440\u0451\u0431\u0440\u0430.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/2a7\/cf2\/e39\/2a7cf2e39346d53303ce6cae8623ccc1.png\" alt=\"\" title=\"\" width=\"640\" height=\"440\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2a7\/cf2\/e39\/2a7cf2e39346d53303ce6cae8623ccc1.png\"\/><figcaption><\/figcaption><\/figure>\n<p>\u041c\u044b \u043d\u0430\u0448\u043b\u0438 \u0413\u0430\u043c\u0438\u043b\u044c\u0442\u043e\u043d\u043e\u0432 \u0446\u0438\u043a\u043b \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b.<\/p>\n<ol start=\"2\">\n<li>\n<p>\u0428\u0430\u0433<\/p>\n<\/li>\n<\/ol>\n<p>\u0412\u043e\u0437\u044c\u043c\u0451\u043c \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u043a\u0440\u0443\u043f\u043d\u0435\u0435 \u0438 \u043f\u0440\u043e\u0432\u0435\u0434\u0451\u043c \u0442\u0435 \u0436\u0435 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f<\/p>\n<pre><code class=\"python\">[[ 0  5  8  5  7  1]  [ 5  0 12  4  4  5]  [ 8 12  0 13 15  7]  [ 5  4 13  0  2  6]  [ 7  4 15  2  0  8]  [ 1  5  7  6  8  0]]<\/code><\/pre>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/2ef\/0d3\/c0e\/2ef0d3c0e0bd77822c1ab6d780a42c55.png\" alt=\"\" title=\"\" width=\"640\" height=\"440\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2ef\/0d3\/c0e\/2ef0d3c0e0bd77822c1ab6d780a42c55.png\"\/><figcaption><\/figcaption><\/figure>\n<p>\u041e \u043d\u0435\u0442, \u0447\u0442\u043e-\u0442\u043e \u043f\u043e\u0448\u043b\u043e \u043d\u0435 \u0442\u0430\u043a!<\/p>\n<pre><code class=\"python\">Minimum path = 26<\/code><\/pre>\n<p>\u041c\u044b \u043d\u0430\u0448\u043b\u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c, \u043f\u0440\u043e\u0445\u043e\u0434\u044f\u0449\u0438\u0439 \u0447\u0435\u0440\u0435\u0437 \u0432\u0441\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u043d\u043e \u0432\u043e\u0442 \u0433\u0440\u0430\u0444 \u0440\u0430\u0441\u043f\u0430\u043b\u0441\u044f \u043d\u0430 \u0434\u0432\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430, \u0442\u0430\u043a \u0434\u0435\u043b\u043e \u043d\u0435 \u043f\u043e\u0439\u0434\u0451\u0442.<\/p>\n<p>\u041a\u0430\u043a \u043c\u044b \u043f\u043e\u043d\u0438\u043c\u0430\u0435\u043c, \u0447\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0435 \u0432\u0435\u0440\u043d\u043e\u0435? \u0423 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0432\u0435\u0440\u043d\u044b\u0439 \u043f\u0440\u0438\u0437\u043d\u0430\u043a: \u0435\u0441\u043b\u0438 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0441\u043f\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0434\u0432\u0430 \u0438\u043b\u0438 \u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430, \u0437\u043d\u0430\u0447\u0438\u0442 \u044d\u0442\u043e \u043d\u0435\u0432\u0435\u0440\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435.<\/p>\n<p>\u0412 \u043c\u043e\u0434\u0443\u043b\u0435 networkx \u0435\u0441\u0442\u044c \u043c\u0430\u0441\u0441\u0430 \u0432\u0441\u044f\u0447\u0435\u0441\u043a\u0438\u0445 \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u0433\u0440\u0430\u0444\u0430\u043c\u0438 \u043d\u0430 \u0432\u0441\u0435 \u0441\u043b\u0443\u0447\u0430\u0438 \u0436\u0438\u0437\u043d\u0438.<\/p>\n<p>\u041d\u0430\u0441 \u0431\u0443\u0434\u0435\u0442 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043e\u0432\u0430\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u044f nx.connected_components, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440 \u0434\u043b\u044f \u0433\u0440\u0430\u0444\u0430 \u0432 \u0432\u0438\u0434\u0435 \u043d\u0430\u0431\u043e\u0440\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432, \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043e\u043d \u0441\u043e\u0441\u0442\u043e\u0438\u0442.<\/p>\n<pre><code class=\"python\">print(list(nx.connected_components(graph))<\/code><\/pre>\n<pre><code class=\"python\">[{0, 2, 5}, {1, 3, 4}]<\/code><\/pre>\n<p>\u041d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0432\u0432\u0435\u0441\u0442\u0438 \u0434\u0438\u0441\u043a\u0440\u0438\u043c\u0438\u043d\u0438\u0440\u0443\u044e\u0449\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0431\u044b \u043e\u0442\u0432\u0435\u0440\u0433\u0430\u043b\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435, \u0435\u0441\u043b\u0438 \u043e\u043d\u043e \u0440\u0430\u0441\u043f\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430. \u041c\u044b \u043f\u043e\u0441\u0442\u0443\u043f\u0438\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c: \u0435\u0441\u043b\u0438 \u0432 \u0433\u0440\u0430\u0444\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430, \u0442\u043e \u043c\u044b \u043e\u0442\u043a\u0430\u0436\u0435\u043c\u0441\u044f \u043e\u0442 \u0442\u0430\u043a\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0438\u00a0\u0434\u043e\u0431\u0430\u0432\u0438\u043c \u043d\u043e\u0432\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c \u0442\u0430\u043a\u0438\u043c, \u0447\u0442\u043e \u0431\u044b \u043c\u0435\u0448\u0430\u043b\u043e \u0441\u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043e\u0448\u0438\u0431\u043e\u0447\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043f\u043e\u0432\u0442\u043e\u0440\u043d\u043e.<\/p>\n<pre><code class=\"python\">model += pl.lpSum([x[i[0] * n + i[1] if i[0] &lt; i[1] else i[1] * n + i[0]] for i in graph.edges]) &lt;= n - 2<\/code><\/pre>\n<p>\u0412 \u043c\u043e\u0434\u0435\u043b\u0438 \u0441\u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u043d\u043e\u0432\u043e\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u0435:<\/p>\n<pre><code class=\"python\">_C7: x_00_02 + x_00_05 + x_01_03 + x_01_04 + x_02_05 + x_03_04 &lt;= 4<\/code><\/pre>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u0435\u0449\u0451 \u0440\u0430\u0437, \u0441 \u0443\u0442\u043e\u0447\u043d\u0451\u043d\u043d\u044b\u043c\u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c\u0438.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/057\/45a\/fcd\/05745afcd8bf98da2f3d23cbe46f36c4.png\" alt=\"\" title=\"\" width=\"640\" height=\"440\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/057\/45a\/fcd\/05745afcd8bf98da2f3d23cbe46f36c4.png\"\/><figcaption><\/figcaption><\/figure>\n<pre><code class=\"python\">Minimum path = 31<\/code><\/pre>\n<p>\u041f\u0443\u0442\u044c \u0441\u0442\u0430\u043b \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0434\u043b\u0438\u043d\u043d\u0435\u0435 \u0447\u0435\u043c \u0440\u0430\u043d\u0435\u0435, \u043d\u043e \u0437\u0430\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432\u0435\u0440\u043d\u043e.<\/p>\n<ol start=\"3\">\n<li>\n<p>\u0428\u0430\u0433<\/p>\n<\/li>\n<\/ol>\n<p>\u0414\u043b\u044f \u0433\u0440\u0430\u0444\u043e\u0432 \u0431\u043e\u043b\u044c\u0448\u0435\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u0440\u043e\u0432\u043e\u0440\u0430\u0447\u0438\u0432\u0430\u0442\u044c \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0439 \u0442\u0440\u044e\u043a \u0432 \u0446\u0438\u043a\u043b\u0435 \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0439\u0434\u0435\u043d\u043e. <\/p>\n<p>\u041e\u0434\u043d\u0430\u043a\u043e \u0434\u0430\u0436\u0435 \u0434\u043b\u044f \u0442\u0430\u043a\u043e\u0433\u043e \u043d\u0435 \u0441\u0435\u0440\u044c\u0451\u0437\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430, \u043a\u0430\u043a \u044d\u0442\u043e\u0442, n=13:<\/p>\n<pre><code class=\"python\">[[  0  35  87  67  77  63  51 118 121 132 116   9  92]  [ 35   0  52  58  45  30  21  91 109 118 107  44  73]  [ 87  52   0  71  20  39  39  57  98 103 104  97  61]  [ 67  58  71   0  51  80  44  63  54  65  50  74  30]  [ 77  45  20  51   0  45  26  48  81  87  85  86  42]  [ 63  30  39  80  45   0  36  92 123 131 125  71  85]  [ 51  21  39  44  26  36   0  70  90  99  90  60  53]  [118  91  57  63  48  92  70   0  54  53  64 127  33]  [121 109  98  54  81 123  90  54   0  12  13 128  38]  [132 118 103  65  87 131  99  53  12   0  24 140  46]  [116 107 104  50  85 125  90  64  13  24   0 122  43]  [  9  44  97  74  86  71  60 127 128 140 122   0 100]  [ 92  73  61  30  42  85  53  33  38  46  43 100   0]]<\/code><\/pre>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u043f\u043e\u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u043f\u0440\u043e\u0439\u0442\u0438 208 \u0448\u0430\u0433\u043e\u0432 \u0438 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c 207 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439, \u043a \u0442\u043e\u043c\u0443 \u0436\u0435 \u0440\u0430\u0441\u0447\u0451\u0442 \u0437\u0430\u0442\u044f\u043d\u0443\u043b\u0441\u044f \u043d\u0430 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043c\u0438\u043d\u0443\u0442.<\/p>\n<p>\u0422\u0430\u043a \u043a\u0430\u043a \u0441 \u0440\u043e\u0441\u0442\u043e\u043c \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043c\u043e\u0436\u0435\u0442 \u0440\u0430\u0441\u043f\u0430\u0441\u0442\u044c\u0441\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u0435\u0442 \u044d\u043a\u0441\u043f\u043e\u043d\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u043e. \u041d\u0430\u043c \u043d\u0443\u0436\u043d\u0430 \u0434\u0440\u0443\u0433\u0430\u044f \u0441\u0442\u0440\u0430\u0442\u0435\u0433\u0438\u044f!<\/p>\n<ol start=\"4\">\n<li>\n<p>\u0428\u0430\u0433<\/p>\n<\/li>\n<\/ol>\n<p>\u0423\u0442\u0432\u0435\u0440\u0436\u0434\u0430\u044e, \u0447\u0442\u043e \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043c\u043e\u0436\u043d\u043e \u0434\u043e\u0431\u0438\u0442\u044c\u0441\u044f \u0432\u0441\u0435\u0433\u043e \u0437\u0430 4 \u0448\u0430\u0433\u0430 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044f \u0438 \u0434\u043e\u0431\u0430\u0432\u0438\u0432 \u0432\u0441\u0435\u0433\u043e 6 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439. \u0412\u0441\u0451 \u0447\u0442\u043e \u043d\u0443\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c, \u044d\u0442\u043e \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u044c \u043d\u0430\u0431\u043e\u0440 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0438\u0432\u0430\u044e\u0449\u0438\u0445 \u0443\u0441\u043b\u043e\u0432\u0438\u0439.<\/p>\n<p>\u0414\u0438\u0441\u043a\u0440\u0438\u043c\u0438\u043d\u0438\u0440\u0443\u044e\u0449\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043e\u043b\u0436\u043d\u0430 \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u044f, \u0447\u0442\u043e \u0431\u044b \u043f\u0440\u0435\u043f\u044f\u0442\u0441\u0442\u0432\u043e\u0432\u0430\u043b\u0438 \u0440\u0430\u0441\u043f\u0430\u0434\u0443 \u0433\u0440\u0430\u0444\u0430 \u043d\u0430 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0435 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430.<\/p>\n<p>\u0412\u043e\u0442 \u043e\u0434\u043d\u043e \u0438\u0437 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439:<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/ce7\/71a\/2d5\/ce771a2d543524474d71029302c68a37.png\" alt=\"\u0412 \u0434\u0430\u043d\u043d\u043e\u043c \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0438 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u043a\u043b\u044e\u0447 \u043a \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u043c\u0443 \u043c\u0435\u0442\u043e\u0434\u0443\" title=\"\u0412 \u0434\u0430\u043d\u043d\u043e\u043c \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0438 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u043a\u043b\u044e\u0447 \u043a \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u043c\u0443 \u043c\u0435\u0442\u043e\u0434\u0443\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ce7\/71a\/2d5\/ce771a2d543524474d71029302c68a37.png\"\/><figcaption>\u0412 \u0434\u0430\u043d\u043d\u043e\u043c \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0438 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u043a\u043b\u044e\u0447 \u043a \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u043c\u0443 \u043c\u0435\u0442\u043e\u0434\u0443<\/figcaption><\/figure>\n<p>\u0417\u0435\u043b\u0451\u043d\u044b\u043c \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u044b \u0440\u0451\u0431\u0440\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u043f\u0430\u0434\u0430\u044e\u0442 \u0432 \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e<\/p>\n<pre><code class=\"python\">_C14: x_00_02 + x_00_03 + x_00_04 + x_00_05 + x_00_06 + x_00_07 + x_00_08  + x_00_09 + x_00_10 + x_00_12 + x_01_02 + x_01_03 + x_01_04 + x_01_05  + x_01_06 + x_01_07 + x_01_08 + x_01_09 + x_01_10 + x_01_12 + x_02_11  + x_03_11 + x_04_11 + x_05_11 + x_06_11 + x_07_11 + x_08_11 + x_09_11  + x_10_11 + x_11_12 >= 2<\/code><\/pre>\n<p>\u0422\u0430\u043a\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043d\u0443\u0436\u043d\u043e \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u043e\u0434\u0433\u0440\u0430\u0444\u0430. \u041d\u0430 \u043f\u0435\u0440\u0432\u043e\u043c \u044d\u0442\u0430\u043f\u0435 \u0432 \u044d\u0442\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u0438\u0445 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c \u0447\u0435\u0442\u044b\u0440\u0435.<\/p>\n<p>\u042d\u0442\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u0445\u043e\u0436\u0435 \u043d\u0430 \u0442\u043e, \u043a\u0430\u043a \u0435\u0441\u043b\u0438 \u0431\u044b \u043c\u044b \u0432\u0437\u044f\u043b\u0438 \u043b\u0438\u043f\u043a\u0443\u044e \u043b\u0435\u043d\u0442\u0443 \u0438 \u043f\u0435\u0440\u0435\u043c\u043e\u0442\u0430\u043b\u0438 \u0433\u0440\u0430\u0444 \u0432 \u0442\u0435\u0445 \u043c\u0435\u0441\u0442\u0430\u0445, \u0433\u0434\u0435 \u043e\u043d \u043f\u044b\u0442\u0430\u0435\u0442\u0441\u044f \u0440\u0430\u0437\u0432\u0430\u043b\u0438\u0442\u044c\u0441\u044f. \u0422\u0430\u043a\u043e\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u043f\u043e\u0434\u0445\u043e\u0434 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442, \u043d\u0435\u0442, \u043d\u0435 \u0432 \u0440\u0430\u0437\u044b, \u0430 \u043d\u0430 \u043f\u043e\u0440\u044f\u0434\u043a\u0438 \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 (\u0434\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043c\u0430\u0442\u0440\u0438\u0446).<\/p>\n<p><strong>\u0412\u043d\u0438\u043c\u0430\u043d\u0438\u0435!<\/strong> \u0421\u0443\u0442\u044c \u043c\u0435\u0442\u043e\u0434\u0430:<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/2cc\/531\/803\/2cc531803edf3316854ce93e13f06438.png\" width=\"676\" height=\"69\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2cc\/531\/803\/2cc531803edf3316854ce93e13f06438.png\"\/><figcaption><\/figcaption><\/figure>\n<p>\u0421\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043c\u043d\u0435 \u0441\u043b\u043e\u0436\u043d\u043e \u0432\u044b\u0440\u0430\u0437\u0438\u0442\u044c \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438, \u043d\u043e \u0437\u0432\u0443\u0447\u0430\u0442\u044c \u043e\u043d\u043e \u0434\u043e\u043b\u0436\u043d\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<blockquote>\n<p><em>\u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430, \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0440\u0430\u0441\u043f\u0430\u0434\u0430\u043b\u043e\u0441\u044c \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e V \u043d\u0430 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445 \u044d\u0442\u0430\u043f\u0430\u0445, \u0434\u043e\u043b\u0436\u043d\u043e \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u043f\u043e \u043a\u0440\u0430\u0439\u043d\u0435\u0439 \u043c\u0435\u0440\u0435 \u0434\u0432\u0435 \u0441\u0432\u044f\u0437\u0438, \u0441\u043e\u0435\u0434\u0438\u043d\u044f\u044e\u0449\u0438\u0435 \u0435\u0433\u043e \u0441 \u0434\u0440\u0443\u0433\u0438\u043c\u0438 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430\u043c\u0438 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0433\u043e \u044d\u0442\u0430\u043f\u0430.<\/em><\/p>\n<p><em>\u041f\u0440\u043e\u0446\u0435\u0441\u0441 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0442\u044c \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043e\u0441\u0442\u0430\u043d\u0435\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u043d\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e, \u043e\u043d\u043e \u0438 \u0431\u0443\u0434\u0435\u0442 \u0438\u0441\u043a\u043e\u043c\u044b\u043c.<\/em><\/p>\n<\/blockquote>\n<hr\/>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/fe2\/a89\/d53\/fe2a89d530e2d599ce30cd87cbdf711f.png\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fe2\/a89\/d53\/fe2a89d530e2d599ce30cd87cbdf711f.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/ec7\/8d9\/557\/ec78d95570b5e9808c1620a38db8a49f.png\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ec7\/8d9\/557\/ec78d95570b5e9808c1620a38db8a49f.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/617\/aa4\/c58\/617aa4c5844978dc0ad8d54997ab38b6.png\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/617\/aa4\/c58\/617aa4c5844978dc0ad8d54997ab38b6.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/bfb\/28e\/7fc\/bfb28e7fcde3fd5ae9cdfb9c913ce81d.png\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/bfb\/28e\/7fc\/bfb28e7fcde3fd5ae9cdfb9c913ce81d.png\"\/><figcaption><\/figcaption><\/figure>\n<p>\u041f\u043e \u043c\u043e\u0438\u043c \u0432\u044b\u043a\u043b\u0430\u0434\u043a\u0430\u043c \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f, \u0447\u0442\u043e \u0434\u0430\u0436\u0435 \u0432 \u0441\u0430\u043c\u043e\u043c <strong>\u0445\u0443\u0434\u0448\u0435\u043c<\/strong> \u0441\u043b\u0443\u0447\u0430\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u043d\u0430 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u043c \u043f\u043e\u043b\u043d\u043e\u0441\u0432\u044f\u0437\u043d\u043e\u043c \u0433\u0440\u0430\u0444\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c \u0448\u0430\u0433\u043e\u0432:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\left\\lceil \\frac{n}{2} \\right\\rceil+1\" alt=\"\\left\\lceil \\frac{n}{2} \\right\\rceil+1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a25\/e35\/7ee\/a25e357ee33370764f62e75a036acb5b.svg\" width=\"72\" height=\"39\"\/><\/p>\n<p>\u0438 \u043d\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\sum_{i=6;n\\ge 6}^{n}\\left\\lfloor\\sqrt{n}-1\\right\\rfloor\" alt=\"\\sum_{i=6;n\\ge 6}^{n}\\left\\lfloor\\sqrt{n}-1\\right\\rfloor\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fef\/840\/e3c\/fef840e3cfd4a55c7ccf36fd8394e7df.svg\" width=\"133\" height=\"59\"\/><\/p>\n<p>\u0427\u0438\u0441\u043b\u043e 6 \u0432 \u0441\u0443\u043c\u043c\u0435 \u043d\u0435 \u0441\u043b\u0443\u0447\u0430\u0439\u043d\u043e, \u043d\u0430 \u0433\u0440\u0430\u0444\u0430\u0445 \u0441 \u0447\u0438\u0441\u043b\u043e\u043c \u0432\u0435\u0440\u0448\u0438\u043d \u043f\u044f\u0442\u044c \u0438 \u043c\u0435\u043d\u0435\u0435 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0441\u043e\u0432\u0441\u0435\u043c \u043d\u0435 \u043d\u0443\u0436\u043d\u044b, \u0442\u0430\u043a \u043a\u0430\u043a \u0432 \u0442\u0430\u043a\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u043f\u043e\u044f\u0432\u0438\u0442\u0441\u044f \u043f\u043e\u0434\u0446\u0438\u043a\u043b\u044b. (\u0414\u043b\u044f \u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u043e\u0434\u0446\u0438\u043a\u043b\u0430 \u043f\u0440\u0438 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u043a\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u0442\u0440\u0438 \u0432\u0435\u0440\u0448\u0438\u043d\u044b.)<\/p>\n<p>\u0422\u0430\u043a \u0434\u043b\u044f n = 100, \u043d\u0443\u0436\u043d\u043e \u043d\u0435 \u0431\u043e\u043b\u0435\u0435 523, \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0430 \u0434\u043b\u044f n=1000, 19613, \u0447\u0442\u043e \u0432\u043f\u043e\u043b\u043d\u0435 \u043d\u0435 \u043f\u043b\u043e\u0445\u043e.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/b52\/464\/1d2\/b524641d26d0787a2b18d56c3303b11a.png\" alt=\"\u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435.\" title=\"\u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435.\" width=\"920\" height=\"520\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b52\/464\/1d2\/b524641d26d0787a2b18d56c3303b11a.png\"\/><figcaption>\u0417\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435.<\/figcaption><\/figure>\n<p>\u0418\u0441\u0445\u043e\u0434\u044f \u0438\u0437 \u0442\u043e\u0433\u043e, \u0447\u0442\u043e \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0437\u0430\u0434\u0430\u044e\u0442\u0441\u044f \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u0435\u0439 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0434\u043b\u044f \u044d\u043a\u043e\u043d\u043e\u043c\u0438\u0438 \u043f\u0430\u043c\u044f\u0442\u0438 \u043e\u0442\u0431\u0440\u043e\u0441\u0438\u0442\u044c \u0432\u0435\u0440\u0445\u043d\u044e\u044e \u0438\u043b\u0438 \u043d\u0438\u0436\u043d\u044e\u044e \u0435\u0451 \u0447\u0430\u0441\u0442\u044c, \u0430 \u0442\u0430\u043a\u0436\u0435 \u0433\u043b\u0430\u0432\u043d\u0443\u044e \u0434\u0438\u0430\u0433\u043e\u043d\u0430\u043b\u044c.<\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/977\/73e\/40b\/97773e40b84884c9bd52c6796d3809dd.png\" width=\"427\" height=\"280\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/977\/73e\/40b\/97773e40b84884c9bd52c6796d3809dd.png\"\/><figcaption><\/figcaption><\/figure>\n<p>\u0423\u043c\u0435\u043d\u044c\u0448\u0438\u043c, \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0447\u0438\u0441\u043b\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u0441\u043e\u043b\u0432\u0435\u0440\u0430 \u0434\u043e:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\frac{(n^{2}-n)}{2}\" alt=\"\\frac{(n^{2}-n)}{2}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/591\/5a2\/995\/5915a2995e16c0f0b08948aa7616ea5c.svg\" width=\"77\" height=\"46\"\/><\/p>\n<p>\u041f\u043e\u0447\u0435\u043c\u0443 \u0436\u0435 \u0442\u0430\u043a \u0432\u0430\u0436\u043d\u043e \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u0447\u0438\u0441\u043b\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0438 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439? \u0415\u0441\u043b\u0438 \u043f\u043e\u0434 \u043a\u0430\u043f\u043e\u0442\u043e\u043c \u0443 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044f \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0441\u0438\u043c\u043f\u043b\u0435\u043a\u0441 \u043c\u0435\u0442\u043e\u0434, \u0438\u043b\u0438 \u0435\u0433\u043e \u0430\u043d\u0430\u043b\u043e\u0433, \u0442\u043e \u0444\u043e\u0440\u043c\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u0430:<\/p>\n<p><img class=\"formula\" source=\"N*M; N>M&#187; alt=&#187;N*M; N>M&#187; src=&#187;https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/71c\/922\/bba\/71c922bba331933fecaa49f611618801.svg&#187; width=&#187;127&#8243; height=&#187;20&#8243;\/><\/p>\n<p>\u0433\u0434\u0435 N \u2013 \u0447\u0438\u0441\u043b\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0443\u0447\u0430\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 \u0432 \u0440\u0430\u0441\u0447\u0451\u0442\u0435, \u0430 M \u2013 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439.<\/p>\n<p>\u0410 \u043a\u0430\u0436\u0434\u043e\u0435 \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442 \u0438\u0441\u0445\u043e\u0434\u043d\u0443\u044e \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u043d\u0430 1 \u043f\u043e \u043e\u0431\u0435\u0438\u043c \u043e\u0441\u044f\u043c.<\/p>\n<p>\u0427\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435 \u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u0442\u0435\u043c \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435 \u0440\u0430\u0441\u0447\u0451\u0442\u044b, \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e. <\/p>\n<p>(PuLP \u043e\u0442\u0431\u0440\u0430\u0441\u044b\u0432\u0430\u0435\u0442 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u044b\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438)<\/p>\n<details class=\"spoiler\">\n<summary>\u041f\u043e\u0448\u0430\u0433\u043e\u0432\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0433\u0440\u0430\u0444 n = 200. \u041e\u0441\u0442\u043e\u0440\u043e\u0436\u043d\u043e \u043c\u043d\u043e\u0433\u043e \u0438\u0437\u043e\u0431\u0440\u0430\u0436\u0435\u043d\u0438\u0439!<\/summary>\n<div class=\"spoiler__content\">\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/804\/aca\/de3\/804acade39b3ddf9decd094d3ee76388.png\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/804\/aca\/de3\/804acade39b3ddf9decd094d3ee76388.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/d3b\/7b6\/fe2\/d3b7b6fe2abb88fee55c46bec5ee3793.png\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d3b\/7b6\/fe2\/d3b7b6fe2abb88fee55c46bec5ee3793.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/3ac\/ce3\/9b5\/3acce39b56329cb548ef85d508a9c89e.png\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3ac\/ce3\/9b5\/3acce39b56329cb548ef85d508a9c89e.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/e6a\/20d\/5eb\/e6a20d5ebb31d29e25c6a235654e2fce.png\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e6a\/20d\/5eb\/e6a20d5ebb31d29e25c6a235654e2fce.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/3ab\/27e\/0bc\/3ab27e0bc2b49d1fdf16e2fca8e06f07.png\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3ab\/27e\/0bc\/3ab27e0bc2b49d1fdf16e2fca8e06f07.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/f11\/0d7\/a06\/f110d7a06725265a7198150682ce25dc.png\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f11\/0d7\/a06\/f110d7a06725265a7198150682ce25dc.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/36b\/baa\/6a4\/36bbaa6a45a6e84afbef1433ca4890ed.png\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/36b\/baa\/6a4\/36bbaa6a45a6e84afbef1433ca4890ed.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/f5d\/f91\/8fb\/f5df918fbc0efe31943e89794b9f33f4.png\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f5d\/f91\/8fb\/f5df918fbc0efe31943e89794b9f33f4.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/86a\/7ff\/77c\/86a7ff77cc75733e332b9dfdd88e04eb.png\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/86a\/7ff\/77c\/86a7ff77cc75733e332b9dfdd88e04eb.png\"\/><figcaption><\/figcaption><\/figure>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/0cb\/301\/efa\/0cb301efab5ebf9d0f1d50c96ba98273.png\" width=\"547\" height=\"347\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0cb\/301\/efa\/0cb301efab5ebf9d0f1d50c96ba98273.png\"\/><figcaption><\/figcaption><\/figure>\n<\/p>\n<\/div>\n<\/details>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0442\u0430\u043a \u0436\u0435 \u0440\u0435\u0448\u0430\u0435\u0442 \u0437\u0434\u0430\u0447\u0443 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0451\u0440\u0430 \u043d\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c, \u0445\u043e\u0442\u044c \u0438 \u043d\u0435 \u0441\u0442\u043e\u043b\u044c \u0445\u043e\u0440\u043e\u0448\u043e \u043a\u0430\u043a \u043d\u0430 \u043c\u0438\u043d\u0438\u043c\u0443\u043c.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/efb\/965\/420\/efb96542079c0f9f49053a3a6192cb40.png\" alt=\"\u0417\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0451\u0440\u0430 \u043d\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c\" title=\"\u0417\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0451\u0440\u0430 \u043d\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c\" width=\"810\" height=\"501\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/efb\/965\/420\/efb96542079c0f9f49053a3a6192cb40.png\"\/><figcaption>\u0417\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0451\u0440\u0430 \u043d\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c<\/figcaption><\/figure>\n<p>\u0418\u043c\u0435\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u043c\u043a\u043d\u0443\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043d\u0435 \u0441\u0442\u043e\u043b\u044c \u0441\u043b\u043e\u0436\u043d\u043e \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0438\u0437\u043c\u0435\u043d\u0438\u0442\u044c \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0438 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043d\u0435 \u0437\u0430\u043c\u043a\u043d\u0443\u0442\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/db1\/b4f\/bff\/db1b4fbfff01089cd164449c7e6ce5ac.png\" alt=\"\u0417\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0451\u0440\u0430 \u043d\u0435 \u0437\u0430\u043c\u043a\u043d\u0443\u0442\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u044f\" title=\"\u0417\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0451\u0440\u0430 \u043d\u0435 \u0437\u0430\u043c\u043a\u043d\u0443\u0442\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u044f\" width=\"810\" height=\"501\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/db1\/b4f\/bff\/db1b4fbfff01089cd164449c7e6ce5ac.png\"\/><figcaption>\u0417\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0451\u0440\u0430 \u043d\u0435 \u0437\u0430\u043c\u043a\u043d\u0443\u0442\u044b\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u044f<\/figcaption><\/figure>\n<p>\u041d\u0435 \u0443\u0431\u0435\u0434\u0438\u043b, \u0447\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0442\u043e\u0440\u0442? \u0422\u0435\u0441\u0442\u0438\u0440\u0443\u0439\u0442\u0435!<\/p>\n<details class=\"spoiler\">\n<summary>TSP PuLP <\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"python\">#------------------------------------------------------------------------------------ # TSP_ILP - traveling salesman problem integer linear programming (ILP) method # \u0420\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u0438\u0432\u043e\u044f\u0436\u043e\u0440\u0430 \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f # Rebuilder 21.01.2023 https:\/\/habr.com\/ru\/publication\/edit\/711708\/ #------------------------------------------------------------------------------------ import numpy as np import random import matplotlib.pyplot as plt import networkx as nx import pulp as pl from datetime import datetime #------------------------------------------------------------------------------------ def distance(x1, y1, x2, y2):     return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5 #------------------------------------------------------------------------------------ print('\u041f\u043e\u0434\u043a\u043b\u044e\u0447\u0435\u043d\u043d\u044b\u0435 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0438:', pl.listSolvers(onlyAvailable=True))  # \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u0440\u0448\u0438\u043d \u0433\u0440\u0430\u0444\u0430 n = 80 # random.seed(2)  points = [(round(random.randint(0, 1500)), round(random.randint(0, 1000))) for i in range(n)] init_graph = nx.complete_graph(n) for i, j in init_graph.edges():     if j > i:         init_graph[i][j]['weight'] = round(distance(points[i][0], points[i][1], points[j][0], points[j][1]))  # \u0420\u0430\u0437\u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0433\u0440\u0430\u0444 \u043a\u0430\u043a \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438 # adjacency_matrix = nx.adjacency_matrix(init_graph).todense() # print(adjacency_matrix)          start_time = datetime.now()  # \u0421\u043e\u0437\u0434\u0430\u0451\u043c \u043c\u043e\u0434\u0435\u043b\u044c \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f model = pl.LpProblem(name=\"tsp\", sense=pl.LpMinimize) #model = pl.LpProblem(name=\"tsp\", sense=pl.LpMaximize)  # \u041f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c solver = pl.PULP_CBC_CMD(msg=False)  # \u041e\u0442\u043a\u0440\u044b\u0442\u044b\u0439, \u043f\u043e \u0443\u043c\u043e\u043b\u0447\u0430\u043d\u0438\u044e # solver = pl.SCIP_CMD(msg=False) # \u041e\u0442\u043a\u0440\u044b\u0442\u044b\u0439, \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435 CBC # solver = pl.CPLEX_PY(msg=False)  # 45 \u0411\u044b\u0441\u0442\u0440\u044b\u0439 \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0439 (1000 \u041f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445) # solver = pl.XPRESS_PY(msg=False)  # ~98 \u0411\u044b\u0441\u0442\u0440\u044b\u0439 \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0439 (5000 \u041f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 + \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439) # solver = pl.GUROBI(msg=False)  # 63 \u0411\u044b\u0441\u0442\u0440\u044b\u0439 \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0439 (2000 \u041f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445)  # \u041e\u0431\u044a\u044f\u0432\u043b\u044f\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 x = [pl.LpVariable(name=f'x_{i:03}_{j:03}', cat='Binary') for i in range(n) for j in range(n)] # \u0417\u0430\u0434\u0430\u0451\u043c \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f   for i in range(n):     model += pl.lpSum([x[i * n + j if i &lt; j else j * n + i] for j in range(n) if i != j]) == 2 # \u0423\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c \u0446\u0435\u043b\u0435\u0432\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e model += pl.lpSum([init_graph[i][j]['weight'] * x[i * n + j if i &lt; j else j * n + i] for i in range(n) for j in range(n) if i &lt; j])  step = 0 while True:     # \u0418\u0449\u0435\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435     status = model.solve(solver)        step += 1      graph_resilt = nx.Graph()      a = 0     for i, v in enumerate(model.variables()):         # \u041f\u0440\u0438\u0432\u043e\u0434\u0438\u043c float \u043e\u0442 \u0441\u043e\u043b\u0432\u0435\u0440\u0430 \u043a int         int_val = round(v.value())         if int_val > 0:                                 temp_name = v.name.split('_')             ii, jj = int(temp_name[1]), int(temp_name[2])             graph_resilt.add_edge(ii, jj)            # \u0420\u0430\u0437\u0431\u0438\u0432\u0430\u0435\u043c \u0433\u0440\u0430\u0444 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u043d\u0430 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430      result_sets = list(nx.connected_components(graph_resilt))     qty_sets = len(result_sets)     print('Step =', step, 'Sets =', len(result_sets))          if qty_sets == 1:         break              if qty_sets == 2:         model += pl.lpSum([x[ii * n + jj if ii&lt;jj else jj * n + ii] for i, vi in enumerate(result_sets) for j, vj in enumerate(result_sets) if i &lt; j for ii in vi for jj in vj]) >= 2     else:         for i, vi in enumerate(result_sets):             model += pl.lpSum([x[ii * n + jj if ii&lt;jj else jj * n + ii] for j, vj in enumerate(result_sets) if i != j for ii in vi for jj in vj]) >= 2             date_diff = (datetime.now() - start_time).total_seconds() print('Time =', date_diff)  min_cycle = nx.find_cycle(graph_resilt, 0) min_path = [i[0] for i in min_cycle] # print(model)  print('Length =', round(model.objective.value()), 'steps =', step, 'path =', min_path) plt.figure(figsize=(8, 6)) plt.axis (\"equal\") nx.draw(init_graph, points, width=0, edge_color=\"#C0C0C0\", with_labels=True, node_size=0, font_size=10) nx.draw(graph_resilt, points, width=2, edge_color=\"red\", style=\"-\", with_labels=False, node_size=0, alpha=1) plt.show() <\/code><\/pre>\n<\/p>\n<\/div>\n<\/details>\n<details class=\"spoiler\">\n<summary>TSP CVXPY<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"python\">#------------------------------------------------------------------------------------ # TSP_ILP - traveling salesman problem integer linear programming (ILP) method # \u0420\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u0438\u0432\u043e\u044f\u0436\u043e\u0440\u0430 \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f # Rebuilder 21.01.2023 https:\/\/habr.com\/ru\/publication\/edit\/711708\/ #------------------------------------------------------------------------------------ import numpy as np import matplotlib.pyplot as plt import cvxpy as cp import random import networkx as nx from datetime import datetime #------------------------------------------------------------------------------------ def distance(x1, y1, x2, y2):     # \u0420\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u0442\u043e\u0447\u043a\u0430\u043c\u0438 \u043d\u0430 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438      return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5 #------------------------------------------------------------------------------------ def to_flat_index(a, b):     # \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0435\u0442 \u043f\u043b\u043e\u0441\u043a\u0438\u0439 \u0438\u043d\u0434\u0435\u043a\u0441 \u0434\u043b\u044f \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u043e\u0439 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b       summ = 0     if a >= b:           for i in range(1, a):             summ += i         return summ + b     else:         for i in range(1, b):             summ += i         return summ + a #------------------------------------------------------------------------------------ def to_matrix_indexes(a):     # \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043a\u043e\u0440\u0442\u0435\u0436 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 \u0434\u043b\u044f \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u043e\u0439 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u043f\u043e \u043f\u043b\u043e\u0441\u043a\u043e\u043c\u0443 \u0438\u043d\u0434\u0435\u043a\u0441\u0443         i = 0     while (a > i):         i += 1         a -= i     return (i+1, a)         #------------------------------------------------------------------------------------ def matrix_count(a):     # \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 \u043f\u043b\u043e\u0441\u043a\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430 \u0434\u043b\u044f \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u043e\u0439 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b      return((a * a - a) \/\/ 2)         #------------------------------------------------------------------------------------ print('\u041f\u043e\u0434\u043a\u043b\u044e\u0447\u0435\u043d\u043d\u044b\u0435 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0438:', cp.installed_solvers()) # \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u0440\u0448\u0438\u043d \u0433\u0440\u0430\u0444\u0430 n = 80 # random.seed(3)  points = [(round(random.randint(0, 1500)), round(random.randint(0, 1000))) for i in range(n)] init_graph = nx.complete_graph(n) for i, j in init_graph.edges():     if j > i:         init_graph[i][j]['weight'] = round(distance(points[i][0], points[i][1], points[j][0], points[j][1]))  # \u0420\u0430\u0437\u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0433\u0440\u0430\u0444 \u043a\u0430\u043a \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438 # adjacency_matrix = nx.adjacency_matrix(init_graph).todense() # print(adjacency_matrix)          start_time = datetime.now() # \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 flat_size = matrix_count(n) c = [0] * flat_size # \u0423\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 for i in range(flat_size):     temp = to_matrix_indexes(i)           c[i] = init_graph[temp[1]][temp[0]]['weight'] x = cp.Variable(flat_size, boolean=True)  # \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f constraints = [] for i in range(n):     constraints += [cp.sum([x[to_flat_index(i, j)] for j in range(n) if i != j]) == 2] # \u0426\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f objective = cp.Minimize(cp.sum(c @ x))  step = 0 while True:     # \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c \u0437\u0430\u0434\u0430\u0447\u0443     prob = cp.Problem(objective, constraints)     # \u0418\u0449\u0435\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435     prob.solve(solver = cp.GLPK_MI) #     prob.solve(solver=cp.SCIPY) #     prob.solve(solver = cp.CBC) #     prob.solve(solver = cp.XPRESS) #     print(\"status:\", prob.status)           step += 1      graph_resilt = nx.Graph()      for i in np.argwhere(x.value == True):             temp = to_matrix_indexes(round(i[0]))         graph_resilt.add_edge(temp[1], temp[0])       # \u0420\u0430\u0437\u0431\u0438\u0432\u0430\u0435\u043c \u0433\u0440\u0430\u0444 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u043d\u0430 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430      result_sets = list(nx.connected_components(graph_resilt))     qty_sets = len(result_sets)     print('Step =', step, 'Sets =', len(result_sets))          # \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430\u0439\u0434\u0435\u043d\u043e       if qty_sets == 1:         break      # \u0414\u043e\u0431\u0430\u0432\u043e\u0447\u043d\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f         if qty_sets == 2:                 constraints += [cp.sum([x[to_flat_index(i, j)] for i in result_sets[0] for j in result_sets[1]]) >= 2]         else:         for i, vi in enumerate(result_sets):             constraints += [cp.sum([x[to_flat_index(ii, jj)] for j, vj in enumerate(result_sets) if i != j for ii in vi for jj in vj]) >= 2]              date_diff = (datetime.now() - start_time).total_seconds() print('Time =', date_diff)  min_cycle = nx.find_cycle(graph_resilt, 0) min_path = [i[0] for i in min_cycle]  print('Length =', round(prob.value), 'steps =', step, 'path =', min_path) plt.figure(figsize=(8, 6)) plt.axis (\"equal\") nx.draw(init_graph, points, width=0, edge_color=\"#C0C0C0\", with_labels=True, node_size=0, font_size=10) nx.draw(graph_resilt, points, width=2, edge_color=\"red\", style=\"-\", with_labels=False, node_size=0, alpha=1) plt.show()<\/code><\/pre>\n<\/p>\n<\/div>\n<\/details>\n<p>\u0422\u0430\u043a \u0436\u0435 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u043e\u0446\u0435\u043d\u0438\u0442\u044c \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u0443\u044e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043e\u0442\u043a\u0440\u044b\u0442\u043e\u0439 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 SciPy. \u0412 SciPy 1.10.0.. (<a href=\"https:\/\/docs.scipy.org\/doc\/scipy\/reference\/generated\/scipy.optimize.linprog.html\" rel=\"noopener noreferrer nofollow\">scipy.optimize.linprog<\/a>) \u041f\u043e\u044f\u0432\u0438\u043b\u0441\u044f \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0439 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c.<\/p>\n<pre><code class=\"python\">scipy.optimize.linprog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=None, method='highs', callback=None, options=None, x0=None, integrality=None)<\/code><\/pre>\n<p>\u0417\u0430\u0434\u0430\u0442\u044c \u0435\u0433\u043e \u043c\u043e\u0436\u043d\u043e, \u0441\u043a\u043e\u043c\u0431\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u0432 \u043e\u043f\u0446\u0438\u0438: [method=&#8217;highs&#8217;, integrality=1].<\/p>\n<p>\u041a\u043e\u0434 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0441\u043b\u043e\u0436\u043d\u043e\u0435\u0435. \u0422\u0430\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0441\u043e \u0437\u0432\u0451\u0437\u0434\u043e\u0447\u043a\u043e\u0439. \u041d\u043e \u0438 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0432\u044b\u0448\u0435.<\/p>\n<details class=\"spoiler\">\n<summary>TSP SciPy<\/summary>\n<div class=\"spoiler__content\">\n<pre><code class=\"python\">#------------------------------------------------------------------------------------ # TSP_ILP - traveling salesman problem integer linear programming (ILP) method # \u0420\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u0438\u0432\u043e\u044f\u0436\u043e\u0440\u0430 \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f # Rebuilder 21.01.2023 https:\/\/habr.com\/ru\/publication\/edit\/711708\/ #------------------------------------------------------------------------------------ import numpy as np from scipy import optimize import random import matplotlib.pyplot as plt import networkx as nx from datetime import datetime #------------------------------------------------------------------------------------ def distance(x1, y1, x2, y2):     # \u0420\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u0442\u043e\u0447\u043a\u0430\u043c\u0438 \u043d\u0430 \u043f\u043b\u043e\u0441\u043a\u043e\u0441\u0442\u0438      return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5 #------------------------------------------------------------------------------------ def to_flat_index(a, b):     # \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0435\u0442 \u043f\u043b\u043e\u0441\u043a\u0438\u0439 \u0438\u043d\u0434\u0435\u043a\u0441 \u0434\u043b\u044f \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u043e\u0439 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b       summ = 0     if a >= b:           for i in range(1, a):             summ += i         return summ + b     else:         for i in range(1, b):             summ += i         return summ + a #------------------------------------------------------------------------------------ def to_matrix_indexes(a):     # \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043a\u043e\u0440\u0442\u0435\u0436 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 \u0434\u043b\u044f \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u043e\u0439 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u043f\u043e \u043f\u043b\u043e\u0441\u043a\u043e\u043c\u0443 \u0438\u043d\u0434\u0435\u043a\u0441\u0443         i = 0     while (a > i):         i += 1         a -= i     return (i+1, a)         #------------------------------------------------------------------------------------ def matrix_count(a):     # \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0435\u0442 \u0440\u0430\u0437\u043c\u0435\u0440 \u043f\u043b\u043e\u0441\u043a\u043e\u0433\u043e \u0441\u043f\u0438\u0441\u043a\u0430 \u0434\u043b\u044f \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u043d\u043e\u0439 \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b      return((a * a - a) \/\/ 2)         #------------------------------------------------------------------------------------ def TSP_ILP_cycle(graph, direction=1):     # \u041d\u0430\u0445\u043e\u0434\u0438\u0442 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 (\u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439) \u043f\u0443\u0442\u044c \u0432 \u0433\u0440\u0430\u0444\u0435 \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f     # direction - \u041d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438: 1 \u041c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u0443\u0442\u044c, -1 \u041c\u0430\u043a\u0441\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u0443\u0442\u044c          print('Run', end='')     # \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u0440\u0448\u0438\u043d \u0433\u0440\u0430\u0444\u0430     n = len(graph.nodes())     # \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445     flat_n = matrix_count(n)     # \u0426\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f     objective_function = np.array([direction * graph[i][j]['weight'] for i in range(n) for j in range(n) if i > j], dtype=np.int32)     # \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043d\u0430 \u0434\u0438\u0430\u043f\u043f\u0430\u0437\u043e\u043d \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445     bounds = (0, 1)     # \u041e\u0431\u044a\u044f\u0432\u043b\u0435\u043d\u0438\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439     equality_a = np.zeros((n, flat_n), dtype=np.int8)     equality_b = np.array([2] * n, dtype=np.int8)     inequalities_a = np.zeros((0, flat_n), dtype=np.int8)     inequalities_b = np.zeros(0, dtype=np.int8)     # \u041d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043c\u043e\u0434\u0435\u043b\u0438     for i in range(n):         for j in range(n):             if i != j:                                 equality_a[i][to_flat_index(i, j)] = 1      # \u0418\u0449\u0435\u043c \u043e\u043f\u043e\u0440\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435     res = optimize.linprog(c=objective_function, bounds=bounds, A_eq=equality_a, b_eq=equality_b, method='highs', integrality=1)      step = 1     constraints = 0     while True:         print('.', end='')         # \u0421\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432 \u0432\u0438\u0434\u0435 \u0433\u0440\u0430\u0444\u0430         graph_resilt = nx.Graph()         for i, val in enumerate(res.x):             # \u041f\u0440\u0438\u0432\u043e\u0434\u0438\u043c float \u043e\u0442 \u0441\u043e\u043b\u0432\u0435\u0440\u0430 \u043a int             int_val = round(val)             if int_val == 1:                 temp = to_matrix_indexes(i)                 graph_resilt.add_edge(temp[1], temp[0])           # \u0420\u0430\u0437\u0431\u0438\u0432\u0430\u0435\u043c \u0433\u0440\u0430\u0444 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u043d\u0430 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430          result_sets = list(nx.connected_components(graph_resilt))              qty_sets = len(result_sets)          #         # \u0420\u0438\u0441\u0443\u0435\u043c \u0433\u0440\u0430\u0444         #         fig = plt.figure(figsize=(6.8, 4), edgecolor='black', linewidth=0) #         plt.title(f'Size: {n}; Length: {direction * round(res.fun)}; Steps: {step}; Constraints: {constraints}', fontsize=10) #         plt.axis(\"equal\")    #         nx.draw(graph, points, width=0, with_labels=True, node_size=0, font_size=6, font_color=\"black\", node_shape='o')        #         nx.draw(graph_resilt, points, width=1, edge_color=\"red\", style=\"-\", with_labels=False, node_size=0)                  # \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430\u0439\u0434\u0435\u043d\u043e \u0435\u0441\u043b\u0438 \u0432 \u0433\u0440\u0430\u0444\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u043d\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e          if qty_sets == 1:             break                  # \u0412\u0432\u043e\u0434\u0438\u043c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043c\u043e\u0434\u0435\u043b\u0438         if qty_sets == 2:             temp = np.zeros((1, flat_n), dtype=np.int8)                 for i in result_sets[0]:                 for j in result_sets[1]:                     temp[0][to_flat_index(i, j)] = -1             inequalities_a = np.append(inequalities_a, temp, axis=0)             inequalities_b = np.append(inequalities_b, np.array([-2], dtype=np.int8))             constraints += 1                 elif qty_sets > 2:             temp = np.zeros((qty_sets, flat_n), dtype=np.int8)             for i, vi in enumerate(result_sets):                            for j, vj in enumerate(result_sets):                     if i != j:                         for ii in vi:                             for jj in vj:                                 temp[i][to_flat_index(ii, jj)] = -1                                                                                            inequalities_a = np.append(inequalities_a, temp, axis=0)                     inequalities_b = np.append(inequalities_b, np.array([-2] * qty_sets, dtype=np.int8))             constraints += qty_sets          # \u0418\u0449\u0435\u043c \u0443\u0442\u043e\u0447\u043d\u0435\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435            res = optimize.linprog(c=objective_function, bounds=bounds, A_eq=equality_a, b_eq=equality_b, A_ub=inequalities_a, b_ub=inequalities_b, method='highs', integrality=1)            step += 1          print()     return {'length' : direction * round(res.fun), 'constraints' : constraints, 'steps' : step, 'path' : [i[0] for i in nx.find_cycle(graph_resilt, 0)], 'graph' : graph_resilt} #----------------------------------------------------------------------------------- def TSP_ILP_path(graph, end_points=(), direction=1):     # \u041d\u0430\u0445\u043e\u0434\u0438\u0442 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 (\u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439) \u043f\u0443\u0442\u044c \u0432 \u0433\u0440\u0430\u0444\u0435 \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f     # direction - \u041d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438: 1 \u041c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u0443\u0442\u044c, -1 \u041c\u0430\u043a\u0441\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043f\u0443\u0442\u044c              def get_end_points(li, n):         # \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u0435 \u0442\u043e\u0447\u043a\u0438 \u043f\u0443\u0442\u0438         path = [0] * n         for i in li:             for j in i:                 path[j] += 1            return [i for i, val in enumerate(path) if val == 1]      print('Run', end='')     # \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u0440\u0448\u0438\u043d \u0433\u0440\u0430\u0444\u0430        n = len(graph.nodes())         # \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445     flat_n = matrix_count(n)     # \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u043c \u0447\u0438\u0441\u043b\u043e \u0437\u0430\u0434\u0430\u043d\u043d\u044b\u0445 \u0433\u0440\u0430\u043d\u0438\u0447\u043d\u044b\u0445 \u0432\u0435\u0440\u0448\u0438\u043d     end_points_n = 0     if len(end_points) > 0 and end_points[0] >= 0 and end_points[0] &lt; n:         end_points_n += 1     if len(end_points) > 1 and end_points[1] >= 0 and end_points[1] &lt; n and end_points[0] != end_points[1]:         end_points_n += 1          # \u0426\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f     objective_function = np.array([direction * graph[i][j]['weight'] for i in range(n) for j in range(n) if i > j], dtype=np.int32)     # \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u043d\u0430 \u0434\u0438\u0430\u043f\u043f\u0430\u0437\u043e\u043d \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445     bounds = (0, 1)     # \u041e\u0431\u044a\u044f\u0432\u043b\u0435\u043d\u0438\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439     equality_a = np.ones((1, flat_n), dtype=np.int8)     equality_b = np.zeros(1, dtype=np.int32)     inequalities_a = np.zeros(((n - end_points_n) * 2, flat_n), dtype=np.int8)     inequalities_b = np.zeros((n - end_points_n) * 2, dtype=np.int8)     # \u041d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043c\u043e\u0434\u0435\u043b\u0438     equality_b[0] = n - 1     k = 0     for i in range(n):                # \u0415\u0441\u043b\u0438 \u0431\u044b\u043b\u0438 \u0437\u0430\u0434\u0430\u043d\u044b \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u0435 \u0442\u043e\u0447\u043a\u0438, \u0442\u043e \u0438\u0441\u043a\u043b\u044e\u0447\u0430\u0435\u043c \u0438\u0445 \u0438\u0437 \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432 \u0434\u043b\u044f \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u044f \u0443\u0441\u043b\u043e\u0432\u0438\u0439         if (end_points_n > 0) and (end_points[0] == i) or (end_points_n > 1) and (end_points[1] == i):                         continue         for j in range(n):             if i != j:                 flat_index = to_flat_index(i, j)                 inequalities_a[k][flat_index] = -1                                 inequalities_a[k + 1][flat_index] = 1         inequalities_b[k] = -1         inequalities_b[k + 1] = 2             k += 2             # \u0415\u0441\u043b\u0438 \u0431\u044b\u043b\u0438 \u0437\u0430\u0434\u0430\u043d\u044b \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u0435 \u0442\u043e\u0447\u043a\u0438, \u0442\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0443\u0441\u043b\u043e\u0432\u0438\u0438\u0435 \u043d\u0430 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e \u0435\u0434\u0438\u043d\u0438\u0446\u0435 \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0430\u0445 \u0442\u0430\u043a\u0438\u0445 \u0442\u043e\u0447\u0435\u043a     if end_points_n > 0:         equality_a = np.append(equality_a, np.zeros((1, flat_n), dtype=np.int8), axis=0)         equality_b = np.append(equality_b, np.ones(1, dtype=np.int8))             for i in range(n):              if i != end_points[0]:                 equality_a[1][to_flat_index(i, end_points[0])] = 1                      if end_points_n > 1:         equality_a = np.append(equality_a, np.zeros((1, flat_n), dtype=np.int8), axis=0)         equality_b = np.append(equality_b, np.ones(1, dtype=np.int8))             for i in range(n):              if i != end_points[1]:                 equality_a[2][to_flat_index(i, end_points[1])] = 1          # \u0418\u0449\u0435\u043c \u043e\u043f\u043e\u0440\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435     res = optimize.linprog(c=objective_function, bounds=bounds, A_eq=equality_a, b_eq=equality_b, A_ub=inequalities_a, b_ub=inequalities_b, method='highs', integrality=1)              step = 1     constraints = 0     while True:         print('.', end='')         # \u0421\u043e\u0445\u0440\u0430\u043d\u044f\u0435\u043c \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u0432 \u0432\u0438\u0434\u0435 \u0433\u0440\u0430\u0444\u0430         graph_resilt = nx.Graph()                  for i, val in enumerate(res.x):             # \u041f\u0440\u0438\u0432\u043e\u0434\u0438\u043c float \u043e\u0442 \u0441\u043e\u043b\u0432\u0435\u0440\u0430 \u043a int             int_val = round(val)             if int_val == 1:                 temp = to_matrix_indexes(i)                 graph_resilt.add_edge(temp[1], temp[0])           # \u0420\u0430\u0437\u0431\u0438\u0432\u0430\u0435\u043c \u0433\u0440\u0430\u0444 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0430 \u043d\u0430 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430          result_sets = list(nx.connected_components(graph_resilt))              qty_sets = len(result_sets)                  # \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430\u0439\u0434\u0435\u043d\u043e \u0435\u0441\u043b\u0438 \u0432 \u0433\u0440\u0430\u0444\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0434\u043d\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e          if qty_sets == 1:             break                  # \u0412\u0432\u043e\u0434\u0438\u043c \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043c\u043e\u0434\u0435\u043b\u0438         if qty_sets == 2:             temp = np.zeros((1, flat_n), dtype=np.int8)                 for i in result_sets[0]:                 for j in result_sets[1]:                     temp[0][to_flat_index(i, j)] = -1             inequalities_a = np.append(inequalities_a, temp, axis=0)             inequalities_b = np.append(inequalities_b, np.array([-2], dtype=np.int8))             constraints += 1                 elif qty_sets > 2:             temp = np.zeros((qty_sets, flat_n), dtype=np.int8)             for i, vi in enumerate(result_sets):                            for j, vj in enumerate(result_sets):                     if i != j:                         for ii in vi:                             for jj in vj:                                 temp[i][to_flat_index(ii, jj)] = -1                                             inequalities_a = np.append(inequalities_a, temp, axis=0)                     inequalities_b = np.append(inequalities_b, np.array([-2] * qty_sets, dtype=np.int8))             constraints += qty_sets          # \u0418\u0449\u0435\u043c \u0443\u0442\u043e\u0447\u043d\u0435\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435            res = optimize.linprog(c=objective_function, bounds=bounds, A_eq=equality_a, b_eq=equality_b, A_ub=inequalities_a, b_ub=inequalities_b, method='highs', integrality=1)         step += 1               # \u041e\u0442\u043e\u0431\u0440\u0430\u0436\u0430\u0435\u043c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c      ep = get_end_points(graph_resilt.edges, n)     path = list(nx.all_simple_paths(graph_resilt, ep[0], ep[1]))[0]              print()     return {'length' : direction * round(res.fun), 'constraints' : constraints, 'steps' : step, 'path' : path, 'graph' : graph_resilt} #----------------------------------------------------------------------------------- # \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0432\u0435\u0440\u0448\u0438\u043d \u0433\u0440\u0430\u0444\u0430 n = 80 # random.seed(4)  points = [(round(random.randint(0, 15000)), round(random.randint(0, 10000))) for i in range(n)]  init_graph = nx.complete_graph(n) for i, j in init_graph.edges():     if j > i:         init_graph[i][j]['weight'] = round(distance(points[i][0], points[i][1], points[j][0], points[j][1])) # \u0420\u0430\u0437\u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0433\u0440\u0430\u0444 \u043a\u0430\u043a \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438 # adjacency_matrix = nx.adjacency_matrix(init_graph).todense() # print(adjacency_matrix)  start_time = datetime.now() # \u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0440\u0430\u0441\u0447\u0451\u0442 \u0437\u0430\u043c\u043a\u043d\u0443\u0442\u043e\u0439 TSP res = TSP_ILP_cycle(init_graph, direction=1) # \u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0440\u0430\u0441\u0447\u0451\u0442 \u043d\u0435\u0437\u0430\u043c\u043a\u043d\u0443\u0442\u043e\u0439 TSP # res = TSP_ILP_path(init_graph, end_points=[], direction=1)  date_diff = (datetime.now() - start_time).total_seconds() print('Time =', date_diff) print('Path =', res['path'])  # \u0420\u0438\u0441\u0443\u0435\u043c \u0433\u0440\u0430\u0444         fig = plt.figure(figsize=(6.8, 4), edgecolor='black', linewidth=0) plt.title(f'Size: {n}; Length: {res[\"length\"]}; Steps: {res[\"steps\"]}; Constraints: {res[\"constraints\"]}', fontsize=10) plt.axis(\"equal\")    nx.draw(init_graph, points, width=0, with_labels=True, node_size=0, font_size=6, font_color=\"black\", node_shape='o') nx.draw(res[\"graph\"], points, width=1, edge_color=\"red\", style=\"-\", with_labels=False, node_size=0)<\/code><\/pre>\n<\/p>\n<\/div>\n<\/details>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043e \u0433\u0440\u0443\u0441\u0442\u043d\u043e\u043c. \u0412\u0441\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0439 \u043b\u043e\u0436\u0438\u0442\u0441\u044f \u043d\u0430 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439. \u041e\u0442 \u0435\u0433\u043e \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0430 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043f\u0440\u0438\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0432\u0441\u0451. \u041a\u0430\u043a \u044f \u043f\u043e\u043d\u0438\u043c\u0430\u044e, \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043a\u0430\u043a O(n^3) \u043e\u0442 \u0447\u0438\u0441\u043b\u0430 \u0432\u0435\u0440\u0448\u0438\u043d. \u041a \u0441\u043e\u0436\u0430\u043b\u0435\u043d\u0438\u044e, \u0435\u0441\u0442\u044c \u0438 \u043f\u043b\u043e\u0445\u0438\u0435 \u0441\u043b\u0443\u0447\u0430\u0438, \u043a\u043e\u0433\u0434\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043f\u0430\u0434\u0430\u0435\u0442 \u0434\u043e O(2^n). \u0426\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f NP-\u0442\u0440\u0443\u0434\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439. \u0421\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0437\u0430\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0451\u0440\u0430 \u043e\u0441\u0442\u0430\u0451\u0442\u0441\u044f NP-\u0442\u0440\u0443\u0434\u043d\u043e\u0439, \u043d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u043c\u044b \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0441\u043d\u0438\u0437\u0438\u043b\u0438 \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u043c\u0430\u0442\u0438\u043a\u0443 \u0437\u0430\u0434\u0430\u0447\u0438.<\/p>\n<p>\u042d\u0432\u0440\u0438\u0441\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u043c\u0435\u0442\u043e\u0434\u044b (\u0433\u0435\u043d\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0438 \u043c\u0443\u0440\u0430\u0432\u044c\u0438\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b) \u043a\u043e\u043d\u0435\u0447\u043d\u043e \u043e\u0431\u0445\u043e\u0434\u044f\u0442 \u0442\u0435\u043a\u0443\u0449\u0443\u044e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f, \u043d\u043e \u0437\u0430\u0442\u043e \u0433\u0440\u0435\u0448\u0430\u0442 \u0432 \u0442\u043e\u0447\u043d\u043e\u0441\u0442\u0438. <\/p>\n<hr\/>\n<p>\u0427\u0442\u043e \u0434\u0430\u0451\u0442 \u043d\u0430\u043c \u0442\u043e\u0447\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0451\u0440\u0430? \u041a\u0430\u043a \u043c\u043d\u0435 \u0432\u0438\u0434\u0438\u0442\u0441\u044f, \u043a\u0440\u043e\u043c\u0435 \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0442\u0440\u0430\u043d\u0441\u043f\u043e\u0440\u0442\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438, \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u0439 \u0432\u044b\u0438\u0433\u0440\u044b\u0448 \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0441\u0445\u0435\u043c\u043e\u0442\u0435\u0445\u043d\u0438\u043a\u0430 \/ \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u043e\u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0430.<\/p>\n<p>\u041d\u0430 \u043f\u0435\u0447\u0430\u0442\u043d\u043e\u0439 \u043f\u043b\u0430\u0442\u0435 \u043d\u0443\u0436\u043d\u043e \u043f\u0440\u043e\u0441\u0432\u0435\u0440\u043b\u0438\u0442\u044c \u043c\u043e\u043d\u0442\u0430\u0436\u043d\u044b\u0435 \u043e\u0442\u0432\u0435\u0440\u0441\u0442\u0438\u044f (\u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u043f\u0430\u0439\u043a\u0443 \/ \u043f\u0440\u043e\u0447\u0435\u0435 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0435), \u0432 \u043a\u0430\u043a\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043d\u0443\u0436\u043d\u043e \u043e\u0431\u0445\u043e\u0434\u0438\u0442\u044c \u0442\u043e\u0447\u043a\u0438 \u043a\u043e\u043d\u0442\u0430\u043a\u0442\u0430, \u0447\u0442\u043e\u0431\u044b \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u0440\u0435\u043c\u044f \u043d\u0430 \u043f\u0435\u0440\u0435\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u0440\u0430\u0431\u043e\u0447\u0435\u0433\u043e \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u0430? \u0417\u0430\u0434\u0430\u0447\u0430 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0451\u0440\u0430 \u0432 \u0447\u0438\u0441\u0442\u043e\u043c \u0432\u0438\u0434\u0435.<\/p>\n<hr\/>\n<p>\u041f\u043e\u043b\u0430\u0433\u0430\u044e, \u0447\u0442\u043e \u0441\u0430\u043c \u043f\u043e\u0434\u0445\u043e\u0434 \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u044b\u0439 \u0432 \u0445\u043e\u0434\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u043c\u043e\u0447\u044c \u043d\u0430\u0439\u0442\u0438 \u043a\u043b\u044e\u0447 \u043a \u0440\u0435\u0448\u0435\u043d\u0438\u044e \u0434\u0440\u0443\u0433\u0438\u0445 \u0437\u0430\u0434\u0430\u0447 \u043a\u043b\u0430\u0441\u0441\u0430 NP.<\/p>\n<p>P.S. \u0421\u043e\u0437\u0434\u0430\u0442\u044c \u044d\u0442\u0443 \u0440\u0430\u0431\u043e\u0442\u0443 \u0431\u044b\u043b\u043e NP-\u0442\u0440\u0443\u0434\u043d\u043e, \u043d\u0430\u0434\u0435\u044e\u0441\u044c \u043e\u043d\u0430 \u0432\u0430\u043c \u043f\u043e\u043d\u0440\u0430\u0432\u0438\u043b\u0430\u0441\u044c.<\/p>\n<\/p>\n<\/div>\n<\/div>\n<\/div>\n<p> <!----> <!----><\/div>\n<p> <!----> <!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/post\/711708\/\"> https:\/\/habr.com\/ru\/post\/711708\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<blockquote>\n<p><em>\u0412\u0441\u0435 \u043f\u0443\u0442\u0438 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b: \u043e\u043d\u0438 \u0432\u0435\u0434\u0443\u0442 \u0432 \u043d\u0438\u043a\u0443\u0434\u0430. \u041d\u043e \u0443 \u043e\u0434\u043d\u0438\u0445 \u0435\u0441\u0442\u044c \u0441\u0435\u0440\u0434\u0446\u0435, \u0430 \u0443 \u0434\u0440\u0443\u0433\u0438\u0445 \u2014 \u043d\u0435\u0442. \u041e\u0434\u0438\u043d \u043f\u0443\u0442\u044c \u0434\u0430\u0435\u0442 \u0442\u0435\u0431\u0435 \u0441\u0438\u043b\u044b, \u0434\u0440\u0443\u0433\u043e\u0439 \u2014 \u0443\u043d\u0438\u0447\u0442\u043e\u0436\u0430\u0435\u0442 \u0442\u0435\u0431\u044f.<\/em><\/p>\n<p><em>&#8212; \u041a\u0430\u0440\u043b\u043e\u0441 \u041a\u0430\u0441\u0442\u0430\u043d\u0435\u0434\u0430<\/em><\/p>\n<\/blockquote>\n<p>\u0417\u0434\u0440\u0430\u0432\u0441\u0442\u0432\u0443\u0439\u0442\u0435 \u0443\u0432\u0430\u0436\u0430\u0435\u043c\u044b\u0435 \u0434\u0430\u043c\u044b \u0438 \u0433\u043e\u0441\u043f\u043e\u0434\u0430, \u0430 \u0442\u0430\u043a\u0436\u0435 \u043d\u0435 \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0435 \u043b\u0438\u0447\u043d\u043e\u0441\u0442\u0438. \u0425\u043e\u0440\u043e\u0448\u0435\u0439 \u044d\u043f\u043e\u0445\u0438.<\/p>\n<p>\u041c\u044b \u0441 \u0432\u0430\u043c\u0438 \u0443\u0436\u0435 \u043f\u0440\u043e\u0431\u043e\u0432\u0430\u043b\u0438 \u0440\u0435\u0448\u0430\u0442\u044c \u0442\u043e\u0447\u043d\u043e \u0437\u0430\u0434\u0430\u0447\u0443 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0451\u0440\u0430 \u043c\u0435\u0442\u043e\u0434\u043e\u043c <a href=\"https:\/\/habr.com\/ru\/post\/701458\/\" rel=\"noopener noreferrer nofollow\">\u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f<\/a> \u0438 \u043c\u0435\u0442\u043e\u0434\u043e\u043c <a href=\"https:\/\/habr.com\/ru\/post\/708072\/\" rel=\"noopener noreferrer nofollow\">\u0432\u0435\u0442\u0432\u0435\u0439 \u0438 \u0433\u0440\u0430\u043d\u0438\u0446<\/a>, \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 \u043d\u0435 \u043f\u043b\u043e\u0445, \u043d\u043e \u0441\u043b\u0430\u0431\u043e\u0432\u0430\u0442.<\/p>\n<p>\u0412 \u0434\u0430\u043d\u043d\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u043f\u043e\u0441\u0442\u0430\u0440\u0430\u044e\u0441\u044c \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c, \u0447\u0442\u043e <strong>\u0442\u043e\u0447\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435<\/strong> \u0431\u043b\u0438\u0436\u0435, \u0447\u0435\u043c \u043f\u0440\u0438\u043d\u044f\u0442\u043e \u0441\u0447\u0438\u0442\u0430\u0442\u044c.<\/p>\n<p>\u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043c\u0435\u0442\u043e\u0434 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0447\u0430\u0441\u0442\u043d\u044b\u043c \u0441\u043b\u0443\u0447\u0430\u0435\u043c \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0432 \u0441\u0432\u043e\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0434\u043a\u043b\u0430\u0441\u0441\u043e\u043c \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f.<\/p>\n<p>\u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435\u00a0&#8212; \u044d\u0442\u043e \u043e\u0431\u043b\u0430\u0441\u0442\u044c \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u043a\u0438, \u0440\u0430\u0437\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u044e\u0449\u0430\u044f \u0442\u0435\u043e\u0440\u0438\u044e, \u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u044b \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043c\u043d\u043e\u0433\u043e\u043c\u0435\u0440\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0441 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c\u0438.<\/p>\n<p>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c: <\/p>\n<ul>\n<li>\n<p>\u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b\u043c\u0438 (\u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0438\u043b\u0438 \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0442\u043e\u0440\u043d\u0430\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f (\u043c\u0435\u0442\u043e\u0434 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u0432\u0435\u0442\u0432\u0435\u0439 \u0438 \u0433\u0440\u0430\u043d\u0438\u0446 \u043c\u043e\u0436\u043d\u043e \u043e\u0442\u043d\u0435\u0441\u0442\u0438 \u0441\u044e\u0434\u0430))<\/p>\n<\/li>\n<li>\n<p>\u043b\u0438\u043d\u0435\u0439\u043d\u044b\u043c\u0438 (\u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0438\u043b\u0438 \u043d\u0435\u043f\u0440\u0435\u0440\u044b\u0432\u043d\u044b\u043c\u0438)<\/p>\n<\/li>\n<li>\n<p>\u043d\u0435\u043b\u0438\u043d\u0435\u0439\u043d\u044b\u043c\u0438<\/p>\n<\/li>\n<\/ul>\n<p>\u041d\u043e \u0438 \u0441\u0430\u043c\u0430 \u0446\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c:<\/p>\n<ul>\n<li>\n<p>\u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 (Linear programming, LP)<\/p>\n<\/li>\n<li>\n<p>\u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u043e\u0439 (Quadratic programming,\u00a0QP)<\/p>\n<\/li>\n<li>\n<p>\u0434\u0440\u0443\u0433\u043e\u0439 \u043d\u0435\u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 (Conic optimization, \u0434\u0440.)<\/p>\n<\/li>\n<\/ul>\n<p>\u0412 \u0434\u0430\u043d\u043d\u043e\u0439 \u0440\u0430\u0431\u043e\u0442\u0435 \u043d\u0430\u0441 \u0431\u0443\u0434\u0435\u0442 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043e\u0432\u0430\u0442\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435, \u0433\u0434\u0435 \u0446\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u044b \u043b\u0438\u043d\u0435\u0439\u043d\u043e.<\/p>\n<p>\u0412 \u0441\u0432\u043e\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u043e\u0442 \u0442\u043e\u0433\u043e \u043a\u0430\u043a\u043e\u0439 \u0442\u0438\u043f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f, \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c:<\/p>\n<ul>\n<li>\n<p>\u0411\u0443\u043b\u0435\u0432\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 (Binary integer programming, PIB)<\/p>\n<\/li>\n<li>\n<p>\u0426\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0435 (\u0432\u0441\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0435, Integer programming, IP)<\/p>\n<\/li>\n<li>\n<p>\u0421\u043c\u0435\u0448\u0430\u043d\u043d\u043e\u0435 (\u0447\u0430\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u0430\u044f, Mixed-integer programming, MIP)<\/p>\n<\/li>\n<li>\n<p>\u041b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 (\u0432\u0441\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442\u0441\u044f \u043a\u0430\u043a \u043d\u0435 \u0446\u0435\u043b\u044b\u0435, \u043d\u0435\u043f\u0440\u0435\u0440\u044b\u0432\u043d\u044b\u0435 \u2013 continuous, LP)<\/p>\n<\/li>\n<\/ul>\n<p>\u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u043a\u043b\u0430\u0441\u0441\u0430 \u0437\u0430\u0434\u0430\u0447 \u0435\u0441\u0442\u044c \u0441\u0432\u043e\u0438 \u043c\u0435\u0442\u043e\u0434\u044b, \u0447\u0430\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u0441\u0435\u043a\u0430\u0435\u0442\u0441\u044f, \u0447\u0430\u0441\u0442\u044c \u0438\u043c\u0435\u0435\u0442 \u0441\u0432\u043e\u0438 \u0433\u0440\u0430\u043d\u0438\u0446\u044b \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f. \u042f \u043d\u0435 \u0431\u0443\u0434\u0443 \u0437\u0430\u043e\u0441\u0442\u0440\u044f\u0442\u044c \u0432\u0430\u0448\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043d\u0430 \u044d\u0442\u043e\u043c. \u041c\u0435\u043d\u044f \u0432 \u043f\u0435\u0440\u0432\u0443\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u0435\u0442 \u043f\u0440\u0438\u043a\u043b\u0430\u0434\u043d\u0430\u044f \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c\u043e\u0441\u0442\u044c \u0432 \u0440\u0430\u0431\u043e\u0442\u0435. <\/p>\n<p>\u041f\u043e\u044d\u0442\u043e\u043c\u0443, \u0435\u0441\u043b\u0438 \u0432\u0441\u0435 \u0441\u0438\u043b\u044c\u043d\u043e \u0443\u043f\u0440\u043e\u0441\u0442\u0438\u0442\u044c, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0432\u044b\u0432\u043e\u0434: \u0447\u0435\u043c \u0431\u043e\u043b\u0435\u0435 \u043d\u0435\u043f\u0440\u0435\u0440\u044b\u0432\u043d\u044b \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435, \u0442\u0435\u043c \u043b\u0435\u0433\u0447\u0435 \u043d\u0430\u0439\u0442\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 (Linear programming \u043b\u0435\u0433\u0447\u0435 \u043d\u0430\u0445\u043e\u0434\u0438\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u0447\u0435\u043c Mixed-integer \u0438 Integer programming)<\/p>\n<p>\u041d\u043e \u0442\u0430\u043a \u043a\u0430\u043a \u0432 \u043d\u0430\u0448\u0435\u0439 \u0436\u0438\u0437\u043d\u0438 \u043c\u043d\u043e\u0433\u0438\u0435 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u044b \u0434\u0438\u0441\u043a\u0440\u0435\u0442\u043d\u044b (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0442\u0440\u0443\u0434\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043f\u043e\u043a\u0443\u043f\u043a\u0443 1,25 \u0430\u0432\u0442\u043e\u043c\u043e\u0431\u0438\u043b\u044f, \u0438\u043b\u0438 \u0440\u0430\u0437\u0431\u0438\u0442\u044c 0,5 \u044f\u0439\u0446\u0430), \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043c\u0435\u0442\u043e\u0434 \u0440\u0435\u043b\u0430\u043a\u0441\u0430\u0446\u0438\u0438 (\u0430\u043f\u043f\u0440\u043e\u043a\u0441\u0438\u043c\u0430\u0446\u0438\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u0441\u043e\u0441\u0435\u0434\u043d\u0435\u0439 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u043e\u0439, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043b\u0435\u0433\u0447\u0435 \u0440\u0435\u0448\u0438\u0442\u044c).<\/p>\n<p>\u0422\u043e \u0435\u0441\u0442\u044c, \u0437\u0430\u0434\u0430\u0447\u0430 \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u043d\u0435 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u0430\u044f (\u0438\u043b\u0438 \u043d\u0435 \u0431\u0438\u043d\u0430\u0440\u043d\u0430\u044f), \u0430 \u0437\u0430\u0442\u0435\u043c \u043a \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u044b\u043c \u0434\u0430\u043d\u043d\u044b\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u044e\u0442\u0441\u044f \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u0440\u0438\u0432\u043e\u0434\u044f\u0442 \u0437\u0430\u0434\u0430\u0447\u0443 \u043a \u0436\u0435\u043b\u0430\u0435\u043c\u043e\u043c\u0443 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0443.<\/p>\n<hr\/>\n<p>\u041f\u0440\u0435\u0436\u0434\u0435 \u0447\u0435\u043c \u043c\u044b \u043f\u0435\u0440\u0435\u0439\u0434\u0451\u043c \u043d\u0435\u043f\u043e\u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443, \u0441\u043a\u0430\u0436\u0435\u043c \u043f\u0430\u0440\u0443 \u0441\u043b\u043e\u0432 \u0437\u0430 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u0430\u0440\u0438\u0439.<\/p>\n<p>\u0420\u0435\u0448\u0430\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u044f \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u043d\u0430 \u044f\u0437\u044b\u043a\u0435 Python, \u043a\u0430\u043a \u043e\u0447\u0435\u043d\u044c \u0443\u0434\u043e\u0431\u043d\u043e\u043c \u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0435 \u043f\u0440\u043e\u0442\u043e\u0442\u0438\u043f\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u043f\u0440\u043e\u0435\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0441 \u0431\u043e\u043b\u044c\u0448\u0438\u043c \u043d\u0430\u0431\u043e\u0440\u043e\u043c \u0432\u043d\u0435\u0448\u043d\u0438\u0445 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a \u0440\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u0438\u044f.<\/p>\n<p>\u0414\u043b\u044f \u043d\u0430\u0448\u0438\u0445 \u0446\u0435\u043b\u0435\u0439 \u043a\u0440\u043e\u043c\u0435 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u0433\u043e \u043d\u0430\u0431\u043e\u0440\u0430 \u043c\u043e\u0434\u0443\u043b\u0435\u0439 \u043d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c (solver) \u0437\u0430\u0434\u0430\u0447 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e (IP) \u0438\u043b\u0438 \u0441\u043c\u0435\u0448\u0430\u043d\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f (MIP). \u041f\u043e\u0434\u043e\u0439\u0434\u0451\u0442 \u043b\u044e\u0431\u043e\u0439 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u044b\u0439 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c.<\/p>\n<p>\u0412 \u0441\u0432\u043e\u0438\u0445 \u0438\u0437\u044b\u0441\u043a\u0430\u043d\u0438\u044f\u0445 \u044f \u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u043b \u0442\u0440\u0438 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0445 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0438 IP\/MIP: PuLP, CVXPY \u0438 SciPy.<\/p>\n<ol>\n<li>\n<p>PuLP &#8212; \u0434\u0430\u0436\u0435 \u0438\u0437 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u044f \u0441\u0442\u0430\u043d\u043e\u0432\u0438\u0442\u0441\u044f \u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u044d\u0442\u043e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u0435\u0434\u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0430 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u0421\u0440\u0435\u0434\u0438 \u0438\u043d\u044b\u0445 \u0430\u043b\u044c\u0442\u0435\u0440\u043d\u0430\u0442\u0438\u0432 \u043e\u043d\u0430 \u0432\u044b\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u0438\u0437\u043c\u043e\u043c, \u043f\u0440\u043e\u0441\u0442\u0430 \u0434\u043b\u044f \u043e\u0441\u0432\u043e\u0435\u043d\u0438\u044f \u043d\u043e\u0432\u0438\u0447\u043a\u0430\u043c\u0438, \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u043e\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c\u044e \u043f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0442\u044c \u0432\u043d\u0435\u0448\u043d\u0438\u0435 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0438.<\/p>\n<\/li>\n<li>\n<p>CVXPY &#8212; \u044d\u0442\u043e \u0432\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u044b\u0439 \u0432 Python \u044f\u0437\u044b\u043a \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u043c \u043a\u043e\u0434\u043e\u043c \u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447 \u0432\u044b\u043f\u0443\u043a\u043b\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438. \u0412 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 PuLP, \u043c\u043e\u0436\u0435\u0442 \u0440\u0435\u0448\u0430\u0442\u044c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438. \u0421\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0431\u043e\u043b\u0435\u0435 \u0431\u043e\u0433\u0430\u0442\u044b\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b \u0438 \u043f\u0440\u0438\u043b\u0438\u0447\u043d\u044b\u0439 \u043d\u0430\u0431\u043e\u0440 \u043f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0435\u043c\u044b\u0445 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0435\u0439. \u041e\u0434\u043d\u0430\u043a\u043e, \u043a\u0430\u043a \u043c\u043d\u0435 \u043f\u043e\u043a\u0430\u0437\u0430\u043b\u043e\u0441\u044c CVXPY \u0441\u043f\u0440\u0430\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441 \u043e\u0434\u043d\u043e\u0442\u0438\u043f\u043d\u044b\u043c\u0438 \u0437\u0430\u0434\u0430\u0447\u0430\u043c\u0438 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c PuLP \u043d\u0430 \u0442\u0435\u0445 \u0436\u0435 \u0432\u043d\u0435\u0448\u043d\u0438\u0445 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044f\u0445 (\u043f\u043e \u043a\u0440\u0430\u0439\u043d\u0435\u0439 \u043c\u0435\u0440\u0435, MIP) \u0438 \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u0435\u043d \u0434\u043b\u044f \u0438\u0437\u0443\u0447\u0435\u043d\u0438\u044f. \u0415\u0441\u043b\u0438 \u0432\u0430\u043c \u043d\u0435 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0432\u044b\u043f\u0443\u043a\u043b\u0430\u044f \u0446\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u0442\u043e \u044f \u0431\u044b \u0435\u0433\u043e \u0434\u043b\u044f \u0434\u0430\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043d\u0435 \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u043e\u0432\u0430\u043b.<\/p>\n<\/li>\n<li>\n<p>SciPy &#8212; \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430 \u0434\u043b\u044f \u044f\u0437\u044b\u043a\u0430 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f Python \u0441 \u043e\u0442\u043a\u0440\u044b\u0442\u044b\u043c \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u043c \u043a\u043e\u0434\u043e\u043c, \u043f\u0440\u0435\u0434\u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u043d\u0430\u044f \u0434\u043b\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u043d\u0430\u0443\u0447\u043d\u044b\u0445 \u0438 \u0438\u043d\u0436\u0435\u043d\u0435\u0440\u043d\u044b\u0445 \u0440\u0430\u0441\u0447\u0451\u0442\u043e\u0432. \u041d\u0430\u0441 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u0443\u0435\u0442 \u0435\u0451 \u043c\u043e\u0434\u0443\u043b\u044c optimize \u2013 \u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0430 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438. \u0421\u043a\u0430\u0436\u0443 \u0441\u0440\u0430\u0437\u0443, \u044d\u0442\u043e \u0432\u0435\u0441\u044c\u043c\u0430 \u0441\u043b\u043e\u0436\u043d\u044b\u0439 \u043f\u043e\u0434\u0445\u043e\u0434, \u043d\u043e \u0441\u0440\u0435\u0434\u0438 \u0432\u0441\u0435\u0445 \u043e\u043f\u0435\u043d\u0441\u043e\u0440\u0441\u043d\u044b\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u0441\u0430\u043c\u044b\u0439 \u0431\u044b\u0441\u0442\u0440\u044b\u0439, \u0447\u0442\u043e \u044f \u043d\u0430\u0448\u0451\u043b.<\/p>\n<\/li>\n<\/ol>\n<p>\u0412 \u043f\u0440\u0438\u043c\u0435\u0440\u0430\u0445 \u043a \u0441\u0442\u0430\u0442\u044c\u0435 \u0431\u0443\u0434\u0443 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u0440\u044b \u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c \u0441 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c PuLP, \u0447\u0442\u043e\u0431\u044b \u0432\u0430\u043c \u043b\u0435\u0433\u0447\u0435 \u0431\u044b\u043b\u043e \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f. <\/p>\n<p>\u041d\u0438\u0436\u0435 \u0431\u0443\u0434\u0443\u0442 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u044b \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u0445 \u0438 \u0441\u043c\u0435\u0448\u0430\u043d\u043d\u044b\u0445 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439, \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c\u044b\u0445 \u0434\u043b\u044f \u043d\u0430\u0448\u0438\u0445 \u0446\u0435\u043b\u0435\u0439.<\/p>\n<p>\u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0443\u0441\u0442\u0430\u043d\u043e\u0432\u0438\u043c \u0441\u0430\u043c <a href=\"https:\/\/github.com\/coin-or\/pulp\" rel=\"noopener noreferrer nofollow\">PuLP <\/a>\u043e\u043d \u0441\u043e\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0441\u043e \u0432\u0441\u0442\u0440\u043e\u0435\u043d\u043d\u044b\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0435\u043c CBC \u043e\u0442 COIN-OR Foundation, \u0438\u043c\u0435\u0435\u0442 \u043d\u0435\u043f\u043b\u043e\u0445\u0443\u044e \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c.<\/p>\n<pre><code class=\"powershell\">pip install pulp<\/code><\/pre>\n<p><a href=\"https:\/\/www.scipopt.org\/)\" rel=\"noopener noreferrer nofollow\">SCIP<\/a> &#8212; \u0442\u0430\u043a \u0436\u0435 \u0441\u0432\u043e\u0431\u043e\u0434\u043d\u044b\u0439 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c, \u043d\u043e \u0434\u043b\u044f \u0434\u0430\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e\u043d \u043c\u0435\u043d\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437\u043e\u0447\u0430\u0440\u043e\u0432\u0430\u043b. \u042d\u0442\u043e \u043d\u0435 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 \u0447\u0442\u043e \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u043f\u043b\u043e\u0445, \u043a\u0430\u043a \u043f\u043e \u043c\u043d\u0435 \u043e\u043d \u0443\u0441\u0442\u0443\u043f\u0430\u0435\u0442 CBC \u0432 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438.<\/p>\n<p><a href=\"https:\/\/www.ibm.com\/products\/ilog-cplex-optimization-studio\" rel=\"noopener noreferrer nofollow\">CPLEX <\/a>\u2013 \u043a\u043b\u0430\u0441\u0441\u043d\u044b\u0439 \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0439 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u043e\u0442 IBM. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043a\u043e\u043c\u044c\u044e\u043d\u0438\u0442\u0438 \u0432\u0435\u0440\u0441\u0438\u044f \u043d\u0435 \u0434\u043b\u044f \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043c\u043e\u0436\u0435\u0442 \u0440\u0435\u0448\u0430\u0442\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0435 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0434\u043e 1000 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0438 1000 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 (\u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u044b n&lt;=45)<\/p>\n<pre><code class=\"powershell\">pip install cplex docplex<\/code><\/pre>\n<p><a href=\"https:\/\/www.gurobi.com\/solutions\/gurobi-optimizer\/\" rel=\"noopener noreferrer nofollow\">GUROBI <\/a>&#8212; \u0435\u0449\u0451 \u043e\u0434\u0438\u043d \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0439 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c. \u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u043a\u043e\u043c\u044c\u044e\u043d\u0438\u0442\u0438 \u0432\u0435\u0440\u0441\u0438\u044f \u043d\u0435 \u0434\u043b\u044f \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043c\u043e\u0436\u0435\u0442 \u0440\u0435\u0448\u0430\u0442\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0435 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0434\u043e 2000 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 (\u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u044b n&lt;=63)<\/p>\n<pre><code class=\"powershell\">pip install gurobipy<\/code><\/pre>\n<p><a href=\"https:\/\/www.fico.com\/en\/products\/fico-xpress-optimization\" rel=\"noopener noreferrer nofollow\">Xpress <\/a>&#8212; \u0442\u0430\u043a \u0436\u0435 \u0445\u043e\u0440\u043e\u0448\u0438\u0439 \u043f\u0440\u043e\u043f\u0440\u0438\u0435\u0442\u0430\u0440\u043d\u044b\u0439 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c.<\/p>\n<p>\u041a\u043e\u043c\u044c\u044e\u043d\u0438\u0442\u0438 \u0432\u0435\u0440\u0441\u0438\u044f \u043d\u0435 \u0434\u043b\u044f \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f, \u043c\u043e\u0436\u0435\u0442 \u0440\u0435\u0448\u0430\u0442\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0435 \u0443\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0434\u043e 5000 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 + \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 (\u0434\u043b\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043a\u043e\u043c\u043c\u0438\u0432\u043e\u044f\u0436\u0435\u0440\u0430 \u043c\u0430\u0442\u0440\u0438\u0446\u044b ~n&lt;=98)<\/p>\n<pre><code class=\"powershell\">pip install xpress<\/code><\/pre>\n<p>\u0417\u0434\u0435\u0441\u044c \u043d\u0435 \u043f\u0440\u043e\u0441\u0442\u043e \u0442\u0430\u043a \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u044b \u0441\u0441\u044b\u043b\u043a\u0438 \u043d\u0430 \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0435 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u0438, \u0442\u0430\u043a \u043a\u0430\u043a \u043e\u043d\u0438 \u0441\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0441 \u0442\u043e\u0439 \u0436\u0435 \u0437\u0430\u0434\u0430\u0447\u0435\u0439 \u0432 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0440\u0430\u0437 \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u043d\u0430 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u043c \u043d\u0430\u0431\u043e\u0440\u0435 \u0434\u0430\u043d\u043d\u044b\u0445. \u0423 CPLEX \u0438 GUROBI \u0435\u0441\u0442\u044c \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0441\u043a\u0430\u0447\u0430\u0442\u044c \u0431\u0435\u0441\u043f\u043b\u0430\u0442\u043d\u0443\u044e \u0430\u043a\u0430\u0434\u0435\u043c\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u043b\u0438\u0446\u0435\u043d\u0437\u0438\u044e. \u0422\u0430\u043a \u043a\u0430\u043a \u044f \u043d\u0435 \u044f\u0432\u043b\u044f\u044e\u0441\u044c \u0443\u0447\u0430\u0441\u0442\u043d\u0438\u043a\u043e\u043c \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0441\u043a\u043e\u0439 \u0434\u0435\u044f\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u043c\u043d\u0435 \u044d\u0442\u043e\u0442 \u043f\u0443\u0442\u044c \u0437\u0430\u043a\u0430\u0437\u0430\u043d, \u043d\u043e \u0441\u043e\u0433\u043b\u0430\u0441\u0438\u0442\u0435\u0441\u044c, \u043f\u043e\u0434\u0445\u043e\u0434 \u043a\u043e\u043c\u043f\u0430\u043d\u0438\u0439 \u043f\u043e\u0434\u043a\u0443\u043f\u0430\u0435\u0442, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u0448\u044c \u043d\u0430 \u043a\u043e\u043c\u043c\u0435\u0440\u0447\u0435\u0441\u043a\u0438\u0435 \u0446\u0435\u043d\u043d\u0438\u043a\u0438.<\/p>\n<hr\/>\n<p>\u041f\u0435\u0440\u0435\u0439\u0434\u0451\u043c \u043a \u0441\u0430\u043c\u043e\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443.<\/p>\n<ol>\n<li>\n<p>\u0428\u0430\u0433<\/p>\n<\/li>\n<\/ol>\n<p>\u0412\u043e\u0437\u044c\u043c\u0451\u043c \u0441\u0438\u043c\u043c\u0435\u0442\u0440\u0438\u0447\u043d\u0443\u044e \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438 \u0434\u043b\u044f \u043d\u0435\u043a\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430 \u043d\u0430 5 \u0432\u0435\u0440\u0448\u0438\u043d:<\/p>\n<pre><code>[[ 0 14  3 13  8]  [14  0 16  2  7]  [ 3 16  0 14 10]  [13  2 14  0  6]  [ 8  7 10  6  0]]<\/code><\/pre>\n<p>\u041d\u0430\u0439\u0434\u0451\u043c \u0434\u043b\u044f \u043d\u0435\u0451 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0413\u0430\u043c\u0438\u043b\u044c\u0442\u043e\u043d\u043e\u0432 \u0446\u0438\u043a\u043b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f PuLP.<\/p>\n<pre><code class=\"python\">import pulp as pl # \u0421\u043e\u0437\u0434\u0430\u0434\u0438\u043c \u043c\u043e\u0434\u0435\u043b\u044c \u0437\u0430\u0434\u0430\u0447\u0438 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f - \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0434\u043b\u0438\u043d\u0443 \u043f\u0443\u0442\u0438 model = pl.LpProblem(name=\"tsp\", sense=pl.LpMinimize) # \u041f\u043e\u0434\u043a\u043b\u044e\u0447\u0430\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c solver = pl.PULP_CBC_CMD(msg=False) # \u0417\u0430\u0432\u043e\u0434\u0438\u043c \u043c\u0430\u0441\u0441\u0438\u0432 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 x = [pl.LpVariable(name=f'x_{i:02}_{j:02}', cat='Binary') for i in range(n) for j in range(n)] # \u0423\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c \u0446\u0435\u043b\u0435\u0432\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e model += pl.lpSum([matrix[i][j] * x[i * n + j if i &lt; j else j * n + i] for i in range(n) for j in range(n) if i &lt; j]) # \u0412\u043d\u043e\u0441\u0438\u043c \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043c\u043e\u0434\u0435\u043b\u0438 for i in range(n):     model += pl.lpSum([x[i * n + j if i &lt; j else j * n + i] for j in range(n) if i != j]) == 2<\/code><\/pre>\n<p>\u0415\u0441\u043b\u0438 \u0441\u0435\u0439\u0447\u0430\u0441 \u0432\u044b\u0432\u0435\u0441\u0442\u0438 \u043c\u043e\u0434\u0435\u043b\u044c, \u0442\u043e \u043e\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u0442\u044c \u0442\u0430\u043a: <\/p>\n<pre><code class=\"python\">tsp: MINIMIZE 14*x_00_01 + 3*x_00_02 + 13*x_00_03 + 8*x_00_04 + 16*x_01_02 + 2*x_01_03 + 7*x_01_04 + 14*x_02_03 + 10*x_02_04 + 6*x_03_04 + 0 SUBJECT TO _C1: x_00_01 + x_00_02 + x_00_03 + x_00_04 = 2 _C2: x_00_01 + x_01_02 + x_01_03 + x_01_04 = 2 _C3: x_00_02 + x_01_02 + x_02_03 + x_02_04 = 2 _C4: x_00_03 + x_01_03 + x_02_03 + x_03_04 = 2 _C5: x_00_04 + x_01_04 + x_02_04 + x_03_04 = 2 VARIABLES 0 &lt;= x_00_01 &lt;= 1 Integer 0 &lt;= x_00_02 &lt;= 1 Integer 0 &lt;= x_00_03 &lt;= 1 Integer 0 &lt;= x_00_04 &lt;= 1 Integer 0 &lt;= x_01_02 &lt;= 1 Integer 0 &lt;= x_01_03 &lt;= 1 Integer 0 &lt;= x_01_04 &lt;= 1 Integer 0 &lt;= x_02_03 &lt;= 1 Integer 0 &lt;= x_02_04 &lt;= 1 Integer 0 &lt;= x_03_04 &lt;= 1 Integer<\/code><\/pre>\n<p>x_[i]_[j] \u2013 \u044d\u0442\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043e\u0442\u0432\u0435\u0447\u0430\u0435\u0442 \u0437\u0430 \u0442\u043e, \u0432\u044b\u0431\u0438\u0440\u0430\u0435\u0442\u0441\u044f \u0434\u0430\u043d\u043d\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u0438\u043b\u0438 \u043d\u0435\u0442 (1 \/ 0).<\/p>\n<p>14 * x_[i]_[j] \u2013 \u044d\u0442\u043e \u0432\u0435\u0441 \u0440\u0435\u0431\u0440\u0430 \u0438\u0437 \u043c\u0430\u0442\u0440\u0438\u0446\u044b \u0441\u043c\u0435\u0436\u043d\u043e\u0441\u0442\u0438.<\/p>\n<p>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0433\u043e\u0432\u043e\u0440\u044f\u0442 \u043d\u0430\u043c \u043e \u0442\u043e\u043c, \u0447\u0442\u043e \u0432 \u043a\u0430\u0436\u0434\u0443\u044e \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0434\u043e\u043b\u0436\u043d\u043e \u0432\u0435\u0441\u0442\u0438 \u0440\u043e\u0432\u043d\u043e \u0434\u0432\u0430 \u043f\u0443\u0442\u0438, \u043f\u043e \u043e\u0434\u043d\u043e\u043c\u0443 \u043c\u044b \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u043c \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0443, \u0430 \u043f\u043e-\u0434\u0440\u0443\u0433\u043e\u043c\u0443 \u043c\u043e\u0436\u0435\u043c \u0432\u044b\u0439\u0442\u0438.<\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u0442\u0438\u0432 \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c<\/p>\n<pre><code class=\"python\">status = model.solve(solver)  for v in model.variables():         print(f'{v.name} = {round(v.value())}') print(f'Minimum path = {round(model.objective.value())}')<\/code><\/pre>\n<p>\u043f\u043e\u043b\u0443\u0447\u0438\u043c:<\/p>\n<pre><code class=\"python\">x_00_01 = 0 x_00_02 = 1 x_00_03 = 0 x_00_04 = 1 x_01_02 = 0 x_01_03 = 1 x_01_04 = 1 x_02_03 = 1 x_02_04 = 0 x_03_04 = 0 Minimum path = 34<\/code><\/pre>\n<p>\u041d\u0430\u043c \u043e\u0441\u0442\u0430\u0451\u0442\u0441\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u043e\u0442\u043e\u0431\u0440\u0430\u0437\u0438\u0442\u044c \u043d\u0430 \u0433\u0440\u0430\u0444\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u0440\u0451\u0431\u0440\u0430.<\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>\u041c\u044b \u043d\u0430\u0448\u043b\u0438 \u0413\u0430\u043c\u0438\u043b\u044c\u0442\u043e\u043d\u043e\u0432 \u0446\u0438\u043a\u043b \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b.<\/p>\n<ol start=\"2\">\n<li>\n<p>\u0428\u0430\u0433<\/p>\n<\/li>\n<\/ol>\n<p>\u0412\u043e\u0437\u044c\u043c\u0451\u043c \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u043a\u0440\u0443\u043f\u043d\u0435\u0435 \u0438 \u043f\u0440\u043e\u0432\u0435\u0434\u0451\u043c \u0442\u0435 \u0436\u0435 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u044f<\/p>\n<pre><code class=\"python\">[[ 0  5  8  5  7  1]  [ 5  0 12  4  4  5]  [ 8 12  0 13 15  7]  [ 5  4 13  0  2  6]  [ 7  4 15  2  0  8]  [ 1  5  7  6  8  0]]<\/code><\/pre>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>\u041e \u043d\u0435\u0442, \u0447\u0442\u043e-\u0442\u043e \u043f\u043e\u0448\u043b\u043e \u043d\u0435 \u0442\u0430\u043a!<\/p>\n<pre><code class=\"python\">Minimum path = 26<\/code><\/pre>\n<p>\u041c\u044b \u043d\u0430\u0448\u043b\u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u043f\u0443\u0442\u044c, \u043f\u0440\u043e\u0445\u043e\u0434\u044f\u0449\u0438\u0439 \u0447\u0435\u0440\u0435\u0437 \u0432\u0441\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b, \u043d\u043e \u0432\u043e\u0442 \u0433\u0440\u0430\u0444 \u0440\u0430\u0441\u043f\u0430\u043b\u0441\u044f \u043d\u0430 \u0434\u0432\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430, \u0442\u0430\u043a \u0434\u0435\u043b\u043e \u043d\u0435 \u043f\u043e\u0439\u0434\u0451\u0442.<\/p>\n<p>\u041a\u0430\u043a \u043c\u044b \u043f\u043e\u043d\u0438\u043c\u0430\u0435\u043c, \u0447\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0435 \u0432\u0435\u0440\u043d\u043e\u0435? \u0423 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0432\u0435\u0440\u043d\u044b\u0439 \u043f\u0440\u0438\u0437\u043d\u0430\u043a: \u0435\u0441\u043b\u0438 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0441\u043f\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0434\u0432\u0430 \u0438\u043b\u0438 \u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u0434\u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430, \u0437\u043d\u0430\u0447\u0438\u0442 \u044d\u0442\u043e \u043d\u0435\u0432\u0435\u0440\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435.<\/p>\n<p>\u0412 \u043c\u043e\u0434\u0443\u043b\u0435 networkx \u0435\u0441\u0442\u044c \u043c\u0430\u0441\u0441\u0430 \u0432\u0441\u044f\u0447\u0435\u0441\u043a\u0438\u0445 \u043f\u043e\u043b\u0435\u0437\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u0433\u0440\u0430\u0444\u0430\u043c\u0438 \u043d\u0430 \u0432\u0441\u0435 \u0441\u043b\u0443\u0447\u0430\u0438 \u0436\u0438\u0437\u043d\u0438.<\/p>\n<p>\u041d\u0430\u0441 \u0431\u0443\u0434\u0435\u0442 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043e\u0432\u0430\u0442\u044c \u0444\u0443\u043d\u043a\u0446\u0438\u044f nx.connected_components, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0433\u0435\u043d\u0435\u0440\u0430\u0442\u043e\u0440 \u0434\u043b\u044f \u0433\u0440\u0430\u0444\u0430 \u0432 \u0432\u0438\u0434\u0435 \u043d\u0430\u0431\u043e\u0440\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432, \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043e\u043d \u0441\u043e\u0441\u0442\u043e\u0438\u0442.<\/p>\n<pre><code class=\"python\">print(list(nx.connected_components(graph))<\/code><\/pre>\n<pre><code class=\"python\">[{0, 2, 5}, {1, 3, 4}]<\/code><\/pre>\n<p>\u041d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0432\u0432\u0435\u0441\u0442\u0438 \u0434\u0438\u0441\u043a\u0440\u0438\u043c\u0438\u043d\u0438\u0440\u0443\u044e\u0449\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0431\u044b \u043e\u0442\u0432\u0435\u0440\u0433\u0430\u043b\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432 \u0441\u043b\u0443\u0447\u0430\u0435, \u0435\u0441\u043b\u0438 \u043e\u043d\u043e \u0440\u0430\u0441\u043f\u0430\u0434\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430. \u041c\u044b \u043f\u043e\u0441\u0442\u0443\u043f\u0438\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c: \u0435\u0441\u043b\u0438 \u0432 \u0433\u0440\u0430\u0444\u0435 \u0431\u043e\u043b\u044c\u0448\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430, \u0442\u043e \u043c\u044b \u043e\u0442\u043a\u0430\u0436\u0435\u043c\u0441\u044f \u043e\u0442 \u0442\u0430\u043a\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0438\u00a0\u0434\u043e\u0431\u0430\u0432\u0438\u043c \u043d\u043e\u0432\u043e\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c \u0442\u0430\u043a\u0438\u043c, \u0447\u0442\u043e \u0431\u044b \u043c\u0435\u0448\u0430\u043b\u043e \u0441\u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043e\u0448\u0438\u0431\u043e\u0447\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043f\u043e\u0432\u0442\u043e\u0440\u043d\u043e.<\/p>\n<pre><code class=\"python\">model += pl.lpSum([x[i[0] * n + i[1] if i[0] &lt; i[1] else i[1] * n + i[0]] for i in graph.edges]) &lt;= n - 2<\/code><\/pre>\n<p>\u0412 \u043c\u043e\u0434\u0435\u043b\u0438 \u0441\u0444\u043e\u0440\u043c\u0438\u0440\u043e\u0432\u0430\u043b\u043e\u0441\u044c \u043d\u043e\u0432\u043e\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u0435:<\/p>\n<pre><code class=\"python\">_C7: x_00_02 + x_00_05 + x_01_03 + x_01_04 + x_02_05 + x_03_04 &lt;= 4<\/code><\/pre>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0440\u0435\u0448\u0430\u0442\u0435\u043b\u044c \u0435\u0449\u0451 \u0440\u0430\u0437, \u0441 \u0443\u0442\u043e\u0447\u043d\u0451\u043d\u043d\u044b\u043c\u0438 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f\u043c\u0438.<\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<pre><code class=\"python\">Minimum path = 31<\/code><\/pre>\n<p>\u041f\u0443\u0442\u044c \u0441\u0442\u0430\u043b \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0434\u043b\u0438\u043d\u043d\u0435\u0435 \u0447\u0435\u043c \u0440\u0430\u043d\u0435\u0435, \u043d\u043e \u0437\u0430\u0442\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0432\u0435\u0440\u043d\u043e.<\/p>\n<ol start=\"3\">\n<li>\n<p>\u0428\u0430\u0433<\/p>\n<\/li>\n<\/ol>\n<p>\u0414\u043b\u044f \u0433\u0440\u0430\u0444\u043e\u0432 \u0431\u043e\u043b\u044c\u0448\u0435\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u0440\u043e\u0432\u043e\u0440\u0430\u0447\u0438\u0432\u0430\u0442\u044c \u043f\u043e\u0434\u043e\u0431\u043d\u044b\u0439 \u0442\u0440\u044e\u043a \u0432 \u0446\u0438\u043a\u043b\u0435 \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0439\u0434\u0435\u043d\u043e. <\/p>\n<p>\u041e\u0434\u043d\u0430\u043a\u043e \u0434\u0430\u0436\u0435 \u0434\u043b\u044f \u0442\u0430\u043a\u043e\u0433\u043e \u043d\u0435 \u0441\u0435\u0440\u044c\u0451\u0437\u043d\u043e\u0433\u043e \u0433\u0440\u0430\u0444\u0430, \u043a\u0430\u043a \u044d\u0442\u043e\u0442, n=13:<\/p>\n<pre><code class=\"python\">[[  0  35  87  67  77  63  51 118 121 132 116   9  92]  [ 35   0  52  58  45  30  21  91 109 118 107  44  73]  [ 87  52   0  71  20  39  39  57  98 103 104  97  61]  [ 67  58  71   0  51  80  44  63  54  65  50  74  30]  [ 77  45  20  51   0  45  26  48  81  87  85  86  42]  [ 63  30<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-344279","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/344279","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=344279"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/344279\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=344279"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=344279"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=344279"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}