Модели и методы принятия решения (стр. 1 из 3)
Задача 1
Решить графоаналитическим методом:
minj (X) = - 2x1 - x2 + x3 (1)
при
2x1 - x2 + 6x3£ 12 (2)
3x1 + 5x2 - 12x3 = 14 (3)
3x1 + 6x2 + 4x3£ 18 (4)
X³ 0 (5)
Решение:
Этап 1. Построение пространства допустимых решений
Выбираем прямоугольную систему координат: по горизонтальной оси указываем значения переменной х1, по вертикальной - х2.
Далее рассмотрим условие неотрицательности переменных (5):
х1³ 0; х2³ 0 и х3³ 0. (6)
Первые два ограничения показывают, что пространство допустимых решений будет лежать в первом квадранте (т.е. выше оси х1 и правее оси х2).
Из ограничения (3) можно получить:
3x1 + 5x2 - 12x3 = 14®
, (7)с учётом условия неотрицательности третьей переменной (6) получаем новое ограничение:
. (8)Подставляем в ограничение (2) найденное значение (7):
2x1 - x2 + 6x3£ 12®
®®
(9)Подставляем в ограничение (4) найденное значение (7):
3x1 + 6x2 + 4x3£ 18®
®®
(10)Чтобы учесть получившиеся ограничения, проще всего заменить неравенства на равенства, в результате чего получим уравнения прямых:
, 
, 
.Теперь рассмотрим, как графически интерпретируются неравенства. Каждое неравенство делит плоскость (х1, х2) на два полупространства, которые располагаются по обе стороны прямой, которая соответствует данному неравенству.
Точки плоскости, расположенные по одну сторону прямой, удовлетворяют неравенству (допустимое полупространство), а точки, лежащие по другую сторону - нет.
На рис.1 допустимые полупространства показаны стрелками.
Рис.1. Нахождение оптимального решения
Ограничения:
(А) (В) (С)х2³ 0 (D)
х1³ 0 (E)
Этап 2. Нахождение оптимального решения
Точки пространства допустимых решений, показанного на рис.1, удовлетворяют одновременно всем ограничениям. Это пространство ограничено отрезками прямых, которые соединяются в угловых точках F, G, H, J и K.
Любая точка, расположенная внутри или на границе области, ограниченной ломаной FGHJK, является допустимым решением, т.к удовлетворяет всем ограничениям.
Пространство допустимых решений содержит бесконечное число точек.
Нахождение оптимального решения требует определения направления убывания целевой функции (1):
minj (X) = - 2x1 - x2 + x3.
Подставляем в целевую функцию найденное значение (7):
.Мы приравниваем j (X) к нескольким убывающим значениям, например, (- 5) и (- 8). Эти значения, подставленные вместо j (X) в выражение целевой функции, порождают уравнения прямых; для значений (- 5) и (- 8) получаем уравнения прямых:
и
.На рис.2 эти прямые показаны штрих-пунктирными линиями, а направление убывания целевой функции - толстой стрелкой.
Целевая функция может убывать до тех пор, пока прямые, соответствующие убывающим значениям этой функции, пересекают область допустимых решений. Точка пересечения области допустимых решений и прямой, соответствующей минимально возможному значению целевой функции, и будет точкой оптимума.
Из рис.2 видно, что оптимальное решение соответствует точке Н. Эта точка является местом пересечения прямых (В) и (С), поэтому её координаты х1 и х2 находятся как решение системы уравнений, задающих эти прямые:
Решением этой системы будет:
х1 = 5,36
х2 = 0,16
при этом значение целевой функции равно:
.Ответ:
Оптимальное решение:
х1 = 5,36
х2 = 0,16
при этом значение целевой функции равно:
j (X) = - 10,621.
Рис.2. Нахождение оптимальной точки
Задача 2
Найти экстремумы методом множителей Лагранжа.
Решение проиллюстрировать графически.
extrj (X) = 3x12 + 2x1 + 2x22 + 4x2x3
при
x1 + 2x2 = 19
x1 + 2x3 = 11.
Решение:
Обозначим:
g1 (X) = x1 + 2x2 - 19 = 0,g2 (X) = x1 + 2x3 - 11 = 0.
Функция Лагранжа имеет вид:
Отсюда получаем необходимые условия экстремума в виде системы уравнений:
, 
, 
, 
, 
.Решаем систему уравнений через определители.
Главный определитель:
.Матрица - столбец левой части системы (свободных членов):
.Находим остальные определители:
, 
, 
, 
, 
.Находим решение системы уравнений:
, 
, 
, 
, 
.Таким образом, получили одну экстремальную точку.
Определяем матрицу Гессе:
Матрица Гессе положительно определена, поэтому в найденной точке
функция Лагранжа L (X, l) выпуклая и, следовательно, имеется минимум.
Для графической иллюстрации решения выразим координату х3 из функции ограничения g2 (X):
g2 (X) = x1 + 2x3 - 11 = 0®
.Подставим полученное значение в целевую функцию:
j (X) = 3x12 + 2x1 + 2x22 + 4x2x3 = 3х12 + 2х1 +2х22 + 4х2 (5,5 - 0,5х1) =
j (X) = 3х12 + 2х1 +2х22 + 22х2 - 2х1х2.
Получили общее уравнение кривой второго порядка.
Для получения канонического вида уравнения производим поворот системы координат, освобождаясь от члена, содержащего произведение координат.
Угол поворота j определяется формулой:
® 
радиан.При этом получаем новые координаты y и z:
, 
.Подставляем полученные выражения в целевую функцию:
j (y, z) = 3х12 + 2х1 +2х22 + 22х2 - 2х1х2 =
, 
, 
, 
Получили уравнение эллипса с центром в точке (y = 1,3633; z = - 7,1513), причём линии симметрии эллипса наклонены на угол j = - 0,55375 радиан относительно начальной системы координат х1х2.