Методы Оптимальных Решений Презентация

Методы Оптимальных Решений Презентация.rar
Закачек 3819
Средняя скорость 5280 Kb/s

Методы Оптимальных Решений Презентация

Презентация была опубликована 2 года назад пользователемВладимир Скрябин

Похожие презентации

Презентация на тему: » 1 Методы оптимальных решений к.ф.-м.н. ЮрченкоА.А.» — Транскрипт:

1 1 Методы оптимальных решений к.ф.-м.н. ЮрченкоА.А.

2 Структура курса Длительность 24 ак. часа 6 лекций (каждую неделю, 12 ак. ч.) 6 семинаров (через неделю 12 ак. ч.) В конце курса экзамен 2

3 Содержание курса 3 Раздел 1. Введение: Системный анализ и исследование операций 1. Системы и этапы системного анализа. 2. Задачи исследования операций. Раздел 2. Линейное программирование 3. Общая постановка задачи. 4. Построение математических моделей простейших экономических задач. 5. Графический метод решения задач линейного программирования. 6. Алгоритмы симплекс-метода. 7. Двойственность в линейном программировании. Раздел 3. Нелинейное программирование 8. Общая постановка задачи. 9. Графический метод решения задач нелинейного программирования. 10. Метод множителей Лагранжа.

4 Литература по курсу Банди, Б. Основы линейного программирования / Б. Банди – Пер. с англ. под ред. В. А. Волынского. М., Радио и связь, – 176 с. Семушин, И. В. Практикум по методам оптимизации Компьютерный курс: учеб. пособие для вузов / И. В. Семушин. – 3-е изд., перераб. и доп. – Ульяновск: УлГТУ, – 146 с. Черноруцкий И.Г. Методы оптимизации и принятия решений. – СПб.: Лань, Лунгу К.Н. Линейное программирование. Руководство к решению задач- М-ФИЗМАТЛИТ, с. Красс М.С., Чупрынов Б.П. Математика для экономического бакалавриата: Учебник. – М.: ИНФРА-М, – 472 С. 4

5 5 Методы оптимальных решений Лекция 1 Введение. Системный анализ. Основные понятия.

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

7 Выбор и альтернатива Для решения проблемы из множества вариантов — альтернатив осуществляется выбор одной или нескольких предпочтительных альтернатив Альтернатива – один из возможных вариантов ( путей, средств ) решения проблемы Выбор – операция, входящая во всякую целенаправленную деятельность и состоящую в целевом сужении множества альтернатив ( если возможно до одной ) 7

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

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

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

11 История Системного анализа СА возник после второй мировой войны как развитие идей исследования операций для анализа создаваемых систем вооружений с позиции их эффективности и затрат ресурсов. 11

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

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

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

15 15 Методы оптимальных решений Линейное программирование

16 16 Линейное программирование (ЛП) — это наука о методах исследования и отыскания наибольших и наименьших значений (экстремум) линейной функции, на неизвестные которой наложены линейные ограничения ЗАДАЧА Необходимо найти набор действительных чисел X=(x1,x2,…,xn), доставляющий экстремум линейной целевой функции Z

17 л 17 Целевая функция Линейные ограничения

18 Стандартная форма Первая ( симметрическая ) стандартная форма задачи линейного программирования имеет вид Первая ( симметрическая ) стандартная форма задачи линейного программирования имеет вид

19 Стандартная форма Вторая ( симметрическая ) стандартная форма задачи линейного программирования имеет вид Вторая ( симметрическая ) стандартная форма задачи линейного программирования имеет вид

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

21 Правила приведения 1. Превращение max в min и наоборот. Если целевая функция в задаче линейного программирования задана в виде то, умножая её на (- 1), приведем её к виду так как смена знака приводит к смене min на max. Аналогично можно заменить max на min.,

22 Правила приведения 2. Смена знака неравенства. Если ограничение задано в виде то, умножая на (-1), получим: Аналогично, неравенство вида больше либо равно можно превратить в неравенство вида меньше либо равно.

23 Правила приведения 3. Превращение равенства в систему неравенств.

24 Правила приведения 4. Канонической задачи в симметричную форму.

Современные методы принятия оптимальных решений. Р.Г.Стронгин, проф., ВМК В.П.Гергель, проф., ВМК В.А.Гришагин, доц., ВМК С.Ю.Городецкий, доц., ВМК М.В.Маркина, доц., мех.-мат.

Слайд 33 из презентации «Математические модели, методы и программные системы современных компьютерных технологий»

Размеры: 720 х 540 пикселей, формат: .jpg. Чтобы бесплатно скачать слайд для использования на уроке, щёлкните на изображении правой кнопкой мышки и нажмите «Сохранить изображение как. ». Скачать всю презентацию «Математические модели, методы и программные системы современных компьютерных технологий.ppt» можно в zip-архиве размером 504 КБ.

Похожие презентации

«Метод интервалов» — Определение. Метод интервалов. Математика. Решение. Общий метод интервалов . Умножив неравенство на -1 и разложив квадратный трёхчлен на множители, получим неравенство равносильное данному. Затем, двигаясь справа налево, при переходе через очередной нуль, сменить знак на противоположный. Умножив неравенство на -1 и разложив квадратные трёхчлены на множители, получим неравенство равносильное данному.

«Основные методы селекции» — 4. Возможно клонирование животных, получение генетических копий от одного организма. 2. Межпородное скрещивание используют для создания новой породы. 4. Использование эффекта гетерозиса. 3.Естественный отбор в селекции играет определяющую роль. Основные методы селекции растений. С помощью микробиологической промышленности получают антибиотики.

«Метод учебного проекта» — Презентация творческих работ с привлечением общественности (родителей, старшеклассников, учителей, педагогов…). Работу над проектом в равной мере осуществляют все члены группы. Длительность выполнения 2-3 недели в режиме урочно — внеурочных занятий. Типы проектов: Все материалы проекта созданы с соблюдением авторских прав.

«Метод проектов в начальных классах» — Проект -. Формирование ученических компетенций учащихся. Задачи: Виды проектов: Цель: Банк проектов: Актуальность. Метод проектов в начальной школе. Этапы работы:

«Метод проектов на уроках математики» — Комната. План выполнения работы. Критерии оценки проекта: Полнота раскрытия темы. Сроки выполнения Презентация проекта происходит на следующем уроке. Плюсы проектной деятельности Каждый ученик участвует в учебном процессе. Организационный момент. Использование полученных знаний в практике. Сроки выполнения На выполнение проекта даётся 3- 5 дней.

«Формы и методы обучения» — По признаку активности детей. Словесные методы (методы изложения). Проблема выбора методов обучения. М.О. зависят: От общих и конкретных целей обучения. Требования к методам обучения. Всякая классификация имеет определенное основание. Понятие методов, приемов обучения. Необходимость систематически изучать, использовать в своей работе инновационные методы.

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

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

6.2. ПРИМЕРЫ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

Рассмотрим сначала простые практические задачи, которые сводятся к задачам ЦЛП, затем обратимся к более сложным. Для удобства задачи, в которых все переменные должны быть целочисленными, называются полностью целочисленными, а задачи, в которых лишь некоторые переменные должны принимать целочисленные значения, — частично-целочисленными.

Пример 6.2-1 . (Распределение капиталовложений)

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

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

Задача сводится к решению типа «да — нет» относительно каждого проекта. Определим двоичные переменные х j :

Задача ЦЛП будет записана следующим образом. Максимизировать

z = 20 х 1 + 40 х 2 + 20 х 3 + 15 х 4 + 30 х 5 при ограничениях

5 x 1 + 4 х 2 + 3 х 3 + 7 х 4 + 8 х 5 25, х 1 + 7 х 2 + 9 х 3 + 4 х 4 + 6 x 5 25, 8 x 1 + 10 х 2 + 2 х 3 + x 4 + 10 x 5 25, х 1 , х 2 , х 3 , х 4 , x 5 = 0 или 1.

Оптимальным целочисленным решением является х 1 = х 2 = х 3 = х 4 = 1, х 5 = 0 с z = 95 (млн. долл.). Это решение означает, что необходимо выбрать для финансирования все проекты, кроме пятого.

Интересно сравнить решение данной задачи ЦЛП с решением «обычной» задачи ЛП с теми же ограничениями, но без условия целочисленности переменных. Задача линейного программирования получается в результате замены условия х j = 0 или 1 на ограничение 0 х j 1 для всех

j . Эта задача имеет решение х 1 = 0.5789, х 2 = х 3 = х 4 = 1, х 5 = 0.7368 и z =

108.68 (млн. долл.). Такое решение с точки зрения целочисленной задачи лишено смысла, так как две переменные принимают дробное значение. Можно было бы попытаться округлить полученный результат, что привело бы к х 1 = х 5 = 1. Полученное при этом решение является

недопустимым, так как нарушаются ограничения задачи. Более существенным в этой ситуации является то, что округление применять нельзя , так как х j представляет решение типа «да — нет», для которого

дробные значения лишены смысла.

8.3.МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

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

Шаг 1. «Ослабление» пространства допустимых решений задачи целочисленного линейного программирования путем замены любой двоичной переменной y непрерывным ограничением 0 у 1 и отбрасывания требования целочисленности для всех остальных переменных. В результате получается обычная задача линейного программирования.

Шаг 2. Решение задачи линейного программирования и определение ее оптимального решения.

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

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

Метод ветвей и границ.

Метод отсекающих плоскостей.

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

Метод ветвей и границ

Основы этого метода объясним на численном примере.

Рассмотрим следующую задачу целочисленного линейного программирования.

х 1 + х 2 5, 10 x 1 + 6 х 2 45, х 1 , х 2 0 и целые.

На рис. 6.6 пространство допустимых решений задачи целочисленного линейного программирования представлено точками. Соответствующая начальная задача линейного программирования (обозначим ее ЛП0)

получается путем отбрасывания условий целочисленности. Ее оптимальным решением будет х 1 = 3.75, х 2 = 1.25 и z = 23.75.

Так как оптимальное решение задачи ЛП0 не удовлетворяет условия целочисленности, метод ветвей и границ изменяет пространство решений задачи линейного программирования так, что, в конечном счете, получается оптимальное решение задачи целочисленного линейного программирования. Для этого сначала выбирается одна из целочисленных переменных, значение которой в оптимальном решении задачи ЛП0 не является целочисленным. Например, выбирая х 1 (= 3.75),


Статьи по теме