Задача упаковки в контейнеры - Программирование, компьютеры и кибернетика реферат

Алгоритмы задач об упаковке в контейнеры: "Следующий подходящий" (NF), "Первый подходящий" (FF), "Наилучший подходящий" (BF), On-line, с ограниченным доступом к контейнерам, первый подходящий с упорядочиванием (FFD). Релаксация линейного программирования.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.


Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
ИНЖЕНЕРНАЯ ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ В Г. ТАГАНРОГЕ
(ТРТИ Южного федерального университета)
Факультет АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
В теории сложности вычислений задача об упаковке в контейнеры -- NP-трудная комбинаторная задача. Задача заключается в упаковке объектов предопределённой формы в конечное число контейнеров предопределённой формы таким способом, чтобы число использованных контейнеров было наименьшим или количество или объём объектов (которые упаковывают) были наибольшими.
Различают следующие алгоритмы задач об упаковке в контейнеры:
«Следующий подходящий» (NF), «Первый подходящий» (FF), «Наилучший подходящий» (BF), On-line, с ограниченным доступом к контейнерам, «Первый подходящий с упорядочиванием» (FFD), A?.
Работу алгоритмов рассмотрим далее.
Дано: множество предметов L = {1, … , n} и их веса wiЎф(0,1), iЎфL.
Найти: разбиение множества L на минимальное число m подмножеств B1, B2, … , Bm такое, что
Множества Bj называют контейнерами.
Требуется упаковать предметы в минимальное число контейнеров.
Задача NP-трудна и часто возникает в приложениях.
1.1. Алгоритм «Следующий подходящий» (NF)
В произвольном порядке упаковываем предметы по следующему правилу.
Первый предмет помещаем в первый контейнер.
На k-м шаге пытаемся поместить k-й предмет в текущий контейнер.
Если предмет входит, то помещаем его и переходим к следующему шагу, иначе помещаем предмет в новый контейнер.
Т = О(n), П = О(1), если не считать место для исходных данных.
Так как любые два последовательных контейнера содержат предметы суммарным весом не меньше единицы, то 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).
Предметы поступают в непредсказуемом порядке. Требуется упаковать их в минимальное число контейнеров. Упакованный предмет нельзя перемещать в другой контейнер. Место для предварительного хранения предметов отсутствует.
Алгоритмы NF, FF, BF являются On-line алгоритмами.
Теорема. Для любого On-line алгоритма A справедливо неравенство
1.5. Алгоритмы с ограниченным доступом к контейнерам
On-line алгоритм называют алгоритмом с ограниченным доступом к контейнерам, если на каждом шаге алгоритм имеет возможность помещать предметы только в один из K контейнеров (K -- const). Эти контейнеры называются открытыми. Если контейнер закрыли, то он уже не открывается (например, отправляется потребителю). Прежде чем добавить пустой открытый контейнер, нужно закрыть один из K открытых контейнеров.
1. Закрыть контейнер с наименьшим номером
2. Закрыть самый заполненный контейнер.
Примеры алгоритмов с ограниченным доступом
1.6. Алгоритм «Первый подходящий с упорядочиванием» (FFD)
* Сортируем предметы по невозрастанию весов w1 ЎГ w2 ЎГ … ЎГ wn
для всех L и существуют примеры со сколь угодно большими значениями OPT(L), для которых
Асимптотические гарантированные оценки точности
Теорема. Для любого Ґе Ўф (0,1] существует алгоритм AҐе , который находит упаковку с числом контейнеров не более (1 + 2Ґе) OPT + 1.
Трудоемкость AҐе полиномиально зависит от n .
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. Релаксация линейного программирования
Заменим условие булевости переменных на условия:
Тогда одно из оптимальных решений имеет вид
(предметы можно резать произвольным образом).
Для примера 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).
Доказательство. При Ґб = 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 }
В соответствии с отношением 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).
ЛПР может выбрать один из полученных вариантов или указать соотношение значений критериев, по которому будет произведён этот выбор, например:
Метод решения задачи об упаковке может быть распространён на случаи, когда:
1) часть объектов может быть упакована только в определённые контейнеры;
2) несколько объектов имеют общие части и должны быть упакованы вместе.
Существует множество разновидностей этой задачи (двумерная упаковка, линейная упаковка, упаковка по весу, упаковка по стоимости и т. п.), которые могут применяться в разных областях, как собственно в вопросе оптимального заполнения контейнеров, загрузки грузовиков с ограничением по весу, созданием резервных копий на съёмных носителях и т. д. Так как задача является NP-трудной, то использование точного переборного алгоритма возможно только при небольших размерностях. Обычно для решения задачи используют эвристические приближённые полиномиальные алгоритмы.
алгоритм линейный упаковка контейнер
1. Э.Х. Гимади. О некоторых математических моделях и методах планирования крупномасштабных проектов //Модели и методы оптимизации.
2. Труды Института математики. Новосибирск. Наука. Сиб. Отделение. 2011. с. 89-115.
3. М. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 2009. с. 154-191.
Постановка задачи линейного программирования и формы ее записи. Понятие и методика нахождения оптимального решения. Порядок приведения задач к каноническому виду. Механизмы решения задач линейного программирования аналитическим и графическим способами. методичка [366,8 K], добавлен 16.01.2010
Многоблочный метод решения сложных задач. Программирование параллельных ЭВМ. Алгоритм сокращения критического пути (CPR). Упаковка в контейнеры. Алгоритмы EVAH. Общая архитектура разработанного средства. Первоначальные предложения по отображению. дипломная работа [611,5 K], добавлен 15.10.2010
Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения". курсовая работа [2,2 M], добавлен 29.05.2015
Оптимизационные исследования задач линейного и нелинейного программирования при заданных математических моделях. Решение задач линейного программирования и использование геометрической интерпретации и табличного симплекс-метода, транспортная задача. курсовая работа [408,7 K], добавлен 13.06.2019
Общее понятие и характеристика задачи линейного программирования. Решение транспортной задачи с помощью программы MS Excel. Рекомендации по решению задач оптимизации с помощью надстройки "Поиск решения". Двойственная задача линейного программирования. дипломная работа [2,4 M], добавлен 20.11.2010
Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов. курсовая работа [280,8 K], добавлен 17.11.2011
Характеристика параметрических методов решения задач линейного программирования: методы внутренней и внешней точки, комбинированные методы. Алгоритм метода барьерных поверхностей и штрафных функций, применяемых для решения задач большой размерности. контрольная работа [59,8 K], добавлен 30.10.2014
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Задача упаковки в контейнеры реферат. Программирование, компьютеры и кибернетика.
Курсовая Работа На Тему Содержание Организации Технической Подготовки Производства
Реферат На Тему Історія Виникнення Філософського Вчення
Реферат: Портрет 2
Контрольная работа по теме Планування інновацій
Эссе Чему Учит Персонаж Гарри Поттер
Реферат по теме Розробка підсилювача
Реферат На Тему Обеспечение Навигационной Безопасности
Реферат: Расчет сушильной установки
Реферат: Защитная функция адвокатуры как правовая традиция
Написать Сочинение С Фразеологизмами
Дипломная работа: ТЕХНОЛОГИЧЕСКИЙ ПРОЦЕСС ВОССТАНОВЛЕНИЯ чашки ДИФФЕРЕНЦИАЛА 130-1805040-Б3. Скачать бесплатно и без регистрации
Дипломная работа по теме Розробка маркетингової стратегії виходу підприємства ЗАТ 'Горлівський завод РЕАХІМ' на зовнішній ринок
Реферат: Курение, как социальная проблема в обществе. Скачать бесплатно и без регистрации
Дипломная работа по теме Динаміка вилову риби в природних водоймах та вплив екологічних факторів на продуктивність
Здоровый Образ Жизни Подростков Реферат
Контрольная работа по теме Заключение, изменение, расторжение договора
Курсовая работа по теме Учет денежных средств в иностранной валюте
Учебное пособие: История Татарстана с древнейших времен до наших дней
Контрольная работа по теме Упаковка ювелирных изделий
Анализ Работы Аттестационной Комиссии В Школе Беларусь
Northern Ireland. The land of tales and legends - География и экономическая география презентация
Data mining - Программирование, компьютеры и кибернетика доклад
Организация как объект управления - Менеджмент и трудовые отношения лекция