Задача линейного программирования – это поиск минимума и максимума линейной функции внутри выпуклого многогранника. К ней сводится множество прикладных алгоритмов оптимального распределения ресурсов: организация транспортных перевозок, планирование диет, стратегические расчёты в теории игр. Известен классический симплекс-метод, трудоемкость которого экспоненциально возрастает с ростом размерности.
Учёные из Челябинска ищут пути «имплантации» искусственного интеллекта в «чистую математику», что существенно ускорило бы поиск решения.
Что такое задача линейного программирования? На первый взгляд, это абстрактная математическая проблема, не имеющая прямого отношения к компьютерам и языкам программирования. Однако сегодня решение таких задач немыслимо без цифровой техники, за исключением, может быть, простых учебных задач для младшекурсников.
Интерес к задачам линейного программирования возник в 20–30-х годах ХХ века. Между прочим, это направление прославило двоих математиков – Василия Леонтьева из США и Леонида Канторовича из СССР, один из них получил Нобелевскую премию в 1973 году, а другой – в 1975-м. Да, за математические открытия Нобелевская премия не присуждается, однако им обоим была вручена премия по экономике. Ведь задачи оптимального распределения ресурсов, решаемые с помощью методов линейного программирования, максимально сближают экономику и математику. В их числе транспортная задача (распределение грузов со складов по магазинам), задача построения оптимального меню для спортсменов, многочисленные задачи теории игр.
Задача линейного программирования – это задача на определение экстремумов – максимальных и минимальных значений целевой функции f(x)=c1x1 + с2x2 + … + сnxn в пространстве размерности n. Во всём пространстве, разумеется, экстремумов у линейной функции быть не может. Поиск ведётся в области, задаваемой системой линейных неравенств
a11x1 + a12x2 + … + a1nxn ≤ b1
…
am1x1 + am2x2 + … + amnxn ≤ bm
Если представить ситуацию на плоскости, тогда прямые, задающие неравенства, образуют многоугольник (результат пересечения полупространств), через который проходит прямая, соответствующая целевой функции. Решение интуитивно «видно» по рисунку, хотя это не отменяет точных вычислений.
Вопрос в том, насколько сложны вычисления? Зависит от алгоритма, по которому они будут вестись. Но Википедия относит такие задачи, как минимум, к задачам экспоненциальной сложности. Традиционным путём решения такой задачи является симплекс-метод, перебирающий вершины многогранника.
С ростом размерности n прямые «превращаются» в гиперплоскости, а многоугольник в n-мерный многогранник. Целевая гиперплоскость задаётся нормалью, то есть ортогональным ей вектором {c1x1, с2x2, … сnxn}, и для любой точки z из плоскости, в сравнении с точкой x из заданной области, верно неравенство скалярных произведений (c,x)<=(c,z).
На целевой плоскости формируется решётка – рецептивное поле. Из каждой узловой точки выпускается ортогональный луч, который где-то достигает целевой области. Множество таких точек образует целевую проекцию. Рецептивное поле становится похожим на «пиксельную» матрицу, вроде той, что входит в устройство цифрового фотоаппарата. Кроме координат, у каждой точки рецептивного поля есть ещё параметр – расстояние до её целевой проекции. Чем ближе точка целевой проекции к целевой гиперплоскости, тем больше значение целевой функции в этой точке.
Учёные из ЮУрГУ Леонид Соколинский и Николай Ольховский приводят алгоритмы построения такого поля и определения координат его узловых точек по их порядковому номеру. Сложность вычислений при этом – квадратичная, O (n2).
А дальше на помощь приходит нейронная сеть, которая определяет минимум или максимум значения целевой функции и выдаёт по нему координаты соответствующего аргумента.
Для построения образа используется распараллеливание задачи на основе BSF – блочно-синхронной фермы. Узлы вычислительной системы делятся на «мастеров» и «рабочих»: первые ведут предварительную обработку и распределение данных, вторые – собственно вычисления. Масштабируемость алгоритма в зависимости от размерности задачи составляет O (n√n) – очень неплохо по времени.
Леонид Соколинский и Николай Ольховский провели вычислительный эксперимент на суперкомпьютере «Торнадо-ЮУрГУ» – одном из крупнейших в Европе университетских кластеров с привлечением генератора задач линейного программирования FraGenLP. Время построения образа растёт экспоненциально с ростом размерности n как 2O(n). Однако метод с привлечением нейронной сети работает с размерностями до 100 и числом неравенств-ограничений – до 100 000.
Нейронные сети помогают усовершенствовать симплекс-метод. Л. Соколинским и И. Соколинской описан апекс-метод. Он разрабатывает паттерны – обучающие наборы данных для нейросетей, способных находить решение задачи линейного программирования на основе её визуального представления – то есть образа, как описано выше. В апекс-методе действуют предиктор и корректор: первый вычисляет координаты некоторой точки из допустимой области, а корректор уже строит итерации, в итоге сходящиеся к точному решению задач линейного программирования.