Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

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

Содержание

Линейное программирование(Целевая функция и функция ограничений – линейные)
Решение задач оптимизации Линейное программирование(Целевая функция и функция ограничений – линейные) Линейное программирование(Графическое решение)45Т + 80С  MAX5Т + 20С ≤ 40010Т + Линейное программирование(Двойственная задача)Двойственная задача400W1 + 450W2  MIN20W1 + 15W2 ≥ 805W1 Линейное программирование(Еще одна задача)3,8M + 4,2N  MIN (4)0,1M + 0,25N ≥ Линейное программирование(Методы решения задач – на примере двумерных (с 2 переменными))Простой переборНахождение Линейное программирование(ТРАНСПОРТНАЯ ЗАДАЧА)Целевая функция:F = 2X11+ 5X12+ 4X13+ 5X14+ X21+ 2X22+ X23+ Целочисленное программирование(Дискретная задача. Решения – целые числа)7X + 3Y  MAXX ≥ Целочисленное программирование(ЗАДАЧА О РАНЦЕ)  Суть задачи сводится к  тому, чтобы Комбинаторное программированиеNP-трудные задачи – не полиномиальные (экспонента – 2n) –перебором  решить Целочисленное программирование(Некоторые методы решения задач)Метод приближения непрерывными задачами – сначала решается задача Теория графов и оптимизация(Основные понятия)ОРИЕНТИРОВАННЫЙ ГРАФНЕОРИЕНТИРОВАННЫЙ ГРАФВершинаДугаРеброПутьКонтурЦепьЦикл Теория графов и оптимизация(ЗАДАЧА О КРАТЧАЙШЕМ (наидлиннейшем) ПУТИ)НАЙТИ КРАТЧАЙШИЙ ПУТЬ В ГРАФЕНа Теория графов и оптимизация(ЗАДАЧА О НАЗНАЧЕНИИ)НАЙТИ ОПТИМАЛЬНОЕ НАЗНАЧЕНИЕ НА ДОЛЖНОСТИВ таблице – Теория графов и оптимизация(ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ)НАЙТИ ПОТОК MAX ВЕЛИЧИНЫАлгоритм (теорема) Форда-ФалкерсонаПусть (ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ. ОПРЕДЕЛЕНИЯ)Последовательным множеством называется подмножество дуг графа, образующих путь Теорема 1. Величина максимального потока в агрегируемой сети меньше или равна величине Теория графов и оптимизация(ЗАДАЧА КОММИВОЯЖЕРА)Найти кратчайший путь, соединяющий все города с возвратом Критерии принятия решений(МАТЕМАТИЧЕСКИЕ ПОСТАНОВКИ)3. Критерий максимакса (крайний оптимизм):4. Критерий Гурвица. Пусть для
Слайды презентации

Слайд 2 Линейное программирование
(Целевая функция и функция ограничений – линейные)

Линейное программирование(Целевая функция и функция ограничений – линейные)

Слайд 3 Линейное программирование
(Графическое решение)
45Т + 80С  MAX
5Т +

Линейное программирование(Графическое решение)45Т + 80С  MAX5Т + 20С ≤ 40010Т

20С ≤ 400
10Т + 15С ≤ 450
C > 0;


T > 0

Находим точку А:
5Т + 20С = 400 (1)
10Т + 15С = 450 (2)
Из (1) T = 80 - 4C
Тогда (2) принимает вид:
10(80 - 4C) + 15С = 450
25С = 350  С = 14
T = 80 – 4*14 = 24


Слайд 4 Линейное программирование
(Двойственная задача)
Двойственная задача
400W1 + 450W2  MIN
20W1

Линейное программирование(Двойственная задача)Двойственная задача400W1 + 450W2  MIN20W1 + 15W2 ≥

+ 15W2 ≥ 80
5W1 + 10W2 ≥ 45

W1 и

W2 – стоимость материала и работы (труда), оцененные по вкладу в целевую функцию

Слайд 5 Линейное программирование
(Еще одна задача)
3,8M + 4,2N  MIN

Линейное программирование(Еще одна задача)3,8M + 4,2N  MIN (4)0,1M + 0,25N

(4)
0,1M + 0,25N ≥ 1 (1)
1M + 0,25N ≥

5 (2)
110M + 120N ≥ 400 (3)
M > 0; N > 0

(1)

(2)

(3)

(4)


Слайд 6 Линейное программирование
(Методы решения задач – на примере двумерных

Линейное программирование(Методы решения задач – на примере двумерных (с 2 переменными))Простой

(с 2 переменными))
Простой перебор
Нахождение квадратного корня из 3 методом

перебора

Направленный перебор

Симплекс-метод


Слайд 7 Линейное программирование
(ТРАНСПОРТНАЯ ЗАДАЧА)
Целевая функция:
F = 2X11+ 5X12+ 4X13+

Линейное программирование(ТРАНСПОРТНАЯ ЗАДАЧА)Целевая функция:F = 2X11+ 5X12+ 4X13+ 5X14+ X21+ 2X22+

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 +

Целочисленное программирование(Дискретная задача. Решения – целые числа)7X + 3Y  MAXX

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 Целочисленное программирование
(ЗАДАЧА О РАНЦЕ)
Суть задачи сводится

Целочисленное программирование(ЗАДАЧА О РАНЦЕ) Суть задачи сводится к тому, чтобы поместить

к тому, чтобы поместить в ранец ограниченного объема набор

предметов максимальной полезности.
Каждый предмет имеет свой объем (ci) и полез- ность (ai).
Переменные xi равны 1 если i-й предмет входит в конечный набор, и xi = 0, если не входит.
Приведем математичес- кую постановку задачи:

Слайд 10 Комбинаторное программирование
NP-трудные задачи – не полиномиальные (экспонента –

Комбинаторное программированиеNP-трудные задачи – не полиномиальные (экспонента – 2n) –перебором решить

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) граница. Выбирается подмножество с максимальной верхней или минимальной нижней границей и процедура повторяется для него, пока не получим оптимальное решение или решение с необходимой точностью.
Эффективность метода ветвей и границ в существенной степени зависит от «качества» оценок. При плохих оценках это фактически полный перебор, при достижимой нижней оценке – это получение оптимального решения за один проход по дереву ветвлений.

Достижимое решение

Задача об очередности обра- ботки 3 деталей на станках


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

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

Слайд 13 Теория графов и оптимизация
(ЗАДАЧА О КРАТЧАЙШЕМ (наидлиннейшем) ПУТИ)
НАЙТИ

Теория графов и оптимизация(ЗАДАЧА О КРАТЧАЙШЕМ (наидлиннейшем) ПУТИ)НАЙТИ КРАТЧАЙШИЙ ПУТЬ В

КРАТЧАЙШИЙ ПУТЬ В ГРАФЕ
На ребрах указаны их длины.
В квадратных

скобках рядом с вершинами – MIN длина пути в эту вершину.
Путь MIN длины ищется методом обратного хода.
У задачи о кратчайшем пути есть массу интерпретаций: - календарное планир., - последовательность работ, - собственно поиск кратчайшего пути - и многие другие.

Слайд 14 Теория графов и оптимизация
(ЗАДАЧА О НАЗНАЧЕНИИ)
НАЙТИ ОПТИМАЛЬНОЕ НАЗНАЧЕНИЕ

Теория графов и оптимизация(ЗАДАЧА О НАЗНАЧЕНИИ)НАЙТИ ОПТИМАЛЬНОЕ НАЗНАЧЕНИЕ НА ДОЛЖНОСТИВ таблице

НА ДОЛЖНОСТИ
В таблице – «зарплата», которую запрашивает претендент.
Эта задача может

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

Двудольный граф

РЕШЕНИЕ: П1 – Д1 Min затр. – 4
П2 – Д3 Возр. на 2
П3 – Д2 Стало – 6


Слайд 15 Теория графов и оптимизация
(ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ)
НАЙТИ ПОТОК

Теория графов и оптимизация(ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ)НАЙТИ ПОТОК MAX ВЕЛИЧИНЫАлгоритм (теорема)

MAX ВЕЛИЧИНЫ
Алгоритм (теорема) Форда-Фалкерсона
Пусть пропускные способности всех дуг равны

1.
Пропускаем произвольный поток.
Помечаем вершины, начиная с входа «0»
если можно увеличить поток в к.-л. вершину, помечаем ее (поток увеличивается на 1).
Если в помеченную вершину входит поток из непомеченной, его можно вычесть (уменьшить).
Если в конце помечена вершина-выход, поток м.б. увеличен, если нет – поток максимален.

Слайд 16 (ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ. ОПРЕДЕЛЕНИЯ)
Последовательным множеством называется подмножество

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

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

начальной, имеет степень захода 1, и любая вершина, кроме конечной имеет степень исхода 1.

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

Пример

максимальная величина потока


Слайд 17 Теорема 1. Величина максимального потока в агрегируемой сети

Теорема 1. Величина максимального потока в агрегируемой сети меньше или равна

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

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

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

MAX поток = MIN разрез


Слайд 18 Теория графов и оптимизация
(ЗАДАЧА КОММИВОЯЖЕРА)
Найти кратчайший путь, соединяющий

Теория графов и оптимизация(ЗАДАЧА КОММИВОЯЖЕРА)Найти кратчайший путь, соединяющий все города с

все города с возвратом в исходный
или
Найти КОНТУР МИНИМАЛЬНОЙ ДЛИНЫ
Задача

– NP-трудная. Для ее решения могут применяются:
Эвристические методы (напр. Всегда идти в ближайший из не пройденных городов)
Метод локальной оптимизации
Метод ветвей и границ

  • Имя файла: reshenie-zadach-optimizatsii.pptx
  • Количество просмотров: 103
  • Количество скачиваний: 0
- Предыдущая Дания