Теория принятия решений

Теория принятия решений НГУ Факультет информационных технологий 3 курс, 2 семестр Лектор: Кочетов Юрий Андреевич http://www.math.nsc.ru/LBRT/k5/or.html

Теория принятия решений Исследование операций — теория математических моделей и методов принятия решений. 1. Наличие некоторого процесса 2. Наличие управляющих воздействий 3. Наличие цели, ради которой проводится операция 4. Выбор наилучшего (оптимального) управления, при котором достигается цель Операция — система действий, объединенная единым замыслом и направленная на достижение определенной цели. Основная задача теории оптимальных решений состоит в представлении обоснованных количественных данных и рекомендаций для принятия оптимальных решений. Лекция 1. Исследование операций. Динамическое программирование

Реальная задача

Уяснение и формулировка задачи

Корректировка модели

Схема исследования Построение математической модели

Оптимальное решение

Математическая модель

Поиск оптимальных решений

Выдача рекомендаций

Лекция 1. Исследование операций. Динамическое программирование

Математическая модель Математическая модель — объективная схематизация основных аспектов решаемой задачи или ее описание в математических терминах. Математическая модель описывает исследуемую систему и позволяет выразить ее эффективность в виде целевой функции W = f(X,Y), где X = (x1,…, xn) — управляемые переменные, Y = (y1,…, ym) — неуправляемые переменные (исходные данные). Связь между переменными X и исходными данными Y выражается с помощью ограничений

ϕ (X, Y) ≤ 0.

Лекция 1. Исследование операций. Динамическое программирование

Типовые модели принятия решений 1. Транспортные задачи 2. Задачи маршрутизации 3. Задачи теории расписаний 4. Задачи размещения 5. Задачи раскроя и упаковки 6. Матричные игры

Лекция 1. Исследование операций. Динамическое программирование

Транспортные задачи

Потребители

Транспортные затраты

Предприятия Минимизировать затраты на перевозку продукции Лекция 1. Исследование операций. Динамическое программирование

Задачи маршрутизации

Найти маршрут минимальной длины

Лекция 1. Исследование операций. Динамическое программирование

Задачи теории расписаний

Графики движения поездов, рабочие бригады, ремонт составов Лекция 1. Исследование операций. Динамическое программирование

Задачи размещения

Системы сотовой связи, филиалы банков, пожарные бригады, скорая помощь Лекция 1. Исследование операций. Динамическое программирование

Задачи раскроя и упаковки

Раскрой пиломатериала, листового железа, станки с ЧПУ Лекция 1. Исследование операций. Динамическое программирование

Матричные игры

Pij вероятность поражения

Лекция 1. Исследование операций. Динамическое программирование

Распределительная задача Имеем n — число предприятий; Y — количество единиц некоторого ресурса; fk(x) — количество продукции, которое будет произведено на k-м предприятии, если в него будет вложено x единиц ресурса (монотонно неубывающая функция). Требуется: максимизировать объем продукции f1(x1) +…+ fn(xn) → max

(1)

x1 +…+ xn ≤ Y

(2)

xi ≥ 0, целые, i = 1,…n.

(3)

Лекция 1. Исследование операций. Динамическое программирование

Идея динамического программирования (ДП) Метод ДП (Р. Беллман, В.С. Михалевич, Н.З. Шор ) можно трактовать как алгоритмическую версию рассуждений по индукции. Пусть sk(y), 1 ≤ k ≤ n, 0 ≤ y ≤ Y, — оптимальное значение целевой функции задачи (1) – (3), где n заменено на k, Y заменено на y. Требуется найти sn(Y) и набор переменных, на котором достигается это значение.

Лекция 1. Исследование операций. Динамическое программирование

ТЕОРЕМА 1. Пусть f1, … , fn — монотонно неубывающие функции. Тогда справедливы следующие рекуррентные соотношения: s1(y) = f1(y), 0 ≤ y ≤ Y;

(4)

sk(y) = max {sk−1(y − x) + fk(x) | 0 ≤ x ≤ y}, 2 ≤ k ≤ n, 0 ≤ y ≤ Y,

(5)

Доказательство: Соотношение (4) очевидно. По определению sk(y) ≥ max {sk−1(y − x) + fk(x) | 0 ≤ x ≤ y}. Пусть теперь ( x1∗ ,..., xk∗ ) — такой вектор, что x1∗ + ... + xk∗ ≤ y и sk ( y ) = f1 ( x1∗ ) + ... + f k ( xk∗ ) .

Поскольку sk −1 ( y − xk∗ ) ≥ f1 ( x1∗ ) + ... + f k −1 ( xk∗ −1 ), имеем

sk ( y ) = f1 ( x1∗ ) + ... + f k ( xk∗ ) ≤ sk −1 ( y − xk∗ ) + f k ( xk∗ ) . Лекция 1. Исследование операций. Динамическое программирование

Алгоритм ДП вычисляет множество Sk = {sk(y) | 0 ≤ y ≤ Y}, k =1,…,n с помощью соотношений (4) и (5), где на каждом шаге оптимизируется ровно одна переменная. Процесс вычисления S1,…,Sn называется прямым ходом алгоритма. Число операций ≈ Y 2n Память ≈ Y n .

y

S1(y) S2(y) … Sn(y)

0 1 2 Y

Sn(Y)

При обратном ходе алгоритма вычисляются значения ( xn∗ ,..., x1∗ ) , с учетом того, что уже известны Sk(y). Например, xn∗ определяется из уравнения sn (Y ) = f n ( xn∗ ) + s n−1 (Y − x n∗ ) и так далее. Число операций ≈ Y n. Память ≈ Y n. Лекция 1. Исследование операций. Динамическое программирование

Характеристики алгоритмов Для оценки качества алгоритмов будем использовать два параметра: TA — трудоемкость (число элементарных операций алгоритма A); ПА — требуемый объем памяти. Элементарная операция — одна из арифметических операций: сложение, вычитание, умножение, деление или логическая операция сравнение двух чисел.

Нас будет интересовать зависимость параметров алгоритма от длины записи исходных данных задачи с точностью до порядка величин. Пример: При Т = 3/2 n2 , будем писать T = O(n2) или T ≈ n2.

Лекция 1. Исследование операций. Динамическое программирование

Полиномиальные алгоритмы Определение. Алгоритм A называют полиномиальным, если его трудоемкость TA ограничена полиномом от длины записи исходных данных, то есть существует константа c > 0 и натуральное число k такие, что TA ≤ c Lk, где L — длина записи исходных данных. n

Пример: Пусть fi (xi) = ai xi, тогда L = ∑ log ai + log Y , i =1

но TДП = O(Y2n), то есть алгоритм ДП не является полиномиальным.

Лекция 1. Исследование операций. Динамическое программирование

Обобщим задачу (1)–(3): f1(x1) +…+ fn(xn) → max

(1′)

h1(x1) +…+ hn(xn) ≤ Y

(2′)

ai ≥ xi ≥ 0, целые, i = 1,…n.

(3′)

Если hi(x) — целочисленные монотонно неубывающие функции, то вместо (4)–(5) можно использовать следующие рекуррентные соотношения: s1(y) = f1(x* ), где x* = max{x ≤ a1 | h1(x) ≤ y}, 0 ≤ y ≤ Y; sk(y) =

max

{ x ≤ ak |hk ( x ) ≤ y}

{ fk(x) + sk−1(y − hk(x))}, 2 ≤ k ≤ n, 0 ≤ y ≤ Y.

(4′) (5′)

Упражнение 1. Доказать справедливость соотношений (4′)–(5′). Лекция 1. Исследование операций. Динамическое программирование

Обратная задача — поиск наименьших затрат на получение заданного количества продукции:

h1(x1) +…+ hn(xn) → min

(6)

f1(x1) +…+ fn(xn) ≥ D

(7)

ai ≥ xi ≥ 0, целые, i = 1,…n.

(8)

Если fk(x) — целочисленные монотонно неубывающие функции, то для решения задачи (6)–(8) можно использовать идеи динамического программирования.

Лекция 1. Исследование операций. Динамическое программирование

Пусть fi−1 (d ) = min{0 ≤ x ≤ ai | fi ( x) ≥ d }. Для 1≤ k ≤ n, 0 ≤ d ≤ D обозначим через tk(d) — оптимальное решение задачи (6)–(8), в которой n заменено на k, а D заменено на d. Требуется найти tn(D). Рекуррентные соотношения если f1 (a1 ) < d , ⎧∞, t1 (d ) = ⎨ −1 h ( f ⎩ 1 1 (d )), если f1 (a1 ) ≥ d ,

0 ≤ d ≤ D,

tk(d) = min{tk–1(d – fk(x)) + hk(x)| 0 ≤ x ≤ ak, x ≤ f k−1 (d ) }, k ≥ 2, 0 ≤ d ≤ D.

(9)

(10)

Упражнение 2. Доказать справедливость соотношений (9)–(10). Лекция 1. Исследование операций. Динамическое программирование

ТЕОРЕМА 2: Предположим, что D — наибольшее число, для которого оптимальное значение целевой функции задачи (6)–(8) не превосходит Y. Тогда оптимальное значение целевой функции задачи (1′)–(3′) равно D. Доказательство: Пусть D удовлетворяет условию теоремы

и ( x1∗ ,..., xn∗ ) — соответствующее решение задачи (6)–(8). Значит f1 ( x1∗ ) + ... + f n ( xn∗ ) ≥ D и h1 ( x1∗ ) + ... + hn ( xn∗ ) ≤ Y .

Следовательно,

D не превосходит оптимального решения D1 задачи

(1′)–(3′). Если бы

D1 было больше D, то решение задачи (6)–(8), в

которой D заменено на D1, тоже не превышало бы Y, что противоречит максимальности D.

Лекция 1. Исследование операций. Динамическое программирование

Задачи о рюкзаке Модель размещения капитала Дано P1, P2, … , PN — проекты; T — горизонт планирования (длина наиболее продолжительного проекта); stk — доход от проекта Pk к концу года t; ytk — инвестиции в проект Pk в начале года t;

s0k = yT+1k = 0;

r — коэффициент дисконтирования затрат T

bk = ∑ ( stk − yt +1, k ) /(1 + r )t — суммарная прибыль от проекта Pk; t =0

C = (c1, …, cT) — доступный капитал для развития проектов Ak = (a1k, …, aTk) — вектор затрат на реализацию проекта Pk (целые); Если доход нельзя реинвестировать, то atk = ytk, иначе atk = ykt – st–1k . Лекция 2. Задачи о рюкзаке

-1-

Найти подмножество проектов, которые можно реализовать на капитал C и которые в сумме дают максимальную прибыль, то есть N

max ∑ bk xk k =1

при ограничениях N

∑ atk xk ≤ ct ,

t = 1,…, T

k =1

xk ∈ {0, 1}, k = 1,…, N Замечание 1. При T = 1 получаем линейную распределительную задачу с 0-1 переменными — задачу о рюкзаке. Замечание 2. Без ограничения общности можно считать, что

N

∑ atk ≥ ct ,

k =1

t = 1,…, T, (можно получить задачу о рюкзаке даже при T >1). Лекция 2. Задачи о рюкзаке

-2-

Алгоритм динамического программирования Обозначим через fk(Y) максимальную прибыль от первых k проектов при доступном капитале Y = (y1, … , yT). Тогда f0(Y) = 0 fk+1(Y) = max [fk(Y), bk+1 + fk(Y – Ak+1)] , k = 0, …, N – 1, 0 ≤ Y ≤ C, где fk(Y – Ak+1) = – ∞, если вектор Y – Ak+1 имеет хотя бы одну отрицательную компоненту. ТДП = O(N ⋅ c1 ⋅ … ⋅ cT); ПДП = O(N ⋅ c1 ⋅ … ⋅ cT). Полный перебор — 2N вариантов.

Лекция 2. Задачи о рюкзаке

-3-

Верхняя оценка Релаксация линейного программирования N

max ∑ bk xk

(1)

k =1

при ограничениях N

∑ atk xk ≤ ct ,

t = 1,…, T

(2)

0 ≤ xk ≤ 1, k = 1, …, N.

(3)

k =1

Теорема 2.1. Существует оптимальное решение xLP с не более чем min (T, N) дробными компонентами

Лекция 2. Задачи о рюкзаке

-4-

Доказательство. Пусть T < N (иначе утверждение очевидно). Приведем задачу к канонической форме. Получим 2N + T переменных и N + T ограничений: N

min ∑ − bk xk ,

(4)

k =1

N

∑ atk xk + λt = ct ,

t = 1,…, T,

(5)

k =1

(6) xj + µj = 1, j = 1,…, N, (7) xj ≥ 0, µj ≥ 0, λt ≥ 0. Любое базисное допустимое решение имеет не менее N нулей. Предположим, что T из них соответствуют переменным λt. Тогда N – T нулей останется для xj и µj. Если для некоторого j имеем µj = 0, то xj = 1 — целое. Если xj = 0 — тоже целое. Таким образом, получаем N – T целых компонент для xj, то есть T дробных. Лекция 2. Задачи о рюкзаке

-5-

Округление дробного решения Пусть xLP — оптимальное решение задачи (4)–(7). Для γ ∈ [0,1] положим

⎧⎪1, если x LP j =1 xj = ⎨ LP ⎪⎩0, если x j < γ Для оставшихся дробных значений переменных сформируем подзадачу вида (4)–(7), пересчитав правые части ограничений. Найдем оптимальное решение xLP для этой подзадачи и положим ⎧1, если x LP j = 1, ⎪ x j = ⎨0, если x LP j = 0, ⎪0 для j = arg min{x LP | 0 < x LP < 1}. j j ⎩ На этом шаге значение как минимум одной переменной будет зафиксировано. Повторяя процедуру, найдем допустимое решение исходной задачи. Лекция 2. Задачи о рюкзаке

-6-

Задача об отправке грузов I = {1,…, n} — авиалайнеры, J = {1,…, m} — контейнеры, Pij — доход от доставки авиалайнером i контейнера j, wj — вес контейнера j, ci — вместимость авиалайнера i, xij = 1, если отправить контейнер j авиалайнером i 0 иначе

{

Модель

max ∑

∑ pij xij

i∈I j∈J

при ограничениях:

∑ xij ≤ 1,

j∈ J,

i∈I

∑ w j xij ≤ ci ,

i∈ I,

j∈J

xij ∈{0,1}, i∈I, j∈J. Лекция 2. Задачи о рюкзаке

-7-

Дальняя экспедиция Морское судно грузоподъемностью С отправляется в экспедицию. J = {1,…, m} — типы грузов (трактора, электрогенераторы, радиостанции,…) Nj — варианты грузов для j∈J, wij — вес груза j по варианту i∈Nj pij — полезность груза xij = 1, если берем i - й вариант груза j 0 иначе

{

Модель

max ∑

∑ pij xij

j∈ ji∈N j

при ограничениях:

∑ xij = 1,

j∈ J,

i∈N j

∑ ∑ wij xij ≤ C ,

j∈J i∈N j

xij ∈{0,1}, i∈Nj, j∈J. Лекция 2. Задачи о рюкзаке

-8-

Гильотинный раскрой материала Дан лист размера L × W и n типов прямоугольников lj × wj, j=1,…,n pj > 0 — доход от прямоугольника j, повороты запрещены, разрезы параллельно осям координат от кромки до кромки. Двухстадийная обработка: сначала режем лист параллельно оси y, затем параллельно оси x. Найти раскрой листа с максимальным доходом. y L

W

x y1

y2

yk Лекция 2. Задачи о рюкзаке

-9-

Пусть

k — число параллельных полос k = ⎣ L / lmin ⎦ yi — ширина полосы i, 1 ≤ i ≤ k, xij — число j-х прямоугольников в полосе i, 1, если xij > 0 ⎧ ′ xij = ⎨ ⎩0 иначе

mj = ⎣W / wj⎦ — максимально возможное число j-х прямоугольников в полосе.

Лекция 2. Задачи о рюкзаке

-10-

Модель: k

n

max ∑ ∑ p j xij i =1 j =1

при ограничениях n

∑ w j xij ≤ W ,

i = 1,..., k ,

j =1

k

∑ yi ≤ L,

i =1

l j xij′ ≤ yi , i = 1,...k , j = 1,..., n, m j xij′ ≥ xij , i = 1,...k , j = 1,..., n, xij′ ∈{0,1}, xij ∈{0,..., m j }, yi ∈{1,..., L}.

Лекция 2. Задачи о рюкзаке

-11-

Классическая задача о рюкзаке Найти:

max

∑ pjxj

j∈J

при ограничениях

∑ w j x j ≤ C,

j∈J

Все коэффициенты pj, wj, C — целые числа. xj∈{0,1}, j∈J. Определение Алгоритм А называется приближенным алгоритмом с гарантированной абсолютной точностью K, если для любого примера I алгоритм находит значение zA(I) с отклонением от оптимума z*(I) не более K, то есть z*(I) – zA(I) ≤ K, для всех I. Обозначим через TA(n, C) трудоемкость алгоритма A для задачи с n предметами и вместимостью рюкзака C. Лекция 2. Задачи о рюкзаке

-12-

Теорема 2.2. Пусть A — приближенный алгоритм с гарантированной абсолютной точностью K и трудоемкостью TA(n, C). Тогда алгоритм A для любого примера позволяет найти точное решение задачи о рюкзаке с той же трудоемкостью. Доказательство. Пример I задается числами p1,…, pn, w1,…, wn, C. Построим новый пример I′, положив С′ = С, p′j = ( K + 1) p j , w′j = w j , j∈J. Оба примера

имею одно и то же множество допустимых решений. Так как целевая функция для I′ в (K + 1) раз больше, чем для I, то оптимальные наборы x∗j совпадают. z*(I′) – zA(I′) ≤ K, но K z*(I′) = (K + 1) z*(I), то есть z*(I) – zA(I) ≤ K +1

Для примера I′ имеем

zA(I′) = (K + 1) zA(I) и

Так как pj — целые, то z*(I) – zA(I) ≤ 0, то есть z*(I) = zA(I), что и требовалось доказать. Лекция 2. Задачи о рюкзаке

-13-

Жадные алгоритмы Упорядочим предметы по плотности pj / wj и будем считать, что p1 / w1 ≥ p2 / w2 ≥ ... ≥ pn / wn

Жадный алгоритм 1. w := 0 ; zG := 0; 2. for j := 1 to n do if w + w j ≤ C then xj:=1; w := w + w j ; z G := z G + p j ; else xj:=0; TG = O(n log n + n), ПG = O(n) Упражнение Если последнюю строку заменить на else { for k:=j to n do xk:=0; break }, то такое решение можно найти с T= O( n). Лекция 2. Задачи о рюкзаке

-14-

Релаксация линейного программирования LP–релаксация

z LP = max

∑ pjxj

j∈J

∑ w j x j ≤ C,

j∈J

0 ≤ xj ≤ 1, j∈J. Так как область допустимых решений увеличилась, то zLP ≥ z*. Пусть предметы упорядочены по плотностям и для некоторого s ∈ J верно: s −1

∑wj ≤ C j =1

Положим

и

s

∑wj > C. j =1

⎧1, j = 1,..., s − 1, s −1 ⎪⎪ 1 x LP (C − ∑ w j ). j =⎨ ⎪ ws j =1 ⎪⎩0, j = s + 1,..., | J | . Лекция 2. Задачи о рюкзаке

-15-

Теорема 2.3. Решение xLP является оптимальным решением LP–релаксации и s −1

s −1 p z LP = ∑ p j + s (C − ∑ w j ). ws j =1 j =1 Доказательство. Будем считать, что предметы с одинаковой плотностью слиты в один и p p1 p2 > > ... > n . w1 w2 wn

Пусть x = ( x1,..., xn ) — оптимальное решение, не равное xLP. Так как

∑ w j x j = C,

то найдутся как минимум два номера k > s и i ≤ s такие, что

j∈J

xk > 0 и xi < xiLP . Положим d = min{wk xk , wi ( xiLP − xi )} > 0 . Построим новое решение x′, которое будет отличаться от x только в координатах i, k: d d . xi′ = xi + , xk′ = xk − wi wk Лекция 2. Задачи о рюкзаке

-16-

Решение x′ является допустимым, так как x′j ≥ 0 по выбору d и

∑ w j x′j =

j∈J

wi d wk d ∑ w j x j + w − w = C. i k j∈J

Кроме того

∑ p j x′j =

j∈J

pi pk ∑ p j x j + d(w − w ) > ∑ p j x j i k j∈J j∈J

pi pk так как , что противоречит оптимальности x . > wi wk

Лекция 2. Задачи о рюкзаке

-17-

Свойства LP-релаксации LP

Верхняя оценка U

LP

= ⎣ z ⎦ , pˆ =

Свойство 1. pˆ ≤ z ∗ ≤ U LP ≤ z LP ≤

s −1

∑ pj j =1 s

G p ≤ p + p ≤ z + ps . ˆ ∑ j s j =1

Свойство 2. z ∗ − z G ≤ z ∗ − pˆ ≤ pmax ,

где

pmax = max p j . j∈J

Свойство 3. z LP ≤ 2 z ∗ и для любого ε >0 найдется пример задачи о рюкзаке такой, что z LP ≥ 2 z ∗ − ε . Доказательство. 1. Так как z ∗ ≥

s −1

* * LP и z ≥ p т о 2 z ≥ z . p s ∑ j

j =1

2. Рассмотрим пример n = 2, C = 2M и wj = M +1, pj = 1, j =1,2. Тогда z* = 1, 2 M и с ростом M получаем zLP / z* → 2. но z LP = M +1

Лекция 2. Задачи о рюкзаке

-18-

Определение Алгоритм A называется приближенным алгоритмом с гарантированной относительной точностью K, если для любого примера I A

алгоритм находит значение z (I) такое, что

Если ε = 1 – K, то

z∗ ( I ) − z A ( I ) ∗

z (I )

z A (I ) ∗

z (I )

≥ K для всех I.

≤ ε – относительная погрешность алгоритма.

Пример. Положим n = 2, C = M и p1 = 2, w1 = 1, p2 = M, w2 = M. Тогда жадный алгоритм получит x1 = 1, x2 = 0, zA = 2,

но x1∗ = 0, x2∗ = 1, z ∗ = M , то есть для жадного алгоритма zA z

∗

→ 0 при M → ∞.

Лекция 2. Задачи о рюкзаке

-19-

Модифицированный жадный алгоритм Используем предыдущий жадный алгоритм, получаем zG . Затем полагаем zMG = max {zG, max{pj | j∈J}}. Теорема 2.4. Модифицированный жадный алгоритм AMG имеет гарантиро-

ванную относительную точность K = ½ . Доказательство. Из свойства 2 для LP-релаксации имеем

z* ≤ zG + pmax ≤ zMG + zMG. Пример.

Положим

n = 3, C = 2M , p1 = 2, p2 = M, p3 = M, w1 = 1, w2 = M, w2 = M.

Получаем z* = 2M, zMG = 2 +M, то есть оценку K = ½ нельзя улучшить. Лекция 2. Задачи о рюкзаке

-20-

Алгоритм G

¾

Сокращаем погрешность за счет трудоемкости Алгоритм G

¾

1. zA := max {pj | j∈J}; 2. Для всех пар (i, k) ∈ J × J if wi + wk ≤ C then • применяем алгоритм AMG к задаче с множеством {j | pj ≤ min{pi, pk}}\{i, k} и вместимостью рюкзака C – wi – wk • if pi + pk + zMG > zA then zA := pi + pk + zMG.

Лекция 2. Задачи о рюкзаке

-21-

Теорема 2.5. Алгоритм G

¾

имеет гарантированную относительную точ-

ность K = ¾. Доказательство. Если оптимальное решение x∗j содержит только один пред-

мет, то zA = z* и утверждение верно. Предположим, что в оптимальном решении не меньше двух предметов. Выберем среди них два (i∗ , k∗ ) с наибольшими pj. На некотором шаге алгоритм G ¾ выберет эту пару (i∗ , k∗ ) и применит алгоритм AMG к задаче с множеством предметов { j | p j ≤ min{ pi∗ , pk∗ }} \ {i∗ , k∗} и вместимостью рюкзака C − wi∗ − wk∗ . Обозначим

через

z s∗

оптимальное

решение

этой

подзадачи.

Тогда

z ∗ = pi∗ + pk∗ + z s∗ . Алгоритм AMG для этой подзадачи найдет значение z sMG .

Так как

zA — лучшее из решений, просмотренных алгоритмом G ¾, то

z A ≥ pi∗ + pk∗ + z sMG . По теореме 2.4 имеем z sMG ≥ 12 z s∗ . Лекция 2. Задачи о рюкзаке

-22-

Рассмотрим два случая. Случай 1. pi∗ + pk∗ ≥ 12 z ∗.

Тогда z A ≥ pi∗ + pk∗ + z sMG ≥ pi∗ + pk∗ + 12 z s∗ =

= pi∗ + pk∗ + 12 ( z ∗ − pi∗ − pk∗ ) = 12 ( z ∗ + pi∗ + pk∗ ) ≥ 34 z ∗.

Случай 2. pi∗ + pk∗ < 12 z ∗.

Тогда min( pi∗ , pk∗ ) < 14 z ∗. По определению z s∗

содержит предметы с p j ≤ 14 z ∗ , значит z s∗ ≤ z sLP ≤ z sMG + 14 z ∗ . Теперь z* = pi∗ + pk∗ + z s∗ ≤ pi∗ + pk∗ + z sMG + 14 z ∗ ≤ z A + 14 z ∗. Пример. Положим

n = 5, C = 4M , p1 = 2, p2 = p3 = p4 = p5 = M, w1 = 1, w2 = w3 = w4 = w5 = M.

Очевидно, что z* = 4M, zA = 3M + 2, то есть оценку K= ¾ нельзя улучшить. Лекция 2. Задачи о рюкзаке

-23-

Silvano Martello, Paolo Toth

Knapsack Problem Algorithms and Computer Implementations University of Bologna John Wiley & Sons 1990 296 р

http://www.math.nsc.ru/LBRT/k5/knapsack_problem.pdf

Лекция 2. Задачи о рюкзаке

-24-

Аппроксимационные схемы Определение Алгоритм A называется ε-аппроксимационной схемой, если для любого ε∈]0,1[ и любых исходных данных I задачи верно zA(I) ≥ (1-ε) z*(I) Другими словами, алгоритм A является (1-ε)-приближенным алгоритмом для всех ε∈]0,1[. Алгоритм Hε 1. l := min{⎡ε1 ⎤ − 2, n}, zA := 0 2. Для всех подмножеств L⊂ J, |L| ≤ l–1 if ( ∑ w j ≤ c) and ( ∑ p j > z A ) then z A := j∈L

j∈L

∑ pj

j∈L

Лекция 3. Задачи о рюкзаке (продолжение)

-1-

3. Для всех подмножеств L⊂ J, |L| = l if ( ∑ w j ≤ c) then j∈L

• Применить алгоритм AMG к задаче с множеством предметов {j | pj ≤ min {pi, i∈L}}\ L и вместимостью рюкзака c −

∑wj

j∈L

• if

MG A A p + z > z then z := ∑ j

j∈L

MG p + z . ∑ j

j∈L

Теорема Алгоритм Hε является ε-аппроксимационной схемой.

Лекция 3. Задачи о рюкзаке (продолжение)

-2-

Доказательство. Если оптимальное решение z* содержит не более l предметов, то zA=z* и утверждение верно. Пусть в оптимальном решении более чем l предметов. Выберем в нем подмножество L* из l предметов с наибольшими весами pj. Рассмотрим подзадачу S с множеством предметов {j | pj ≤ min {pi, i∈L*}}\ L*и вместимостью рюкзака c − ∑ w j . Оптимальное решение этой подзадачи j∈L∗

обозначим через z S∗ . Тогда z ∗ = z S∗ +

∑

j∈L∗

p j . Приближенное решение,

полученное алгоритмом AMG, обозначим через z SMG . По определению z A ≥

MG MG 1 ∗ p + z и кроме того z ≥ 2 zS . ∑∗ j S S

j∈L

Лекция 3. Задачи о рюкзаке (продолжение)

-3-

Рассмотрим два случая: 1. ∑ p j ≥ l +l 2 z ∗ . Тогда z A ≥ ∗

j∈L

∑

j∈L∗

2.

∑

j∈L∗

p j + 12 ( z ∗ −

∑

j∈L∗

∑

∗

j∈L

p j + z SMG ≥

p j ) = 12 ( z ∗ +

∑

j∈L∗

∑

j∈L∗

p j + 12 z S∗ =

p j ) ≥ 12 ( z ∗ + l +l 2 z ∗ ) =

p j < l +l 2 z ∗ . Тогда в L* найдется предмет с

l +1 ∗ z l+2

p j < l +12 z ∗ . По

определению в подзадаче S все предметы имеют вес не более Применяя свойство 2 для LP-релаксаций, получаем z ∗ = ∑ p j + z S∗ ≤ ∑ p j + z SMG + l +12 z ∗ ≤ z A + l +12 z ∗ . j∈L∗

1 z∗. l +2

j∈L∗

Итак, в обоих случаях получаем z A ≥ ll++12 z ∗ . Величина ll++12 растет с ростом l l + 1 1ε − 1 ≥ = 1− ε. и 1 l+2 ε

T = O(n nl) = O(nl+1). П = O(n).

Лекция 3. Задачи о рюкзаке (продолжение)

-4-

⎡1 ⎤ ⎡1 ⎤ Пример Положим n = ⎢ ⎥ + 1, c = ⎢ ⎥ M и ⎢ε ⎥ ⎢ε ⎥ p1 =2, p2 = p3 =…= pn = M,

w1 = 1, w2 = w3 =…= wn = M. Оптимум z* = M(l + 2), l = n – 3, zA = (l +1)M + 2 и

zA / z* → (l+1) / (l+2) при M → ∞. Определение ε-аппроксимационная схема A называется полиномиальной, если ее трудоемкость полиномиально зависит от размерности задачи.

TH = O(nl+1) = O(n1/ε –1) — полиномиальная зависимость при заданном ε. Если ε = 0.1, то TH = O(n9), то есть алгоритм Hε является полиномиальной εаппроксимационной схемой для задачи о рюкзаке.

ε-аппроксимационная схема A называется полностью Определение полиномиальной, если ее трудоемкость полиномиально зависит от размерности задачи и величины 1/ε. Лекция 3. Задачи о рюкзаке (продолжение)

-5-

Теорема Для задачи о рюкзаке существует полностью полиномиальная ε-аппроксимационная схема. Доказательство Для примера I = {p1,…, pn, w1,…, wn,c} построим новый p пример I , в котором c = c, w j = w j , p j = ⎢ Kj ⎥ для некоторой константы ⎢⎣ ⎥⎦ K > 0, которую определим позже. Для примера I применим алгоритм ДП и найдем оптимальный набор предметов X . Скорее всего он будет отличаться от оптимального набора X* для примера I. Оценим разность

между полученным значением zA и оптимальным z*: pj pj ⎥ ⎢ z = ∑ p j ≥ ∑ K K ≥ ∑ K ( K − 1) = ∑ ( p j − K ) = z ∗ − | X ∗ | K . ⎢ ⎥ j∈ X ⎣ ⎦ j∈ X ∗ j∈ X j∈ X ∗ Второе неравенство в этой цепочке следует из оптимальности X для I . A

Лекция 3. Задачи о рюкзаке (продолжение)

-6-

Мы хотим получить Следовательно, K ≤

z∗ − z A z

∗

≤

| X∗ | K z

∗

≤ ε.

ε ⋅ z∗

* * . Так как n ≥ | X | и z ≥ pmax , то ∗ |X |

ε ⋅ z∗

ε ⋅ z∗

ε ⋅ pmax ≥ ≥ n n | X∗ | и, полагая K = ε ⋅ pmax n , получим нужное значение для параметра K. Трудоемкость алгоритма определяется трудоемкостью ДП. Если вместо исходной задачи решать обратную к ней, то T = O(Un), где U — верхняя оценка на оптимальное значение целевой функции z ∗ =

∑ p j.

j∈X p

Очевидно, что z ∗ ≤ npmax , но pmax ≤ Kmax = εn , то есть z ∗ ≤ n 2 / ε . Полагая U = n2/ε , получаем T = O(n 3 ⋅ ε1 ) , П = O (Un) = O(n 3 ⋅ ε1 ) . Лекция 3. Задачи о рюкзаке (продолжение)

-7-

Задача о ближайшем соседе Дано: функция f (x, y) ≥ 0 — затраты на обслуживание отрезка дороги от x до y,

0 ≤ x ≤ y ≤ M,

x, y — целочисленные точки,

n — число отрезков. Найти: оптимальное разбиение сегмента [0,M] на n отрезков. Математическая модель: n

min ∑ f ( xk −1, xk ) k =1

0 = x0 ≤ … ≤ xn = M

Лекция 3. Задача о ближайшем соседе

-1-

Алгоритм динамического программирования Sk(y) — минимальные затраты на обслуживание k отрезков для сегмента [0, y].

Рекуррентные соотношения: S1(y) = f (0,y), y = 1,…, M S k ( y ) = min {S k −1 ( x) + f ( x, y )}, y = 1,…, M, k = 2,…, n. 1≤ x ≤ y

T = O(nM 2) П = O(nM)

Лекция 3. Задача о ближайшем соседе

-2-

Оптимизация числа отрезков Для каждого n = 1,…, M найти Sn(M) и выбрать наименьшее значение T = O(M 3), П = O(M 2). Модифицированный вариант ~ S ( y ) — минимальные затраты на обслуживание сегмента [0, y].

Рекуррентные соотношения: ~ S (0) = 0, ~ ~ S ( y ) = min {S ( x) + f ( x, y )}, y = 1,…, M. 0≤ x≤ y −1

T = O(M 2), П = O(M). Лекция 3. Задача о ближайшем соседе

-3-

Замена оборудования Дано:

g — начальная стоимость оборудования,

ϕ (t) — относительная остаточная стоимость на год t ψ (t) — эксплуатационные затраты за все года от 0 до t. S(t) = g(1 – ϕ (t)) + ψ (t) — суммарные затраты за все года от 0 до t.

σ (t) = S(t)/t — удельные затраты Критерий оптимизации

σ (t ∗ ) = min σ (t ) t >0

Будем менять оборудование через каждые t* лет.

Лекция 3. Задача о ближайшем соседе

-4-

Случай 1. S(t) — вогнутая растущая функция. Пусть ϕ (t) — выпуклая убывающая функция ϕ (0) = 1, ϕ (t) ≥ 0;

ψ (t) — вогнутая растущая функция ψ (0) = 0. Покажем, что σ (t) убывает с ростом t. g

ψ (t)

Так как S(t) — вогнутая функция, то для любого α ∈[0,1] и t0 < t2 имеем (1–α)S(t0) + αS(t2) ≤ S((1–α)t0+α t2). Для t1 < t2 положим α = t1/t2, t0 = 0.

gϕ (t) t

Тогда S(t0)=0 и t1S(t2) ≤ t2S(t1), то есть σ (t1) ≥ σ (t2). Следовательно, оборудование выгодно эксплуатировать как можно дольше. Лекция 3. Задача о ближайшем соседе

-5-

Случай 2.

ϕ (t) = e–λ t, ψ (t) = k (e–µ t –1), λ > 0, k > 0, µ > 0. Тогда σ (t) = [g(1 – e–λ t) + k (e–µ t –1)]/t — выпуклая функция. и t* можно найти методом дихотомии за O(log(T/ε)) операций, где ε — требуемая точность, T — оценка сверху на t*. 1

ψ (t)

ϕ (t) t Лекция 3. Задача о ближайшем соседе

-6-

Задача замены оборудования с учетом дисконтирования затрат Приведение затрат к начальному моменту Пусть χ — банковский процент, или коэффициент эффективности капиталовложений (годовая норма дисконта). Если S1 — капитал в начальный год, то по истечении года эта сумма станет равной S2 = S1⋅(1 + χ), а в конце t-го года St = S1⋅(1 + χ)t–1. Если в год t хотим потратить сумму St, то в начальный год должны иметь St . Затраты St в год t, будучи приведенными к начальному моменS1 = t −1 (1 + χ ) ту t =1, равны

~ S = α t −1 ⋅ St ,

где α = 1+1χ — коэффициент дисконтирования, 0 < α ≤ 1. Лекция 3. Задача о ближайшем соседе

-7-

Если в течении T лет производились траты S1, S2,…, St приведенные затраты вычисляются по формуле: ~ T t −1 S = ∑α St .

то суммарные

t =1

Пример. Рассмотрим распределение капитала в 8 млн. руб. в течение 8 лет при банковском проценте χ = 0.1 (α = 0.91) и трех стратегиях: 1) все траты в 1-й год; 2) равномерные траты; 3) все траты в последний год. Стратегия

1 2 3

Год

1 8 1 –

2 – 1 –

3 – 1 –

4 – 1 –

5 – 1 –

6 – 1 –

7 – 1 –

8 – 1 8

Суммарные приведенные затраты

8.0 5.9 4.2

Лекция 3. Задача о ближайшем соседе

-8-

Постановка задачи g — начальная стоимость оборудования; ct — стоимость эксплуатации оборудования в t год, ct+1 ≥ ct; Система функционирует бесконечно, оборудование периодически заменяется. T — период замены оборудования; ST — суммарные затраты при фиксированном периоде замены T : T

T

T

t =1

t =1

t =1

ST = g + ∑ α t −1ct + α T g + ∑ α T + t −1ct + α 2T g + ∑ α 2T + t −1ct + ... . за первые T лет

за вторые T лет

………….

Благодаря дисконтированию затрат (α < 1) величина ST конечна: T

T

t =1

t =1

ST = ( g + ∑ α t −1ct )(1 + α T + α 2T + ...) = ( g + ∑ α t −1ct ) /(1 − α T ) < ∞ .

Задача отыскания оптимального периода замены оборудования:

ST → min

Лекция 3. Задача о ближайшем соседе

T >0

-9-

Теорема. Если эксплуатационные затраты ct не убывают со временем, то оптимальный период замены T*, если он существует, определяется следующим соотношением T*=min {T | cT+1> (1– α)ST , T >0, целое}.

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

Лекция 3. Задача о ближайшем соседе

-10-

Лемма 1.

∆ST +1 = ST +1 − ST = KT ,α (cT +1 − (1 − α ) ST ), где KT ,α = α T /(1 − α T +1 ),

Доказательство.

∆ST +1 = ( g +

T ≥ 1.

T +1

t −1 T +1 α c ) /( 1 − α ) − ST = ∑ t

t =1

ST (1 − α T ) + α T cT +1 − ST (1 − α T +1 ) 1 − α T +1

αT = (c − (1 − α ) ST ). T +1 T +1 1−α

Следствие 1. При T > 0

∆ST+1 > 0 ⇔ cT + 1 > (1 – α)ST .

Лекция 3. Задача о ближайшем соседе

-11-

Лемма 2. Пусть существует T* = min {T | ∆ST+1 > 0}. Тогда последовательность {ST}, T = T*, T*+1, T*+2,… — монотонно возрастающая. Доказательство проведем индукцией по T. При T = T* имеем ∆ST*+1 > 0 и ST* < ST*+1. Пусть ST* < ST*+1 < …< ST , T > T*. Покажем, что ST < ST+1. Учитывая неубывание последовательности {ct} и положительность ∆ST, по лемме 1 имеем ST +1 − ST = KT ,α (cT +1 − (1 − α ) ST ) ≥ KT ,α (cT − (1 − α ) ST ) = = K T ,α (cT − (1 − α ) S T −1 − (1 − α )∆S T ) = K T ,α (∆S T /( K T −1,α ) − (1 − α )∆S T ) =

α (1 − α T −1 ) = ∆ST > 0 . T +1 1−α Следствие 2. Если существует T* согласно лемме 2, то функция ST — квазивыпуклая с минимум в точке T*.

Утверждение теоремы вытекает из следствий 1 и 2. Если T* не существует, то затраты ST — невозрастающая функция и оборудование заменять не следует. Лекция 3. Задача о ближайшем соседе

-12-

Применение динамического программирования Рассмотрим систему, функционирующую в течение T лет, причем решение о замене оборудования принимается каждый год. Дано: {1,…, m} — набор типов оборудования; g ti — стоимость оборудования i-го типа, купленного в год t;

cti (τ ) — стоимость годовых эксплуатационных затрат на оборудование i-го типа, купленного в год t и проработавшего τ лет; Φti (τ ) — остаточная стоимость оборудования i-го типа возраста τ, купленного в год t; n — максимально допустимый возраст оборудования; i0, τ0 — тип и возраст оборудования в начале функционирования; Пусть Sti (τ ) — минимальные суммарные затраты в интервале [t, T], приведенные к началу t-го года, при условии, что в начале t-го года было оборудоi вание типа i возраста τ. Требуется найти S10 (τ 0 ) . Лекция 3. Задача о ближайшем соседе

-13-

Рекуррентные соотношения: ⎧cTi −τ (τ + 1) − αΦ Ti −τ (τ + 1), если замены нет, ⎪ i S T (τ ) = min ⎨ k k k i min [ g c ( 1 ) α Φ ( 1 )] Φ + − − T T T −τ (τ ), в случае замены, ⎪⎩1≤k ≤m T

1 ≤ τ ≤ n, 1 ≤ i ≤ m, ⎧cti −τ (τ + 1) + αSti+1 (τ + 1), ⎪ Sti (τ ) = min ⎨ k k k i + + − min [ g c ( 1 ) α S ( 1 )] Φ t t +1 t −τ (τ ), ⎪⎩1≤ k ≤ m t

если продолжаем эксплуатировать оборудование если заменяем оборудование

1 ≤ τ ≤ n, 1 ≤ i ≤ m, 1 ≤ t < T. Алгоритм может быть реализован с трудоемкостью T = O(mnT), и памятью П = O(mnT). Лекция 3. Задача о ближайшем соседе

-14-

Задача упаковки в контейнеры Дано: множество предметов L = {1, … , n} и их веса wi∈(0,1), i∈L. Найти: разбиение множества L на минимальное число m подмножеств B1, B2, … , Bm такое, что

∑ wi ≤ 1, для всех 1 ≤ j ≤ m.

i∈B j

Множества Bj называют контейнерами. Требуется упаковать предметы в минимальное число контейнеров. Задача NP-трудна и часто возникает в приложениях.

Лекция 4. Задачи раскроя и упаковки

-1-

Алгоритм «Следующий подходящий» (NF) В произвольном порядке упаковываем предметы по следующему правилу. Первый предмет помещаем в первый контейнер. На k-м шаге пытаемся поместить k-й предмет в текущий контейнер. Если предмет входит, то помещаем его и переходим к следующему шагу, иначе помещаем предмет в новый контейнер. Т = О(n), П = О(1). Теорема. NF(L) ≤ 2OPT(L). Доказательство. Пусть W =

∑ wi . Так как любые два последовательных кон-

i∈L

тейнера содержат предметы суммарным весом не меньше единицы, то NF(L) < 2⎡W⎤. Кроме того, OPT(L) ≥ ⎡W⎤, откуда и следует требуемое. Лекция 4. Задачи раскроя и упаковки

-2-

Пример L = {12 , 21N , 12 , 21N , ..., 12 , 21N }.

½

Всего 4N предметов.

1/2N 1/2N 1/2N 1/2N

½

½ 1/2N

N

1

2N

OPT(L) = N + 1

NF(L) = 2N

Замечание. NF(L) ≤ 2OPT(L) – 1 для всех L. Лекция 4. Задачи раскроя и упаковки

-3-

Пусть алгоритм A для множества L порождает A(L) контейнеров и R A ( L) ≡ A( L)

OPT ( L)

.

Для задачи на минимум гарантированная относительная точность RA для алгоритма A определяется как RA ≡ inf {r ≥ 1 | RA (L) ≤ r для всех L}. Определение. Асимптотическая гарантированная относительная точность R A∞ для алгоритма A определяется как

R A∞ ≡ inf {r ≥ 1 | ∃ N > 0 такое, что RA (L) ≤ r для всех L с OPT(L) ≥ N}.

Лекция 4. Задачи раскроя и упаковки

-4-

Алгоритм «Первый подходящий» (FF) В произвольном порядке упаковываем предметы по следующему правилу. Первый предмет помещаем в первый контейнер. На k-м шаге находим контейнер с наименьшим номером, куда помещается k-й предмет, и помещаем его туда. Если такого контейнера нет, то берем новый пустой контейнер и помещаем предмет в него. Т = О(n2), П = О(n).

OPT(L) +1⎤ для всех L и существуют примеры со сколь Теорема. FF(L) ≤ ⎡ 17 10 OPT(L) – 1⎤ . угодно большими значениями OPT, для которых FF(L) ≥ ⎡ 17 10 (Без доказательства) Лекция 4. Задачи раскроя и упаковки

-5-

Пример

L = {1,…, 18 m}

1/7 + ε 1/3 + ε 1/2 + ε

⎧1 + ε , 1 ≤ i ≤ 6m 7 ⎪⎪1 wi = ⎨ 3 + ε , 6m < i ≤ 12m ⎪1 ⎪⎩ 2 + ε , 12m < i ≤ 18m

1/7 + ε 1/7 + ε 1/7 + ε 1/7 + ε 1/7 + ε

1/3 + ε 1/2 1/2 + + εε 1/3 + ε

FF ( L) 5 = OPT ( L) 3

1/7 + ε

m

OPT(L) = 6m

3m

6m

FF(L) = 10m

Лекция 4. Задачи раскроя и упаковки

-6-

Алгоритм «Наилучший подходящий» (BF) В произвольном порядке упаковываем предметы по следующему правилу. Первый предмет помещаем в первый контейнер. На k-м шаге размещаем k-й предмет. Находим частично заполненные контейнеры, где достаточно для него свободного места и выбираем среди них наиболее заполненный. Если таких нет, то берем новый пустой контейнер и помещаем k-й предмет в него. Т = О(n2), П = О(n). ∞ ∞ RBF = RFF и существуют примеры со сколь угодно большими значениями OPT(L), для которых BF(L) = 4/3 FF(L)

Теорема. RBF = RFF,

и FF(L) = 3/2 BF(L). (Без доказательства) Лекция 4. Задачи раскроя и упаковки

-7-

Алгоритмы типа On-line Предметы поступают в непредсказуемом порядке. Требуется упаковать их в минимальное число контейнеров. Упакованный предмет нельзя перемещать в другой контейнер. Место для предварительного хранения предметов отсутствует. Алгоритмы NF, FF, BF являются On-line алгоритмами.

Теорема. Для любого On-line алгоритма A справедливо неравенство R A∞ > 1.5 (Без доказательства)

Лекция 4. Задачи раскроя и упаковки

-8-

Алгоритмы с ограниченным доступом к контейнерам On-line алгоритм называют алгоритмом с ограниченным доступом к контейнерам, если на каждом шаге алгоритм имеет возможность помещать предметы только в один из K контейнеров (K — const). Эти контейнеры называются открытыми. Если контейнер закрыли, то он уже не открывается (например, отправляется потребителю). Прежде чем добавить пустой открытый контейнер, нужно закрыть один из K открытых контейнеров. Алгоритм NF — пример для K = 1. Правила для выбора контейнера 1. Закрыть контейнер с наименьшим номером 2. Закрыть самый заполненный контейнер.

Лекция 4. Задачи раскроя и упаковки

-9-

Примеры алгоритмов с ограниченным доступом FF1 — алгоритм FF с правилом 1. FF2 — алгоритм FF с правилом 2. BF1 — алгоритм BF с правилом 1. BF2 — алгоритм BF с правилом 2. Теорема. Для любого K ≥ 2 ∞ ∞ 3 = R = 1 , 7 + . 1) RFF FF2 1 10( K −1)

∞ 3 . = 1 , 7 + 2) RBF 1 10 K ∞ = 1,7 . 3) RBF 2

4) Для любого алгоритма A с ограниченным доступом к контейнерам R A∞ ≥ 1,69103... Лекция 4. Задачи раскроя и упаковки

-10-

Алгоритм «Первый подходящий с упорядочиванием» (FFD) • Сортируем предметы по невозрастанию весов w1 ≥ w2 ≥ … ≥ wn • Применяем алгоритм FF (BF). Теорема. FFD(L) ≤ 11 OPT(L) + 4 для всех L и существуют примеры со 9 сколь угодно большими значениями OPT(L), для которых

FFD(L) ≥ 11 OPT(L). 9 ∞ ∞ = RBFD = 11 ≈ 1.22 . Кроме того RFFD 9

(Без доказательства)

Лекция 4. Задачи раскроя и упаковки

-11-

Пример

L = {1,…, 30 m}

¼ – 2ε

¼ – 2ε

¼+ε

¼ – 2ε

½ +ε

¼ + 2ε

⎧1 + ε , ⎪ 12 ⎪ 4 + 2ε , wi = ⎨ 1 ⎪4 + ε , ⎪ 1 − 2ε , ⎩4

1 ≤ i ≤ 6m 6m < i ≤ 12m 12m < i ≤ 18m 18m < i ≤ 30m

¼ + 2ε ½ +ε

¼ + 2ε

6m

3m

OPT(L) = 9m

¼+ε ¼+ε ¼+ε

6m

2m

¼ – 2ε ¼ – 2ε ¼ – 2ε ¼ – 2ε

3m

FFD(L) = 11m Лекция 4. Задачи раскроя и упаковки

-12-

Асимптотические гарантированные оценки точности Алгоритм

T*A

R A∞

R A∞ ( 1 2 )

R A∞ ( 13 )

R A∞ ( 1 4 )

NF

O(n)

2.000

2.000

1.500

1.333

FF

O(n log n)

1.700

1.500

1.333

1.250

BF

O(n log n)

1.700

1.500

1.333

1.250

NFD

O(n log n)

1.691

1.424

1.302

1.234

FFD

O(n log n)

1.222

1.183

1.183

1.150

BFD

O(n log n)

1.222

1.183

1.183

1.150

R A∞ (α ) — асимптотическая точность для примеров с весами предметов

wi ≤ α, для всех i ∈ L. Лекция 4. Задачи раскроя и упаковки

-13-

Теорема. Для любого ε ∈ (0,1] существует алгоритм Aε , который находит

упаковку с числом контейнеров не более (1 + 2ε) OPT + 1. Трудоемкость Aε полиномиально зависит от n . (Без доказательства) Алгоритм Aε

1. Удалить предметы с весом менее ε. 2. Упорядочить оставшиеся предметы и разбить их на K = ⎡1/ε 2⎤ групп. 3. В каждой группе увеличить веса предметов до максимального веса в группе. 4. Найти оптимальную упаковку предметов, имеющих только K различных весов каждый из которых не менее ε. 5. Вернуть исходные веса предметов и применить алгоритм FF для предметов с весом менее ε. Лекция 4. Задачи раскроя и упаковки

-14-

Негативный результат Теорема. Для любого ε > 0 существование приближенного полиномиально-

го алгоритма A с гарантированной точностью RA = 32 – ε влечет P = NP. Доказательство. Пусть такой алгоритм А существует. Покажем, как с его помощью можно решить точно одну из NP-полных задач, а именно задачу о разбиении. Дано n неотрицательных чисел a1,…, an. Можно ли разбить их на два подмножества так, чтобы сумма чисел в каждом подмножестве равнялась C=

1 2

n

∑ ai ?

Рассмотрим задачу упаковки в контейнеры с весами предметов

i =1

wi =ai/C, i = 1,…, n. Если их можно упаковать в два контейнера, ответ в задаче о разбиении — «ДА». Применим алгоритм А к задаче о контейнерах. Если OPT = 2, то алгоритм А тоже дает 2, иначе RA ≥ 32 , то есть алгоритм А точный. Лекция 4. Задачи раскроя и упаковки

-15-

Нижние оценки 1, Переменные задачи y j = ⎧⎨ ⎩0, 1, xij = ⎧⎨ ⎩0, Математическая модель

если используется контейнер j в противном случае

если предмет i помещен в контейнер j в противном случае n

min ∑ y j j =1

при ограничениях

m

∑ wi xij ≤ y j ,

j = 1,..., n,

i =1

n

∑ xij = 1,

i = 1,..., n,

j =1

yj, xij ∈{0,1} i, j = 1,…, n. Лекция 4. Задачи раскроя и упаковки

-16-

Релаксация линейного программирования Заменим условие Булевости переменных на условия: 0 ≤ yj ≤ 1, j = 1,…, n 0 ≤ xij ≤ 1, i, j = 1,…, n. Тогда одно из оптимальных решений имеет вид 1, i = j , y ∗j = w j , xij∗ = ⎧⎨ ⎩0, i ≠ j что дает нижнюю оценку ⎡n ⎤ H 0 = ⎢∑ wi ⎥ ⎢i =1 ⎥ (предметы можно резать произвольным образом).

Лекция 4. Задачи раскроя и упаковки

-17-

Оценки Martello & Toth Для примера L = {1,…, n}, 0 ≤ wi < 1 и произвольного 0 ≤ α ≤ ½ положим L1 = { i∈L | wi > 1 – α }

— крупные предметы

L2 = { i∈L | 1– α ≥ wi > ½ } — средние предметы L3 = { i∈L | ½ ≥ wi ≥ α } — мелкие предметы Теорема. Для любого 0 ≤ α ≤ ½ величина ⎛ ⎡ ⎤ ⎜ H1 (α ) = | L1 | + | L2 | + max 0, ⎢ ∑ wi − (| L2 | − ∑ wi )⎥ ⎜ ⎢ ⎥⎥ i∈L2 ⎝ ⎢i∈L3

⎞ ⎟. ⎟ ⎠

является нижней оценкой для OPT(L).

Лекция 4. Задачи раскроя и упаковки

-18-

Доказательство. Каждый предмет из множества L1 ∪ L2 требует отдельный

контейнер. Поэтому в любом допустимом решении не менее | L1 | + | L2 | контейнеров. Предметы из множества L3 не лежат вместе с предметами из L1. Значит, они лежат либо вместе с предметами из L2 , либо в отдельных контей⎛ ⎞ ⎜ нерах. В контейнерах для L2 осталось S = | L2 | − ∑ wi ⎟ свободного места. ⎟ ⎜ i L ∈ ⎠ ⎝ 2 Следовательно, для предметов из множества L3 требуется как минимум ⎡ ⎤ ⎢ ∑ wi − S ⎥ отдельных контейнеров. ⎢⎢i∈L3 ⎥⎥

Лекция 4. Задачи раскроя и упаковки

-19-

Теорема. Для любого 0 ≤ α ≤ ½ величина H 2 (α ) =| L1 | + | L2 | + max ⎧⎨ ⎩

⎣ ⎦⎥⎤

1− wi ⎡| L | − ⎢ 3 ∑ α i∈L2 0, ⎢ ⎢ 1 ⎢ ⎣ α ⎦ ⎢

⎫ ⎥ ⎬ ⎥ ⎭ ⎥ ⎥

является нижней оценкой для OPT(L). Доказательство. Заменим вес каждого предмета из множества L3 на α. Тогда

⎣ ⎦

в один контейнер войдет α1 предметов, и для множества L3 потребовалось ⎤ дополнительных контейнеров. Но часть предметов из L можно бы ⎡⎢| L 3 | 3 ⎥ ⎢

⎣ α1 ⎦⎥

уложить в контейнеры для L2. Каждый из них имеет 1– wi, i∈L2 свободного ⎢1 − wi ⎥ места, где поместится ⎢ предметов из L3. ⎥ ⎣ α ⎦ Лекция 4. Задачи раскроя и упаковки

-20-

Следствие 1. Величина H = max{H1 (α ), H 2 (α ), 0 ≤ α ≤ 0,5} является нижней оценкой для OPT(L). ⎡ ⎤ Следствие 2. H ≥ H 0 ≡ ⎢ ∑ wi ⎥ . ⎢i∈L ⎥

Доказательство. При α = 0 получаем H ≥ H1(0) = max{|L2|, H0}≥ H0. Следствие 3. Пусть V — множество всех различных значений wi ≤ 0,5. Тогда если V = ∅, n, ⎧ H =⎨ ⎩max{H1 (α ), H 2 (α ), для α ∈V }, если V ≠ ∅.

т. е. после сортировки предметов получаем TH = O (n + n log n).

Лекция 4. Задачи раскроя и упаковки

-21-

Дополнительная литература 1. E.G. Coffman, M.R. Garey, D.S. Johnson. Approximation algorithms for bin packing: A survey. http://www.math.nsc.ru/LBRT/k5/bp-chapter.pdf 2. Э.Х. Гимади. О некоторых математических моделях и методах планирования крупномасштабных проектов //Модели и методы оптимизации. Труды Института математики. Новосибирск. Наука. Сиб. Отд–ние. 1988. с. 89–115. 3. М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. с. 154–191.

Лекция 4. Задачи раскроя и упаковки

-22-

Задачи двумерной упаковки Дано:

n прямоугольных предметов с размерами wi × li , i = 1,…, n.

Найти:

упаковку в положительном ортанте с минимальной площадью окаймляющего прямоугольника

y Повороты запрещены. Стороны предметов параллельны осям координат.

6 W

2 1

L × M → min

5 3

4

L

Задача является NP-трудной. x Пример гильотинной упаковки Лекция 5. Задачи раскроя и упаковки

-1-

Задача упаковки в полосу Дано: n прямоугольных предметов с размерами wi × li , i = 1,…, n, и полубесконечная полоса шириной W. Найти: упаковку предметов с минимальной длиной занимаемой полосы. y При li=1 , i = 1,…, n, получаем одномерную

2 4

W 1

5

задачу упаковки в контейнеры.

3

x

Лекция 5. Задачи раскроя и упаковки

-2-

Задача о рюкзаке для прямоугольников Дано:

n прямоугольных предметов с размерами wi × li и весами ci, i = 1,…, n, и большой прямоугольник W × L.

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

5

При li=L, i = 1,…, n, 6

получаем известную задачу о рюкзаке.

4

7

W

10

1

3

2

8

L Лекция 5. Задачи раскроя и упаковки

-3-

Задача упаковки в контейнеры для прямоугольников Дано: n прямоугольных предметов с размерами wi × li , i = 1,…, n, и неограниченное число одинаковых заготовок размером W × L. Найти: упаковку предметов с минимальным числом используемых заготовок.

3

L

5

W n 1

2

4

... L Лекция 5. Задачи раскроя и упаковки

-4-

Задача прямоугольного раскроя для серийного производства n прямоугольных предметов с размерами wi × li и потребностью ki штук i = 1,…, n. Известны размеры заготовок W × L.

Дано:

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

6

7

3

1

2

n–1

5

n

... Лекция 5. Задачи раскроя и упаковки

-5-

Кодировки решений Список предметов L = {i1, i2, … , in}. Декодирующая процедура: до упора влево, до упора вниз, до упора влево, … Если нельзя сдвинуть предмет влево или вправо, то переходим к следующему предмету.

3

5 2

W 1

4

Всего n! вариантов. Лекция 5. Задачи раскроя и упаковки

-6-

Контрпример

2

W 1

5

7

4

6

8

Оптимальное решение, которое нельзя получить никаким списком.

3

Пример негильотинной упаковки..

Лекция 5. Задачи раскроя и упаковки

-7-

Определение. Кодировка решений называется допустимой, если она удовлетворяет следующим требованиям: 1. множество всех кодов конечно; 2. каждому коду соответствует допустимое решение; 3. вычисление целевой функции для каждого кода осуществляется с полиномиальной трудоемкостью; 4. решение, соответствующее коду с наименьшим значением целевой функции, является оптимальным решением исходной задачи. Пример. Каждому предмету сопоставляется два числа (x, y) — координаты левого нижнего угла.

Лекция 5. Задачи раскроя и упаковки

-8-

Кодировка «O – tree» Определение. Решение называется L–компактным, если ни один предмет нельзя сместить влево при условии, что остальные предметы остаются неподвижными. Аналогично определяются B–, V– и R–компактные решения для смещения вниз, вверх и вправо соответственно. Решение называется LB–компактным, если оно является L–компактным и B–компактным одновременно. 5

5

2 1

2

4 3

LB–компактное

1

4 3

B–, но не L–компактное Лекция 5. Задачи раскроя и упаковки

-9-

Представление LB–компактных решений Корень дерева — левая граница упаковки. Ориентация дуг от корня к листьям. Предмет Bi связан дугой с Bj, если левая сторона Bj касается правой стороны Bi. Если для Bj имеется несколько таких предметов (Bi, Bk), то дуга идет только от нижнего предмета.

Всего вариантов n ! ⋅ C2nn +1 /( 2n + 1) (числа Каталана) Bk Bi

Bj

Лекция 5. Задачи раскроя и упаковки

-10-

Процедура декодирования Дано:

ориентированное корневое дерево, каждой вершине кроме корня приписан предмет (метка).

Найти: площадь окаймляющего прямоугольника.

Bk

Поиск в глубину Bj Bi

Упражнение. Найти алгоритм декодирования с T = O(n) Лекция 5. Задачи раскроя и упаковки

-11-

Соседние упаковки Для данного корневого ориентированного дерева с помеченными вершинами определим две операции: • две некорневые вершины меняются метками (предметами); • отрываем лист дерева и приклеиваем к другой вершине. Каждая операция порождает новую упаковку. Таких упаковок O(n2). Назовем их соседними для данной. Множество соседних упаковок называется окрестностью.

Лекция 5. Задачи раскроя и упаковки

-12-

Алгоритм локального спуска S — упаковка N(S) — окрестность для S. F(S) — значение целевой функции для S. Алгоритм

1. Выбрать начальное решение S и вычислить F(S). 2. Найти в окрестности N(S) решение S′ с минимальным значением целевой функции F ( S ′) = min{F ( S ), S ∈ N ( S )}. 3. Если F(S′ ) < F(S), то положить S := S′ и вернуться на 2 иначе STOP.

Лекция 5. Задачи раскроя и упаковки

-13-

Число локальных оптимумов

Численные эксперименты

Имитация отжига

Локальный спуск

Относительная погрешность

Задача упаковки в положительном ортанте, n = 100. Лекция 5. Задачи раскроя и упаковки

-14-

Алгоритм имитации отжига Предложен в 1983 г. физиками S. Kirpatrick, C.D. Gelatt, M.P. Vecchi. В основе аналогия с поведением атомов при медленном остывании тела.

Число итераций

Алгоритм не останавливается в локальном минимуме и может «путешествовать» по всей допустимой области. Лекция 5. Задачи раскроя и упаковки

-15-

Общая схема имитации отжига 1. Выбрать начальное решение S и вычислить F(S). 2. Задать начальную температуру T. 3. Пока не выполнен критерий остановки, делать следующее: 3.1. Выполнить цикл L раз: 3.1.1.

Выбрать в N(S) случайным образом решение S′ ;

3.1.2.

Положить ∆ = F(S′ ) – F(S);

3.1.3.

Если ∆ ≤ 0, то S := S′ ;

3.1.4.

Если ∆ > 0, то с вероятностью e

−∆T

положить S := S′ ;

3.2. Понизить температуру T := T ⋅ r.

Лекция 5. Задачи раскроя и упаковки

-16-

Параметры алгоритма • Начальная температура T. • Коэффициент охлаждения r. • Число шагов L при заданной температуре • Критерий остановки: – минимальное значение температуры – число смен температуры без изменения текущего решения S. – суммарное число шагов алгоритма

Лекция 5. Задачи раскроя и упаковки

-17-

Зависимость частоты переходов в соседнее решение от температуры

Понижение температуры Лекция 5. Задачи раскроя и упаковки

-18-

Переход от LB–компактных к RB–компактным решениям Перестройка корневого ориентированного дерева без ухудшения целевой функции. Выполняется при каждой смене температуры.

Лекция 5. Задачи раскроя и упаковки

-19-

Лекция 5. Задачи раскроя и упаковки

-20-

Лекция 5. Задачи раскроя и упаковки

-21-

Задачи календарного планирования Олимпийские игры 1992 г., Барселона, более 2000 мероприятий за 15 дней. • частичный порядок на множестве событий (четверть финала, полуфинал, финал); • мощность спортивных сооружений (число одновременных соревнований, число зрителей); • транспортные проблемы и доход (максимизировать посещаемость наиболее популярных соревнований — раздвинуть их по времени); • требования TV (минимум параллельных трансляций); • обеспечение безопасности (число полицейских ограничено). Система поддержки решений «SUCCESS–92» Университет г. Барселоны

Лекция 6. Задачи календарного планирования. Часть 1

-1-

Постановка задачи Дано: J = {1,…, n} — множество работ;

τj ≥ 0 — длительность работы j; C = {(i, j)| i, j∈ J} — частичный порядок, работа j не может начаться раньше окончания работы i. Найти: • Минимальное время завершения всего проекта. • Наиболее ранний момент начала и завершения каждой работы. • Множество критических работ, то есть таких работ, задержка хотя бы одной из которых приведет к задержке всего проекта. • Допустимое запаздывание для некритических работ. • Вероятность завершения проекта к заданному сроку. Лекция 6. Задачи календарного планирования. Часть 1

-2-

Сетевой график «работы — дуги» G = (V, E) — ориентированный взвешенный граф без циклов с одним источником s и одним стоком t, каждой дуге j = (i, k) приписан вес τj ≥ 0.

s

. . .

Вершины — события.

t

Дуги — работы.

Лекция 6. Задачи календарного планирования. Часть 1

-3-

Пример Предшествование

Длительность

A — выбрать место для офиса

—

3

B — создать финансовый и организационный план

—

5

C — определить обязанности персонала

B

3

A, C

5

E — ремонт помещений

D

10

F — отобрать кандидатов на увольнение

C

2

G — нанять новых служащих

F

5

H — назначить ключевых руководителей

F

2

I — распределить обязанности руководителей

B

5

H, E, G

3

D — разработать план офиса

J — обучить персонал

Лекция 6. Задачи календарного планирования. Часть 1

-4-

Диаграмма Гантта J I H G F E D C B A 3

5

8

10

13

15

23

26

Работа E является критической. Задержка работы F ведет к задержке работ G, H , но не работы J. Лекция 6. Задачи календарного планирования. Часть 1

-5-

Сетевой график «работы — дуги» D

E

C

F

s B

G

J

t

H

I

Некоторые фиктивные дуги можно исключить A

D

E J

s B

G C

F

H

t

I Лекция 6. Задачи календарного планирования. Часть 1

-6-

Параметры сетевой модели Определение. Рангом r(x) вершины x∈V называется число дуг в максимальном пути (по числу дуг) из источника s в вершину x. Рангом проекта R называется ранг стока t : R = r(t). Рекуррентные соотношения для рангов 0, x=s r ( x) = ⎧⎨ ⎩max{r ( y ) + 1 | ( y, x) ∈ E}, x ≠ s

Лекция 6. Задачи календарного планирования. Часть 1

-7-

Алгоритм Форда |V| = n, |E| = m,

дуга e = (i(e), k(e))∈E.

Алгоритм 1. r(x) := 0 для всех x∈V. 2. for l := 1,…, |V| do for e := 1,…, |E| do if r(k(e)) < r(i(e)) + 1 then r(k(e)) := r(i(e)) + 1. T = O(|V| |E| ), П = O(|V| + |E| )

Лекция 6. Задачи календарного планирования. Часть 1

-8-

Определение. Нумерация вершин сети G = (V, E) называется правильной, если для каждой дуги e = (i(e), k(e))∈E справедливо неравенство i(e) < k(e). Построение правильной нумерации вершин

r(x) = 1

r(x) = 2

...

...

t ...

s

r(x) = R–1

В произвольном порядке нумеруем вершины ранга 1, затем ранга 2, и т.д. Лекция 6. Задачи календарного планирования. Часть 1

-9-

Определение. Наиболее ранним моментом свершения события x называется минимальный момент времени Tp(x), раньше которого данное событие произойти не может. Обозначим через Lsx длину максимального пути из s в x во взвешенном графе G = (V, E), τ (e) ≥ 0, e∈E.

Тогда Tp(x) = Lsx.

Рекуррентные соотношения 0, TP ( x) = ⎧⎨ ⎩max{TP ( y ) + τ ( yx) | ( yx) ∈ E},

x=s x≠s

Упражнение 1. Используя правильную нумерацию вершин построить алгоритм вычисления всех величин TР (x) с трудоемкостью Т=О(|V|).

Лекция 6. Задачи календарного планирования. Часть 1

-10-

Критическое время проекта — наиболее раннее время завершения всего проекта, то есть TКр = TР(t). Определение. Всякий путь в G = (V, E), имеющий длину TКр называется критическим. Работы и события, лежащие на критическом пути, называются критическими. D

A

5

3

s B

E 10

G

0

5

5

C

F

3

2

I

H 2

J 3

t

5

Лекция 6. Задачи календарного планирования. Часть 1

-11-

Определение. Наиболее поздним моментом TП (x) свершения события x называется максимально возможный момент свершения события x, не приводящий к увеличению TКр. Легко заметить, что TП (x) = TКр – Lxt. Рекуррентные соотношения x=t ⎧TКр , TП ( x ) = ⎨ ⎩min{TП ( y ) − τ ( x, y ) | ( x, y ) ∈ E}, x ≠ t

L y1t

y1 S

y2

… x y3

L y 2t

t

L y 3t

Упражнение 2. Построить алгоритм вычисления величин TП (x) с Т=О(|V|). Лекция 6. Задачи календарного планирования. Часть 1

-12-

Определение. Полным резервом времени для работы e = (i, k) ∈ E называется величина TП(k) – TР(i) – τ (e). Теорема. Необходимым и достаточным условием принадлежности работы критическому пути является равенство нулю ее полного резерва времени. Доказательство. Необходимость. Пусть дуга e = (i, k) является критической. Тогда Lsi + τ (e) + Lkt = LКр и

(TКр – Lkt) – Lsi – τ (e) = 0,

но TКр – Lkt = TП(k) и Lsi = TР(i), откуда и следует доказательство теоремы. Достаточность доказывается аналогично. Следствие. Событие x является критическим если и только если TР(x) = TП(x). Лекция 6. Задачи календарного планирования. Часть 1

-13-

Стратегический анализ Критический путь B, C, D, E, J. Длина пути TКр = 26. Работа J — обучение персонала. Работа E — ремонт помещений. Можно обучать персонал в учебном центре и убрать предшествование E для J. Длительности работ можно сократить, если привлечь дополнительные средства. D

A

E 5

3

s B

10

G

0

5

5

C

F 3

2

H 2

J 3

t

I 5

Лекция 6. Задачи календарного планирования. Часть 1

-14-

Новая сетевая модель Сократили длительности работ D, E, G и удалили работу E из предшественников работы J. Новый критический путь B, C, D, E. Длина пути TКр = 20.

D

A

E 4

3

s B

8 0

5

G

C

F 3

2

I

4

H

3 2

J

t

5

Лекция 6. Задачи календарного планирования. Часть 1

-15-

Вероятностная модель Для каждой работы j∈J кроме τj — длительности выполнения (в среднем) зададим три величины: aj — оптимальное время завершения; mj — наиболее вероятное время завершения; bj — пессимистическое время завершения. pj

β – распределение • несимметричное • равно 0 вне интервала [a, b]

t aj

mj τ j

bj Лекция 6. Задачи календарного планирования. Часть 1

-16-

Оценка параметров для β – распределения Для работы j среднее значение τ j ≈ стандартное отклонение σ τj A B C D E F G H I J

a 1 3 2 2 4 1 2,5 1 4 1,5

m 3 4,5 3 4 7 1,5 3,5 2 5 3

(a j + 4m j + b j ) , 6

b j −a j j ≈ 6 . Среднее b

5 9 4 6 16 5 7,5 3 6 4,5

3 5 3 4 8 2 4 2 5 3

2

b j −a j ⎞ ⎛ дисперсия σ j ≈ ⎜ ⎟ , 6 ⎝ ⎠

Ст. отклонение Дисперсия

2/3 1 1/3 2/3 2 2/3 5/6 1/3 1/3 1/2

4/9 1 1/9 4/9 4 4/9 25/36 1/9 1/9 1/4

Лекция 6. Задачи календарного планирования. Часть 1

-17-

Вероятность завершения проекта к заданному сроку Предполагаем, что • длительности работ являются независимыми случайными величинами; ~ • случайная величина TКр имеет нормальное распределение. ~ Требуется оценить Prob{TКр ≤ T*} для любого T*. ~ Пример. Берем критический путь B, C, D, E и считаем дисперсию для TКр . ~ σ (TКр ) = σ (B) + σ (C) + σ (D) + σ (E) = 1 + 13 + 94 + 4 = 50 . Стандартное откло9 ~ ~ нение σ (TКр ) = 50 9 = 2,357. Итак, TКр – нормально распределенная слу-

чайная величина с мат.ожиданием TКр =20 и стандартным отклонением 2,357. ~ Тогда для z = (TКр − TКр ) / σ при T*= 22 получаем ~ ∗ ⎧ − − TКр ⎫⎪ T T T ⎪ ~ Кр Кр * ≤ Prob {TКр ≤ T }= Prob ⎨ ⎬ = Prob {z ≤ 0,8485} ≈ 0,8. σ σ ⎪ ⎪⎩ ⎭ Лекция 6. Задачи календарного планирования. Часть 1

-18-

Расчеты по имитационной модели Функция распределения для вероятности окончания проекта к времени T* ~ Prob{TКр ≤ T*} 100 %

80 %

60 %

40 %

20 %

T* 16.625

18.25 19.875

21.5

23.125

24.75

26.375

28

Лекция 6. Задачи календарного планирования. Часть 1

-19-

Распределение резерва времени для работы F 20 %

Полный резерв для работы F равен 3. Среднее значение полного резерва по имитационной модели 3,026, но большая дисперсия. Достаточно часто работа F оказывалась критической!

16 %

12 % 8% 4% 0% –10

–7.5

–5

–2.5

0

2.5

5

7.5

10

Лекция 6. Задачи календарного планирования. Часть 1

-20-

Заключение При анализе проекта необходимо 1. построить диаграмму Гантта и сетевой график 2. посчитать среднюю длительность каждой работы (τj = aj+4mj+bj)/6) 3. вычислить дисперсию (σ j = (b j − a j ) 2 / 36 ) Используя полученные данные 1. найти критический путь и его длину 2. вычислить полный резерв времени для каждой работы 3. определить вероятность завершения работ в этом критическом пути для желаемого срока окончания проекта. Если полученная вероятность слишком мала, то провести стратегический анализ проекта с целью сокращения критического пути за счет изменения условий предшествования и (или) длительностей работ. Лекция 6. Задачи календарного планирования. Часть 1

-21-

Анализ проекта по критерию «стоимость–длительность» Для каждой работы j∈J вместо длительности τj задан временной интервал [aj, bj] и линейная функция cj стоимости выполнения работы в зависимости от длительности. c j = k j ρ j + c 0j , k j ≤ 0

aj

bj

t

Требуется найти минимальные суммарные затраты на выполнение всех работ и соответствующие им длительности работ, чтобы закончить проект к заданному сроку T*. Лекция 7. Задачи календарного планирования. Часть 2

-1-

Модель линейного программирования Дано: J = {1,…, n} — множество работ; C = {(i, j) | i, j ∈ J} — частичный порядок; [aj, bj] — допустимый интервал выполнения работы j; c j = k j ρ j + c 0j — стоимость выполнения работы j;

T* — время окончания всего проекта. Найти: Минимальные суммарные затраты и длительность выполнения каждой работы для окончания проекта к заданному сроку T*. Модель: при ограничениях

min

∑ (k j ρ j + c0j )

ρ j j∈J

si +ρi ≤ sj, для всех (i, j) ∈C st ≤ T* aj ≤ ρj ≤ bj, j∈J. Лекция 7. Задачи календарного планирования. Часть 2

-2-

Обратная задача Дано: J = {1,…, n} — множество работ; C = {(i, j) | i, j ∈ J} — частичный порядок; [aj, bj] — допустимый интервал выполнения работы j; c j = k j ρ j + c 0j — стоимость выполнения работы j;

С* — суммарная стоимость выполнения всех работ. Найти: Наиболее раннее время выполнения проекта при условии, что суммарные стоимость выполнения всех работ не превысит величины С*. Модель: при ограничениях

min st si +ρi ≤ sj, для всех (i, j) ∈C, 0 ∗ ( k ρ + c ) ≤ C , ∑ j j j

j∈ J

aj ≤ ρj ≤ bj, j∈J. Лекция 7. Задачи календарного планирования. Часть 2

-3-

Пакеты линейного программирования ABACUS 2.3 BCP

2004 2004

http://www.informatik.uni-koeln.de/abacus/ http://www.coin-or.org/

BonsaiG 2.8

2004

http://www.cs.sfu.ca/~lou/BonsaiG/dwnldreq.html

CBC

2004

http://www.coin-or.org/.

GLPK 4.2

2004

http://www.gnu.org/software/glpk/glpk.html

lp solve 5.1

2004

http://groups.yahoo.com/group/lp_solve/

MINTO 3.1

2004

http://coral.ie.lehigh.edu/minto/

SYMPHONY 5.0 2004

http://www.branchandcut.org/SYMPHONY/

Лекция 7. Задачи календарного планирования. Часть 2

-4-

Пример A B C D E F G H I J

Длительность

TР (старт)

ТП (старт)

3 5 3 4 8 2 4 2 5 3

0 0 5 8 12 8 10 10 5 14

5 0 5 8 12 11 13 18 15 17

Итого:

Затраты

2 100 5 000 1 800 4 800 32 000 1 000 2 800 7 000 4 000 30 000 90 500

Лекция 7. Задачи календарного планирования. Часть 2

-5-

Еженедельные затраты при наиболее раннем старте работ Недели 1

2

3

700

700

4

5

A

700

B

1000 1000 1000 1000 1000

C

6

7

8

600

600

600

D

9

1200

10

11

12

14

4000 4000

F

500

700

H

3500 3500 800

800

800

J

16

17

4000

4000

4000

18

19

20

4000 4000 4000

500

G 800

15

1200 1200 1200

E

I

13

700

700

700

800 10000 10000 10000

В неделю 1700 1700 1700 1000 1000 1400 1400

1400

2500

2500 5400 5400 4700 4700 14000 14000 14000 4000 4000 4000

Всего за 1700 3400 5100 6100 7100 8500 9900 11300 13800 16300 21700 27100 31800 36500 50500 64500 78500 82500 86500 90500 проект

Лекция 7. Задачи календарного планирования. Часть 2

-6-

Еженедельные затраты при наиболее позднем старте работ Недели 1

2

3

4

5

A B C

6

7

8

700

700

700

600

600

600

9

10

11

12

13

14

15

16

17

4000

4000

4000

700

700

700

18

19

20

1000 1000 1000 1000 1000

D

1200

1200 1200 1200

E

4000 4000

F

500

G

4000 4000 4000

500 700

H

3500 3500

I

800

J

800

800

800

800

10000 10000 10000

В неделю 1000 1000 1000 1000 1000 1300 1300

1300

1200

Всего за 1000 2000 3000 4000 5000 6300 7600 проект

8900

10100 11300 12500 14200 18700 23400 28100 33600 39100 53900 72200 90500

1200 1200 1700 4500 4700

4700

5500

5500 14800 18300 18300

Лекция 7. Задачи календарного планирования. Часть 2

-7-

Управление финансами

Область допустимых решений задачи

27 600

14 200

t

Лекция 7. Задачи календарного планирования. Часть 2

-8-

Затраты к концу 11-й недели Завершенность (%)

A B C D E F G H I J

Итого

100 100 100 75 0 100 25 50 20 0

Общие затраты (план)

Текущие затраты (план)

Текущие затраты (факт)

2100 5000 1800 4800 32000 1000 2800 7000 4000 30000 90500

2100 5000 1800 3600 0 1000 700 3500 800 0 18500

2300 4900 1800 4600 0 1200 1400 5400 500 0 22100

Перерасход

200 –100 0 1000 0 200 700 1900 –300 0 3600

Лекция 7. Задачи календарного планирования. Часть 2

-9-

Календарное планирование с ограниченными ресурсами Три типа ресурсов: • Возобновляемые ресурсы (рабочее время, эфирное время, производственные мощности,…) если не потратили, то пропадают. • Складируемые ресурсы (пиломатериалы, деньги, зерно, ГСМ, …) если не потратили, то можно потратить позже. • Невозобновляемые ресурсы (кредиты, суммарный запас непополняемых материалов,…) можно потратить в любой момент выполнения проекта.

Лекция 7. Задачи календарного планирования. Часть 2

-10-

Постановка задачи Дано: J = {1,…, n} — множество работ; C = {(i, j) | i, j ∈ J} — частичный порядок; Mj, j∈J — моды (варианты) выполнения работы; Kν — множество невозобновляемых ресурсов; Kρ — множество возобновляемых ресурсов; Kσ — множество складируемых ресурсов;

Лекция 7. Задачи календарного планирования. Часть 2

-11-

ρ

σ

rkjm (τ ) ≥ 0 — потребность в ресурсе k ∈ K ∪ K в интервале времени [τ–1,τ],

считая от начала выполнения работы j в моде m; rkjm ≥ 0 — потребность в невозобновляемом ресурсе k ∈ Kν при выполнении

работы j в моде m; qk(t) ≥ 0 — количество ресурса k ∈ Kρ ∪ Kσ, выделяемое в момент времени t на выполнение всех работ; qk > 0 — количество невозобновляемого ресурса k ∈ Kν, выделяемое в момент t = 0 на выполнение всех работ в течение всего интервала планирования;

ρ mj ≥ 0 — длительность работы j в моде m; dj ≥ 0 — директивный срок окончания работы j.

Лекция 7. Задачи календарного планирования. Часть 2

-12-

Переменные задачи: m(j) — мода работы j; sj ≥ 0 — начало выполнения работы j A(t ) = { j ∈ J | s j < t ≤ s j + ρ m j } — множество работ, выполняемых в момент времени t.

Допустимое решение задачи: назначение моды m(j) и времени старта каждой работы так, чтобы выполнить • условия предшествования; • ограничения по ресурсам; • директивные сроки окончания каждой работы. Задача состоит в том, чтобы найти допустимое решение задачи с минимальным временем окончания всех работ. Лекция 7. Задачи календарного планирования. Часть 2

-13-

Математическая модель

при ограничениях

∑

j∈ A(t )

t

∑ ∑

t ′ =1 j∈ A(t ′)

⎧ ( j) ⎫ min ⎨max( s j + ρ m )⎬ j ⎩ j∈J ⎭ ( j) s j + ρm ≤ d j , j∈J; j

(2)

si + ρim(i ) ≤ s j , (i, j)∈C;

(3)

rkjm( j ) (t − s j ) ≤ qk (t ) , k∈Kρ, t ≥ 0; rkjm( j ) (t ′ − s j ) ≤

∑

j∈J

(1)

(4)

t

σ ′ q ( t ), k∈K , t ≥ 0; ∑ k

t ′ =1

rkjm( j ) ≤ qk , k∈ Kν;

(5) (6)

m(j)∈ Mj, sj ≥ 0, j∈J. (7) Задача является NP–трудной при наличии хотя бы одного возобновляемого ресурса и | Mj | =1 для всех j∈J. Лекция 7. Задачи календарного планирования. Часть 2

-14-

Частные случаи модели Для | Mj | =1, j∈J, рассмотрим следующие частные случаи: 1. Kρ = Kσ = ∅, Kν ≠ ∅ — только невозобновляемые ресурсы. Тривиальный случай, проверяем хватает ли ресурсов и если да, то отбрасываем все ресурсные ограничения. 2. Kρ = Kν = ∅, Kσ ≠ ∅ — только складируемые ресурсы. Полиномиально разрешимый случай, алгоритм Гимади дает точное решение задачи. 3. Kσ = Kν = ∅, Kρ ≠ ∅ — только возобновляемые ресурсы. Наиболее трудный случай, применяем эвристические алгоритмы. Лекция 7. Задачи календарного планирования. Часть 2

-15-

Задача со складируемыми ресурсами Определение. Расписание S = {sj ≥ 0, j∈J} называют полудопустимым, если оно удовлетворяет условиям предшествования (3) и директивным срокам (2), но быть может не удовлетворяет ограничениям по ресурсам.

Упражнение 1. Полудопустимое расписание существует ⇔ наиболее ранние сроки выполнения работ Tp(x) удовлетворяют директивным срокам (2).

Лекция 7. Задачи календарного планирования. Часть 2

-16-

Определение. Полудопустимое расписание ST = { sTj ≥ 0, j∈J} для T ≥ TКр называется T–поздним, если sTj + ρj ≤ T, для всех j∈J и ни одно из значений sTj не может быть увеличено полудопустимости расписания.

без нарушения

этого условия или

Алгоритм вычислении T-позднего расписания аналогичен алгоритму вычисления наиболее поздних моментов, если перед началом вычислений положить

TП(y) = min {dj , T}, j=(x,y)∈J.

Лекция 7. Задачи календарного планирования. Часть 2

-17-

Теорема. Пусть T* — длина оптимального расписания. Тогда T*–позднее расписание является оптимальным. Доказательство: По определению T*–позднее расписание удовлетворяет всем ограничениям кроме, быть может, ресурсных ограничений (5). Ограничения (4)–(6) игнорируются, так как Kρ = Kν = ∅. Покажем, что ограничения (5) также выполняются. *

Пусть S — оптимальное решение и S

T∗

— T*–позднее расписание. Из опре-

деления T–позднего расписания следует, что

s∗j

T∗ ≤ sj ,

для всех j∈J. Так как

S* удовлетворяет (5), то есть в каждый момент времени ресурсов достаточно, то эти же ресурсы могут быть использованы и позже в силу их складируемости. Значит, для

T∗ Sj

тоже хватает ресурсов и (5) верно. Следовательно

T∗ Sj —

оптимальное расписание. Лекция 7. Задачи календарного планирования. Часть 2

-18-

Идея алгоритма Гимади

не допустимо

T

допустимо

t T1

T2

Лекция 7. Задачи календарного планирования. Часть 2

-19-

Алгоритм Гимади 1. Если наиболее ранние сроки выполнения работ Tp(x) не удовлетворяют директивным срокам, то STOP, задача не имеет решения. 2. Положить T1 = TКр. 3. Если T1–позднее расписание допустимо по ресурсам, то STOP, получено оптимальное решение задачи. 4. Положить T2 = max d j . j∈ J

5. Если T2–позднее расписание недопустимо по ресурсам, то STOP, задача не имеет решения. 6. Положить T := ⎡(T1 + T2)/2⎤. 7. Построить T–позднее расписание ST. 8. Если ST допустимо по ресурсам, то T2 = T, иначе T1= T. 9. Если T2 – T1 > 1, то вернуться на 6, иначе STOP, получено оптимальное решение S T2 . Лекция 7. Задачи календарного планирования. Часть 2

-20-

Задача с возобновляемыми ресурсами Будем предполагать, что qk (t ) = qk , и r jk (τ ) = r jk , j ∈ J , k ∈ K ρ , т.е. выделение и потребление ресурсов не зависит от времени. Для произвольного расписания S = {sj ≥ 0, j∈J} и момента времени t ≥ 0 определим три множества:

C(t) = { j∈J | sj + ρj < t} — завершенные работы A(t) = { j∈J | sj < t ≤ sj + ρj } — выполняемые работы D(t) = { j∈J \ (C(t) ∪ A(t)) | P(j) ⊆C(t),

ρ r + r ≤ q , k ∈ K } — работы, ко∑ ik jk k

i∈ A(t )

торые можно начать в момент времени t согласно условиям предшествования и ограничениям по ресурсам, P(j) — множество предшественников работы j. Лекция 7. Задачи календарного планирования. Часть 2

-21-

Идея алгоритма qk

D(t) C(t)

A(t) t Основной вопрос: как выбрать подмножество D′ ⊆ D(t) ? Лекция 7. Задачи календарного планирования. Часть 2

-22-

Приближенный алгоритм 1. t0 := 0, C(t0) := ∅, A(t0) := ∅, l := 0; 2. Пока | C(tl) ∪ A(tl) | < | J | выполнять 2.1. l := l + 1 2.2. tl := min {sj + ρj | j∈A(tl–1)} 2.3. Найти множества D(tl), A(tl), C(tl) 2.4. Положить Qk := qk −

ρ r , k ∈ K ∑ jk

j∈ A(tl )

2.5. Выбрать D′ ⊆ D(tl ) так, чтобы

ρ r ≤ Q для всех k∈K ∑ jk k

j∈D ′

2.6. Положить sj := tl для всех j∈D′ и A(tl):= A(tl) ∪ D′.

Лекция 7. Задачи календарного планирования. Часть 2

-23-

Выбор множества D′ Обозначим через R j =

∑

k∈K ρ

r jk

qk

, j∈D(tl) долю ресурсов, потребляемых

работой j. Тогда D′ целесообразно выбирать по решению задачи о рюкзаке: max

∑Rjxj

j∈D (tl )

при ограничениях

∑ r jk x j ≤ qk −

j∈D (tl )

ρ , r , k ∈ K ∑ ik

i∈ A(tl )

xj∈{0, 1}, j∈D(tl). Полагаем D′ = { j∈D(tl) | x∗j = 1 }, где x∗j –– оптимальное решение задачи. Упражнение 2. Показать, что любое правило выбора подмножества D′ , имеющее полиномиальную трудоемкость, не может гарантировать получение оптимального решения, если P ≠ NP. Лекция 7. Задачи календарного планирования. Часть 2

-24-

Задача коммивояжера Дана матрица (cij) попарных расстояний между городами, 1 ≤ i, j ≤ n. Найти контур минимальной длины, то есть цикл, проходящий через каждую вершину ровно один раз и имеющий минимальный вес.

Лекция 8. Задача коммивояжера. Часть 1

-1-

Трудоемкость полного перебора Фантастический компьютер: Куб со стороной 1 км. Оперативная память – количество ячеек размером в атом водорода. Все операции обмена проходят со скоростью света. Производительность – 1052 операций в секунду. Всего вариантов n! Для n=100 получаем 10152 варианта. Время счета 10100 секунд.

Лекция 8. Задача коммивояжера. Часть 1

-2-

Задачи маршрутизации

Найти маршрут минимальной длины

Лекция 8. Задача коммивояжера. Часть 1

-3-

Составление расписаний на одном станке Дано n деталей и один станок, сij — длительность переналадки станка для обработки j-й детали после i-й детали, pj – длительность обработки j-й детали. Найти последовательность обработки деталей, имеющую минимальную суммарную длительность. in

in–1

детали

…

i1

станок Лекция 8. Задача коммивояжера. Часть 1

-4-

Раскрой рулонного материала с рисунком Дано бесконечный рулон с рисунком в 1м и размеры n кусков 0 ≤ sj ≤ 1 — начало куска j, 0 ≤ fj ≤ 1 — конец куска j. Начало рулона и конец раскроя — f0. Найти последовательность отрезания кусков с минимальной длиной использованного материала если s j ≥ f i , ⎧s j − f i , cij = ⎨ ⎩1 + s j − f i , если s j < f i Задача коммивояжера для (n + 1)-го города.

f0

0

sj

1

fj

2

3

Лекция 8. Задача коммивояжера. Часть 1

-5-

Алгоритмическая сложность Теорема 1. Задача коммивояжера является NP-трудной даже в случае, когда (сij) — евклидовы расстояния на плоскости, то есть матрица симметрична и удовлетворяет неравенству треугольника сij ≤ сik + сkj , 1 ≤ i, j, k ≤ n. Теорема 2. Если существует приближенный полиномиальный алгоритм A и константа r, 1 ≤ r < ∞ такие, что для любого примера I задачи коммивояжера верно A(I) ≤ r OPT(I), то P = NP.

Лекция 8. Задача коммивояжера. Часть 1

-6-

Доказательство. Рассмотрим NP–полную задачу в гамильтоновом цикле: дан граф G = (V, E), правда ли, что он содержит гамильтонов цикл? Если условия теоремы верны и такие A и r существуют, то мы получим точный полиномиальный алгоритм решения задачи о гамильтоновом цикле. По заданному графу G = (V, E) построим пример задачи коммивояжера, положив

1, cij = ⎧⎨ ⎩nr ,

если (ij ) ∈ E , если (ij ) ∉ E ,

n =|V | .

Применим алгоритм A и посмотрим на ответ. Если получили цикл длины n, то граф G, очевидно, содержит гамильтонов цикл. Если длина цикла больше n, то она не меньше чем n⋅r + (n – 1), так как включает вес хотя бы одного из «тяжелых» ребер. Но в этом случае граф G не может иметь гамильтонов цикл, так как алгоритм A ошибается не более чем в r раз и ответ в задаче коммивояжера не должен превосходить n⋅r, если гамильтонов цикл есть. Итак, алгоритм A всегда дает правильный ответ для NP– полной задачи и имеет полиномиальную трудоемкость, то есть P = NP. Лекция 8. Задача коммивояжера. Часть 1

-7-

Алгоритмы локального спуска Пусть C — гамильтонов цикл. N(C) — окрестность полиномиальной мощности, т. е. число элементов окрестности полиномиально ограничено. Примеры окрестностей:

Окрестность 2 – замена a b

c

d

a

b

d

Выбираем в C два несмежных ребра и заменяем их другими так, чтобы снова получился гамильтонов цикл. Всего таких соседей n (n – 3) / 2. Аналогично получаем окрестности 3 – замена, 4 – замена и т.д. Лекция 8. Задача коммивояжера. Часть 1

-8-

Стандартный алгоритм локального спуска 1. Выбрать C0 — начальный цикл и вычислить его длину F(C0), i := 0. 2. Найти наилучшего соседа Ci+1 для цикла Ci : F(Ci+1) = min {F(C) | C ∈ N(Ci) }. 3. Если F(Ci+1) < F(Ci), то положить i := i + 1 и вернуться на 2, иначе STOP, Ci — локальный минимум.

Погрешность локальных оптимумов Теорема 3. Пусть A — алгоритм локального спуска и окрестность N(C) имеет полиномиальную мощность. Если существует константа r, 1 ≤ r < ∞ такая, что для любого примера I задачи коммивояжера справедливо неравенство

A(I) ≤ r⋅ OPT(I), то P = NP. Лекция 8. Задача коммивояжера. Часть 1

-9-

Доказательство. (Аналогично предыдущему) Рассмотрим задачу в гамильтоновом цикле и получим точный полиномиальный алгоритм ее решения. Снова по графу G = (V, E) строим матрицу 1, cij = ⎧⎨ ⎩nr ,

если (ij ) ∈ E , если (ij ) ∉ E ,

n =|V | .

Выбираем произвольный цикл C0. Его длина в худшем случае равна F(C0)=(nr)n. На каждом шаге локального спуска часть «тяжелых ребер» заменяется на легкие. При самом длинном спуске одно «тяжелое» ребро заменяется на одно легкое. Значит число шагов (возвращений на п.2) не превосходит n. Каждый шаг имеет полиномиальную трудоемкость, так как окрестность N(C) имеет полиномиальную мощность. Следовательно, алгоритм A является полиномиальным для данного класса примеров и, как следует из доказательства предыдущей теоремы, A — точный алгоритм. Значит P = NP. Лекция 8. Задача коммивояжера. Часть 1

-10-

Эвристические алгоритмы Алгоритм АБ «Иди в ближайший из непройденных городов»

1. Выбираем произвольный город i1. 2. Находим ближайший город к i1, обозначаем его i2 и помечаем город i1: ci1i2 = min ci1 j . j ≠ i1

3. На k-м шаге находим ближайший город к ik, обозначаем его ik+1 и помечаем город ik : cik ik +1 = min cik j . j ≠i1 ,...,ik

Теорема 4. Для любого r > 1 найдется пример I задачи коммивояжера такой, что AБ(I) ≥ r OPT(I)

даже при условии, что cij ≤ cik + ckj, для всех 1 ≤ i, j, k ≤ n. Лекция 8. Задача коммивояжера. Часть 1

-11-

Трудный пример для алгоритма АББ Имеется 15 городов, расположенных на окружности длиной 15 единиц, OPT(I) =15. Алгоритм АБ получает 27 единиц:

Лекция 8. Задача коммивояжера. Часть 1

-12-

Вероятностный аналог алгоритма АББ Алгоритм AБ(α), α ≥ 1. На k-м шаге формируем список кандидатов ⎫ ⎧ I k (α ) = ⎨ j ≠ i1 ,..., ik | cik j ≤ α min cik j ⎬ j ≠i1 ,...,ik ⎭ ⎩

Следующий город ik+1 выбирается из списка кандидатов случайным образом. При α = 1 получаем алгоритм «Иди в ближайший из непройденных городов».

Лекция 8. Задача коммивояжера. Часть 1

-13-

Итерационный алгоритм Алгоритм AБ(α) применяется несколько раз и для каждого решения используется стандартная процедура локального спуска. Лучший из найденных локальных оптимумов предъявляется в качестве ответа. 1. Полагаем F* := ∞ 2. For t := 1,…, T do 2.1. Применяем алгоритм AБ(α) и получаем цикл Ct. 2.2. Применяем алгоритм локального спуска с начальным решением Ct. ~ 2.3. Если полученный локальный минимум Ct меньше рекорда, т.е. ~ ~ F (Ct ) < F ∗, то меняем рекорд F ∗ := F (Ct ).

Увеличивая T и α, будем получать все более и более точные решения. Лекция 8. Задача коммивояжера. Часть 1

-14-

Алгоритмы с гарантированной точностью Остовное дерево. Дан связный граф G = (V, E), каждому ребру e∈E приписан вес we ≥ 0. Найти в G остовное дерево с минимальным суммарным весом ребер.

Алгоритм Круcкала Ak дает точное решение задачи и нижнюю оценку для задачи коммивояжера: Ak(I) ≤ OPT(I).

Лекция 8. Задача коммивояжера. Часть 1

-15-

Двойной обход остовного дерева

Обходим остовное дерево по правилу алгоритма «Поиск в глубину». Получаем маршрут, проходящий через все вершины. Листья посещаются один раз, но внутренние вершины посещаются несколько раз. Лекция 8. Задача коммивояжера. Часть 1

-16-

Перестройка остовного дерева

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

Лекция 8. Задача коммивояжера. Часть 1

-17-

Оценка точности алгоритма Теорема 5. Если матрица (cij) удовлетворяет неравенству треугольника, то ал-

горитм перестройки двойного обхода остовного дерева AST получает Гамильтонов цикл не более чем в 2 раза хуже оптимального для любого примера I задачи коммивояжера, то есть AST (I) ≤ 2 OPT(I). Доказательство. Для длины двойного обхода имеем

2 AK (I) ≤ 2 OPT(I). Пусть новое ребро e, не содержащееся в двойном обходе, заменяет цепочку ребер {e1, e2,…, ek}. Из неравенства треугольника следует, что k

we ≤ ∑ wei , то есть AST (I) ≤ 2 AK (I) ≤ 2 OPT(I). i =1

Лекция 8. Задача коммивояжера. Часть 1

-18-

Теорема 6. Полученная оценка точности

AST (I) ≤ 2 OPT(I) является неулучшаемой. Доказательство. Приведем пример семейства исходных данных задачи коммивояжера, на котором оценка 2 достигается асимптотически.

Рассмотрим следующий пример на плоскости с 3(n +1) вершинами:

ε

ε 1

1

ε

1–ε

1–ε

ε n Лекция 8. Задача коммивояжера. Часть 1

-19-

Для этого примера минимальное остовное дерево имеет вид:

Длина остовного дерева Ak = n + (n + 1)(1 – ε) + 2ε Алгоритм перестройки двойного обхода получит решение

Длина этого Гамильтонова цикла AST ≈ 2n + 2n (1 – ε) Лекция 8. Задача коммивояжера. Часть 1

-20-

Оптимальное решение задачи OPT(I) ≈ 2n +2.

Таким образом, при n → ∞ и ε → 0 получаем AST (I) / OPT(I) → 2

Лекция 8. Задача коммивояжера. Часть 1

-21-

Нижние оценки в задаче коммивояжера Примитивная оценка. Плата за выезд ai = min cij , i = 1,…, n. j ≠i

Плата за въезд b j = min (cij − ai ) j = 1,…, n. i≠ j

n

n

i =1

j =1

Теорема. OPT (cij ) ≥ ∑ ai + ∑ b j . Доказательство. Положим cij′ = cij − ai , 1 ≤ i, j ≤ n. Тогда n

OPT (cij ) = OPT (cij′ ) + ∑ ai . Аналогично, cij′′ = cij′ − b j , 1 ≤ i, j ≤ n, и i =1 n

OPT (cij ) = OPT (cij′′ ) + ∑ ai + i =1

n

n

n

j =1

i =1

j =1

∑ b j ≥ ∑ ai + ∑ b j . Лекция 9. Задача коммивояжера. Часть 2

-1-

Оценка линейного программирования 1, если из города i едем в город j. Введем переменные xij = ⎧⎨ ⎩0 в противном случае Математическая модель

n

n

min ∑ ∑ cij xij i =1 j =1

при ограничениях

n

∑ xij = 1,

j ∈ J,

∑ xij = 1,

i ∈ I,

i =1 n

j =1

∑ ∑ xij ≥ 1,

∀S ⊂ J , S ≠ ∅, (исключение подциклов)

i∈S j∈J \ S

xij∈{0,1}, i,j ∈J. Заменяя xij∈{0,1} на 0 ≤ xij ≤ 1, получаем задачу линейного программирования, которая дает нижнюю оценку для оптимума. Лекция 9. Задача коммивояжера. Часть 2

-2-

1–Деревья для симметричных матриц Хотим найти гамильтонов цикл минимального веса, т.е. найти − ровно n ребер, − которые покрывают все вершины, − имеют минимальный суммарный вес и − каждая вершина инцидентна ровно двум ребрам. Заменим последнее условие на следующее: − одна заданная вершина инцидентна ровно двум ребрам. Ослабили условия, значит, получим нижнюю оценку. Алгоритм построения 1-дерева

1. Удаляем заданную вершину и строим остовное дерево минимального веса (алгоритм Крускала) 2. Добавляем два ребра минимального веса, проходящих через заданную вершину, получаем 1-дерево. Лекция 9. Задача коммивояжера. Часть 2

-3-

Задача о назначениях Дано: n рабочих, n станков, cij — время выполнения работы i-рабочим на j-м станке. Найти расстановку рабочих по станкам с минимальным суммарным рабочим временем. 1, если рабочий i получил станок j . Переменные задачи: xij = ⎧⎨ ⎩0 в противном случае n

n

min ∑ ∑ cij xij

Математическая модель:

i =1 j =1

при ограничениях

n

∑ xij = 1,

1 ≤ j ≤ n,

∑ xij = 1,

1 ≤ i ≤ n,

i =1 n

j =1

xij∈{0,1}, 1≤ i,j ≤ n. Лекция 9. Задача коммивояжера. Часть 2

-4-

Сравнивая с задачей коммивояжера, замечаем, что оптимальное решение задачи о назначениях дает нижнюю оценку для задачи коммивояжера. Определение. Пусть ∆ = (∆1,…, ∆n) — некоторый вектор. Элемент cij называ-

ется ∆-минимальным, если cij – ∆j ≤ cik – ∆k для всех 1≤ k ≤ n. Теорема. Пусть для некоторого ∆ существует набор ∆-минимальных элементов (c1 j(1),…, cn j(n)) по одному в каждой строке и столбце. Тогда этот набор является оптимальным решением задачи. Доказательство. Решение (c1 j(1),…, cn j(n)) является допустимым и n

n

n

i =1

i =1

j =1

∑ cij (i ) = ∑ (cij (i) − ∆ j (i) ) + ∑ ∆ j .

В правой части равенства первая сумма является минимальной среди всех допустимых назначений, а вторая сумма является константой, то есть полученное решение является оптимальным. Лекция 9. Задача коммивояжера. Часть 2

-5-

Определение. Для вектора ∆ выделим в каждой строке по одному ∆-минимальному элементу и назовем его ∆-основой. Другие ∆-минимальные элементы будем называть альтернативными ∆-основами. Число столбцов матрицы cij без ∆-основ назовем дефектом. Общая идея алгоритма

Начинаем с ∆ ≡ 0. На каждом этапе алгоритма дефект уменьшается на 1, т.е. не более чем за n этапов найдем оптимальное решение задачи. Описание одного этапа

1. Выберем столбец без ∆-основы и обозначим его S1.

Лекция 9. Задача коммивояжера. Часть 2

-6-

2. Увеличить ∆S1 на максимальное δ так, чтобы все ∆-минимальные элементы остались ∆-минимальными (возможно δ = 0 ). Получим для некоторой строки i1 новый ∆-минимальный элемент ci1S1 , назовем его альтернативной основой для строки i1. S1

i1 Лекция 9. Задача коммивояжера. Часть 2

-7-

3. Для строки i1 столбец j(i1) с ∆-основой пометим меткой S2. S2

S1

i1 4. Увеличим ∆S1 и ∆S 2 на максимальное δ так, чтобы все ∆-основы остались ∆-минимальными элементами.

Лекция 9. Задача коммивояжера. Часть 2

-8-

Найдем новую альтернативную основу в одном из столбцов S1 или S2. Пусть она оказалась в строке i2. Пометим столбец j(i2) меткой S3 и будем продолжать этот процесс до тех пор пока не встретим столбец с двумя или более основами. S3

S2

S1 i2

i1

Лекция 9. Задача коммивояжера. Часть 2

-9-

5. Строим новый набор из ∆-основ. Заменой основы в строке назовем следующую операцию: альтернативная основа становится основой, а старая перестает быть основой. 5.1. Произведем замену основ в строке, где лежит последняя альтернативная основа (строка ik). Тогда в столбце j(ik) число основ уменьшится на 1, но останется положительным. S3

S2

S1 i2

i1 Лекция 9. Задача коммивояжера. Часть 2

-10-

В столбце, где появилась новая основа, возьмем старую основу и в этой строке тоже проведем замену основ и т.д. до тех пор, пока не доберемся до столбца S1. В итоге, столбец S1 получит основу, а число основ в столбце j(ik) уменьшится на 1. S3

S2

S1 i2

i1

Лекция 9. Задача коммивояжера. Часть 2

-11-

Метод ветвей и границ В основе метода лежит принцип «разделяй и властвуй». Пусть D — множество допустимых решений задачи min {f(x) | x∈D}, и для любого подмножества d ⊆ D умеем вычислять: LB(d) — нижнюю оценку для минимума f(x), x∈d, UB(d) — верхнюю оценку для минимума f(x), x∈d, т. е. LB(d) ≤ min {f(x) | x∈d} ≤ UB(d), для любого d ⊆ D.

Лекция 9. Задача коммивояжера. Часть 2

-12-

Основная идея Пусть x* — текущий рекорд и сначала f(x*) = UB(D). Вычисляем LB(D) и, если LB(D) = UB(D), то STOP, x* — оптимальное решение задачи. В противном случае разбиваем D на подмножества D = d1 ∪ …. ∪ dk. Для каждого подмножества вычисляем UB(di), LB(di), i = 1,…, k. Если f(x*) > UB(di), то меняем рекорд. Если LB(di) ≥ f(x*), то выбрасываем di, иначе дробим di на подмножества.

d1

d2

Так как D — конечное множество, то процесс конечен и дает точное решение задачи.

d3 D

Лекция 9. Задача коммивояжера. Часть 2

-13-

Описание метода На каждом шаге имеется − рекорд x*; − просмотренная часть P ⊂ D, для которой f(x) ≥ f(x*), x∈P; − разбиение множества D \ P на подмножества di1 , di2 ,..., dik . Шаг состоит в следующем.

1. Выбрать элемент разбиения, например, dik ; 2. Вычислить UB(dik ). Если f ( x∗ ) > UB(dik ), то сменить рекорд x*. 3. Вычислить LB (dik ).

Лекция 9. Задача коммивояжера. Часть 2

-14-

3.1. Если LB (dik ) ≥ f ( x∗ ), то добавить dik к P и перейти к следующему шагу. 3.2. Если LB (d ik ) ≤ f ( x ∗ ), но в множестве dik удалось найти наилучший x: элемент ~ f (~ x ) = min{ f ( x) | x ∈ d ik }, то добавить dik к P; если x. f ( x∗ ) > f ( ~ x ), то положить x∗ := ~ x найти не удалось, то разбиваем dik 3.3. Если LB (d ik ) ≤ f ( x ∗ ), но элемент ~

на подмножества dik = dik +1 ∪ ... ∪ dik +m и переходим к следующему шагу, имея новое разбиение для D \ P.

Лекция 9. Задача коммивояжера. Часть 2

-15-

Метод В&Г для задачи коммивояжера Разбиение множества D представляется в виде бинарного дерева.

D

Каждой вершине дерева соответствует частичный тур и список запретов.

{1,5} d1

Например, вершине d6 соответствует частичный тур 1,5 и запреты {4,3} на выход из города 5.

{1,5,4} d3

5 4

{1,5,3} d5

d2

d4 3 d6

Лекция 9. Задача коммивояжера. Часть 2

-16-

Метод В&Г для задачи коммивояжера Примитивная нижняя оценка для вершины дерева, например, d6: 5

LB (d 6 ) = c15 + ∑ ai + i =2

с15

5

∑bj.

j =2

Задача о назначениях: 5

LB (d 6 ) = c15 + ∑ cij (i ) , при c53 = c54 = +∞. i =2

с53 с54

Верхняя оценка — алгоритм «Иди в ближайший».

Лекция 9. Задача коммивояжера. Часть 2

-17-

Выбор переменной для ветвления Основная идея — угадать оптимальное решение на подмножестве dik и ветвиться по дугам этого тура:

d ik

• для частичного тура i1,…, ik выбираем минимальный элемент в строке ik матрицы cij′′ = cij − ai − b j , j ≠ i1 ,..., ik • для частичного тура i1,…, ik строим верхнюю оценку и ветвимся по дуге (i1,…, ik+1). • для частичного тура i1,…, ik решаем задачу о назначениях и ветвимся вдоль цикла, проходящего через вершину ik.

Лекция 9. Задача коммивояжера. Часть 2

-18-

Выбор подмножества из разбиения D \ P Две основные схемы: • многосторонняя схема ветвления, когда выбирается подмножество d′ такое, что LB(d′ ) = min {LB(di) | i = i1,…, ik}. Среди элементов разбиения D \ P = d i1 ∪ ...d ik выбирается подмножество с наименьшей нижней границей. • односторонняя схема ветвления, когда всегда выбираем последний элемент d ′ = d ik . Первая схема требует много оперативной памяти, но в среднем просматривает меньше вершин, чем вторая. Возможна комбинация этих схем: сначала первая, пока хватает памяти, затем вторая. Лекция 9. Задача коммивояжера. Часть 2

-19-

Влияние основных элементов на трудоемкость Верхняя оценка UB Нижняя оценка LB Схема ветвления и выбор переменной для ветвления f(x*) OPT H 1 2 3 ……

Итерации H= min LB(di) i1,…,ik

Лекция 9. Задача коммивояжера. Часть 2

-20-

Задача коммивояжера в Интернет • TSPBIB Home Page http://www.ing.unlp.edu.ar/cetad/mos/TSPBIB_home.html •

The Hamiltonian Page: Hamiltonian cycle and path problems, their generalizations and variations

http://www.ing.unlp.edu.ar/cetad/mos/Hamilton.html • Fractal Instances of the Traveling Salesman Problem http://www.ing.unlp.edu.ar/cetad/mos/FRACTAL_TSP_home.html • DIMACS: The Traveling Salesman Problem http://www.research.att.com/~dsj/chtsp/

Лекция 9. Задача коммивояжера. Часть 2

-21-

Задача маршрутизации Дано: множество клиентов J = {2, 3, …, n}, j = 1 — гараж, множество грузовиков K = {1,…, m} Qk — грузоподъемность k-го грузовика qj — вес груза для j-го клиента сij — расстояние между клиентами i и j. Найти: набор циклов, начинающихся и заканчивающихся в гараже j = 1 (по одному циклу на транспортное средство) такой, что суммарная длина циклов была бы минимальной и позволила бы обслужить всех клиентов данным набором транспортных средств.

Лекция 9. Задача коммивояжера. Часть 2

-22-

Математическая модель Переменные задачи

xijk =

yik =

1, если транспорт k посещает клиента j сразу после клиента i, 0 в противном случае 1, если транспорт k посещает клиента i, 0 в противном случае

Лекция 9. Задача коммивояжера. Часть 2

-23-

Модель min

∑ cij ∑ xijk

ij∈J

k ∈K

1, i = 2,..., n ⎧ ∑ yik = ⎨⎩m, i = 1 k ∈K

при ограничениях

∑ yik qi ≤ Qk ,

k∈K

i∈J

∑ xijk = ∑ x jik = yik , j

i ∈ J,k ∈ K

j

∑ xijk ≤ | S | −1, для всех S ⊆ {2,…, n},

k∈K

ij∈S

yik∈{0,1}, xijk∈{0,1}, i,j ∈ J, k∈K. Лекция 9. Задача коммивояжера. Часть 2

-24-

Возможные обобщения модели 1. Каждый клиент имеет «временное окно», в течение которого транспортное средство должно его посетить. 2. Клиенты могут не только получать продукцию, но и отправлять ее в гараж. 3. Обслуживание клиентов происходит не мгновенно, а в течение определенного времени: разгрузка, загрузка, оформление документов и т.п. 4. Транспортное средство может несколько раз вернуться в гараж (пройти несколько циклов). 5. Транспортное средство имеет временное окно (рабочий день водителя) для обслуживания клиентов.

Лекция 9. Задача коммивояжера. Часть 2

-25-

Целевые функции •

Суммарное расстояние или расход бензина (каждое транспортное средство имеет свой расход на 100 км).

•

Зарплата водителей и эксплуатационные расходы на транспортные средства.

•

Оптимизация парка транспортных средств (расширить или сузить, заменить тяжелые на легкие или наоборот, …).

•

Оптимальное размещение гаражей, их количество и вместимость.

Системы поддержки решений по оперативному управлению транспортными средствами, замена водителей, форс-мажорные обстоятельства, изменения потребностей клиентов,….

Лекция 9. Задача коммивояжера. Часть 2

-26-

Задачи о покрытии Дано: Сеть дорог и конечное множество пунктов размещения постов ГАИ. Каждый пункт может контролировать дорогу на заданном расстоянии от него. Известно множество опасных участков на дорогах. Найти: минимальное число постов для контроля всех опасных участков. Обозначения: I ={1,…, m} — множество всех возможных пунктов размещения постов ГАИ; J ={1,…, n} — множество опасных участков;

1, если из пункта i можно контролировать участок j aij = ⎧⎨ ⎩0 в противном случае Переменные задачи:

1, если в пункте i устанавливается пост ГАИ ⎧ xi = ⎨ ⎩0 в противном случае Лекция 10. Дискретные задачи размещения. Часть 1

-1-

Математическая модель min ∑ xi i∈I

при ограничениях:

∑ aij xi ≥ 1,

j∈J;

i∈I

xi∈{0,1} i∈I. Пусть ci ≥ 0 — стоимость создания поста в пункте i и число постов не превосходит p>0. Требуется минимизировать суммарную стоимость: min ∑ ci xi i∈I

при ограничениях:

∑ aij xi ≥ 1,

j∈J;

i∈I

∑ xi ≤ p;

i∈I

xi∈{0,1} i∈I. Лекция 10. Дискретные задачи размещения. Часть 1

-2-

Предположим, что имеется возможность открыть не более p постов и их не хватит для контроля всех опасных участков. Требуется при данном ограничении найти размещение постов для контроля максимального числа опасных участков. Переменные задачи: 1, если опасный участок j под контролем y j = ⎧⎨ ⎩0 в противном случае 1, если в пункте i устанавливается пост ГАИ xi = ⎧⎨ ⎩0 в противном случае

Лекция 10. Дискретные задачи размещения. Часть 1

-3-

Математическая модель max

∑ yj

j∈J

при ограничениях:

∑ aij xi ≥ y j ,

i∈I

j∈J;

∑ xi ≤ p;

i∈I

xi, yj∈{0,1}, i∈I, j∈J. Упражнение. Показать, что эта модель не эквивалентна нижеследующей модели: max

∑ ∑ aij xi

j∈J i∈I

при ограничениях:

∑ xi ≤ p;

i∈I

xi∈{0,1}, i∈I. Лекция 10. Дискретные задачи размещения. Часть 1

-4-

Если опасные участки опасны в разной степени и величина bj задает, например, число аварий на участке j за год, то задача предотвращения максимального числа аварий записывается следующим образом: max

∑bj y j

j∈J

при ограничениях:

∑ aij xi ≥ y j ,

j ∈ J,

i∈I

∑ xi ≤ p;

i∈I

xi, yj∈{0,1}, i∈I, j∈J.

Лекция 10. Дискретные задачи размещения. Часть 1

-5-

Метод Лагранжевых релаксаций Рассмотрим один из приближенных методов, основанный на Лагранжевых релаксациях. Рассмотрим оптимизационную задачу P:

νp = min cx Ax ≤ b Dx ≤ e x∈ {0, 1}n. Заносим первую группу ограничений в целевую функцию с множителями Лагранжа λ ≥ 0. Получаем Лагранжеву релаксацию LR(λ): при ограничениях

νλ = min {cx + λ( Ax – b)} при ограничениях

Dx ≤ e x∈ {0, 1}n. Лекция 10. Дискретные задачи размещения. Часть 1

-6-

Двойственная задача D к задаче P имеет вид:

ν D = max ν λ . λ ≥0

При любом λ ≥ 0 получаем νλ ≤ νD ≤ νP и в отличие от задач линейного программирования существуют примеры, где νD < νP. Величина νD зависит от разбиения множества ограничений на части Ax ≤ b и Dx ≤ e. Разбиение выбирается таким образом, чтобы вычисление νλ было простым, а число заносимых в целевую функцию ограничений было поменьше (меньше множителей Лагранжа).

Лекция 10. Дискретные задачи размещения. Часть 1

-7-

Теорема 1. Если пара (λ , x ) удовлетворяет условиям: 1. x — оптимальное решение задачи LR (λ ) , 2. Ax ≤ b, 3. λ ( Ax − b) = 0 , то решение x является оптимальным решением задачи P. Доказательство. Решение x является допустимым решением задачи P и значение целевой функции νP на этом решении cx совпадает с нижней оценкой ν λ = cx + λ ( Ax − b) = cx . Замечание. Выполнение условий 1 – 3 влечет νP = νD , что маловероятно для дискретных задач.

Лекция 10. Дискретные задачи размещения. Часть 1

-8-

Теорема 2. Если пара (λ , x ) удовлетворяет условиям:

1. x — оптимальное решение задачи LR (λ ) , 2. Ax ≤ b, то решение x является приближенным решением задачи P с погрешностью не более ∆ = λ (b − Ax ). Доказательство.

Для

оптимального

решения

x*

задачи

P

имеем

ν λ = cx + λ ( Ax − b) ≤ cx∗ ≤ cx , то есть cx − cx∗ ≤ λ (b − Ax ) = ∆. Определение. Вектор γ называется субградиентом функции νλ в точке λ , ес-

ли ν λ − ν λ ≤ (λ − λ )γ для всех λ. Подпространство {λ | (λ − λ )γ ≥ 0} содержит все вектора λ, для которых ν λ ≥ ν λ , то есть движение в направлении субградиента приводит к росту функции νλ. Лекция 10. Дискретные задачи размещения. Часть 1

-9-

Функция νλ может иметь несколько субградиентов в точке λ и любая выпуклая комбинация субградиентов

γ = α1γ 1 + α 2γ 2 + ... + α k γ k , αk ≥ 0,

∑α k

=1

тоже является субградиентом. Теорема 3. Пусть x — оптимальное решение задачи LR (λ ) . Тогда вектор

γ = Ax − b является субградиентом функции νλ в точке λ . Без доказательства.

Лекция 10. Дискретные задачи размещения. Часть 1

-10-

Алгоритм решения задачи P 1. Положить рекорд F* = +∞, i : = 0 и выбрать произвольно λ0 ≥ 0. 2. Найти оптимальное решение xi задачи LR(λi) i

3. Если Axi ≤ b и cxi = νλ , то STOP, xi –оптимальное решение задачи P 4. Если Axi ≤ b и F* > cxi, то сменить рекорд F* : = cxi. 5. Изменить множители Лагранжа λi +1 := max{0, λi + θ i ( Ax i − b)}, где θ i — длина шага в направлении субградиента. Если i < imax, то положить i : = i + 1 и вернуться на шаг 2. Длина шага θ i > 0 выбирается таким образом, чтобы θ i → 0 при i → ∞. Если

∞

i θ ∑ → ∞, то ν λi → ν D .

i =0

Лекция 10. Дискретные задачи размещения. Часть 1

-11-

Поведение величины νλ

ν

итерации

Лекция 10. Дискретные задачи размещения. Часть 1

-12-

Метод Лагранжевых релаксаций для задачи о покрытии Представим задачу о минимальном покрытии в следующем виде: min ∑ ci xi i∈I

при ограничениях

∑ aij zij ≥ 1,

j ∈ J,

i∈I

x i ≥ z ij , i ∈ I , j ∈ J , ∑ xi ≤ p, i∈I

zij , xi ∈ {0,1}, i ∈ I , j ∈ J , 1, если участок j контролируется постом i, где zij = ⎧⎨ ⎩0 в противном случае. Занесем первую группу ограничений с множителями Лагранжа λj ≥ 0, j∈J в целевую функцию. Лекция 10. Дискретные задачи размещения. Часть 1

-13-

Релаксированная задача Задача LR(λ): ⎧⎪ ⎫⎪ ν λ = min ∑ ⎨ci xi − ∑ λ j aij zij ⎬ + ∑ λ j ⎪⎭ j∈J i∈I ⎪ j∈J ⎩ при ограничениях x i ≥ z ij , i ∈ I , j ∈ J ,

∑ xi ≤ p,

i∈I

zij , xi ∈ {0,1}, i ∈ I , j ∈ J . Двойственная задача D:

ν D = max ν λ λ ≥0

Заметим, что при любом λ ≥ 0 задача LR(λ) легко решается точно и

ν P ≥ν D ≥νλ . Лекция 10. Дискретные задачи размещения. Часть 1

-14-

Алгоритм решения релаксированной задачи При фиксированном векторе λ ≥ 0 задача LR(λ) может быть представлена в следующем виде ν λ = min ∑ f i xi i∈I

∑ xi ≤ p,

при ограничениях

i∈I

xi ∈ {0,1}, i ∈ I ,

где f i = min{0, ci −

∑ λ j aij } ≤ 0 .

j∈J

Лекция 10. Дискретные задачи размещения. Часть 1

-15-

Упорядочим величины fi и возьмем p самых малых значений, то есть f i1 ≤ f i2 ≤ ... ≤ f i p ≤ ... ≤ f in .

Получаем 1, если l ≤ p, xi∗l = ⎧⎨ ⎩0 в противном случае, zi∗l j

⎧ xi∗ , если ai j = 1, l =⎨ l ⎩0 в противном случае.

Лекция 10. Дискретные задачи размещения. Часть 1

-16-

Поиск допустимого решения Пусть xi∗ , zij∗ — оптимальное решение задачи LR(λ) и для каждого j∈J

∑ aij zij∗ ≥ 1. Тогда решение

i∈I

xi∗ , zij∗ является допустимым решением задачи P.

В противном случае решение xi∗ , zij∗ не является допустимым и требуется корректировка решения. Пусть J 0 = { j ∈ J | ∑ aij xi∗ = 0} ≠ ∞. Определим окрестi∈I

ность 1–замена для произвольно решения x, удовлетворяющего N ( x) = { yi ∈ {0,1}, i ∈ I | ∑ yi = p и d ( xy ) = 2}

∑ xi = p.

i∈I

i∈I

d(xy) — расстояние Хэмминга (число несовпадающих координат). Введем вспомогательную функцию g ( x) = ∑ ci xi + Φ | J 0 |, i∈I

где Φ — большое число, штраф за нарушение ограничений. Лекция 10. Дискретные задачи размещения. Часть 1

-17-

Алгоритм корректировки 1. Положить xi =

xi∗ , i ∈ I , J 0

⎧⎪ ⎫⎪ = ⎨ j ∈ J | ∑ aij xi = 0⎬. ⎪⎩ ⎪⎭ i∈I

2. Если J0 = ∅, то STOP, получено допустимое решение задачи P. 3. Для решения x найти наилучшего соседа g ( y ) = min{g ( x′), x′ ∈ N ( x)}.

4. Если g(y) < g(x), то положить x : = y, пересчитать J0 и вернуться на шаг 2. 5. Если g(y) ≥ g(x), то STOP, допустимое решение задачи P найти не удалось.

Лекция 10. Дискретные задачи размещения. Часть 1

-18-

Алгоритм решения задачи о покрытии 1. Положить F ∗ = ∞, i := 0, λ0j = max ci , j ∈ J . 2. Найти оптимальное решение 3. Если

i∈I xi∗ , zij∗

релаксированной задачи LR(λi).

∗ ∗ a z ≥ 1 для всех j∈J и ν = c x i ∑ ij ij ∑ i i , то STOP, получено λ

i∈I

i∈I

оптимальное решение задачи. 4. Применить к решению xi∗ алгоритм корректировки, если F ∗ > g (x) , то F ∗ := g ( x) . 5. Изменить множители Лагранжа ⎧⎪ i ⎫⎪ i +1 i ∗ λ j := max ⎨0, λ j + θ ( ∑ aij zij − 1)⎬, j ∈ J . ⎪⎩ ⎪⎭ i∈I Если i < imax , то положить i :=i +1 и вернуться на шаг 2.

Лекция 10. Дискретные задачи размещения. Часть 1

-19-

Задача о p-центрах Предположим, что p постов ГАИ уже выбрано, и каждый опасный участок прикреплен к ближайшему посту. Обозначим через dij расстояние между участком j и постом i. Для выбранного набора постов S ⊂ I, | S | = p обозначим через D максимальное расстояние между постом и участками D = max min d ij . j∈J i∈S

Величина D связана с задержкой при выезде из поста i на участок j. Задача минимизации этой задержки называется задачей о p-центрах: max min d ij → j∈J i∈S

min

S ⊂ I ,|S |= p

.

Задача о p-центрах сводится к решению более m⋅n задач о минимальном покрытии. Лекция 10. Дискретные задачи размещения. Часть 1

не

-20-

Задача о многократных покрытиях Пусть величина D задает радиус ответственности поста, т. е. все участки на расстоянии D от поста находятся в зоне его ответственности. Зоны могут пересекаться. Пусть rj ≥ 1 — минимальное число постов, которые должны контролировать участок j, bj > 0 — среднее число аварий на участке j. Требуется выбрать p постов так, чтобы каждый участок контролировался не менее rj постами, и число предотвращенных аварий было бы максимальным: max

∑ b j ∑ aij xi

j∈J

i∈I

∑ xi ≤ p,

при условиях

i∈I

∑ aij xi ≥ r j , j ∈ J ,

i∈I

xi∈{0,1}, i∈I. Лекция 10. Дискретные задачи размещения. Часть 1

-21-

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

q > 0 — вероятность того, что пост не может откликнуться на вызов; pk = 1 – qk — вероятность того, что хотя бы один из k постов откликнется; pk – pk–1 = (1 – qk) – (1 – qk-1) = (1 – q) qk-1 — прирост вероятности при добавлении одного пункта. Переменные: 1, если участок j контролируется как минимум k постами, y jk = ⎧⎨ ⎩0 в противном случае.

Лекция 10. Дискретные задачи размещения. Часть 1

-22-

Математическая модель: max

∑

nj

k −1 b ( 1 − q ) q y jk ∑ j

j∈J k =1

nj

при ограничениях

∑ y jk ≤ ∑ aij xi ,

k =1

j∈ J,

i∈I

∑ xi ≤ p,

i∈I

xi , y jk ∈ {0,1},

где n j =

∑ aij ,

j ∈ J, i ∈ I .

i∈I

Замечание. В оптимальном решении

yjk ≤ yjk–1 для всех j∈J, 1< k ≤ nj. Лекция 10. Дискретные задачи размещения. Часть 1

-23-

Задача о размещении филиалов банка Дано: I = {1,…, m} — множество мест (районов, городов, округов), где можно открывать филиалы; J = {1,…, n} — множество потенциальных клиентов; fi ≥ 0 — расходы на открытие филиала i. cij ≥ 0 — доход от обслуживания клиента j филиалом i. p > 0 — максимальное число открываемых филиалов. Найти: подмножество S ⊂ I, | S | ≤ p, открываемых филиалов, которое дает максимум суммарной прибыли. Переменные задачи:

1, если открываем филиал i, xi = ⎧⎨ ⎩0 в противном случае 1, если клиент j обслуживается филиалом i, zij = ⎧⎨ ⎩0 в противном случае Лекция 11. Дискретные задачи размещения. Часть 2

-1-

Математическая модель ⎧⎪ ⎫⎪ max ⎨∑ ∑ cij zij − ∑ f i xi ⎬ ⎪⎩i∈I j∈J ⎪⎭ i∈I

при ограничениях:

∑ zij ≤ 1,

j∈J;

i∈I

xi ≥ zij , i ∈ I , j ∈ J ;

∑ xi ≤ p;

i∈I

zij, xi∈{0,1}, i∈I, j∈J

Лекция 11. Дискретные задачи размещения. Часть 2

-2-

Задача размещения производства Дано: I = {1,…, m} — множество районов (городов, областей), где можно открыть производство некоторой продукции; J = {1,…, n} — множество потребителей этой продукции (клиентов); fi ≥ 0 — затраты на организацию производства в пункте i. cij ≥ 0 — производственно–транспортные расходы на удовлетворение спроса j-го клиента i-м предприятием. p > 0 — максимально возможное число предприятий. Найти: подмножество предприятий S ⊂ I, | S | ≤ p, которое позволяет удовлетворить спрос всех клиентов с минимальными суммарными затратами.

Лекция 11. Дискретные задачи размещения. Часть 2

-3-

Переменные задачи:

1, если открываем предприятие i, xi = ⎧⎨ ⎩0 в противном случае 1, если предприятие i обслуживает клиента j , zij = ⎧⎨ ⎩0 в противном случае

Математическая модель

при ограничениях:

⎧⎪ ⎫⎪ min ⎨ ∑ ∑ cij zij + ∑ f i xi ⎬ ⎪⎩i∈I j∈J ⎪⎭ i∈I ∑ zij = 1, j ∈ J ; i∈I

xi ≥ zij , i ∈ I , j ∈ J ; ∑ xi ≤ p; i∈I

zij, xi∈{0,1}, i∈I, j∈J. Лекция 11. Дискретные задачи размещения. Часть 2

-4-

Выбор состава системы технических средств Дано: I = {1,…, m} — множество типов технических средств; J = {1,…, n} — множество видов работ, выполняемых этими техническими средствами; fi ≥ 0 — затраты на разработку и организацию производства технического средства i-го типа; gi ≥ 0 — затраты на производство одного средства i-го типа; cij ≥ 0 — затраты на выполнение одной работы j-го вида техническими средствами i-го типа; pij ≥ 1 — число технических средств i-го типа, необходимых для выполнения одной работы j-го вида; ϕj ≥ 1 — число работ j-го вида; p > 0 — максимально возможное число типов технических средств в составе системы. Лекция 11. Дискретные задачи размещения. Часть 2

-5-

Найти: Состав системы, который позволил бы выполнить все работы с минимальными суммарными затратами.

Переменные задачи:

1, если включаем в состав системы технические средства i-го типа ⎧ xi= ⎨ ⎩0 в противном случае vi ≥ 0, целые — число технических средств i-го типа в составе системы

1, если работы j-го вида выполняются техническими средствами i-го типа ⎧ zij= ⎨ ⎩0 в противном случае

Лекция 11. Дискретные задачи размещения. Часть 2

-6-

Математическая модель ⎧⎪ ⎛ ⎞⎫⎪ ⎜ min ⎨ ∑ f i xi + g i vi + ∑ ϕ j cij zij ⎟⎬ ⎟⎪ ⎪⎩i∈I ⎜⎝ j∈ j ⎠⎭

при ограничениях:

∑ zij = 1,

j∈J;

i∈I

vi =

∑ ϕ j pij zij ,

i ∈ I;

j∈ J

xi ≥ zij , i ∈ I , j ∈ J ;

∑ xi ≤ p;

i∈I

zij, xi∈{0,1}, i∈I, j∈J. Лекция 11. Дискретные задачи размещения. Часть 2

-7-

Двухуровневая задача размещения Дано: I = {1,…, m} — множество мест, где можно открыть производство некоторой продукции; J = {1,…, n} — множество потребителей этой продукции (клиентов); fi ≥ 0 — затраты на организацию производства в пункте i. cij ≥ 0 — производственно–транспортные расходы на удовлетворение спроса j-го клиента i-м предприятием. p > 0 — максимально возможное число предприятий. dij ≥ 0 — предпочтения j-го клиента на множестве предприятий:

min d ij — наиболее желаемый поставщик; i∈I

max d ij — наименее желаемый поставщик. i∈I

Лекция 11. Дискретные задачи размещения. Часть 2

-8-

Найти: Подмножество S ⊂ I, | S | ≤ p, открываемых предприятий, которые позволили бы удовлетворить спрос всех клиентов с минимальными суммарными затратами. Переменные задачи: 1, если открываем предприятие i, ⎧ xi = ⎨ ⎩0 в противном случае

1, если предприятие i обслуживает клиента j , zij = ⎧⎨ ⎩0 в противном случае

Лекция 11. Дискретные задачи размещения. Часть 2

-9-

Математическая модель ⎧⎪ ⎫⎪ ∗ min ⎨ ∑ ∑ cij zij + ∑ f i xi ⎬ ⎪⎩i∈I j∈J ⎪⎭ i∈I

при ограничениях:

∑ xi ≤ p;

i∈I

xi∈{0,1}, i∈I, где zij∗ — оптимальное решение задачи потребителя:

min

∑ ∑ dij zij

j∈J i∈I

при ограничениях:

∑ zij = 1,

j ∈ J;

i∈I

xi ≥ zij , i ∈ I , j ∈ J ;

zij ∈{0,1}, i∈I, j∈J. Лекция 11. Дискретные задачи размещения. Часть 2

-10-

Квадратичная задача о назначениях Дано: I = {1,…, n} — множество зданий, где могут размещаться цеха; J = {1,…, n} — множество производственных цехов; akl — расстояние между зданиями k, l ∈I ; bij — объем продукции, транспортируемый из цеха i в цех j, где i, j ∈J.

Найти: Размещение цехов по зданиям, при котором суммарный объем перевозок продукции был бы минимальным.

Лекция 11. Дискретные задачи размещения. Часть 2

-11-

Переменные задачи: 1, если цех i размещается в здании k , xik = ⎧⎨ ⎩0 в противном случае Математическая модель min ∑

∑ ∑ ∑ akl bij xik x jl

i∈J j∈J l∈I k ∈I

при ограничениях:

∑ xik

= 1, для всех k∈I;

∑ xik

= 1, для всех i∈J;

i∈J

k ∈I

xik ∈{0,1}, i∈J, k∈I.

Лекция 11. Дискретные задачи размещения. Часть 2

-12-

Генетический алгоритм для задач размещения Идея заимствована у живой природы и состоит в организации эволюции, целью которой является получение оптимального решения в сложной комбинаторной задаче: min{ f (S), S∈Sol}. Начальная популяция P = {S1, S2, … , Sk} — набор допустимых решений исходной задачи. Шаг эволюции: выбираем из популяции два решения, скрещиваем их, применяем мутацию, локальную перестройку и добавляем в популяцию, затем наихудшее решение удаляем из популяции.

Лекция 11. Дискретные задачи размещения. Часть 2

-13-

Общая схема алгоритма 1. Выбрать начальную популяцию P и запомнить рекорд F ∗ = min f ( Si ) . i =1,..., k

2. Пока не выполнен критерий остановки делать следующее: 2.1. Выбрать “родителей” S i1 , Si2 из популяции. 2.2. Применить к S i1 , Si2 оператор скрещивания и получить новое решение S ′. 2.3. Применить к S ′ оператор мутации и получить новое решение S ″. 2.4. Применить к S″ оператор локального улучшения и получить новое решение S ″′. 2.5. Если f (S ″′) < F*, то сменить рекорд F* := f (S ″′). 2.6. Добавить S ″′ к популяции и удалить из нее наихудшее решение. Лекция 11. Дискретные задачи размещения. Часть 2

-14-

Оператор скрещивания Пусть S1, S2 — два решения, задаваемые векторами X 1, X 2 ∈{0,1}n. Одноточечный оператор скрещивания: выбираем случайным образом координату 1 ≤ l ≤ n и новый вектор X ′ получает первые l координат от вектора X1, а остальные от вектора X 2. X 1 : (0 1 0 0 1 . . . 0 1 1 ) X 2 : (1 1 0 1 0 . . . 1 1 1 ) X ′ : (0 1 0 0 0 . . . 1 1 1 ) l Аналогично определяется двухточечный, трехточечный и т.д. операторы.

Равномерный оператор скрещивания: новое решение X ′ в каждой координате получает с вероятностью 0.5 значение одного из родителей. Лекция 11. Дискретные задачи размещения. Часть 2

-15-

Выбор родителей Турнирная селекция: из популяции P случайным образом выбирается некоторое подмножество P ′ ⊆ P и родителем назначается наилучшее решение в P ′: Si = min f ( S ) . S ∈P ′

Пропорциональная селекция: из популяции P случайным образом выбираются два родителя. Для решения Si вероятность быть выбранным обратно пропорциональна значению целевой функции f (Si). Варианты: Лучший в популяции + случайно выбранный. Случайно выбранный + наиболее удаленный от него и др.

Лекция 11. Дискретные задачи размещения. Часть 2

-16-

Оператор мутации Вероятностный оператор мутации случайным образом вносит изменения в допустимое решение задачи. Например, с малой вероятностью q < 1 в каждой n

координате значение Xi∈{0,1} заменяется на противоположное 1 – Xi. Если в решении требуется сохранить ∑ xi = p, то случайным образом выбирается i∈I

координата i1 такая, что X i1 = 1 и координата i2 такая, что X i2 = 0 и производится замена X i1 := 0, X i2 := 1. X ′ = (0 1 0 1 0 . . . 0 1 1 ) X ″ = (1 1 0 0 0 . . . 0 1 1 ) i1 i2

Лекция 11. Дискретные задачи размещения. Часть 2

-17-

Локальное улучшение Для решения S обозначим через N(S) его окрестность, например, множество всех решений S ′, находящихся от S на расстоянии не более 2 (3, 4, 5…) Алгоритм локального спуска

1. Положить S := S ″; 2. Найти в окрестности решения S наилучшего соседа S f ( S ) = min{ f ( Sˆ ), Sˆ ∈ N ( S )}; f ( S ) < f ( S ), то положить S := S и вернуться на шаг 2, 3. Если иначе STOP, получен локальный минимум.

Лекция 11. Дискретные задачи размещения. Часть 2

-18-

Выбор состава системы при многоэтапном процессе выполнения работ

1. Работы из множества J = {1,…, n} выполняются не все сразу, а по частям: сначала J1 ⊂ J, затем J2 ⊂ J и т.д. Множество работ J разбито на непересекающиеся подмножества J = U ( J l , l = 1,..., L). Технические средства после выполнения работ первого этапа J1, могут использоваться на втором этапе для работ из J2 и т.д.

2. Имеется начальный состав системы vi0 ≥ 0, i ∈ I , то есть система уже существует и требуется ее пополнить, чтобы выполнить все работы на каждом этапе и суммарные затраты были бы минимальными.

Лекция 11. Дискретные задачи размещения. Часть 2

-19-

Математическая модель ⎧⎪ ⎛ ⎞⎫⎪ min ⎨∑ ⎜ f i xi + g i vi + ∑ ϕ j cij zij ⎟⎬ ⎟⎪ ⎪⎩i∈I ⎜⎝ j∈J ⎠⎭

при ограничениях

∑ zij = 1,

j ∈ J;

i∈I

∑ϕ j pij zij ≤ vi0 + vi ,

i ∈ I , l = 1,..., L;

j∈J l

xi ≥ zij , i ∈ I , j ∈ J ; ∑ xi ≤ p; i∈I

xi , zij ∈{0,1}, vi ≥ 0, целые, i∈I, j∈J.

Лекция 11. Дискретные задачи размещения. Часть 2

-20-

Задача долгосрочного планирования развития системы Задан плановый период T = {1,…, T} и для каждого года t∈T известно множество работ Jt, подлежащих выполнению в этом году в объемах ϕjt > 0. Каждое техническое средство i∈I имеет срок службы ρi ≥ 0 и максимальный объем производства Vit ≥ 0 в году t∈T. Начальный состав системы содержит технические средства разного года выпуска, и величины vit0 ≥ 0 задают число технических средств i-го типа годных к эксплуатации в год t∈T. Требуется найти вариант пополнения системы, при котором гарантируется выполнение всех работ в каждом году планового периода и суммарные затраты были бы минимальными. Лекция 11. Дискретные задачи размещения. Часть 2

-21-

Математическая модель ⎫⎪ ⎧⎪ f x + g it vit + ∑ ϕ j cij zij ⎬ min ∑ t −1 ∑ ⎨ it it ⎪⎭ t∈T (1 + χ ) i∈I ⎪ j∈ J t ⎩ 1

∑ zij = 1,

при ограничениях

i∈I

∑

ϕ jt pij zij ≤ vit0

+

j∈J t

j ∈ Jt , t ∈T ; t

∑ viτ ,

i ∈ I , t ∈T ;

τ =t − ρi +1

0 ≤ vit ≤ Vit max xiτ , i ∈ I , t ∈ T ; τ ≤t

zij ≤ max xiτ , i ∈ I , t ∈ T ; τ ≤t ( j )

xit, zij ∈{0,1}, vit ≥ 0, целые, i∈I, j∈Jt, t∈T. Лекция 11. Дискретные задачи размещения. Часть 2

-22-

Введение в теорию расписаний Рассматриваются два множества: M = {M1, M2,…, Mm} — машины (станки, процессоры, бригады, …) J = {J1, J2,…, Jn}

— работы (задания, пакеты задач, …)

Расписание — указание, на каких машинах и в какое время должны выполняться работы. В каждый момент времени каждая машина выполняет не более одной работы, и каждая работа выполняется на одной машине или не выполняется вовсе.

Лекция 12. Теория расписаний. Часть 1

-1-

Два типа диаграмм Гантта Одно решение, представленное на двух диаграммах

M3

J3

J2

M2

J2

J4

M1

J1

M2

J4 J3 J2 J3

J1

M3 M2

M1 M3

M1 t

t

Лекция 12. Теория расписаний. Часть 1

-2-

Характеристики работ Работы состоят из операций: J i = {Oi1 , Oi2 ,..., Oin } i Операция Oi j требует pij времени и может выполняться на одной из машин множества µij ⊆ {M1,…, Mm}. Если | µij | = 1, ∀ i j, то получаем модель с предписаниями. Если | µij | = m, ∀ i j, то получаем модель с параллельными машинами. Для работы Ji известны:

ri ≥ 0 — время появления первой операции Oi1 di ≥ 0 — директивное время окончания последней операции Oin

i

wi ≥ 0 — важность (вес, ценность) работы Ji Лекция 12. Теория расписаний. Часть 1

-3-

Классификация задач теории расписаний Краткая запись задачи α | β | γ

α — характеристики машин; β — характеристики работ; γ — целевая функция задачи; Варианты для β : β1 = pmtn (preemption) разрешаются прерывания; β2 = prec (precedence relations) условия предшествования на множестве работ (цепи, деревья, сети); β3 = ri — время поступления на обслуживание

β4 ∈ {pij =1; pij ∈{0,1}; pij = pij(t), …} — уточнения для времени выполнения операций. β5 = di — директивные сроки окончания работ;

β6 = p-batching (s-batching) — работы разбиваются на группы, и в каждой группе берется максимум (сумма) времён выполнения работ; Лекция 12. Теория расписаний. Часть 1

-4-

Характеристики машин Поле α состоит из двух частей α = α1 α2 :

α1 — характеристики машин, α2 — число машин. Если α1∈{∅, P, Q, R}, то ni = 1 ∀ Ji, то есть каждая работа состоит ровно из одной операции.

α1 = ∅ — для каждой работы задана машина для ее выполнения, α1 = P — машины параллельны и одинаковы pij = pi, α1 = Q — машины параллельны, но различаются скоростями pij = pi / sj , α1 = R — машины параллельны, длительности выполнения работ произвольны, но pij = pi / sij .

Лекция 12. Теория расписаний. Часть 1

-5-

Если α1∈{G, X, J, F, O}, то ni ≥ 1, то есть у каждой работы может быть несколько операций.

α1 = J (job shop, рабочий цех) — у каждой операции своя машина | µij | = 1 и линейный порядок выполнения операций Oi1 → Oi2 → ... → Oin . i

α1 = F (flow shop, потоковая линия) — машины упорядочены M1, M2,…, Mm и каждая работа проходит все машины в этом порядке, ni = m и µij = Mj, ∀i. α1 = O (open shop, открытая линия) — каждая работа состоит из m операций (ni = m), но µij = { M1,…, Mm } и на множестве операций нет условий предшествования,

α1 = X (mixed shop, смешанный цикл) — смесь J и O, α1 = G (general case) — произвольный порядок предшествования на операциях (как в календарном планировании). Лекция 12. Теория расписаний. Часть 1

-6-

Целевые функции Обозначим через ci — время окончания работы Ji. Рассматриваются два типа минимизируемых целевых функций:

f (c) = max f i (ci ), i

n

f (c) = ∑ f i (ci ). i =1

Примеры целевых функций: Cmax = max ci — время окончания всех работ; i =1,...,n

Lmax = max (ci − d i ) — запаздывание относительно директивных сроков; i =1,...,n

Dmax = max | ci − d i | — отклонение от директивных сроков; i =1,...,n

Fmax = max (max{0, d i − ci }) — опережение директивных сроков; i =1,...,n

n

∑ wi ci

— взвешенная сумма окончания работ.

i =1

Лекция 12. Теория расписаний. Часть 1

-7-

Примеры задач теории расписаний Пример 1. P | prec, pi = 1 | Cmax

Задача поиска расписания с минимальным временем окончания всех работ на m параллельных машинах с длительностями работ pi = 1 и условиями предшествования, то есть предполагается известным ориентированный граф без циклов, вершинами которого являются работы, а дуги задают частичный порядок выполнения работ. Если n = 7, m = 2 и условия предшествования заданы графом: 2 1

5

4 3

6

7

то одно из допустимых решений имеет вид M2

2

4

M1 1

3

5

6

7

t Лекция 12. Теория расписаний. Часть 1

-8-

Пример 2. 1 | ri, pmtn | Lmax

Задача на одной машине с возможностью прерывания работ, директивными сроками окончания работ и произвольными временами появления работы. Требуется найти расписание {ci }in=1, минимизирующее максимальное запаздывание, то есть Lmax = max (ci − d i ) → min i =1,...,n

Для n =4 и i

Одно из допустимых решений имеет вид:

1

2

3

4

pi 2 ri 1

1

2

2

2

2

7

di 2

3

4

8

J1

M1 0

1

J2 3

J3 4

J4 6

7

9

Lmax = max {3 – 2; 4 – 3; 6 – 4; 9 – 8} = 2. Лекция 12. Теория расписаний. Часть 1

-9-

Пример 3. J 3 | pij = 1 | Cmax

Задача поиска расписания с минимальным временем окончания всех работ на трех машинах, образующих систему job shop — рабочий цех; длительности всех операций равны 1; у каждой работы свое множество операций; для каждой операции указана машина для ее выполнения. При n = 5, m = 3 и матрице Машины

J1 J2 J3 J4 J5

M1 M2 M3 M1 M3

M3 M3 M1 M3 M1

M2 – – M1 M2

M1 – – – M3

Одно из допустимых решений задачи имеет вид: M1

J1

M2

J2

M3

J5

0

J5 J3

1

2

J4

J3

J5

J1

J1

J4

3

4

J1

J4

J5

J2

5

6

t

Заметим, что машина M1 обязана работать не менее 6 единиц времени (2 для J1, 1 для J3, 2 для J4, 1 для J5), то есть нашли оптимум! Лекция 12. Теория расписаний. Часть 1

-10-

Пример 4. R3 | di | Dmax Задача поиска расписания, минимизирующего максимальное отклонение времен завершения работ от директивных сроков на трех параллельных машинах.

При n = 4, m = 3 и матрице длительностей выполнения работ pij Одно из допустимых решений задачи имеет вид M1

M2

M3

di

J1

10

6

1

5

M3

J2

5

20

3

5

M2

J3

9

30

1

6

J4

6

5

10

7

J3

J4 J1 J2

M1

5

1

6

11

t

Dmax = max {| 5 – 6 |; | 5 – 5 |; | 6 – 1 |; | 7 – 11 |} = 5 J1

J2

J3

J4

Лекция 12. Теория расписаний. Часть 1

-11-

Пример 5. 1 | s–batch |

∑ wi ci

Задача собрать работы в группы для обработки на одной машине так, чтобы минимизировать взвешенную сумму окончания всех работ. В каждой группе время окончания работ равно времени окончания последней работы в группе. Длительность выполнения всей группы работ равна сумме длительностей работ. При переходе от одной группы к другой машина требует переналадки τ (простой.) При n = 6, m = 1, τ = 1 и i pi wi

1 3 1

2 2 2

3 2 1

4 3 1

5 1 4

Одно из допустимых решений при разбиении на 3 группы: {J2}, { J3, J1, J5}, { J4, J6} имеет вид

6 1 4

τ 6

0

τ

J2 1

3

J3 4

J1

J5

τ 10 11

J4

J6 15

∑ wi ci = w2 ⋅ 3 + (w3 + w1 + w5 ) ⋅10 + (w4 + w6 ) ⋅15. i =1

Лекция 12. Теория расписаний. Часть 1

-12-

Задачи теории расписаний на одной машине Первые публикации появились в 1955 – 1956 гг (Jackson, Smith) Рассмотрим задачу с ri ≡ 0 и минимизируемой функцией f max (ci ) = max f i (ci ) , fi — монотонно возрастающая функция; прерываний i =1,..., n

работ разрешены, то есть 1 | pmtn | fmax Теорема 1. Среди оптимальных решений найдется решение без прерывания и простоя машины. Доказательство. Пусть в оптимальном решении работа J i0 выполнялась с прерыванием M1 J i0 J i0 t t t t t 1

2

3

4

Тогда изменим расписание, сохранив ci0 = t 4 , а работы из интервала [t2, t3] сдвинем влево к t1. Так как fi — монотонно возрастающая функция, то новое решение также будет оптимальным. Лекция 12. Теория расписаний. Часть 1

-13-

Задача 1 | prec | f mmaaxx Решение задается перестановкой П = (П1,…, Пn). Величина Пi задает номер работы, стоящей на i-м месте в перестановке П. Отношения предшествования задаются матрицей A: aij = 1, если работа Ji предшествует работе Jj и aij = 0 в противном случае. Идея алгоритма

Пусть N = {1,…, n} — множество всех работ и P ( N ) =

∑ pi .

Тогда в

i∈N

оптимальном решении последней работой будет работа, которая не имеет последователей и дает min f i ( P( N )) . i∈N

Лекция 12. Теория расписаний. Часть 1

-14-

Алгоритм Лаулера 1. For i := 1,…, n do n(i ) :=

n

∑ aij ; j =1

2. S := {1,…, N}; p :=

∑ pi ;

i∈S

3. For k := n,… , 1 do 3.1. Найти j∈S, для которого n(j) = 0 и f j ( p ) = min f i ( p ); i∈S

3.2. Положить S \ {j}; П k := j; p := p – pj ; 3.3. For i := 1,…, n do if aij =1 then n(i) := n(i) – 1. Трудоемкость алгоритма T ≈ O(n2).

Лекция 12. Теория расписаний. Часть 1

-15-

Теорема 2. Алгоритм Лаулера строит оптимальную перестановку П. Доказательство. Перенумеруем все работы так, чтобы П(i) = i, i = 1,…, n. Предположим, что П не является оптимальным решением, и пусть σ = (σ (1), …, σ (n)) — оптимальное решение. Найдем в нем первый номер c конца, где j = σ (i) ≠ i и σ (i +1) = i +1:

. . .

Ji

Jk

. . .

Jj

Ji+1

. . .

Jn

Блок (Jk,…, Jj)

Согласно алгоритму Лаулера, работа Ji может быть поставлена сразу перед Ji+1, так как у нее нет последователей в блоке (Jk,…, Jj). Но fi(p) ≤ fj(p), i

p = ∑l =1 pl . Значит, вставка i перед i +1 не увеличит целевую функцию и

новое решение также является оптимальным. Действуя аналогично, мы уберем все нарушения, переходя от одного оптимального решения к другому, и в итоге получим П. Лекция 12. Теория расписаний. Часть 1

-16-

Задача 1 | prec, pmtn, rii | f mmaaxx По-прежнему

f max = max f i (ci ) и i =1,...,n

fi(x) — монотонно возрастающие

функции. Времена прихода работ ri ≥ 0 могут не быть согласованными с частичным порядком, то есть aij = 1 (i → j), но rj < ri + pi. Поэтому сначала модифицируем величины ri. Занумеруем работы так, что i<j при (i → j) и упорядочим пары e=(i → j) по возрастанию j. Если всего пар |E| штук, то алгоритм пересчета величин ri может быть записан следующим образом. Алгоритм Modify ri

For e := 1,…, | E | do rj := max { rj, ri + pi };

Лекция 12. Теория расписаний. Часть 1

-17-

Разбиение на блоки Упорядочим работы так, чтобы r 1 ≤ r2 ≤ … ≤ rn . Этот порядок порождает допустимое расписание. Оно разбивается на блоки. Блок — это максимальное подмножество работ, которое выполняется без простоя машины:

J1

J2

B1

J3

J4

B2

J5

J6

...

B3

Лекция 12. Теория расписаний. Часть 1

-18-

Алгоритм построения блоков Алгоритм Blocks {1, 2, …, n}

1. i := 1, j := 1; 2. While i ≤ n do 2.1. t := ri; Bj := ∅; 2.2. While (ri ≤ t) & (i ≤ n) do 2.2.1. Bj := Bj ∪ {i}; 2.2.2. t := t + pi; 2.2.3. ci := t; 2.2.4. i := i + 1; 2.3 j:=j+1; Трудоемкость алгоритма T ≈ O(n). Лекция 12. Теория расписаний. Часть 1

-19-

Параметры блоков Для блока Bj определим: p( B j ) =

∑ pi

s j = min ri — начало блока; i∈B j

— длительность блока; tj = t(Bj) = sj + p(Bj) — окончание блока.

i∈B j

Теорема 3. Для задачи 1 | prec, pmtn, ri | f

max

существует оптимальное

расписание, в котором машина работает без простоев в интервалах [sj, tj], j = 1,…, K, где K — число блоков. Доказательство. Рассмотрим оптимальное расписание и предположим, что в интервале [sj, tj] машина простаивает с s по t:

sj

s

t

tj

Рассмотрим первый такой интервал (самый левый). Лекция 12. Теория расписаний. Часть 1

-20-

Покажем, что ∃ работа J i0 такая, что ri0 ≤ s, но ci0 > s. Предположим, что такой работы нет. Рассмотрим множество работ T, стартующих позже s: T = {Ji | si > s}. Для них r = min{ri | i ∈ T } > s,

так как нет работы J i0 . Но тогда алгоритм Blocks должен был дать простой машины в интервале [s, r]. Получили противоречие. Значит работа J i0 существует. Сдвинем ее начало в s и сократим интервал [s, t] на pi0 . Если t − s > pi0 , то повторяем процедуру до тех пор, пока не покроем весь интервал. Но [s, t] был первым интервалом. Аналогично поступим со вторым и т.д.

Лекция 12. Теория расписаний. Часть 1

-21-

Оптимальное расписание для блока ∗ Каждый блок можно рассматривать отдельно. Пусть f max ( B) — оптимальное ∗ ( B \ { j}) — оптимальное решение для B \ {j}. решение для блока B и f max ∗ ∗ Так как fi — монотонно неубывающие функции, то f max ( B ) ≥ f max ( B \ { j}) и ∗ ∗ f max ( B ) ≥ max f max ( B \ { j}) j∈ B

(*)

В блоке B одна из работ заканчивается последней. Обозначим ее через Jl. Она не имеет последователей в B и fl ( t(B) ) = min{ fj ( t(B) ) | j∈B и j не имеет последователей в B}. Очевидно, что ∗ ( B) ≥ f l (t ( B )) f max

(**)

Лекция 12. Теория расписаний. Часть 1

-22-

Удалим работу Jl из B и найдем оптимальное решение для этой подзадачи. Оно снова будет иметь блочную структуру. Простой машины в интервале [sj, tj] будет соответствовать времени выполнения работы Jl и ∗ ∗ ( B ) = max{ f max ( B \ {J l }), f l (t ( B ))}. f max

В силу неравенств (*) и (**) это значение будет оптимальным. Применяя алгоритм рекурсивно, получаем оптимальное решение задачи.

Лекция 12. Теория расписаний. Часть 1

-23-

Общая схема алгоритма 1 | prec, pmtn, rii | f mmaaxx 1. S := {1,…, n} ∗ := Decompose (S) 2. f max

Procedure Decompose (S) 1. If S = ∅ then return –∞ 2. If S = {i} then return fi (ri + pi) else 2.1. Call Blocks (S) 2.2. f := –∞ 2.3. For all blocks B do 2.3.1. Найти l: fl (t(B)) = min{ fj (t(B)) | j ∈B и j не имеет в B последователей}; 2.3.2. h := Decompose (B \ {Jl}) 2.3.3. f := max {f, h, fl (t(B))} 2.4. return f Лекция 12. Теория расписаний. Часть 1

-24-

Трудоемкость алгоритма T = O(n2) Число прерываний не более (n – 1), т.к. каждое прерывание дает разбиение на блоки. Если ri = 0 для всех i∈S, то получаем алгоритм Лаулера. Упражнение. Разработать точный полиномиальный алгоритм для задачи

1 | prec, pi = 1, ri | f max .

Следующая лекция состоится 14 мая 2005 г. Лекция 12. Теория расписаний. Часть 1

-25-

Задачи на параллельных машинах Задача P | pmtn | Cmax Имеется m одинаковых машин и n работ. Любая работа может выполняться на любой машине. Прерывания работ разрешены. Требуется найти расписание с минимальным временем завершения всех работ. Нижняя оценка ⎧⎪ 1 n ⎫⎪ LB = max ⎨ max pi ; pi ⎬ . ∑ m i =1 ⎪⎭ ⎪⎩i =1,..., n

Если найдем расписание с Cmax= LB, то получим оптимальное решение.

Лекция 13. Теория расписаний. Часть 2

-1-

Алгоритм: возьмем произвольный список работ и будем «загружать» машины последовательно: сначала первую машину в интервале времени [0, LB], «отрезая» часть последней работы, если она не вошла целиком и, перенося эту часть на следующую машину в интервале [0, LB] и т.д. Получим некоторое расписание. Пример:

M1

m = 3, n = 5 i 1 pi 4

2 5

3 3

4 5

5 4

M2 M3

1 2

2 3

4

4 5

t

LB = 7 Так как LB ≥ max pi , то в каждый момент времени работа выполняется не i =1,...,n

более чем на одной машине. Значит, полученное расписание является допустимым, и Cmax = LB, то есть получили оптимальное расписание. Лекция 13. Теория расписаний. Часть 2

-2-

Задача P | pmtn, rii | Lm maaxx Имеется m одинаковых машин и n работ. Для каждой работы заданы время поступления на обслуживание ri ≥ 0 и директивный срок окончания di ≥ ri. Требуется найти расписание с минимальной задержкой Lmax = max (ci − di ), где ci — время окончания работы i.

i =1,...,n

Для решения этой задачи сначала научимся отвечать на вопрос: ∃ ли расписание с Lmax ≤ L? А затем методом дихотомии найдем минимальное значение L, для которого такое расписание существует. Пусть L задано. Если расписание существует, то работа i выполняется в интервале [ri, ci] и ci – di ≤ L, то есть ci ≤ L + d i = d iL и можно считать, что работа i выполняется в интервале [ri , d iL ]. Для того, чтобы ответить на вопрос «∃ ли расписание с прерываниями, где каждая работа выполняется в своем временном окне», нам потребуется задача о потоке в сети, которая может быть решена симплекс–методом. Лекция 13. Теория расписаний. Часть 2

-3-

Задача о потоке в сети Задана сеть G = (V, E, s, t) с одним источником s и одним стоком t. Сеть G есть ориентированный ациклический граф. Каждой дуге (ij) ∈E приписан вес cij ≥ 0 — пропускная способность дуги. Определение. Потоком в сети G называется функция F : E → R на дугах, которая удовлетворяет условиям на пропускные способности 0 ≤ fij ≤ cij, (ij) ∈E и сохраняет поток в каждой внутренней вершине v∈V \ {s, t}:

∑ fij = ∑ f ji ,

i∈V (ij )∈E

i∈V ( ji )∈E

∀j ∈ V \ {s, t}.

s

j

Лекция 13. Теория расписаний. Часть 2

t

-4-

Легко проверить, что

∑ f si = ∑ f it .

i∈V ( si )∈E

i∈V (it )∈E

Определение. Величина M ( f ) =

∑ f si

называется мощностью потока.

i∈V ( si )∈E

Задача состоит в том, чтобы найти поток максимальной мощности. Заметим, что это задача линейного программирования. Множество допустимых решений задачи не пусто, т.к. решение fij = 0, ∀(ij)∈E, является допустимым решением задачи. Целевая функция ограничена сверху, следовательно, оптимальное решение существует. Покажем, как с помощью задачи о потоке в сети найти расписание, удовлетворяющее временным окнам. Лекция 13. Теория расписаний. Часть 2

-5-

Сольем два массива ri, d iL и упорядочим их значения t1 < t2 < … < tk, k ≤ 2n. Рассматриваем только различные значения r и d. Построим интервалы Ik = [tk, tk+1], длины Tk = tk+1– tk и рассмотрим сеть G = (V, E, s, t):

J1 p1

p2 J2

s

T1

I1 T2

T( J 2 )

pn

Jn

mT1 t

I2 mTK IK

Дуга (i, k) принадлежит E, если работа Ji может выполняться в интервале Ik, т.e. I k ⊆ [ri , d iL ] . Каждой дуге приписан вес, как показано на рисунке. Лекция 13. Теория расписаний. Часть 2

-6-

Решим задачу о максимальном потоке в этой сети. Получим max M(F). Сравним эту величину с

n

∑ pi . Если они равны, то искомое расписание существует,

i =1

если нет, то есть

∑ pi > M ( F ) , то такого расписания не существует.

Пусть имеет место равенство. Тогда сохранение потока в каждой вершине Ji дает: ∑ f ik = pi , ∀i = 1,..., n k

и величины fik определяют расписание работы Ji. Сохранение потока в вершине Ik:

∑ fik ≤ mTk ,

∀k = 1,..., K , гарантирует, что m

i

машин справятся со всеми работами в интервале Tk.

Лекция 13. Теория расписаний. Часть 2

-7-

Задача Q | pmtn | Cm maaxx Имеется m машин со скоростями s1 ≥ s2 ≥ … ≥ sm и n работ с трудоемкостью p1 ≥ p2 ≥ … ≥ pn. Время выполнения pij = pi / sj. Разрешаются прерывания. Найти расписание с минимальным временем выполнения всех работ. Сначала найдем нижнюю оценку на Cmax, затем построим расписание с Cmax =LB, то есть оптимальное! Положим Pi = p1 + p2 + … + pi, Sj = s1 + s2 + … + sj. Предполагаем, что n ≥ m, иначе выбрасываем (m – n) самых медленных машин. Если хотим выполнить все работы в интервале [0, T], то Pn ≤ SmT. Аналогично, Pj ≤ SjT, ∀j = 1,…, m – 1, так как Pj / Sj есть нижняя граница для выполнения работ j′ = 1,…, j. Таким образом, LB = max{ max Pj S j ; Pn S m } j =1,..., m −1

есть нижняя граница для Cmax. Лекция 13. Теория расписаний. Часть 2

-8-

Предположим, что Cmax = T и до момента T ни одна машина не простаивала. Тогда T = Pn / Sm . Если бы можно было выполнить работу сразу на всех машинах, то расписание легко построить:

M1 M2

Mm

1 1 1 1 1

2 2 2 2 2

P1/Sm

P2/Sm

n n n n n T

Но это расписание легко переделать так, чтобы работа не была одновременно на нескольких машинах. Лекция 13. Теория расписаний. Часть 2

-9-

Так как n ≥ m, то сдвинем работы по времени следующим образом:

M1

1

M2 ... ...

Mm

3

...

...

2

3

1

2

3

1

2

3

1

2

3

1

2

...

t T

Это оптимальное расписание, если pi = pj ∀ i j = 1,…, n . Если pi = p, то мы умеем строить оптимальное расписание и оно обладает тем свойством, что ни одна машина не простаивает до завершения всех работ. Лекция 13. Теория расписаний. Часть 2

-10-

Теперь рассмотрим общий случай разных pi. В нем работы с большими длительностями ставятся на самые быстрые машины до тех пор, пока их длительность не сократится настолько, что совпадет с длительностью других работ, образуя группу одинаковых работ, а группу мы умеем расписывать оптимально. Обозначим через pi(t) часть работы i, которая еще не выполнена к моменту t. Наш алгоритм будет двигаться по t и в некоторых моментах времени s останавливаться для переназначения работ по машинам.

Лекция 13. Теория расписаний. Часть 2

-11-

Алгоритм Level 1. t := 0 2. While ∃ работа с p(t) > 0 do 2.1. Assign (t) 2.2. t1 := min{s > t | ∃ работа завершающаяся в момент s} 2.3. t2 := min{s > t | ∃ ij, pi(t) > pj(t) и pi(s) = pj(s)} 2.4. t = min { t1, t2} 3. Восстановить расписание работ.

Процедура Assign (t) производит назначение работ по машинам.

Лекция 13. Теория расписаний. Часть 2

-12-

Процедура Assign 1. J := {j | pj(t)>0}. 2. M := {M1,…, Mm}. 3. Всем j∈J и Mi∈M присвоить статус «свободен». 4. While ∃ (свободные работы) и (свободные машины) do 4.1. Найти множество I ⊆ J всех работ c pi (t ) = max pk (t ) . k ∈J

4.2. k := min {| M |, | I |}. 4.3. Назначить работы из I на k самых быстрых машин из M для совместной обработки. 4.4. J := J \ I. 4.5. Исключить k самых быстрых машин из M.

Лекция 13. Теория расписаний. Часть 2

-13-

Пример Имеется 5 работ и 4 машины p1 p1(t)

p2 p3

p2(t)

В момент t1 p5 = p4(t1) и далее они выполняются вместе на машине 4.

p3(t)

p4 p5

t t1

M1

J1

M2

J2

M3

J3

M4

В момент 0 начали выполняться 4 работы.

t2

t3

t4

t5

J1 J2

J4

J4 J5 t1

В момент t2 p1(t2) = p2(t2) и далее они выполняются вместе на двух самых быстрых машинах.

t2

t t3

t4

t5 Лекция 13. Теория расписаний. Часть 2

-14-

Заметим, что кривая p1(t) всегда остается выше всех других, p2(t) не ниже

pi(t), i > 2 и т.д., т.е. p1(t) ≥ p2(t) ≥ … ≥ pn(t), ∀t ≥ 0, и процедура Assign (t) назначает работы на машины именно в этом порядке Теорема. Алгоритм Level строит оптимальное расписание. Доказательство. Достаточно убедится в том, что алгоритм закончит работу в момент

⎧ m −1 ⎫ t = LB = max ⎨max Pj S j ; Pn S m ⎬ . ⎩ j =1 ⎭ 1. Если к моменту завершения всех работ ни одна машина не простаивала, то t = Pn S m и решение оптимально.

Лекция 13. Теория расписаний. Часть 2

-15-

2. Пусть машины завершили свою работу в разное время. Тогда f1 ≥ f2 ≥… ≥ fm, fi — время остановки машины i, и хотя бы одно неравенство строгое, т.е. T = f1 = f2 = … = fj > fj+1 и j < m Но работы, заканчивающиеся в момент T, должны были начаться в t = 0, и тогда T = Pj S j . Убедимся в том, что все работы, заканчивающиеся в момент T, начали выполняться в t = 0. Предположим, что это не так, т.е. ∃ работа i, которая началась в момент ti > 0. Тогда в t = 0 начались другие работы: 1, 2, …, m и p1(0) ≥ p2(0) ≥ … ≥ pm(0) > pi(0). Все машины работали до t ≤ ti, а в момент ti мы получим p1(ti) = p2(ti) = … = pm(ti) = pi(0) и далее они выполнялись вместе, т.е. машины не простаивали. Это противоречит предположению. Лекция 13. Теория расписаний. Часть 2

-16-

Задача F || Cm maaxx Имеется n работ, каждая из которых должна пройти обработку последовательно на всех машинах M1, M2,…, Mm, т.е. каждая работа состоит из m операций и для всех работ порядок выполнения операций один и тот же. Требуется найти расписание выполнения работ за наименьшее время. Работы

M1

M2

...

M

Модель «Открытый цех» (Flow Shop)

Лекция 13. Теория расписаний. Часть 2

-17-

Теорема. Существует оптимальное расписание для задачи F || Cmax, обладающее следующими свойствами: 1. Последовательности выполнения работ на первой и второй машинах одинаковы. 2. Последовательности выполнения работ на последней и предпоследней машинах одинаковы. Доказательство. 1. Пусть утверждение не верно и среди всех оптимальных расписаний выберем такое, что последовательности на M1 и M2 совпадают для первых k работ, k < n и k — максимально. M1 M2

i

l

...

j

h i

j

Обозначим эту k-ю работу через Ji. На первой машине за ней идет Jl. На второй машине — Jj. Если на первой машине поставим Jj между Ji и Jl, то длина расписания не изменится, но k увеличится. Получили противоречие. Второе утверждение доказывается аналогично. Лекция 13. Теория расписаний. Часть 2

-18-

Следствие. При m ≤ 3 существует оптимальное решение задачи F || Cmax с одинаковым порядком выполнения работ на всех машинах. Контрпример для m = 4. n = 2 и длительности операций для J1 и J2 задаются векторами: (1, 100, 100, 1) и (100, 1, 1, 100). Если порядки выполнения работ на всех машинах одинаковы, то их всего два: (J1, J2) или (J2, J1). Тогда в обоих случаях Cmax = 302. M1 1 M2 M3 M4

2 1

1 1

M1 M2 M3 M4

2 2 1

100 101

2

1 2

2

201

302

t

1 2

1 2

100 101

1 201

t

302

Лекция 13. Теория расписаний. Часть 2

-19-

Оптимальное решение Cmax = 204 M1 1 M2 M3 M4

2 1

2 2

1

101

103

1 2

1 204

t

Порядок выполнения работ на M2 и M3 разный. Если при m > 3 искать решение в виде одной перестановки, то отношение перестановочного оптимума и глобального оптимума может достигать величины 0,5 m .

Лекция 13. Теория расписаний. Часть 2

-20-

Задача Джонсона F2 || Cm maaxx Пусть заданы перестановка Π, определяющая порядок выполнения работ на двух машинах. Соответствующее расписание представим в виде сетевого графика: . . . M1

Π1

Π2

Π3

M2

Π1

Π2

Π3

Πn

. . .

Πn

сток

Каждой вершине приписан вес равный длительности выполнения соответствующей операции. Заметим, что при заданной перестановке Π время окончания всех работ (Cmax) равно длине максимального пути из источника в сток. Этот путь на некоторой работе s переходит от M1 к M2. Пусть aj — время выполнения работы j на M1, bj — время выполнения работы j на M2. n ⎞ ⎛ s Тогда Cmax ( Π ) = max ⎜ ∑ a Пk + ∑ bΠk ⎟ . ⎟ 1≤ s ≤ n⎜⎝ k =1 ⎠ k =s Лекция 13. Теория расписаний. Часть 2

-21-

Теорема. Перестановка Π номер q такой, что

1. aj ≤ bj, j = 1,…, q

0

= (1, 2, … , n) оптимальна, если существует

и a1 ≤ a2 ≤ … ≤ aq;

2. aj ≥ bj, j = q + 1,…, n и bq +1 ≥ bq +2 ≥ … ≥ bn; или более наглядно

≥

≥

bq

an ≥

b2 …

≥

b1

aq +1 aq +2 … ≥

≥

a1 ≤ a2 ≤ … ≤ aq

bq +1 ≥ bq +2 ≥ … ≥ bn

Лекция 13. Теория расписаний. Часть 2

-22-

Доказательство. Пусть Π — произвольная перестановка и s

Cmax (Π , s ) = ∑ a Пk + k =1

n

∑ bΠ k .

Поскольку Cmax (Π ) = max Cmax (Π , s ), то s

k =s

достаточно показать, что для всякого s найдется номер r такой, что Cmax (Π 0 , s ) ≤ Cmax (Π , r ).

В случае s ≤ q выберем r так чтобы Πr∈{s, …, q} ⊂ {Πr , Πr +1,…, Πn}. Для этого достаточно в перестановке Π найти работу из {s, …, q} с наименьшей позицией. Эту работа обозначили через Πr. Тогда s −1

Cmax (Π , s ) = ∑ ak + a s + 0

k =1

q

n

k =s

k = q +1

∑ bk + ∑ bk = as + ∑ bk + ∑ min(ak , bk ), k∈s ,q

k∉s ,q

где s, q = {s,..., q}.

Лекция 13. Теория расписаний. Часть 2

-23-

Для перестановки Π величина Cmax (Π, r) представима в виде Cmax (Π , r ) = aΠ r +

∑ bk + ∑ ck ,

k∈s ,q

k∉s ,q

где ck ≥ min(ak , bk ) . Второе слагаемое содержит только величины bk, так как {s, …, q} ⊂ {Πr , Πr +1,…, Πn}. Из условия Πr∈{s, …, q} получаем aΠ r ≥ as откуда и следует нужное неравенство. В случае s > q выбираем r так, чтобы Πr∈{q +1, …, s} ⊂ {Π1,…, Πr }. Остальная часть доказательства проводится аналогично.

Лекция 13. Теория расписаний. Часть 2

-24-

Введение в матричные игры Предметом исследований в теории игр являются модели и методы принятия решений в ситуациях, где участвуют несколько сторон (игроков). Цели игроков различны, часто противоположны. Мы будем рассматривать только игры двух лиц с противоположными интересами. Игра состоит из последовательности ходов. Ходы бывают личные и случайные. (В шахматах все ходы личные. Рулетка содержит случайный ход). Результаты ходов оцениваются функцией выигрыша для каждого игрока. Если сумма выигрышей равна 0, то игра называется игрой с нулевой суммой (преферанс). Будем рассматривать только такие игры. Стратегией называется набор правил, определяющих поведение игрока, т.е. выбор хода. Оптимальной стратегией называют такую стратегию, при которой достигается максимальный ожидаемый средний выигрыш при многократном повторении игры. Лекция 14. Матричные игры

-1-

Матричные игры — это игры, где два игрока играют в игру с нулевой суммой, имея конечное число «чистых» стратегий: {1,…, m} и {1,…, n} и ∀ (ij) задан платеж aij второго игрока первому. Матрица (aij) задает выигрыш первого игрока и проигрыш второго, aij ≷ 0 ! Игра в орлянку. Игроки выбирают ход∈{орел, решка}. Если ходы совпали, то выиграл первый, иначе второй. II игрок I игрок орел решка

орел

решка

1

–1

–1

1

Лекция 14. Матричные игры

-2-

Прорыв обороны. Первый игрок выбирает систему зенитного вооружения. Второй игрок выбирает самолет. Элементы aij задают вероятность поражения самолета j системой i. Цель второго игрока — прорвать оборону. Самолеты

0,5 0,6 0,8 Зенитки

0,9 0,7 0,8 0,7 0,5 0,6

В первом примере все ходы одинаково плохи или хороши. Во втором примере ход (2, 2) в некотором смысле лучший для обеих сторон: если взять самолет 2, то зенитка 2 — лучшая для первого игрока; если взять зенитку 2, то самолет 2 лучший для второго. В матрице есть седловая точка! Определение. Седловой точкой матрицы (aij) называют пару (i0j0) такую, что aij 0 ≤ ai0 j0 ≤ ai0 j , ∀ij . Лекция 14. Матричные игры

-3-

Принцип минимакса (осторожности). Предположим, что противник всеведущ и угадывает все ходы! Первый игрок предполагает, что второй все знает и для хода i выберет j(i): aij(i) ≤ aij, ∀ j = 1,…, n. Обозначим α i = aij (i ) = min aij , i = 1,..., m. Тогда лучшей 1≤ j ≤ n

стратегией для первого игрока есть α = max α i = max min aij = α i0 . i

1≤i ≤ m 1≤ j ≤ n

Величину α назовем нижней ценой игры в чистых стратегиях. Второй игрок: из соображений осторожности считает, что первый выберет i(j) ∀ j так, что ai(j)j ≥ aij, ∀ j, т.е. β j = max aij и выбирает j с минимальным βj, т.е. 1≤i ≤ m

β = min max aij = β j0 . 1≤ j ≤ n 1≤i ≤ m

Величину β назовем верхней ценой игры в чистых стратегиях. Пример 1. α = –1, β = +1, α ≤ β Пример 2. α = max{0.5, 0.7, 0.5} = 0.7 , β = min{0.9, 0.7, 0.8} = 0.7. i

j

Лекция 14. Матричные игры

-4-

Лемма. Для любой функции f(x,y), x∈X, y∈Y, справедливо неравенство max min f ( x, y ) ≤ min max f ( x, y ) x∈X y∈Y

y∈Y x∈X

в предположении, что эти величины существуют. Доказательство. Введем обозначения: f ( x, y ( x)) = min f ( x, y ) , y∈Y

f ( x ∗ , y ( x∗ )) = max f ( x, y ( x)) . x∈X

Тогда max min f ( x, y ) = f ( x ∗ , y ( x∗ )) = min f ( x∗ , y ) ≤ min max f ( x, y ). x∈X y∈Y

y∈Y

y∈Y x∈X

Лекция 14. Матричные игры

-5-

Теорема. Необходимым и достаточным условием равенства верхней и нижней цен игры в чистых стратегиях является существование седловой точки в матрице (aij). Доказательство. Необходимость. Пусть α = β. По определению ⎧α = max min aij = min ai0 j ≤ ai0 j0 ⎪ 1≤ j ≤ n 1≤i ≤ m 1≤ j ≤ n ⎨ β = min max a = max a ≥ a ij ij i0 j0 ⎪⎩ 1≤ j ≤ n 1≤i ≤ m 1≤i ≤ m 0 т.е. α ≤ ai0 j0 ≤ β . Так как α = β, то aij0 ≤ ai0 j0 ≤ ai0 j , ∀ij , т.е. является седловой точкой. Достаточность. Пусть седловая точка (i0j0) существует, т.е. aij0 ≤ ai0 j0 ≤ ai0 j , ∀i = 1,..., m, j = 1,..., n. Тогда min max aij ≤ max aij0 ≤ ai0 j0 ≤ min ai0 j ≤ max min aij , но по лемме верно j

i

j

i

i

j

обратное, т.е. min max aij = max min aij . Следовательно α = β. j

i

i

j

Лекция 14. Матричные игры

-6-

Смешанные стратегии и основная теорема матричных игр Определение. Под смешанной стратегией будем понимать вероятностное распределение на множестве чистых стратегий. Смешанная стратегия первого игрока: p = (p1,…, pm), m

p ∈ Pm = {( p1 ,..., pm ) | ∑ pi = 1, pi ≥ 0, i = 1,..., m}. i =1

Смешанная стратегия второго игрока q = (q1,…, qn), n

q ∈ Qn = {( q1 ,..., qn ) | ∑ q j = 1, q j ≥ 0, j = 1,..., n}. j =1

При многократном повторении игры игрок выбирает чистые стратегии случайным образом с соответствующими вероятностями. Платежная функция для смешанных стратегий p и q: m n

E ( p, q ) = ∑ ∑ a ij pi q j i =1 j =1

задает математическое ожидание выигрыша первого игрока при p,q. Лекция 14. Матричные игры

-7-

Замечание. Добавлением большой положительной константы можно добиться того, что E(p,q) > 0, ∀ p,q без изменения стратегий. Из принципа осторожности: Первый игрок ищет максимум α ( p ) = min E ( p, q ) и получает нижнюю цену игры α = max α ( p ).

q∈Qn

p∈Pm

Второй игрок ищет минимум β (q ) = max E ( p, q ) и получает верхнюю цену игры β = min β (q ).

p∈Pm

q∈Qn

Теорема (Фон–Неймана) В матричной игре существует пара ( p ∗ , q ∗ ) смешанных стратегий, таких что 1. E ( p, q ∗ ) ≤ E ( p ∗ , q ∗ ) ≤ E ( p ∗q ) , ∀ p∈Pm, q∈Qn. 2. α = β = E ( p ∗ , q ∗ ) . Лекция 14. Матричные игры

-8-

Доказательство. Сначала покажем, как представить задачу о выборе наилучших стратегий в виде ЛП, а затем докажем теорему. Первый игрок: α(p) → max m

α ( p ) = min E ( p, q ) ≤ ∑ aij pi , ∀j = 1,..., n. q∈Qn

i =1

Пусть ui = pi /α(p), i = 1,…, m, в предположении α(p) > 0. m

m

1 Тогда ui ≥ 0, i = 1,…, m, и ∑ aij ui ≥ 1, ∀j = 1,..., n. Заметим, что ∑ ui = α ( p) i =1 i =1 и задача α(p) → max может быть записана следующим образом: m

min ∑ ui i =1

m

∑ aij ui ≥ 1, j = 1,..., n

i =1

,

ui ≥ 0, i = 1,..., m . Лекция 14. Матричные игры

-9-

Аналогичным образом получаем задачу второго игрока: n

max ∑ v j j =1

n

∑ aij v j ≤ 1,

i = 1,..., m,

j =1

v j ≥ 0, j = 1,..., n, где vj = qj /β(q), j = 1,…, n. Полученные задачи являются взаимодвойственными. Пусть ui∗ , v ∗j — оптимальные решения этих задач. Положим pi∗ = ui∗

m

∑ ui∗ , i =1

q ∗j = v ∗j

n

∑ v∗j . Из второй теоремы двойственности j =1

следует, что m

v∗j (∑ aij ui∗ − 1) = 0, j = 1,..., n, i =1

n

ui∗ ( ∑ aij v ∗j − 1) = 0, i = 1,..., m. j =1

Лекция 14. Матричные игры

-10-

Просуммировав, получим n

v∗j j =1

∑

m n

= aij ui∗v ∗j i =1 j =1

∑∑

m

= ∑ ui∗ . i =1

Поделим на (∑ v ∗j )(∑ ui∗ ) : E ( p∗ , q∗ ) =

1

1 = . ∗ ∗ ∑ v j ∑ ui

Теперь докажем первое утверждение теоремы: m

n

m

n

i =1

j =1

i =1

j =1

n

m

n

m

E ( p, q ∗ ) = ∑ pi ∑ aij q ∗j = ∑ pi ∑ aij

v∗j

1 1 p ≤ = . ∗ ∗∑ i ∗ ∑v j ∑v j ∑v j

Аналогично E ( p∗ , q) =

∑ q j ∑ aij pi∗ = j =1

i =1

∑ q j ∑ aij j =1

i =1

ui∗

∑

ui∗

≥

1

∑

ui∗

∑qj =

1

∑

ui∗

.

т.е. E ( p, q ∗ ) ≤ E ( p ∗ , q ∗ ) ≤ E ( p ∗ , q ), ∀p ∈ Pm , q ∈ Qn . Лекция 14. Матричные игры

-11-

Докажем второе утверждение теоремы. Из предыдущего неравенства имеем: max E ( p, q ∗ ) ≤ E ( p ∗ , q ∗ ) ≤ min E ( p ∗ , q ), q

p

т.е. β = min max ∑ aij pi q j ≤ max min ∑ aij pi q j = α . q

p

ij

p

q

ij

Но по лемме α ≤ β ⇒ α = β = E ( p ∗ , q ∗ ).

Лекция 14. Матричные игры

-12-