Математические модели систем управления и методы оптимизации

Решение является допустимым (допуская ), и является оптимальным.

Из симплекс таблицы 2.4 получим:

 

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

Экстремальное значение функции (2.8) примет значение:

 

Переменным прямой задачи поставим в соответствие переменные двойственной задачи:

 

В -строке симплекс таблицы 2.4 двойственной задачи расположены коэффициенты при небазисных переменных . Используя соответствие, найдем оптимальное решение прямой задачи:

Тогда оптимальный план прямой задачи:

Оптимальный план прямой задачи, найденный путем решения двойственной задачи, совпадает с оптимальным планом в выражении (2.6), полученным при решении прямой задачи. Экстремальные значения функции цели прямой и двойственной задачи совпадают.

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

 

2.3 Нахождение целочисленного решения задачи

Задача, в которой некоторые переменные могут принимать только целые значения, называется частично-целочисленной.

Для задачи (2.1) найдем частично-целочисленное решение, считая, что переменная должна быть целой.

Дополнительное ограничение должно быть составлено по строке симплекс-таблицы с переменной, значение которой должны быть целочисленными [1]. Дополнительное ограничение имеет вид:

(2.10)

где  – коэффициенты при небазисных переменных в данной строке;

 – дробная часть свободного члена.

 

С учетом выражения (2.10) для переменной получим:

(2.11)

Добавим условие (2.11) в симплекс-таблицу:

 

	(2.12)

 

Учтем (2.12) путем добавления дополнительной строки в симплекс-таблицу (таблицу 2.2). Тогда симплекс-таблица примет вид:

 

Таблица 2.5 – Первая итерация

БП	Своб. члены	НП

 

Решение не является допустимым, так как существует свободный член меньше нуля.

В строке с отрицательным свободным членом найдем максимальный отрицательный по абсолютному значению элемент. Этот элемент станет ведущим. Ведущий элемент выделен полужирный шрифтом в таблице 2.5.

Симплекс таблица после пересчета имеет вид, представленный в таблице (2.6).

 

Таблица 2.6 – Вторая итерация

БП	Своб. члены	НП

 

Решение является допустимым, но не является оптимальным.

Выберем столбец, в котором функция цели имеет отрицательный коэффициент.

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

Пересчитаем таблицу в соответствии с правилами.

 

Таблица 2.7 – Третья итерация

БП	Своб. члены	НП

 

Решение является оптимальным и допустимым.

Из симплекс-таблицы 2.7 получаем:

(2.13)

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

(2.14)

Экстремальное значение функции (2.1) примет значение:

 

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

3.1 Нахождение безусловного экстремума функции F(x)

Исходная задача имеет вид:

(3.1)

Начальная точка имеет координаты:

 

График функции, построенный в Matlab, представлен на рисунке 3.1.

Решим задачу различными методами и сравним полученные результаты.

Метод Ньютона-Рафсона.

В данном методе решение заданной нелинейной задачи, как правило, происходит за один шаг, т.е. будет решением данной задачи.

 

Здесь – матрица Гессе (матрица, составленная из вторых частных производных), – значение градиента функции в начальной точке.

Найдем вид вектора градиента:

 

 

(3.2)

В точке вектор градиента примет значение:

 

Составим матрицу Гессе:

 

 

Найдем обратную матрицу для матрицы Гессе.

 

Координаты следующей точки будут определятся по выражению:

 

 

Найдем значение вектора градиента по выражению (3.2) в точке :

 

Следовательно в точке функция достигает своего максимального значения:

 

Метод наискорейшего спуска

В данном методе на каждой итерации в текущей точке определяется направление движения (вектором градиента для задачи на максимум) и величина шага в данном направлении [2].

Шаг 1.

Координаты точки будут определяться выражением:

 

где  – значение вектора градиента, вычисленное в точке ;

 – величина шага в данном направлении.

Найдем значение функции по выражению (3.1) в точке :

 

Найдем направление вектора градиента по выражению (3.2) в точке :

 

Подставим известные значения в выражение для определения координаты следующей точки:

 

Найдем величину шага . Для этого подставим в функцию (3.1) найденные выражения для , т.е. получим функцию зависящую от величины шага. Затем исследуем полученную функцию на экстремум, для чего возьмем производную от полученной функции и приравняем к нулю:

 

 

 

 

Тогда координаты точки будут равны:

 

Найдем значение функции по выражению (3.1) в точке :

 

Шаг 2.

Координаты точки будут определяться выражением:

 

Найдем направление вектора градиента по выражению (3.2) в точке :

 

Подставим известные значения в выражение для определения координаты следующей точки:

 

Найдем величину шага . Для этого подставим в функцию (3.1) найденные выражения для , т.е. получим функцию зависящую от величины шага. Затем исследуем полученную функцию на экстремум:

 

 

 

 

Тогда координаты точки будут равны:

 

Найдем значение функции по выражению (3.1) в точке :

 

Шаг 3.

Координаты точки будут определяться выражением:

 

Найдем направление вектора градиента по выражению (3.2) в точке :

 

Подставим известные значения в выражение для определения координаты следующей точки:

 

Найдем величину шага :

 

 

 

 

Тогда координаты точки будут равны:

 

Найдем значение функции по выражению (3.1) в точке :

 

Шаг 4.

Координаты точки будут определяться выражением:

 

Найдем направление вектора градиента по выражению (3.2) в точке :

 

Подставим известные значения в выражение для определения координаты следующей точки:

 

Найдем величину шага :

 

 

 

 

Тогда координаты точки будут равны:

 

Найдем значение функции по выражению (3.1) в точке :

 

Графическая интерпретация метода найскорейшего спуска представлена на рисунке 3.2.

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

 

3.2 Нахождение экстремума функции F(x) с учетом системы ограничений

На задачу (3.1) наложим ограничения на значения переменных в соответствии с условием. Полученная задача примет вид:

(3.3)

Для графического построения области определения преобразуем неравенства:

 

Область определения построена на рисунке 3.3.

Метод допустимых направлений Зойтендейка.

Метод Зойтендейка является расширением метода наискорейшего спуска, позволяющий учитывать ограничения. На каждом шаге строится возможное допустимое направление шага, и выбирается величина шага в соответствии с ограничениями [1].

Шаг 1.

Координаты точки будут определяться выражением:

 

Найдем направление вектора градиента по выражению (3.2) в точке :

 

Подставим известные значения в выражение для определения координаты следующей точки:

 

Найдем величину шага . Для этого подставим в функцию (3.1) найденные выражения для , т.е. получим функцию зависящую от величины шага. Затем исследуем полученную функцию на экстремум:

 

 

 

 

Найдем интервал допустимых значений , который обеспечивает нахождение точки внутри ОДЗП:

 

 

Найденное входит в найденный выше интервал. Тогда координаты следующей точки определяться по выражению:

 

Шаг 2.

Координаты точки будут определяться выражением:

 

Найдем направление вектора градиента по выражению (3.2) в точке :

 

Подставим известные значения в выражение для определения координаты следующей точки:

 

Найдем величину шага так же, как и на предыдущих шагах:

 

 

 

 

Найдем интервал допустимых значений , который обеспечивает нахождение точки внутри ОДЗП:

 

 

Найденное не входит в найденный выше интервал. В качестве величины шага возьмем правую границу интервала .

Найдем координаты следующей точки:

 

Шаг 3.

Найдем направление вектора градиента по выражению (3.2) в точке :

 

Вектор градиента направлен в сторону ОДЗП. Следовательно, координаты следующей точки будут определяться по выражению:

 

Подставим известные значения в выражение для определения координаты следующей точки:

 

Найдем величину шага так же, как и на предыдущих шагах:

 

 

 

 

Найдем интервал допустимых значений , который обеспечивает нахождение точки внутри ОДЗП:

 

 

Найденное входит в найденный выше интервал. Тогда координаты следующей точки определятся по выражению:

 

Шаг 4.

Координаты точки будут определяться выражением:

 

Найдем направление вектора градиента по выражению (3.2) в точке :

 

Подставим известные значения в выражение для определения координаты следующей точки:

 

Найдем величину шага так же, как и на предыдущих шагах:

 

 

 

 

Найдем интервал допустимых значений , который обеспечивает нахождение точки внутри ОДЗП:

 

 

Найденное не входит в найденный выше интервал. В качестве величины шага возьмем правую границу интервала .

Найдем координаты следующей точки:

 

Шаг 5.

Найдем направление вектора градиента по выражению (3.2) в точке :

 

Вектор градиента направлен за ОДЗП. Поэтому необходимо найти направление , в сторону которого нужно двигаться. Найдем это направление из условия , где – вектор, составленный из коэффициентов при переменных ограничения, на котором находится точка. Так как точка принадлежит граничной прямой , то направление очередного шага определяем из условия:

 

Отсюда следует, что . Тогда из условия нормировки:

 

 

При движении вдоль граничной прямой следует двигаться в направлении, которое составляет острый угол с вектором градиента, т.е. скалярное произведение векторов и должно быть больше или равно нуля [2]. Это достигается при выборе:

 

Координаты точки будут определяться выражением:

 

Подставим известные значения в выражение для определения координаты следующей точки:

 

Найдем величину шага :

 

 

 

 

Найдем интервал допустимых значений , который обеспечивает нахождение точки внутри ОДЗП. Ограничение, вдоль которого происходит движение, опускается:

 

 

Найденное входит в найденный выше интервал. Тогда координаты следующей точки определятся по выражению:

 

Найденная точка находится в вершине ОДЗП.

 

Проверим перпендикулярность направления движения и вектора градиента , для этого перемножим эти вектора скалярно:

 

Скалярное произведение равно нулю, следовательно вектор градиента перпендикулярен направлению движения, значит максимум достигнут.