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

    х₁₁+х₁₂=360,

    (2.1) х₂₁+х₂₂=360,

          х₃₁+х₃₂=360,

    5х₁₁+6х₂₁+5х₃₁=5х₁₂+2х₂₂+3х₃₂.

    Выберем  в качестве свободных переменных, например, x₁₂ и x₂₂ и выразим через них остальные (базисные) переменные: х₁₁, х₂₁, х₃₂, х₃₁. Из первого уравнения имеем:

    х₁₁=360-х₁₂    (2.2)

    Из  второго:

    х₂₁=360-х₂₂    (2.3)

    Из  третьего:

    х₃₁=360-х₃₂.    (2.4)

    Подставляя (2.2), (2.3.) и (2.4.) в последнее уравнение и разрешая его относительно  х₃₂, имеем:

    х₃₂=720-1,25х₁₂-х₂₂,   (2.5)

    х₃₁=-360+1,25х₁₂+х₂₂.   (2.6)

    Геометрическая  интерпретация задачи представлена на рисунке 3 (прямые х₁₂=0, х₂₂=0 – оси координат; остальные ограничивающие прямые х₃₁=0, х₃₂=0, х₁₁=0 и х₂₁=0; штриховкой помечены допустимые полуплоскости).

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

    Рисунок 3

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

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

    L=5х₁₁+5х₁₂+6х₂₁+2х₂₂+5х₃₁+3х₃₂   (2.7)

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

          L’=2.5х₁₂-2х₂₂+4320 (2.8)

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

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

                            L’=2.5х₁₂-2х₂₂

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

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

                      L’=y₁х₁₂-y₂х₂₂=С

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

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

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

    

    Рисунок 4

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

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

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

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

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

    

    Рисунок 5

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

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

    х₁₁*=0,

    х₂₁*=360,

    х₃₁*=90,

    х₃₂*=270,

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

                L_max=y₀+y₁х₁₂*+y₂х₂₂*

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

    Таким образом, если число независимых  уравнений- ограничений, которым должны удовлетворять переменные х₁₁, х₁₂, х₂₁, х₂₂, х₃₁, х₃₂ на два меньше, чем число переменных, решение ОЗЛП может быть получено простым геометрическим построением.

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

• D (0; 360)

   х₁₂*=0,

   х₂₂*=360,

   х₁₁*=360,

   х₂₁*=0,

   х₃₁*=0,

   х₃₂*=360,

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

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

• А (288; 360)

   х₁₂*=288,

   х₂₂*=360,

   х₁₁*=72,

   х₂₁*=0,

   х₃₁*=360,

   х₃₂*=0,

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

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

• В (360; 270)

   х₁₂*=360,

   х₂₂*=270,

   х₁₁*=0,

   х₂₁*=90,

   х₃₁*=360,

   х₃₂*=0,

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

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

• Е (288; 0)

   х₁₂*=288,

   х₂₂*=0,

   х₁₁*=72,

   х₂₁*=360,

   х₃₁*=0,

   х₃₂*=360,

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

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

• С (360; 0)

   х₁₂*=360,

   х₂₂*=0,

   х₁₁*=0,

   х₂₁*=360,

   х₃₁*=90,

   х₃₂*=270,

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

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

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

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

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

    х₁₁+х₁₂=360,

    х₂₁+х₂₂=360, (2.9)

    х₃₁+х₃₂=360,

    5х₁₁+6х₂₁+5х₃₁=5х₁₂+2х₂₂+3х₃₂,

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

    L=5х₁₁+5х₁₂+6х₂₁+2х₂₂+5х₃₁+3х₃₂.

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

    х₁₁=360-х₁₂,

    х₂₁=360-х₂₂,

    х₃₁=-360+1,25х₁₂+х₂₂,   (3.0)

    х₃₂=720-1,25х₁₂-2х₂₂,

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

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

    L_min=-L_max=-4320-2,5х₁₂+2х₂₂. (3.1)

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

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