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

МИНОБРНАУКИ РОССИИ Федеральное государственное автономное образовательное учреждение высшего профессионального образования

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

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

(ТРТИ Южного федерального университета) Факультет АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ РЕФЕРАТ по учебной дисциплине

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

на тему

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

Выполнила: студентка гр. А₃₁,

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

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

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

Введение

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

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

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

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

1. Задача упаковки в контейнеры Дано: множество предметов L = {1, …, n} и их веса wiЎф (0,1), iЎфL.

Найти: разбиение множества L на минимальное число m подмножеств B1, B2, …, Bm такое, что Множества Bj называют контейнерами.

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

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

1.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 .

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

ЎХ inf ў¤ N > 0 такое, что RA (L) ЎВ r для всех L с OPT (L) ЎГ N.

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

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

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

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

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

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

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

Пример.

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

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

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

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

Теорема.

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

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

Предметы поступают в непредсказуемом порядке. Требуется упаковать их в минимальное число контейнеров. Упакованный предмет нельзя перемещать в другой контейнер. Место для предварительного хранения предметов отсутствует.

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

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

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

1.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

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

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

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

Теорема.

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

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

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

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

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

1.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, иначе, то есть алгоритм, А точный.

1.8. Релаксация линейного программирования Заменим условие булевости переменных на условия:

0 ЎВ yj ЎВ 1, j = 1,…, n

0 ЎВ xij ЎВ 1, i, j = 1,…, n.

Тогда одно из оптимальных решений имеет вид что дает нижнюю оценку

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

1.9. Оценки Martello & Toth

Для примера L = {1,…, n}, 0 ЎВ wi < 1 и произвольного 0 ЎВ Ґб ЎВ ½ положим

L1 = iЎфL — крупные предметы

L2 = 1- Ґб ЎГ wi > ½ — средние предметы

L3 = iЎфL — мелкие предметы Теорема. Для любого 0 ЎВ Ґб ЎВ ½ величина является нижней оценкой для OPT (L).

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

Значит, они лежат либо вместе с предметами из L2, либо в отдельных контейнерах. В контейнерах для L2 осталось свободного места.

Следовательно, для предметов из множества L3 требуется как минимум отдельных контейнеров.

Теорема. Для любого 0 ЎВ Ґб ЎВ ½ величина является нижней оценкой для OPT (L).

Доказательство. Заменим вес каждого предмета из множества L3 на Ґб.

Тогда в один контейнер войдет предметов, и для множества L3 потребовалось бы дополнительных контейнеров.

Но часть предметов из L3 можно уложить в контейнеры для L2. Каждый из них имеет 1- wi, iЎфL2 свободного места, где поместится предметов из L3.

Следствие 1. Величина H = max{H1(Ґб), H2(Ґб), 0 ЎВҐб ЎВ 0,5} является нижней оценкой для OPT (L).

Следствие 2.

Доказательство. При Ґб = 0 получаем H ЎГ H1(0) = maxL2ЎГ H0.

Как найти H, не перебирая все значения Ґб ?

Следствие 3. Пусть V — множество всех различных значений wi ЎВ 0,5.

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

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

1. Предварительное упорядочивание объектов в соответствии с отношением доминирования.

Исследование соотношений по качеству объектов. Путём попарного сравнения объектов определяется асимметричное транзитивное отношение доминирования:

P0=(yi, yj) YY

2. Выделение паретовых слоёв.

В соответствии с отношением P0 на множестве объектов можно выделить подмножество недоминируемых объектов. После их удаления можно выделить второе подмножество и т. д. до исчерпания множества. Выделенные слоя являются паретовыми слоями.

3. Предварительная упаковка объектов.

Она заключается в применении алгоритма АОЧ по слоям.

Пусть упаковка объектов (i-1) первых слоёв возможна, но объекты i-го слоя уже не входят. Рассмотрим частный случай, когда каждый объект (i-1)-го слоя превосходит каждый объект i-го слоя и каждый объект i-го слоя в свою очередь превосходит каждый объект (i+1)-го слоя, причём объекты, принадлежащие одному слою, эквиваленты по качеству. В этом случае можно сразу переходить к шагу 6, т.к. имеется вся необходимая информация для упаковки объектов в месте их предполагаемого «разреза» на группы упакованных и неупакованных объектов.

В общем случае такая информация отсутствует. Для уменьшения неопределённости требуются шаги 4,5.

4. Определение информации, требующейся для предварительного упорядочивания объектов.

Производится сравнение объектов (i-1), i и (i+1) слоёв, т. е. тех слоёв, где вероятно произойдёт разделение объектов при упаковке. Определяется объём информации, необходимый для упорядочения этих объектов по качеству.

Если объекты этих слоёв находятся в отношении доминирования или «почти» доминирования (т.е. доминирования по всем критериям, кроме одного), то информация для упорядочения этих объектов может быть получена от ЛПР путём прямого опроса. ЛПР предъявляют объекты (попарно) и выясняют, какой из них для ЛПР является более ценным. При возникновении противоречий (A>B>C>A) необходимо указывать на эти противоречия ЛПР для их разрешения.

В общем случае объекты отличаются оценками по нескольким критериям и при этом являются достаточно представительными элементами множества Y. Для их упорядочения требуется дополнительная информация о предпочтениях ЛПР.

Например, если все объекты можно расположить в соответствии с оценками так, как это приведено на рис. 3.1,а, то объекты 2 и 5, 4 и 6, 4 и 7 оказываются несравнимыми. Для их упорядочения нужна дополнительная информация от ЛПР (рис. 3.1,б).

Методы прямого опроса в данной ситуации используются редко, т.к. это достаточно сложная для ЛПР операция выбора. Выявление предпочтений ЛПР осуществляется с помощью построения решающего правила ЛПР (мы рассмотрим это позже).

Рис. 3.1. Пример построения квазипорядка для объектов

5. Построение квазипорядка на множестве объектов.

На основе сформированного на шаге 4 бинарного отношения можно построить квазипорядок (рис. 3.1,в) и выделить паретовые слои. При этом считается, что объект, принадлежащий высшему слою, «потенциально» лучше объекта из низшего слоя.

6. Нахождение различных вариантов упаковки.

К построенному квазипорядку итеративно применяется алгоритм АОЧ. Среди объектов, упакованных на первом этапе, выделяется подмножество объектов, превосходящих каждый из остальных упакованных, если таковые имеются. Это подмножество подлежит обязательной упаковке. Далее к списку применяется алгоритм АОЧ, но объекты из вышеуказанного подмножества не отбрасываются. Т.о., алгоритм применяется, начиная с i-го слоя объектов.

Будем применять алгоритм АОЧ до исчерпания списка. Получим варианты с различными значениями критериев, например, для случая двух критериев (рис. 3.2)

Рис. 3.2. Примеры оценок вариантов решений по двум критериям

7. Определение компромисса между критериями (3) и (4).

ЛПР может выбрать один из полученных вариантов или указать соотношение значений критериев, по которому будет произведён этот выбор, например:

K = max (0.9O1 + 0.3O2)

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

1) часть объектов может быть упакована только в определённые контейнеры;

2) несколько объектов имеют общие части и должны быть упакованы вместе.

Вывод Существует множество разновидностей этой задачи (двумерная упаковка, линейная упаковка, упаковка по весу, упаковка по стоимости и т. п.), которые могут применяться в разных областях, как собственно в вопросе оптимального заполнения контейнеров, загрузки грузовиков с ограничением по весу, созданием резервных копий на съёмных носителях и т. д. Так как задача является NP-трудной, то использование точного переборного алгоритма возможно только при небольших размерностях. Обычно для решения задачи используют эвристические приближённые полиномиальные алгоритмы.

алгоритм линейный упаковка контейнер Список литературы

1. Э. Х. Гимади. О некоторых математических моделях и методах планирования крупномасштабных проектов //Модели и методы оптимизации.

2. Труды Института математики. Новосибирск. Наука. Сиб. Отделение. 2011. с. 89−115.

3. М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 2009. с. 154−191.

.ur