Параллельный алгоритм решения
Исследование плана параллельного решения и формирование алгоритма будем сопровождать примером, для проверки правильности заимствованным в [15]. Для краткости условия (5.3) и (5.4) опущены.
Пример.
Z=7x11+8x12+5x13+3x14+2x21+4x22+5x23+ +9x24+6x31+3x32+1x33+2x34
при ограничениях
x11 + x12 + x13 + x14 = 11
x21 + x22 + x23 + x24 = 11
x31 + x32 + x33 + x34 = 8
x11 + x21 + x31 = 5 (5.6)
x12 + x22 + x32 = 9
x13 + x23 + x33 = 9
x14 + x24 + x34 = 7
Введем линейный массив переменных xij = yk, где k = (i - 1)n + j.
Исключим из рассмотрения последнее уравнение. Система уравнений граней (действительных и возможных) многогранника решений примет вид
y1 + y2 + y3 + y4 = 11
y5 + y6 + y7 + y8 = 11
y9 + y10 + y11 + y12 = 8 (5.7)
y1+y5+ y9=5
y2+y6+y10 = 9
y3+ y7+ y11 = 9
yk = 0, k = 1, 2, ... , 12.
Итак, на первом этапе задача свелась к выбору и анализу комбинаций по 12 - 6 = 6нулевых значений координат искомой вершины многогранника решений. Выполняя подстановку выбранной комбинации в (5.7), мы можем решить образовавшуюся систему шести уравнений с шестью неизвестными. Таким образом, мы сможем найти координаты некоторой вершины.
Комбинации по шесть нулевых значений координат ("комбинации нулей") следует выбирать так, чтобы не обратилась в нуль левая часть хотя бы одного уравнения (5.7), включая исключенное уравнение. Например, комбинация, где y1 = y2 = y3 = y4 = 0, недопустима.
Найдем дополнительные контрольные ограничения: чтобы решение было не отрицательным, необходимо, чтобы любое значение yk, k = 1, ... , m ? n, не превышало значение yk — величины правой части того уравнения, в котором оно участвует.
Тогда в нашем примере y1
y12 = 7. Здесь при оценке y4, y8, y12учтено последнее уравнение в (5.6).
Воспользуемся векторной формой представления, чтобы подготовить удобные, нетрудоемкие матричные преобразования. А именно, наша система m + n - 1линейных уравнений-ограничений имеет вид
AY = B,
где A— нуль- единичная матрица, Y— столбец переменных, B— столбец свободных членов:
 | (5.8) |
- Положим l = 0.
- Положим l := l + 1, yl = 0. Исключим из матрицы A столбец, соответствующий этой переменной.
- Проверяем, появилась ли в A строка, содержащая только нулевые элементы, или обратилась ли в нуль левая часть исключенного уравнения. (Предполагаем, что все свободные члены уравнений больше нуля.) При положительном результате анализа выполняем шаг 5. В противном случае — следующий шаг.
- Для каждой s-й строки A выделяем множество {ys}переменных, соответствующих единичным элементам. Проверяем:При отрицательном результате анализа (свободный член превышает сумму верхних оценок переменных) выполняем шаг 5. В случае успешной проверки 3 и 4 выполняем шаг 6.
- Данный шаг выполняется, если испытываемое значение yl = 0 выбрано неудачно. Отменяем исключение столбца, соответствующего переменной yl, и выполняем шаг 2.
- Фиксируем yl = 0, и если комбинация нулей сформирована не полностью, выполняем шаг 2.
Продолжим рассмотрение примера.
Полагаем y1 = 0. Это не приводит к нарушению оценок, указанных в алгоритме.
Полагаем y2 = 0. Это также не приводит к нарушению оценок.
Полагаем y3 = 0. Нулевые строки не появились. Однако в первой строке осталась единственная единица, соответствующая переменной y4. Т.к. y4= 7 < 11, отвергаем нулевое значение переменной.
Полагаем y4 = 0. Нулевые строки не появились, однако в первой же строке осталась единственная единица, соответствующая переменной y3. Т.к. y3 = 9 < 11, отвергаем и это значение.
Полагаем y5 = 0. Это не приводит к нарушению оценок.
Полагаем y6 = 0. В пятой строке остается единственная единица, соответствующая y10. Т.к. y10 = 8 < 9, отвергаем нулевое значение переменной.
Полагаем y7 = 0, что не приводит к нарушению оценок.
Значение y8 = 0 приводит к нарушению оценки во втором уравнении.
Значение y9 = 0 приводит к появлению нулевой строки.
Значение y10 = 0 не приводит к нарушению оценок.
Значение y11 = 0 также не приводит к нарушению оценок.
Итак, комбинация нулей найдена. Это отмеченные в (5.8) значения
y1 = 0, y2 = 0, y5 = 0, y7 = 0, y10 = 0, y11 = 0. (5.9)
Для нахождения других значений переменных необходимо решить систему уравнений на основе (5.8), после исключения нулевых столбцов
Найдем все строки матрицы A, содержащие не более одного единичного элемента. Это строки, определяющие компоненты решения y3
= 9, y6 = 9, y9 = 5.
Выполним подстановку, последовательно находя в столбцах найденных переменных единицы (не более одной) и корректируя правые части вычитанием найденных значений. Строки и столбцы, соответствующие найденным значениям переменных, исключаем из матрицы A.
Такой прием подстановки можно повторять до исчерпания уравнений, содержащих в левой части единственную переменную.
В нашем примере после подстановки найденных значений в уравнения 1, 2 и 3 получаем систему
В ней все уравнения имеют единственную переменную. Они определяют решение y4 = 2, y8 = 2, y12 = 3.
Таким образом, нам не пришлось пока воспользоваться методом Гаусса, но мы нашли допустимое решение Y0 = (0, 0, 9, 2, 0, 9, 0, 2, 5, 0, 0, 3), для которого выполняются ограничения задачи. Вектор Y0 определяет некоторую вершину многогранника допустимых решений, со значением целевой функции Z(Y0) = 141.
Примем следующий план решения, соответствующий рассмотренному ранее плану параллельного решения задач линейного программирования.
Для перебора всех смежных вершин необходимо в комбинации нулей, определивших вершину Y0, поочередно исключать одно значение yr = 0 (это определит одно из исходящих ребер) и оставшуюся систему решать совместно поочередно со всеми другими уравнениями вида ys = 0, не входящими в комбинацию нулей. Этим мы будем совершать перемещение в смежные вершины. Находя значение Z для каждого такого решения Y1 там, где оно существует, можно найти вершину с меньшим значением целевой функции. "Перебравшись" в эту вершину (приняв ее за Y0 ), мы можем продолжить анализ смежных ей вершин и т.д.
Решение задачи найдено в том случае, если после перебора всех смежных вершин не отыскивается вершина с меньшим значением целевой функции.
Продолжим рассмотрение примера.
Итак, (5.8) — исходный вид системы уравнений, (5.9) — комбинация нулей ("отсутствующие" столбцы в (5.7) выделены), (5.8) и (5.9) определяют вершину Y0.
Исключим из (5.9) уравнение y1 = 0, а оставшуюся систему, с учетом остальных нулей из комбинации (5.9), будем решать совместно с уравнениями
y3 = 0, y4 = 0, y6 = 0, y8 = 0, y9 = 0, y12 = 0. (5.10)
Значит, в (5.8) положим первоначально y3 = 0 вместо y1 = 0. Левая часть шестого уравнения (последняя строка матрицы А) обратилась в нуль.
Положим y4 = 0 вместо y1 = 0. Получим систему
Из нее, как и ранее, за два шага подстановки находим y3 = 9, y6 = 9, y9 = 5, а затем — y1 = 2, y8 = 2, y12 = 3.
Таким образом, найдено новое допустимое решение Y1 = (2, 0, 9, 0, 0, 9, 0, 2, 5, 0, 0, 3). Однако Z(Y1) =149 > 141. Найденную вершину отвергаем. Вместе с тем, т.к. мы нашли вершину "на другом конце" анализируемого ребра, то и анализ этого ребра прекращаем.
Приступаем к анализу следующего ребра, исключив из (5.9) уравнение y2 = 0. Оставшуюся систему, с учетом остальных нулей из (5.9), будем решать совместно с теми же уравнениями (5.10).
Положим в (5.8) y3 = 0 вместо y2 = 0. Последняя строка матрицы A стала нулевой.
Замена y4 = 0 вместо y2 = 0 приводит к системе
На ее основе находим новый вектор — допустимое решение Y1 = (0, 2, 9, 0, 0, 9, 0, 2, 5, 0, 0, 3). Однако Z(Y1) = 151 > 141. Найденную вершину также отвергаем. Ребро исследовано полностью.
Исключим из (5.9) уравнение y5 = 0, а оставшуюся систему, с учетом остальных нулей из (5.9), будем решать совместно с теми же уравнениями (5.10).
Положим в (5.8) y3 = 0 вместо y5 = 0. Последняя строка матрицы A обратится в нуль.
Положим y4 = 0 вместо y5 = 0. В первом уравнении не выполняется ограничение по y3 (y3 = 9).
Положим y6 = 0 вместо y5 = 0. Пятая строка A обратилась в нулевую.
Положим y8 = 0 вместо y5 = 0.
Получим систему уравнений
Находим y3 = 9, y6 = 9 и после подстановки — y4 = 2, y5 = 2. Вновь выполняем подстановку, находим y9 = 3, и после следующей подстановки y12 = 5.
Итак, получена вершина Y1 = (0, 0, 9, 2, 2, 9, 0, 0, 3, 0, 0, 5). Т.к. Z(Y1) = 119 < 141, полагаем Y0 := Y1 и начинаем пробу возможных перемещений вдоль ребер из найденной вершины многогранника решений в вершину с меньшим значением целевой функции:
Запишем вновь аналогично (5.8) и (5.9) систему уравнений, решением которой является вершина Y0, отметив в ней "отсутствующие" столбцы:
 | (5.11) |
y1 = 0, y2 = 0, y7 = 0, y8 = 0, y10 = 0, y11 = 0. (5.12)
Начнем движение по ребрам из данной вершины. Для этого будем исключать из (5.12) одно из уравнений, а оставшуюся систему будем решать совместно с не вошедшими в (5.12) уравнениями:
y3 = 0, y4 = 0, y5 = 0, y6 = 0, y9 = 0, y12 = 0. (5.13)
При этом надо учесть, что могут формироваться ранее исследованные комбинации нулей. (Комбинации нулей удобно метить индексным кодом, который следует запоминать для исключения повторного анализа.)
Положим в (5.13) y3 = 0 вместо y1 = 0. Последняя строка матрицы A станет нулевой.
Замена y1 = 0 уравнением y4 = 0 приводит к системе
Решаем с помощью подстановок, находим Y1 = (2, 0, 9, 0, 2, 9, 0, 0, 3, 0, 0, 5). Т.к. Z(Y1) = 127 > 119, найденную вершину отвергаем.
Примечание. Нам вновь не пришлось воспользоваться схемой Гаусса. По-видимому, вид уравнений и вхождение каждой переменной не более чем в два уравнения позволяют довольствоваться простой подстановкой. Ниже мы исследуем это подробнее.
Переходим к другому ребру, заменяя в (5.12) уравнение y2 = 0 уравнениями из (5.13).
Замена y3 = 0 вместо y2 = 0 приводит к тому, что последняя строка матрицы A становится нулевой.
Замена y4 = 0 вместо y2 = 0 приводит к системе уравнений
Находим с помощью подстановок Y1 = (0, 2, 9, 0, 4, 7, 0, 0, 1, 0, 0, 7). Т.к. Z(Y1) = 127 > 119, найденную вершину отвергаем и переходим к анализу следующего ребра.
Замена y3 = 0 вместо y7 = 0 приводит к тому, что в первом уравнении (9.25) не выполняется условие по ограничению y4 (y4 = 7).
Замена y4 = 0 вместо y7 = 0 приводит к тому, что в первом же уравнении (9.25) не выполняется условие по ограничению y3 (y3 = 9).
Замена y5 = 0 вместо y7 = 0 приводит к системе
Находим Y1 = (0, 0, 7, 4, 0, 9, 2, 0, 5, 0, 0, 3). Однако Z(Y1) = 129 > 119.
Переходим к анализу следующего ребра, поочередно заменяя уравнениями из (5.13) уравнение y8 = 0 из (5.11).
Замена y3 = 0 вместо y8 = 0 приводит к образованию последней нулевой строки матрицы A.
Замена y4 = 0 вместо y8 = 0 приводит к тому, что в первом уравнении не выполняется условие по ограничению y3 (y3 = 9).
Замена y5 = 0 вместо y8 = 0 приводит к системе
Находим Y1 = (0, 0, 9, 2, 0, 9, 0, 2, 5, 0, 0, 3). Т.к. Z(Y1) = 141 > 119, найденную вершину отвергаем.
Переходим к анализу следующего ребра, поочередно заменяя уравнениями из (5.13) уравнение y10 = 0 из (5.11).
Замена y3 = 0 вместо y10 = 0 приводит к тому, что в первом уравнении (5.11) не выполняется условие по ограничению y4 (y4 = 7).
Замена y4 = 0 вместо y10 = 0 приводит к тому, в первом же уравнении (5.11) не выполняется условие по ограничению y3 (y3 = 9).
Замена y5 = 0 вместо y10 = 0 приводит к тому, что во втором уравнении (5.11) не выполняется условие по ограничению y6 (y6= 9).
Замена y6 = 0 вместо y10 = 0 приводит к тому, что во втором же уравнении (5.11) не выполняется условие по ограничению y5 (y5 = 5).
Замена y9 = 0 вместо y10 = 0 приводит к системе
Находим Y1 = (0, 0, 9, 2, 5, 6, 0, 0, 0, 3, 0, 5). Т.к. Z(Y1) = 104 < 119, "перемещаемся" в найденную вершину с меньшим значением целевой функции.
Новая вершина характеризуется системой уравнений
y1 = 0, y2 = 0, y7 = 0, y8 = 0, y9 = 0, y11 = 0. (5.14)
Перепишем систему (5.11), выделив "отсутствующие" столбцы, вследствие (5.14):
 | (5.15) |
y3 = 0, y4 = 0, y5 = 0, y6 = 0, y10 = 0, y12 = 0 (5.16)
Замена y1 = 0 на y3 = 0 приводит к появлению (последней) нулевой строки матрицы A.
Замена y4 = 0 вместо y1 = 0 приводит к системе
Отсюда Y1 = (2, 0, 9, 0, 3, 8, 0, 0, 0, 1, 0, 7). Т.к. Z(Y1) = 114 > 104, исследуем следующее ребро, исключив в системе (5.14) уравнение y2 = 0 и заменяя его последовательно уравнениями из (5.16).
Замена y4 = 0 вместо y2 = 0 приводит к системе
Находим Y1 = (0, 2, 9, 0, 5, 6, 0, 0, 0, 1, 0, 7). Т.к. Z(Y1) = 114 > 104, исследуем следующее ребро, исключив в системе (5.14) уравнение y7 = 0 и заменяя его последовательно уравнениями из (5.16).
Замена y3 = 0 вместо y7 = 0 приводит к тому, что в первом уравнении (9.29) не выполняется условие по ограничению y4 (y4 = 7).
Замена y4 = 0 вместо y7 = 0 приводит к тому, что в первом же уравнении (9.29) не выполняется условие по ограничению y3 (y3= 9).
Замена y5 = 0 вместо y7 = 0 приводит к формированию нулевой (четвертой) строки матрицы A.
Замена y6 = 0 вместо y7 = 0 приводит к формированию нулевой (пятой) строки матрицы A.
Замена y10 = 0 вместо y7 = 0 приводит к тому, что в третьем уравнении (5.15) не выполняется условие по ограничению y12
(y12 = 7).
Замена y12 = 0 вместо y7 = 0 приводит к системе
Находим Y1 = (0, 0, 4, 7, 5, 1, 5, 0, 0, 8, 0, 0). Т.к. Z(Y1) = 104 и это не меньше уже полученной оценки, исследуем следующее ребро, исключив в системе (5.14) уравнение y8 = 0 и заменяя его последовательно уравнениями из (5.16).
Замена y3 = 0 вместо y8 = 0 приводит к образованию нулевой (шестой) строки матрицы A.
Замена y4 = 0 вместо y8 = 0 приводит к тому, что в первом уравнении (5.15) не выполняется условие по ограничению y3 (y3 = 9).
Замена y5 = 0 вместо y8 = 0 приводит к образованию нулевой (четвертой) строки матрицы A.
Замена y6 = 0 вместо y8 = 0 приводит к тому, что в пятом уравнении (5.15) не выполняется условие по ограничению y10 (y10= 8).
Замена y10 = 0 вместо y8 = 0 приводит к тому, что в третьем уравнении (5.15) не выполняется условие по ограничению y12 (y12 = 7).
Замена y12 = 0 вместо y8 = 0 приводит к системе
Ее решение Y1 = (0, 0, 9, 2, 5, 1, 0, 5, 0, 8, 0, 0) определяет значение Z(Y1) = 134 > 104.
Продолжаем перебор по следующему ребру.
Замена y3 = 0 вместо y9 = 0 приводит к образованию нулевой (шестой) строки матрицы A.
Замена y4 = 0 вместо y9 = 0 приводит к тому, что в первом уравнении (5.15) не выполняется условие по ограничению y3 (y3 = 9).
Замена y5 = 0 вместо y9 = 0 приводит к тому, что во втором уравнении (5.15) не выполняется условие по ограничению y6 (y6= 9).
Замена y6 = 0 вместо y9 = 0 приводит к тому, что во втором же уравнении (5.15) не выполняется условие по ограничению y5 (y5 = 5).
Замена y10 = 0 вместо y9 = 0 приводит к системе
Ее решение Y1 = (0, 0, 9, 2, 2, 9, 0, 0, 3, 0, 0, 5) определяет значение Z(Y1) = 119 > 104.
Приступаем к анализу следующего ребра, исключая в (5.14) уравнение y11 = 0 и заменяя его последовательно уравнениями из (5.16).
Замена y3 = 0 вместо y11 = 0 приводит к тому, что в первом уравнении (5.15) не выполняется условие по ограничению y4 (y4 = 7).
Замена y4 = 0 вместо y11 = 0 приводит к тому, что в первом уравнении (5.15) не выполняется условие по ограничению y3 (y3 = 9).
Замена y5 = 0 вместо y11 = 0 приводит к тому, что во втором уравнении (5.15) не выполняется условие по ограничению y6 (y6 = 9).
Замена y6 = 0 вместо y11 = 0 приводит к тому, что во втором же уравнении (5.15) не выполняется условие по ограничению y5 (y5 = 5).
Замена y10 = 0 вместо y11 = 0 приводит к системе
 | (5.17) |
Система не имеет решения, т.к. ранг матрицы системы не равен рангу расширенной матрицы.
Примечание. В несложном примере это легко обнаружить: вторая строка матрицы равна сумме четвертой и пятой строк, что противоречит соотношению между соответствующими свободными членами, 9 + 5
11. По-видимому, это говорит в пользу применения схемы Гаусса. В противном случае мы должны контролировать последовательно получаемые решения на удовлетворение тем соотношениям, которые в его получении не участвовали. Так, из четвертого и пятого уравнений имеем y5 = 5, y6 = 9. Но в соответствии со вторым уравнением y5 + y6 = 11. В то же время, совершая подстановку во второе уравнение, мы получаем нулевую левую часть, т.е.
нулевую строку матрицы A, что опять говорит в пользу подстановок!
Замена y12 = 0 вместо y11 = 0 приводит к системе
Ее решение Y1 = (0, 0, 4, 7, 5, 6, 0, 0, 0, 3, 5, 0) определяет значение целевой функции Z(Y1) = 89 < 104.
Полагаем Y0 := Y1. Теперь мы должны перемещаться по ребрам из вновь найденной вершины в поисках вершины с еще меньшим значением целевой функции. Придется перебрать до 6 ? 6 = 36 вариантов такого перемещения. Однако, достигнув ответа задачи в [15], положимся на его правильность и прекратим рассмотрение примера.
