Рис. 5.3.1 Объекты и контейнеры.

На рис. 5.3.2 приведены сформированные слои Парето, выделенные из исходного множества на основании предпочтений ЛПР. Объекты внутри слоёв отсортированы по полезности. Полезность объекта при упаковке прямо пропорциональна значениям оценок по критериям и обратно пропорциональна массе и объёму.

Рис. 5.3.2 Слои Парето, отсортированные по полезности.

На рис. 5.3.3 показаны слои Парето, отсортированные по объёму и массе.

Рис. 5.3.3 Слои Парето, отсортированные по объёму и массе.

Результаты упаковки для сортировки по полезности и по объёму и массе показаны на рисунках 5.3.4 и 5.3.5 соответственно.

Рис. 5.3.4 Результат упаковки при сортировке по полезности.

Рис. 5.3.5 Результат упаковки при сортировке по объёму и весу.

Заключение

В процессе работы над дипломным проектом разработана и написана программа, реализующая процесс упаковки предметов с заданными параметрами (масса и объем) по контейнерам в условиях недостаточности контейнеров для упаковки всех предметов. После процесса упаковки возможен просмотр полученных данных (результатов) в виде текстовой информации. В ходе выполнения работы были описаны методы оценки многомерных альтернатив и один из методов решения многокритериальных задач.

Было рассмотрено и решено два варианта задачи об упаковке. В первом случае полученная информация позволяет определить порядок упаковки многокритериальных объектов, а во втором позволяет определить, каким образом можно упаковать парные объекты.

Список использованных источников

1. Ногин В.Д. Принятие решений в многокритериальной среде: количественный подход, М.: ФИЗМАТЛИТ, 2004, 176с.

2. Ларичев О.И. Объективные модели и субъективные решения. М.: Изд-во "Наука", 1987. 480с.

3. П. Ноутон, Г. Шилдт Java 2 в подлиннике, БХВ-Петербург, 2008 г., 1072 стр.

Приложения

Приложение 1

Классы предметной области.

При чтении кода рекомендуется обращать внимание на комментарии (текст после последовательностей " // " и между последовательностями "/**" и "*/"). Код, к которому относится конкретный комментарий, расположен ниже него.

Класс "Упаковываемый объект". Параметры этого класса - ID, объём, вес, оценки по пяти критериям и ссылка на парный объект.

/**

* Упаковываемый объект.

* @author AtemB

*

*/

public class Item {

/** ID. */

String id;

/** Объём. */

int volume;

/** Вес. */

int weight;

/** Критерий 1. */

int rate1;

/** Критерий 2. */

int rate2;

/** Критерий 3. */

int rate3;

/** Критерий 4. */

int rate4;

/** Критерий 5. */

int rate5;

/** Ссылка на парный объект. */

private Item pair;

public Item (String id,

int volume,

int weight,

int rate1,int rate2,int rate3,int rate4,int rate5) {

super ();

this. id = id;

this. volume = volume;

this. weight = weight;

this. rate1 = rate1;

this. rate2 = rate2;

this. rate3 = rate3;

this. rate4 = rate4;

this. rate5 = rate5;

}

/***/

public Item () {

this. id = 0 + "";

this. volume = 0;

this. weight = 0;

this. rate1 = 0;

this. rate2 = 0;

this. rate3 = 0;

this. rate4 = 0;

this. rate5 = 0;

}

public String getId () {

return id;

}

public Item getPair () {

return pair;

}

public void setPair (Item pair) {

this. pair = pair;

}

public boolean hasPair () {

return pair! = null;

}

/**

* @return the volume

*/

public int getVolume () {

return volume;

}

/**

* @return the weight

*/

public int getWeight () {

return weight;

}

/**

* @return the rate1

*/

public int getRate1 () {

return rate1;

}

/**

* @return the rate2

*/

public int getRate2 () {

return rate2;

}

/**

* @return the rate3

*/

public int getRate3 () {

return rate3;

}

/**

* @return the rate4

*/

public int getRate4 () {

return rate4;

}

/**

* @return the rate5

*/

public int getRate5 () {

return rate5;

}

/**

* @param volume the volume to set

*/

public void setVolume (int volume) {

this. volume = volume;

}

/**

* @param weight the weight to set

*/

public void setWeight (int weight) {

this. weight = weight;

}

/**

* @param rate1 the rate1 to set

*/

public void setRate1 (int rate1) {

this. rate1 = rate1;

}

/**

* @param rate2 the rate2 to set

*/

public void setRate2 (int rate2) {

this. rate2 = rate2;

}

/**

* @param rate3 the rate3 to set

*/

public void setRate3 (int rate3) {

this. rate3 = rate3;

}

/**

* @param rate4 the rate4 to set

*/

public void setRate4 (int rate4) {

this. rate4 = rate4;

}

/**

* @param rate5 the rate5 to set

*/

public void setRate5 (int rate5) {

this. rate5 = rate5;

}

/* (non-Javadoc)

* @see java. lang. Object#equals (java. lang. Object)

*/

@Override

public boolean equals (Object obj) {

if (this == obj) {

return true;

}

if (obj == null) {

return false;

}

if (! (obj instanceof Item)) {

return false;

}

Item other = (Item) obj;

if (rate1! = other. rate1) {

return false;

}

if (rate2! = other. rate2) {

return false;

}

if (rate3! = other. rate3) {

return false;

}

if (rate4! = other. rate4) {

return false;

}

if (rate5! = other. rate5) {

return false;

}

if (volume! = other. volume) {

return false;

}

if (Double. doubleToLongBits (weight)! = Double

. doubleToLongBits (other. weight)) {

return false;

}

return true;

}

@Override

public Item clone () {

Item clone = new Item (id, volume, weight, rate1, rate2, rate3, rate4, rate5);

return clone;

}

/* (non-Javadoc)

* @see java. lang. Object#toString ()

*/

@Override

public String toString () {

return "Объект" +

"\nID: " + id + ",\nОбъём: " + volume + ",\nВес: " + weight

+ ",\nКр.1: " + rate1 + ",\nКр.2: " + rate2 + ",\nКр.3: " + rate3

+ ",\nКр.4: " + rate4 + ",\nКр.5" + rate5 + ",\nID парного объекта: " + pair. id;

}

Класс "Контейнер". Его параметры - это ID, объём и грузоподъёмность.

/**

* Контейнер.

* @author AtemB

*

*/

public class Container {

/** ID. */

private int id;

/** Объём. */

private int volume;

/** Грузоподъёмность. */

private int cargo;

public Container (int id, int volume, int cargo) {

this. id = id;

this. volume = volume;

this. cargo = cargo;

}

public int getVolume () {

return volume;

}

public int getCargo () {

return cargo;

}

public int getId () {

return id;

}

/**

* @param volume the volume to set

*/

public void setVolume (int volume) {

this. volume = volume;

}

/**

* @param cargo the cargo to set

*/

public void setCargo (int cargo) {

this. cargo = cargo;

}

/**

* @param id the id to set

*/

public void setId (int id) {

this. id = id;

}

@Override

public Container clone () {

Container clone = new Container (id, volume, cargo);

return clone;

}

/* (non-Javadoc)

* @see java. lang. Object#toString ()

*/

@Override

public String toString () {

return "Контейнер" +

",\nID: " + id +

"\nОбъём: " + volume +

",\nГрузоподъёмность: " + cargo;

}

}

Класс ЛПР. У этого класса всего одно поле - список весов критериев, используемая им при расчёте полезности объекта. ЛПР умеет сравнивать объекты, используя вложенный класс "Бинарное отношение", умеет отображать пару объектов в один объект и получать значение полезности любого объекта. Для ЛПР в данном случае полезность объекта прямо пропорциональна значениям оценок по критериям объекта и обратно пропорциональна его массе и объёму.

/**

* ЛПР (лицо, принимающее решения).

* @author AtemB

*

*/

public class Boss {

class BossBinaryRelation implements BinaryRelation<Item> {

@Override

public Item compare (Item i1, Item i2) {

// Конечно, не самая пряморукая реализация, зато относительно понятна для восприятия.

// В этот список заносятся разности оценок по критериям.

List<Double> rates = new LinkedList<Double> ();

rates. add ( (double) (i1. rate1 - i2. rate1));

rates. add ( (double) (i1. rate2 - i2. rate2));

// Флаги в этом списке означают, положителен или отрицателен

// результат сравнения критериев.

// Одинаковые значения в список не заносятся.

List<Boolean> flags = new LinkedList<Boolean> ();

for (Double d: rates) {

if (d. doubleValue () > 0) {

flags. add (true);

} else if (d. doubleValue () < 0) {

flags. add (false);

}

}

// Если спиок флагов пуст, значит, объекты по проверяемым критериям равны.

if (flags. isEmpty ()) {

return null;

} else {

boolean resultFlag = false;

for (int i = 1; i < flags. size (); i++) {

resultFlag = flags. get (i);

// Если в списке встречаются разные значения флагов, значит,

// объекты несравнимы по значимым критериям

// (один лучше по одним критериям, другой по другим).

if (flags. get (i - 1)! = flags. get (i)) {

return null;

}

}

// Если предыдущий цикл выполнился до конца, значит,

// один из объектов оказался лучше другого.

// Проверяем значение результирующего флага

// и возвращаем доминирующий объект.

if (resultFlag) {

return i1;

} else {

return i2;

}

}

}

}

private List<Double> weights;

public Boss () {

weights = new ArrayList<Double> ();

{

weights. add (0.45);

weights. add (0.45);

weights. add (0.04);

weights. add (0.04);

weights. add (0.02);

}

}

/**

* Получить полезность объекта.

* @param i Объект.

* @return Оценка объекта.

*/

public double getUtility (Item i) {

double ratesSum = i. rate1 * weights. get (0) +

i. rate2 * weights. get (1) +

i. rate3 * weights. get (2) +

i. rate4 * weights. get (3) +

i. rate5 * weights. get (4);

return ratesSum / i. weight / i. volume; // ( (i. weight + i. volume) / 2);

}

/**

* Отобразить пару объектов в один объект.

* @param i Любой объект из пары.

* @return Результирующий объект.

*/

public static Item mapPair (Item i) {

Item first = i;

Item second = i. getPair ();

Item resultItem = new Item (first. id + ": " + second. id,

first. volume + second. volume,

first. weight + second. weight,

first. rate1 + second. rate1,first. rate2 + second. rate2,first. rate3 + second. rate3,first. rate4 + second. rate4,first. rate5 + second. rate5);

return resultItem;

}

/**

* Получить бинарное отношение, определённое ЛПР.

* @return Бинарное отношение.

*/

public BinaryRelation<Item> getBinaryRelation () {

return new BossBinaryRelation ();

}

}

Класс "Склад". Его поля - список упаковываемых объектов, список контейнеров, сформированные слои Парето (при создании объекта это поле равно null), карта упакованных объектов и остаток, представляющий из себя список объектов. Также есть поле типа java. math. Random, использующееся при инициализации упаковываемых объектов и контейнеров.

/**

* Склад.

* @author AtemB

*

*/

public class Store {

class MapKeysComparator implements Comparator<Container> {

@Override

public int compare (Container c1, Container c2) {

return c1. getId () - c2. getId ();

}

}

private List<Item> items;

private List<Container> containers;

private Random r = new Random ();

private List<List<Item>> paretoSet;

private SortedMap<Container, List<Item>> map;

private List<Item> rest;

public Store () {

containers = new ArrayList<Container> ();

items = new ArrayList<Item> ();

rest = new ArrayList<Item> ();

map = new TreeMap<Container, List<Item>> (new MapKeysComparator ());

}

public void createContainers (int containersNum, ContainerTemplate ct, int maxVolume, int maxCargo) {

Random r = new Random ();

int volumeDiapasonLength = maxVolume - ct. getVolume (). getBegin ();

int cargoDiapasonLength = maxCargo - ct. getCargo (). getBegin ();

for (int i = 0; i < containersNum; i++) {

containers. add (new Container (i,

r. nextInt (volumeDiapasonLength + 1) + ct. getVolume (). getBegin (),

r. nextInt (cargoDiapasonLength + 1) + ct. getCargo (). getBegin ()));

}

for (Container c: containers) {

map. put (c, new LinkedList<Item> ());

}

}

public void createItems (int itemsNum, ItemTemplate it, int maxVolume, int maxWeight) {

int volumeDiapasonLength = maxVolume - it. getVolume (). getBegin ();

int weightDiapasonLength = maxWeight - it. getWeight (). getBegin ();

int r1DiapasonLength = it. getRate1 (). getEnd () - it. getRate1 (). getBegin ();

int r2DiapasonLength = it. getRate2 (). getEnd () - it. getRate2 (). getBegin ();

int r3DiapasonLength = it. getRate3 (). getEnd () - it. getRate3 (). getBegin ();

int r4DiapasonLength = it. getRate4 (). getEnd () - it. getRate4 (). getBegin ();

int r5DiapasonLength = it. getRate5 (). getEnd () - it. getRate5 (). getBegin ();

for (int i = 0; i < itemsNum; i++) {

items. add (new Item (i + "", r. nextInt (volumeDiapasonLength + 1) + it. getVolume (). getBegin (),

r. nextInt (weightDiapasonLength + 1) + it. getWeight (). getBegin (),

r. nextInt (r1DiapasonLength + 1) + it. getRate1 (). getBegin (),

r. nextInt (r2DiapasonLength + 1) + it. getRate2 (). getBegin (),

r. nextInt (r3DiapasonLength + 1) + it. getRate3 (). getBegin (),

r. nextInt (r4DiapasonLength + 1) + it. getRate4 (). getBegin (),

r. nextInt (r5DiapasonLength + 1) + it. getRate5 (). getBegin ()));

}

}

/**

* @return the containers

*/

public List<Container> getContainers () {

return containers;

}

/**

* @return the items

*/

public List<Item> getItemsClones () {

List<SimpleEntry<String, String>> itemPairs = new ArrayList<SimpleEntry<String, String>> ();

List<Item> newItems = new ArrayList<Item> ();

for (Item i: items) {

newItems. add (i. clone ());

if (i. hasPair ()) {

itemPairs. add (new SimpleEntry<String, String> (i. getId (), i. getPair (). getId ()));

}

}

for (Entry<String, String> e: itemPairs) {

getItemFromListByID (e. getKey (), newItems). setPair (getItemFromListByID (e. getValue (), newItems));

}

return newItems;

}

public List<Item> getItemsInstance () {

return items;

}

public void setEmpty () {

items. clear ();

containers. clear ();

}

/**

* @return the paretoSet

*/

public List<List<Item>> getParetoSetInstance () {

return paretoSet;

}

/**

* @return the paretoSet

*/

public List<List<Item>> getParetoSetClone () {

List<List<Item>> clone = new ArrayList<List<Item>> ();

List<SimpleEntry<String, String>> itemPairs = new ArrayList<SimpleEntry<String, String>> ();

for (List<Item> paretoLayer: paretoSet) {

List<Item> newParetoLayer = new ArrayList<Item> ();

for (Item i: paretoLayer) {

newParetoLayer. add (i. clone ());

if (i. hasPair ()) {

itemPairs. add (new SimpleEntry<String, String> (i. getId (), i. getPair (). getId ()));

}

}

clone. add (newParetoLayer);

}

for (Entry<String, String> e: itemPairs) {

getItemFromParetoSetByID (e. getKey (), clone). setPair (getItemFromParetoSetByID (e. getValue (), clone));

}

return clone;

}

/**

* @param paretoSet the paretoSet to set

*/

public void setParetoSet (List<List<Item>> paretoSet) {

this. paretoSet = paretoSet;

}

private Item getItemFromListByID (String id, List<Item> items) {

for (Item i: items) {

if (i. getId (). equals (id)) {

return i;

}

}

return null;

}

private Item getItemFromParetoSetByID (String id, List<List<Item>> paretoSet) {

for (List<Item> items: paretoSet) {

for (Item i: items) {

if (i. getId (). equals (id)) {

return i;

}

}

}

return null;

}

/**

* @return the map

*/

public SortedMap<Container, List<Item>> getMapInstance () {

return map;

}

/**

* @return the map

*/

public SortedMap<Container, List<Item>> getMapClone () {

SortedMap<Container, List<Item>> clone = new TreeMap<Container, List<Item>> (new MapKeysComparator ());

Set<Entry<Container, List<Item>>> set = map. entrySet ();

for (Entry<Container, List<Item>> e: set) {

List<Item> items = new ArrayList<Item> ();

for (Item i: e. getValue ()) {

items. add (i. clone ());

}

clone. put (e. getKey (). clone (), items);

}

return clone;

}

/**

* @param map the map to set

*/

public void setMap (SortedMap<Container, List<Item>> map) {

this. map = map;

}

public boolean paretoSetIsEmpty () {

boolean result = false;

return result;

}

/**

* @return the rest

*/

public List<Item> getRest () {

return rest;

}

/**

* @param rest the rest to set

*/

public void setRest (List<Item> rest) {

this. rest = rest;

}

}

Класс Упаковщик. Поля этого класса - ЛПР и Склад. Также в нём объявлены два перечисления, в которых указаны тип сортировки объектов и алгоритм упаковки. Этот класс оперирует с упаковываемыми объектами на основе информации ЛПР (обрабатывает парные объекты, создаёт слои Парето), сортирует указанным образом, и упаковывает объекты.

/**

* Упаковщик.

* @author AtemB

*

*/

public class Packer {

/**

* Алгоритм упаковки.

* @author AtemB

*

*/

public enum ALGORYTHM {

/** В первый подходящий. */

FIRST,

/** В первый подходящий с убыванием. */

FIRST_DECREASE,

/** В лучший из подходящих. */

BEST,

/** В лучший из подходящих с убыванием. */

BEST_DECREASE

}

/**

* Тип сортировки.

* @author AtemB

*

*/

public enum SORT_TYPE {

/** По весу. */

WEIGHT,

/** По объёму. */

VOLUME,

/** По полезности. */

UTILITY,

/** По величине. */

SIZE

}

private Store store;

private Boss boss;

public Packer (Store store, Boss boss) {

this. store = store;

this. boss = boss;

}

public void breakPair (Item i1, Item i2) {

i1. setPair (null);

i2. setPair (null);

}

public void createPair (Item i1, Item i2) {

i1. setPair (i2);

i2. setPair (i1);

}

/**

* Обработать парные объекты.

* @param items Исходное множество объектов.

* @return Результирующее множество объектов.

*/

public List<Item> processPairs (List<Item> items) {

List<Item> listForRemove = new ArrayList<Item> ();

// Отображаем все пары в монолитные объекты.

for (int i = 0; i < items. size (); i++) {

Item current = items. get (i);

if (current. hasPair ()) {

// Помещаем парный текущему объект в список на удаление,

// т.к. теперь его параметры будут отражены в результирующем объекте.

listForRemove. add (current. getPair ());

Item resultItem = Boss. mapPair (current);

// Замещаем исходный объект по текущему индексу результирующим.

items. set (i, resultItem);

current. getPair (). setPair (null);

}

}

// Удаляем парные объекты из списка.

for (Item i: listForRemove) {

items. remove (i);

}

return items;

}

/**

* Создать слой Парето.

* @param boss ЛПР.

* @param items Исходное множество.

* @return Слой парето.

*/

public List<Item> extractParetoLayer (List<Item> items) {

BinaryRelation<Item> relation = boss. getBinaryRelation ();

if (items. isEmpty ()) {

return null;

} else {

// Сначала извлекаем первый попавшийся недоминируемый объект на исходном множестве.

List<Item> bestItems = new ArrayList<Item> ();

Item best = items. get (0);

for (Item i: items) {

// Сравниваем текущий элемент с каждым из элементов последовательности.

// Если новый элемент лучше текущего - инициализируем им ссылку на лучший объект.

if (relation.compare (best, i) == i) {

best = i;

}

}

// Удаляем недоминируемый объект из исходного множества.

items. remove (best);

// Добавляем его в слой Парето.

bestItems. add (best);

// Теперь нужно найти все несравнимые с ним элементы исходного множества.

List<Item> equalItems = new ArrayList<Item> ();

for (Item i: items) {

// Если очередной элемент несравним с ранее полученным лучшим,

// добавляем его в результирующее множество.

if (relation.compare (best, i) == null) {

equalItems. add (i);

}

}

// Удаляем из исходного множества все ссылки на недоминируемые объекты.

for (Item i: equalItems) {

items. remove (i);

}

// Добавляем недоминируемые объекты в слой Парето.

for (Item i: equalItems) {

bestItems. add (i);

}

return bestItems;

}

}

/**

* Получить множества (слои) Парето.

* @param boss ЛПР.

* @param items Исходное множество.

* @return Слои Парето.

*/

public List<List<Item>> createParetoSet (List<Item> items) {

List<List<Item>> layers = new ArrayList<List<Item>> ();

while (! (items. isEmpty ())) {

List<Item> paretoLayer = extractParetoLayer (items);

layers. add (paretoLayer);

}

return layers;

}

/**

* Упаковать очередной слой Парето. Инкапсулирует логику алгоритма упаковки.

* @param map Карта, содержащая информацию о контейнерах и об упакованных объектах.

* @param paretoLayer Слой Парето.

* @return Ту же карту с очередным добавленным слоем.

*/

public SortedMap<Container, List<Item>> pack (SortedMap<Container, List<Item>> map, List<Item> paretoLayer, ALGORYTHM algorythm) {

// Получаем массу и объём слоя Парето.

double layerWeight = 0.0;

double layerVolume = 0.0;

for (Item i: paretoLayer) {

layerWeight += i. weight;

layerVolume += i. volume;

}

if (algorythm == ALGORYTHM. FIRST_DECREASE || algorythm == ALGORYTHM. BEST_DECREASE) {

sort (paretoLayer, SORT_TYPE. SIZE);

}

// Если он в полном составе не упаковывается, его нужно сортировать по эффективности.

if (layerWeight > getFreeCargo (map) ||

layerVolume > getFreeSpace (map)) {

sort (paretoLayer, Packer. SORT_TYPE. UTILITY);

}

List<Item> forRemove = new ArrayList<Item> ();

for (Item item: paretoLayer) {

if (! tryToPack (map, item, algorythm)) {

store. getRest (). add (item);

forRemove. add (item);

}

}

for (Item i: forRemove) {

paretoLayer. remove (i);

}

return map;

}

/**

* Попробовать паковать объект.

* @param map

* @param item Объект.

* @return Флаг удачного завершения операции.

*/

private boolean tryToPack (SortedMap<Container, List<Item>> map, Item item, ALGORYTHM algorythm) {

Set<Container> containers = map. keySet ();

if (algorythm == ALGORYTHM. BEST || algorythm == ALGORYTHM. BEST_DECREASE) {

Container bestContainer = getBest (containers, item, map);

if (bestContainer == null) {

return false;

} else {

map. get (bestContainer). add (item);

return true;

}

}

for (Container container: containers) {

if (canPack (container, item, map)) {

map. get (container). add (item);

return true;

}

}

return false;

}

/**

* Получить свободное место в контейнерах.

* @param map Карта, содержащая информацию о контейнерах и об упакованных объектах.

* @return Свободное место.

*/

private double getFreeSpace (SortedMap<Container, List<Item>> map) {

double freeSpace = 0.0;

for (Container c: map. keySet ()) {

double itemsVolume = 0.0;

for (Item i: map. get (c)) {

itemsVolume += i. volume;

}

freeSpace += (c. getVolume () - itemsVolume);

}

return freeSpace;

}

/**

* Получить оставшуюся грузоподъёмность контейнеров.

* @param map Карта, содержащая информацию о контейнерах и об упакованных объектах.

* @return Оставшуюся грузоподъёмность контейнеров.

*/

private double getFreeCargo (SortedMap<Container, List<Item>> map) {

double freeCargo = 0.0;

for (Container c: map. keySet ()) {

double itemsWeight = 0.0;

for (Item i: map. get (c)) {

itemsWeight += i. weight;

}

freeCargo += (c. getCargo () - itemsWeight);

}

return freeCargo;

}

/**

* Проверить возможность упаковки объекта в контейнер.

* @param c Контейнер.

* @param i Объект.

* @param map Карта, содержащая информацию об упакованных объектах.

* @return Флаг проверки.

*/

private boolean canPack (Container c, Item i, SortedMap<Container, List<Item>> map) {

// Получаем список объектов, упакованных в этот контейнер.

List<Item> items = map. get (c);

int totalVolume = 0;

double totalWeight = 0.0;

// Получаем суммарный вес и объём объектов, упакованных в этот контейнер.

for (Item item: items) {

totalVolume += item. volume;

totalWeight += item. weight;

}

// Если масса или объём проверяемого объекта

// больше оставшейся грузоподъёмности

// или свободного места в контейнере,

// объект в него упаковать нельзя.

if (c. getVolume () - totalVolume < i. volume ||

c. getCargo () - totalWeight < i. weight) {

return false;

}

return true;

}

/**

* Создать парные объекты на исходном множестве.

* @param pairsNum Необходимое количество пар.

* @param items Исходное множество.

*/

public void createPairs (int pairsNum, List<Item> items) {

Random r = new Random ();

int pairCounter = 0;

while (pairCounter < pairsNum) {

findPair (items. get (r. nextInt (items. size ())), items);

pairCounter = countPairs (items);

}

}

/**

* Найти парный объект.

* @param i Объект, для которого ищется парный объект.

* @param items Исходное множество.

*/

private void findPair (Item i, List<Item> items) {

if (! (i. hasPair ())) {

Random r = new Random ();

Item pair;

do {

pair = items. get (r. nextInt (items. size ()));

} while (pair. hasPair () || pair == i);

i. setPair (pair);

pair. setPair (i);

}

}

/**

* Сосчитать парные объекты.

* @param items Исходное множество.

* @return Количество пар.

*/

public int countPairs (List<Item> items) {

int pairsCounter = 0;

for (Item i: items) {

if (i. hasPair ()) {

pairsCounter++;

}

}

return pairsCounter / 2;

}

/**

* Извлечь наиболее тяжёлый объект. <p>

* Полученный объект удаляется из списка.

* @param items Список объектов.

* @return Самый тяжёлый объект.

*/

public Item extractHardest (List<Item> items) {

Item hardest = items. get (0);

for (Item i: items) {

if (i. weight > hardest. weight) {

hardest = i;

}

}

items. remove (hardest);

return hardest;

}

/**

* Извлечь наиболее объёмный объект. <p>

* Полученный объект удаляется из списка.

* @param items Список объектов.

* @return Самый объёмный объект.

*/

public Item extractLargest (List<Item> items) {

Item largest = items. get (0);

for (Item i: items) {

if (i. volume > largest. volume) {

largest = i;

}

}

items. remove (largest);

return largest;

}

public void sort (List<Item> items, SORT_TYPE. template) {

int itemsSize = items. size ();

int templateLength = template. length;

for (int i = 0; i < itemsSize; i++) {

SORT_TYPE type = template [i % templateLength];

for (int j = i; j < itemsSize; j++) {

for (int k = i; k < itemsSize; k++) {

switch (type) {

case VOLUME:

if (items. get (j). volume < items. get (k). volume) {

Item buffer = items. get (j);

items. set (j, items. get (k));

items. set (k, buffer);

}

break;

case WEIGHT:

if (items. get (j). weight < items. get (k). weight) {

Item buffer = items. get (j);

items. set (j, items. get (k));

items. set (k, buffer);

}

break;

case UTILITY:

if (boss. getUtility (items. get (j)) < boss. getUtility (items. get (k))) {

Item buffer = items. get (j);

items. set (j, items. get (k));

items. set (k, buffer);

}

break;

case SIZE:

if (countSize (items. get (j)) > countSize (items. get (k))) {

Item buffer = items. get (j);

items. set (j, items. get (k));

items. set (k, buffer);

}

break;

default:

break;

}

}

}

}

}

/**

* Рассчитать размер. Расчёт производится по массе и объёму.

* @param i Объект.

*/

private double countSize (Item i) {

return i. volume * i. weight;

}

/**

* Получить лучший контейнер из подходящих. <p>

* Лучшим контейнер с минимальным свободным местом (грузоподъёмность или объём) под упаковку объекта.

* @param containers Контейнеры.

* @param i Объект.

* @param map Карта упаковки.

* @return Лучший контейнер.

*/

private Container getBest (Collection<Container> containers, Item i, SortedMap<Container, List<Item>> map) {

return getValid (getValidContainers (containers, i, map), i, map);

}

/**

* Получить контейнеры, пригодные для упаковки объекта.

* @param containers Контейнеры.

* @param i Объект.

* @param map Карта упаковки.

* @return Список контейнеров, в которые можно упаковать объект.

*/

private List<Container> getValidContainers (Collection<Container> containers, Item i, SortedMap<Container, List<Item>> map) {

List<Container> validContainers = new ArrayList<Container> ();

for (Container c: containers) {

if (canPack (c, i, map)) {

validContainers. add (c);

}

}

return validContainers;

}

/**

* Получить контейнер, в котором осталось наименьшее количество места для упаковки объекта.

* @param containers Контейнеры.

* @param i Объект.

* @param map Карта упаковки.

* @return Контейнер.

*/

private Container getValid (List<Container> containers, Item i, SortedMap<Container, List<Item>> map) {

double minimalRests = 0;

for (Container c: containers) {

double rests = getRests (c, i, map);

if (rests > minimalRests) {

minimalRests += rests;

}

}

for (Container c: containers) {

double rests = getRests (c, i, map);

if (rests == 0) {

return c;

}

if (rests < minimalRests) {

minimalRests = rests;

}

}

for (Container c: containers) {

if (getRests (c, i, map) == minimalRests) {

return c;

}

}

return null;

}

/**

* Получить остаток. <p>

* Остатком считается наименьшее значение из остатка по грузоподъёмности или остатка по объёму.

* @param c Контейнер.

* @param i Объект.

* @param map Карта упаковки.

* @return Остаток.

*/

private double getRests (Container c, Item i, SortedMap<Container, List<Item>> map) {

double totalVolume = 0;

double totalWeight = 0;

for (Item item: map. get (c)) {

totalVolume += item. volume;

totalWeight += item. weight;

}

double volumeRests = c. getVolume () - totalVolume;

double cargoRests = c. getCargo () - totalWeight;

if (volumeRests < cargoRests) {

return volumeRests;

} else if (cargoRests < volumeRests) {

return cargoRests;

}

return 0;

}

}

Также в программе присутствуют классы графического интерфейса и отдельный класс, содержащий метод main ().

Полный исходный код программы.

Исходный код программы на Java.

Пакет core.

BinaryRelation. java

package core;

/**

* Бинарное отношение.

* @author AtemB

*

* @param <T> Тип элементов множества.

*/

public interface BinaryRelation<T> {

/**

* Сравнить два элемента множества. Этот метод инкапсулирует логику бинарного отношения.

* @param t1 Первый элемент.

* @param t2 Второй элемент.

* @return Доминирующий элемент или null, если элементы несравнимы.

*/

public T compare (T t1, T t2);

}

Boss. java

package core;

import java. util. ArrayList;

import java. util. LinkedList;

import java. util. List;

import java. util. Map;

/**

* ЛПР (лицо, принимающее решения).

* @author AtemB

*

*/

public class Boss {

class BossBinaryRelation implements BinaryRelation<Item> {

@Override

public Item compare (Item i1, Item i2) {

// Конечно, не самая пряморукая реализация, зато относительно понятна для восприятия.

// В этот список заносятся разности оценок по критериям.

List<Double> rates = new LinkedList<Double> ();

rates. add ( (double) (i1. rate1 - i2. rate1));

rates. add ( (double) (i1. rate2 - i2. rate2));

// Флаги в этом списке означают, положителен или отрицателен

// результат сравнения критериев.

// Одинаковые значения в список не заносятся.

List<Boolean> flags = new LinkedList<Boolean> ();

for (Double d: rates) {

if (d. doubleValue () > 0) {

flags. add (true);

} else if (d. doubleValue () < 0) {

flags. add (false);

}

}

// Если спиок флагов пуст, значит, объекты по проверяемым критериям равны.

if (flags. isEmpty ()) {

return null;

} else {

boolean resultFlag = false;

for (int i = 1; i < flags. size (); i++) {

resultFlag = flags. get (i);

// Если в списке встречаются разные значения флагов, значит,

// объекты несравнимы по значимым критериям

// (один лучше по одним критериям, другой по другим).

if (flags. get (i - 1)! = flags. get (i)) {

return null;

}

}

// Если предыдущий цикл выполнился до конца, значит,

// один из объектов оказался лучше другого.

// Проверяем значение результирующего флага

// и возвращаем доминирующий объект.

if (resultFlag) {

return i1;

} else {

return i2;

}

}

}

}

private List<Double> weights;

public Boss () {

weights = new ArrayList<Double> ();

{

weights. add (0.45);

weights. add (0.45);

weights. add (0.04);

weights. add (0.04);

weights. add (0.02);

}

}

/**

* Получить полезность объекта.

* @param i Объект.

* @return Оценка объекта.

*/

public double getUtility (Item i) {

double ratesSum = i. rate1 * weights. get (0) +

i. rate2 * weights. get (1) +

i. rate3 * weights. get (2) +

i. rate4 * weights. get (3) +

i. rate5 * weights. get (4);

return ratesSum / i. weight / i. volume;

}

private double getCriterialUtility (Item i) {

return i. rate1 * weights. get (0) +

i. rate2 * weights. get (1) +

i. rate3 * weights. get (2) +

i. rate4 * weights. get (3) +

i. rate5 * weights. get (4);

}

/**

* Отобразить пару объектов в один объект.

* @param i Любой объект из пары.

* @return Результирующий объект.

*/

public static Item mapPair (Item i) {

Item first = i;

Item second = i. getPair ();

Item resultItem = new Item (first. id + ": " + second. id,

first. volume + second. volume,

first. weight + second. weight,

first. rate1 + second. rate1,first. rate2 + second. rate2,first. rate3 + second. rate3,first. rate4 + second. rate4,first. rate5 + second. rate5);

return resultItem;

}

/**

* Получить бинарное отношение, определённое ЛПР.

* @return Бинарное отношение.

*/

public BinaryRelation<Item> getBinaryRelation () {

return new BossBinaryRelation ();

}

public double getPackUtility (Map<Container, List<Item>> map) {

double utility = 0;

for (Container c: map. keySet ()) {

for (Item i: map. get (c)) {

utility += getCriterialUtility (i);

}

}

return utility;

}

}

Container. java

package core;

/**

* Контейнер.

* @author AtemB

*

*/

public class Container {

/** ID. */

private int id;

/** Объём. */

private int volume;

/** Грузоподъёмность. */

private int cargo;

public Container (int id, int volume, int cargo) {

this. id = id;

this. volume = volume;

this. cargo = cargo;

}

public int getVolume () {

return volume;

}

public int getCargo () {

return cargo;

}

public int getId () {

return id;

}

/**

* @param volume the volume to set

*/

public void setVolume (int volume) {

this. volume = volume;

}

/**

* @param cargo the cargo to set

*/

public void setCargo (int cargo) {

this. cargo = cargo;

}

/**

* @param id the id to set

*/

public void setId (int id) {

this. id = id;

}

@Override

public Container clone () {

Container clone = new Container (id, volume, cargo);

return clone;

}

/* (non-Javadoc)

* @see java. lang. Object#toString ()

*/

@Override

public String toString () {

return "Контейнер" +

",\nID: " + id +

"\nОбъём: " + volume +

",\nГрузоподъёмность: " + cargo;

}

}

Item. java

package core;

/**

* Упаковываемый объект.

* @author AtemB

*

*/

public class Item {

/** ID. */

String id;

/** Объём. */

int volume;

/** Вес. */

int weight;

/** Критерий 1. */

int rate1;

/** Критерий 2. */

int rate2;

/** Критерий 3. */

int rate3;

/** Критерий 4. */

int rate4;

/** Критерий 5. */

int rate5;

/** Ссылка на парный объект. */

private Item pair;

public Item (String id,

int volume,

int weight,

int rate1,int rate2,int rate3,int rate4,int rate5) {

super ();

this. id = id;

this. volume = volume;

this. weight = weight;

this. rate1 = rate1;

this. rate2 = rate2;

this. rate3 = rate3;

this. rate4 = rate4;

this. rate5 = rate5;

}

/***/

public Item () {

this. id = 0 + "";

this. volume = 0;

this. weight = 0;

this. rate1 = 0;

this. rate2 = 0;

this. rate3 = 0;

this. rate4 = 0;

this. rate5 = 0;

}

public String getId () {

return id;

}

public Item getPair () {

return pair;

}

public void setPair (Item pair) {

this. pair = pair;

}

public boolean hasPair () {

return pair! = null;

}

/**

* @return the volume

*/

public int getVolume () {

return volume;

}

/**

* @return the weight

*/

public int getWeight () {

return weight;

}

/**

* @return the rate1

*/

public int getRate1 () {

return rate1;

}

/**

* @return the rate2

*/

public int getRate2 () {

return rate2;

}

/**

* @return the rate3

*/

public int getRate3 () {

return rate3;

}

/**

* @return the rate4

*/

public int getRate4 () {

return rate4;

}

/**

* @return the rate5

*/

public int getRate5 () {

return rate5;

}

/**

* @param volume the volume to set

*/

public void setVolume (int volume) {

this. volume = volume;

}

/**

* @param weight the weight to set

*/

public void setWeight (int weight) {

this. weight = weight;

}

/**

* @param rate1 the rate1 to set

*/

public void setRate1 (int rate1) {

this. rate1 = rate1;

}

/**

* @param rate2 the rate2 to set

*/

public void setRate2 (int rate2) {

this. rate2 = rate2;

}

/**

* @param rate3 the rate3 to set

*/

public void setRate3 (int rate3) {

this. rate3 = rate3;

}

/**

* @param rate4 the rate4 to set

*/

public void setRate4 (int rate4) {

this. rate4 = rate4;

}

/**

* @param rate5 the rate5 to set

*/

public void setRate5 (int rate5) {

this. rate5 = rate5;

}

/* (non-Javadoc)

* @see java. lang. Object#equals (java. lang. Object)

*/

@Override

public boolean equals (Object obj) {

if (this == obj) {

return true;

}

if (obj == null) {

return false;

}

if (! (obj instanceof Item)) {

return false;

}

Item other = (Item) obj;

if (rate1! = other. rate1) {

return false;

}

if (rate2! = other. rate2) {

return false;

}

if (rate3! = other. rate3) {

return false;

}

if (rate4! = other. rate4) {

return false;

}

if (rate5! = other. rate5) {

return false;

}

if (volume! = other. volume) {

return false;

}

if (Double. doubleToLongBits (weight)! = Double

. doubleToLongBits (other. weight)) {

return false;

}

return true;

}

@Override

public Item clone () {

Item clone = new Item (id, volume, weight, rate1, rate2, rate3, rate4, rate5);

return clone;

}

/* (non-Javadoc)

* @see java. lang. Object#toString ()

*/

@Override

public String toString () {

return "Объект" +

"\nID: " + id + ",\nОбъём: " + volume + ",\nВес: " + weight

+ ",\nКр.1: " + rate1 + ",\nКр.2: " + rate2 + ",\nКр.3: " + rate3

+ ",\nКр.4: " + rate4 + ",\nКр.5" + rate5 + ",\nID парного объекта: " + pair. id;

}

}

Packer. java

package core;

import java. util. ArrayList;

import java. util. Collection;

import java. util. List;

import java. util. Random;

import java. util. Set;

import java. util. SortedMap;

/**

* Упаковщик.

* @author AtemB

*

*/

public class Packer {

/**

* Алгоритм упаковки.

* @author AtemB

*

*/

public enum ALGORYTHM {

/** В первый подходящий. */

FIRST,

// /** В первый подходящий с убыванием. */

// FIRST_DECREASE,

/** В лучший из подходящих. */

BEST,

// /** В лучший из подходящих с убыванием. */

// BEST_DECREASE

}

/**

* Тип сортировки.

* @author AtemB

*

*/

public enum SORT_TYPE {

/** По весу. */

WEIGHT,

/** По объёму. */

VOLUME,

/** По полезности. */

UTILITY,

/** По величине. */

SIZE

}

private Store store;

private Boss boss;

public Packer (Store store, Boss boss) {

this. store = store;

this. boss = boss;

}

public void breakPair (Item i1, Item i2) {

i1. setPair (null);

i2. setPair (null);

}

public void createPair (Item i1, Item i2) {

i1. setPair (i2);

i2. setPair (i1);

}

/**

* Обработать парные объекты.

* @param items Исходное множество объектов.

* @return Результирующее множество объектов.

*/

public List<Item> processPairs (List<Item> items) {

List<Item> listForRemove = new ArrayList<Item> ();

// Отображаем все пары в монолитные объекты.

for (int i = 0; i < items. size (); i++) {

Item current = items. get (i);

if (current. hasPair ()) {

// Помещаем парный текущему объект в список на удаление,

// т.к. теперь его параметры будут отражены в результирующем объекте.

listForRemove. add (current. getPair ());

Item resultItem = Boss. mapPair (current);

// Замещаем исходный объект по текущему индексу результирующим.

items. set (i, resultItem);

current. getPair (). setPair (null);

}

}

// Удаляем парные объекты из списка.

for (Item i: listForRemove) {

items. remove (i);

}

return items;

}

/**

* Создать слой Парето.

* @param boss ЛПР.

* @param items Исходное множество.

* @return Слой парето.

*/

public List<Item> extractParetoLayer (List<Item> items) {

BinaryRelation<Item> relation = boss. getBinaryRelation ();

if (items. isEmpty ()) {

return null;

} else {

// Сначала извлекаем первый попавшийся недоминируемый объект на исходном множестве.

List<Item> bestItems = new ArrayList<Item> ();

Item best = items. get (0);

for (Item i: items) {

// Сравниваем текущий элемент с каждым из элементов последовательности.

// Если новый элемент лучше текущего - инициализируем им ссылку на лучший объект.

if (relation.compare (best, i) == i) {

best = i;

}

}

// Удаляем недоминируемый объект из исходного множества.

items. remove (best);

// Добавляем его в слой Парето.

bestItems. add (best);

// Теперь нужно найти все несравнимые с ним элементы исходного множества.

List<Item> equalItems = new ArrayList<Item> ();

for (Item i: items) {

// Если очередной элемент несравним с ранее полученным лучшим,

// добавляем его в результирующее множество.

if (relation.compare (best, i) == null) {

equalItems. add (i);

}

}

// Удаляем из исходного множества все ссылки на недоминируемые объекты.

for (Item i: equalItems) {

items. remove (i);

}

// Добавляем недоминируемые объекты в слой Парето.

for (Item i: equalItems) {

bestItems. add (i);

}

return bestItems;

}

}

/**

* Получить множества (слои) Парето.

* @param boss ЛПР.

* @param items Исходное множество.

* @return Слои Парето.

*/

public List<List<Item>> createParetoSet (List<Item> items) {

List<List<Item>> layers = new ArrayList<List<Item>> ();

while (! (items. isEmpty ())) {

List<Item> paretoLayer = extractParetoLayer (items);

layers. add (paretoLayer);

}

return layers;

}

/**

* Упаковать очередной слой Парето. Инкапсулирует логику алгоритма упаковки.

* @param map Карта, содержащая информацию о контейнерах и об упакованных объектах.

* @param paretoLayer Слой Парето.

* @return Ту же карту с очередным добавленным слоем.

*/

public SortedMap<Container, List<Item>> pack (SortedMap<Container, List<Item>> map, List<Item> paretoLayer, ALGORYTHM algorythm) {

// Получаем массу и объём слоя Парето.

double layerWeight = 0.0;

double layerVolume = 0.0;

for (Item i: paretoLayer) {

layerWeight += i. weight;

layerVolume += i. volume;

}

// if (algorythm == ALGORYTHM. FIRST_DECREASE || algorythm == ALGORYTHM. BEST_DECREASE) {

// sort (paretoLayer, SORT_TYPE. SIZE);

// }

// Если он в полном составе не упаковывается, его нужно сортировать по эффективности.

if (layerWeight > getFreeCargo (map) ||

layerVolume > getFreeSpace (map)) {

sort (paretoLayer, Packer. SORT_TYPE. UTILITY);

}

List<Item> forRemove = new ArrayList<Item> ();

for (Item item: paretoLayer) {

if (! tryToPack (map, item, algorythm)) {

store. getRest (). add (item);

forRemove. add (item);

}

}

for (Item i: forRemove) {

paretoLayer. remove (i);

}

return map;

}

/**

* Попробовать паковать объект.

* @param map

* @param item Объект.

* @return Флаг удачного завершения операции.

*/

private boolean tryToPack (SortedMap<Container, List<Item>> map, Item item, ALGORYTHM algorythm) {

Set<Container> containers = map. keySet ();

if (algorythm == ALGORYTHM. BEST/* || algorythm == ALGORYTHM. BEST_DECREASE*/) {

Container bestContainer = getBest (containers, item, map);

if (bestContainer == null) {

return false;

} else {

map. get (bestContainer). add (item);

return true;

}

} else if (algorythm == ALGORYTHM. FIRST) {

for (Container container: containers) {

if (canPack (container, item, map)) {

map. get (container). add (item);

return true;

}

}

}

return false;

}

/**

* Получить свободное место в контейнерах.

* @param map Карта, содержащая информацию о контейнерах и об упакованных объектах.

* @return Свободное место.

*/

private double getFreeSpace (SortedMap<Container, List<Item>> map) {

double freeSpace = 0.0;

for (Container c: map. keySet ()) {

double itemsVolume = 0.0;

for (Item i: map. get (c)) {

itemsVolume += i. volume;

}

freeSpace += (c. getVolume () - itemsVolume);

}

return freeSpace;

}

/**

* Получить оставшуюся грузоподъёмность контейнеров.

* @param map Карта, содержащая информацию о контейнерах и об упакованных объектах.

* @return Оставшуюся грузоподъёмность контейнеров.