Скачать .docx |
Реферат: Контрольная работа: Линейное программирование 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. Поэтому целевая функция
принимает минимальное значение
в точке
, причем
|

Ответ: и
Задача 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-ое уравнения выше написанной системы, считая базисными переменными начальной угловой точки
,
,
и
.
Вспомогательную целевую функцию выразим через свободные переменные
,
,
,
,
и
с помощью двух первых уравнений выше написанной системы.
Последовательность симплекс-таблиц, приводящих к решению задачи, приведена ниже. Рамками обведены опорные элементы, а те свободные переменные, которые на данном шаге нельзя переносить в базисные из-за условий , обведены кружками.
Как видим, в последней строчке нет отрицательных чисел, следовательно, мы нашли решение и оно имеет вид и
.
Ответ: и