Контрольная работа по предмету "Информатика"


Линейное программирование 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

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

смотрим на нижнюю строку – выбираем тот столбец, в котором нижний элемент отрицательный, если таких столбцов несколько, то выбираем любой (в нашем случае выбираем первый столбец );

далее смотрим на последний и выбранный столбцы – сравниваем отношения элементов последнего и выбранного столбцов (в выбранном столбце берем только положительные числа), и выбираем тот элемент выбранного столбца, где отношение элементов будет наименьшим (в нашем случае 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-ое уравнения выше написанной системы, считая базисными переменными начальной угловой точки , , и .

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

Последовательность симплекс-таблиц, приводящих к решению задачи, приведена ниже. Рамками обведены опорные элементы, а те свободные переменные, которые на данном шаге нельзя переносить в базисные из-за условий , обведены кружками.




Как видим, в последней строчке нет отрицательных чисел, следовательно, мы нашли решение и оно имеет вид и .

Ответ: и



Не сдавайте скачаную работу преподавателю!
Данную контрольную работу Вы можете использовать для выполнения своих заданий.

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :