rpd000000406 (230100 (09.03.01).Б2 Автоматизированные системы обработки информации и управления), страница 5

20. Чем отличается двойственный симплекс-метод от обычного (1. Структурой симплекс- таблиц 2. Правилом проверки условий оптимальности 3. Порядком выбора разрешающего элемента 4. Порядком преобразования симплекс-таблиц 5. Возможными исходами работы алгоритма)?

21. Чем определяется необходимость выделения специальных ЗЛП (1. Принципиальной невозможностью использования для них универсальных алгоритмов решения

2. Неэффективностью использования универсальных алгоритмов по вычислительной сложности или (и) по требуемой памяти ЭВМ 3. Большими погрешностями работы универсальных алгоритмов)?

22. Какие из перечисленных ниже задач являются специальными ЗЛП (1. Задача коммивояжера 2. Производственная задача с ограничениями на мощности производств 3.Задача о максимальном потоке через транспортную сеть 4. Задача о составлении рациона кормления животных без ограничений на объемы кормов 5. Т-задача 6. ЗЛП с блочно-диагональной матрицей условий)?

23. Чем отличается специальный алгоритм поиска допустимого решения (САПДР) Т-задачи от метода минимизации невязок (1. В САПДР формируется вспомогательная задача специальной структуры 2. Используемыми структурами данных 3. Правилами проверки условий пустоты области допустимых решений 4. В САПДР применяются эвристические правила)?

24. Из каких двух частей состоит специальный алгоритм поиска допустимого решении Т-задачи (1. Формирования матрицы перевозок и значения целевой функции 2. Формирования базисного множества 3. Формирования матрицы перевозок, соответствующих компонент базисного множества и значения целевой функции 4. Дополнения базисного множества до необходимой размерности)?

25. Определите набор и порядок действий, определяющих работу специального алгоритма поиска оптимального решения Т-задачи (1. Формирование допустимого решения 2.Формирование цепочки 3. Определение элемента, вводимого в базис

4. Проверка условий неограниченности целевой функции 5. Определение элемента, выводимого из базиса 6. Расчет потенциалов 7. Корректировка базисного решения

Расчет симплекс-разностей 8. Проверка условий оптимальности).

26. Определите набор и последовательность действий алгоритма симплекс-таблиц T₁(B_k)

(1. Корректировка базисного множества 2. Проверка условий оптимальности 3. Проверка неограниченности целевой функции 4. Выбор разрешающей строки 5. Выбор разрешающего столбца 6. Корректировка действительной части симплекс- таблицы 7. Расчет разрешающего столбца 8. Расчет симплекс-разностей 9. Проверка пустоты области допустимых решений )

27. Определите набор и последовательность действий алгоритма симплекс-таблиц T₂(B_k)

(1. Корректировка базисного множества 2. Проверка условий оптимальности 3. Проверка неограниченности целевой функции 4. Выбор разрешающей строки 5. Выбор разрешающего столбца 6. Корректировка действительной части симплекс- таблицы 7. Расчет разрешающего столбца 8. Расчет симплекс-разностей 9. Проверка пустоты области допустимых решений )

28. Определите набор и последовательность действий алгоритма симплекс-таблиц

(1. Корректировка базисного множества 2. Проверка условий оптимальности 3. Проверка неограниченности целевой функции 4. Выбор разрешающей строки 5. Выбор разрешающего столбца 6. Корректировка действительной части симплекс- таблицы 7. Расчет разрешающего столбца 8. Расчет симплекс-разностей 9. Проверка пустоты области допустимых решений )

29. Определите набор и последовательность действий алгоритма симплекс-таблиц

(1. Корректировка базисного множества 2. Проверка условий оптимальности 3. Проверка неограниченности целевой функции 4. Выбор разрешающей строки 5. Выбор разрешающего столбца 6. Корректировка действительной части симплекс- таблицы 7. Расчет разрешающего столбца 8. Расчет симплекс-разностей 9. Проверка пустоты области допустимых решений 10. Расчет разрешающей строки )

30. Какие дополнительные возможности применения линейного программирования знаете (1. Поиск допустимого решения методом минимизации невязок 2. Решение нелинейных задач, допускающих эквивалентную линеаризацию 3. Решение исходной задачи двойственным симплекс-методом 4. Исследование влияния на оптимальное решение вариаций параметров ЗЛП без повторного решения задачи сначала)?

ТЕСТ_ВОПРОС_НП.doc

ВОПРОСЫ ДЛЯТЕСТОВ ПО НЕЛИНЕЙНОМУ ПРОГРАММИРОВАНИЮ

1. Сформулируйте признаки, по которым может быть осуществлена классификация ЗНП. Какие подклассы ЗНП выделяются по этим признакам?

2. По каким принципам может быть осуществлена классификация методов одномерной нелинейной оптимизации?

3. Сформулируйте условия унимодальности одномерной функции? В какой взаимосвязи оно находится с понятием выпуклости?

4. Как свойство унимодальности может быть использовано для сокращения интервала неопределенности в методах одномерной оптимизации без использования информации о производных целевой функции?

5. Сформулируйте правила работы метода дихотомического поиска. Как в этом методе сокращается интервал неопределенности?

6. Сформулируйте принципы работы метода золотого сечения. Как в этом методе сокращается интервал неопределенности?

7. Как формируется последовательность чисел Фибоначчи? Как они используются в алгоритме одномерного поиска, реализующем соответствующий метод одномерной оптимизации?

8. Как в методе Фибоначчи сокращается интервал неопределенности? Как, исходя из этого, определяется число итераций метода для достижения заданной точности оптимизации?

9. Сравните по эффективности следующие методы одномерной оптимизации: дихотомического поиска, Фибоначчи и золотого сечения.

10. Определите идею метода деления отрезка пополам.

11. Определите идею метода Ньютона для решения задачи одномерной оптимизации. При каких условиях гарантируется его эффективная работа?

12. Какие существуют подходы к решению многоэкстремальных задач одномерной оптимизации?

13. Опишите идею метода случайного поиска. В чем его достоинства и недостатки?

14. Опишите идею и основные этапы метода аппроксимации.

15. Как строится аппроксимирующая модель целевой функции? Какие сложности вычислительного характера при этом возникают?

16. Какая информация из аппроксимирующей модели и как используется для определения точки глобального экстремума?

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

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

19. Опишите идею и охарактеризуйте метод покоординатного спуска Зейделя. При решении каких задач и на каком этапе сходимость этого метода замедляется?

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

21. Какими потенциальными возможностями обладают методы случайного поиска применительно к решению задач многомерной безусловной оптимизации?

22. В каком виде используется информация о производных целевой функции в методах многомерной безусловной оптимизации?

23. Как формируется направление поиска в методе наискорейшего спуска? При каких условиях метод работает эффективно, а когда сходимость метода существенно замедляется? Что такое эффект зигзага?

24. Поясните идею многомерного варианта метода Ньютона. Какая информация о целевой функции используется на каждой итерации метода? Дайте характеристику сходимости метода.

25. Какие подходы знаете к решению многоэкстремальных задач многомерной безусловной оптимизации? Сформулируйте идею сведения такой задачи к последовательному решению вложенных друг в друга задач одномерной оптимизацию. Дайте характеристику этому подходу.

26. Опишите идею методов возможных направлений. Дайте определения конуса возможных направлений, возможного направления.

27. Какие теоретические положения лежат в основе методов возможных направлений?

28. Какие знаете виды геометрической формы необходимых условий оптимальности решения задач нелинейной условной оптимизации?

29. В чем состоит проблема учета нелинейных ограничений типа равенств в методах возможных направлений? Каков подход к решению этой проблемы?

ТЕСТ_ВОПРОС_ДИСП.doc

ВОПРОСЫ ДЛЯ ТЕСТИРОВАНИЯ. ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ

1. Каков основной признак задач дискретного программирования (1. Целочисленность оптимизационных переменных 2. Бинарный характер оптимизационных переменных 3. Несвязность области допустимых решений)?

2. Какие основные подклассы задач дискретного программирования знаете

(1. Целочисленные 2.Комбинаторные 3. Частично-целочисленные 4. Задачи о назначениях)?

1. Какие примеры типовых комбинаторных задач дискретного программирования знаете (1. Задача о ранце 2. Задача о назначениях 3. Задача о размещении взаимосвязанных производств 4. Т-задача с фиксированными доплатами 5. Задача о коммивояжере)?

3. Какие задачи из перечисленных ниже приводятся к задачам частично-целочисленного программирования (1. Задача о ранце 2. Задача коммивояжера

3. Задача о назначении 4. Задачи с альтернативными ограничениями 5.Т-задача с фиксированными доплатами)

1. Для каких задач дискретного программирования из перечисленных ниже возможно применение методов неявного перебора (1. Целочисленных 2. Частично-целочисленных 3. Комбинаторных 4. Задач с альтернативными ограничениями)?

1. За счет чего реализуется экономия вычислений при реализации метода лексикографического неявного перебора (1. За счет отбрасывания неэффективных точек 2. За счет экономии на проверке ограничений)?

1. Какие процедуры используются в методе лексикографического неявного перебора для экономии вычислений (1. Правило допустимой точки 2. Фильтрующее ограничение 3. Отсеивание недопустимых точек 4. Переупорядочение переменных по быстроте изменения 5. Упорядочение ограничений по жесткости)?

1. К каким задачам дискретного программирования применяется метод векторной решетки ( 1. К любым задачам 2. К нелинейным целочисленным задачам 3. К линейным частично-целочисленным задачам 4. К линейным целочисленным задачам)?

8. К какому виду должна быть приведена оптимизационная задача для непосредственного применения метода векторной решетки (1. Направление оптимизации на минимум 2. Направление оптимизации на максимум 3. Все коэффициенты целевой функции отрицательные 4. Все коэффициенты целевой функции неотрицательные 5. Все ограничения – равенства 6. Все ограничения – неравенства)?

9. За счет чего реализуется экономия вычислений при реализации метода неявного перебора по векторной решетке (1. За счет неполного перебора точек 2. За счет экономии на проверке ограничений)?

10. При работке каких критериев в методе неявного перебора по векторной решетке используется свойство неотрицательности коэффициентов целевой функции (1. Правило допустимой точки 2. Критерий КПИА 3. Критерий КН 4. Критерии КПП)?

11. К каким элементам векторной решетки применяются критерии КН и КПИА (1. КН и КПИА к точке 2. КН и КПИА к маршруту 3. КН к точке, КПИА к маршруту 4. КН к маршруту, КПИА к точке)?

12. В какой точке начинает и заканчивает работу метод неявного перебора по векторной решетке (1. Начинает – в нулевой точке, заканчивает – в точке оптимального решения 2. Начинает – в первой найденной допустимой точке, заканчивает – в точке оптимального решения 3. Начинает и заканчивает в нулевой точке)?

1. 13. Через какой критерий (правило) проявляется действие критерия КПП в методе неявного перебора по векторной решетке (1. Правило допустимой точки 2. КПИА

14. С какими точками большей частью работает метод неявного перебора по векторной решетке (1. С допустимыми 2. С недопустимыми)?

15. С какими точками работает метод неявного перебора, основанный на стратегии локального поиска (1. С допустимыми 2. С недопустимыми)?

16. Гарантируется ли нахождение оптимального решения при применении метода неявного перебора, основанного на стратегии локального поиска (1. Да 2. Нет)?

17. Какие основные процедуры являются составными частями метода неявного перебора, основанного на стратегии локального поиска (1. Отсев недопустимых точек 2. Нахождение начальной допустимой точки 3. Выбор точек с лучшими значениями целевой функции 4. Перебор допустимых точек их окрестности найденной на предыдущем этапе допустимой точки)?

18. Чем обеспечивается проведение нескольких больших итераций в методе неявного перебора, основанном на стратегии локального поиска (1. Выбором как можно лучшей начальной допустимой точки 2. Стохастичностью процедуры формирования начальных точек)?

19. Какие из указанных ниже способов организации перебора в окрестности рассматриваемой точки применяются в методе неявного перебора, основанном на стратегии локального поиска (1. k-замен, 2. Перебор до первого улучшения 3.Лексикографический перебор 4. Перебор по всей окрестности 5. Круговой поиск

6. Перебор, основанный на эвристических правилах)

20. К каким задачам дискретного программирования применяется метод отсекающих плоскостей( 1. К любым задачам 2. К нелинейным целочисленным задачам 3. К линейным частично-целочисленным задачам 4. К линейным целочисленным задачам)?

21. Что такое «правильное отсечение» в методе отсекающих плоскостей

(1. Ограничение, отсекающее недопустимое решение 2. Ограничение, осекающее неоптимальное решение 3. Ограничение, отсекающее решение, не удовлетворяющее условиям целочисленности исходной задачи, но не отсекающее ни одного допустимого решения 4. Ограничение, отсекающее нецелочисленное решение)?