Методы принятия упр. ...

3.2 Поиск оптимального решения

1. Строится направляющий вектор N (градиент целевой функции);

2. Строится линия уровня целевой функции;

3. Определяется экстремальная точка многоугольника;

4. Вычисляется значение целевой функции в полученной точке.

1. Построение направляющего вектора N

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

Для нахождения экстремальной точки строят градиент функции (направляющий вектор, который показывает направление возрастания целевой функции). Градиент исходит из начала координат. Координатами его являются коэффициенты целевой функции. Вектор N показывает направление возрастания целевой функции.

Для удобства восприятия штриховки на рисунке удалены. В рассматриваемом примере вектор выходит из точки начала координат к точке с координатами (2;3)

2. Построение линии уровня целевой функции

Построим одну из линий уровня целевой функции, задав этой функции некоторое произвольное значение.

Это значение удобно выбирать таким образом, чтобы линия уровня проходила через найденную ОДР и чтобы это значение делилось нацело на коэффициенты целевой функции.

Если по осям х1 и х2 деление одинаковое, то можно построить перпендикуляр к вектору N, это и будет линия уровня целевой функции.

3. Нахождение экстремальной точки

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

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

Предельное положение линии уровня будет соответствовать прямой, проходящей через точку А – точка экстремума целевой функции.

При дальнейшем движении в том же на­правлении линия уровня покинет пределы ОДР данной задачи.

В нашем случае экстремальная точка (точка максимуму) находится на пересечении двух прямых х1+3х2=18 и 2х1+х2=16. Для нахождения координат экстремальной точки необходимо решить систему уравнений данных прямых.

Решив систему уравнений, получим следующие координаты точки экстремума А(6;4).

Заме­тим, что если бы мы решали задачу на минимум целевой функции, то надо было бы двигаться в направлении, противоположном направле­нию вектора N и в нашей задаче предельной точкой переме­щения линии уровня в сторону минимума была бы точка 0(0; 0).

4. Нахождение значения целевой функции в экстремальной точке.

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

С=2*6+3*4=24