Тема 1. Математические основы для решения оптимальных задач Лекция 1. Математические основы для решения оптимальных задач
Пусть область допустимых решений (ОДР), в которой отыскивается наилучшее решение для целевой функции, определена соотношениями:
Z = 2x1 + 3x2 max
x1 + x2 6 (1)
x1 + 2x2 8,5 (2)
x
1
4 (3)
x2 3 (4)
Ясно, что минимальное значение для целевой функции (для неотрицательных x1, x2) находится в начале координат (рис.1). Значит, для отыскания максимума целевой функции надо двигаться в плоскости (пространстве) переменных на «северо–восток». Нам придется сделать пять таких шагов.
Первый и второй шаг. Первоначальная запись целевой функции (ЦФ) и ограничений (1-4) можно представить в канонической форме:
Z=2x1 + 3x2 max или Z=2x1 + 3x2 max
x1 + x2 + x3 = 6 (1) x3 = 6 – x1 – x2 (1)
x1 + 2x2 + x4 = 8,5 (2) x4 = 8,5 – x1 2x2 (2)
x1 + x5 = 4 (3) x5 = 4 – x1 (3)
x2 + x6= 3 (4) x6 = 3 – x2 (4)
В этих выражениях x1, x2 называются свободными, а x3, x4, x5 и x6 – базисными переменными. Базисное решение определяется, когда движение на «северо–восток» начнется из начала координат – то есть при x1 = 0 и x2 = 0. Тогда значения x3 = 6, x4 = 8,5, x5 = 4, x6 = 3. При этом Z = 0; увеличим его за счет x1.
Третий шаг. Увеличивать x1 можно до тех пор, пока базовая переменная x5 не станет равной нулю. Из (3) следует, что значение x1 = 4 – x5. Подставив это значение в правый столбец соотношений (1-4), получим:
Z=2x1 + 3x2 = 8 – 2x1 + 3x2 max
x3 = 2 + x5 – x2 (1)
x4 = 4,5 + x5 2x2 (2)
x1 = 4 – x5 (3)
x6 = 3 – x2 (4)
Видно, что значение ЦФ выросло до величины Z = 8, а значения базовых переменных уменьшились: x3 = 2, x4 = 4,5. Свободная переменная x1 = 4. На третьем шаге к нулю приравнивались значения переменных x5 = 0 и x2 = 0. Теперь уже точно определяется угол наклона линии ЦФ и значения, отсекаемые этой прямой на каждой из осей: x1 = 4 x2 = 2,67. Тогда и направление ЦФ в начале координат также становится известным – оно параллельно линии Z = 8.
Четвертый шаг. Проделав аналогичные операции преобразования, для увеличения ЦФ только за счет x2, и положив значение x2 =2 + x5 x3 , получим следующие значения отыскиваемых переменных: x1 = 4, x2 = 2, x3 = 0, x4 = 0,5, x5 = 0, x6 = 1. Здесь в качестве базовых переменных были x3 и x5. Значение Z = 14 проходит через новую угловую точку С(4;2) параллельно линии Z = 8.
Пятый шаг. Осталась возможность улучшить значение ЦФ за счет x5. Поскольку x5 = 0,5 + 2x3 x4, получим преобразованную систему уравнений:
Z = 2x1 + 3x2 = 14,5 – x3 x4 max
x2 = 2,5 + x3 – x4 (1)
x4 = x1 =2x3 2x3 + x4 (2)
x1 = 3,5 –2x3 + x4 (3)
x6 = 0,5 –x3 + x4 (4)
Поскольку на этом шаге свободными переменными оказались x3, x4, их значения надо приравнять к нулю. Тогда Z = 14,5; x1 = 3,5; x2 = 2,5. Свободные же переменные значительно отличаются от их первоначальных значений: x3 = 0 (а было равно 6); x4 = 0 (было 8,5); x5 = 0,5 (было 4); x6 = 0,5 (было 3).
Таким образом, в случае решения линейных оптимизационных задач мы получили надежный математический аппарат, пригодный для решения задач и со многими переменными.
Но линейные задачи оптимизации обладают чудесными свойствами дополнительных информационных ресурсов.