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

План занятия

1. Общие положения вероятностного планирования.

2. Априорная информация о возмущениях.

3. Схема управления.

4. Оптимизация в среднем.

5. Вероятностно-гарантирующий подход к планированию.

Задача Между тремя предприятиями распределить 120 единиц ограниченного ресурса. Значения получаемой предприятиями прибыли в зависимости от выделенной суммы Х приведены в таблице. Найти оптимальный план распределения методом обратной прогонки.

Контрольные вопросы

1. Вероятностно-гарантирующие решения дискретных задач с конечным множеством возмущений и планов.

2. Универсальная формулировка задачи о вероятностно-гарантирующем планировании.

3. Жесткие и нежесткие ограничения на управление.

4. Возможный диапазон наилучших вероятностно-гарантирующих оценок.

5. Достаточные условия предельной тождественности.

6. Примеры отсутствия предельной тождественности. Характер сходимости вероятностного решения к гарантирующему.

Тема 6 Вероятностное планирование

План занятия

1. Стратегии игры. Матричные игры.

2. Верхняя и нижняя цена игры.

3. Седловая точка.

4. Оптимальная стратегия.

5. Игры с природой.

Задача Между тремя предприятиями распределить 120 единиц ограниченного ресурса. Значения получаемой предприятиями прибыли в зависимости от выделенной суммы Х приведены в таблице. Найти оптимальный план распределения методом обратной прогонки.

Контрольные вопросы

1. Критерий Лапласа

2. Принцип максимакса

3. Критерий максимаксного риска.

4. Кооперативные игры.

5. Характеристическая функция и её свойства

Тема 7 Матричные игры и игровое управление

Задача Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице.

Контрольные вопросы

1. Критерий Лапласа

2. Принцип максимакса

3. Критерий максимаксного риска.

4. Кооперативные игры.

5. Характеристическая функция и её свойства

Тема 8 Плоские графы и сетевое планирование

План занятия

1. Способы задания графа.

2. Изоморфизмы графов.

3. Связность графа.

4. Плоский граф.

5. Рёбра и грани графа.

6. Эйлеров путь, цикл и эйлеров граф.

7. Гамильтонов путь и гамильтоновы графы.

Задача Лизинговой компании необходимо сделать выбор объектов предполагаемых лизинговых сделок с определением оптимальных объемов финансирования на приобретение этих объектов в размерах кратных 100 млн. руб. Для инвестирования на эти цели компания располагает капиталом в объеме 700 млн. руб. В таблице 4 приводится среднегодовая прибыль компаний, ожидаемая от лизингополучателей при предоставлении им того или иного объекта на сумму от 0 до 700 млн. руб.

Контрольные вопросы

1. Ориентированные графы. Орграфы.

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

3. Основные понятия— работа, события, пути.

4. Критический путь.

5. Стандартные обозначения.

6. Двудольные графы и сети Петри.

7. Виды сетей Петри.

Тема 9 Оптимизация в микроэкономических моделях

План занятия

1. Случайная последовательность событий.

2. Поток однородных событий.

3. Простейший поток Пуассона.

4. Мгновенная плотность потока.

Задача Между тремя предприятиями распределить 120 единиц ограниченного ресурса. Значения получаемой предприятиями прибыли в зависимости от выделенной суммы Х приведены в таблице. Найти оптимальный план распределения методом прямой прогонки.

Контрольные вопросы

1. Марковские процессы.

2. Матрица переходных вероятностей

3. Задачи анализа замкнутых и разомкнутых цепей массового обслуживания.

4. Нахождение стационарных вероятностей.

Тема 10 Оптимизация в макроэкономических моделях

План занятия

1. Функции полезности.

2. Кривые безразличия.

3. Функции спроса и предложения.

4. Кривые «доход-потребление».

5. Кривые «цены-потребление».

6. Коэффициенты эластичности.

Задача Для модернизации предприятий совет директоров инвестирует средства в объеме 25 млн. руб. с дискретностью 5 млн. руб. Прирост выпуска продукции зависит от выделенной суммы, его значения представлены предприятиями и содержатся в таблице. Найти распределение инвестиций между предприятиями, обеспечивающее фирме максимальный прирост выпуска продукции, причем на одно предприятие можно осуществить только одну инвестицию.

Контрольные вопросы

1. Материальные балансы.

2. Функции выпуска продукции.

3. Производственные функции затрат ресурсов

4. Линейные, мультипликативно-степенные производственные функции.

5. Равновесные траектории.

 

7. Методические указания для индивидуальной и самостоятельной работы

 

7.1 Вопросы для собеседования

1. Вероятностно-гарантирующие решения дискретных задач с конечным множеством возмущений и планов.

2. Универсальная формулировка задачи о вероятностно-гарантирующем планировании.

3. Жесткие и нежесткие ограничения на управление.

4. Возможный диапазон наилучших вероятностно-гарантирующих оценок.

5. Достаточные условия предельной тождественности.

6. Примеры отсутствия предельной тождественности.

7. Характер сходимости вероятностного решения к гарантирующему

8. Критерий Лапласа

9. Принцип максимакса

10. Критерий максимаксного риска.

11. Кооперативные игры.

12. Характеристическая функция и её свойства

 

7.2 Индивидуальные домашние задания

1. Метод искусственного базиса
Решить методом искусственного базиса.

2. Задача о кормовой смеси. Пример решения

3. Задача оптимального производства продукции

4. Пример решения задачи симплексным методом в Excel

5. Пример решения симлекс-методом
Решить следующую задачу ЛП в неканонической форме симплекс-методом:
f(x) = x1 – x2 – 3x3 → min

6. М-метод
Решить задачу М-методом.

7. Симплекс-метод. Поиск наибольшего значения

8. Пример нахождения максимума функции симплексным методом

9. Пример нахождения минимума функции симплексным методом

10. Решение прямой задачи линейного программирования симплексным методом

11. Решение задачи симплексным методом путем преобразования симплекс–таблиц

12. Подробное решение задачи симплекс-методом

13. Математическая модель задачи
Предприятие выпускает 3 вида микросхем: M1, M2, M3. Для производства используются одни и те же ресурсы: кремний (S), алюминий (Al), золото (Au), пластик (P), которые берутся в разных количествах. Расход ресурсов на единицу продукции каждого вида приведен в таблице 1. Максимальные суточные запасы ресурсов приведены в таблице 2. Изучение рынка сбыта показало, что разница суточного спроса между отдельно взятыми видами микросхем (Продукт1 – Продукт2) никогда не превышает величин, приведенных в таблице 3. Цены за микросхему каждого вида приведены в таблице 4.

14. Линейное программирование в Excel

15. Примеры задач линейного программирования

16. Пример решения модифицированным симплекс-методом
Решить задачу модифицированным симплексным методом.

17. Задача линейного программирования модифицированным симплексным методом

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

19. Пример решения симплекс-методом в столбцовой форме записи

20. Симплекс-метод в строчечной форме записи. Пример решения

21. Двухэтапный симплекс-метод

22. Двухфазный симплекс-метод

23. Сборник решений по симплекс-методу

 

6.3 Расчетно-графические задания

1. Между тремя предприятиями распределить 120 единиц ограниченного ресурса. Значения получаемой предприятиями прибыли в зависимости от выделенной суммы Х приведены в таблице. Найти оптимальный план распределения методом прямой прогонки.

2. Для модернизации предприятий совет директоров инвестирует средства в объеме 25 млн. руб. с дискретностью 5 млн. руб. Прирост выпуска продукции зависит от выделенной суммы, его значения представлены предприятиями и содержатся в таблице. Найти распределение инвестиций между предприятиями, обеспечивающее фирме максимальный прирост выпуска продукции, причем на одно предприятие можно осуществить только одну инвестицию.

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

4. Найти оптимальное распределение средств между тремя предприятиями при условии, что прибыль f(u), k=1,2,3 полученная от k - того предприятия, является функцией от вложенных в него средство u.

7.4 Тестовые задания

 

1. В методах группы ELECTRE обязательно введение …

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

3. Метод ELECTRE есть метод … удовлетворительных решений на основе оценки предпочтений экспертов по … критериев.

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

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

6. Критерий оптимальности по Парето служит ….

7. В методах оценки многокритериальных альтернатив, если один из критериев принимается за …, для остальных критериев назначают пороговые величины. Изменяя пороговые значения можно получить ….

8. Матричный вид функции полезности используется для представления ….

9. Многокритериальная задача линейного программирования ставится по итогам построения вектора наилучших значений критериев ….

10. Различия в методах оценки многокритериальных альтернатив и методе аналитической иерархии состоит в ….

 

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

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

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

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

15. Если решение принимается в условиях риска, то решение обосновывается критерием ожидаемого значения, в соответствии с которым … с точки зрения ожидаемой прибыли или минимизации затрат.

16. Нормативный и вероятностный способ учета риска различаются тем, что первый основан на …, накладываемых на возможные варианты решения, а во втором находится … возможных альтернатив.

17. Поскольку определение полезности является …, оно зависит от нашего отношения к риску. Поэтому часто при оценке риска применяется модель функции полезности, которая занимает место реальных денег.

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

19. Если лицо, принимающее решение, не расположено к риску (осторожен), то результирующая функция полезности является …, соединяющей точки минимальной и максимальной полезности.

20. Если лицо, принимающее решение, настроено на риск, то результирующая функция полезности является …, соединяющей точки минимальной и максимальной полезности.

21. Допустим, вы — студент университета и имеете сильное желание присутствовать на следующем баскетбольном матче. Проблема в том, что входной билет стоит 10 д.е., а у вас есть лишь 5 д.е. Вы можете рискнуть 5 д.е. в игре в покер с шансами 50 на 50 удвоить свою сумму или совсем ее проиграть. Полезность игры равна …. Если функция полезности прямая, то игра в покер ….

22. 102. Допустим, вы — студент университета и имеете сильное желание присутствовать на следующем баскетбольном матче. Проблема в том, что входной билет стоит 10 д.е., а у вас есть лишь 5 д.е. Вы можете рискнуть 5 д.е. в игре в покер с шансами 50 на 50 удвоить свою сумму или совсем ее проиграть. Полезность игры равна …. Если функция полезности выпуклая, то игра в покер ….

23. Допустим, вы — студент университета и имеете сильное желание присутствовать на следующем баскетбольном матче. Проблема в том, что входной билет стоит 10 д.е., а у вас есть лишь 5 д.е. Вы можете рискнуть 5 д.е. в игре в покер с шансами 50 на 50 удвоить свою сумму или совсем ее проиграть. Полезность игры равна …. Если функция полезности вогнутая, то игра в покер ….

24. Процедура выявления отношения к риску ЛПР заключается в последовательном определении ожидаемого значения полезности в диалоговом режиме на основе ….

25. В ситуациях неопределенности необходимо при построении модели принятия решений сохранять определенную степень риска, ….

26. Из данных о погоде прошлых лет следует, что имеется 70%-ная вероятность, что в сезон дождей будет идти дождь. В шесть часов вечера синоптики предсказали с 85%-ной вероятностью, что завтра будет дождь. Оценка риска дождя завтра в данной ситуации равна ….

27. Из данных о погоде прошлых лет следует, что имеется 60%-ная вероятность, что в сезон дождей будет идти дождь. В шесть часов вечера синоптики предсказали с 15%-ной вероятностью, что завтра будет дождь. Оценка риска дождя завтра в данной ситуации равна ….

28. Задача «Выпускники военной академии получают распределение на места службы. Каждый офицер имеет определенные пожелания относительно места службы. В свою очередь, в зависимости от места службы определенные требования предъявляются к офицеру. Желательно заполнить все вакантные места. Необходимо найти наилучшие (с точки зрения обеих сторон) решения» есть ….

29. Многокритериальная задача о назначениях …

30. Многокритериальная задача о назначениях относится к ….

 

 

Тематика рефератов

 

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. Метод простой интеграции, метод Ньютона-Канторовича, метод наискорейшего спуска и метод случайного поиска.

 

 

Задания для контрольной работы

 

1. Функции полезности.

2. Кривые безразличия.

3. Функции спроса и предложения.

4. Кривые «доход-потребление».

5. Кривые «цены-потребление».

6. Коэффициенты эластичности.

7. Материальные балансы.

8. Функции выпуска продукции.

9. Производственные функции затрат ресурсов

10. Линейные, мультипликативно-степенные производственные функции.

11. Равновесные траектории.

12. Модели общего экономического равновесия.

13. Статическая и динамическая модели межотраслевого баланса.

14. Матрица межотраслевого баланса в модели Леонтьева как пример замкнутой статической модели межотраслевого баланса.

15. Динамическая модель расширяющейся экономики Неймана.

16. Оптимизация производственного процесса внутри планового периода.

Вопросы для коллоквиумов

\

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. Решение задач на условный экстремум методом непосредственного исключения функционально зависимых переменных при помощи дополнительных условий.

30. Необходимые и достаточные условия существования внутренних точек экстремума.

31. Общая задача оптимизации и линейное программирование

32. Способы задания графа.

33. Изоморфизмы графов.

34. Связность графа.

35. Плоский граф.

36. Рёбра и грани графа.

37. Модели общего экономического равновесия.

38. Статическая и динамическая модели межотраслевого баланса.

 

 

подписано в печать 2013 г. Формат 60ч84 1/16

Бумага офисная. Печать лазерная. Усл.-печ. л.

Тираж экз. Заказ

_____________________________________________________________

Отпечатано в типографии ГОУ ВПО НГГТИ,

357100, г. Невинномысск, Бульвар Мира, 17