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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

РЕФЕРАТ

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

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

на тему

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

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

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

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

Таганрог, 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 | RA (L) ЎВ r для всех L}.

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

ЎХ inf {r ЎГ 1 | ў¤ 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 ЎВ Ґб ЎВ 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 , либо в отдельных контейнерах. В контейнерах для L2 осталось свободного места.

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

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

является нижней оценкой для 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) = max{|L2|, H0}ЎГ H0.

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

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

Тогда

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



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

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

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

P0={(yi,yj)YY | k=1,…,N; yik yjk и p: yip< yjp }

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.

Размещено на Allbest.ur