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

МИНОБРНАУКИ РОССИИ

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

ИНЖЕНЕРНАЯ ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ В Г. ТАГАНРОГЕ

(ТРТИ Южного федерального  университета)

 

Факультет  АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ 

 

 

 

 

 

 

РЕФЕРАТ

по учебной дисциплине

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

на тему:

«Задача упаковки в контейнеры»

 

 

 

 

 

Выполнила: 

студентка гр. А-31,

Панченко Е.Л.

 

 

Проверил:  
Грищенко А. С.

 

 

 

« ___ »  _____________  2014г.

 

 

 

 

 

Таганрог, 2014 г.

Содержание

1. Введение.
2. Задача упаковки в контейнеры.

1. Алгоритм «Следующий подходящий» (NF).
2. Алгоритм «Первый подходящий» (FF).
3. Алгоритм «Наилучший подходящий» (BF).
4. Алгоритмы типа On-line.
5. Алгоритмы с ограниченным доступом к контейнерам.
6. Алгоритм «Первый подходящий с упорядочиванием» (FFD).
7. Алгоритм Aε.
8. Релаксация линейного программирования.
9. Оценки Martello & Toth.

3. Общий алгоритм решения задачи об упаковке.
4. Вывод.

     Список литературы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Введение

 

В теории сложности вычислений задача об упаковке в контейнеры — NP-трудная комбинаторная задача. Задача заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объём объектов (которые упаковывают) были наибольшими.

Различают следующие алгоритмы задач об упаковке в контейнеры:

«Следующий подходящий» (NF), «Первый подходящий» (FF), «Наилучший подходящий» (BF), On-line, с ограниченным доступом к контейнерам, «Первый подходящий с упорядочиванием» (FFD), Aε.

Работу алгоритмов рассмотрим далее. 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Дано: множество предметов L = {1, … , n} и их веса wi∈(0,1), i∈L.

Найти: разбиение множества L на минимальное число m подмножеств

B1, B2, … , Bm такое, что

 

Множества Bj называют контейнерами.

Требуется упаковать предметы в минимальное число контейнеров.

Задача NP-трудна и часто возникает в приложениях.

 

1. Алгоритм «Следующий подходящий» (NF)

В произвольном порядке упаковываем предметы по следующему правилу.

Первый предмет помещаем в первый контейнер.

На k-м шаге пытаемся поместить k-й предмет в текущий контейнер.

Если предмет входит, то помещаем его и переходим к следующему шагу,

иначе помещаем предмет в новый контейнер.

Т = О(n), П = О(1), если не считать место для исходных данных.

Теорема. NF(L) ≤ 2OPT(L).

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

 

Так как любые два последовательных контейнера содержат предметы суммарным весом не меньше единицы, то NF(L) < 2⎡W⎤.

Кроме того, OPT(L) ≥ ⎡W⎤, откуда и следует требуемое.

Пример.

 

 

 

 

 

 

 

Замечание. NF(L) ≤ 2OPT(L) – 1 для всех L.

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

 

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

Определение. Асимптотическая гарантированная относительная точность

для алгоритма A определяется как

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

 

2. Алгоритм «Первый подходящий» (FF)

В произвольном порядке упаковываем предметы по следующему правилу.

Первый предмет помещаем в первый контейнер.

На k-м шаге находим контейнер с наименьшим номером, куда помещается k-й

предмет, и помещаем его туда. Если такого контейнера нет, то берем новый

пустой контейнер и помещаем предмет в него.  Т = О(n2), П = О(n).

Теорема.                                           для всех L и существуют примеры со сколь

угодно большими значениями OPT, для которых

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

Пример.

 

 

 

 

 

 

3. Алгоритм «Наилучший подходящий» (BF)

В произвольном порядке упаковываем предметы по следующему правилу.

Первый предмет помещаем в первый контейнер.

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

Теорема.                                         и существуют примеры со сколь угодно большими значениями OPT(L), для которых BF(L) = 4/3 FF(L) и FF(L) = 3/2 BF(L).

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

 

4. Алгоритмы типа On-line

Предметы поступают в непредсказуемом порядке. Требуется упаковать их в

минимальное число контейнеров. Упакованный предмет нельзя перемещать в

другой контейнер. Место для предварительного хранения предметов отсутствует.

Алгоритмы NF, FF, BF являются On-line алгоритмами.

Теорема. Для любого On-line алгоритма A справедливо неравенство 

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

 

5. Алгоритмы с ограниченным доступом к контейнерам

On-line алгоритм называют алгоритмом с ограниченным доступом

к контейнерам, если на каждом шаге алгоритм имеет возможность помещать

предметы только в один из K контейнеров (K — const). Эти контейнеры называются открытыми. Если контейнер закрыли, то он уже не открывается (например, отправляется потребителю). Прежде чем добавить пустой открытый контейнер, нужно закрыть один из K открытых контейнеров.

Алгоритм NF — пример для K = 1.

Правила для выбора контейнера:

1. Закрыть контейнер с  наименьшим номером

2. Закрыть самый заполненный  контейнер.

 

Примеры алгоритмов с ограниченным доступом

FF1 — алгоритм FF с правилом 1.

FF2 — алгоритм FF с правилом 2.

BF1 — алгоритм BF с правилом 1.

BF2 — алгоритм BF с правилом 2.

Теорема. Для любого K ≥ 2

 

6. Алгоритм «Первый подходящий с упорядочиванием» (FFD)

• Сортируем предметы по невозрастанию весов  w1 ≥ w2 ≥ … ≥ wn

• Применяем алгоритм FF (BF).

Теорема.

                                                   для всех L и существуют примеры со сколь угодно     большими значениями OPT(L), для которых

Кроме того 

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

 

Пример.

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

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

Трудоемкость Aε полиномиально зависит от n .

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

 

7. Алгоритм Aε

1. Удалить предметы с  весом менее ε.

2. Упорядочить оставшиеся  предметы и разбить их на K = ⎡1/ε2⎤ групп.

3. В каждой группе увеличить  веса предметов до максимального  веса в группе.

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

весов каждый из которых не менее ε.

5. Вернуть исходные веса  предметов и применить алгоритм FF для предметов с весом менее ε.

 

Негативный результат

Теорема. Для любого ε > 0 существование приближенного полиномиального алгоритма A с гарантированной точностью                       влечет P = NP.

Доказательство. Пусть такой алгоритм А существует. Покажем, как с его помощью можно решить точно одну из NP-полных задач, а именно задачу о

разбиении. Дано n неотрицательных чисел a1,…, an.

Можно ли разбить их на два подмножества так, чтобы сумма чисел в каждом

 

подмножестве равнялась                        ?

 

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

wi =ai/C, i = 1,…, n. Если их можно упаковать в два контейнера, ответ в задаче

о разбиении — «ДА». Применим алгоритм А к задаче о контейнерах.

Если OPT = 2, то алгоритм А тоже дает 2, иначе            , то есть алгоритм А точный.

 

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

Заменим условие булевости переменных на условия:

0 ≤ yj ≤ 1, j = 1,…, n

0 ≤ xij ≤ 1, i, j = 1,…, n.

Тогда одно из оптимальных решений имеет вид

что дает нижнюю оценку

(предметы можно резать  произвольным образом).

9. Оценки Martello & Toth

Для примера L = {1,…, n}, 0 ≤ wi < 1 и произвольного 0 ≤ α ≤ 1/2 положим

L1 = { i∈L | wi > 1 – α } — крупные предметы

L2 = { i∈L | 1– α ≥ wi > 1/2 } — средние предметы

L3 = { i∈L | 1/2 ≥ wi ≥ α } — мелкие предметы

Теорема. Для любого 0 ≤ α ≤ 1/2 величина

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

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

контейнер. Поэтому в любом допустимом решении не менее | L1 | + | L2 | контейнеров. Предметы из множества L3 не лежат вместе с предметами из L1.

Значит, они лежат либо вместе с предметами из L2 , либо в отдельных