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

 

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

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

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

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

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

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

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

РЕФЕРАТ

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

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

на тему

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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема(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).

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

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

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

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

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

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

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

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

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

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

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

Примеры алгоритмов с ограниченным доступом- алгоритм FF с правилом 1.- алгоритм FF с правилом 2.- алгоритм BF с правилом 1.- алгоритм 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?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

? yj ? 1, j = 1,…, n

? xij ? 1, i, j = 1,…, n.

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

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

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

.9.Оценки Martello & Toth

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

= { i?L | wi > 1 - ? } - крупные предметы= { i?L | 1- ? ? wi > 1/2 } - средние предметы= { 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)ÎY´Y | "k=1,…,N; yik£ yjk и $p: yip< yjp }

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

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

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

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

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

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

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

Производится сравнение объектов (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,в) и выделить паретовые слои. При этом считается, что объект, принадлежащий высшему слою, "потенциально" лучше объекта из низшего слоя.

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

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

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

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

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

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

K = max (0.9O1 + 0.3O2)

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

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

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

Вывод

Существует множество разновидностей этой задачи (двумерная упаковка <#"center">алгоритм линейный упаковка контейнер

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

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

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

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

МИНОБРНАУКИ РОССИИ Федеральное государственное автономное образовательное учреждение высшего профессионального образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВ

Больше работ по теме: