Задача 1 (16.88)
Минимизировать функцию f(x) на всей числовой оси методом Ньютона. Критерием достижения требуемой точности считать выполнение неравенства />.
/>
Решение:
Найдем первую и вторую производные исходной функции:
/>
/>
Выберем начальное приближение />. И осуществим вычисления по формуле
/>
Результаты запишем в таблице
n
/>
/>
/>
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:
/>
/>
Проверка на выпуклость и нахождение градиента в точке x
/>
Ответ: градиент равен />и функция f(x) будет выпуклой в />.
Задача 3 (16.136)
Минимизировать квадратичную функцию методом наискорейшего спуска, заканчивая вычисления при />, />.
/>
Решение:
/>
Тогда производные исходной функции будут иметь вид:
/>
Выберем начальное приближение />. Тогда --PAGE_BREAK--
/>
Для нахождения точки минимума функции /> найдем нули ее производной:
/>
Зная />, мы определим /> следующим образом:
/>
И так далее по выше описанной цепочке.
Реализуем решение данной задачи в математическом пакете Mathcad.
Функция имеет вид:
/>
/>
Тогда коэффициенты будут равны
/>
Возьмем следующие начальное приближение /> и />:
/>
/>
Далее пишем программу
/>
/>
В результате получаем искомое решение />и функцию />:
/>
Ответ:
/>и />
Задача 4 (16.155)
Минимизировать функцию f(x) методом сопряженных направлений, заканчивая вычисления при />, />.
/>
Решение:
/>
Тогда частные производные исходной функции будут иметь вид:
/>
/>
Решение будем искать по следующему алгоритму:
/>
Шаг 1.
Выбрав начальное приближение
/>, />
/>
Для нахождения точки минимума функции /> используем метод перебора:
/>
=>> />, откуда />
Шаг 2.
/>
Для нахождения точки минимума функции /> используем метод перебора:
/>
=>> />,
откуда
/>
Шаг 3.
/>
Для нахождения точки минимума функции /> используем метод перебора:
/>
=>> />, откуда
/>
Шаг 4.
/>
следовательно требуемая точность достигнута и
/>
Ответ:
/>
Задача 5 (16.193)
Решить задачу линейного программирования графическим методом.
/>
/>
Решение:
Изобразим на плоскости /> наш многоугольник ABCDE (красного цвета) и одну из линий уровня />(розового цвета).
Линии AB соответствует уравнение />, BC соответствует />, CD соответствует />, DE соответствует /> и EA соответствует />
Направление убывания функции /> указывает вектор />. Совершая параллельный перенос линии уровня вдоль направления />, находим ее крайнее положение. В этом положении прямая /> проходит через вершину /> многоугольника ABCDE. Поэтому целевая функция /> принимает минимальное значение /> в точке />, причем />
/>
Ответ: /> и />
Задача 6 (16.205)
Решить задачу линейного программирования в каноническом виде графическим методом.
/>
/>
Решение:
Матрица системы будет иметь следующий вид:
/>
Ранг этой матрицы равен />. Тогда число свободных переменных равно />, поэтому для решения задачи можно использовать графический метод. Решив систему ограничений – равенств относительно базисных переменных />, />, получим:
/>
Исключая с помощью полученной системы переменные />, /> из выражения для целевой функции, получаем:
/>
С учетом условия неотрицательности />, />, и последних равенств получаем следующую задачу:
/>
/>/>
Изобразим на плоскости /> наш многоугольник ABCDEJ (красного цвета) и одну из линий уровня />(розового цвета). продолжение
--PAGE_BREAK--
Линии AB соответствует уравнение />, BC соответствует />, CD соответствует />, DE соответствует />, EJ соответствует /> и JA соответствует />.
Направление убывания функции /> указывает вектор />. Совершая параллельный перенос линии уровня вдоль направления />, мы видим, что целевая функция содержит сторону AB многоугольника ABCDEJ. Таким образом, все точки отрезка AB являются точками минимума функции />. Так как концы A и B имеют координаты /> и /> соответственно, то найдем отсюда координаты /> и />:
/>
Тогда любая точка минимума /> представима в виде
/>
где />. Минимальное значение целевой функции
/>
Ответ: бесконечное множество решений
/>, где /> и />.
Задача 7 (16.216)
Решить задачу линейного программирования симплекс — методом, находя начальную угловую точку методом искусственного базиса.
/>
/>
Решение:
Матрица системы имеет вид
/>.
Ее ранг равен 3. Введем дополнительные переменные /> и запишем условие вспомогательной задачи линейного программирования для рассматриваемого случая:
/>
/>
Считая дополнительные переменные /> базисными, запишем симплекс таблицу этой задачи, соответствующую угловой точке />:
/>
/>
/>
/>
/>
3
-2
3
2
9
/>
1
2
-1
1
/>
-1
-1
2
1
6
-3
1
-4
-4
-15
Произведем преобразования исходной симплекс-таблицы симплекс-методом следующим образом:
смотрим на нижнюю строку – выбираем тот столбец, в котором нижний элемент отрицательный, если таких столбцов несколько, то выбираем любой (в нашем случае выбираем первый столбец />);
далее смотрим на последний и выбранный столбцы – сравниваем отношения элементов последнего и выбранного столбцов (в выбранном столбце берем только положительные числа), и выбираем тот элемент выбранного столбца, где отношение элементов будет наименьшим (в нашем случае 9/3 и 0/1, так как второе отношение наименьшее, следовательно, опорным элементом будет 1);
меняем местами переменные /> и />, остальные переменные оставляем на своих местах;
на место опорного элемента ставим отношение 1/(опорный элемент);
на остальных местах разрешающей строки записываем соответствующие элементы исходной таблицы, деленные на опорный элемент;
на свободные места разрешающего столбца ставим со знаком минус соответствующие элементы исходной таблицы, деленные на опорный элемент;
оставшиеся свободные места в новой симплекс-таблице заполняем построчно следующим образом: из строки элементов исходной таблицы вычитаем произведение ее элемента из разрешающего столбца на уже заполненную разрешающую строку новой таблицы.
Производя преобразования симплекс-метода, получим такую последовательность симплекс-таблиц:
/>
/>
/>
/>
/>
-3
-8
6
-1
9
/>
1
2
-1
1
/>
1
1
1
2
6
3 продолжение
--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
/>
3/7
2/7
-1/7
2/7
16/7
/>
2/7
-1/7
-3/7
-1/7
-1/7
1
1
1
/>
/>
/>
/>
/>
2
8
-3
-1
2
/>
-2
-9
4
1
3
/>
1
2
-1
2
/>
-2
-7
3
1
1
1
1
1
Полученная симплекс-таблица не только соответствует допустимому базисному решению, но и дает решение рассматриваемой задачи:
/>и />
Ответ: /> и />
Задача 9 (16.258)
Решить задачу дробно — линейного программирования.
/>
/>
Знаменатель /> целевой функции положителен при всех xиз допустимого множества U, так как />.
Вводим новые переменные
/>, />, />
и получаем следующую задачу линейного программирования:
/>
/>/>
Неизвестные параметры мы можем уже из этих выражений найти:
/>/>
/>/>/>,
Ответ: />, />
Задача 10 (16.268)
Решить задачу квадратичного программирования.
/>,
/>
Решение:
Матрица /> нашей квадратичной функции положительно определена. Наша исходная задача имеет вид:
/>(1)
/>, />, (2)
/>, />. (3)
На основании теоремы Куна-Таккера точка минимума /> целевой функции /> из (1) на допустимом множестве (2) и (3) может быть найдена как решение следующей системы уравнений с дополнительными переменными />; />:
/>, />,
/>, />,
/>, />,
/>, />,
удовлетворяющее условию неотрицательности:
/>, />, />,
/>, />.
Применяя выше описанные условия, мы преобразуем исходную задачу в следующий вид:
/>
Будем искать угловую точку множества, определяемого этой системой, методом искусственного базиса. Введем дополнительные переменные /> и /> в 3-е и 4-ое уравнения выше написанной системы, считая базисными переменными начальной угловой точки />, />, /> и />.
Вспомогательную целевую функцию /> выразим через свободные переменные />, />, />, />, /> и /> с помощью двух первых уравнений выше написанной системы.
Последовательность симплекс-таблиц, приводящих к решению задачи, приведена ниже. Рамками обведены опорные элементы, а те свободные переменные, которые на данном шаге нельзя переносить в базисные из-за условий />, обведены кружками.
/>
/>
Как видим, в последней строчке нет отрицательных чисел, следовательно, мы нашли решение и оно имеет вид />и />.
Ответ: />и />