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

и ранее, линейное множество переменных


Введем, как и ранее, линейное множество переменных и сформулируем задачу:
Z = 2y1 + 3y2 + 3y3 + 2y4 + 2y5 + y6
min
при ограничениях
y1 + y2 + y3 = 12
y4 + y5 + y6 =10 (5.21)
y1+ y4 =7
y2 + y5 =7
y3 + y6 = 8
и при условии
0
y1
4, 0
y2
4, 0
y3
5, 0
y4
4, 0
y5
4, 0
y6
3. (5.22)
Сформируем ограничения каждой переменной: y1 = min{12, 7, 4} = 4, аналогично y2 = 4, y3 = 5, y4 = 4, y5 = 4, y6 = 3. Исключим из рассмотрения последнее уравнение (5.21) и запишем уравнения всех потенциальных граней на основе (5.22):
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10(5.23)
y1 + y4 = 7
y2 + y5 = 7
y1 = 0; y1 = 4
y2 = 0; y2 = 4
y3= 0; y3 = 5 (5.24)
y4 = 0; y4 = 4
y5 = 0; y5 = 4
y6 = 0; y6 = 3
Начнем перебор систем по шесть граней в поисках координат одной из вершин многогранника решений. В каждой такой системе должны присутствовать все уравнения (5.23) и два уравнения с разными переменными из (5.24).
Для формирования первой системы уравнений пробуем добавить к (5.23) уравнение y1 = 0. В результате в третьем уравнении не выполняется ограничение по y4 (y4 = 4).
Пробуем вариант y1 = 4. Совершив подстановку, убеждаемся, что он не приводит к подобному противоречию.
Полагаем y2 = 0. В первом уравнении не выполняется ограничение по y3 (y3 = 5).
Полагаем y2 = 4. Получаем и решаем систему уравнений
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10
y1 + y4 = 7
y2 + y5 = 7
y1= 4
y2 = 4.
Находим Y = (4, 4, 4, 3, 3, 4). Однако данная точка не является вершиной многогранника решений, т.к. y6 = 4 противоречит условию (5.22).
Испытываем уравнение y3 = 0. В первом уравнении нарушается ограничение по y1 + y2 (y1 + y2 = 8 < 12).
Испытываем уравнение y3 = 5. Решаем систему уравнений
y1 + y2 + y3 = 12
y4 + y5 + y6 = 10
y1 + y4 = 7
y2 + y5 = 7
y1 = 4
y3 = 5.
Находим Y0 = (4, 3, 5, 3, 4, 3). Решение удовлетворяет условиям задачи, следовательно, найденная точка — вершина многогранника решений. Находим значение целевой функции Z(Y0) = 49.
На основе (5.23) и (5.24) выпишем уравнения всех граней, которым удовлетворяет вершина Y0, т.е.

Содержание раздела