Учебная работа. Контрольная работа: Линейное программирование 2 3

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

X2

Ответ: и

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

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

Произведем преобразования начальной симплекс-таблицы симплекс-методом последующим образом: смотрим на нижнюю строчку – избираем тот столбец, в каком нижний элемент отрицательный, если таковых столбцов несколько, то избираем хоть какой (в нашем случае избираем 1-ый столбец ); дальше смотрим на крайний и избранный столбцы – сравниваем дела частей крайнего и избранного столбцов (в избранном столбце берем лишь положительные числа), и избираем тот элемент избранного столбца, где отношение частей будет минимальным (в нашем случае 9/3 и 0/1, потому что 2-ое отношение меньшее, как следует, опорным элементом будет 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

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


). При помощи вспомогательной переменной это ограничение представляется в виде равенства и вводится в симплекс-таблицу доборной строчкой

Где

,

где фигурные скобки означают дробную часть.

Таковым образом, мы получаем последующую таблицу:

-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/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-ое уравнения выше написанной системы, считая базовыми переменными исходной угловой точки , , и .

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

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

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

Ответ: и

]]>