Индивидуальные задания 12

Решить квадратичным симплекс-методом, найдя минимум целевой функции, если задача имеет следующий вид:

Коэффициенты целевой функции и системы ограничений берутся из таблицы 8 индивидуального задания 11 в соответствии с номером варианта.

Контрольные вопросы и задания

1. Какая функция называется выпуклой?

2. Какая функция называется гладкой?

3. Какая функция называется квадратичной?

4. Какая функция имеет локальный максимум, а какая абсолютный максимум?

5. В чем разница между локальным и абсолютным максимумом?

6. Какие методы поиска Вы знаете?

7. Сформулируйте алгоритм метода последовательного изменения координат и запишите в виде схемы.

8. Сформулируйте алгоритм метода наискорейшего подъема (спуска) и запишите в виде схемы.

9. В чем отличие метода наискорейшего подъема от метода наискорейшего спуска ?

10. Какие градиентные методы Вы знаете?

11. В чем отличие метода локального случайног поиска от метода нелокального случайног поиска?

12. В чем отличие метода штрафных функций при решении задачи выпуклого программирования и задачи линейного программирования?

13. Какой вид линий уровня задач квадратичного программирования Вы знаете?

14. Всегда ли задача линейного программирования и задача квадратичного программирования имеют решение?

Тестовые задания Тесты - выпуклое программирование

1*. Множество точек называется выпуклым, если

1. – оно является многоугольником;

2. – оно вместе с любыми двумя своими точками содержит весь отрезок, соединяющий эти точки;

3. – большинство точек отрезка принадлежит данному множеству;

4. – отрезок, соединяющий любые две несовпадающие точки множества, целиком принадлежит этому множеству.

2. Функция называется выпуклой, если

1. – она является строго вогнутой;

2. – она определена на выпуклом множестве W;

3. – она определена на выпуклом множестве W и выполняется условие для любых точек х₁,х₂  W и для любого t  [0,1];

4. - она определена на выпуклом множестве W и выполняется условие F(αX₁ + (1-α/2)X₂) ≤ αF(X₁) + (1-α/2)F(X₂) для любых точек х₁,х₂  W и для любого t  [0,1].

2. Функция называется гладкой, если

1 – непрерывны ее первые производные;

2 – непрерывны ее первая и вторая производные;

3 – на переменные наложено условие неотрицательности.

2. Какая функция имеет локальный максимум?

1. – если в окрестностях точки Х* выполняется неравенство любая точка, принадлежащая окрестности любого, в том числе бесконечно малого радиуса;

2. – если в окрестностях точки Х* выполняется неравенство любая точка, принадлежащая области определения функции;

3. – если в окрестностях точки Х* выполняется неравенство любая точка, принадлежащая окрестности любого, в том числе бесконечно малого радиуса.

2. Какая функция имеет абсолютный максимум?

1. – если в окрестностях точки Х* выполняется неравенство любая точка, принадлежащая окрестности бесконечно малого радиуса;

2. – если в окрестностях точки Х* выполняется неравенство любая точка, принадлежащая области определения функции;

3. – если в окрестностях точки Х* выполняется неравенство любая точка, принадлежащая определенному множеству.

2. Задача называется выпуклой, если она имеет

1. – выпуклую целевую функцию;

2. – выпуклую систему ограничений и выпуклую целевую функцию;

3. – выпуклую целевую функцию и нелинейную систему ограничений;

2. «Если область D замкнута и ограничена, то дифференцируемая функция z = f(x) достигает в этой области своего наибольшего или наименьшего значений или в стационарной точке, или в граничной точке области».

   1. – теорема Ляпунова;

   2. – теорема Неймана;

   3. – теорема Вейерштрасса;

   4. – теорема Лагранжа.

8*. Градиентные методы:

1. – наискорейшего подъема;

2. – штрафных функций;

3. –наискорейшего спуска;

4. – локального случайного поиска;

5. – нелокального случайного поиска.

9. В чем отличие метода локального случайного поиска от метода нелокального случайного поиска?

1. – в формировании случайного вектора ;

2. – в формировании случайного вектора

;

3. – в ограничении количества проводимых испытаний;

4. – в задании начального вектора Х₀.

10*. В чем отличие метода штрафных функций при решении задачи выпуклого программирования и задачи линейного программирования?

1. – определяется число М для задания функции штрафов, формируется массив случайных чисел, находится функция штрафов, определяется конечное число неудачных испытаний;

2. – задаются числа М_j для задания функции штрафов для каждого ограничения, формируется массив случайных чисел, находится функция штрафов, определяется конечное число неудачных испытаний;

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

4. – параметр М в процессе решения задачи меняется от малой величины до большой.

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

1. – методами отсечения;

2. – методами поиска;

3. – методами возможных направлений;

11. Градиентом функции называется

1. – вектор, проекциями которого на координатные оси служат соответствующие частные производные, т.е. F = ;

2. – вектор, направление которого указывает скорость убывания функции в этой точке;

3. – отрезок, ограничивающий область определения функции.

13. Функция называется сепарабельной, если

1. – ее можно представить в виде суммы функций, каждая из которых зависит только от одной переменной;

2. – ее можно представить в виде квадратичной функции;

3. – она содержит константу.

14*. Приближенное решение задач выпуклого программирования градиентным методом заключается

1. – в задании «выгодного» направления приближения к оптимальному решению;

2. – в нахождении оптимального решения за наименьшее число шагов;

3. – в поиске точки начального приближения;

4. – в нахождении приближенного значения оптимального решения в определенной области решения.

15*. Градиентный метод называется «методом наискорейшего спуска», если

1. – величина длины шага выбирается так, что приращение функции при перемещении из точки Х₀ в точку Х₁ будет наибольшим при решении задачи на минимум;

2. – величина длины шага выбирается так, что приращение функции при перемещении из точки Х₀ в точку Х₁ будет наименьшим при решении задачи на минимум;

3. – величина длины шага выбирается так, что приращение функции при перемещении из точки Х₀ в точку Х₁ будет наименьшим при решении задачи на минимум и наибольшим при решении задачи на максимум.

16. Для задач выпуклого программирования справедлива теорема: необходимым и достаточным условием оптимальности вектора является существование вектора такого, что пара будет седловой для соответствующей функции Лагранжа, т.е. при всех , .

1. – теорема двойственности;

2. – теорема Лагранжа;

3. – теорема Куна–Таккера;

4. – теорема Эйлера.