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

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

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

W1 и

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

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

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

(1)

(2)

(3)

(4)

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

перебора

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

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

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

Существует программная реализация решения подобных задач

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 станков типа В

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

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

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 млн. лет)

– сначала решается задача линейного программирования без учета целочисленности,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

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