Геометрическая интерпретация ОЗЛП как метод оптимизации

Как видно из расположения прямых и отмеченных полуплоскостей, допустимые решения для рассмотренной задачи существуют; они заполняют ОДР, которая на рисунке 3 показана штриховкой.

Рисунок 3

Геометрическая интерпретация задачи (ОДР)

Теперь возникает вопрос о нахождении из числа допустимых решений оптимального решения, т.е. такого, которое обращает в максимум линейную функцию

L=5х11+5х12+6х21+2х22+5х31+3х32                                          (2.7)

Подставим выражения (2.2), (2.3.), (2.4.), (2.5) и (2.6) в формулу (2.7), приведем подобные члены и выразим линейную функцию L всех переменных как линейную функцию только двух свободных переменных: х12 и х22. Получим:

              L’=2.5х12-2х22+4320              (2.8)

Где 4320 (далее y0)– свободный член, которого в первоначальном виде у функции L не было; теперь, при переходе к переменным х12 и х22, он мог появиться.

Очевидно, линейная функция (2.8) достигает максимума при тех же значениях х12 и х22, что и функция

                                                        L’=2.5х12-2х22

Без свободного члена (линейная форма). Действительно, L’= L- y0., где y0 не зависит от х12 и х22, и, очевидно, максимумы той и другой              функций, отличающиеся на 4320, достигаются при одних и тех же значениях х12, х22.

Найдем эти значения, пользуясь геометрической интерпретацией. Придадим L’ некоторое постоянное значение С:

                                          L’=y1х12-y2х22=С

Получим уравнение прямой на полуплоскости х22Ох12. Угловой коэффициент этой прямой равен - y1/ y2, а отрезок, отсекаемый ею на оси Ох22 (начальная ордината), равен С/ y2. очевидно, если мы заменим постоянную С на некоторую другую С1, угловой коэффициент прямой не изменится; изменится только начальная ордината, и прямая параллельно самой себе в новое положение L’=С1

Таким образом, различным значениям L’ соответствуют разные прямые на плоскости, но все они параллельны между собой. Очевидно, вместо всех этих прямых достаточно изобразить на плоскости одну основную прямую, например, L’=0, а затем можно мысленно перемещать ее параллельно самой себе. При перемещении этой прямой в одну сторону L’ и будет возрастать, в другую – убывать.

Построим основную прямую L’=0 на плоскости х12Ох22 (рисунок 4) . Мы знаем, что угловой коэффициент равен–  y1/ y2; чтобы построить прямую, проходящую через начало координат с угловым коэффициентом–  y1/ y2 отложим по оси абсцисс отрезок y2, а по оси ординат отрезок y1(предварительно умножив их на 200, для облегчения построения, получим точку К(400;500)), и через точку К с такими координатами проведем прямую. Это и будет основная прямая L’=0.

Рисунок 4

График основной прямой L’=0

Теперь остается только выяснить, в какую сторону (параллельно самой себе) надо двигать эту прямую, чтобы величина L’ возрастала. В нашем случае, показанном на рисунке 5 (коэффициент y1 положительный, а y2 - отрицательный), направление возрастания L’ – вниз и направо (это показано стрелками, направленными от основной прямой в сторону возрастания L’). При других знаках коэффициентов y1, y2 направление меняется.

Таким образом, и направление основной прямой L’=0, и направление возрастания линейной формы L’ определяются величинами и знаками коэффициентов y1, y2 при свободных переменных х12, х22 в выражении L’.

Дадим теперь геометрическую интерпретацию нахождения оптимального решения ОЗЛП среди допустимых.

Пусть имеется область допустимых решений ОДР (рис. 5) и основная прямая L’=0; известно (указано стрелками) направление возрастания линейной формы L’.

Рисунок 5

Оптимальное решение задачи

При перемещении основной прямой в направлении, указанном стрелками, линейная форма L’ будет возрастать. Очевидно, наибольшего значения она достигнет, когда прямая будет проходить через крайнюю точку ОДР, наиболее удаленную от начала координат в направлении стрелок (в нашем случае, точку С). Координаты этой точки 360;0 и определяют оптимальное решение ОЗЛП. Зная оптимальные значения свободных переменных Х12*, Х22*, можно найти, подставляя их в уравнения (2.2), (2.3), (2.4) и (2.5), и оптимальные значения базисных переменных:

х11*=0,

х21*=360,

х31*=90,

х32*=270,

А также оптимальное (максимальное) значение линейной функции L:

                            Lmax=y0+y1х12*+y2х22*

                            Lmax=4320+2.5*360+2*0=5220

Таким образом, если число независимых уравнений- ограничений, которым должны удовлетворять переменные х11, х12, х21, х22, х31, х32 на два меньше, чем число переменных, решение ОЗЛП может быть получено простым геометрическим построением.

Можно решить эту задачу и без построения линейной функции L, следующим образом. В теории математического программирования убедительно показывается, что оптимальному решению соответствует одна из вершин многоугольника, а именно та, для которой общая производительность окажется максимальной. Рассмотрим все вершины многоугольника:

                 D (0; 360)

х12*=0,

х22*=360,

х11*=360,

х21*=0,

х31*=0,

х32*=360,

А также значение линейной функции L:

                            L=5*360+5*0+6*0+2*360+5*0+3*360=3600

                 А (288; 360)

х12*=288,

х22*=360,

х11*=72,

х21*=0,

х31*=360,

х32*=0,

А также значение линейной функции L:

                            L=5*72+5*288+6*0+2*360+5*360+3*0=4320

                 В (360; 270)

х12*=360,

х22*=270,

х11*=0,

х21*=90,

х31*=360,

х32*=0,

А также значение линейной функции L:

                            L=5*0+5*360+6*90+2*270+5*360+3*0=4680

                 Е (288; 0)

х12*=288,

х22*=0,

х11*=72,

х21*=360,

х31*=0,

х32*=360,

А также значение линейной функции L:

                            L=5*72+5*288+6*360+2*0+5*0+3*360=5040

                 С (360; 0)

х12*=360,

х22*=0,

х11*=0,

х21*=360,

х31*=90,

х32*=270,

А также значение линейной функции L:

                            L=5*0+5*360+6*360+2*0+5*90+3*270=5220

Как видно из вычислений, это вершина С с координатами 360;0, в этой точке линейная функция L достигает максимального значения, равное 5220, оно и является оптимальным для нас.

Рассмотрим этот же пример, в котором оптимизация может быть проведена с помощью симплекс метода - табличного алгоритма замены.

Имеется ряд уравнений:

х11+х12=360,

х21+х22=360,              (2.9)

х31+х32=360,

5х11+6х21+5х31=5х12+2х22+3х32,

необходимо найти решение задачи линейного программирования, которое будет обращать в максимум линейную функцию:

L=5х11+5х12+6х21+2х22+5х31+3х32.

Выберем в качестве свободных переменных х12 и х22, выразим относительно этих переменных все базисные (оставшиеся), переменные, получим уравнения вида:

х11=360-х12,

х21=360-х22,

х31=-360+1,25х12+х22,                                          (3.0)

х32=720-1,25х12-2х22,

Выразив через свободные переменные х12 и х22 линейную функцию, получим Lmax=4320+2,5х12-2х22.

Т.к. по определению ОЗЛП мы должны минимизировать линейную функцию L, то необходимо записать L, как

Lmin=-Lmax=-4320-2,5х12+2х22.              (3.1)

Запишем (3.0) и (3.1) в виде стандартной таблицы, причем свободные члены будем писать без изменений, а коэффициенты при переменных предварительно умножим на -1. таким образом получим Таблицу № 3.

Выбираем из свободных членов отрицательный (х31) и смотрим на строку элементов, выбирая из элементов отрицательный. Смотрим на столбец, те элементы, которые имеют один знак со свободным членом, выбираем разрешающим элементом тот, отношение которого меньше при делении свободного члена на элемент. В данном случае это элемент столбца х12 и строки х31. выделим в таблице разрешающий элемент -1,25. вычислим его обратную величину -1/1,25 (или -4/5) и запишем ее в нижней части той же ячейки (в нижнем углу). Все элементы разрешающей строки (кроме самого -1,25) умножим на -4/5, результат запишем в нижней части той же ячейки. Все элементы разрешающего столбца (кроме самого -1,25) умножим на 4/5, результат запишем в нижней части той же ячейки. Подчеркнем (или выделим иным способом) в разрешающей строке все верхние числа (прежние элементы), за исключением самого разрешающего элемента ячейки, а в разрешающем столбце – все нижние числа (новые элементы), за исключением самого разрешающего элемента.

Для каждого из элементов, не принадлежащих ни к разрешающему столбцу, ни к разрешающей строке, записать в нижнюю часть ячейки произведение выделенных чисел, стоящих в том же столбце и в той же строке, что и данный элемент.

Таблица 3                            Табличный алгоритм замены шаг 1

Перепишем Таблицу № 3 в Таблицу № 4, заменив:

- х12 на х31 и обратно;

- элементы разрешающей строки и столбца – числами, стоящими в нижних частях тех же ячеек;

- каждый из остальных элементов – суммой чисел, стоящих в верхней и нижней части той же ячейки.

Т.к. коэффициент в первой строке при х31 положителен, значит переменную х31 нужно вывести из числа свободных. В качестве разрешающего берем тот из положительных элементов столбца х31, для которого  отношение к нему свободного члена минимально. Отношения равны 4/5/72=0,011; 1/360=0,0027. Минимальное из них 0,0027. Значит в качестве разрешающего нужно взять элемент 1 в столбце х31, строке х32. Произведем замену х31↔х32. (см.Таблицу № 4).

Таблица 4                            Табличный алгоритм замены шаг 2