Задача об упаковке (стр. 2 из 2)
Получим теперь упаковку с максимальным значением критерия О1.
Применим алгоритм АОЧ ко всему множеству упаковываемых объектов. Не удаляются только упомянутые выше наилучшие объекты, доминирующие по качеству над всеми остальными (если таковые имеются). Ясно, что при этом получим упаковку с максимальным значением критерия О1 при условии сохранения доминирующих объектов. Рассматривая точки на плоскости О1 – О2, ЛПР определить наилучший для себя компромисс между критериями О1 и О2 и тем самым наилучшую упаковку.
4.Алгоритм программы.
 | |||||
 | |||||
| Разбиение на пар. слои |
| Сорт. объем /вес |
| Упаковка по слоям |
| Упаковка объем/вес |
| Слой | Номера объектов | |||||||
| 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;
}