Контрольная работа по "Методам оптимальных решений"

 

49. Какие возможности предоставляет среда MS Excel для решения задач линейного программирования?

 

Для решения подобных задач в MS EXCEL предназначена команда Поиск решения из меню Сервис.

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

 

50. В чем состоят градиентные методы решения задачи безусловной оптимизации?

 

Применяя градиентный метод, находят множество точек локальных максимумов (или минимумов), среди которых определяется максимум (или минимум) глобальный.

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

f(x(1)), то функция f будет возрастать, по крайней мере, в некоторой окрестности х(1).

 

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

 

Метод квадратичной штрафной функции, будучи примененным к двойственной задаче, дает возможность получить нормальное решение прямой задачи при конечном значении коэффициента штрафа.

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

 

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

 

Методы штрафных функций:

- «бесконечный» штраф

- логарифмический штраф

- штраф обратной функции

- штраф квадрата срезки

 

53. Сформулируйте задачу выбора решений в условиях неопределенности.

 

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

 

54. Назовите и сформулируйте критерии выбора решений в условиях неопределенности    (принцип гарантированного результата, критерий Гурвица, критерий Байеса-Лапласа, критерий Сэвиджа).

 

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

- критерий Вальда (критерий «максимина»)

- критерий «максимакса»

- критерий Гурвица (критерий «оптимизма-пессимизма» или «альфа-критерий»)

- критерий Сэвиджа (критерий потерь от «минимакса»)

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

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

3. Критерий Гурвица (критерий «оптимизма-пессимизма» или «альфа-критерий») позволяет руководствоваться при выборе рискового решения в условиях неопределенности некоторым средним результатом эффективности, находящимся в поле между значениями по критериям «максимакса» и «максимина» (поле между этими значениями связано посредством выпуклой линейной функции).

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

 

55. Как определяется множество допустимых гарантирующих программ? Что такое наилучшая гарантирующая программа?

 

Множество допустимых гарантирующих программ определяется следующим образом:

1. Строят прямые соответствующие  стратегиям второго (первого) игрока.

2. Определяют нижнюю (верхнюю) границу выигрыша

3. Находят две стратегии второго (первого) игрока, которым соответствуют две прямые, пересекающиеся в точке с минимальной (максимальной) ординатой.

Координаты точек принадлежащих нижней (верхней) огибающей, определяют минимальный гарантированный выигрыш первого (второго) игрока при применении им любых смешанных стратегий.

Наилучшая гарантирующая программа – стратегия, которая гарантирует максимальный выигрыш игрока в наихудших для него условиях

Она определяется как точка с максимальной (минимальной) ординатой на построенном множестве допустимых программ (нижней (верхней) границе выигрыша)

 

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

 

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

заданные величины cj, аij, bi, dj, Dj. Часто на практике величины cj, аij, bi могут быть случайными. Так, если bi - ресурс, то он зависит от ряда факторов. Аналогично, cj - цены - будут зависеть от спроса и предложения, аij - расходные коэффициенты - от уровня техники и технологии.

Задачи, в которых cj, аij, bi - случайные величины, относят к задачам стохастического программирования.

В задачах стохастического программирования случайный характер величин указывают различными способами:

реализацией случайных величин;

законом распределения случайных величин.

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

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

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

 

 

57. В чем состоит принятие решений на основе математического ожидания?

 

Процедура принятия решений строится на основе теории вероятностей и математической статистики.

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

                                                           (28)

 

58. Как учитывается склонность к риску?

 

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

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

Склонность к риску - это устойчивый эффект, особенно когда вероятность потерь значительна.

 

59. Сформулируйте постановку задачи многокритериальной оптимизации.

 

Задача многокритериальной оптимизации формулируется следующим образом:

  (29)

Где это k ( ) целевых функций. Векторы решений   относятся к не пустой области определения S.

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

 

60. Что такое множество достижимых критериальных векторов?

 

Числовое m-мерное пространство Em, координатами которого являются  yi=fi(X), называется критериальным пространством. Очевидно, что каждому Х можно поставить в соответствие точку в критериальном пространстве. Если же решение Х допустимо, то соответствующая точка в Em, определяемая вектором Y, является достижимой. Множество таких точек в критериальном пространстве называется множеством достижимости (достижимых векторов).

 

61. Дайте определение доминирования и оптимальности по Парето.

 

В случае доминирования при переходе от решения X2 к X1 ничего не будет проиграно ни по одному из частных критериев, но в отношении j – го частного критерия точно будет получен выигрыш. Говорят, что решение X1 лучше (предпочтительнее) решения X2.

Если решение не доминируемо никаким другим решением, то оно называется недоминируемым или оптимальным в смысле Парето.

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

Эффективное решение называется решением, оптимальным по Парето, или Парето-оптимальным решением.

 

62. Что такое эффективные решения и паретова граница.

 

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

для всякого ;

существует такое что .

Допустимое решение называется слабо эффективным (или оптимальным по Слейтеру), если не существует , такого, что строго, т.е. для всякого существует число , такое, что

. (30)

Паретова граница – это множество критериальных векторов, оптимальных по Парето.

 

63. Назовите основные подходы к построению методов поиска решений в задачах многокритериальной оптимизации.

 

- Интерактивность

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

- Эволюционные методы

Упоминания о применении генетических алгоритмов для решения задачи многокритериальной оптимизации относятся к концу 1960-х.

 

64. Приведите примеры многошаговых систем в экономике.

 

Динамическое моделирование – многошаговый процесс, каждый шаг соответствует поведению экономической системы в определенный временной период.

 

65. В чем состоят особенности динамических задач оптимизации?

 

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

 

66. Приведите примеры динамической задачи оптимизации.

 

Маршрутизация запросов в распределенном хранилище информации представляет собой задачу динамической оптимизации.

 

67. Что такое многошаговые динамические модели?

 

Это модели, в которых текущие управляющие решения "проявляются" как в период, относящийся непосредственно к моменту принятия решения, так и в последующие периоды.

 

68. Что такое непрерывные динамические модели?

 

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