ОТЗЫВ
научного руководителя на диссертационную работу «Алгоритмы с оценками для некоторых задач размещения производства», представленную на соискание ученой степени кандидата физико-математических наук по специальности 01.01.09 – дискретная математика и математическая кибернетика.
Основная цель, поставленная перед диссертантом, состояла в построении эффективных алгоритмов (полиномиальной временной сложности) и в теоретическом обосновании гарантированных оценок качества применения этих алгоритмов для решения ряда модификаций задачи размещения. Эта задача является в общем случае известной труднорешаемой проблемой дискретной оптимизации. Особый акцент делается на задаче размещения с ограниченными объемами производства, которая, пожалуй, представляет один из наиболее сложных подклассов дискретной теории размещения. Исследованию ее нетривиальных разновидностей посвящена большая часть диссертационной работы.
Первые две главы диссертационной работы посвящены исследованию двух специальных подклассов задачи размещения на сети, для которых удается построить точные полиномиальные алгоритмы решения. В первой главе исследуется задача размещения на путевом графе (цепи) в предположении, что предприятия имеют одинаковые ограничения на объемы производства. Результатом исследования является построение и обоснование корректности точного алгоритма решения с временной сложностью, на порядок улучшенной по сравнению с ранее известным результатом . Во второй главе изучается двухстадийная задача размещения на древовидной сети. Благодаря установлению факта существования оптимального решения, обладающего специальными структурными свойствами, удалось обосновать нетривиальные рекуррентные соотношения и построить точный алгоритм с временной сложностью, линейно зависящей от числа точек спроса.
Характерной чертой следующих двух глав является рассмотрение оптимизационных постановок на случайных входных данных и проведение нетривиального вероятностного анализа работы предлагаемых алгоритмов. Третья глава посвящена построению и обоснованию оценок качества работы быстрого приближенного алгоритма поиска совершенного паросочетания в случайном графе. Полученные здесь результаты эффективно используются далее в четвертой главе, где исследуется общая постановка задачи размещения на произвольной сети при ограничениях на производственные мощности предприятий в предположении, что входные данные задаются случайным образом. Основным результатом здесь является построение быстрых приближенных алгоритмов решения как в случае одинаковых, так и в случае произвольных ограничений на объемы производства предприятий. При этом обоснованы соответствующие гарантированные оценки точности получаемых решений и представлены условия асимптотической точности предложенных алгоритмов.
В целом за время учебы в аспирантуре и работы над диссертацией проявил себя как зрелый научный исследователь, способный самостоятельно решать сложные проблемы в области дискретной оптимизации и исследования операций. Результаты, представленные в диссертации, являются весомым вкладом в названную область. Они опубликованы в печати, неоднократно докладывались на различных международных и всероссийских конференциях, а также на семинарах ИМ СО РАН и ИВМиМГ СО РАН. Считаю, что представленная к защите диссертационная работа удовлетворяет всем требованиям Высшей аттестационной комиссии, и Александр Александрович Курочкин несомненно заслуживает присуждения ему степени кандидата физико-математических наук по специальности 01.01.09 – дискретная математика и математическая кибернетика.
Научный руководитель, доктор физико-математических наук, профессор,
заведующий лабораторией Дискретной оптимизации в исследовании операций Института математики им.
//
г. Новосибирск 13 января 2014 г.
