Презентация на тему "Решение задач оптимизации"

Содержание

• 
  Слайд 1

  Решение задач оптимизации

• 
  Слайд 2
  
• 
  Слайд 3
  
• 
  Слайд 4
  
• 
  Слайд 5
  
• 
  Слайд 6

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

  (Методы решения задач – на примере двумерных (с 2 переменными)) Простой перебор  Нахождение квадратного корня из 3 методом перебора Направленный перебор Симплекс-метод

• 
  Слайд 7
  

  (ТРАНСПОРТНАЯ ЗАДАЧА) Целевая функция: F = 2X11+ 5X12+ 4X13+ 5X14+ X21+ 2X22+ X23+ 4X24+ 3X31+ X32+ 5X33+ 2X34 MIN Ограничения: X11+ X12+ X13+ X14 = 60 X21+ X22+ X23+ X24 = 80 X31+ X32+ X33+ X34 = 60 X11+ X21+ X31 = 50 X12+ X22+ X32 = 40 X13+ X23+ X33 = 70 X12+ X22+ X32 = 40 Существует программная реализация решения подобных задач

• 
  Слайд 8

  Целочисленное программирование

  (Дискретная задача. Решения – целые числа) 7X + 3Y MAX X ≥ 0; Y ≥ 0; X,Y - целые 8X + 4Y≤ 38 5X+ 2Y≤ 20 ПОСТАНОВКА ЗАДАЧИ Возможно решение МЕТОДОМ ПЕРЕБОРА Из ограничений X ≤ 4. 1. X = 4  Y = 0  C = 28 (выбирается min Y, при котором выполняются оба ограничения). 2. X = 3  Y = 2 C = 27. 3. X = 2  Y ≤ 5  C = 29. 4. X = 1  Y ≤7 C = 28. 5. X = 0  Y ≤9 C = 27. Для обеспечения MAX производительности покупаем 2 станка типа Aи 5 станков типа В

• 
  Слайд 9
  

  (ЗАДАЧА О РАНЦЕ) Предм. 6 0 1 2 3 4 3 2 2 4 4 4 5 5 5 [3] [3] [3] [3] [2] [2] [2] [5] [6] [7] [9] [9] [5] [5] [6] [7] Вес 4 Суть задачи сводится к тому, чтобы поместить в ранец ограниченного объема набор предметов максимальной полезности. Каждый предмет имеетсвой объем (ci) и полез-ность (ai). Переменные xi равны 1 если i-й предмет входит в конечный набор,и xi = 0, если не входит. Приведем математичес-кую постановку задачи:

• 
  Слайд 10

  Комбинаторное программирование

  NP-трудные задачи – не полиномиальные (экспонента – 2n) –перебором решить невозможно. Примеры NP-трудных задач: Задача о ранце. – последовательностьиз n элементов, каждый из которых может принимать 2 значения (xi = [0;1])) Число комбинаций 2n Задача коммивояжера– перестановка из nэлементов =(i1, i2, … ,in) (n!). Подбор команды численностью m человек из nпретендентов. (Число сочетаний). Примеры комбинаций Перестановка (Pn) из n элементов (например чисел 1,2,…,n) – любой упорядоч- енный набор из элементов. Размещение из n элементов по n – n!. Размещение(Ank) из n элементов по k– упорядоченный набор из k различных элементов некоторого n-элементного множества – n!/(n-k)!. Сочетание из n по k (Cnk) – набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми (отличие от размещений) – n!/(n-k)!/k!. Последовательность – набор из nэлементов, каждый из которых может принимать одно из m значений – mn. 20! = 2,432902 × 1018 (Проверяя по 100 комбинаций в 1 сек. мы потратим около 770 млн. лет)

• 
  Слайд 11

  Целочисленное программирование

  (Некоторые методы решения задач) Метод приближения непрерывными задачами – сначала решается задача линейного программирования без учета целочисленности, а затем в окрестности оптимального решения ищутся целочисленные точки. Метод ветвей и границ (один из наиболее известных видов метода направленного перебора) – множество возможных решений делится на непересекающиеся подмножества, для каждого вычисляется верхняя (задача на MAX) или нижняя (задача на MIN) граница. Выбирается подмножество с максимальной верхней или минимальной нижней границей и процедура повторяется для него, пока не получим оптимальное решение или решение с необходимой точностью. Эффективность метода ветвей и границ в существенной степени зависит от «качества» оценок. При плохих оценках это фактически полный перебор, при достижимой нижней оценке – это получение оптимального решения за один проход по дереву ветвлений. Q 22 20 22 (1) (3) (не 1) (не 3) 20 Достижимое решение Задача об очередности обра-ботки 3 деталей на станках

• 
  Слайд 12

  Теория графов и оптимизация

  (Основные понятия) ОРИЕНТИРОВАННЫЙ ГРАФ НЕОРИЕНТИРОВАННЫЙ ГРАФ Вершина Дуга Ребро Путь Контур Цепь Цикл

• 
  Слайд 13
  

  (ЗАДАЧА О КРАТЧАЙШЕМ (наидлиннейшем) ПУТИ) НАЙТИ КРАТЧАЙШИЙ ПУТЬ В ГРАФЕ На ребрах указаны их длины. В квадратных скобках рядом с вершинами – MIN длина пути в эту вершину. Путь MIN длины ищется методом обратного хода. У задачи о кратчайшем пути есть массу интерпретаций: - календарное планир., - последовательность работ, - собственно поиск кратчайшего пути - и многие другие.

• 
  Слайд 14
  

  (ЗАДАЧА О НАЗНАЧЕНИИ) НАЙТИ ОПТИМАЛЬНОЕ НАЗНАЧЕНИЕ НА ДОЛЖНОСТИ В таблице – «зарплата», которуюзапрашивает претендент. Эта задача может решаться с помощью алгоритма поиска кратчайшего пути, рассмотренного выше. Двудольный граф РЕШЕНИЕ: П1 – Д1 Min затр. – 4 П2 – Д3 Возр. на 2 П3 – Д2 Стало – 6

• 
  Слайд 15
  

  (ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ) НАЙТИ ПОТОК MAX ВЕЛИЧИНЫ Алгоритм (теорема) Форда-Фалкерсона Пусть пропускные способности всех дуг равны 1. Пропускаем произвольный поток. Помечаем вершины, начиная с входа «0» если можно увеличить поток в к.-л. вершину, помечаем ее (поток увеличивается на 1). Если в помеченную вершину входит поток из непомеченной, его можно вычесть (уменьшить). Если в конце помечена вершина-выход,поток м.б. увеличен, если нет – поток максимален.

• 
  Слайд 16
  

  16 (ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ. ОПРЕДЕЛЕНИЯ) Последовательныммножествомназываетсяподмножестводугграфа, образующихпутьтакой, чтолюбаявершина, кроме начальной, имеетстепеньзахода 1, и любаявершина, кромеконечнойимеетстепеньисхода 1. Параллельныммножествомдугназываетсяподмножестводугсети, у которыхначальная и конечнаявершинысовпадают. Сетьагрегируемая, еслипутемагрегированияпоследовательныхи (или) параллельныхмножествдугееможносвести к однойдуге. Пример максимальная величина потока

• 
  Слайд 17
  

  17 Теорема 1. Величинамаксимальногопотока в агрегируемойсетименьшеилиравнавеличинемаксимальногопотока в исходнойсети. Доказательствоследуетизочевидногофакта, чтолюбомупотоку в агрегируемойсетиоднозначносоответствуетнекоторыйпоток в исходнойсети. Теорема 2 (двойственности). Существуетразбиениепропускныхспособностейдуг, исходящихизразделенныхвершин, такоечтовеличинамаксимальногопотока в агрегируемойсетиравнавеличинемаксимальногопотока в исходнойсети(ОДЗ) MAX поток = MIN разрез

• 
  Слайд 18

  Теория графов и оптимизация

  (ЗАДАЧА КОММИВОЯЖЕРА) Найти кратчайший путь, соединяющий все города с возвратом в исходный или Найти КОНТУР МИНИМАЛЬНОЙ ДЛИНЫ Задача – NP-трудная.Для ее решения могут применяются: Эвристические методы (напр.Всегда идти в ближайший из не пройденных городов) Метод локальной оптимизации Метод ветвей и границ

• 
  Слайд 19

  Критерии принятия решений

  (МАТЕМАТИЧЕСКИЕ ПОСТАНОВКИ) 3. Критерий максимакса (крайний оптимизм): 4. Критерий Гурвица. Пусть для i-ой альтернативы При заданном  (степень оптимизма ЛПР) выбирается . При  = 1 данный критерий переходит в критерий Вальда. 5. Критерий Лапласа. (Аналог вероятностной модели при равных вероятностях.) Для каждой альтернативы Аiопределяется показатель Далее выбирается . Максиминныйкритерий Вальда(наибольшей осторожности) 2. Критерий минимаксного сожаления(критерий Сэвиджа).