Задача об упаковке
Категория реферата: Рефераты по информатике, программированию
Теги реферата: изложение 4 класс, заключение реферата
Добавил(а) на сайт: Коньяков.
1 2 3 4 5 | Следующая страница реферата
Санкт-Петербургский Государственный Технический Университет
Факультет Технической Кибернетики
Кафедра Системный Анализ и Управление
ПРИНЯТИЕ РЕШЕНИЙ
Расчетное задание
Тема: "Задача об упаковке"
Дата:_____________
Санкт-Петербург
2001 г.
Содержание
1.Постановка
задачи......................................................................
......................…….2
2.Теоретическая часть………………………………………………………………..3
3.Решение……………………………………………………………………………..5
4.Алгоритм программы………………………………………………………………6
5.Результаты…………………………………………………………………………..7
6.Выводы……………………………………………………………………………...7
Приложение…………………………………………………………………………..8
1.Постановка задачи.
Рассмотреть задачу об упаковке 20 гипотетических объектов в пять
контейнеров. Объекты имеют оценки по пяти критериям Б,В,Г,Д,Е с порядковыми
шкалами, имеющими три градации (первая - лучшая, вторая – средняя, третья
- худшая), а также два физических параметра (вес и объем). Критерии имеют
одинаковую значимость. Контейнеры имеют следующие параметры:
. Грузоподъемность контейнера – 5
. Объем контейнера – 7
Далее приведены данные объектов:
|Номер |Вес |Обьем |Б |В |Г |Д |Е |
|1 | | | | | 3| | |
| |3 |2 |3 |3 | |3 |3 |
|2 | | | | | 2| | |
| |1 |1 |3 |2 | |1 |1 |
|3 | | | | 1| 1| | |
| |3 |1 |2 | | |1 |2 |
|4 |2 |3 |2 | | | | |
| | | | |1 |3 |2 |3 |
|5 |1 |1 |1 |1 |1 | | |
| | | | | | |3 |3 |
|6 |3 |2 |2 |2 |1 | | |
| | | | | | |1 |1 |
|7 |1 |2 |3 |1 |3 | | |
| | | | | | |3 |1 |
|8 |2 |1 |1 |1 |1 | | |
| | | | | | |2 |3 |
|9 |3 |2 |2 |2 |1 | | |
| | | | | | |3 |2 |
|10 | |1 |1 |1 |2 | | |
| |2 | | | | |2 |2 |
|11 |1 |2 |3 |3 |1 |1 | |
| | | | | | | |1 |
|12 |3 |1 |2 |1 |2 | | |
| | | | | | |3 |1 |
|13 |1 |1 |2 |2 |3 | | |
| | | | | | |3 |1 |
|14 |1 |1 |3 |3 |3 | | |
| | | | | | |2 |1 |
|15 |2 |2 |1 |2 |2 | | |
| | | | | | |1 |1 |
|16 |3 |2 |3 |1 |2 | | |
| | | | | | |1 |3 |
|17 |1 |1 |2 |1 |2 | | |
| | | | | | |1 |2 |
|18 |2 |2 |3 |1 |3 | | |
| | | | | | |2 |1 |
|19 |1 |1 |1 |1 |1 | | |
| | | | | | |2 |1 |
|20 |1 |2 |1 |1 |1 | | |
| | | | | | |1 |1 |
2.Теоретическая часть.
Рассмотрим следующую задачу: имеется множество из М объектов, которое
желательно упаковать в К емкостей для последующей перевозки, причем М
существенно больше К. Каждый объект характеризуется Р -количественными
физическими параметрами (весом и объемом); каждая емкость характеризуется
этими же предельными физическими параметрами (например, общим объемом и
грузоподъемностью). Кроме того, каждый из упаковываемых объектов имеет
оценки по нескольким критериям , которые характеризуют его качество и
привлекательность для лица, ответственного за перевозку. Емкость
контейнеров недостаточна для упаковки всех имеющихся объектов. Желательно
осуществить упаковку наилучшим образом, т.е. так чтобы:
1. Число упакованных объектов было бы максимально возможным, так как все они в той или иной степени заслуживают упаковки в емкости (т.е. предварительный отбор, исключающий абсолютно плохие объекты, уже сделан)
– критерий О1.
2. Среди упакованных объектов было бы наибольшее количество таких, качество которых превосходило бы качество неупакованных – критерий О2.
Имеется конечное множество объектов, причем размер каждого из них задан рациональным числом. Требуется упаковать предметы в минимально возможное количество контейнеров так, чтобы суммарный размер объектов в каждом контейнере не превышал его размер (также рациональное число).
Для решения этой задачи предлагается ряд алгоритмов:
1. Алгоритм "в первый подходящий". Пусть имеется какой-то порядок объектов и контейнеров. Первый предмет кладем в первый попавшийся контейнер.
Второй объект кладем в первый контейнер, если он туда помещается, а если нет – то во второй контейнер. Аналогично упаковываем прочие объекты.
2. Алгоритм "в первый подходящий с убыванием". Упорядочим список объектов от больших к меньшим. Далее используем алгоритм "в первый подходящий".
3. Алгоритм "в лучший из подходящих". Пусть имеется какой-то произвольный порядок объектов. Идея упаковки аналогична алгоритму "в первый подходящий", но со следующей разницей: очередной объект кладется в тот контейнер, где имеется наименьшее, но достаточное для него неиспользованное пространство.
4. Алгоритм "в лучший из подходящих с убыванием". Алгоритм аналогичен "в лучший из подходящих", но объекты упорядочены от больших к меньшим.
Упаковываемые объекты имеют оценки качества по многим критериям.
Требуется упаковать максимальное число объектов, а не получить минимальное
число контейнеров. Введем следующие обозначения:
[pic]
vij – j-й физический параметр i-го объекта;
Vlj – j-й физический параметр l-го контейнера;
Ui – общая ценность i-го объекта.
Обозначим через I=1, 2, …, М множество номеров объектов, а через
[pic]
Множество тех упакованных объектов, для которых не найдется более ценных среди не упакованных. Формальная постановка задачи имеет следующий вид:
[pic], [pic].
Рекомендуем скачать другие рефераты по теме: доклад на тему россия, сочинение на тему.
1 2 3 4 5 | Следующая страница реферата