Главная Учебники - Разные Лекции (разные) - часть 32
Санкт-Петербургский Государственный Технический Университет Факультет Технической Кибернетики Кафедра Системный Анализ и Управление Дата:_____________ Содержание 1.Постановка задачи............................................................................................…….2 2.Теоретическая часть………………………………………………………………..3 3.Решение……………………………………………………………………………..5 4.Алгоритм программы………………………………………………………………6 5.Результаты…………………………………………………………………………..7 6.Выводы……………………………………………………………………………...7 Приложение…………………………………………………………………………..8 1.Постановка задачи. Рассмотреть задачу об упаковке 20 гипотетических объектов в пять контейнеров. Объекты имеют оценки по пяти критериям Б,В,Г,Д,Е с порядковыми шкалами, имеющими три градации (первая - лучшая, вторая – средняя, третья - худшая), а также два физических параметра (вес и объем). Критерии имеют одинаковую значимость. Контейнеры имеют следующие параметры: · Грузоподъемность контейнера – 5 · Объем контейнера – 7 Далее приведены данные объектов: Номер Вес Обьем Б В Г Д Е 1 3 2 3 3 3 3 3 2 1 1 3 2 2 1 1 3 3 1 2 1 1 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 2 1 1 1 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. Алгоритм "в лучший из подходящих с убыванием". Алгоритм аналогичен "в лучший из подходящих", но объекты упорядочены от больших к меньшим. Упаковываемые объекты имеют оценки качества по многим критериям. Требуется упаковать максимальное число объектов, а не получить минимальное число контейнеров. Введем следующие обозначения:
vij
– j-й физический параметр i-го объекта; Vlj
– j-й физический параметр l-го контейнера; Ui
– общая ценность i-го объекта. Обозначим через I=1, 2, …, М множество номеров объектов, а через Множество тех упакованных объектов, для которых не найдется более ценных среди не упакованных. Формальная постановка задачи имеет следующий вид:
При ограничениях: Алгоритм решения поставленной задачи включает в себя алгоритмы решения вспомогательных задач: 1.Упаковка многомерных объектов в контейнеры; 2.Получение информации от ЛПР, позволяющей определить порядок упаковки многокритериальных объектов. 3.Решение задачи. 1. Путем попарного сравнения упаковываемых объектов определяется асимметричное транзитивное отношение доминирования:
где Q – количество критериев. 2. В соответствии с отношением P0 на множестве упаковываемых объектов можно выделить подмножество недоминируемых объектов. После их удаления можно выделить второе подмножество и т.д. до исчерпания множества. Выделенные подмножества называются паретовыми слоями. 3. Применяем алгоритм упаковки с отбрасыванием при чередовании, упаковывая по слоям объекты в контейнеры. К построенному квазипорядку упаковываемых объектов итеративно применяем алгоритм упаковки с отбрасыванием для послойной упаковки объектов. Пусть объекты первых (i–1)-го слоев упаковываются, а элементы i слоев не упаковываются. Среди объектов, входящих в первые (i=1) слои, выделяется подмножество лучших объектов, превосходящих каждый из остальных упаковываемых объектов (если таковое имеется). Это подмножество считается на данном этапе решения задачи подлежащим обязательной упаковке. Получим одну из возможных упаковок, наилучших с точки зрения О2.
Будем упаковывать, используя алгоритм с отбрасыванием при чередовании, объекты первых i слоев. Последовательно удаляем при упаковке объекты i-го слоя в соответствии с их порядком в списке с чередованием (от первых к последним) до получения упаковки. Если при этом в контейнерах остаются свободные места по всем физическим параметрам, то в рассмотрение включаются объекты (i+1)-го слоя, недоминируемые неупакованными объектами i-го слоя, и осуществляется доупаковка. Если и теперь остаются возможности, то аналогично осуществляется упаковка некоторыми объектами (i+2)-го слоя и т.д. В итоге получаем упаковку с максимальным значением критерия О2
. Получим теперь упаковку с максимальным значением критерия О1
. Применим алгоритм АОЧ ко всему множеству упаковываемых объектов. Не удаляются только упомянутые выше наилучшие объекты, доминирующие по качеству над всеми остальными (если таковые имеются). Ясно, что при этом получим упаковку с максимальным значением критерия О1
при условии сохранения доминирующих объектов. Рассматривая точки на плоскости О1
– О2
, ЛПР определить наилучший для себя компромисс между критериями О1
и О2
и тем самым наилучшую упаковку. 4.Алгоритм программы. Инициализация данных Разбиение на пар. слои Сорт. объем /вес Упаковка по слоям Упаковка объем/вес 5.Результаты. После выполнения программы получены следующие результаты. Программа распределила объекты из исходного списка по паретовым слоям. Ниже приведены эти слои (в таблице указаны номера эл-тов): Слой Номера объектов 1 20 2 3 6 15 19 3 2 8 9 10 11 12 17 18 4 4 5 7 13 14 16 5 1 Далее программа отсортировала список объектов по очередности макс.вес / макс.объем. 1 4 3 6 9 7 12 16 11 15 8 10 18 20 2 5 13 14 17 19 Ниже приведена таблица результатов упаковки (по алгоритму упаковки с отбрасыванием). Кол-во Σ Польза 14 123 10 83 Результаты можно отразить графически в виде плоскости критериев О1
(суммарное количество упакованных предметов), О2
(суммарная полезность упакованных элементов). 6.Выводы. В результате выполнения задания была написана программа, упаковывающая объекты в контейнеры. Упаковка производится с помощью двух вариантов упорядочивания объектов. По критерию О1
(кол-во упакованных) наиболее эффективен второй метод(есть варианты упаковки по 14 предметов). Например, были упакованы следующие 14 предметов: 16 11 15 8 10 18 20 2 5 13 14 17 19 7 О1
=14, О2
=130. По критерию О2
выигрывает первый метод. Упакованные объекты: 14 16 1 20 3 6 15 19 2 8 О1
=10, О2
=83. Оба метода позволяют ЛПР выбрать оптимальный вариант упаковки на плоскости критериев О1
,О2
. Приложение. Текст программы. Программа написана на языке программирования С++ в среде разработки Visual C++ 6.0. Выбор языка обусловлен наличием в его стандарте структуры данных – класс, с помощью которой удобно моделировать объекты задания. #include <stdlib.h> #include <fstream.h> #include "iostream.h" #include "stdio.h" class Object{ public: int Mass; int Cap; int vol[5]; int Val; bool Packed; int INN; bool NDom; Object(){ Mass = 0; Cap = 0; Packed = false; vol[0] = 0; vol[1] = 0; vol[2] = 0; vol[3] = 0; vol[4] = 0; Val=0; INN=0; NDom=false; }; void ObjectInit(int m, int c, int v1, int v2, int v3, int v4, int v5,int inn) { Mass=m; Cap=c; Packed=false; vol[0]=v1; vol[1]=v2; vol[2]=v3; vol[3]=v4; vol[4]=v5; Val= vol[0]+vol[1]+vol[2]+vol[3]+vol[4]; INN=inn; NDom=false; }; }; class Konteiner{ public: int Mass; int Cap; Konteiner(){ Mass = 0; Cap = 0; }; void KonteinerInit(int m, int c){ Mass = m; Cap = c; }; }; struct Result{ int Value; int Num; }; void main(){ Object Ob[21],ObD[400],ObND[400],ObRs,ObMC1[20],ObMC2[20],ObMC[21],ObMCRs[20]; Object ObSlice[10][10]; bool MFLAG[21]; Result Res[20],Res1[20]; Konteiner Kon[5]; Ob[0].ObjectInit(3,2,3,3,3,3,3, 1); Ob[1].ObjectInit(1,1,3,2,2,1,1, 2); Ob[2].ObjectInit(3,1,2,1,1,1,2, 3); Ob[3].ObjectInit(2,3,2,1,3,2,3, 4); Ob[4].ObjectInit(1,1,1,1,1,3,3, 5); Ob[5].ObjectInit(3,2,2,2,1,1,1, 6); Ob[6].ObjectInit(1,2,3,1,3,3,1, 7); Ob[7].ObjectInit(2,1,1,1,1,2,3, 8); Ob[8].ObjectInit(3,2,2,2,1,3,2, 9); Ob[9].ObjectInit(2,1,1,1,2,2,2,10); Ob[10].ObjectInit(1,2,3,3,1,1,1,11); Ob[11].ObjectInit(3,1,2,1,2,3,1,12); Ob[12].ObjectInit(1,1,2,2,3,3,1,13); Ob[13].ObjectInit(1,1,3,3,3,2,1,14); Ob[14].ObjectInit(2,2,1,2,2,1,1,15); Ob[15].ObjectInit(3,2,3,1,2,1,3,16); Ob[16].ObjectInit(1,1,2,1,2,1,2,17); Ob[17].ObjectInit(2,2,3,1,3,2,1,18); Ob[18].ObjectInit(1,1,1,1,1,2,1,19); Ob[19].ObjectInit(1,2,1,1,1,1,1,20); for (int i=0;i<5;i++){ Kon[i].KonteinerInit(5,7); }; MFLAG[0]=true; for(i=1;i<21;i++){ MFLAG[i]=false; }; bool flag,superflag; superflag=true; int counter=0; int j; while(counter!=10){ superflag=false; for(i=0;i<200;i++){ObND[i].ObjectInit(0,0,0,0,0,0,0,0);ObD[i].ObjectInit(0,0,0,0,0,0,0,0);}; j=0; for(int l=0;l<20;l++){ for(i=0;i<20;i++){ if((MFLAG[Ob[i].INN]==false)&&(MFLAG[Ob[l].INN]==false)&&(i!=l)&&(Ob[l].vol[0]>=Ob[i].vol[0])&&(Ob[l].vol[1]>=Ob[i].vol[1])&&(Ob[l].vol[2]>=Ob[i].vol[2])&&(Ob[l].vol[3]>=Ob[i].vol[3])&&(Ob[l].vol[4]>=Ob[i].vol[4])){ ObD[j]=Ob[l]; ObND[j]=Ob[i];j++;}else{ if((MFLAG[Ob[i].INN]==false)&(MFLAG[Ob[l].INN]==false)&&(i!=l)&&(Ob[l].vol[0]<=Ob[i].vol[0])&&(Ob[l].vol[1]<=Ob[i].vol[1])&&(Ob[l].vol[2]<=Ob[i].vol[2])&&(Ob[l].vol[3]<=Ob[i].vol[3])&&(Ob[l].vol[4]<=Ob[i].vol[4])){ ObD[j]=Ob[i]; ObND[j]=Ob[l];j++;}; }; }; }; j=0; for(l=0;l<200;l++){ flag=true; for(i=0;i<200;i++){ if(ObND[l].INN==ObD[i].INN){flag=false;}; }; if(flag&&(MFLAG[ObND[l].INN]!=true)){ObSlice[counter][j]=ObND[l];MFLAG[ObND[l].INN]=true;j++;}; }; counter++; }; for(counter=0;counter<10;counter++){ if(ObSlice[counter][0].INN==0){ObSlice[counter][0]=Ob[0];break;}; for( i=0;i<20;i++){ ObMC1[i] = Ob[i];}; for( j=0;j<20;j++){ for(i=19;i>j;i--){ if((ObMC1[i-1].Mass<ObMC1[i].Mass)){ ObRs=ObMC1[i]; ObMC1[i]=ObMC1[i-1]; ObMC1[i-1]=ObRs; }; }; }; for(i=0;i<20;i++){ ObMCRs[i]=ObMC1[i]; }; for(i=0;i<20;i++){ cout<<ObMCRs[i].INN<<" "; }; for( i=0;i<20;i++){ ObMC2[i] = Ob[i];}; for( j=0;j<20;j++){ for(i=19;i>j;i--){ if((ObMC2[i-1].Cap<ObMC2[i].Cap)){ ObRs=ObMC2[i]; ObMC2[i]=ObMC2[i-1]; ObMC2[i-1]=ObRs; }; }; }; cout<<"\n"; for(i=0;i<20;i++){ cout<<ObMC2[i].INN<<" "; }; flag=true; bool flag1=true; int n; int m=0; for(n=0;n<20;n++){ flag1=true; flag=true; for(j=0;j<20;j++){ if((ObMCRs[n].INN==ObMC2[n].INN)||(ObMCRs[n].INN==ObMC[j].INN)){flag1=false;}; }; for(j=0;j<20;j++){ if(ObMC2[n].INN==ObMC[j].INN){flag=false;}; }; if((flag1)&&(flag)){ ObMC[m]=ObMCRs[n]; ObMC[m+1]=ObMC2[n]; m=m+2; }; if((flag1)&&(!flag)){ ObMC[m]=ObMCRs[n]; m++; }; if((!flag1)&&(flag)){ ObMC[m]=ObMC2[n]; m++; }; if((!flag1)&&(!flag)){ }; }; cout<<"\n"; for(i=0;i<20;i++){ cout<<ObMC[i].INN<<" "; }; int l=0; m=0; flag=true; int countj=0; int counti=0; int lasti=0; int Value=0; int Num=0; int count=0; int countp=0; for(j=0;j<10,ObSlice[j][0].INN!=0;j++){ for(i=0;i<10,ObSlice[j][i].INN!=0;i++){ Ob[count]=ObSlice[j][i];count++;}; }; count=0; while ((count!=20)){ for(j=0;j<20;j++){ flag=true; for(m=0;m<5;m++){ if(flag&&(Ob[j].Cap<Kon[m].Cap)&&(Ob[j].Mass<Kon[m].Mass)){ Kon[m].Cap=Kon[m].Cap-Ob[j].Cap; Kon[m].Mass=Kon[m].Mass-Ob[j].Mass; Value=Value+Ob[j].Val; Num=Num++; Ob[j].Packed=true; flag=false; }; }; }; Ob[20]=Ob[0]; for(i=1;i<21;i++){Ob[i-1]=Ob[i];}; Res[count].Value=Value; Res[count].Num=Num; if(count==0){ cout<<"\n"; for(i=0;i<20;i++){ if(Ob[i].Packed){cout<<Ob[i].INN<<" ";}; }; }; count++; for(j=0;j<10;j++){ Ob[j].Packed=false; }; Value=0; Num=0; for(m=0;m<5;m++){ Kon[m].KonteinerInit(5,7); }; }; cout<<"\n"; flag=true; countj=0; counti=0; lasti=0; Value=0; Num=0; count=1; countp=0; while ((countj!=20)){ for(j=0;j<20;j++){ flag=true; for(m=0;m<5;m++){ if(flag&&(ObMC[j].Cap<Kon[m].Cap)&&(ObMC[j].Mass<Kon[m].Mass)){ Kon[m].Cap=Kon[m].Cap-ObMC[j].Cap; Kon[m].Mass=Kon[m].Mass-ObMC[j].Mass; Value=Value+ObMC[j].Val; Num++; ObMC[j].Packed=true; flag=false; }; }; }; ObMC[20]=ObMC[0]; for(j=1;j<21;j++){ObMC[j-1]=ObMC[j];}; if(countj==8){ cout<<"\n"; for(i=0;i<20;i++){ if(ObMC[i].Packed){cout<<ObMC[i].INN<<" ";}; }; }; for(j=0;j<20;j++){ ObMC[j].Packed=false; }; Res1[countj].Value=Value; Res1[countj].Num=Num; countj++; Value=0; Num=0; for(m=0;m<5;m++){ Kon[m].KonteinerInit(5,7); }; }; ofstream out("out.txt",ios::out|ios::trunc); out<<" Итоговые данные после упаковки: \n"; out<<"Сортировка по Пар. сл.: Сортировка вес.объем:\n"; out<<"Ценность Кол-во Ценность Кол-во \n"; for(i=0;i<20;i++){ cout<<Res[i].Value<<" "<<Res[i].Num<<" "; cout<<Res1[i].Value<<" "<<Res1[i].Num<<" \n"; out<<Res[i].Value<<" "<<Res[i].Num<<" "; out<<Res1[i].Value<<" "<<Res1[i].Num<<" \n"; }; char ch; cout<<"Press a key\n"; cin>>ch; } |