Минимизировать функцию f(x) на всей числовой оси методом Ньютона. Критерием достижения требуемой точности считать выполнение неравенства
.
Минимизировать квадратичную функцию методом наискорейшего спуска, заканчивая вычисления при
,
.
И так далее по выше описанной цепочке.
Реализуем решение данной задачи в математическом пакете Mathcad.
Минимизировать функцию f(x) методом сопряженных направлений, заканчивая вычисления при
,
.
Шаг 1.
Шаг 2.
Шаг 3.
Шаг 4.
Решить задачу линейного программирования графическим методом.
Ответ:
и
Задача 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
|
Произведем преобразования исходной симплекс-таблицы симплекс-методом следующим образом:
1) смотрим на нижнюю строку – выбираем тот столбец, в котором нижний элемент отрицательный, если таких столбцов несколько, то выбираем любой (в нашем случае выбираем первый столбец
);
2) далее смотрим на последний и выбранный столбцы – сравниваем отношения элементов последнего и выбранного столбцов (в выбранном столбце берем только положительные числа), и выбираем тот элемент выбранного столбца, где отношение элементов будет наименьшим (в нашем случае 9/3 и 0/1, так как второе отношение наименьшее, следовательно, опорным элементом будет 1);
3) меняем местами переменные
и
, остальные переменные оставляем на своих местах;
4) на место опорного элемента ставим отношение 1/(опорный элемент);
5) на остальных местах разрешающей строки записываем соответствующие элементы исходной таблицы, деленные на опорный элемент;
6) на свободные места разрешающего столбца ставим со знаком минус соответствующие элементы исходной таблицы, деленные на опорный элемент;
7) оставшиеся свободные места в новой симплекс-таблице заполняем построчно следующим образом: из строки элементов исходной таблицы вычитаем произведение ее элемента из разрешающего столбца на уже заполненную разрешающую строку новой таблицы.
Производя преобразования симплекс-метода, получим такую последовательность симплекс-таблиц:
|
|
|
|
|
-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-ое уравнения выше написанной системы, считая базисными переменными начальной угловой точки
,
,
и .
Вспомогательную целевую функцию
выразим через свободные переменные
,
,
,
,
и
с помощью двух первых уравнений выше написанной системы.
Последовательность симплекс-таблиц, приводящих к решению задачи, приведена ниже. Рамками обведены опорные элементы, а те свободные переменные, которые на данном шаге нельзя переносить в базисные из-за условий
, обведены кружками.
Как видим, в последней строчке нет отрицательных чисел, следовательно, мы нашли решение и оно имеет вид
и
.
Ответ:
и