Задача 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. Поэтому целевая функция принимает минимальное значение в точке , причем
Ответ: и
Задача 6 (16.205)
Решить задачу линейного программирования в каноническом виде графическим методом.
Решение:
Матрица системы будет иметь следующий вид:
Ранг этой матрицы равен . Тогда число свободных переменных равно , поэтому для решения задачи можно использовать графический метод. Решив систему ограничений – равенств относительно базисных переменных , , получим:
Исключая с помощью полученной системы переменные , из выражения для целевой функции, получаем:
С учетом условия неотрицательности , , и последних равенств получаем следующую задачу:
Изобразим на плоскости наш многоугольник ABCDEJ (красного цвета) и одну из линий уровня (розового цвета).
Линии AB соответствует уравнение , BC соответствует , CD соответствует , DE соответствует , EJ соответствует и JA соответствует .
Направление убывания функции указывает вектор . Совершая параллельный перенос линии уровня вдоль направления , мы видим, что целевая функция содержит сторону AB многоугольника ABCDEJ. Таким образом, все точки отрезка AB являются точками минимума функции . Так как концы A и B имеют координаты и соответственно, то найдем отсюда координаты и :
Тогда любая точка минимума представима в виде
где . Минимальное значение целевой функции
Ответ: бесконечное множество решений
, где и .
Задача 7 (16.216)
Решить задачу линейного программирования симплекс - методом, находя начальную угловую точку методом искусственного базиса.
Решение:
Матрица системы имеет вид
.
Ее ранг равен 3. Введем дополнительные переменные и запишем условие вспомогательной задачи линейного программирования для рассматриваемого случая:
Считая дополнительные переменные базисными, запишем симплекс таблицу этой задачи, соответствующую угловой точке :
|
| 3 | -2 | 3 | 2 | 9 |
|
| 1 | 2 | -1 | 1 | 0 |
|
| -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 | 0 |
|
| 1 | 1 | 1 | 2 | 6 |
| 3 | 7 | -7 | -1 | -15 |
|
| -2 | -6 | 5 | 1 | 9 |
|
| 1 | 2 | -1 | 1 | 0 |
|
| -1 | -3 | 3 | -2 | 6 |
| 4 | 9 | -8 | 1 | -15 |
|
| -2/5 | -6/5 | 1/5 | 1/5 | 9/5 |
|
| 3/5 | 4/5 | 1/5 | 6/5 | 9/5 |
|
| 1/5 | 3/5 | -3/5 | -13/5 | 3/5 |
| 4/5 | -3/5 | 8/5 | 13/5 | -3/5 |
|
| 0 | 2 | -1 | -5 | 3 |
|
| 1/3 | -4/3 | 1 | 14/3 | 1 |
|
| 1/3 | 5/3 | -1 | -13/3 | 1 |
| 1 | 1 | 1 | 0 | 0 |
В нижней строке последней симплекс-таблицы нет отрицательных элементов, следовательно, минимум вспомогательной целевой функции достигнут и есть угловая точка допустимого множества исходной задачи линейного программирования, тогда
Ответ: и .
Задача 8 (16.237)
Решить полностью целочисленную задачу линейного программирования методом Гомори.
Решение:
Введем дополнительные переменные и запишем условие вспомогательной задачи линейного программирования для рассматриваемого случая:
Считая дополнительные переменные базисными, запишем симплекс таблицу этой задачи, соответствующую угловой точке :
|
| 1 | 0 | 2 | 1 | 8 |
|
| 1 | 1 | 0 | -1 | 4 |
|
| -1 | 2 | 1 | 3 | 6 |
| -1 | -3 | -3 | -3 | -18 |
Произведем преобразования исходной симплекс-таблицы симплекс-методом следующим образом: смотрим на нижнюю строку – выбираем тот столбец, в котором нижний элемент отрицательный, если таких столбцов несколько, то выбираем любой (в нашем случае выбираем первый столбец ); далее смотрим на последний и выбранный столбцы – сравниваем отношения элементов последнего и выбранного столбцов (в выбранном столбце берем только положительные числа), и выбираем тот элемент выбранного столбца, где отношение элементов будет наименьшим (в нашем случае 9/3 и 0/1, так как второе отношение наименьшее, следовательно, опорным элементом будет 1); меняем местами переменные и , остальные переменные оставляем на своих местах; на место опорного элемента ставим отношение 1/(опорный элемент); а остальных местах разрешающей строки записываем соответствующие элементы исходной таблицы, деленные на опорный элемент; на свободные места разрешающего столбца ставим со знаком минус соответствующие элементы исходной таблицы, деленные на опорный элемент; оставшиеся свободные места в новой симплекс-таблице заполняем построчно следующим образом: из строки элементов исходной таблицы вычитаем произведение ее элемента из разрешающего столбца на уже заполненную разрешающую строку новой таблицы. Производя преобразования симплекс-метода, получим такую последовательность симплекс-таблиц:
|
| 4/3 | -2/3 | 5/3 | -1/3 | 6 |
|
| 2/3 | 5/3 | 1/3 | 1/3 | 6 |
|
| -1/3 | 2/3 | 1/3 | 1/3 | 2 |
| -2 | -1 | -2 | 1 | -12 |
|
| 1 | 1 | 2 | 0 | 8 |
|
| 3/2 | -5/2 | -1/2 | -1/2 | 1 |
|
| -1/2 | 3/2 | 1/2 | 1/2 | 3 |
| -5/2 | 3/2 | -3/2 | 3/2 | -9 |
|
|
|
|
| ||
|
| 1/2 | 1/2 | 1/2 | 0 | 4 |
|
| 7/4 | -9/4 | 1/4 | -1/2 | 3 |
|
| -3/4 | 5/4 | -1/4 | 1/2 | 1 |
| -7/4 | 9/4 | 3/4 | 3/2 | -3 |
|
| -2/7 | 8/7 | 3/7 | 1/7 | 22/7 |
|
| 4/7 | -9/7 | 1/7 | -2/7 | 12/7 |
|
| 3/7 | 2/7 | -1/7 | 2/7 | 16/7 |
| 1 | 0 | 1 | 1 | 0 |
Как видим, в последней строке таблицы все элементы положительны, то есть получаем решение и . Но это решение не удовлетворяет условию целочисленности, поэтому дополняем последнюю симплекс-таблицу строкой, используя следующие правила: среди нецелых элементов выбирается произвольный элемент , по r-ой строке симплекс-таблицы составляется дополнительное ограничение вида (здесь мы полагаем, что свободные переменные имеют номера m+1,…,n). С помощью вспомогательной переменной это ограничение представляется в виде равенства и вводится в симплекс-таблицу дополнительной строкой
Где
,
где фигурные скобки означают дробную часть.
Таким образом, мы получаем следующую таблицу:
|
|
|
|
| ||
|
| -2/7 | 8/7 | 3/7 | 1/7 | 22/7 |
|
| 4/7 | -9/7 | 1/7 | -2/7 | 12/7 |
|
| 3/7 | 2/7 | -1/7 | 2/7 | 16/7 |
|
| 2/7 | -1/7 | -3/7 | -1/7 | -1/7 |
| 1 | 0 | 1 | 1 | 0 |
Так как , то после дополнения строкой симплекс-таблица перестает соответствовать допустимому базисному решению задачи линейного программирования, которую она описывает.
Для перехода к допустимому базисному решению производятся следующие операции:
а) строка с отрицательным свободным членом считается разрешающей;
б) если все коэффициенты , то задача не имеет решения, в противном случае номер l разрешающего столбца находится из условия:
в) совершается преобразование симплекс-таблицы с опорным элементом
Если в новой таблице по-прежнему есть хотя бы один отрицательный свободный член, то описанная процедура повторяется, начиная с операции а), необходимое число раз.
Применяя данные правила к нашей симплекс-таблице, мы получаем следующие преобразования:
|
|
|
|
| ||
|
| -2/7 | 8/7 | 3/7 | 1/7 | 22/7 |
|
| 4/7 | -9/7 | 1/7 | -2/7 | 12/7 |
|
| 3/7 | 2/7 | -1/7 | 2/7 | 16/7 |
|
| 2/7 | -1/7 | -3/7 | -1/7 | -1/7 |
| 1 | 0 | 1 | 1 | 0 |
|
| 2 | 8 | -3 | -1 | 2 |
|
| -2 | -9 | 4 | 1 | 3 |
|
| 1 | 2 | -1 | 0 | 2 |
|
| -2 | -7 | 3 | 1 | 1 |
| 1 | 0 | 1 | 1 | 0 |
Полученная симплекс-таблица не только соответствует допустимому базисному решению, но и дает решение рассматриваемой задачи:
и
Ответ: и
Задача 9 (16.258)
Решить задачу дробно - линейного программирования.
Знаменатель целевой функции положителен при всех xиз допустимого множества U, так как .
Вводим новые переменные
, ,
и получаем следующую задачу линейного программирования:
Неизвестные параметры мы можем уже из этих выражений найти:
,
Ответ: ,
Задача 10 (16.268)
Решить задачу квадратичного программирования.
,
Решение:
Матрица нашей квадратичной функции положительно определена. Наша исходная задача имеет вид:
(1)
, , (2)
, . (3)
На основании теоремы Куна-Таккера точка минимума целевой функции из (1) на допустимом множестве (2) и (3) может быть найдена как решение следующей системы уравнений с дополнительными переменными ; :
, ,
, ,
, ,
, ,
удовлетворяющее условию неотрицательности:
, , ,
, .
Применяя выше описанные условия, мы преобразуем исходную задачу в следующий вид:
Будем искать угловую точку множества, определяемого этой системой, методом искусственного базиса. Введем дополнительные переменные и в 3-е и 4-ое уравнения выше написанной системы, считая базисными переменными начальной угловой точки , , и .
Вспомогательную целевую функцию выразим через свободные переменные , , , , и с помощью двух первых уравнений выше написанной системы.
Последовательность симплекс-таблиц, приводящих к решению задачи, приведена ниже. Рамками обведены опорные элементы, а те свободные переменные, которые на данном шаге нельзя переносить в базисные из-за условий , обведены кружками.
Как видим, в последней строчке нет отрицательных чисел, следовательно, мы нашли решение и оно имеет вид и .
Ответ: и