История создания нового подхода для решения нелинейных  оптимизационных многокритериальных задач – метод «надувного  шарика» 



        В конце 1973 г., будучи нач. АСУТП на Нелидовском заводе пластмасс и, кстати, молодым специалистом, я принимал у разработчиков систему. В числе прочих задач была задача оптимального распределения плана производства в цехе. Размерность задачи была небольшой. В цехе было 16 экструзионных агрегатов, номенклатура составляла несколько десятков наименований видов продукции, но при переходе с выпуска с одной продукции на другую требовалась переналадка длительностью смена. Компьютер у нас был – 1010В, один из самых современных и мощных тогда в СССР. Решением этой задачи занималась группа молодых выпускников московского физико-технического института (МФТИ)- Самсонов В.Г (основной программист), Фаянс А.М., Винокур Р.Ю. (в будущем кандидат технических наук) во главе с молодым кандидатом технических наук Алешиным А.Я. Первоначально эта задача беспокойства не вызывала. Ее регулярно решали в техбюро цеха без особых проблем и перевод на компьютер решили сделать, как говорится, попутно.

        Когда мне принесли готовую распечатку результатов работы новой программы и акт сдачи-приемки работы, я решил, просто на всякий случай, подойти к нач.техбюро и показать результаты, прежде чем подписать акт. Но неожиданно на моих глазах нач. техбюро Садова Л.П. (в будущем кандидат химических наук) улучшила план, рассчитанный компьютером. Я отправил программу на доработку. Второй раз через месяц эта история повторилась с новым вариантом программы. Еще через два месяца это повторилось с третьим вариантом программы.

       Но на этот раз перед демонстрацией результатов нач.техбюро мне разработчики рассказали следующее. Они перед подготовкой последнего варианта программы связались со своими профессорами в МФТИ, которые занимались вопросами оптимизации и были одними из ведущих специалистов в СССР в этой области. После обсуждения они пришли к выводу, что поставленная задача на тот момент была теоретически неразрешима. Можно было применить лишь метод полного перебора, но это уже не позволял реализовать компьютер.

       Я был крайне удивлен этой ситуацией, ведь опытный специалист цеха достаточно легко решал эту задачу. Но разработчиков я пожалел, задача эта принципиального значения для работы АСУТП не имела. Акт сдачи-приемки я им подписал. Тогда невыполнение даже небольшой части работы было весьма чревато для разработчиков.

       Мне предстояло еще в будущем готовить диссертацию. Дел у меня в тот момент с АСУТП было очень много и я решил оставить себе эту неразрешимую задачу, которую впрочем при мне достаточно легко решал специалист и без компьютера, чтобы попытаться ее решить в дальнейшем.

      Через год в конце 1974 г., когда у меня стало посвободней со временем, я занялся этой задачей. Начал с бесед с нач. техбюро, выясняя как она решала эту задачу. Затем изучил научную литературу по данному вопросу. Потом переговорил со своим научным руководителем к.т.н., профессором Николаевым Анатолием Алексеевичем. Несколько месяцев зимой 1974-75 гг. я искал решение. Иногда мне казалось, что я его находил и тогда я ехал в Калинин к Николаеву. Обсуждение обычно происходило так, - я излагал Николаеву свои мысли, пока рассказывал, я сам находил свою ошибку и на этом обсуждение обычно заканчивалось. Так присходило несколько раз.

       Не могу не сказать несколько слов о Николаеве А.А. Это человек одновременно и героической и трагической судьбы. Во время Отечественной войны в Ленинграде стал сиротой, убежал на фронт, стал сыном полка, воевал, закончил войну в Германии. После войны учился в детдоме, стал военным летчиком. Потом работал начальником отдела у Королева С.П. (того самого - генерального конструктора космических ракет), готовил комонавтов, дружил с Гагариным Ю.А. и Береговым Г.Т. После катастрофы во время учебного полета на реактивном самолете Николаева А.А. комисовали и он стал преподавать у нас в Калининском политехническом институте (КПИ). К сожалению, его уже давно нет с нами. Вторым моим научным руковдителем уже в Горьком стал д.т.н., профессор, член-корреспондент РАН Кондратьев В.В.

       Но вернемся к методу. В начале марта 1975 г. меня неожиданно призвали на военные сборы на месяц и там я простыл. После возвращения я заболел воспалением легких и попал на три недели в больницу. По выходе из нее я узнаю, что через пять дней мне предстоит выступать с докладом на ежегодной годовой научной конференции в ГПИ. Я к Николаеву - что делать, метода я не нашел и вообще кое-что подзабыл за два месяца отвлечения от работы. Николаев мне и говорит: "выступать надо, ведь что-то ты несколько месяцев делал, расскажи о постановке задачи, о возникших проблемах". Я начал готовить доклад, собирал вместе обрывки тех положительных результатов, которые нашел. После двух дней работы, ночью, я вдруг понял, что нашел метод.

         Николаеву мой метод понравился и он решил объединить два доклада вместе его и мой. С общим докладом на конференции в КПИ выступил он сам. Так состоялось первое сообщение о методе в 1975 г.

         Однако запрограммировать и внедрить окончательно новый метод на своем предприятии мне не удалось. У меня в подчинении были программисты, но АСУТП работала в 3 смены месяцами, а компьютер был один. Отладка программ производилась только в период редких простоев и лишь для текущих задач.

          В 1976 г. я переехал г.Гороький, начал работать в НИИУавтопроме. В течение полутора лет я разбирался, что же у меня получилось, весь задача была неразрешима.

         Первое на что я натолкнулся - это своеобразная постановка задачи. В линейном варианте (без переналадок) - эта задача максимизации выпуска комплектов продукции согласно заданной пропорции. Впервые я эту постановку встретил в книге Канторовича Л.В. (кстати Нобелевского лауреата)Экономический расчет наилучшего использования ресурсов, 1960 г.. Причем он утверждает, что изучал эту задачу в 30-х годах. Иногда ее называют эту задачу - задачей Канторовича. В этой задаче максимизируется один параметр. С виду это простейший случай оптимизации суммарного критерия задачи линейного программирования. Но все оказалось сложнее. Именно эту постановку задачи решает мой метод "надувного шарика", который имеет не меньше, а гораздо больше возможностей, чем, например, симплекс - метод. Все проскакивали мимо особенностей этой постановки задачи. Наверно и я бы проскочил, если бы начинал с теории. Но я начинал с конкретной практической задачи. 

        Основной же успех обеспечивало использование сочетания уже хорошо известных методов - итеративного подхода, метода максимального элемента, метода ветвей и границ и специального приема понижения размерности. Этот весьма эффективный и совершенно очевидный прием понижения размерности (кстати, в общем-то он хорошо известен) я узнал у нач.техбюро в Нелидово, выясняя, как она так быстро решает задачу планирования. По нему можно долго рассуждать (в приводимой на сайте статье он описан), но это в другой раз.

        В 1976 г. в г. Горьком, я обратился в НИИ прикладной математики и кибернетики (один из ведущих тогда в СССР институтов по оптимизации), чтобы мне разъяснили, что я придумал. Мою статью посмотрел доцент Коган Д.И.(позже профессор), сказал, что особых ошибок не нашел и, возможно, для конкретной задачи метод действительно подходит. Позже через 10 лет возникла ситуация, когда еще один сотрудник НИИ ПМК плотно разбирался с моим методом и он снова подтвердил, в основном, его работоспособность.

         Но вернемся к 1977 г. Я решил опубликовать статью в трудах НИИУавтопрома, в более центральные издания, обратиться побоялся, меня бы не пропустили. После бурных обсуждений (я тогда был новый человек для института) статью опубликовали. Лишь через год до меня дошло окончательно, что же я придумал, и пришло название - метод «надувного шарика». До сих пор, считается, что глобальный оптимум для невыпуклой замкнутой области изменения переменных можно найти только путем нахождения и полного перебора локальных оптимумов. Уже для многих реальных задач средней и большой размерности это нереально.

         Однако, если, условно, в некий невыпуклый (или выпуклый, как частный случай), но замкнутый объем, поместить внутрь резиновый шарик и начать его надувать, то он быстро изнутри достигнет оболочки, независимо от сложностей ее невыпуклостей и количества локальных оптимумов. Момент полного прикосновения к внешней оболочки изнутри и является моментом нахождения решения задачи. Мой конкретный метод и реализует этот общий принцип. Я, не исключаю, что могут быть и другие, включая аналитические , методы реализации принципа «надувного шарика». Таким образом, кроме конкретного метода, я придумал общий принцип нахождения решения нелинейных оптимизационных задач.

        Для данного принципа такая проблема, как проблема поиска целочисленного решения вообще автоматически решается. А, многие нелинейные эффекты, которые до сих пор делали точное решение практических задач невозможным, лишь только немного усложняют их решение.

         У данного принципа «надувного шарика» есть и прямая физическая аналогия. Например, в некую жестяную сферу через узкое отверстие поместим надувной резиновый шарик. Начнем насосом подавать в резиновый шарик воздух, измеряя его давление. Вначале шарик внутри сферы начнет надуваться. В момент после соприкосновения поверхности резинового шарика с внутренней поверхностью сферы начнет быстро нарастать давление воздуха. Если мы любым образом будем предварительно деформировать поверхность сферы, скорость достижения этого момента (момента нарастания давления) пропорционален только внутреннему объему сферы независимо от ее деформируемости.

        Для математического метода «надувного шарика» скорость нахождения конечно не связана с внутренним объемом, а только с размерностью задачи и сложностью расчета нелинейных эффектов в исходной постановке задачи.

         Формально максимизируемый показатель один и он линеен. Но в правой части систем уравнений при мю фигурируют коэффициенты b . И в процессе итеративного решения задачи можно сделать так, чтобы каждый из этих коэффициентов был бы представлен нелинейной возрастающей функцией (в статье об этом не сказано, но об этом было сказано и в первом докладе в 1975 г. и потом было практически использовано в 1991-92 гг.). Возникает возможность одновременно работать с множеством целевых функций (критериев) и обеспечивать их одновременное достижение.

          Все привыкли к суммарному критерию и его вариантам, который широко используется в линейном программировании. Но он хорош, когда Вы работаете с денежным эквивалентом, к чему могут быть сведены разные процессы. Но на практике планирования и управления – это редкий случай, чаще возникают совсем другие проблемы. Даже в бизнес-планах, там большая часть говорится не о деньгах (хотя потом к деньгам сводится). Мой метод представляет совершенно новые возможности по решению многоцелевых (многокритериальных) задач.

         Наиболее близко к моему методу (насколько мне известно), подошли создатели метода «внутренних точек» (тоже итеративного, как и мой) из Новосибирска в конце 70-х годов. Однако они ограничились решением задачи линейного программирования со стандартным критерием, что и сузило возможности применения их метода.

        Однако параллельно постепенным размышлениям над найденным методом, у меня стояли совсем другие практические задачи – решение новых для меня конкретных производственных проблем, упрочнение своего положения в институте и необходимость защитить диссертацию. Поскольку выходить в те времена на защиту с совершенно новым методом, не имея длительных серьезных наработок, было опасно, я стал искать другую тему и научного руководителя.

        Лишь после защиты в 1984 г. по совсем другому направлению, я снова задумался о методе, хотя у меня к тому времени были уже новые интересные наработки и идеи. Поскольку финансирования для реализации метода я так и не нашел, я сам решил запрограммировать метод. Хотя у меня был достаточно приличный опыт программирования конкретных задач, я быстро столкнулся с некоторыми чисто программистскими трудностями , которые не смог преодолеть. Видимо, умение программировать не относится к моим сильным сторонам. Все застряло еще на несколько лет, а я занялся решением совсем других возникших проблем и идей.

        В 1991 г., уже создав свое первое предприятие НПЧВП «ВЕХА», уже реализовав одну свою старую (менее старую чем метод «надувного шарика») идею создания столема, имея приличные тогда ПЭВМ и уже имея некоторые деньги, я решил все-таки запрограммировать метод «надувного шарика». Для начала я стал искать заказы на оптимизацию планирования производства. Быстро найти не удалось, но в процессе переговоров с заказчиками, неожиданно натолкнулся на то, что задача оптимизации линейного раскроя материалов для швейной фабрики имеет близкую математическую постановку задачи. Значит мой метод тоже решит и эту задачу. Заключили с заказчиком договор, хороший программист у меня уже был – Патокин Д.В. Потом еще один договор сделали. В общем метод заработал, находимое на ПЭВМ решение было не хуже, чем находимое человеком. Выход годного раскраиваемого материала составлял 99,3-99,5 процентов (0,5-0,7 процентов остатки). Когда же мы стали сравнивать решения, оказалось, что человек незаметно немного нарушал условия задачи, что приходило, естественно, к ухудшению качества продукции, но обычно это не замечалась.

        Но уже шел 1992 г. – экономическая ситуация стала быстро ухудшаться, у швейных фабрик и других предприятий стали падать объемы производства, об оптимизации речь не шла, лишь бы выжить. И готовая программа, которую я готов был внедрять по всей стране, оказалась ненужной. В результате вынужден был свернуть это направление, как теперь понимаю зря. Я тогда, как многие предприниматели, пробовал разные направления работ, и многие из них себя не оправдывали.

        Теперь эта программа устарела, на новых компьютерах не идет, программист давно занимается продажей недвижимости, требуется ее снова перепрограммировать, снова требуется финансирование. Периодически, я выступаю с докладами (последний раз в 2007 г.) . Мне не раз в зале приходилось объяснять другим докладчикам, что у меня есть решение задачи, которое Вы не можете решить.

       Наука представляет собой, что-то вроде «расчески». Общее основание расчески - это общие научные принципы, а зубья расчески – это конкретные научные направления. Каждый ученый работает в своем направлении годами и десятилетиями все дальше и дальше, а зуб расчески становится все тоньше и тоньше. В этом же направлении работают другие ученые и они понимают друг друга, а и их научные результаты признаются. А между зубьями расчески большое пространство, как и между научными направлениями. И если, какой-то ученый или специалист, что-то находит между научными направлениями (по разным причинам), то он испытывает большую проблему в понимании среди других ученых. И чем больше это расстояние с соседними направлениями, тем больше непонимание.

         По-видимому, со своим методом я попал в это большое пустое пространство, а другие ученые (кроме некоторых, как постепенно выясняется) до него (уже более 30 лет) пока никак не доберутся. Хотя я уже давно открыл дверь нового направления, где желающие могут сделать десятки докторских и сотни кандидатских диссертаций (с учетом применения метода в других областях)и получать более высокий эффект от своих вложений.

         Кстати, многие бы подобные проблемы смогло бы решить создание «интеллектуальных электронных книг» - элинг (это мой новый проект, упомянутый на первой странице сайта), но до этого пока далеко. 

                                                                                                                        Дополнение

        20.12.06 г. 15 лет пролежала у меня книга Лорьера Ж.Л. Системы искусственного интеллекта, М., Мир, 1991 г. среди прочей более интересной (обычно чаще смотрел) литературы по направлении ИИ, которым мне приходится заниматься более 20 лет. И вот вдруг обратил большее внимание на описанную в ней информационную интеллектуальную систему для решения задач, которой Лорьер гордится.

          И вдруг опешил от неожиданности - в качестве ядра этой системы использован тот же, подход, который я применил в своем методе «надувного шарика» и назвал «принципом надувного шарика» и который развиваю с 1975 г.

          Он свой подход в основном развил для работы с интеллектуальными системами, я больше занимался чисто численными задачами, но обратил внимание на несколько иные возможности данного подхода, чем он.

       Он постоянно говорит об очень больших возможностях данного подхода, я тоже говорю о том же. На мой взгляд, теперь уж совершенно ясно, что данный подход станет одним из основных новых математических методов для решения различных задач различных областей в 21 веке, в т.ч. активно использоваться при создания ЭВМ 5 поколения.

        Готов к сотрудничеству (на определенных условиях) с желающими поработать в данном направлении – реализации метода «надувного шарика», его применения и дальнейших теоретических разработках.