допустимых решений, представленный на рис.
Рассмотрим задачу линейного программирования
Z = 26x + 20y + 21z
при ограничениях
q1 = 2x + 7y - 76z + 222
q2 = - 8x +9y - 8z + 64
q3 = - 8x + 13y -24z + 96
q4 = - x - 6y - z + 70
q5 = - 2x - 7y - 2z + 90
q6 = 33x + 3y +22z - 165
и при условии x
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)
 | (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.
Первая же система
Следующее возможное ребро, исходящее из вершины 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.
Система
решается впервые. Она определяет точку K. Однако Z(10, 10, 0) = 460 < 602.
Таким образом, нам не удалось сместиться из вершины F в вершину с большим значением Z. Значит, найденная точка F определяет решение задачи ЛП.
