Графический метод решения и его обобщение
Рассмотрим пример
z=c1x1+c2x2=2x1+5x2
при ограничениях
q1=x1
q2=x2
q3=x1+x2
и условиях x1
Каждое ограничение в двухмерном пространстве, n=2, определяет полуплоскость. Их пересечение образует многоугольник R (рис. 4.1). Его грани — прямые, получены на основе ограничений, в которых неравенства заменены равенствами.
q1 = 40
q2 = 30 (4.2)
q3 = 50
Эти равенства образуют уравнения границ или просто границы R.
Рис. 4.1. Графический метод решения задачи линейного программирования
Этот многоугольник (выпуклый многогранник; выпуклый, — ибо он остается по одну сторону от любой прямой, проходящей через его ребро) представляет собой допустимое множество решений R задачи ЛП.
Выберем произвольное значение, например, z=100 целевой функции. Прямая 2x1+5x2=100 показана на рисунке. Она пересекает ось x1 в точке x1=50 и ось x2 в точке x2=20.
Отметим, что для
Т.к. dx1 и dx2 принадлежат прямой z, то скалярное произведение двух векторов, которое здесь изображено, равно нулю в том случае, если вектор (c1, c2) =(2, 5) перпендикулярен прямой z.
Увеличиваем значение z, передвигая (с помощью линейки) прямую — целевую — функцию параллельно самой себе в сторону ее возрастания вдоль вектора (2, 5) до тех пор, пока линейка не коснется последней возможной точки многогранника. R. Это значение z и будет максимальным. В данном случае — это точка A = (x1=20, x2=30).
Сделаем важное замечание относительно многогранника R.
- То, что он выпуклый, мы заметили ранее.
-
Нам были заданы три ограничения, отсекающие полуплоскости, но определившие не все границы многогранника R. С "не закрытой" ими стороны область R оказалась закрытой условиями неотрицательного решения задачи: x1
0, x20. Значит, эти выражения пришлось из ранга условий перевести в ранг ограничений.При этом не все условия могут быть переведены в ограничения. В нашей задаче могло существовать некоторое ограничение q4 (на рисунке пунктиром), которое бы определяло границу R слева, исключая границу x1 = 0.
При этом граница x2 = 0 внизу осталась бы.
- Другое важное замечание: решение задачи мы нашли на границе многогранника R.
При этом возможны варианты:
- Единственному конечному решению соответствует вершина R, как в нашем примере.
- Решением может являться бесконечное множество точек на грани R, например, если бы ограничение q3 определяло бы прямую, параллельную z (уравнения q3 и z были бы линейно зависимыми).
- Система ограничений может определять "открытый" многогранник R, включающий бесконечно удаленные точки, в которых достигается max z, т.е. max z = ?. Например, та же задача ЛП могла быть поставлена при отсутствии ограничений q2 и q3 (
рис. 4.2). Перемещение z в сторону ее увеличения может быть бесконечным, т.е. max z = ?. Но если бы была поставлена задача zmin, то она бы при этих ограничениях имела конечное и единственное решение, в данном случае x1=x2=0.
Рис. 4.2. Случай отсутствия решения
Значит, имеет значение, с какой стороны многогранник R открыт: либо он позволяет поиск решения вдоль "закрытых" стенок, либо допускает возможность "выпасть" за его пределы, искать решение в бесконечности.
Тогда, как бы мы могли искать решение нашей первоначально поставленной задачи ЛП?
Учитывая, что решение задачи — в одной из вершин R, мы сначала выпишем уравнения всех прямых, ограничивающих R, т.е. уравнения всех его границ:
x1 = 40
x2 = 30
x1 + x2 = 50
x1 = 0
x2 = 0
Для нахождения координат каждой вершины R решаем совместно пару уравнений прямых, образующих эту вершину, и находим значение z в найденной вершине:
Действительно, max z = 190 достигается в точке A.
Отметим возможноcть распараллеливания решения задачи на многопроцессорной ВС, точнее, ВС SPMD-технологии.
В трехмерном пространстве ограничения и условия образуют пространственный многогранник R, охваченный плоскостями-границами, записанными на основе ограничений и условий, где неравенства заменены равенствами, а каждая плоскость z = const, среди которых мы ищем решение, пересекает, "прорезает" его, деля на две части (
рис. 4.3).
Рис. 4.3. Задача линейного программирования в трёхмерной области
На рисунке иллюстрируется задача ЛП:
z=c1x1+c2x2+c3x3
при ограничениях
q1=a11x1+a12x2+a13x3
q2=a21x1+a22x2+a23x3
и при условии
x1
Две грани q1=b1 и q2=b2, ограничивают многогранник R — область возможных значений переменных сверху (спереди) и справа. Слева, внизу и сзади пространственный многогранник R ограничен условиями неотрицательности решения, ставшими ограничениями x1 = 0, x2 = 0, x3 = 0. Плоскость z=const пересекает многогранник R. Перемещая плоскость z параллельно себе, т.е. вдоль вектора (c1, c2, c3), в сторону возрастания значений линейной формы z, мы находим решение. Здесь наглядно показана очевидность того, что решение следует искать в вершинах R.
Однако графическое представление уже в трехмерном пространстве затруднительно, в n-мерном пространстве нам необходимо действовать формально. Здесь существует ряд проблем.
Во-первых, мы не представляем пространственной картины и не знаем, охватывают ли заданные ограничения область R со всех сторон и какими условиями эти ограничения должны быть дополнены без противоречий.
Во-вторых, мы не знаем, какие n ограничений, дополненных условиями, соответствуют каждой конкретной вершине многогранника R, чтобы найти координаты этой вершины и найти в ней значение целевой функции z. Значит, мы должны испытать все возможные комбинации по n (в данном случае — тройки) ограничений и условий, т.е. все возможные комбинации по три, составленные на основе всех потенциальных границ- ограничений и условий.
Тогда при построении (параллельной!) вычислительной процедуры мы должны опираться на то, что любая противоречивость в системе ограничений (в их состав мы включили теперь и условия) выразится в неразрешимости системы трех уравнений, составленной для нахождения координат очередной испытываемой вершины R. Т.е. в этом случае вершина находится в бесконечности или содержит отрицательные значения координат. Эта неразрешимость находится в процессе счета.
Оставаясь в области практических решений задач ЛП, т.е. в области инженерии и экономики, примем предположение, что задача сформулирована корректно. Под этим будем предполагать, что ограничения выбраны так, что она не имеет неограниченного решения z = ?.
Например, ставя задачу о максимизации прибыли от перевозки, не надо забывать о том, что объем перевозок ограничен ресурсами страны, сообщества и т.д. В противном случае мы получим тривиальное решение: чем больше, тем лучше.
Значит, мы будем предполагать, что в многограннике R обязательно есть вершины (их координаты не отрицательны), в целом ограничивающие области изменения переменных, и хотя бы в одной из этих вершин целевая функция — линейная форма z принимает максимальное значение.
В свете сказанного будем также считать, что ограничения не противоречивы. Противоречивые ограничения приводят к случаю R =
Например, ограничения
x + y
x + y
противоречивы.
Тогда, развивая на n-мерное пространство, мы можем реализовать следующую стратегию поиска решения задачи ЛП.
