Санкт-Петербургский Государственный Технический Университет

Факультет Технической Кибернетики

Кафедра Системный Анализ и Управление

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

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

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

Дата:_____________

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

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].