Линейное программирование Задача теории расписаний. - презентация

1 Линейное программирование Задача теории расписаний

2 Задача линейного программирования (ЛП)

3 Крайние точки x ={x 1,…,x n } R n Множество S всех векторов x. удовлетворяющих ограничениям задачи ЛП, называется допустимым множеством, а любое x S допустимым решением или допустимой точкой. Если x 1, x 2 S, то x 1 + (1 ) x 2 S, 0 1. Точка x S называется крайней точкой выпуклого множества, если не существует двух отличных от x точек y, z S таких, что x = y + (1 )z для некоторого 0 1.

4 Свойства крайних точек Если задача ЛП в стандартной форме имеет оптимальное решение, то существует оптимальное решение, которое является крайней точкой. Алгоритм эллипсоидов и симплекс метод находят решения ЛП, которые являются крайними точками.

5 Почему ЛП полезно для построения приближенных алгоритмов? Многие комбинаторные задачи могут быть сформулированы, как задачи ЦЛП. ЛП является естественной нижней границей.

6 Основные методы Округление –Решить задачу линейного программирования –Преобразовать полученное дробное решение в целочисленное Прямо-двойственная схема –Итеративно вычисляются целочисленное решение прямой задачи и дробное двойственной –Качество алгоритма оценивается сравнением этих двух решений

7 Разрыв двойственности Рассмотрим ЛП-релаксацию некоторой задачи минимизации Π, пусть OPT f (I) – стоимость оптимального дробного решения примера I. Разрывом двойственности называется следующая величина.

8 R| |C max J={1,..., n} – работы. M={M 1,..., M m } – параллельные машины. ( j, M i ): p ij 0 (j = 1,…, n; i = 1,…, m). Каждая работа должна быть выполнена на одной из m машин. Прерывания запрещены. Каждая машина обслуживает не более одной работы одновременно.

9 ЦЛП (R| |C max )

10 Замечание ЦЛП (R| |C max ) имеет неограниченный разрыв двойственности. Пример: J 1 : p i1 = m (i=1,…, m). C max (ЦЛП) = m. C max (ЛП) = 1.

11 ЛП (R| |C max ) Почему ЛП так сильно выигрывает у ЦЛП? ЦЛП автоматически полагает x ij =0, если p ij > t, а ЛП распределяет по 1/m работе на каждую из машин. i = 1,…,m, j=1,…,n: если p ij > t, то x ij =0. Это нелинейное ограничение!

12 Бинарный поиск T Z + : S T ={(i, j)| p ij T}.

13 Свойства решений ЛП(T) Лемма 9.1 Любое экстремальное решение ЛП(T) имеет не более n + m ненулевых переменных.

14 Доказательство леммы 9.1 Пусть r = |S T | число переменных в ЛП(T). Допустимое решение является экстремальным r линейно независимых ограничений обращаются в равенство. По крайней мере r – (n + m) из них будут выбраны из третьего множества ограничений. По крайней мере r – (n + m) соответствующих переменных равны 0. Любое экстремальное решение ЛП(T) имеет не более n + m ненулевых переменных.

15 Определение Пусть x экстремальное решение ЛП(T). Будем называть работу в решении x целой, если она назначена ровно на одну машину. В противном случае, будем называть работу дробной.

16 Свойства решений ЛП(T) Следствие 9.2 В любом экстремальном решении ЛП(T) по крайней мере n – m целых работ.

17 Доказательство следствия Пусть – x экстремальная точка –α число целых работ –β число дробных работ α + β = n Каждая дробная работа дает не менее двух ненулевых входов в x. α + 2β n + m. β m и α n – m.

18 Представление экстремального решения двудольным графом Машины и Работы

19 F J, F – множество дробных работ Машины и Работы

20 Паросочетание Паросочетание в H назовем совершенным, если оно покрывает каждую работу J i F.

21 Границы бинарного поиска. Назначим каждую работу на ту машину, на которой она имеет наименьшее время выполнения. Пусть α длина полученного расписания. α/m C max (σ*) α

22 Алгоритм LST (Lenstra, Shmoys, Tardosh 1990) Input ( J={1,..., n}, M={M 1,..., M m }, p: J×M Q + ) 1.Используя бинарный поиск в интервале [α/m,α] найти наименьшее значение T Z +, для которого ЛП(T) имеет допустимое решение. Обозначим его T*. 2.Найти x любое экстремальное решение ЛП(T*). 3.Назначить все целые работы на те же машины, что и в x. 4.Построить граф H и найти совершенное паросочетание в нем. 5.Назначить дробные работы на машины согласно этому паросочетанию. Обозначим полученное расписание σ. Output (σ)

23 Псевдолес Связный граф на множестве вершин V называется псевдодеревом, если он имеет не более | V | ребер. Граф называется псевдолесом, если каждая его связная компонента псевдодерево. Лемма 9.3 Граф G псевдолес.

24 Доказательство леммы 9.3 Рассмотрим связную компоненту G C. Ограничим ЛП(T) и x работами и машинами из G C, обозначим полученное ЛП C (T) и x C. Тогда x C тоже экстремальная точка. Лемма 7.1 число ребер не больше чем n C + m C G C псевдодерево.

25 Совершенное паросочетание Лемма 9.4 Граф H имеет совершенное паросочетание.

26 Доказательство леммы 9.4 Удаляя из G все вершины, соответствующие целым работам, и инцидентные им ребра, получим H. Так как удалено одинаковое количество вершин и ребер H псевдолес. Все листья (если есть) в H соответствуют машинам. Выберем произвольный лист (машину), и добавим инцидентное ему ребро в паросочетание. Удалим обе вершины (машину и работу) этого ребра из Н. Повторим эту процедуру, пока не получим либо набор четных циклов либо пустой граф. В каждом цикле добавим набор чередующихся ребер в паросочетание. В результате получим совершенное паросочетание, покрывающее все работы.

27 Алгоритм LST Теорема 9.5 Алгоритм LST является 2-приближенным алгоритмом для R| |C max.

28 Алгоритм LST (Lenstra, Shmoys, Tardosh 1990) Input ( J={1,..., n}, M={M 1,..., M m }, p: J×M Q + ) 1.Используя бинарный поиск в интервале [α/m,α] найти наименьшее значение T Z +, для которого ЛП(T) имеет допустимое решение. Обозначим его T*. 2.Найти x любое экстремальное решение ЛП(T*). 3.Назначить все целые работы на те же машины, что и в x. 4.Построить граф H и найти совершенное паросочетание в нем. 5.Назначить дробные работы на машины согласно этому паросочетанию. Обозначим полученное расписание σ. Output (σ)

29 Доказательство теоремы 9.5 Из шага 1 алгоритма имеем, что T* OPT. Длина расписания на множестве целых работ не превосходит T*. При распределении работ согласно совершенному паросочетанию на каждую машину добавляется не больше одной дробной работы. Так как p ij T*, то общая длина полученного расписания не больше 2T* 2OPT.

30 Точность J 1,..., J n – работы, n = m 2 – m +1. M 1,..., M m – параллельные машины. J 1 : p i1 = m (i=1,…, m). (J j, M i ): p ij = 1 (j=2,…, n; i=1,…, m).

31 Пример J1J1 J4J4 J7J7 J2J2 M1M1 M2M2 M3M3 J5J5 J9J9 J8J8 J 12 J 11 J3J3 J6J6 J 10 M4M4 J 13 J1J1 J7J7 J1J1 M1M1 M2M2 M3M3 J5J5 J9J9 J8J8 J 12 J 11 J1J1 J6J6 J 10 M4M4 J 13 J1J1 J2J2 J3J3 J4J4 M2M2 M3M3 M4M4 J1J1 M1M1

32 Практика Можно ли улучшить оценку точности алгоритма Ленстра-Шмойс-Тардош для задачи, в которой все машины являются идентичными? Доказать, что точка x C, выбранная в доказательстве леммы 9.3, является экстремальной точкой в ЛП C (T). Доказать, что дробное решение в примере, доказывающем достижимость оценки алгоритма Ленстра-Шмойс-Тардош является экстремальной точкой.