Параллельное программирование



              

Параллельный алгоритм решения - часть 3


Значение y10 = 0 не приводит к нарушению оценок.

Значение y11 = 0 также не приводит к нарушению оценок.

Итак, комбинация нулей найдена. Это отмеченные в (5.8) значения

y1 = 0, y2 = 0, y5 = 0, y7 = 0, y10 = 0, y11 = 0. (5.9)

Для нахождения других значений переменных необходимо решить систему уравнений на основе (5.8), после исключения нулевых столбцов

 \begin{pmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} \times \begin{pmatrix} y_3\\y_4\\y_6\\y_8\\y_9\\y_{12} \end{pmatrix} = \begin{pmatrix} 11\\ 11\\ 8\\ 5\\ 9\\ 9 \end{pmatrix}.

Найдем все строки матрицы A, содержащие не более одного единичного элемента. Это строки, определяющие компоненты решения y3

= 9, y6 = 9, y9 = 5.

Выполним подстановку, последовательно находя в столбцах найденных переменных единицы (не более одной) и корректируя правые части вычитанием найденных значений. Строки и столбцы, соответствующие найденным значениям переменных, исключаем из матрицы A.

Такой прием подстановки можно повторять до исчерпания уравнений, содержащих в левой части единственную переменную.

В нашем примере после подстановки найденных значений в уравнения 1, 2 и 3 получаем систему

 \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1 \end{pmatrix} \times \begin{pmatrix} y_4\\y_8\\y_{12} \end{pmatrix} = \begin{pmatrix} 11-9\\ 11-9\\ 8-5 \end{pmatrix}

В ней все уравнения имеют единственную переменную. Они определяют решение 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 ), мы можем продолжить анализ смежных ей вершин и т.д.


Содержание  Назад  Вперед