Новости Словари Конкурсы Бесплатные SMS Знакомства Подари звезду
В нашей
базе уже
59876
рефератов!
Логин

Пароль

Задача об упаковке

Задача об упаковке.
Задача об упаковке Санкт-Петербургский Государственный Технический Университет
Факультет Технической Кибернетики




ПРИНЯТИЕ РЕШЕНИЙ


Расчетное задание


Тема: "Задача об упаковке"



Дата:_____________



Санкт-Петербург


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. Алгоритм "в лучший из подходящих с убыванием". Алгоритм аналогичен "в
лучший из подходящих", но объекты упорядочены от больших к меньшим.
Упаковываемые объекты имеют оценки качества по многим критериям.
Требуется упаковать максимальное число объектов, а не получить минимальное
число контейнеров. Введем следующие обозначения:
Умар.Ш. был тут !!!!!
 
давайте изгоним мат !!!
 
ДОБРОЙ НОЧИ ОТ Ъ
ЛОКИ ИНО
 
ДМК МЭ
 
где инфааа?