Предпосылки метода
Ниже предлагается метод нахождения вершины многогранника допустимых решений задачи линейного программирования для начала процесса параллельного поиска оптимального решения. В основе метода лежит предположение, что для некоторых вершин образующие их грани имеют нормали, которые составляют с каждой из этих нормалей минимальные углы. При обобщении на произвольное пространство обсуждается возможность использования косинусов углов между нормалями в качестве функции меры.
Параллельный алгоритм решения задачи линейного программирования (ЛП) ориентирован на применение SPMD-технологии ("одна программа — много потоков данных"), наиболее эффективной при организации распределенных (в локальной вычислительной сети) и параллельных (в многопроцессорной вычислительной системе) вычислений. Метод базируется на отказе от традиционного ввода свободных переменных. Поиск решения производится непосредственно в n-мерном пространстве, что сохраняет наглядность "физического смысла" задачи.
Суть метода в следующем. Первоначально должна быть известна некоторая вершина многогранника допустимых решений вместе с системой уравнений границ на основе ограничений и возможных границ — координатных плоскостей, которым эта вершина удовлетворяет. Эта вершина определяет начальный или опорный план. Далее с помощью множества процессоров вычислительной системы или рабочих станций вычислительной сети производится одновременное и независимое смещение вдоль ребер, исходящих из вершины, для поиска одной или более вершин с "лучшим" (большим или меньшим, в зависимости от поставленной задачи) значением целевой функции. Процессоры переключаются на новую вершину, и процесс продолжается до решения задачи.
Нетрадиционность этого подхода обусловлена высокой размерностью задачи и необходимостью распараллеливания. Распараллеливание требует, в свою очередь, пересмотра алгоритмов, ранее ориентированных только на сокращение количества операций и не обеспечивающих эффективную, одновременную загрузку оборудования, тем более — локальной вычислительной сети.
В лекции 4 курса "Архитектура параллельных вычислительных систем" даются рекомендации по параллельному нахождению опорного плана на основе прямого перебора. На задачах малой размерности, рассматриваемых в качестве примеров, это вполне допустимо, однако практическая задача размерности n = 36 и с числом ограничений m = 18 привела к недопустимому времени счета. Компьютеры стали бы искать опорный план не один месяц, что связано с экспоненциальной сложностью такого перебора.
Таким образом, необходимо найти "быстрый" параллельный алгоритм нахождения опорного плана.
Здесь можно было бы воспользоваться одним из известных "традиционных" методов. Однако желание максимально использовать "физический смысл" задачи и потому остаться в n-мерном пространстве сулит выявление замечательных свойств выпуклого многогранника допустимых решений, которые скрыты при традиционном абстрагировании.
