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


              

комбинация нулей найдена. Это отмеченные


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

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