{"id":388780,"date":"2024-06-29T08:09:57","date_gmt":"2024-06-29T08:09:57","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=388780"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=388780","title":{"rendered":"<span>\u041c\u0435\u0442\u043e\u0434 \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438<\/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<p>     \u041d\u0435\u0434\u0430\u0432\u043d\u043e \u043d\u0430 \u0445\u0430\u0431\u0440\u0435 \u043c\u043d\u0435 \u043f\u043e\u043d\u0440\u0430\u0432\u0438\u043b\u0430\u0441\u044c \u0441\u0442\u0430\u0442\u044c\u044f  &#171;<a href=\"https:\/\/habr.com\/ru\/articles\/731006\/\" rel=\"noopener noreferrer nofollow\">\u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0438 \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0432 PuLP: \u0437\u0430\u0434\u0430\u0447\u0430 \u043e \u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u0445<\/a>&#187; , \u0433\u0434\u0435 \u0430\u0432\u0442\u043e\u0440 \u0438, \u043a\u0430\u043a \u044f \u043f\u043e\u0442\u043e\u043c \u0443\u0437\u043d\u0430\u043b, \u043c\u043e\u0439 \u0437\u043d\u0430\u043a\u043e\u043c\u044b\u0439 \u0440\u0435\u0448\u0438\u043b \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439 \u043e \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438, \u0441 \u0446\u0435\u043b\u044c\u044e \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u043e \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442\u044c \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0435\u0439 \u0441 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u0430\u043c\u0438, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u043c\u0438 \u0440\u0435\u0448\u0430\u0442\u044c \u0442\u0430\u043a\u043e\u0439 \u043a\u043b\u0430\u0441\u0441 \u0437\u0430\u0434\u0430\u0447, \u0438 \u043d\u0430\u0443\u0447\u0438\u0442\u044c \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f \u0432\u0438\u0434\u0435\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u043c \u043c\u0438\u0440\u0435, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043d\u0438\u043c\u0430\u0442\u044c, \u0433\u0434\u0435 \u043c\u043e\u0436\u0435\u0442 \u043e\u043a\u0430\u0437\u0430\u0442\u044c\u0441\u044f \u043f\u043e\u043b\u0435\u0437\u0435\u043d \u044d\u0442\u043e\u0442 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442. \u0422\u0430\u043a, \u0432 \u0441\u0432\u043e\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0430\u0432\u0442\u043e\u0440 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0440\u0435\u0441\u0443\u0440\u0441\u043e\u0432 \u043d\u0430 \u043f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0432\u0435\u0440\u0445\u043d\u0435\u0443\u0440\u043e\u0432\u043d\u0435\u0432\u043e\u0439 \u043f\u0438\u0442\u043e\u043d\u043e\u0432\u0441\u043a\u043e\u0439 \u043e\u0431\u043e\u043b\u043e\u0447\u043a\u0438 <a href=\"https:\/\/pypi.org\/project\/PuLP\/\" rel=\"noopener noreferrer nofollow\"><strong><em>pulp<\/em><\/strong><\/a> \u0441 \u043f\u043e\u0434\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435\u043c \u0441\u043e\u043b\u0432\u0435\u0440\u0430 <a href=\"https:\/\/github.com\/coin-or\/Cbc\" rel=\"noopener noreferrer nofollow\"><strong><em>cbc<\/em><\/strong><\/a> \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0441\u0430\u043c\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441\u043c\u0435\u0448\u0430\u043d\u043d\u043e\u0433\u043e \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. <\/p>\n<p>    \u041c\u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u043d\u0440\u0430\u0432\u0438\u043b\u0441\u044f \u0435\u0433\u043e \u0438\u0434\u0435\u044f, \u0432\u0435\u0434\u044c \u0442\u0430\u043a\u043e\u0439 \u043d\u0430\u0431\u043e\u0440 \u0441\u0442\u0430\u0442\u0435\u0439 \u043c\u043e\u0436\u0435\u0442 \u0440\u0430\u0441\u0448\u0438\u0440\u0438\u0442\u044c \u043a\u0440\u0443\u0433\u043e\u0437\u043e\u0440 \u043b\u044e\u0434\u0435\u0439 \u0438\u0437 \u0440\u0430\u0437\u043d\u044b\u0445 \u043e\u0431\u043b\u0430\u0441\u0442\u0435\u0439 &#8212; \u0443\u0447\u0435\u043d\u044b\u0445 \u043f\u043e \u0434\u0430\u043d\u043d\u044b\u043c, \u0431\u0438\u0437\u043d\u0435\u0441-\u0430\u043d\u0430\u043b\u0438\u0442\u0438\u043a\u043e\u0432, \u0430\u0440\u0445\u0438\u0442\u0435\u043a\u0442\u043e\u0440\u043e\u0432 \u0438 \u0432\u0441\u0435\u0445-\u0432\u0441\u0435\u0445-\u0432\u0441\u0435\u0445. \u041a\u0430\u043a \u0438\u0442\u043e\u0433, \u043e\u043d\u0430 \u043c\u0435\u043d\u044f \u043c\u043e\u0442\u0438\u0432\u0438\u0440\u043e\u0432\u0430\u043b\u0430 \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439 \u043e \u043c\u0435\u0442\u043e\u0434\u0430\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447 \u0441 \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c\u044e \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0441\u043f\u0435\u0446\u0438\u0444\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438. \u0415\u0441\u043b\u0438 \u0441\u0442\u0430\u0442\u044c\u0438 \u0431\u0443\u0434\u0443\u0442 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044e, \u0442\u043e \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0432\u043e\u0441\u043f\u0440\u0438\u044f\u0442\u0438\u044f \u044f \u0442\u0430\u043a\u0436\u0435 \u0431\u0443\u0434\u0443 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u0438\u0442\u043e\u043d\u043e\u0432\u0441\u043a\u0443\u044e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 <strong><em>pulp<\/em><\/strong> \u0434\u043b\u044f \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f.<\/p>\n<p>    <strong><em>\u0422\u0435\u043f\u0435\u0440\u044c \u043a \u0438\u0441\u0442\u043e\u043a\u0430\u043c \u0437\u0430\u0434\u0430\u0447\u0438:<\/em><\/strong> \u0447\u0430\u0441\u0442\u043e, \u0447\u0442\u043e\u0431\u044b \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043c\u043e\u0434\u0435\u043b\u044c \u0431\u044b\u043b\u0430 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c\u0430 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u043c \u0441\u0435\u043a\u0442\u043e\u0440\u0435, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u0447\u0435\u043d\u044c \u043c\u043d\u043e\u0433\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0438 \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445. \u00a0\u0412\u0440\u0435\u043c\u0435\u043d\u0430\u043c\u0438 \u0437\u0430\u0434\u0430\u0447\u0430 \u0432 \u043b\u043e\u0431 \u043c\u043e\u0436\u0435\u0442 \u0438 \u043d\u0435 \u0440\u0435\u0448\u0438\u0442\u044c\u0441\u044f, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0431\u044b\u043b\u0438 \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043d\u044b \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0442\u0440\u044e\u043a\u0438. \u041e\u0434\u0438\u043d \u0438\u0437 \u043d\u0438\u0445 &#8212; \u043c\u0435\u0442\u043e\u0434  \u00ab\u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432\u00bb   (Column generation). <\/p>\n<p>    \u041c\u0430\u0442\u0435\u0440\u0438\u0430\u043b \u0441 \u0434\u0435\u0442\u0430\u043b\u044f\u043c\u0438 \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043a\u0430\u0436\u0435\u0442\u0441\u044f \u0432\u0435\u0441\u044c\u043c\u0430 \u043e\u0431\u044a\u0435\u043c\u043d\u044b\u043c, \u0438, \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u043f\u0435\u0440\u0435\u043d\u0430\u0441\u044b\u0449\u0430\u0442\u044c \u0442\u0435\u043a\u0443\u0449\u0443\u044e \u0441\u0442\u0430\u0442\u044c\u044e, \u044f \u0440\u0435\u0448\u0438\u043b \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u0435\u0435 \u043d\u0430 \u0442\u0440\u0438 \u0447\u0430\u0441\u0442\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435, \u043f\u043e \u0441\u0443\u0442\u0438, \u043c\u043e\u0436\u043d\u043e \u0447\u0438\u0442\u0430\u0442\u044c \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e, \u043d\u043e \u043f\u0440\u0438 \u043f\u0440\u043e\u0447\u0442\u0435\u043d\u0438\u0438 \u0432\u0441\u0435\u0445 \u0442\u0440\u0435\u0445 \u0443 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044f \u0441\u043b\u043e\u0436\u0438\u0442\u0441\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435, \u043a\u0430\u043a \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441\u0430\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u0412 \u043f\u0435\u0440\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u044f \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u044e \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443 \u0437\u0430\u0434\u0430\u0447\u0438 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D1%80%D0%B0%D1%81%D0%BA%D1%80%D0%BE%D1%8F#:~:text=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%20%D1%80%D0%B0%D1%81%D0%BA%D1%80%D0%BE%D1%8F%20%E2%80%94%20%D1%8D%D1%82%D0%BE%20NP%2D%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F,%D0%B2%D0%BE%D0%B7%D0%BD%D0%B8%D0%BA%D0%B0%D0%B5%D1%82%20%D0%B2%D0%BE%20%D0%BC%D0%BD%D0%BE%D0%B3%D0%B8%D1%85%20%D0%BE%D0%B1%D0%BB%D0%B0%D1%81%D1%82%D1%8F%D1%85%20%D0%BF%D1%80%D0%BE%D0%BC%D1%8B%D1%88%D0%BB%D0%B5%D0%BD%D0%BD%D0%BE%D1%81%D1%82%D0%B8.\" rel=\"noopener noreferrer nofollow\">\u0440\u0430\u0441\u043a\u0440\u043e\u044f <\/a>\u0438 \u0434\u0432\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u044f (\u0432 \u043b\u043e\u0431 \u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432 \u0438\u043b\u0438 \u0448\u0430\u0431\u043b\u043e\u043d\u043e\u0432 \u0440\u0430\u0437\u0440\u0435\u0437\u043e\u0432), \u0432\u043e \u0432\u0442\u043e\u0440\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043e \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0441\u0430\u043c\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432, \u0430 \u0432 \u0442\u0440\u0435\u0442\u044c\u0435\u0439 &#8212; \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u0445, \u0447\u0442\u043e\u0431\u044b \u0443 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044f \u0441\u043b\u043e\u0436\u0438\u043b\u043e\u0441\u044c \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043e \u0448\u0438\u0440\u043e\u043a\u0438\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044f\u0445 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u043c\u0435\u0442\u043e\u0434\u0430. \u0422\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u043c\u0435\u0442\u043e\u0434\u0430 \u0431\u044b\u043b\u043e \u0432\u0437\u044f\u0442\u043e \u0438\u0437 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e <a href=\"https:\/\/www.cse.iitb.ac.in\/~mitra\/mtp\/seminar\/report\/colgen.pdf\" rel=\"noopener noreferrer nofollow\">\u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430<\/a>.  <\/p>\n<p>(\u0415\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u0435\u0441\u043b\u0438 \u043f\u0435\u0440\u0432\u0430\u044f \u0441\u0442\u0430\u0442\u044c\u044f \u0432 \u0441\u0435\u0440\u0438\u0438 \u043d\u0435 \u043f\u043e\u043d\u0440\u0430\u0432\u0438\u0442\u0441\u044f, \u0442\u043e \u044f \u043f\u0440\u0438\u043c\u0443 \u0441\u0432\u043e\u0435 \u0430\u0432\u0442\u043e\u0440\u0441\u043a\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 &#8212; \u0434\u0430\u043b\u0435\u0435 \u043d\u0435 \u043f\u0443\u0431\u043b\u0438\u043a\u043e\u0432\u0430\u0442\u044c, \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u043d\u0443\u0434\u043d\u043e\u0439 \u0438 \u043d\u0435\u043d\u0443\u0436\u043d\u043e\u0439 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u0432 \u0441\u0435\u0442\u0438.)<\/p>\n<p><em>    <\/em><strong><em>\u041f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u0437\u0430\u0434\u0430\u0447\u0438<\/em>:<\/strong> \u0415\u0441\u0442\u044c \u0444\u0438\u0440\u043c\u0430, \u043e\u043d\u0430 \u0437\u0430\u043a\u0443\u043f\u0430\u0435\u0442 \u0441 \u0437\u0430\u0432\u043e\u0434\u0430 \u043c\u0435\u0442\u0430\u043b\u043b\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0440\u0443\u043b\u043e\u043d\u044b  \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0439 \u0448\u0438\u0440\u0438\u043d\u044b, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 10 \u0434\u044e\u0439\u043c\u043e\u0432. \u00a0\u0421\u043e \u0441\u0442\u043e\u0440\u043e\u043d\u044b \u043f\u043e\u043a\u0443\u043f\u0430\u0442\u0435\u043b\u0435\u0439 \u043f\u0440\u0438\u0445\u043e\u0434\u044f\u0442 \u0437\u0430\u043a\u0430\u0437\u044b \u043d\u0430 \u043f\u0440\u043e\u0434\u0443\u043a\u0446\u0438\u044e \u0440\u0430\u0437\u043d\u043e\u0439 \u0448\u0438\u0440\u0438\u043d\u044b. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0440\u0438\u0445\u043e\u0434\u044f\u0442 \u0437\u0430\u043a\u0430\u0437\u044b \u043d\u0430 \u0440\u0443\u043b\u043e\u043d\u044b \u0441 \u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0448\u0438\u0440\u0438\u043d\u043e\u0439. \u0422\u0430\u043a \u043e\u0434\u043d\u043e\u0439 \u0444\u0438\u0440\u043c\u0435 \u043d\u0443\u0436\u043d\u0430 \u043e\u0431\u0440\u0435\u0437\u043a\u0430 \u044d\u0442\u0438\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0448\u0438\u0440\u0438\u043d\u043e\u0439 3 \u0434\u044e\u0439\u043c\u0430, \u0434\u0440\u0443\u0433\u043e\u0439 \u0444\u0438\u0440\u043c\u0435 \u043d\u0443\u0436\u043d\u044b \u043e\u0431\u0440\u0435\u0437\u043a\u0438 \u0432 5 \u0434\u044e\u0439\u043c\u043e\u0432, \u0442\u0440\u0435\u0442\u044c\u0435\u0439 &#8212; 6, \u0447\u0435\u0442\u0432\u0435\u0440\u0442\u043e\u0439 &#8212; 9. \u0426\u0435\u043b\u044c \u0444\u0438\u0440\u043c\u044b &#8212; \u043d\u0430\u0440\u0435\u0437\u043a\u0430 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u0437\u0430\u043a\u0430\u0437\u044b \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432. \u0414\u0430\u043d\u043d\u044b\u0435 \u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u0437\u0430\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0439 \u043f\u0440\u043e\u0434\u0443\u043a\u0446\u0438\u0438 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u044b \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0435 \u043d\u0438\u0436\u0435.  <\/p>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td>\n<p align=\"center\">\u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043a\u0430\u0437\u043e\u0432 <em>b<sub>i<\/sub><\/em><\/p>\n<\/td>\n<td>\n<p align=\"left\">\u0428\u0438\u0440\u0438\u043d\u0430 \u0437\u0430\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430 <em>w<sub>i <\/sub>, \u0434\u044e\u0439\u043c\u044b<\/em><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"center\">9<\/p>\n<\/td>\n<td>\n<p align=\"center\">3<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"center\">79<\/p>\n<\/td>\n<td>\n<p align=\"center\">5<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"center\">90<\/p>\n<\/td>\n<td>\n<p align=\"center\">6<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"center\">27<\/p>\n<\/td>\n<td>\n<p align=\"center\">9<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p> \u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0442\u0441\u044f \u0432 \u043a\u043b\u0430\u0441\u0441\u0435 Data: <\/p>\n<pre><code class=\"python\">@dataclass class Data:     '''\u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u0434\u043b\u044f \u043c\u043e\u0434\u0435\u043b\u0438.'''     # \u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0448\u0438\u0440\u0438\u043d\u0430 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432.     RAWS_WIDTH = 10     # \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043a\u0430\u0437\u043e\u0432 \u0432 \u0448\u0442\u0443\u043a\u0430\u0445 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0442\u0438\u043f\u0430 \u0440\u0443\u043b\u043e\u043d\u043e\u0432.     orders = [9, 79, 90, 27]     # \u0428\u0438\u0440\u0438\u043d\u0430 \u0437\u0430\u043a\u0430\u0437\u043e\u0432 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0442\u0438\u043f\u0430. \u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0435 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435.     # \u0422\u0430\u043a \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e 9 \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0448\u0438\u0440\u0438\u043d\u044b 3, 79 \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0448\u0438\u0440\u0438\u043d\u044b 5 \u0438 \u0442.\u0434.     order_sizes = [3, 5, 6, 9]     # \u0421\u043f\u0438\u0441\u043e\u043a \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432, \u043f\u043e \u043a\u0430\u043a\u0438\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043d\u0430\u0440\u0435\u0437\u0430\u043d \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0440\u0443\u043b\u043e\u043d.     # \u0422\u0430\u043a, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0430\u0442\u0442\u0435\u0440\u043d [1, 0, 1, 0] \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430 \u0448\u0438\u0440\u0438\u043d\u044b 10,     # \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0432\u044b\u0440\u0435\u0437\u0430\u043d \u0440\u0443\u043b\u043e\u043d \u0448\u0438\u0440\u0438\u043d\u044b 3 \u0438 \u0440\u0443\u043b\u043e\u043d \u0448\u0438\u0440\u0438\u043d\u044b 6.     patterns = [[0, 0, 0, 1],                 [0, 0, 1, 0],                 [1, 0, 1, 0],                   [0, 1, 0, 0],                 [0, 2, 0, 0],                 [1, 1, 0, 0],                 [1, 0, 0, 0],                 [2, 0, 0, 0],                 [3, 0, 0, 0]]     # \u041e\u0431\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043a\u0430\u0437\u043e\u0432.     RAWS_NUMBER = sum(orders)<\/code><\/pre>\n<p>    \u041d\u0430\u043f\u043e\u043c\u043d\u044e, \u0447\u0442\u043e \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441\u043c\u0435\u0448\u0430\u043d\u043d\u043e\u0433\u043e \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 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0437\u0430\u0434\u0430\u0442\u044c: <\/p>\n<p>\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong><em>\u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u043c\u043e\u0434\u0435\u043b\u0438<\/em><\/strong> \u2013 \u0442\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0430\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u0435\u0440\u0435\u0431\u0440\u0430\u0442\u044c \u0438 \u0432\u044b\u0431\u0440\u0430\u0442\u044c, \u043f\u0440\u0438 \u043a\u0430\u043a\u0438\u0445 \u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u0445 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442 \u043e\u043f\u0442\u0438\u043c\u0443\u043c\u0430, \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 &#8212; \u044d\u0442\u043e \u043a\u0430\u043a\u043e\u0439 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0440\u0443\u043b\u043e\u043d \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u0442\u044c \u0438 \u043a\u0430\u043a\u0438\u0435 \u0442\u0438\u043f\u044b \u0437\u0430\u043a\u0430\u0437\u043e\u0432 \u043e\u0442\u0442\u0443\u0434\u0430 \u0432\u044b\u0440\u0435\u0437\u0430\u0442\u044c. <\/p>\n<p>\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong><em>\u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f,<\/em><\/strong> \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u0443\u044e\u0449\u0438\u0435 \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u0438\u0435, \u0442\u0435\u0445\u043d\u0438\u0447\u0435\u0441\u043a\u0438\u0435, \u0437\u0430\u043a\u043e\u043d\u043e\u0434\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u044b, \u0432 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0443\u0441\u043b\u043e\u0432\u0438\u0435, \u0447\u0442\u043e \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u043e \u0432\u0441\u0435 \u0437\u0430\u043a\u0430\u0437\u044b.  <\/p>\n<p>\u00b7\u00a0\u00a0\u00a0    <strong><em>\u0446\u0435\u043b\u0435\u0432\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e<\/em><\/strong>, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c, \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u044d\u0442\u043e<br \/> \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u043d\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432. <\/p>\n<h2>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 1. \u041c\u043e\u0434\u0435\u043b\u044c \u041a\u0430\u043d\u0442\u043e\u0440\u043e\u0432\u0438\u0447\u0430. \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0432 \u043b\u043e\u0431.<\/h2>\n<p>\u0418\u043c\u043f\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0435 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438, \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u043c \u043c\u043e\u0434\u0435\u043b\u044c \u0438 \u043f\u0435\u0440\u0435\u043f\u0438\u0448\u0435\u043c \u0431\u0438\u0437\u043d\u0435\u0441 \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443 \u0437\u0430\u0434\u0430\u0447\u0438 \u0432 \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0432 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u0432\u0438\u0434\u0435, \u043f\u043e\u0442\u043e\u043c \u0432 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u043d\u043e\u043c.<\/p>\n<pre><code class=\"python\">import pulp import numpy as np import itertools as it from dataclasses import dataclass from collections import Counter<\/code><\/pre>\n<pre><code class=\"python\">#  \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043c\u043e\u0434\u0435\u043b\u0438. model = pulp.LpProblem('Kantorovich model', pulp.LpMinimize)<\/code><\/pre>\n<p>\u00b7\u00a0\u00a0<strong>1.<\/strong> <strong>\u041f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435<\/strong><\/p>\n<p>    \u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0432\u0441\u0435\u0433\u043e <em>K<\/em> \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b. \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u0432\u0435\u0434\u0435\u043d\u0430 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"y_{k}=\\left \\{   \\begin{array}{ccc}     &amp;1&amp;, \u0435\u0441\u043b\u0438   \\ \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \\  \u0440\u0443\u043b\u043e\u043d\\  \u0432\u044b\u0431\u0440\u0430\u043d\\  \u0434\u043b\u044f\\  \u0440\u0430\u0437\u0440\u0435\u0437\u0430; \\\\     &amp;0&amp;, \u0435\u0441\u043b\u0438   \\ \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \\  \u0440\u0443\u043b\u043e\u043d\\  \u043e\u0441\u0442\u0430\u0435\u0442\u0441\u044f\\  \u043d\u0435\\  \u0442\u0440\u043e\u043d\u0443\u0442.\\\\   \\end{array} \\right .\" alt=\"y_{k}=\\left \\{   \\begin{array}{ccc}     &amp;1&amp;, \u0435\u0441\u043b\u0438   \\ \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \\  \u0440\u0443\u043b\u043e\u043d\\  \u0432\u044b\u0431\u0440\u0430\u043d\\  \u0434\u043b\u044f\\  \u0440\u0430\u0437\u0440\u0435\u0437\u0430; \\\\     &amp;0&amp;, \u0435\u0441\u043b\u0438   \\ \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \\  \u0440\u0443\u043b\u043e\u043d\\  \u043e\u0441\u0442\u0430\u0435\u0442\u0441\u044f\\  \u043d\u0435\\  \u0442\u0440\u043e\u043d\u0443\u0442.\\\\   \\end{array} \\right .\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d01\/a9e\/6d6\/d01a9e6d63e4b4863baf6370a7cd55fb.svg\" width=\"418\" height=\"49\"\/><\/p>\n<p>    \u0427\u0442\u043e\u0431\u044b \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u0437\u0430\u043a\u0430\u0437\u044b, \u043d\u0430\u043c \u0442\u043e\u0447\u043d\u043e \u0445\u0432\u0430\u0442\u0438\u0442 <em>K<\/em> = 9 + 79 + 90 +27 = 215 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432, \u0435\u0441\u043b\u0438 \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0437\u0430\u043a\u0430\u0437\u0430 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0432\u044b\u0440\u0435\u0437\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u0440\u0443\u043b\u043e\u043d \u043e\u0434\u043d\u043e\u0433\u043e \u0442\u0438\u043f\u0430. \u0415\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u044d\u0442\u043e \u043d\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e, \u0442\u0430\u043a \u043a\u0430\u043a \u0441 \u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430 \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0440\u0435\u0437\u0430\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0437\u0430\u043a\u0430\u0437\u043e\u0432 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0442\u0438\u043f\u043e\u0432. \u0422\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435 \u0437\u0430\u0432\u0435\u0434\u0435\u043c \u0432\u0441\u0435 215 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u043f\u0443\u0441\u0442\u044c \u0438 \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0438\u0445 \u0447\u0430\u0441\u0442\u044c \u043e\u043a\u0430\u0436\u0435\u0442\u0441\u044f \u043d\u0443\u043b\u044f\u043c\u0438. \u0414\u043e\u0431\u0430\u0432\u0438\u043c \u044d\u0442\u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435:<\/p>\n<pre><code class=\"python\"># \u0417\u0430\u0434\u0430\u043d\u0438\u0435 \u0442\u0438\u043f\u0430 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 (\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0443\u043a\u0430\u0437\u0430\u0442\u044c \u0438\u0445 \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u043d\u0435\u043e\u0445\u043e\u0434\u0438\u043c\u0430  # \u0434\u043b\u044f \u043e\u0446\u0435\u043d\u043a\u0438 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 \u0440\u0435\u043b\u0430\u043a\u0441\u0430\u0446\u0438\u0438). #vars_type = pulp.LpContinuous vars_type = pulp.LpInteger  # \u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430. cuts_ids = range(data.RAWS_NUMBER) # \u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 y_{k}. cuts = pulp.LpVariable.dicts(\"raw_cut\", cuts_ids, lowBound=0, upBound=1, cat=vars_type)<\/code><\/pre>\n<p>\u0417\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x_{ik} \" alt=\"x_{ik} \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f13\/69c\/0a4\/f1369c0a48694f5a4b470d0bf54bf3a4.svg\" width=\"25\" height=\"15\"\/>\u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u043d\u0430, \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0442\u0438\u043f\u0430 <em><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i \\in I\" alt=\"i \\in I\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b01\/102\/3a8\/b011023a861a70c70fbd7a4fd8085205.svg\" width=\"40\" height=\"17\"\/><\/em>\u0432\u044b\u0440\u0435\u0437\u0430\u043d\u043d\u043e\u0433\u043e \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430 <em>k, \u0433\u0434\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"I\" alt=\"I\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/df6\/0d8\/13c\/df60d813cb5aa6aa87e0d18d7f420367.svg\" width=\"10\" height=\"17\"\/><\/em>\u043d\u0430\u0431\u043e\u0440 \u0432\u0441\u0435\u0445 \u0442\u0438\u043f\u043e\u0432 \u0440\u0443\u043b\u043e\u043d\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0442\u0440\u0435\u0431\u0443\u044e\u0442\u0441\u044f \u043f\u043e\u043a\u0443\u043f\u0430\u0442\u0435\u043b\u044f\u043c. \u0414\u043e\u0431\u0430\u0432\u0438\u043c \u044d\u0442\u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0432 \u043c\u043e\u0434\u0435\u043b\u044c:<\/p>\n<pre><code class=\"python\"># \u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430. cuts_ids = range(data.RAWS_NUMBER) order_types_ids = range(len(data.orders)) items_ids = list(it.product(order_types_ids, cuts_ids))  # \u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 x_{i,k}. items = pulp.LpVariable.dicts(\"item\", items_ids, lowBound=0, cat=vars_type)<\/code><\/pre>\n<h4>2. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f<\/h4>\n<p>\u0421\u0443\u043c\u043c\u0430 \u0432\u0441\u0435\u0445 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 x \u0434\u043e\u043b\u0436\u043d\u0430 \u0431\u044b\u0442\u044c \u043d\u0435 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0440\u0430\u0437\u043c\u0435\u0440 \u0437\u0430\u043a\u0430\u0437\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0442\u0438\u043f\u0430, \u0442\u043e \u0435\u0441\u0442\u044c \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u0437\u0430\u043a\u0430\u0437\u044b \u0432\u0441\u0435\u0445 \u0442\u0438\u043f\u043e\u0432:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\sum_{k=1}^{K}x_{ik} \\geq b_i, \\forall i \\in I\" alt=\"\\sum_{k=1}^{K}x_{ik} \\geq b_i, \\forall i \\in I\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b04\/519\/10e\/b0451910ebc9d8873805823e2693fb99.svg\" width=\"156\" height=\"60\"\/><\/p>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u044d\u0442\u043e\u0433\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0432 \u043c\u043e\u0434\u0435\u043b\u044c, \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043e \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c \u0432\u0438\u0434\u0435:<\/p>\n<pre><code class=\"python\"># \u041b\u044e\u0431\u043e\u0439 \u0437\u0430\u043a\u0430\u0437 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d. for t in order_types_ids:     model += pulp.LpConstraint(pulp.lpSum(items[t, c] for c in cuts_ids) >= data.orders[t],                                name=\"min_demand_{}\".format(t), sense=pulp.LpConstraintGE)<\/code><\/pre>\n<p>\u00a0<\/p>\n<p>\u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0435\u0441\u0442\u044c \u043f\u0440\u0430\u0432\u0438\u043b\u043e, \u0447\u0442\u043e \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430 \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u0431\u043e\u043b\u044c\u0448\u0435 \u0437\u0430\u043a\u0430\u0437\u043e\u0432, \u0447\u0435\u043c \u0435\u0433\u043e \u0434\u043b\u0438\u043d\u0430. \u042d\u0442\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043a\u0430\u0436\u0435\u0442\u0441\u044f \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b\u043c, \u043d\u043e \u0432 \u043c\u043e\u0434\u0435\u043b\u044c \u043e\u043d\u043e \u0442\u043e\u0436\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u043e:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\sum_{i=1}^{m}x_{ik}w_{i} \\leq y_{k}W, \\forall k \\in K\" alt=\"\\sum_{i=1}^{m}x_{ik}w_{i} \\leq y_{k}W, \\forall k \\in K\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/171\/8de\/750\/1718de750655e7532ea4770863e7906a.svg\" width=\"211\" height=\"57\"\/><\/p>\n<pre><code class=\"python\"># \u0420\u0443\u043b\u043e\u043d \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u043d \u043d\u0430 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0449\u0438\u0435 \u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u043f\u043e \u0448\u0438\u0440\u0438\u043d\u0435, \u0447\u0435\u043c \u0442\u043e\u0442 \u0440\u0443\u043b\u043e\u043d, \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0435\u0433\u043e \u0432\u044b\u0440\u0435\u0437\u0430\u043b\u0438. for c in cuts_ids:       model += pulp.LpConstraint(pulp.lpSum(data.order_sizes[t] * items[t, c]                                             for t in order_types_ids) &lt;= data.RAWS_WIDTH * cuts[c],                                  name=\"max_width_{}\".format(c), sense=pulp.LpConstraintLE)<\/code><\/pre>\n<p>\u0422\u0430\u043a, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0435\u0441\u043b\u0438 \u043d\u0435 \u0431\u044b\u043b \u0432\u044b\u0431\u0440\u0430\u043d \u0440\u0443\u043b\u043e\u043d \u043a \u0440\u0430\u0437\u0440\u0435\u0437\u0443 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"y_k=0\" alt=\"y_k=0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ea5\/ea7\/97a\/ea5ea797a60e8919932f0b240f0ec365.svg\" width=\"54\" height=\"19\"\/>, \u0442\u043e \u044d\u0442\u043e \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0432\u0441\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x_{ik}\" alt=\"x_{ik}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1ec\/b62\/9cd\/1ecb629cd6171ab1f29144955c49179f.svg\" width=\"25\" height=\"15\"\/><em><sub> <\/sub><\/em>\u0442\u043e\u0436\u0435 \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u0440\u0430\u0432\u043d\u044b \u043d\u0443\u043b\u044e, \u0442\u0430\u043a \u043a\u0430\u043a \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430  <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x_{1k}w_1+...+x_{mk}w_k \\leq y_k W =0\" alt=\"x_{1k}w_1+...+x_{mk}w_k \\leq y_k W =0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b75\/33d\/568\/b7533d568df5643bb4e336b4690e66bf.svg\" width=\"260\" height=\"20\"\/>, \u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x_{ik}\" alt=\"x_{ik}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b92\/8d2\/2c0\/b928d22c0f3dd4d232e0b6bf2a5e19fe.svg\" width=\"25\" height=\"15\"\/>\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"w_{k}\" alt=\"w_{k}\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/320\/358\/c92\/320358c92fa07201f660a0dfe8b0c454.svg\" width=\"23\" height=\"15\"\/>&#8212; \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435.<\/p>\n<p>\u00b7\u00a03.  <strong>\u0426\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f<\/strong><\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043d\u0430\u0448\u0435\u0439 \u0446\u0435\u043b\u044c &#8212; \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432:<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"z=\\sum_{k=1}^{K}y_{k} \\rightarrow min\" alt=\"z=\\sum_{k=1}^{K}y_{k} \\rightarrow min\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d17\/0d2\/8a8\/d170d28a877db78bd1caed7766289565.svg\" width=\"149\" height=\"60\"\/><\/p>\n<pre><code class=\"python\"># \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0432 \u043c\u043e\u0434\u0435\u043b\u044c \u0446\u0435\u043b\u0435\u0432\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e. model += pulp.lpSum([cuts[c] for c in cuts_ids])<\/code><\/pre>\n<p>\u0420\u0435\u0448\u0430\u0435\u043c \u0441\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 \u0438 \u0432\u044b\u0432\u043e\u0434\u0438\u043c \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<pre><code class=\"python\">model.solve()  used_patterns = [] for c in cuts_ids:     if cuts[c] >= 0.001:         used_patterns.append(tuple([items[t, c].varValue for t in order_types_ids])) print(\"\u0417\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 {}:\".format(model.objective.value())) print(\"\u041a\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043d\u0430\u0440\u0435\u0437\u0430\u043b\u0438\u0441\u044c \u0438\u0441\u043a\u043e\u0434\u043d\u044b\u0435 \u0440\u0443\u043b\u043e\u043d\u044b {}\".format(dict(Counter(used_patterns))))<\/code><\/pre>\n<p>\u0412 \u0442\u0435\u043a\u0443\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0446\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0440\u0430\u0432\u043d\u0430 157, \u0442\u043e \u0435\u0441\u0442\u044c \u0434\u043b\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0432\u0441\u0435\u0445 \u0437\u0430\u043a\u0430\u0437\u043e\u0432, \u043d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0441\u0442\u043e\u043b\u044c\u043a\u043e \u0448\u0442\u0443\u043a \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u043e, &#8212; \u0443\u0431\u0440\u0430\u0442\u044c \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u0435 \u043d\u0430 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0438  \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u0438\u043c\u043f\u043b\u0435\u043a\u0441 \u043c\u0435\u0442\u043e\u0434\u043e\u043c. \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0440\u0435\u043b\u0430\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 (\u0431\u0435\u0437 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0431\u044b\u043b\u0438 \u0446\u0435\u043b\u044b\u043c\u0438) \u0437\u0430\u0434\u0430\u0447\u0438 \u0440\u0430\u0432\u043d\u043e 120,5, \u0447\u0442\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u0434\u0430\u043b\u0435\u043a\u043e \u043e\u0442 \u043d\u0443\u0436\u043d\u043e\u0433\u043e \u043d\u0430\u043c \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f. \u041f\u0440\u0438 \u0434\u0440\u0443\u0433\u0438\u0445 \u0442\u0438\u043f\u0430\u0445 \u0437\u0430\u043a\u0430\u0437\u043e\u0432, \u044d\u0442\u0430 \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u043c\u043e\u0436\u0435\u0442 \u0438 \u0434\u0430\u043b\u044c\u0448\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0440\u0430\u0441\u0442\u0438. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0435\u0441\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0430 \u0431\u0443\u0434\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u043e\u0439, \u0442\u043e \u043f\u043e\u043b\u044c\u0437\u0443\u044f\u0441\u044c \u0442\u0435\u043a\u0443\u0449\u0438\u043c \u043c\u0435\u0442\u043e\u0434\u043e\u043c, \u043c\u044b \u0432 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0435 \u0435\u0435 \u043d\u0435 \u0441\u043c\u043e\u0436\u0435\u043c \u0440\u0435\u0448\u0438\u0442\u044c \u0438\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043e\u0447\u0435\u043d\u044c \u043f\u043b\u043e\u0445\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435.   <\/p>\n<p>\u041f\u043e\u043b\u043d\u044b\u0439 \u043a\u043e\u0434 \u043c\u043e\u0434\u0435\u043b\u0438 \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 <a href=\"https:\/\/github.com\/m-krasilnikov\/optimization\/blob\/main\/column_generation.py\" rel=\"noopener noreferrer nofollow\">\u0437\u0434\u0435\u0441\u044c<\/a>.<\/p>\n<h3>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 2. \u041c\u043e\u0434\u0435\u043b\u044c \u0413\u0438\u043b\u043c\u043e\u0440\u0430-\u0413\u043e\u043c\u043e\u0440\u0438. \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432 \u0440\u0430\u0437\u0440\u0435\u0437\u0430 (\u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432).<\/h3>\n<p>    \u0422\u0440\u044e\u043a \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0430 \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0432 \u0441\u043b\u0443\u0447\u0430\u0435, \u043a\u043e\u0433\u0434\u0430 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0432\u0441\u0435 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u044b \u043f\u043e \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043d\u0430\u0440\u0435\u0437\u0430\u043d \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0440\u0443\u043b\u043e\u043d, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445. \u041c\u0430\u0442\u0440\u0438\u0446\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"(a_1, a_2, ..., a_n) \" alt=\"(a_1, a_2, ..., a_n) \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ce0\/729\/2f3\/ce07292f3374a2e466832c181ef65ecc.svg\" width=\"125\" height=\"22\"\/>, \u0433\u0434\u0435 \u043a\u0430\u0436\u0434\u044b\u0439 \u0435\u0435 \u0441\u0442\u043e\u043b\u0431\u0435\u0446 \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u0443\u0435\u0442 \u043e\u0434\u0438\u043d \u043f\u0430\u0442\u0442\u0435\u0440\u043d \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u0432\u0441\u0435\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u0440\u0430\u0437\u0440\u0435\u0437\u0430 (\u043e\u0434\u0438\u043d \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0440\u0430\u0437\u0440\u0435\u0437\u0430 \u0440\u0443\u043b\u043e\u043d\u0430 &#8212; \u043e\u0434\u0438\u043d \u0441\u0442\u043e\u043b\u0431\u0435\u0446 \u044d\u0442\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b). \u0422\u0430\u043a \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0435\u0441\u043b\u0438 \u0443 \u043d\u0430\u0441 \u0437\u0430\u043a\u0430\u0437 \u0434\u043b\u0438\u043d\u044b (3, 5, 6, 9), \u0430 \u0448\u0438\u0440\u0438\u043d\u0430 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430 10, \u0442\u043e \u0435\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u0442\u044c \u043d\u0430 \u0434\u0432\u0430 \u043a\u0443\u0441\u043a\u0430, \u043e\u0434\u0438\u043d \u0448\u0438\u0440\u0438\u043d\u044b 3, \u0430 \u0434\u0440\u0443\u0433\u043e\u0439 \u0448\u0438\u0440\u0438\u043d\u044b 6. \u0410 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u043f\u0430\u0442\u0442\u0435\u0440\u043d \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u044f \u0431\u0443\u0434\u0435\u0442 (1, 0, 1, 0). \u0422\u0430\u043a \u043a\u0430\u043a \u043c\u044b \u0432\u0437\u044f\u043b\u0438 \u043f\u0435\u0440\u0432\u044b\u0439 \u0438 \u0442\u0440\u0435\u0442\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430 \u0441 \u0442\u0438\u043f\u0430\u043c\u0438 \u0437\u0430\u043a\u0430\u0437\u043e\u0432. \u041f\u0430\u0442\u0442\u0435\u0440\u043d\u044b \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u044f, \u0432 \u043d\u0430\u0448\u0435\u043c \u0443\u0447\u0435\u0431\u043d\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u044b \u043d\u0430 \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u043d\u0438\u0436\u0435: <\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/eb4\/4a4\/cd0\/eb44a4cd0ac9f4e140cf919e8d29e762.png\" width=\"1175\" height=\"385\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/eb4\/4a4\/cd0\/eb44a4cd0ac9f4e140cf919e8d29e762.png\"\/><\/figure>\n<p>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043d\u0430\u043b\u0438\u0447\u0438\u0435 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u043d\u0430\u0448\u0443 \u043c\u043e\u0434\u0435\u043b\u044c \u0432 \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u043c \u0432\u0438\u0434\u0435: \u00a0<\/p>\n<ol>\n<li>\n<p><strong>\u041f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435<\/strong> <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x_j\" alt=\"x_j\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/83e\/2a3\/664\/83e2a3664cea7e8f4bd48fa9a13aca9c.svg\" width=\"19\" height=\"17\"\/>&#8212; \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432 (\u0448\u0430\u0431\u043b\u043e\u043d\u043e\u0432 \u0440\u0430\u0437\u0440\u0435\u0437\u0430) <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"j\" alt=\"j\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e72\/c84\/b32\/e72c84b32589ce4b28f28e2beb323088.svg\" width=\"8\" height=\"19\"\/> , \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043d\u0443\u0436\u043d\u043e \u0432\u044b\u0431\u0440\u0430\u0442\u044c \u0438\u0437 \u0432\u0441\u0435\u0433\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0433\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"J\" alt=\"J\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b6b\/3ac\/7c3\/b6b3ac7c36d86745edc58d4d8290005b.svg\" width=\"12\" height=\"17\"\/> \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432.<\/p>\n<\/li>\n<li>\n<p><strong>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f.<\/strong><\/p>\n<p>\u0421\u0443\u043c\u043c\u0430 \u0432\u0441\u0435\u0445 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u043d\u044b\u0445 \u0440\u0430\u0437\u0440\u0435\u0437\u043e\u0432 \u043f\u043e \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u0430\u043c \u0434\u043e\u043b\u0436\u043d\u0430 \u0431\u044b\u0442\u044c \u043d\u0435 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0440\u0430\u0437\u043c\u0435\u0440 \u0437\u0430\u043a\u0430\u0437\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0442\u0438\u043f\u0430, \u0442\u043e \u0435\u0441\u0442\u044c \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u0437\u0430\u043a\u0430\u0437\u044b \u0432\u0441\u0435\u0445 \u0442\u0438\u043f\u043e\u0432:<\/p>\n<\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"\\sum_{j \\in J}a_{ij}x_{j} \\geq b_{i}, \\forall i \\in I\" alt=\"\\sum_{j \\in J}a_{ij}x_{j} \\geq b_{i}, \\forall i \\in I\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3fe\/e21\/260\/3fee21260a66719b15bfc148898a3a89.svg\" width=\"172\" height=\"47\"\/><\/p>\n<ol start=\"3\">\n<li>\n<p><strong>\u0426\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f<\/strong><\/p>\n<p>\u0426\u0435\u043b\u044c &#8212; \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u0445 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432, \u0442\u043e \u0435\u0441\u0442\u044c \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432.<\/p>\n<\/li>\n<\/ol>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula\" source=\"z_p= \\sum_{j \\in J}x_j \\rightarrow min \" alt=\"z_p= \\sum_{j \\in J}x_j \\rightarrow min \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0fb\/59b\/e7d\/0fb59be7d851ec8b1edff598d251e32c.svg\" width=\"158\" height=\"47\"\/><\/p>\n<p>\u041e\u0441\u043d\u043e\u0432\u043d\u044b\u043c \u043e\u0442\u043b\u0438\u0447\u0438\u0435\u043c \u043e\u0442 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0430, &#8212; \u0441\u0435\u0439\u0447\u0430\u0441 \u043c\u044b \u0438\u0449\u0435\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0445 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432. \u041a\u0430\u043a \u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0435, \u0443 \u043d\u0430\u0441 \u0432 \u043c\u043e\u0434\u0435\u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445. <\/p>\n<p>\u041a\u043e\u0434 \u043c\u043e\u0434\u0435\u043b\u0438: <\/p>\n<pre><code class=\"python\">model = pulp.LpProblem('Gilmore-Gomory model', pulp.LpMinimize)  # \u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445. patterns_ids = range(len(data.patterns)) order_types = range(len(data.orders))  # \u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u043c\u043e\u0434\u0435\u043b\u0438. pattern_vars = pulp.LpVariable.dicts('patterns', patterns_ids, lowBound=0, cat=vars_type)  # \u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u043f\u043e \u043e\u0431\u044f\u0437\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0432\u0441\u0435\u0445 \u0437\u0430\u043a\u0430\u0437\u043e\u0432 for t in order_types:     model += pulp.LpConstraint(         pulp.lpSum(np.multiply(pattern_vars[p], data.patterns[p])[t]                     for p in patterns_ids) >= data.orders[t],         sense=pulp.LpConstraintGE, name=\"min_demand_{}\".format(t))  # \u0414\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0432 \u043c\u043e\u0434\u0435\u043b\u044c, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0439 \u0434\u043b\u044f \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c\u044b\u0445 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432. model += (pulp.lpSum(pattern_vars[p] for p in patterns_ids)) model.solve()      used_patterns = {} for p in patterns_ids:     if pattern_vars[p].varValue >= 0.001:         used_patterns[tuple(data.patterns[p])] = pattern_vars[p].varValue  print(\"\u0417\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 {}:\".format(model.objective.value())) print(\"\u041a\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043d\u0430\u0440\u0435\u0437\u0430\u043b\u0438\u0441\u044c \u0438\u0441\u043a\u043e\u0434\u043d\u044b\u0435 \u0440\u0443\u043b\u043e\u043d\u044b {}\".format(dict(Counter(used_patterns))))<\/code><\/pre>\n<p>      \u0422\u0435\u043f\u0435\u0440\u044c \u0440\u0435\u043b\u0430\u043a\u0441\u0430\u0446\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043d\u0430\u043c \u0434\u0430\u0435\u0442 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435: <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x_1 =27\" alt=\"x_1 =27\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/601\/692\/c92\/601692c920c1b52353050f14c6a53067.svg\" width=\"65\" height=\"19\"\/>, \u0442\u043e \u0435\u0441\u0442\u044c \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0438\u0437 27 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0432\u044b\u0440\u0435\u0437\u0430\u0442\u044c 27 \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u043f\u043e 9 \u0434\u044e\u0439\u043c\u043e\u0432, <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x_2=27\" alt=\"x_2=27\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3de\/4c3\/2de\/3de4c32deeb6fb1b74a6dd11919378aa.svg\" width=\"65\" height=\"19\"\/>  ,\u0442\u043e \u0435\u0441\u0442\u044c, \u0438\u0437 27 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432, \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0432\u044b\u0440\u0435\u0437\u0430\u0442\u044c \u0440\u0443\u043b\u043e\u043d\u044b \u0448\u0438\u0440\u0438\u043d\u043e\u0439 6 \u0434\u044e\u0439\u043c\u043e\u0432, <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x_3 = 9\" alt=\"x_3 = 9\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/67b\/9cf\/a72\/67b9cfa7270e72c754acabba15f29f62.svg\" width=\"55\" height=\"19\"\/>, \u0438\u0437 9 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0432\u044b\u0440\u0435\u0437\u0430\u0442\u044c \u0438\u0437 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u044b 3 \u0438 6 \u0434\u044e\u0439\u043c\u043e\u0432,  <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x_5\" alt=\"x_5\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8ce\/d41\/db3\/8ced41db3e0c36464bd6f4080ba92de6.svg\" width=\"20\" height=\"15\"\/>= 39.5 \u0438 \u0438\u0437 39.5 \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0432\u044b\u0440\u0435\u0437\u0430\u0442\u044c \u043f\u043e \u0434\u0432\u0430 \u0440\u0443\u043b\u043e\u043d\u0430 \u043f\u043e 5 \u0434\u044e\u0439\u043c\u043e\u0432. \u0412\u0438\u0434\u043d\u043e, \u0447\u0442\u043e \u0446\u0435\u043b\u0435\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0432 \u044d\u0442\u043e\u0439 \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0435 \u0440\u0430\u0432\u043d\u043e 156.5, \u0438 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u043b\u0438\u0436\u0435 \u043a \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u043c\u0443 \u0440\u0435\u0448\u0435\u043d\u0438\u044e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0440\u0430\u0432\u043d\u043e 157. \u0418 \u043e\u043a\u0440\u0443\u0433\u043b\u044f\u044f  <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"x_5\" alt=\"x_5\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/145\/b18\/0af\/145b180af0795766870ff03bf850861f.svg\" width=\"20\" height=\"15\"\/>\u0434\u043e \u0431\u043b\u0438\u0436\u0430\u0439\u0448\u0435\u0433\u043e \u0446\u0435\u043b\u043e\u0433\u043e \u043c\u044b \u0442\u043e\u0447\u043d\u043e \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u043c \u0442\u043e\u0447\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438.<\/p>\n<p>    \u0415\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432 (\u0448\u0430\u0431\u043b\u043e\u043d\u043e\u0432) \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u0437\u0430\u0434\u0430\u0447\u0430\u0445 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0431\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c \u0432 \u0442\u0435\u043a\u0443\u0449\u0435\u0439, \u0438\u043b\u043b\u044e\u0441\u0442\u0440\u0430\u0442\u0438\u0432\u043d\u043e\u0439 \u0438 \u043c\u043e\u0436\u0435\u0442 \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0442\u044c \u0434\u0435\u0441\u044f\u0442\u043a\u043e\u0432 \u0438 \u0441\u043e\u0442\u0435\u043d \u043c\u0438\u043b\u043b\u0438\u043e\u043d\u043e\u0432. \u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e \u043d\u0435 \u044f\u0441\u043d\u043e, \u043a\u0430\u043a \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u044d\u0442\u0438 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u044b, \u0435\u0441\u043b\u0438 \u0438\u0445 \u043d\u0435\u0442 \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u0422\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u0432\u0438\u0442\u044c \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438 \u0441\u0442\u0430\u0440\u0442\u043e\u0432\u0430\u0442\u044c \u0432\u0441\u0435\u0433\u043e \u043b\u0438\u0448\u044c \u0441 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b\u0445 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432, \u0430 \u043f\u043e\u0442\u043e\u043c \u043a \u043d\u0438\u043c \u0443\u0436\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c, \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u0435 \u0448\u0430\u0431\u043b\u043e\u043d\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0431\u0443\u0434\u0443\u0442 \u0443\u043b\u0443\u0447\u0448\u0430\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u0435. \u041a\u0430\u043a \u044d\u0442\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u0442\u0441\u044f, &#8212; \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u043e\u043c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0438. <\/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\/articles\/733804\/\"> https:\/\/habr.com\/ru\/articles\/733804\/<\/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<p>     \u041d\u0435\u0434\u0430\u0432\u043d\u043e \u043d\u0430 \u0445\u0430\u0431\u0440\u0435 \u043c\u043d\u0435 \u043f\u043e\u043d\u0440\u0430\u0432\u0438\u043b\u0430\u0441\u044c \u0441\u0442\u0430\u0442\u044c\u044f  &#171;<a href=\"https:\/\/habr.com\/ru\/articles\/731006\/\" rel=\"noopener noreferrer nofollow\">\u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u0438 \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435 \u0432 PuLP: \u0437\u0430\u0434\u0430\u0447\u0430 \u043e \u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u0445<\/a>&#187; , \u0433\u0434\u0435 \u0430\u0432\u0442\u043e\u0440 \u0438, \u043a\u0430\u043a \u044f \u043f\u043e\u0442\u043e\u043c \u0443\u0437\u043d\u0430\u043b, \u043c\u043e\u0439 \u0437\u043d\u0430\u043a\u043e\u043c\u044b\u0439 \u0440\u0435\u0448\u0438\u043b \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439 \u043e \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438, \u0441 \u0446\u0435\u043b\u044c\u044e \u043f\u043e\u043f\u0443\u043b\u044f\u0440\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u044d\u0442\u043e \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u043e \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442\u044c \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0435\u0439 \u0441 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442\u0430\u043c\u0438, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u043c\u0438 \u0440\u0435\u0448\u0430\u0442\u044c \u0442\u0430\u043a\u043e\u0439 \u043a\u043b\u0430\u0441\u0441 \u0437\u0430\u0434\u0430\u0447, \u0438 \u043d\u0430\u0443\u0447\u0438\u0442\u044c \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044f \u0432\u0438\u0434\u0435\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u043c \u043c\u0438\u0440\u0435, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u043d\u0438\u043c\u0430\u0442\u044c, \u0433\u0434\u0435 \u043c\u043e\u0436\u0435\u0442 \u043e\u043a\u0430\u0437\u0430\u0442\u044c\u0441\u044f \u043f\u043e\u043b\u0435\u0437\u0435\u043d \u044d\u0442\u043e\u0442 \u0438\u043d\u0441\u0442\u0440\u0443\u043c\u0435\u043d\u0442. \u0422\u0430\u043a, \u0432 \u0441\u0432\u043e\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0430\u0432\u0442\u043e\u0440 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0440\u0435\u0441\u0443\u0440\u0441\u043e\u0432 \u043d\u0430 \u043f\u043e\u0442\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0435 \u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0432\u0435\u0440\u0445\u043d\u0435\u0443\u0440\u043e\u0432\u043d\u0435\u0432\u043e\u0439 \u043f\u0438\u0442\u043e\u043d\u043e\u0432\u0441\u043a\u043e\u0439 \u043e\u0431\u043e\u043b\u043e\u0447\u043a\u0438 <a href=\"https:\/\/pypi.org\/project\/PuLP\/\" rel=\"noopener noreferrer nofollow\"><strong><em>pulp<\/em><\/strong><\/a> \u0441 \u043f\u043e\u0434\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435\u043c \u0441\u043e\u043b\u0432\u0435\u0440\u0430 <a href=\"https:\/\/github.com\/coin-or\/Cbc\" rel=\"noopener noreferrer nofollow\"><strong><em>cbc<\/em><\/strong><\/a> \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0441\u0430\u043c\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441\u043c\u0435\u0448\u0430\u043d\u043d\u043e\u0433\u043e \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. <\/p>\n<p>    \u041c\u043d\u0435 \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u043d\u0440\u0430\u0432\u0438\u043b\u0441\u044f \u0435\u0433\u043e \u0438\u0434\u0435\u044f, \u0432\u0435\u0434\u044c \u0442\u0430\u043a\u043e\u0439 \u043d\u0430\u0431\u043e\u0440 \u0441\u0442\u0430\u0442\u0435\u0439 \u043c\u043e\u0436\u0435\u0442 \u0440\u0430\u0441\u0448\u0438\u0440\u0438\u0442\u044c \u043a\u0440\u0443\u0433\u043e\u0437\u043e\u0440 \u043b\u044e\u0434\u0435\u0439 \u0438\u0437 \u0440\u0430\u0437\u043d\u044b\u0445 \u043e\u0431\u043b\u0430\u0441\u0442\u0435\u0439 &#8212; \u0443\u0447\u0435\u043d\u044b\u0445 \u043f\u043e \u0434\u0430\u043d\u043d\u044b\u043c, \u0431\u0438\u0437\u043d\u0435\u0441-\u0430\u043d\u0430\u043b\u0438\u0442\u0438\u043a\u043e\u0432, \u0430\u0440\u0445\u0438\u0442\u0435\u043a\u0442\u043e\u0440\u043e\u0432 \u0438 \u0432\u0441\u0435\u0445-\u0432\u0441\u0435\u0445-\u0432\u0441\u0435\u0445. \u041a\u0430\u043a \u0438\u0442\u043e\u0433, \u043e\u043d\u0430 \u043c\u0435\u043d\u044f \u043c\u043e\u0442\u0438\u0432\u0438\u0440\u043e\u0432\u0430\u043b\u0430 \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u0441\u0435\u0440\u0438\u044e \u0441\u0442\u0430\u0442\u0435\u0439 \u043e \u043c\u0435\u0442\u043e\u0434\u0430\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447 \u0441 \u0431\u043e\u043b\u044c\u0448\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u044c\u044e \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0441\u043f\u0435\u0446\u0438\u0444\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0439 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0438. \u0415\u0441\u043b\u0438 \u0441\u0442\u0430\u0442\u044c\u0438 \u0431\u0443\u0434\u0443\u0442 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044e, \u0442\u043e \u0434\u043b\u044f \u0443\u0434\u043e\u0431\u0441\u0442\u0432\u0430 \u0432\u043e\u0441\u043f\u0440\u0438\u044f\u0442\u0438\u044f \u044f \u0442\u0430\u043a\u0436\u0435 \u0431\u0443\u0434\u0443 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u0438\u0442\u043e\u043d\u043e\u0432\u0441\u043a\u0443\u044e \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0443 <strong><em>pulp<\/em><\/strong> \u0434\u043b\u044f \u043c\u043e\u0434\u0435\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f.<\/p>\n<p>    <strong><em>\u0422\u0435\u043f\u0435\u0440\u044c \u043a \u0438\u0441\u0442\u043e\u043a\u0430\u043c \u0437\u0430\u0434\u0430\u0447\u0438:<\/em><\/strong> \u0447\u0430\u0441\u0442\u043e, \u0447\u0442\u043e\u0431\u044b \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0430\u044f \u043c\u043e\u0434\u0435\u043b\u044c \u0431\u044b\u043b\u0430 \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u043c\u0430 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u043e\u043c \u0441\u0435\u043a\u0442\u043e\u0440\u0435, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043e\u0447\u0435\u043d\u044c \u043c\u043d\u043e\u0433\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u0439 \u0438 \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445. \u00a0\u0412\u0440\u0435\u043c\u0435\u043d\u0430\u043c\u0438 \u0437\u0430\u0434\u0430\u0447\u0430 \u0432 \u043b\u043e\u0431 \u043c\u043e\u0436\u0435\u0442 \u0438 \u043d\u0435 \u0440\u0435\u0448\u0438\u0442\u044c\u0441\u044f, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0431\u044b\u043b\u0438 \u043f\u0440\u0438\u0434\u0443\u043c\u0430\u043d\u044b \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u0442\u0440\u044e\u043a\u0438. \u041e\u0434\u0438\u043d \u0438\u0437 \u043d\u0438\u0445 &#8212; \u043c\u0435\u0442\u043e\u0434  \u00ab\u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432\u00bb   (Column generation). <\/p>\n<p>    \u041c\u0430\u0442\u0435\u0440\u0438\u0430\u043b \u0441 \u0434\u0435\u0442\u0430\u043b\u044f\u043c\u0438 \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043a\u0430\u0436\u0435\u0442\u0441\u044f \u0432\u0435\u0441\u044c\u043c\u0430 \u043e\u0431\u044a\u0435\u043c\u043d\u044b\u043c, \u0438, \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u043f\u0435\u0440\u0435\u043d\u0430\u0441\u044b\u0449\u0430\u0442\u044c \u0442\u0435\u043a\u0443\u0449\u0443\u044e \u0441\u0442\u0430\u0442\u044c\u044e, \u044f \u0440\u0435\u0448\u0438\u043b \u0440\u0430\u0437\u0431\u0438\u0442\u044c \u0435\u0435 \u043d\u0430 \u0442\u0440\u0438 \u0447\u0430\u0441\u0442\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435, \u043f\u043e \u0441\u0443\u0442\u0438, \u043c\u043e\u0436\u043d\u043e \u0447\u0438\u0442\u0430\u0442\u044c \u043d\u0435\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e, \u043d\u043e \u043f\u0440\u0438 \u043f\u0440\u043e\u0447\u0442\u0435\u043d\u0438\u0438 \u0432\u0441\u0435\u0445 \u0442\u0440\u0435\u0445 \u0443 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044f \u0441\u043b\u043e\u0436\u0438\u0442\u0441\u044f \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0438\u0435, \u043a\u0430\u043a \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0441\u0430\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u0412 \u043f\u0435\u0440\u0432\u043e\u0439 \u0447\u0430\u0441\u0442\u0438 \u044f \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u044e \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443 \u0437\u0430\u0434\u0430\u0447\u0438 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D1%80%D0%B0%D1%81%D0%BA%D1%80%D0%BE%D1%8F#:~:text=%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0%20%D1%80%D0%B0%D1%81%D0%BA%D1%80%D0%BE%D1%8F%20%E2%80%94%20%D1%8D%D1%82%D0%BE%20NP%2D%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F,%D0%B2%D0%BE%D0%B7%D0%BD%D0%B8%D0%BA%D0%B0%D0%B5%D1%82%20%D0%B2%D0%BE%20%D0%BC%D0%BD%D0%BE%D0%B3%D0%B8%D1%85%20%D0%BE%D0%B1%D0%BB%D0%B0%D1%81%D1%82%D1%8F%D1%85%20%D0%BF%D1%80%D0%BE%D0%BC%D1%8B%D1%88%D0%BB%D0%B5%D0%BD%D0%BD%D0%BE%D1%81%D1%82%D0%B8.\" rel=\"noopener noreferrer nofollow\">\u0440\u0430\u0441\u043a\u0440\u043e\u044f <\/a>\u0438 \u0434\u0432\u0430 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0440\u0435\u0448\u0435\u043d\u0438\u044f (\u0432 \u043b\u043e\u0431 \u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432 \u0438\u043b\u0438 \u0448\u0430\u0431\u043b\u043e\u043d\u043e\u0432 \u0440\u0430\u0437\u0440\u0435\u0437\u043e\u0432), \u0432\u043e \u0432\u0442\u043e\u0440\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0431\u0443\u0434\u0435\u0442 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u043d\u043e \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0441\u0430\u043c\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0433\u0435\u043d\u0435\u0440\u0430\u0446\u0438\u0438 \u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432, \u0430 \u0432 \u0442\u0440\u0435\u0442\u044c\u0435\u0439 &#8212; \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043d\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u0445, \u0447\u0442\u043e\u0431\u044b \u0443 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044f \u0441\u043b\u043e\u0436\u0438\u043b\u043e\u0441\u044c \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u0435 \u043e \u0448\u0438\u0440\u043e\u043a\u0438\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044f\u0445 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u043c\u0435\u0442\u043e\u0434\u0430. \u0422\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u043c\u0435\u0442\u043e\u0434\u0430 \u0431\u044b\u043b\u043e \u0432\u0437\u044f\u0442\u043e \u0438\u0437 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e <a href=\"https:\/\/www.cse.iitb.ac.in\/~mitra\/mtp\/seminar\/report\/colgen.pdf\" rel=\"noopener noreferrer nofollow\">\u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u0430<\/a>.  <\/p>\n<p>(\u0415\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u0435\u0441\u043b\u0438 \u043f\u0435\u0440\u0432\u0430\u044f \u0441\u0442\u0430\u0442\u044c\u044f \u0432 \u0441\u0435\u0440\u0438\u0438 \u043d\u0435 \u043f\u043e\u043d\u0440\u0430\u0432\u0438\u0442\u0441\u044f, \u0442\u043e \u044f \u043f\u0440\u0438\u043c\u0443 \u0441\u0432\u043e\u0435 \u0430\u0432\u0442\u043e\u0440\u0441\u043a\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 &#8212; \u0434\u0430\u043b\u0435\u0435 \u043d\u0435 \u043f\u0443\u0431\u043b\u0438\u043a\u043e\u0432\u0430\u0442\u044c, \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u043d\u0443\u0434\u043d\u043e\u0439 \u0438 \u043d\u0435\u043d\u0443\u0436\u043d\u043e\u0439 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u0432 \u0441\u0435\u0442\u0438.)<\/p>\n<p><em>    <\/em><strong><em>\u041f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0430 \u0437\u0430\u0434\u0430\u0447\u0438<\/em>:<\/strong> \u0415\u0441\u0442\u044c \u0444\u0438\u0440\u043c\u0430, \u043e\u043d\u0430 \u0437\u0430\u043a\u0443\u043f\u0430\u0435\u0442 \u0441 \u0437\u0430\u0432\u043e\u0434\u0430 \u043c\u0435\u0442\u0430\u043b\u043b\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u0440\u0443\u043b\u043e\u043d\u044b  \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0439 \u0448\u0438\u0440\u0438\u043d\u044b, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440 10 \u0434\u044e\u0439\u043c\u043e\u0432. \u00a0\u0421\u043e \u0441\u0442\u043e\u0440\u043e\u043d\u044b \u043f\u043e\u043a\u0443\u043f\u0430\u0442\u0435\u043b\u0435\u0439 \u043f\u0440\u0438\u0445\u043e\u0434\u044f\u0442 \u0437\u0430\u043a\u0430\u0437\u044b \u043d\u0430 \u043f\u0440\u043e\u0434\u0443\u043a\u0446\u0438\u044e \u0440\u0430\u0437\u043d\u043e\u0439 \u0448\u0438\u0440\u0438\u043d\u044b. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0440\u0438\u0445\u043e\u0434\u044f\u0442 \u0437\u0430\u043a\u0430\u0437\u044b \u043d\u0430 \u0440\u0443\u043b\u043e\u043d\u044b \u0441 \u043c\u0435\u043d\u044c\u0448\u0435\u0439 \u0448\u0438\u0440\u0438\u043d\u043e\u0439. \u0422\u0430\u043a \u043e\u0434\u043d\u043e\u0439 \u0444\u0438\u0440\u043c\u0435 \u043d\u0443\u0436\u043d\u0430 \u043e\u0431\u0440\u0435\u0437\u043a\u0430 \u044d\u0442\u0438\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0448\u0438\u0440\u0438\u043d\u043e\u0439 3 \u0434\u044e\u0439\u043c\u0430, \u0434\u0440\u0443\u0433\u043e\u0439 \u0444\u0438\u0440\u043c\u0435 \u043d\u0443\u0436\u043d\u044b \u043e\u0431\u0440\u0435\u0437\u043a\u0438 \u0432 5 \u0434\u044e\u0439\u043c\u043e\u0432, \u0442\u0440\u0435\u0442\u044c\u0435\u0439 &#8212; 6, \u0447\u0435\u0442\u0432\u0435\u0440\u0442\u043e\u0439 &#8212; 9. \u0426\u0435\u043b\u044c \u0444\u0438\u0440\u043c\u044b &#8212; \u043d\u0430\u0440\u0435\u0437\u043a\u0430 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u0437\u0430\u043a\u0430\u0437\u044b \u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043d\u0430\u0438\u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432. \u0414\u0430\u043d\u043d\u044b\u0435 \u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u0437\u0430\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0439 \u043f\u0440\u043e\u0434\u0443\u043a\u0446\u0438\u0438 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u044b \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0435 \u043d\u0438\u0436\u0435.  <\/p>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td>\n<p align=\"center\">\u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043a\u0430\u0437\u043e\u0432 <em>b<sub>i<\/sub><\/em><\/p>\n<\/td>\n<td>\n<p align=\"left\">\u0428\u0438\u0440\u0438\u043d\u0430 \u0437\u0430\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430 <em>w<sub>i <\/sub>, \u0434\u044e\u0439\u043c\u044b<\/em><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"center\">9<\/p>\n<\/td>\n<td>\n<p align=\"center\">3<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"center\">79<\/p>\n<\/td>\n<td>\n<p align=\"center\">5<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"center\">90<\/p>\n<\/td>\n<td>\n<p align=\"center\">6<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"center\">27<\/p>\n<\/td>\n<td>\n<p align=\"center\">9<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p> \u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0442\u0441\u044f \u0432 \u043a\u043b\u0430\u0441\u0441\u0435 Data: <\/p>\n<pre><code class=\"python\">@dataclass class Data:     '''\u0418\u0441\u0445\u043e\u0434\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 \u0434\u043b\u044f \u043c\u043e\u0434\u0435\u043b\u0438.'''     # \u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0448\u0438\u0440\u0438\u043d\u0430 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432.     RAWS_WIDTH = 10     # \u041a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043a\u0430\u0437\u043e\u0432 \u0432 \u0448\u0442\u0443\u043a\u0430\u0445 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0442\u0438\u043f\u0430 \u0440\u0443\u043b\u043e\u043d\u043e\u0432.     orders = [9, 79, 90, 27]     # \u0428\u0438\u0440\u0438\u043d\u0430 \u0437\u0430\u043a\u0430\u0437\u043e\u0432 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0442\u0438\u043f\u0430. \u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0435 \u043f\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0443 \u0432 \u0441\u043f\u0438\u0441\u043a\u0435.     # \u0422\u0430\u043a \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e 9 \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0448\u0438\u0440\u0438\u043d\u044b 3, 79 \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0448\u0438\u0440\u0438\u043d\u044b 5 \u0438 \u0442.\u0434.     order_sizes = [3, 5, 6, 9]     # \u0421\u043f\u0438\u0441\u043e\u043a \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432, \u043f\u043e \u043a\u0430\u043a\u0438\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043d\u0430\u0440\u0435\u0437\u0430\u043d \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0440\u0443\u043b\u043e\u043d.     # \u0422\u0430\u043a, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0430\u0442\u0442\u0435\u0440\u043d [1, 0, 1, 0] \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430 \u0448\u0438\u0440\u0438\u043d\u044b 10,     # \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0432\u044b\u0440\u0435\u0437\u0430\u043d \u0440\u0443\u043b\u043e\u043d \u0448\u0438\u0440\u0438\u043d\u044b 3 \u0438 \u0440\u0443\u043b\u043e\u043d \u0448\u0438\u0440\u0438\u043d\u044b 6.     patterns = [[0, 0, 0, 1],                 [0, 0, 1, 0],                 [1, 0, 1, 0],                   [0, 1, 0, 0],                 [0, 2, 0, 0],                 [1, 1, 0, 0],                 [1, 0, 0, 0],                 [2, 0, 0, 0],                 [3, 0, 0, 0]]     # \u041e\u0431\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043a\u0430\u0437\u043e\u0432.     RAWS_NUMBER = sum(orders)<\/code><\/pre>\n<p>    \u041d\u0430\u043f\u043e\u043c\u043d\u044e, \u0447\u0442\u043e \u0434\u043b\u044f \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0438 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441\u043c\u0435\u0448\u0430\u043d\u043d\u043e\u0433\u043e \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 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0437\u0430\u0434\u0430\u0442\u044c: <\/p>\n<p>\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong><em>\u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u043c\u043e\u0434\u0435\u043b\u0438<\/em><\/strong> \u2013 \u0442\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0430\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u0435\u0440\u0435\u0431\u0440\u0430\u0442\u044c \u0438 \u0432\u044b\u0431\u0440\u0430\u0442\u044c, \u043f\u0440\u0438 \u043a\u0430\u043a\u0438\u0445 \u0438\u0445 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u0445 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u0434\u043e\u0441\u0442\u0438\u0433\u0430\u0435\u0442 \u043e\u043f\u0442\u0438\u043c\u0443\u043c\u0430, \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 &#8212; \u044d\u0442\u043e \u043a\u0430\u043a\u043e\u0439 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0440\u0443\u043b\u043e\u043d \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u0442\u044c \u0438 \u043a\u0430\u043a\u0438\u0435 \u0442\u0438\u043f\u044b \u0437\u0430\u043a\u0430\u0437\u043e\u0432 \u043e\u0442\u0442\u0443\u0434\u0430 \u0432\u044b\u0440\u0435\u0437\u0430\u0442\u044c. <\/p>\n<p>\u00b7\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 <strong><em>\u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f,<\/em><\/strong> \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u0443\u044e\u0449\u0438\u0435 \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u0438\u0435, \u0442\u0435\u0445\u043d\u0438\u0447\u0435\u0441\u043a\u0438\u0435, \u0437\u0430\u043a\u043e\u043d\u043e\u0434\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0443\u0441\u043b\u043e\u0432\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u044b, \u0432 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0443\u0441\u043b\u043e\u0432\u0438\u0435, \u0447\u0442\u043e \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0430\u0431\u0441\u043e\u043b\u044e\u0442\u043d\u043e \u0432\u0441\u0435 \u0437\u0430\u043a\u0430\u0437\u044b.  <\/p>\n<p>\u00b7\u00a0\u00a0\u00a0    <strong><em>\u0446\u0435\u043b\u0435\u0432\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e<\/em><\/strong>, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c, \u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u044d\u0442\u043e<br \/> \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u043d\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432. <\/p>\n<h2>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 1. \u041c\u043e\u0434\u0435\u043b\u044c \u041a\u0430\u043d\u0442\u043e\u0440\u043e\u0432\u0438\u0447\u0430. \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0432 \u043b\u043e\u0431.<\/h2>\n<p>\u0418\u043c\u043f\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0435 \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0438, \u0438\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0438\u0440\u0443\u0435\u043c \u043c\u043e\u0434\u0435\u043b\u044c \u0438 \u043f\u0435\u0440\u0435\u043f\u0438\u0448\u0435\u043c \u0431\u0438\u0437\u043d\u0435\u0441 \u043f\u043e\u0441\u0442\u0430\u043d\u043e\u0432\u043a\u0443 \u0437\u0430\u0434\u0430\u0447\u0438 \u0432 \u0441\u043d\u0430\u0447\u0430\u043b\u0430 \u0432 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u0432\u0438\u0434\u0435, \u043f\u043e\u0442\u043e\u043c \u0432 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u043d\u043e\u043c.<\/p>\n<pre><code class=\"python\">import pulp import numpy as np import itertools as it from dataclasses import dataclass from collections import Counter<\/code><\/pre>\n<pre><code class=\"python\">#  \u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f \u043c\u043e\u0434\u0435\u043b\u0438. model = pulp.LpProblem('Kantorovich model', pulp.LpMinimize)<\/code><\/pre>\n<p>\u00b7\u00a0\u00a0<strong>1.<\/strong> <strong>\u041f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435<\/strong><\/p>\n<p>    \u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u0432\u0441\u0435\u0433\u043e <em>K<\/em> \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b. \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430 \u0431\u0443\u0434\u0435\u0442 \u0437\u0430\u0432\u0435\u0434\u0435\u043d\u0430 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f:<\/p>\n<\/p>\n<p>    \u0427\u0442\u043e\u0431\u044b \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u0437\u0430\u043a\u0430\u0437\u044b, \u043d\u0430\u043c \u0442\u043e\u0447\u043d\u043e \u0445\u0432\u0430\u0442\u0438\u0442 <em>K<\/em> = 9 + 79 + 90 +27 = 215 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432, \u0435\u0441\u043b\u0438 \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0437\u0430\u043a\u0430\u0437\u0430 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0432\u044b\u0440\u0435\u0437\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u0440\u0443\u043b\u043e\u043d \u043e\u0434\u043d\u043e\u0433\u043e \u0442\u0438\u043f\u0430. \u0415\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u044d\u0442\u043e \u043d\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u043e, \u0442\u0430\u043a \u043a\u0430\u043a \u0441 \u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430 \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0440\u0435\u0437\u0430\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0437\u0430\u043a\u0430\u0437\u043e\u0432 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0445 \u0442\u0438\u043f\u043e\u0432. \u0422\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435 \u0437\u0430\u0432\u0435\u0434\u0435\u043c \u0432\u0441\u0435 215 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u043f\u0443\u0441\u0442\u044c \u0438 \u0432 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0438\u0445 \u0447\u0430\u0441\u0442\u044c \u043e\u043a\u0430\u0436\u0435\u0442\u0441\u044f \u043d\u0443\u043b\u044f\u043c\u0438. \u0414\u043e\u0431\u0430\u0432\u0438\u043c \u044d\u0442\u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435:<\/p>\n<pre><code class=\"python\"># \u0417\u0430\u0434\u0430\u043d\u0438\u0435 \u0442\u0438\u043f\u0430 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 (\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0443\u043a\u0430\u0437\u0430\u0442\u044c \u0438\u0445 \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u043d\u0435\u043e\u0445\u043e\u0434\u0438\u043c\u0430  # \u0434\u043b\u044f \u043e\u0446\u0435\u043d\u043a\u0438 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0439 \u0440\u0435\u043b\u0430\u043a\u0441\u0430\u0446\u0438\u0438). #vars_type = pulp.LpContinuous vars_type = pulp.LpInteger  # \u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430. cuts_ids = range(data.RAWS_NUMBER) # \u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 y_{k}. cuts = pulp.LpVariable.dicts(\"raw_cut\", cuts_ids, lowBound=0, upBound=1, cat=vars_type)<\/code><\/pre>\n<p>\u0417\u0430 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0432\u043d\u0430, \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0443 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432 \u0442\u0438\u043f\u0430 <em><\/em>\u0432\u044b\u0440\u0435\u0437\u0430\u043d\u043d\u043e\u0433\u043e \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430 <em>k, \u0433\u0434\u0435 <\/em>\u043d\u0430\u0431\u043e\u0440 \u0432\u0441\u0435\u0445 \u0442\u0438\u043f\u043e\u0432 \u0440\u0443\u043b\u043e\u043d\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0442\u0440\u0435\u0431\u0443\u044e\u0442\u0441\u044f \u043f\u043e\u043a\u0443\u043f\u0430\u0442\u0435\u043b\u044f\u043c. \u0414\u043e\u0431\u0430\u0432\u0438\u043c \u044d\u0442\u0438 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0432 \u043c\u043e\u0434\u0435\u043b\u044c:<\/p>\n<pre><code class=\"python\"># \u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 \u0434\u043b\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430. cuts_ids = range(data.RAWS_NUMBER) order_types_ids = range(len(data.orders)) items_ids = list(it.product(order_types_ids, cuts_ids))  # \u0421\u043e\u0437\u0434\u0430\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0445 x_{i,k}. items = pulp.LpVariable.dicts(\"item\", items_ids, lowBound=0, cat=vars_type)<\/code><\/pre>\n<h4>2. \u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f<\/h4>\n<p>\u0421\u0443\u043c\u043c\u0430 \u0432\u0441\u0435\u0445 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 x \u0434\u043e\u043b\u0436\u043d\u0430 \u0431\u044b\u0442\u044c \u043d\u0435 \u043c\u0435\u043d\u044c\u0448\u0435, \u0447\u0435\u043c \u0440\u0430\u0437\u043c\u0435\u0440 \u0437\u0430\u043a\u0430\u0437\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0442\u0438\u043f\u0430, \u0442\u043e \u0435\u0441\u0442\u044c \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0432\u0441\u0435 \u0437\u0430\u043a\u0430\u0437\u044b \u0432\u0441\u0435\u0445 \u0442\u0438\u043f\u043e\u0432:<\/p>\n<p>\u0414\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u044d\u0442\u043e\u0433\u043e \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f \u0432 \u043c\u043e\u0434\u0435\u043b\u044c, \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043d\u043e \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c \u0432\u0438\u0434\u0435:<\/p>\n<pre><code class=\"python\"># \u041b\u044e\u0431\u043e\u0439 \u0437\u0430\u043a\u0430\u0437 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d. for t in order_types_ids:     model += pulp.LpConstraint(pulp.lpSum(items[t, c] for c in cuts_ids) >= data.orders[t],                                name=\"min_demand_{}\".format(t), sense=pulp.LpConstraintGE)<\/code><\/pre>\n<p>\u00a0<\/p>\n<p>\u041a\u0440\u043e\u043c\u0435 \u0442\u043e\u0433\u043e, \u0435\u0441\u0442\u044c \u043f\u0440\u0430\u0432\u0438\u043b\u043e, \u0447\u0442\u043e \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430 \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u0431\u043e\u043b\u044c\u0448\u0435 \u0437\u0430\u043a\u0430\u0437\u043e\u0432, \u0447\u0435\u043c \u0435\u0433\u043e \u0434\u043b\u0438\u043d\u0430. \u042d\u0442\u043e \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043a\u0430\u0436\u0435\u0442\u0441\u044f \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u044b\u043c, \u043d\u043e \u0432 \u043c\u043e\u0434\u0435\u043b\u044c \u043e\u043d\u043e \u0442\u043e\u0436\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u043e:<\/p>\n<pre><code class=\"python\"># \u0420\u0443\u043b\u043e\u043d \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u043d \u043d\u0430 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0449\u0438\u0435 \u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u043f\u043e \u0448\u0438\u0440\u0438\u043d\u0435, \u0447\u0435\u043c \u0442\u043e\u0442 \u0440\u0443\u043b\u043e\u043d, \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0435\u0433\u043e \u0432\u044b\u0440\u0435\u0437\u0430\u043b\u0438. for c in cuts_ids:       model += pulp.LpConstraint(pulp.lpSum(data.order_sizes[t] * items[t, c]                                             for t in order_types_ids) &lt;= data.RAWS_WIDTH * cuts[c],                                  name=\"max_width_{}\".format(c), sense=pulp.LpConstraintLE)<\/code><\/pre>\n<p>\u0422\u0430\u043a, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0435\u0441\u043b\u0438 \u043d\u0435 \u0431\u044b\u043b \u0432\u044b\u0431\u0440\u0430\u043d \u0440\u0443\u043b\u043e\u043d \u043a \u0440\u0430\u0437\u0440\u0435\u0437\u0443 , \u0442\u043e \u044d\u0442\u043e \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0432\u0441\u0435 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 <em><sub> <\/sub><\/em>\u0442\u043e\u0436\u0435 \u0434\u043e\u043b\u0436\u043d\u044b \u0431\u044b\u0442\u044c \u0440\u0430\u0432\u043d\u044b \u043d\u0443\u043b\u044e, \u0442\u0430\u043a \u043a\u0430\u043a \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430  , \u0430 \u0438 &#8212; \u043f\u043e\u043b\u043e\u0436\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435.<\/p>\n<p>\u00b7\u00a03.  <strong>\u0426\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f<\/strong><\/p>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u043d\u0430\u0448\u0435\u0439 \u0446\u0435\u043b\u044c &#8212; \u043c\u0438\u043d\u0438\u043c\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432:<\/p>\n<pre><code class=\"python\"># \u0414\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0432 \u043c\u043e\u0434\u0435\u043b\u044c \u0446\u0435\u043b\u0435\u0432\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e. model += pulp.lpSum([cuts[c] for c in cuts_ids])<\/code><\/pre>\n<p>\u0420\u0435\u0448\u0430\u0435\u043c \u0441\u0444\u043e\u0440\u043c\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 \u0438 \u0432\u044b\u0432\u043e\u0434\u0438\u043c \u043f\u043e\u043b\u0443\u0447\u0435\u043d\u043d\u044b\u0439 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<pre><code class=\"python\">model.solve()  used_patterns = [] for c in cuts_ids:     if cuts[c] >= 0.001:         used_patterns.append(tuple([items[t, c].varValue for t in order_types_ids])) print(\"\u0417\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0446\u0435\u043b\u0435\u0432\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 {}:\".format(model.objective.value())) print(\"\u041a\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043d\u0430\u0440\u0435\u0437\u0430\u043b\u0438\u0441\u044c \u0438\u0441\u043a\u043e\u0434\u043d\u044b\u0435 \u0440\u0443\u043b\u043e\u043d\u044b {}\".format(dict(Counter(used_patterns))))<\/code><\/pre>\n<p>\u0412 \u0442\u0435\u043a\u0443\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0446\u0435\u043b\u0435\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u0440\u0430\u0432\u043d\u0430 157, \u0442\u043e \u0435\u0441\u0442\u044c \u0434\u043b\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f \u0432\u0441\u0435\u0445 \u0437\u0430\u043a\u0430\u0437\u043e\u0432, \u043d\u0430\u043c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0441\u0442\u043e\u043b\u044c\u043a\u043e \u0448\u0442\u0443\u043a \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0445 \u0440\u0443\u043b\u043e\u043d\u043e\u0432. \u041f\u0440\u0438 \u044d\u0442\u043e\u043c \u0437\u0430\u0434\u0430\u0447\u0443 \u043c\u043e\u0436\u043d\u043e \u0440\u0435\u0448\u0438\u0442\u044c \u0431\u044b\u0441\u0442\u0440\u043e, &#8212; \u0443\u0431\u0440\u0430\u0442\u044c \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u0435 \u043d\u0430 \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0441\u0442\u044c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0438  \u0432\u043e\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u0438\u043c\u043f\u043b\u0435\u043a\u0441 \u043c\u0435\u0442\u043e\u0434\u043e\u043c. \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0440\u0435\u043b\u0430\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0439 (\u0431\u0435\u0437 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 \u0431\u044b\u043b\u0438 \u0446\u0435\u043b\u044b\u043c\u0438) \u0437\u0430\u0434\u0430\u0447\u0438 \u0440\u0430\u0432\u043d\u043e 120,5, \u0447\u0442\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u043e\u0447\u0435\u043d\u044c \u0434\u0430\u043b\u0435\u043a\u043e \u043e\u0442 \u043d\u0443\u0436\u043d\u043e\u0433\u043e \u043d\u0430\u043c \u0446\u0435\u043b\u043e\u0447\u0438\u0441\u043b\u0435\u043d\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f. \u041f\u0440\u0438 \u0434\u0440\u0443\u0433\u0438\u0445 \u0442\u0438\u043f\u0430\u0445 \u0437\u0430\u043a\u0430\u0437\u043e\u0432, \u044d\u0442\u0430 \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u043c\u043e\u0436\u0435\u0442 \u0438 \u0434\u0430\u043b\u044c\u0448\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u043e \u0440\u0430\u0441\u0442\u0438. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0435\u0441\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0430 \u0431\u0443\u0434\u0435\u0442 \u0431\u043e\u043b\u044c\u0448\u043e\u0439, \u0442\u043e \u043f\u043e\u043b\u044c\u0437\u0443\u044f\u0441\u044c \u0442\u0435\u043a\u0443\u0449\u0438\u043c \u043c\u0435\u0442\u043e\u0434\u043e\u043c, \u043c\u044b \u0432 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0435 \u0435\u0435 \u043d\u0435 \u0441\u043c\u043e\u0436\u0435\u043c \u0440\u0435\u0448\u0438\u0442\u044c \u0438\u043b\u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043e\u0447\u0435\u043d\u044c \u043f\u043b\u043e\u0445\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435.   <\/p>\n<p>\u041f\u043e\u043b\u043d\u044b\u0439 \u043a\u043e\u0434 \u043c\u043e\u0434\u0435\u043b\u0438 \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 <a href=\"https:\/\/github.com\/m-krasilnikov\/optimization\/blob\/main\/column_generation.py\" rel=\"noopener noreferrer nofollow\">\u0437\u0434\u0435\u0441\u044c<\/a>.<\/p>\n<h3>\u0420\u0435\u0448\u0435\u043d\u0438\u0435 2. \u041c\u043e\u0434\u0435\u043b\u044c \u0413\u0438\u043b\u043c\u043e\u0440\u0430-\u0413\u043e\u043c\u043e\u0440\u0438. \u0420\u0435\u0448\u0435\u043d\u0438\u0435 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432 \u0440\u0430\u0437\u0440\u0435\u0437\u0430 (\u0441\u0442\u043e\u043b\u0431\u0446\u043e\u0432).<\/h3>\n<p>    \u0422\u0440\u044e\u043a \u044d\u0442\u043e\u0433\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0430 \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u0432 \u0441\u043b\u0443\u0447\u0430\u0435, \u043a\u043e\u0433\u0434\u0430 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u043f\u0435\u0440\u0435\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0432\u0441\u0435 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u044b \u043f\u043e \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043d\u0430\u0440\u0435\u0437\u0430\u043d \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u0440\u0443\u043b\u043e\u043d, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0441\u043e\u043a\u0440\u0430\u0442\u0438\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445. \u041c\u0430\u0442\u0440\u0438\u0446\u0430 , \u0433\u0434\u0435 \u043a\u0430\u0436\u0434\u044b\u0439 \u0435\u0435 \u0441\u0442\u043e\u043b\u0431\u0435\u0446 \u0445\u0430\u0440\u0430\u043a\u0442\u0435\u0440\u0438\u0437\u0443\u0435\u0442 \u043e\u0434\u0438\u043d \u043f\u0430\u0442\u0442\u0435\u0440\u043d \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u0432\u0441\u0435\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u0440\u0430\u0437\u0440\u0435\u0437\u0430 (\u043e\u0434\u0438\u043d \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u0440\u0430\u0437\u0440\u0435\u0437\u0430 \u0440\u0443\u043b\u043e\u043d\u0430 &#8212; \u043e\u0434\u0438\u043d \u0441\u0442\u043e\u043b\u0431\u0435\u0446 \u044d\u0442\u043e\u0439 \u043c\u0430\u0442\u0440\u0438\u0446\u044b). \u0422\u0430\u043a \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0435\u0441\u043b\u0438 \u0443 \u043d\u0430\u0441 \u0437\u0430\u043a\u0430\u0437 \u0434\u043b\u0438\u043d\u044b (3, 5, 6, 9), \u0430 \u0448\u0438\u0440\u0438\u043d\u0430 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0443\u043b\u043e\u043d\u0430 10, \u0442\u043e \u0435\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u0440\u0435\u0437\u0430\u0442\u044c \u043d\u0430 \u0434\u0432\u0430 \u043a\u0443\u0441\u043a\u0430, \u043e\u0434\u0438\u043d \u0448\u0438\u0440\u0438\u043d\u044b 3, \u0430 \u0434\u0440\u0443\u0433\u043e\u0439 \u0448\u0438\u0440\u0438\u043d\u044b 6. \u0410 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u043f\u0430\u0442\u0442\u0435\u0440\u043d \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u044f \u0431\u0443\u0434\u0435\u0442 (1, 0, 1, 0). \u0422\u0430\u043a \u043a\u0430\u043a \u043c\u044b \u0432\u0437\u044f\u043b\u0438 \u043f\u0435\u0440\u0432\u044b\u0439 \u0438 \u0442\u0440\u0435\u0442\u0438\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 \u0441\u043f\u0438\u0441\u043a\u0430 \u0441 \u0442\u0438\u043f\u0430\u043c\u0438 \u0437\u0430\u043a\u0430\u0437\u043e\u0432. \u041f\u0430\u0442\u0442\u0435\u0440\u043d\u044b \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u044f, \u0432 \u043d\u0430\u0448\u0435\u043c \u0443\u0447\u0435\u0431\u043d\u043e\u043c \u043f\u0440\u0438\u043c\u0435\u0440\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u044b \u043d\u0430 \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u043d\u0438\u0436\u0435: <\/p>\n<figure class=\"full-width\"><\/figure>\n<p>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f<\/p>\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-388780","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/388780","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=388780"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/388780\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=388780"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=388780"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=388780"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}