close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Параллельное программирование
4. Лекция: Параллельные и сетевые технологии решения задач линейного
программирования: версия для печати и PDA
Предлагаются параллельные методы решения задач линейного и целочисленного линейного
программирования. Методы предполагают применение SPMD-технологии в вычислительных сетях и в
многопроцессорных вычислительных системах.
Предпосылки методов
Задачи линейной и нелинейной оптимизации, сетевые транспортные задачи — задачи
высокой сложности, подверженные "проклятию размерности". Ориентация на
применение многопроцессорных симметричных вычислительных систем в составе
персональных компьютеров или рабочих станций (параллельные вычисления) и на
применение сетевых технологий (распределенные вычисления) требует разработки
новых параллельных методов их решения. Эти методы должны быть лишены
недостатков "традиционных" методов: последовательного характера вычислений и
введения дополнительных переменных (для задач линейного программирования).
Анализ способов распараллеливания показывает эффективность распараллеливания
"по информации". Весьма перспективной поэтому становится SPMD-технология
программирования (Single Program — Multiple Data). При этой технологии
вычислительный процесс строится на основе единственной программы, запускаемой на
всех процессорах вычислительной системы или на многих станциях локальной сети.
Копии программы могут выполняться по разным ветвям алгоритма, обрабатывая
подмножества данных. Неизбежна синхронизация во времени и при обработке общих
данных.
Такая технология параллельного программирования и обусловила разработку
рассмотренных ниже методов. В то же время не отрицаются известные традиционные
методы, сокращающие общее число операций и исключающие перебор. Иной
методологический подход открывает дорогу решению задач большой размерности и
эффективной параллельной работе многих процессоров. Для ряда задач этот подход
еще нуждается в исследовании, уточнении области применения и развитии —
проведении тщательной математической экспертизы. Поэтому мы посчитали
необходимым осветить его подробно — для лучшего представления "физического
смысла", ощутимости пространственной модели задач и следующих из этого планов их
параллельного решения.
Метод прямого перебора при решении задачи линейного
программирования
Графический метод решения и его обобщение
Рассмотрим пример
z=c1x1+c2x2=2x1+5x2
при ограничениях
q1=x1
40
q2=x2
30
q3=x1+x2
50
max
(4.1)
и условиях x1
0, x2
0.
Каждое ограничение в двухмерном пространстве, n=2, определяет полуплоскость. Их
пересечение образует многоугольник R (рис. 4.1). Его грани — прямые, получены на
основе ограничений, в которых неравенства заменены равенствами.
q1 = 40
q2 = 30 (4.2)
q3 = 50
Эти равенства образуют уравнения границ или просто границы R.
Рис. 4.1. Графический метод решения задачи линейного программирования
Этот многоугольник (выпуклый многогранник; выпуклый, — ибо он остается по одну
сторону от любой прямой, проходящей через его ребро) представляет собой
допустимое множество решений R задачи ЛП.
Выберем произвольное значение, например, z=100 целевой функции. Прямая
2x1+5x2=100 показана на рисунке. Она пересекает ось x1 в точке x1=50 и ось x2 в точке
x2=20.
Отметим, что для
.
Т.к. dx1 и dx2 принадлежат прямой z, то скалярное произведение двух векторов,
которое здесь изображено, равно нулю в том случае, если вектор (c1, c2) =(2, 5)
перпендикулярен прямой z.
Увеличиваем значение z, передвигая (с помощью линейки) прямую — целевую —
функцию параллельно самой себе в сторону ее возрастания вдоль вектора (2, 5) до
тех пор, пока линейка не коснется последней возможной точки многогранника. R. Это
значение z и будет максимальным. В данном случае — это точка A = (x1=20, x2=30).
Сделаем важное замечание относительно многогранника R.
1. То, что он выпуклый, мы заметили ранее.
2. Нам были заданы три ограничения, отсекающие полуплоскости, но
определившие не все границы многогранника R. С "не закрытой" ими стороны
область R оказалась закрытой условиями неотрицательного решения задачи: x1
0, x2 0. Значит, эти выражения пришлось из ранга условий перевести в ранг
ограничений.
При этом не все условия могут быть переведены в ограничения. В нашей задаче
могло существовать некоторое ограничение q4 (на рисунке пунктиром), которое
бы определяло границу R слева, исключая границу x1 = 0. При этом граница x2
= 0 внизу осталась бы.
3. Другое важное замечание: решение задачи мы нашли на границе многогранника
R.
При этом возможны варианты:
1. Единственному конечному решению соответствует вершина R, как в нашем
примере.
2. Решением может являться бесконечное множество точек на грани R, например,
если бы ограничение q3 определяло бы прямую, параллельную z (уравнения q3 и
z были бы линейно зависимыми).
3. Система ограничений может определять "открытый" многогранник R,
включающий бесконечно удаленные точки, в которых достигается max z, т.е. max
z = ∞. Например, та же задача ЛП могла быть поставлена при отсутствии
ограничений q2 и q3 ( рис. 4.2). Перемещение z в сторону ее увеличения может
быть бесконечным, т.е. max z = ∞. Но если бы была поставлена задача z
min,
то она бы при этих ограничениях имела конечное и единственное решение, в
данном случае x1=x2=0.
Рис. 4.2. Случай отсутствия решения
Значит, имеет значение, с какой стороны многогранник R открыт: либо он позволяет
поиск решения вдоль "закрытых" стенок, либо допускает возможность "выпасть" за его
пределы, искать решение в бесконечности.
Тогда, как бы мы могли искать решение нашей первоначально поставленной задачи
ЛП?
Учитывая, что решение задачи — в одной из вершин R, мы сначала выпишем уравнения
всех прямых, ограничивающих R, т.е. уравнения всех его границ:
x1 = 40
x2 = 30
x1 + x2 = 50
x1 = 0
x2 = 0
Для нахождения координат каждой вершины R решаем совместно пару уравнений
прямых, образующих эту вершину, и находим значение z в найденной вершине:
Действительно, max z = 190 достигается в точке A.
Отметим возможноcть распараллеливания решения задачи на многопроцессорной ВС,
точнее, ВС SPMD-технологии.
В трехмерном пространстве ограничения и условия образуют пространственный
многогранник R, охваченный плоскостями-границами, записанными на основе
ограничений и условий, где неравенства заменены равенствами, а каждая плоскость z
= const, среди которых мы ищем решение, пересекает, "прорезает" его, деля на две
части ( рис. 4.3).
Рис. 4.3. Задача линейного программирования в трёхмерной области
На рисунке иллюстрируется задача ЛП:
z=c1x1+c2x2+c3x3
max
при ограничениях
q1=a11x1+a12x2+a13x3
b1
q2=a21x1+a22x2+a23x3
b2
и при условии
x1
0, x2
0, x3
0.
Две грани q1=b1 и q2=b2, ограничивают многогранник R — область возможных значений
переменных сверху (спереди) и справа. Слева, внизу и сзади пространственный
многогранник R ограничен условиями неотрицательности решения, ставшими
ограничениями x1 = 0, x2 = 0, x3 = 0. Плоскость z=const пересекает многогранник R.
Перемещая плоскость z параллельно себе, т.е. вдоль вектора (c1, c2, c3), в сторону
возрастания значений линейной формы z, мы находим решение. Здесь наглядно
показана очевидность того, что решение следует искать в вершинах R.
Однако графическое представление уже в трехмерном пространстве затруднительно, в
n-мерном пространстве нам необходимо действовать формально. Здесь существует ряд
проблем.
Во-первых, мы не представляем пространственной картины и не знаем, охватывают ли
заданные ограничения область R со всех сторон и какими условиями эти ограничения
должны быть дополнены без противоречий.
Во-вторых, мы не знаем, какие n ограничений, дополненных условиями, соответствуют
каждой конкретной вершине многогранника R, чтобы найти координаты этой вершины
и найти в ней значение целевой функции z. Значит, мы должны испытать все
возможные комбинации по n (в данном случае — тройки) ограничений и условий, т.е.
все возможные комбинации по три, составленные на основе всех потенциальных
границ- ограничений и условий.
Тогда при построении (параллельной!) вычислительной процедуры мы должны
опираться на то, что любая противоречивость в системе ограничений (в их состав мы
включили теперь и условия) выразится в неразрешимости системы трех уравнений,
составленной для нахождения координат очередной испытываемой вершины R. Т.е. в
этом случае вершина находится в бесконечности или содержит отрицательные
значения координат. Эта неразрешимость находится в процессе счета.
Оставаясь в области практических решений задач ЛП, т.е. в области инженерии и
экономики, примем предположение, что задача сформулирована корректно. Под этим
будем предполагать, что ограничения выбраны так, что она не имеет неограниченного
решения z = ∞.
Например, ставя задачу о максимизации прибыли от перевозки, не надо забывать о
том, что объем перевозок ограничен ресурсами страны, сообщества и т.д. В противном
случае мы получим тривиальное решение: чем больше, тем лучше.
Значит, мы будем предполагать, что в многограннике R обязательно есть вершины (их
координаты не отрицательны), в целом ограничивающие области изменения
переменных, и хотя бы в одной из этих вершин целевая функция — линейная форма z
принимает максимальное значение.
В свете сказанного будем также считать, что ограничения не противоречивы.
Противоречивые ограничения приводят к случаю R =
.
Например, ограничения
x + y
5
x + y
2
противоречивы.
Тогда, развивая на n-мерное пространство, мы можем реализовать следующую
стратегию поиска решения задачи ЛП.
Общий алгоритм перебора
1. На основе ограничений задачи q1 b1, ... qm bm строим систему граней
(гиперплоскостей) q1 = b1, ... qm = bm. Дополним эту систему граней всеми
потенциальными гранями на основе условий: x1 = 0, ... , xn = 0. Получим
систему m+n линейных уравнений, в общем случае избыточную и, возможно,
противоречивую.
2. Выбираем из этой системы очередную подсистему n линейных уравнений (всего
таких подсистем Cnm + n) и решаем ее.
Как известно, система n линейных уравнений имеет единственное решение в том
и только в том случае, если ранг r матрицы системы равен рангу расширенной
матрицы системы и равен n.
Можно в вычислительную процедуру включить анализ соответствующих матриц.
Можно ограничиться анализом только определителя системы, его отличием от
нуля, т.к. нас интересует лишь единственное решение. Однако ориентация на
современные вычислительные средства и их операционные системы позволяет
этого не делать.
Дело в том, что любой метод решения системы линейных уравнений в случае
неразрешимости системы или неоднозначности решения столкнется с операцией
деления на нуль — т.е. возникнет прерывание. Этим целесообразно активно
пользоваться для упрощения вычислительной процедуры.
После обработки прерывания необходимо предусмотреть переход к решению
следующей, очередной подсистемы линейных уравнений, если такие еще не
исчерпаны.
Однако традиционно при решении систем линейных уравнений в подобных
задачах используют метод Гаусса как обобщение метода последовательного
исключения. Метод Гаусса позволяет получать значения переменных
последовательно. Значит, их контроль на отрицательность производится
немедленно и останавливает дальнейший счет. Кроме того, попутные
преобразования системы уравнений позволяют динамически выявить тот случай,
когда матрица — алгебраическое дополнение диагонального элемента содержит
нулевую строку, т.е. определитель системы равен нулю. Это также
останавливает дальнейший анализ системы уравнений.
Если же получено единственное решение и все его компоненты x1, ... , xn не
отрицательны, то они могут определять вершину многогранника R. Могут, ибо
если среди уравнений подсистемы есть уравнения вида xj = 0, введенные в
состав граней на основе условий неотрицательности решений, и не вошли все
уравнения граней, обусловленные ограничениями задачи, то полученное
решение может противоречить некоторым "законным" ограничениям задачи. А
именно — не представленным в составе решенной подсистемы.
Поэтому в таком случае необходимо дополнительно проверить, принадлежит ли
действительно точка (x1, ... , xn) многограннику R, т.е. выполняются ли для
нее все не отображенные в подсистеме ограничения вида qj
указанные при постановке задачи ЛП.
bj, первоначально
3. Если найденная точка (x1, ... , xn) действительно является вершиной
многогранника R, определяемого ограничениями и условиями при постановке
задачи, отыскивается значение z(x1, ... , xn) = c1x1+c2x2+ ... +cnxn. Если
это значение превосходит ранее полученные при уже проведенном анализе
других вершин, оно запоминается вместе со значениями x1, ... , xn — для
продолжения поиска и анализа других вершин R или окончания решения задачи.
4. Перебор всех подсистем n линейных уравнений на основе m+n ограничений
(исходных и дополнительных), их число Cnm+n, полученные при их решении
координаты вершин многогранника R, обусловленного числом m основных
ограничений, позволяет выбрать ту вершину, которая порождает максимальное
(минимальное) значение целевой функции — линейной формы z.
Данная вычислительная процедура хорошо реализуется на многопроцессорных ВС.
Различные варианты подсистем линейных уравнений следует динамически
распределять между процессорами. А это, в свою очередь, полностью соответствует
SPMD-технологии "одна программа — много потоков данных".
О единственности решения. Мы видели по рисункам, что z = zmax может выполняться
на ребрах и гранях многогранника R. Если на ребре, то в двух сопряженных вершинах z
принимает одинаковое значение zmax. Если на гранях, то более чем в двух вершинах z =
zmax . Это легко переносится в n-мерное пространство.
Итак, указанная вычислительная процедура может привести к получению единственной
вершины X = (x1, ... , xn) многогранника R, в которой z(X) = zmax.
Пусть в r вершинах X1, ... , Xr многогранника R выполняются равенства z(Xj) = zmax,
j = 1, ... ,r. Построим выпуклую комбинацию векторов:
X = k1 X1 + k2 X2 + ... + kr Xr , k1 + k2 + ... + kr = 1, kj
0. (4.3)
Множество значений X, удовлетворяющих этому условию, определяет бесконечное
множество решений данной задачи ЛП.
Легко видеть, что данная вычислительная процедура предполагает любое соотношение
n
m.
Пример применения параллельной процедуры прямого перебора
Решим ту же задачу (2), подойдя формально, по правилу, пригодному для любой
размерности пространства.
Исходная система уравнений действительных или потенциальных плоскостей — граней
R имеет вид
(4.4)
Т.к. C23+2=10, исследование десяти комбинаций (подсистем уравнений) по два
уравнения из (9.4) выглядит следующим образом.
1.
Подставляем это уже готовое решение в третье ограничение задачи, x1+ x2
и отвергаем его, т.к. ограничение не выполняется.
2.
Решение удовлетворяет третьему ограничению x2
30.
Находим и запоминаем z(40, 10) = 130.
3.
Система не имеет решения.
4.
Решение удовлетворяет ограничениям
Находим z(40, 0) = 80. Если мы решаем задачу не на параллельном
компьютере, то сразу же видим, что новое значение z не превосходит уже
найденное. Поэтому и это решение отвергаем.
50,
5.
Решение x1 = 20, x2 = 30 удовлетворяет и третьему "основному" ограничению
задачи x1 40. Находим z(20, 30) = 190. Запоминаем его вместе с решением,
т.к. оно превосходит ранее полученное.
6.
Решение удовлетворяет всем ограничениям задачи. z(0, 30) = 150, что не
превосходит уже найденное значение. Решение отвергаем.
7.
Не имеет решения.
8.
Решение x1 = 0, x2 = 50 противоречит "основному" ограничению x2
Отвергаем его.
30.
Решение x1 = 50, x2 = 0 противоречит "основному" ограничению x1
Отвергаем его.
40.
9.
10.
Решение не противоречит "основным" ограничениям задачи. Однако z(0, 0) =
0, что не превосходит уже найденное значение. (Кстати, оно обеспечивает
решение задачи z
min.)
Итак, x1 = 20, x2 =30 обеспечивает zmax =190, т.е. является решением задачи ЛП.
Сложность алгоритма прямого перебора
Основным элементом решаемой задачи является решение системы n линейных
уравнений. Сложность решения такой системы можно считать полиномиальной O(n3).
Число решений определяется как Cnm+n. Чтобы найти зависимость сложности от
основных параметров n и m, определим, во сколько раз увеличивается сложность при
увеличении размерности n на единицу:
(4.5)
Если считать, что m соразмерно с n, т.е. m n, то увеличение размерности n на единицу
при больших n примерно в два раза увеличивает сложность задачи, т.е. ее сложность
определяется как O(2nn3). Это экспоненциальная сложность, практически сильно
ограничивающая размерность решаемых задач.
Простота параллельного алгоритма прямого перебора делает его привлекательным для
значений n порядка двух-трех десятков. Для большей размерности необходимо искать
алгоритмы полиномиальной сложности.
Параллельный аналог "симплекс-метода"
Пример
Рассмотрим задачу линейного программирования
max (4.6)
Z = 26x + 20y + 21z
при ограничениях
q1 = 2x + 7y - 76z + 222
0
q2 = - 8x +9y - 8z + 64
0
0 (4.7)
q3 = - 8x + 13y -24z + 96
q4 = - x - 6y - z + 70
0
q5 = - 2x - 7y - 2z + 90
0
q6 = 33x + 3y +22z - 165
0
и при условии x
0, y
0, z
0.
Ограничения и условия образуют многогранник R(ABCDEFGHKL) допустимых решений,
представленный на рис. 4.4.
Рис. 4.4. Многогранник допустимых решений
Формально мы не знаем R, и множество граней — действительных и возможных — этого
многогранника представлено системой уравнений:
q1 = 2x + 7y - 76z + 222 = 0
q2 = - 8x +9y - 8z + 64 = 0
q3 = - 8x + 13y -24z + 96 = 0
q4 = - x - 6y - z + 70 = 0
q5 = - 2x - 7y - 2z + 90 = 0 (4.8)
q6 = 33x + 3y +22z - 165 = 0
q7 = x = 0
q8 = y = 0
q9 = z = 0
В результате решения первой же подсистемы трех уравнений (n = 3) системы (4.8)
получаем координаты вершины E многогранника R
(4.9)
Постараемся "сместиться" в ту вершину, смежную вершине E, т.е. соединенную с ней
ребром (в одну из вершин A, D, L, F), в которой целевая функция Z имеет максимальное
значение, превышающее Z(E).
Ребра, исходящие из вершины, определяются подсистемами n-1 плоскостей,
пересекающихся в этой вершине, т.е. образующими ее.
В данном случае подсистема
определяет несуществующее ребро. Пока мы
знаем это только по рисунку. Подсистема
определяет ребро EA, подсистема
определяет ребро ED. А вот ребра EL и EF мы пока не знаем, т.к. не знаем (формально,
а не по рисунку!) все плоскости (плоскость q5), пересекающиеся в E. Это значит, что из
каждой вершины в общем случае исходят не менее n ребер, а сколько в
действительности — предстоит уточнить. (Представьте себе R — бриллиант
классической огранки.)
Значит, q1, q2, q3 — это лишь наше начальное представление о множестве плоскостей
— граней, пересекающихся в вершине E. Нам необходимо развить это представление до
полного.
Тогда выясним все множество граней, образующих вершину E, подстановкой ее
координат во все другие уравнения (9.8) и испытанием на получение тождества.
Находим q5(13, 8, 4) 0. Добавляем q5 в (4.9), полагаем полностью известным число
p = 4 ребер, образующих вершину E. Т.е. вместо (4.9) получаем
(4.10)
Каждую возможную грань, определяемую двумя (n-1) уравнениями плоскостей из
(4.10), будем решать совместно со всеми плоскостями из (4.8), не вошедшими в (4.10),
— с гранями q4, q6, q7, q8, q9.
Первая такая система имеет вид
(4.11)
Ее решение (535, 8,7, -517,2) содержит отрицательную составляющую. Т.е. эта
точка не принадлежит R. Если бы решение было не отрицательным, мы должны были
бы проверить выполнение всех ограничений (4.7), не представленных в (4.11).
Можно показать, что в выпуклом многограннике несуществующее ребро не вызовет
появления "ложной" вершины, и достаточно проверить (4.7).
Системы
имеют не положительное решение.
Следующая испытываемая система линейных уравнений на основе двух уравнений из
(4.10) и не входящих в (4.10) уравнений из (4.8), имеет вид
Ее решение — приблизительно точка (5,2, 9,4, 4) не является вершиной R, т.к. не
удовлетворяет всем ограничениям (9.7), q5(5,2, 9,4, 4) < 0.
Следующая испытываемая система имеет вид
Ее решением является вершина A (3, 0, 3), Z(A) = 141 < 592.
Т.к. мы нашли вершину на "другом конце" ребра, анализ данного ребра прекращаем.
Следующее исследуемое ребро, исходящее из вершины E, определяется подсистемой
которая должна решаться совместно с уравнениями q4 = 0, q6 = 0, q7 = 0, q8 = 0, q9 =
0.
Первая же система
592.
определяет вершину L (6, 10, 4). Однако Z(L) = 440 <
Следующее возможное ребро, исходящее из вершины E, определяется комбинацией
Решая ее совместно с другими гранями R, - q4 = 0, q6 = 0, q7 = 0, q8 = 0, q9 = 0,
пытаемся найти другую вершину в R, смежную E.
Очередная решаемая система уравнений
имеет не отрицательное решение (13,625, 8,7, 4,175). Проверяем выполнение
ограничений (9.7), не представленных в решенной системе. Находим, что q1(13,625,
8,7, 4,195) < 0. Этой проверки достаточно для вывода о том, что найденная точка не
является вершиной многогранника R.
Системы
и
имеют решение в отрицательной области.
Система
определяет вершину D (6, 0, 2), для которой Z(D) = 198 < 592.
Следующее возможное ребро по (4.10) определяется парой граней
Решаем совместно с остальными гранями, не входящими в (10): q4 = 0, q6 = 0, q7 = 0,
q8 = 0, q9 = 0.
Система
не имеет решения, ранг матрицы системы не равен рангу расширенной матрицы.
Система
имеет отрицательное решение.
Система
имеет неотрицательное решение, при котором q1 < 0. Найденная
точка не является вершиной R.
Система
не имеет решения.
Система
имеет неотрицательное решение — точку F (17, 8, 0), удовлетворяющую всем
ограничениям: q1(17, 8, 0) > 0, q3 (17, 8, 0) > 0, q4(17, 8, 0) > 0, q6(17, 8, 0)
> 0. Точка F — вершина многогранника R. Z(F) = 602 > 592.
Таким образом, мы нашли вершину F, смежную вершине E, с превышающим значением
целевой функции. Однако поиск всех вершин на основе (4.10), смежных вершин E,
следует продолжить. Ведь формально возможна и другая вершина, с еще большим
значением целевой функции.
Перебор продолжаем на основе ребра
хотя мы видим по рисунку, что такого ребра нет.
Ищем точки пересечения этого ребра со всеми гранями R, не вошедшими в (4.10).
Система уравнений
имеет решение (0,875, 10, 9,125).
При проверке выполнения первого же ограничения оказывается, что q1(0,875, 10,
9,125) < 0. Найденная точка действительно не является вершиной R.
Система
имеет отрицательное решение.
Система
ограничению.
имеет решение (0, 10,144, 9,5), не удовлетворяющее первому же
Система
имеет отрицательное решение.
Система
имеет не отрицательное решение (22,96, 6,44, 0), не
удовлетворяющее ограничениям.
Таким образом, анализ всех возможных вершин, смежных вершине E, закончен. Мы
нашли единственную вершину F(17, 8, 0), где значение целевой функции Z(17, 8,
0) = 602 превышает ее значение в точке E. Система уравнений, определившая эту
вершину, имеет вид
(4.12)
Если бы мы нашли несколько вершин с одинаковым значением целевой функции, то
были бы возможны различные стратегии дальнейших действий. Мы здесь
рассматриваем случай, когда для дальнейшего поиска фиксируется одна из таких
вершин. Других граней, которым принадлежит точка F, нет. Смещаемся в эту вершину,
полагаем p = 3.
Начинаем весь процесс поиска смежной вершины с максимальным (среди смежных
вершин) значением целевой функции Z, обязательно превышающим значение Z(F).
Первое возможное ребро, исходящее из F, определяется уравнениями
Однако эта комбинация возвращает нас в ту вершину, которую мы уже исследовали.
Поэтому сразу же переходим к следующему возможному ребру
решая его совместно с гранями q1, q3, q4, q6, q7, q8.
Система
решалась ранее. Ее решение неположительно. (Если мы переупорядочим уравнения
системы по индексам, то получим индексный код, по которому будем входить в таблицу
с информацией о решенной ранее системе. Так мы реализуем самообучение в процессе
решения.)
Система
компонент.
решалась ранее. Ее решение также содержит отрицательный
Система
решается впервые. Ее не отрицательное решение не удовлетворяет всем ограничениям,
q3(17,8, 8,7, 0) < 0.
Системы
компоненты.
и
имеют решения, содержащие отрицательные
Система
определяет вершину C, Z(8, 0, 0) = 208 < 602.
Следующее исследуемое ребро определяется системой уравнений
Система
исследовалась раньше. Она не имеет решения.
Система
решалась ранее. Она определяет точку, не являющуюся вершиной R.
Система
460 < 602.
решается впервые. Она определяет точку K. Однако Z(10, 10, 0) =
Таким образом, нам не удалось сместиться из вершины F в вершину с большим
значением Z. Значит, найденная точка F определяет решение задачи ЛП.
Общий алгоритм
1. Формируем систему m + n уравнений
(4.13)
2. действительных и возможных границ многогранника R допустимых решений. Эта
система уравнений отображает m заданных ограничений и n условий
неотрицательности решения.
3. Решая совместно подмножество n уравнений этой системы, находим одну из
вершин X0 многогранника R. Находим значение z0 целевой функции в точке X0.
4. Дополним систему n уравнений, первоначально породившую вершину X0, теми
уравнениями, которым X0 также удовлетворяет. Получим систему p
уравнений, порождающих вершину X0.
n
(4.14)
5. Примечание 1. Теперь наша задача — переместиться вдоль одного из ребер,
исходящих из вершины X0, в смежную вершину X1, такую, что Z(X1) > Z(X0). При
этом, желая ускорить процесс (хотя выбор стратегии нуждается в обосновании),
будем среди всех смежных вершин искать ту вершину X1, в которой достигается
максимальное увеличение значения целевой функции. Каждое ребро
описывается системой n - 1 уравнений из состава p уравнений, породивших
испытываемую вершину X0. Введем переменную p, первоначально приняв p = n
6. Выбирая из (4.14) по n - 1 уравнений, будем получать систему, которая
определяет некоторое ребро, исходящее из X0. Всего таких подсистем может
быть Cpn - 1.
7. Последовательно испытываем данное ребро на его пересечение с теми из m
гранями из (4.13), которые не вошли в состав (4.14). Т.е. дополняем нашу
систему n - 1 уравнений очередной испытываемой гранью. Получаем систему n
уравнений и решаем ее. Возможны следующие варианты.
1. Система не имеет решения, имеет не единственное решение или решение
содержит отрицательные компоненты. Переходим к испытанию
следующей грани.
2. Система имеет неотрицательное решение, но это решение не
удовлетворяет всем m ограничениям задачи, т.е. находится вне R.
Переходим к испытанию следующей грани.
3. Система имеет неотрицательное решение X1 X0, удовлетворяющее всем m
ограничениям задачи. Значит, найдена смежная вершина. Если Z(X1) <
Z(X0), переходим к испытанию следующего ребра — к выполнению шага
6. Если Z(X1) = Z(X0), запоминаем вершину X1. Это для случая, если в
результате проводимых испытаний оказалось, что точка X0 — решение
задачи. Тогда необходимо знать все вершины, образующие решение,
чтобы построить общее параметрическое выражение. Переходим к
испытанию следующего ребра. Если Z(X1) > Z(X0), запоминаем точку X1 в
данном качестве и переходим к испытанию следующего ребра.
Примечание 2. Возможна стратегия, при которой смещение производится в
первую же найденную вершину с превышающим значением целевой функции.
Есть вариант, что это — более правильная стратегия, т.к. значительное
увеличение значения целевой функции на данном шаге может привести в
дальнейшем к увеличению числа шагов: мы ничего не знаем о особенностях
многогранника решений. Мы же здесь рассматриваем стратегию, при которой
отыскивается смежная вершина с максимальным превышением целевой
функции.
8. Перебрав все грани для одной подсистемы n - 1 линейных уравнений (для
одного ребра), формируем другую подсистему таких уравнений на основе (4.14).
Анализируем ее совместно со всеми m + n - p уравнениями из (4.13).
9. Таким образом, исследовав все ребра, исходящие из X0, мы можем найти ту
смежную вершину X1, где целевая функция максимально превышает ее значение
в исходной вершине. Перемещаемся в эту вершину, полагая X0 = X1. Система
(4.14) теперь — та система n уравнений, решение которой породило X1.
Дополняем ее уравнениями других граней, проходящих через X1. Получаем p n.
Начинаем весь процесс перемещения сначала. Однако первое ребро,
определяемое первыми n - 1 уравнениями (4.14), это ребро, которое ведет в
вершину, из которой мы вышли. Т.е. первую комбинацию n - 1 граней следует
пропустить.
10. Если не удается найти вершину, в которой значение целевой функции
превышает ранее найденное, то мы нашли решение. Одновременно мы нашли и
сохранили те смежные (проанализированной вершине!) вершины, в которых
значения целевой функции равны. Однако мы могли найти не все вершины,
обладающие одним, максимальным, значением Z. Ведь мы двигались только по
ребрам, исходящим из предыдущей анализируемой вершины. "Напротив" этой
вершины могут быть другие вершины с тем же значением целевой функции, и в
эти вершины не ведут ребра из данной. Однако на основе свойств выпуклого
многогранника можно заключить, что отношение взаимной смежности связывает
все вершины, образующие решение задачи ЛП. Т.е. вершины-решения, не
смежные друг другу, являются смежными другим вершинам-решениям.
Существует путь вдоль ребер, связывающий вершины-решения. Тогда можно
построить алгоритм выявления всех вершин R — решений задачи ЛП.
1. Пусть найденные уже вершины-решения образуют множество A. Дополним
его последней найденной вершиной. Выбираем первую из ранее
запомнившихся вершин из A с равным, максимальным, значением целевой
функции и делаем ее опорной, X0.
2. Выполняем шаги 4-8 для поиска вершины многогранника R с более
высоким значением Z, чем значение Z(X0). Конечно, мы такой вершины
найти не можем. Но мы можем найти новую вершину X, не входящую в
множество A, такую, что Z(X) = Z(X0). Включаем вершину X в A, полагаем
X0 := X. Продолжаем выполнение данного пункта до тех пор, пока
множество A не перестанет пополняться новыми вершинами. Производим
параметрическую запись (4.4) общего решения задачи.
Сложность алгоритма
Если считать, что чаще всего из одной вершины исходят n граней, то число решаемых
систем n линейных уравнений при поиске смежных вершин определяется как
r = n × (m + n - n) = n × m.
Число вершин k, по которым производится перемещение в поисках решения,
предсказать трудно. Однако очевидно, что k << Cnm + n, т.к. лишь локально
затрагивается некоторый "бок" многогранника R. Считая, как и раньше, m
n, можно
оценить сложность решения данным методом, как O(kn5). Эта сложность является
полиномиальной.
План параллельных вычислений
Воспользуемся в основном той же схемой вычислений, что и в разделе 4.1.
Пусть все процессоры ВС или используемые станции локальной сети обладают своим
номером и знают количество используемых средств. Как показывалось ранее, они все
начинают решать "свои" системы линейных уравнений. Здесь уже можно применить
различные стратегии. Одна из них: пусть хотя бы один процессор нашел вершину
многогранника R. Ее можно взять за вершину X0.
Другая стратегия заключается в том, чтобы дать возможность всем участвующим
процессорам найти по одной вершине R. Вершину с максимальным значением целевой
функции Z можно взять за X0.
Выбрав вершину X0, все процессоры начинают решать "свои" варианты систем
линейных уравнений в поисках смежных вершин с превышающим значением целевой
функции. Согласовав действия при нахождении вершины X1 и приняв X0 := X1, они
продолжают процесс движения по ребрам R.
Параллельное решение задачи целочисленного линейного
программирования
Методы параллельного решения задачи ЛП, основанные на непосредственном
перемещении по ребрам многогранника решений, не привлекая дополнительных
переменных, способствуют построению наглядного метода решения соответствующей
задачи линейного программирования (задачи ЦЛП). Под соответствием мы понимаем
добавление условия целочисленности решения при той же формальной постановке
задачи ЛП.
Такой метод основан на захвате в "вилку" некоторой целой точки внутри
многогранника решений, вблизи точки решения задачи ЛП.
Рассмотрим пример.
Решим задачу ЦЛП:
Z = x - 3y + 3z
max
при ограничениях
2x + y - z
4x - 3y
4
2
-3x + 2y + z
6
и при условиях x, y, z
0, целые.
Решение задачи ЛП достигается (рис. 4.5) в точке (0,5, 0, 7,5), которая является
результатом решения системы уравнений — граней
q2 = 4x - 3y - 2 = 0
q3 = -3x + 2y + z - 6 = 0
q5 = y = 0
Значение целевой функции Z(0,5, 0, 7,5) = 23.
Рис. 4.5. Решение задачи целочисленного линейного программирования
Положим Δ Z = 4, и найдем все точки пересечения образовавшейся "целевой
плоскости" с ребрами, исходящими из вершины-решения. Для ребра (q2, q3)
Все координаты при переходе из вершины-решения в найденную точку превысили
некоторые целые значения. Причем, одна из координат "преодолела" именно
ближайшее целое, заставив другие координаты "преодолеть" большее число единиц.
Для ребра (q2, q5)
Не все координаты "преодолели" ближайшее целое значение: x остался внутри
интервала (0, 1).
Для ребра (q3, q5)
Опять не все координаты "преодолели" ближайшее целое: x остался внутри интервала
(0, 1).
Значит, только в точке
наблюдается "преодоление" целых значений по
сравнению с точкой (0,5, 0, 7,5), представляющей точное решение задачи ЛП. Т.е.
нам удалось захватить решение задачи ЦЛП в "вилку". При этом точка (2, 2, 8),
"преодоление" которой произошло, — возможное решение задачи ЦЛП.
Однако для того, чтобы координате z преодолеть ближайшее целое значение,
координатам x и y пришлось преодолеть по два целых значения. Поэтому закономерен
вопрос о том, нет ли внутри отсеченной с помощью Δ Z области целых точек, где z
преодолевает ближайшее целое с меньшей ценой для других координат. Ведь значение
целевой функции в таких точках было бы больше.
Половиним "вилку". Положим Δ Z = 2 и найдем точки пересечения "целевой плоскости"
Z = 21 c ребрами, исходящими из вершины-решения задачи ЛП:
Видим, что есть координата,
, которая не "преодолела" ближайшее целое,
определяемое решением задачи ЛП. Там z =7,5. Очевидно, что на других двух ребрах
ситуация тем более останется прежней.
Вновь половиним "вилку" в сторону увеличения значения Δ Z, пытаясь вплотную
подойти к возможной целой точке, где значение Z максимально. Положим Δ Z = 3.
Найдем точки пересечения "целевой плоскости" Z = 20 с ребрами, исходящими из
вершины-решения задачи ЛП.
Решаем первую систему.
Решение "преодолело" целые значения по всем координатам. Не менее чем по одной
координате произошло округление до ближайшего целого. Более того, по всем
координатам получены целые значения. Дальнейший поиск прекращается, решение
задачи ЦЛП найдено.
Если бы решение не совпало с целым, мы проверили бы точки пересечения "целевой
плоскости" с другими ребрами. Вместе с тем, это можно и не делать, т.к. для меньшего
значения Z = 19 уже установлен факт "непреодоления" там целых значений. Так что
нам осталось бы только выполнить округление.
Рассмотренные в лекции методы решения задач линейного программирования имеют
важную методологическую направленность, обусловленную наглядностью,
ощутимостью, чувством "физического смысла" задач. Их роль не осмысленна до конца,
но они позволяют эффективно распараллеливать вычисления. В этом смысле такие
методы, как симплекс-метод, венгерский метод ориентированы исключительно на
последовательные вычисления, но зато полностью исключают перебор. Для большой
размерности задачи введение дополнительных переменных, что предполагается в
симплекс-методе, может показаться нежелательным.
Предложен вполне практический метод (хотя и не описан алгоритмически) решения
задачи ЦЛП, опирающийся на нахождение хотя бы одного решения соответствующей
задачи ЛП. Мы не затронули вопроса о единственности решения — как задачи ЛП, так
и задачи ЦЛП, о произвольном числе ребер, образующих вершину-решение задачи ЛП.
Метод, несомненно, подлежит развитию. Его достоинство заключается в том, что он, по
сравнению с методом "ветвей и границ", не требует многократного решения задачи ЛП
с динамически уточняющимися и размножающимися ограничениями.
Можно указать на осуществляемое практическое применение предлагаемых методов в
качестве тестовых задач для оценки эффективности многопроцессорных ВС,
использующих принципы SPMD-технологии ("единственная программа — много потоков
данных"). Эти же методы используются при разработке сетевых технологий решения
сложных задач.
1/--страниц
Пожаловаться на содержимое документа