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



              

Графический метод решения и его обобщение


Рассмотрим пример

z=c1x1+c2x2=2x1+5x2

max    (4.1)

при ограничениях

q1=x1

40

q2=x2

30

q3=x1+x2

50

и условиях x1

0, x2
0.

Каждое ограничение в двухмерном пространстве, 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.

Отметим, что для

z=\const dz = \frac{{\partial z}} {{\partial x_1 }}dx_1 + \frac{{\partial z}} {{\partial x_2 }}dx_2 = c_1 dx_1 + c_2 dx_2 = 0
.

Т.к. dx1 и dx2 принадлежат прямой z, то скалярное произведение двух векторов, которое здесь изображено, равно нулю в том случае, если вектор (c1, c2) =(2, 5) перпендикулярен прямой z.

Увеличиваем значение z, передвигая (с помощью линейки) прямую — целевую — функцию параллельно самой себе в сторону ее возрастания вдоль вектора (2, 5) до тех пор, пока линейка не коснется последней возможной точки многогранника. R. Это значение z и будет максимальным. В данном случае — это точка A = (x1=20, x2=30).

Сделаем важное замечание относительно многогранника R.

  1. То, что он выпуклый, мы заметили ранее.
  2. Нам были заданы три ограничения, отсекающие полуплоскости, но определившие не все границы многогранника R. С "не закрытой" ими стороны область R оказалась закрытой условиями неотрицательного решения задачи: x1

    0, x2
    0. Значит, эти выражения пришлось из ранга условий перевести в ранг ограничений.

    При этом не все условия могут быть переведены в ограничения. В нашей задаче могло существовать некоторое ограничение q4 (на рисунке пунктиром), которое бы определяло границу R слева, исключая границу x1 = 0.


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