ТЕОРЕТИЧЕСКИЕ ОСНОВАНИЯ МЕТОДА РЕШЕНИЯ НЕЛИНЕЙНЫХ ОПТИМИЗАЦИОННЫХ ЗАДАЧ - МЕТОДА "НАДУВНОГО ШАРИКА "

На этой странице будет приведена статья Бронфельда Г.Б. от 1977 г. (сам метод разработан в 1975 г.), наиболее полно излагающая основную суть метода. Здесь будет изложена история создания метода, приведены новые дополнения к статье, которые были сделаны за эти годы, а также описаны некоторые результаты других ученых, стыкующиеся с данным методом.

___В конце 1973 г., будучи нач. АСУТП на Нелидовском заводе пластмасс и, кстати, молодым специалистом, я принимал у разработчиков систему. В числе прочих задач была задача оптимального распределения плана производства в цехе. Размерность задачи была небольшой. В цехе было 16 экструзионных агрегатов, номенклатура составляла несколько десятков наименований видов продукции, но при переходе с выпуска с одной продукции на другую требовалась переналадка длительностью смена. Компьютер у нас был – 1010В, один из самых современных и мощных тогда в СССР. Решением этой задачи занималась группа молодых выпускников московского физико-технического института (МФТИ)- Самсонов В.Г (основной программист), Фаянс А.М., Винокур Р.Ю. (в будущем кандидат технических наук) во главе с молодым кандидатом технических наук Алешиным А.Я. Первоначально эта задача беспокойства не вызывала. Ее регулярно решали в техбюро цеха без особых проблем и перевод на компьютер решили сделать, как говорится, попутно.
___Когда мне принесли готовую распечатку результатов работы новой программы и акт сдачи-приемки работы, я решил, просто на всякий случай, подойти к нач.техбюро и показать результаты, прежде чем подписать акт. Но неожиданно на моих глазах нач. техбюро Садова Л.П. (в будущем кандидат химических наук) улучшила план, рассчитанный компьютером. Я отправил программу на доработку. Второй раз через месяц эта история повторилась с новым вариантом программы. Еще через два месяца это повторилось с третьим вариантом программы.
___Но на этот раз перед демонстрацией результатов нач.техбюро мне разработчики рассказали следующее. Они перед подготовкой последнего варианта программы связались со своими профессорами в МФТИ, которые занимались вопросами оптимизации и были одними из ведущих специалистов в СССР в этой области. После обсуждения они пришли к выводу, что поставленная задача на тот момент была теоретически неразрешима. Можно было применить лишь метод полного перебора, но это уже не позволял реализовать компьютер.
___Я был крайне удивлен этой ситуацией, ведь опытный специалист цеха достаточно легко решал эту задачу. Но разработчиков я пожалел, задача эта принципиального значения для работы АСУТП не имела. Акт сдачи-приемки я им подписал. Тогда невыполнение даже небольшой части работы было весьма чревато для разработчиков.
___Мне предстояло еще в будущем готовить диссертацию. Дел у меня в тот момент с АСУТП было очень много и я решил оставить себе эту неразрешимую задачу, которую впрочем при мне достаточно легко решал специалист и без компьютера, чтобы попытаться ее решить в дальнейшем.
___Через год в конце 1974 г., когда у меня стало посвободней со временем, я занялся этой задачей. Начал с бесед с нач. техбюро, выясняя как она решала эту задачу. Затем изучил научную литературу по данному вопросу. Потом переговорил со своим научным руководителем к.т.н., профессором Николаевым Анатолием Алексеевичем. Несколько месяцев зимой 1974-75 гг. я искал решение. Иногда мне казалось, что я его находил и тогда я ехал в Калинин к Николаеву. Обсуждение обычно происходило так, - я излагал Николаеву свои мысли, пока рассказывал, я сам находил свою ошибку и на этом обсуждение обычно заканчивалось. Так присходило несколько раз.
___Не могу не сказать несколько слов о Николаеве А.А. Это человек одновременно и героической и трагической судьбы. Во время Отечественной войны в Ленинграде стал сиротой, убежал на фронт, стал сыном полка, воевал, закончил войну в Германии. После войны учился в детдоме, стал военным летчиком. Потом работал начальником отдела у Королева С.П. (того самого - генерального конструктора космических ракет), готовил комонавтов, дружил с Гагариным Ю.А. и Береговым Г.Т. После катастрофы во время учебного полета на реактивном самолете Николаева А.А. комисовали и он стал преподавать у нас в Калининском политехническом институте (КПИ). К сожалению, его уже давно нет с нами. Вторым моим научным руковдителем уже в Горьком стал д.т.н., профессор, член-корреспондент РАН Кондратьев В.В.
___Но вернемся к методу. В начале марта 1975 г. меня неожиданно призвали на военные сборы на месяц и там я простыл. После возвращения я заболел воспалением легких и попал на три недели в больницу. По выходе из нее я узнаю, что через пять дней мне предстоит выступать с докладом на ежегодной годовой научной конференции в ГПИ. Я к Николаеву - что делать, метода я не нашел и вообще кое-что подзабыл за два месяца отвлечения от работы. Николаев мне и говорит: "выступать надо, ведь что-то ты несколько месяцев делал, расскажи о постановке задачи, о возникших проблемах". Я начал готовить доклад, собирал вместе обрывки тех положительных результатов, которые нашел. После двух дней работы, ночью, я вдруг понял, что нашел метод.
___Николаеву мой метод понравился и он решил объединить два доклада вместе его и мой. С общим докладом на конференции в КПИ выступил он сам. Так состоялось первое сообщение о методе в 1975 г.

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

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

__Основной же успех обеспечивало использование сочетания уже хорошо известных методов - итеративного подхода, метода максимального элемента, метода ветвей и границ и специального приема понижения размерности. Этот весьма эффективный и совершенно очевидный прием понижения размерности (кстати, в общем-то он хорошо известен) я узнал у нач.техбюро в Нелидово, выясняя, как она так быстро решает задачу планирования. По нему можно долго рассуждать (в приводимой на сайте статье он описан), но это в другой раз.
___В 1976 г. в г. Горьком, я обратился в НИИ прикладной математики и кибернетики (один из ведущих тогда в СССР институтов по оптимизации), чтобы мне разъяснили, что я придумал. Мою статью посмотрел доцент Коган Д.И.(позже профессор), сказал, что особых ошибок не нашел и, возможно, для конкретной задачи метод действительно подходит. Позже через 10 лет возникла ситуация, когда еще один сотрудник НИИ ПМК плотно разбирался с моим методом и он снова подтвердил, в основном, его работоспособность.
___Но вернемся к 1977 г. Я решил опубликовать статью в трудах НИИУавтопрома, в более центральные издания, обратиться побоялся, меня бы не пропустили. После бурных обсуждений (я тогда был новый человек для института) статью опубликовали. Лишь через год до меня дошло окончательно, что же я придумал, и пришло название - метод «надувного шарика». До сих пор, считается, что глобальный оптимум для невыпуклой замкнутой области изменения переменных можно найти только путем нахождения и полного перебора локальных оптимумов. Уже для многих реальных задач средней и большой размерности это нереально.
___Однако, если, условно, в некий невыпуклый (или выпуклый, как частный случай), но замкнутый объем, поместить внутрь резиновый шарик и начать его надувать, то он быстро изнутри достигнет оболочки, независимо от сложностей ее невыпуклостей и количества локальных оптимумов. Момент полного прикосновения к внешней оболочки изнутри и является моментом нахождения решения задачи. Мой конкретный метод и реализует этот общий принцип. Я, не исключаю, что могут быть и другие, включая аналитические , методы реализации принципа «надувного шарика». Таким образом, кроме конкретного метода, я придумал общий принцип нахождения решения нелинейных оптимизационных задач.
___Для данного принципа такая проблема, как проблема поиска целочисленного решения вообще автоматически решается. А, многие нелинейные эффекты, которые до сих пор делали точное решение практических задач невозможным, лишь только немного усложняют их решение.
___У данного принципа «надувного шарика» есть и прямая физическая аналогия. Например, в некую жестяную сферу через узкое отверстие поместим надувной резиновый шарик. Начнем насосом подавать в резиновый шарик воздух, измеряя его давление. Вначале шарик внутри сферы начнет надуваться. В момент после соприкосновения поверхности резинового шарика с внутренней поверхностью сферы начнет быстро нарастать давление воздуха. Если мы любым образом будем предварительно деформировать поверхность сферы, скорость достижения этого момента (момента нарастания давления) пропорционален только внутреннему объему сферы независимо от ее деформируемости.
___ Для математического метода «надувного шарика» скорость нахождения конечно не связана с внутренним объемом, а только с размерностью задачи и сложностью расчета нелинейных эффектов в исходной постановке задачи.
___Формально максимизируемый показатель один и он линеен. Но в правой части систем уравнений при мю фигурируют коэффициенты b . И в процессе итеративного решения задачи можно сделать так, чтобы каждый из этих коэффициентов был бы представлен нелинейной возрастающей функцией (в статье об этом не сказано, но об этом было сказано и в первом докладе в 1975 г. и потом было практически использовано в 1991-92 гг.). Возникает возможность одновременно работать с множеством целевых функций (критериев) и обеспечивать их одновременное достижение.
___Все привыкли к суммарному критерию и его вариантам, который широко используется в линейном программировании. Но он хорош, когда Вы работаете с денежным эквивалентом, к чему могут быть сведены разные процессы. Но на практике планирования и управления – это редкий случай, чаще возникают совсем другие проблемы. Даже в бизнес-планах, там большая часть говорится не о деньгах (хотя потом к деньгам сводится). Мой метод представляет совершенно новые возможности по решению многоцелевых (многокритериальных) задач.
___Наиболее близко к моему методу (насколько мне известно), подошли создатели метода «внутренних точек» (тоже итеративного, как и мой) из Новосибирска. Однако они ограничились решением задачи линейного программирования со стандартным критерием, что и сузило возможности применения их метода.
___Однако параллельно постепенным размышлениям над найденным методом, у меня стояли совсем другие практические задачи – решение новых для меня конкретных производственных проблем, упрочнение своего положения в институте и необходимость защитить диссертацию. Поскольку выходить в те времена на защиту с совершенно новым методом, не имея длительных серьезных наработок, было опасно, я стал искать другую тему и научного руководителя.
___Лишь после защиты в 1984 г. по совсем другому направлению, я снова задумался о методе, хотя у меня к тому времени были уже новые интересные наработки и идеи. Поскольку финансирования для реализации метода я так и не нашел, я сам решил запрограммировать метод. Хотя у меня был достаточно приличный опыт программирования конкретных задач, я быстро столкнулся с некоторыми чисто программистскими трудностями , которые не смог преодолеть. Видимо, умение программировать не относится к моим сильным сторонам. Все застряло еще на несколько лет, а я занялся решением совсем других возникших проблем и идей.

___В 1991 г., уже создав свое первое предприятие НПЧВП «ВЕХА», уже реализовав одну свою старую (менее старую чем метод «надувного шарика») идею создания столема, имея приличные тогда ПЭВМ и уже имея некоторые деньги, я решил все-таки запрограммировать метод «надувного шарика». Для начала я стал искать заказы на оптимизацию планирования производства. Быстро найти не удалось, но в процессе переговоров с заказчиками, неожиданно натолкнулся на то, что задача оптимизации линейного раскроя материалов для швейной фабрики имеет близкую математическую постановку задачи. Значит мой метод тоже решит и эту задачу. Заключили с заказчиком договор, хороший программист у меня уже был – Патокин Д.В. Потом еще один договор сделали. В общем метод заработал, находимое на ПЭВМ решение было не хуже, чем находимое человеком. Выход годного раскраиваемого материала составлял 99,3-99,5 процентов (0,5-0,7 процентов остатки). Когда же мы стали сравнивать решения, оказалось, что человек незаметно немного нарушал условия задачи, что приходило, естественно, к ухудшению качества продукции, но обычно это не замечалась.
___Но уже шел 1992 г. – экономическая ситуация стала быстро ухудшаться, у швейных фабрик и других предприятий стали падать объемы производства, об оптимизации речь не шла, лишь бы выжить. И готовая программа, которую я готов был внедрять по всей стране, оказалась ненужной. В результате вынужден был свернуть это направление, как теперь понимаю зря. Я тогда, как многие предприниматели, пробовал разные направления работ, и многие из них себя не оправдывали.
___Теперь эта программа устарела, на новых компьютерах не идет, программист давно занимается продажей недвижимости, требуется ее снова перепрограммировать, снова требуется финансирование. Периодически, я выступаю с докладами (последний раз в 2007 г.) . Мне не раз в зале приходилось объяснять другим докладчикам, что у меня есть решение задачи, которое Вы не можете решить.
___Наука представляет собой, что-то вроде «расчески». Общее основание расчески - это общие научные принципы, а зубья расчески – это конкретные научные направления. Каждый ученый работает в своем направлении годами и десятилетиями все дальше и дальше, а зуб расчески становится все тоньше и тоньше. В этом же направлении работают другие ученые и они понимают друг друга, а и их научные результаты признаются. А между зубьями расчески большое пространство, как и между научными направлениями. И если, какой-то ученый или специалист, что-то находит между научными направлениями (по разным причинам), то он испытывает большую проблему в понимании среди других ученых. И чем больше это расстояние с соседними направлениями, тем больше непонимание.
___По-видимому, со своим методом я попал в это большое пустое пространство, а другие ученые (кроме некоторых, как постепенно выясняется) до него (уже более 30 лет) пока никак не доберутся. Хотя я уже давно открыл дверь нового направления, где желающие могут сделать десятки докторских и сотни кандидатских диссертаций (с учетом применения метода в других областях)и получать более высокий эффект от своих вложений.
___Кстати, многие бы подобные проблемы смогло бы решить создание «интеллектуальных электронных книг» - элинг (это мой новый проект, упомянутый на первой странице сайта), но до этого пока далеко.
__20.12.06 г. 15 лет пролежала у меня книга Лорьера Ж.Л. Системы искусственного интеллекта, М., Мир, 1991 г. среди прочей более интересной (обычно чаще смотрел) литературы по направлении ИИ, которым мне приходится заниматься более 20 лет. И вот вдруг обратил большее внимание на описанную в ней информационную интеллектуальную систему для решения задач, которой Лорьер гордится.
___И вдруг опешил от неожиданности - в качестве ядра этой системы использован тот же, подход, который я применил в своем методе «надувного шарика» и назвал «принципом надувного шарика» и который развиваю с 1975 г.
___Он свой подход в основном развил для работы с интеллектуальными системами, я больше занимался чисто численными задачами, но обратил внимание на несколько иные возможности данного подхода, чем он.
___Он постоянно говорит об очень больших возможностях данного подхода, я тоже говорю о том же. На мой взгляд, теперь уж совершенно ясно, что данный подход станет одним из основных новых математических методов для решения различных задач различных областей в 21 веке, в т.ч. активно использоваться при создания ЭВМ 5 поколения.
___Готов к сотрудничеству (на определенных условиях) с желающими поработать в данном направлении – реализации метода «надувного шарика», его применения и дальнейших теоретических разработках.