Какую задачу нельзя решать методами динамического программирования тест

Для решения таких задач метод динамического программирования применить нельзя

2015-03-20
647

Например, если в качестве оценки пути принята немонотонная функция суммы шаговых затрат. Или, например, сумма произведений шаговых затрат S_i на двух последних шагах,

S₁ S₂ + S₂ S₃ +…+ S_k-1 S_k , где k- число шагов, которое в задаче с сеткой равно m + n.

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

Объём вычислений резко возрастает при возрастании размерности задачи ( это число шаговых вариантов или в конечном итоге размер сетки). В нашей задаче из одного состояния ( узла ) можно перейти не более, чем в два других.

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

Даже такой эффективный алгоритм, как алгоритм динамичес-кого программирования, который хорошо справляется с задачами малой и средней размерности, мало что может дать при числе ва-риантов на каждом шаге порядка десятков тысяч и более. Однако и для таких задач возможны различные ухищрения для сокраще-ния времени счёта.

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

В частности, можно ли применять метод, если некоторые переходы изначально запрещены, или количественная оценка пути является более сложной функцией (даются конкретные функции), чем сумма шаговых затрат. Для понимания сущности метода представляется интересным вопрос о его применимости, если в той же задаче с сеткой в качестве количественной оценки пути принять не просто сумму затрат, но и количество изменений направления, умноженное на заданное число (штраф за “извили-стость” пути).

Программа считает, что в этом случае алгоритм динамичес-кого программирования применить нельзя. Однако речь идёт об алгоритме, реализованном в данной программе, в котором сос-тояние – это узел. Если же принять, что состояние это отрезок, соединяющий два узла, то можно реализовать несколько более сложный алгоритм, но всё того же метода динамического прог-раммирования.

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

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

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

Наличие локальных минимумов (иначе говоря многоэкстре-мальность задачи ) является серьёзным препятствием для применения многих методов оптимизации [4].

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

В некоторых практических задачах оптимизации для приме-нения метода динамического програмирования приходится искусственно вводить дискретность перебора. Если речь идёт о поиске непрерывной оптимальной траектории, то эта траектория представляется ломаной линией из – за введённой дискретности.

В этом случае точность решения задачи тем выше, чем меньший дискрет используется (например, меньше размер ячеек двумерной сетки).

Источник

• НИУ
• ГУ (Екатеринбург)
• МФПА
• ИММиФ
• ГЭИТИ
• СПбГТИ ФЭМ

Экспресс-подготовка к онлайн-тестированию:

для студентов дистанционного обучения, при устройстве на работу, прохождении аттестаций

Сдаешь тесты самостоятельно?

Закажи скайп-консультацию и узнай все секреты успешной сдачи экзаменов онлайн!

Вы здесь: Home База вопросов ИММиФ Математические методы Тесты с ответами ИММиФ Математические методы Тесты с ответами Тема 1-2-3-4

Математические методы Тесты с ответами Тема 1-2-3-4

Для быстрого поиска по странице нажмите Ctrl+F и в появившемся окошке напечатайте слово запроса (или первые буквы)

ТЕМА 1

Какой из этапов математического моделирования должен проводиться перед остальными ?

+Постановка экономической проблемы и ее качественный анализ

Математический анализ модели

Подготовка исходной информации

Построение математической модели

Модель межотраслевых связей является …

Модель производства, основанная на производственных функциях, построенная на основе обработки статистических данных, является …

На каком из этапов рационально использовать ЭВМ?

Математический анализ модели

Постановка экономической проблемы и ее качественный анализ

Построение математической модели

Подготовка исходной информации

ТЕМА 2

Дана задача линейного программирования

Сформулированная в таком виде она является

Вектор градиента при решении задачи геометрическим методом имеет координаты:

Область допустимых решений D есть геометрическая фигура, являющаяся:

Число переменных у двойственной задачи равно…

Целевая функция двойственной задачи будет…

Все переменные двойственной задачи будут …

Дана транспортная задача

Предложение\спрос 200 Z 170

При каком значении Z транспортная задача будет закрытой?

Сколько базисных (основных) переменных будет у данной задачи?

Сколько свободных (не основных) переменных будет у данной задачи?

Поставка Z в распределительном методе решения транспортной задачи по приведенной схеме равна:

Величина коэффициента затрат базисной клетки равен 6, один из потенциалов равен 4. Тогда другой потенциал равен…

ТЕМА 3

Какую задачу нельзя решать методами динамического программирования:

+определения оптимального ассортимента продукции

разработка правил управления запасами

разработка принципов календарного планирования производства

Согласно принципу оптимальности Беллмана, оптимальное управление на данном шаге зависит от оптимального управления на …

На сколько этапов разбивается процесс решения задачи о распределении средств между четырьмя предприятиями:

Какому условию должна удовлетворять целевая функция при ее решении методами динамического программирования:

Среди критериев выбора оптимального решения при играх с природой наиболее осторожным (с минимальным риском) является критерий:

Тема 4

Дана платежная матрица парной матричной игры:

Ai Bj B1 B2 B3 B4

Нижняя цена игры равна

Дана платежная матрица парной матричной игры:

Цена игры равна

Дана платежная матрица парной матричной игры:

Ai Bj B1 B2 B3 B4

Верхняя цена игры равна

Дана платежная матрица парной матричной игры:

Ai Bj B1 B2 B3 B4

Верно ли то, что оптимальная стратегия игрока А равна А3?

Дана матрица выигрышей игры с природой:

Верно ли то, что оптимальной стратегией, в соответствии с критерием Лапласа, будет стратегия А3?

Источник

Математические методы. Тест с ответами

1. Модель производства, основанная на производственных функциях, построенная на основе обработки статистических данных, является …
• Дискриптивной

2. Среди критериев выбора оптимального решения при играх с природой наиболее осторожным (с минимальным риском) является критерий:
• Вальда

3. Согласно принципу оптимальности Беллмана, оптимальное управление на данном шаге зависит от оптимального управления на …
• Последующих шагах

4. На сколько этапов разбивается процесс решения задачи о распределении средств между четырьмя предприятиями:
• 4

5. На каком из этапов рационально использовать ЭВМ?
• Численное решение

6. Какой из этапов математического моделирования должен проводиться перед остальными?
• Постановка экономической проблемы и ее качественный анализ

7. Какую задачу нельзя решать методами динамического программирования:
• определения оптимального ассортимента продукции

8. Прибыль отрасли в балансовой модели Леонтьева образует матрицу
• Чистой продукции

9. Какому условию должна удовлетворять целевая функция при ее решении методами динамического программирования:
• Аддитивности

10. Модель межотраслевых связей является …
• Структурной
11. Величина коэффициента затрат базисной клетки равен 6, один из потенциалов равен 4. Тогда другой потенциал равен…
• 2

Источник

Тест с ответами: Динамическое программирование

В процессе динамического программирования раньше всех планируется
первый шаг
последний шаг +
как сказано в условии задачи
предпоследний шаг

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

Задача о загрузке рюкзака является задачей …. Программирования
нелинейного
параметрического
динамического +
линейного
целочисленного

В задачах теории игр говорят, что игра имеет седловую точку, если
нижняя цена игры меньше верхней
нижняя цена игры равна верхней +
нижняя цена игры больше верхней
нижняя цена игры не больше верхней
нижняя цена игры не меньше верхней

Игра называется игрой с нулевой суммой, если
выигрыш игрока А равен 0
выигрыш игрока В равен 0
сумма выигрышей игроков равна 0 +
выигрыш переходит от одного игрока другому
выигрыш приходит извне игры

В задачах теории игр та стратегия, которая соответствует нижней цене игры, называется
Максиминной +
минимаксной
оптимальной
нижней
лучшей

В задачах теории игр элементы платежной матрицы
положительные
целые
дробные +
любые
неотрицательные

В играх с «природой» критерий, учитывающий возможность как наихудшего, так и наилучшего для человека поведения природы, называется критерием
Вальда
Сэвиджа
Гурвица +
вероятностным критерием

Динамическое программирование – это метод оптимизации многошаговых задач в условиях
отсутствия обратной связи (последействия) и аддитивности целевой функции +
учета обратной связи (последействия) и аддитивности целевой функции
отсутствия обратной связи (последействия) и неаддитивности целевой функции

Метод динамического программирования применяется для решения
многошаговых задач +
задач, которые нельзя представить в виде последовательности отдельных шагов
только задач линейного программирования
задач макроэкономики

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

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

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

Критический путь сетевого графика – это
полный путь с максимальной продолжительностью +
полный путь с минимальной продолжительностью
расчетный полный путь со средней продолжительностью

Исходное событие сетевого графика – это
событие, не имеющее предшествующих работ и событий +
любое начальное событие
момент начала какого-либо процесса

Завершающее событие – это
событие не имеющее последующих работ и событий +
любое конечное событие
момент завершения какого-либо процесса

Начальное событие – это
момент завершения какого-либо процесса, начиная с которого происходит выполнение одной или нескольких работ +
исходное событие
момент завершения какого-либо процесса с определенным результатом

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

Система массового обслуживания включает следующие элементы
входящий поток требований или заявок на обслуживание
очередь
обслуживающее устройство
выходящий поток, обслуженных требований
входящий поток требований или заявок на обслуживание, очередь, обслуживающее устройство, выходящий поток, обслуженных требований +

Средняя доля пришедших заявок, обслуживаемых системой, называется
интенсивность потока обслуживаний
абсолютная пропускная способность
относительная пропускная способность +
интенсивность нагрузки

Поток, в котором одновременное появление двух или более заявок невозможно, называется
стационарным
ординарным +
простейшим
без последствий

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

Если значение коэффициента Q (относительная пропускная способность) равно 0,78, это значит, что
в единицу времени обслуживается 78 заявок
обслуживается 78% поступающих заявок +
78% заявок получают отказ в обслуживании
обслуживается 0,78% поступающих заявок

Среднее число заявок, обслуживаемых системой в единицу времени называется
интенсивность потока обслуживаний
абсолютная пропускная способность +
относительная пропускная способность
интенсивность нагрузки

Корреляция ценных бумаг на риск портфеля ценных бумаг
Влияет +
не влияет
однозначно сказать нельзя

Корреляция ценных бумаг на эффективность портфеля
влияет
не влияет +
однозначно сказать нельзя

Возникает необходимость в операции «short sale», если вектор долей рисковых ценных бумаг есть ценные бумаги
первого и второго вида
только первого вида
только третьего вида +

Проведение операции «short sale» с ценными бумагами означает
инвестор, формирующий портфель, обязуется через какое-то время поставить ценные бумаги 2-го вида (вместе с доходом, который они бы принесли их владельцу за это время). За это сейчас он получает их денежный эквивалент. На эти деньги он покупает ценные бумаги 1-го вида и получает по ним доход +
инвестор, формирующий портфель, обязуется через какое-то время поставить ценные бумаги 1-го вида (вместе с доходом, который они бы принесли их владельцу за это время). За это сейчас он получает их денежный эквивалент. На эти деньги он покупает ценные бумаги 2-го вида и получает по ним доход

Утверждение о том, что при полной прямой корреляции ценных бумаг (все коэффициенты корреляции равны 1) диверсификация портфеля не дает никакого эффекта – риск портфеля равен среднему арифметическому рисков составляющих его ценных бумаг и к нулю не стремится при росте числа видов ценных бумаг
Верно +
неверно
нельзя проверить, т. к. для утверждения о том верно оно или нет недостаточно информации

Задача управления запасами состоит в
определении такой стратегии пополнения и расхода запасов, при которой суммарные издержки на создание и хранение (функция затрат) являются минимальными +
обеспечении такого объема запасов, который позволяет осуществлять бесперебойный
производственный процесс
управлении дефицитом

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

Источник