Линейное программирование 2 3

Задача 1 (16.88)

Минимизировать функцию f(x) на всей числовой оси методом Ньютона. Критерием достижения требуемой точности считать выполнение неравенства .

Решение:

Найдем первую и вторую производные исходной функции:

Выберем начальное приближение . И осуществим вычисления по формуле

Результаты запишем в таблице

n
0	0	2	1
1	-0,2	1,91	-0,1649
2	-0,175697	1,908525	-0,0032
3	-0,17520305	1,908524	-0,0000013

n=1

n=2

n=3

n=4

Далее мы заканчиваем вычисления, потому что данная точность достигнута. В результате мы получаем: и .

Осуществим проверку при помощи встроенной функции Minimize:

,

Ответ:

и

Задача 2 (16.115)

Выписать матрицу Q квадратичной функции f(x), найти ее градиент в точке и убедиться в выпуклости f(x) в .

,

Решение:

Запишем исходную функцию в следующем виде:

,

где

Тогда матрица Q примет вид:

Найдем градиент в точке по формуле , где r – вектор-столбец и равен :

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

Теперь убедимся в выпуклости f(x) в . Для того, чтобы исходная функция была выпуклой в , достаточно, чтобы матрица Q была положительно определена. Для этого найдем угловые миноры матрицы Q и если они будут больше нуля, то функция f(x) будет выпуклой в .

,

Так как , ,то функция f(x) выпукла в .

Проверка в Mathcad :

Проверка на выпуклость и нахождение градиента в точке x0

Ответ: градиент равен и функция f(x) будет выпуклой в .

Задача 3 (16.136)

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

Решение:

Тогда производные исходной функции будут иметь вид:

Выберем начальное приближение . Тогда

Для нахождения точки минимума функции найдем нули ее производной:

Зная , мы определим следующим образом:

И так далее по выше описанной цепочке.

Реализуем решение данной задачи в математическом пакете Mathcad.

Функция имеет вид:

Тогда коэффициенты будут равны

Возьмем следующие начальное приближение и :

Далее пишем программу

В результате получаем искомое решение и функцию :

Ответ:

и

Задача 4 (16.155)

Минимизировать функцию f(x) методом сопряженных направлений, заканчивая вычисления при , .

Решение:

Тогда частные производные исходной функции будут иметь вид:

Решение будем искать по следующему алгоритму:

Шаг 1.

Выбрав начальное приближение

,

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

=>> , откуда

Шаг 2.

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

=>> ,

откуда

Шаг 3.

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

=>> , откуда

Шаг 4.

следовательно требуемая точность достигнута и

Ответ:

Задача 5 (16.193)

Решить задачу линейного программирования графическим методом.

Решение:

Изобразим на плоскости наш многоугольник ABCDE (красного цвета) и одну из линий уровня (розового цвета).

Линии AB соответствует уравнение , BC соответствует , CD соответствует , DE соответствует и EA соответствует

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

X2

Ответ: и

Задача 6 (16.205)

Решить задачу линейного программирования в каноническом виде графическим методом.

Решение:

Матрица системы будет иметь следующий вид:

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

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

С учетом условия

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать