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

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

Крайние точки 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.

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

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

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

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

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

ЦЛП (R| |C max )

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм 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 (σ)

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

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

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

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

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

Алгоритм 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 (σ)

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

Точность 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).

Пример 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

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