Информационная система поддержки принятия решений в условиях многокритериальной оптимизации

 

Оглавление


Введение

Основные понятия теории принятия решений

Формализация задач принятия решений

Однокритериальные задачи в условиях определенности

Многокритериальные задачи в условиях определенности

1.Методы оценки многокритериальных альтернатив

Прямые методы

Аксиоматические методы

Методы компенсации

Человеко-машинные процедуры принятия решений

2. Постановка задачи об упаковке

3. Функция полезности.

Методы построения аддитивной функции полезности

4. Слои Парето

5. Программа

Структура

Пример решения задачи

Заключение

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

Приложения

Введение


Основные понятия теории принятия решений


Термин "Системный анализ" будем понимать как совокупность методов, ориентированных на исследование сложных систем - технических, экономических, экологических. программных и т.д.

Результатом этих исследований, как правило, является выбор определенной альтернативы: плана развития, параметров конструкции, стратегии управления и т.д.

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

Под принятием решения будем понимать выбор одного или нескольких вариантов решения задачи из некоторого исходного множества вариантов (альтернатив). Последствием принятия решения назовем событие (исход), на возможность появления которого влияет данное решение. Чем является этот исход - зависит от ситуации, в которой это решение принимается. В большинстве случаев это будет максимальный выход продукта при минимальных затратах на его производство, но это всё же далеко не общий случай, и от него тоже можно (и нужно) абстрагироваться: это могут быть как прямые энергозатраты, так и затраты денег, времени и вообще всего, что является ресурсом с точки зрения конкретной предметной области. То же самое касается и продукта: это может быть как материальная ценность, так и нематериальная. Например, принятие определённого решения, результатом которого станет повышение процента сгорания топлива в двигателе разрабатываемой конструкции.

Система предпочтений - совокупность правил, устанавливающих приоритеты при выборе из множества альтернатив.

принятие решение аддитивная функция

Решение - подмножество множества альтернатив, образованное на основе системы предпочтений.

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

На принятие решений в той или иной степени влияют активные группы людей, имеющих общие интересы по отношению к проблеме, требующей решение - эксперты в предметной области. К ним обычно обращаются за оценками, за прогнозами исходов тех или иных решений. Эксперты высказывают свое субъективное мнение. Если эксперт беспристрастен и является профессионалом, его оценки близки к объективным.

При принятии сложных решений в их подготовке принимает участие консультант по принятию решений (аналитик). Он, как правило, не дает собственных оценок (т.к. оценивать - это задача ЛПР), а помогает уяснить предпочтение, взвесить все за" и против" и выработать разумный компромисс.

Задача принятия решений (ПР) возникает, когда существует несколько вариантов действий (альтернатив) для достижения заданного результата. При этом требуется выбрать наилучшую в определенном смысле альтернативу. Задача выбора состоит в следующем:

построение формальных моделей ситуации выбора;

анализ неопределенностей;

формирование целей принятия решений.

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


Формализация задач принятия решений


Под принятием решения будем понимать выбор подмножества альтернатив из исходного их множества. При этом не стоит забывать, что множество может быть пустым, содержать один или больше одного элемента. Выбор той или иной альтернативы из исходного множества должен быть так или иначе обусловлен. Значимые критерии альтернатив устанавливаются лицом, принимающим решения (в дальнейшем ЛПР) и, при отображении альтернативы в вектор, будут представлять из себя скаляры, входящие в его состав. При недостатке информации о критериях выбора, который ему предстоит сделать, ЛПР может обратиться к экспертам в текущей предметной области. Для возможности выбора той или иной альтернативы из исходного множества у ЛПР должна быть, во-первых, возможность сравнивать их между собой, и, во-вторых, возможность оценивать эти альтернативы. В общем случае задача принятия решения представима кортежем следующего вида: áX, I, S, Fñ, где X - исходное множество альтернатив; I - уровень информации; S - метод поиска (метод) решения; F - множество критериев оценки альтернатив.

Для любых двух множеств X и Y (различных или нет) существует единственное множество, состоящее из всех упорядоченных пар (x,y), x Î X, y ÎY. Обозначается X ´ Y и называется декартовым произведением (или просто произведением) X и Y. Поскольку ЛПР попарно сравнивает элементы одного и того же множества, нас интересует произведение множества X на само себя - X ´ X, и его мы будем обозначать как X2. Бинарным отношением на множестве X будем называть произвольное подмножество R множества X2, т.е. R Í А2 (R Í X ´ X).

Если задано отношение R Í X2 и (xi,xj) Î R ( (xi,xj) Î R xi R xj), xi Î X, xj Î X, то графически:



Получившиеся фигуры называют ориентированным графом, или графом, узлы - вершинами графа. Задание бинарного отношения интерпретируется как введение некоторой системы предпочтений, т.е. если (xi,xj) Î R, xi Î X, xj Î X, то подразумевается, что в определенном смысле элемент xi лучше или не хуже" элемента xj.

Рассмотрим некоторые свойства бинарного отношения.

. Отношение называется рефлексивным, если (xi,xi) R " xi Î X.

. Отношение называется антирефлексивным, если из xi R xj Þ xi ¹ xj.

. Отношение называется связным, если " xi, xj Î X (xi,xj) Î R или (xj,xi) Î R.

. Отношение называется симметричным, если " xi, xj Î X из xi R xj Þ xj R xi.

. Отношение называется асимметричным, если из двух соотношений xi R xj и xj R xi, по меньшей мере одно не выполняется. Если отношение ассиметрично, то оно и антирефлексивно.

. Отношение называется антисимметричным, если " xi, xj Î X из xi R xj и xj R xi Þ xi = xj.

. Отношение называется транзитивным, если " xi, xj, xk Î X таких, что (xi,xj) R и (xj,xk) R Þ (xi,xk) R.

. Отношение R называется квазипорядком, если R рефлексивно и транзитивно.

. Отношение R называется линейным квазипорядком, если R рефлексивно, транзитивно и связно.

. Отношение P называется отношением строгого предпочтения, если оно антисимметрично и связно.

. Отношение I называется отношением безразличия, если оно симметрично и транзитивно.

Граф рефлексивного отношения содержит петли у всех вершин, антирефлексивного - не содержит ни одной петли. Граф связного отношения содержит дуги между любыми двумя вершинами графа. Для симметричного отношения вершины графа связаны парами противоположно направленных дуг. В графе асимметричного отношения петли отсутствуют, а вершины могут быть связаны только одной направленной дугой. Граф антисимметричного отношения может иметь петли, но связь между вершинами отображается только одной направленной дугой.

На практике не всегда требуется максимизация или минимизация того или иного критерия. Может оказаться, что требуется удержать его определённое значение. Для удобства в этом случае используют так называемую функцию полезности (далее ФП). Под этим абстрактным понятием подразумевается некая функция, значение которой отражает приближение её аргументов (в качестве аргумента выступает некое решение, выраженное в виде вектора критериев) к оптимальному значению. В случае оптимизации по одному критерию, ФП может принимать в качестве аргумента скалярное значение вместо одномерного вектора. В ФП локализована логика, численно выражающая разницу между текущим и требуемым значением. Наиболее распространенным подходом к решению задач ПР является построение ФП U (x) со следующими свойствами: U (xi) > U (xj), если (xi,xj) P; U (xi) = U (xj), если (xi,xj) I. Если ФП существует, то она определяет линейный квазипорядок на множестве X. Верно и обратное, если на множестве X построен линейный квазипорядок, то возможно построение ФП (например, путем сопоставления альтернативам множества X, расположенных в порядке убывания их предпочтительности натуральных чисел в возрастающем порядке; одинаково предпочтительным альтернативам будут присвоены одинаковые числа).

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

Если найдено решение, для которого не существует лучшей альтернативы, то такое решение называется парето-оптимальным. Заметим, что парето-оптимальных решений может быть больше одного. Они образуют множество Парето, являющееся, соответственно, подмножеством исходного множества. Для определения нахождения выбранной альтернативы в множестве Парето достаточно сравнить её с остальными альтернативами исходного множества, используя бинарное отношение, определённое на исходном множестве. Если ни одна из них не оказалась лучше, значит, выбранная альтернатива принадлежит множеству Парето. В таком случае говорят, что данная альтернатива недоминируема на исходном множестве. Элементы множества Парето - это решения, недоминируемые на исходном множестве. Также невозможно сравнить между собой элементы множества Парето, используя определённое на исходном множестве бинарное отношение. В таком случае говорят, что элементы несравнимы между собой.

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

На основе выбранного бинарного отношения осуществляется попарное сравнение всех альтернатив, причем альтернативы, оказавшиеся лучшими при всех сравнениях выделяются в новое множество, называемое ядром. Размер ядра характеризуется количеством альтернатив. Если бинарное отношение является отношением доминирования одной альтернативы над другой, при котором одна альтернатива имеет по всем критериям не худшие, а хотя бы по одному из критериев лучшие оценки, то появившееся при этом ядро является множеством Парето.


Однокритериальные задачи в условиях определенности


Простейшая ситуация выбора возникает, когда принятие конкретного решения x приводит к однозначному исходу y, оцениваемому с помощью единственного критерия. Предполагается однозначная зависимость y = j (x). Ценность" (полезность) исходов можно определить функционалом: F: Y ? E, где y = j (x). Таким образом каждому x соответствует числовая оценка f (y) = f (j (x)).

Функционал F позволяет в явном виде отразить систему предпочтений ЛПР. Будем считать, чем больше значение F, тем более предпочтительна данная альтернатива.

Обозначим суперпозицию функций f и j через F, приходим к оптимизационной задаче:


(1)


Функционал F (x) называют целевым функционалом или целевой функцией. Требуется построить множество:


= (2)


Соответствующее бинарное отношение R может быть задано следующим образом: (x,x) R тогда и только тогда, когда F (x) > F (x). Если F (x) = F (x), то точки x, x несравнимы по R и (x,x) R. Такое отношение обладает антирефлексивностью, ассиметричностью, транзитивностью и поэтому является отношением строгого порядка на X.


Многокритериальные задачи в условиях определенности


Положим, что любому решению x Î X соответствует единственный элемент y Î Y, где y = j (x), но в данном случае качество" или полезность" исхода y оценивается несколькими числами f (y) - по нескольким критериям, т.е. fi: Y ® E, причем каждый из функционалов требуется максимизировать. Т.о. любому решению x соответствует исход y = j (x), а последнему соответствует вектор (f1, f2,., fm).

С помощью суперпозиции fi (x) = fi (j (x)) i = 1,.,m можно непосредственно оценивать качество самого решения x, используя векторное отображение F: X Em, F = (f1,., fm).

Рассмотрим точки x1, x2 Î X. Если fi (x2) £ fi (x1) i = 1,., m, причем по крайней мере одно из неравенств строгое, то будем говорить, что x1 предпочтительнее x2. Если для некоторого x0 Î X не существует более предпочтительных точек, то x0 будем называть эффективным или Парето - оптимальным решением многокритериальной задачи:


fi (x) ® , i = 1,., X (3)


Множество, включающее в себя все эффективные решения обозначим PF (X) или P (X) (для известного векторного отображения) и будем называть множеством Парето для векторного отображения F: X Em, F = (f1,., fm), PF (X) Í X.

Множество P (F) = F (P (X)) будем называть множеством эффективных оценок.

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

Точку x1 Î X будем называть слабо эффективным решением задачи (3), если не существует x2 Î X, для которой выполняются строгие неравенства fi (x2) > fi (x1), i = 1,., m. Т.е. решение называется слабо эффективным, если оно не может быть сразу по всем критериям полезности, задаваемых с помощью fi (x), i = 1,., m.

Множество слабо эффективных решений обозначим SF (X) или S (X), P (X) Í S (X) (S (F) = F (S (X)).

Такая система предпочтений на множестве альтернатив X, заданная с помощью векторного отображения F может быть представлена на языке бинарных отношений: "x1, x2 Î X

1 R1 x2 Û fi (x1) > fi (x2), i = 1,., m. (4)1 R2 x2 Û fi (x1) ³ fi (x2), i = 1,., m, fi (x1) ¹ fi (x2).


Бинарное отношение R1 - называют отношением строгого доминирования или Слейтера, а R2 - отношением Парето. Ядра этих отношений совпадают с множествами SF (X), PF (X).


1.Методы оценки многокритериальных альтернатив


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

Разные методы принятия решений при многих критериях отличаются способом перехода к единой оценке полезности альтернатив. Можно выделить ряд групп таких методов.


Прямые методы


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

Прямые методы можно разделить на пять групп:

Постулируется сама формула зависимости полезности для многокритериальной альтернативы и все ее параметры.

ЛПР выбирает один из способов определения полезности альтернатив при неизвестной информации о вероятности различных внешних условий.

Обоснованием выбора считается привлекательность того или иного способа для ЛПР.

Постулируется основная формула зависимости, но ее параметры непосредственно назначаются ЛПР. Например, метод взвешенных сумм оценок критериев.

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

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

Обоснованием является представление о принципе максимизации ожидаемой полезности как о единственном рациональном принципе в принятии решений.


Аксиоматические методы


В литературе эта группа методов рассматривается как единственный научно обоснованный подход к анализу многокритериальных альтернатив, известный под названием MAUT (многокритериальная теория полезности). Аксиоматические методы разделяют на две подгруппы:

  1. Оценки альтернатив по многим критериям считаются известными (принятие решений при определенности).
  2. Заданы функции распределения вероятностей оценок альтернатив (принятие решений при риске).

Система аксиом:

  1. Аксиомы слабого порядка" и транзитивности. Эти аксиомы определяют отношение превосходства одной альтернативы над другой при наличии таких свойств, как связность и транзитивность.

Пусть u, v, w Î U - полезности альтернатив, тогда для любых u и v имеет место одно из следующих отношений:

=v, u>v, u<v; из u>v, v>w следует u>w.


Аксиомы, исключающие ненормальности в предпочтениях. Т.е. можно использовать любые части полезности двух альтернатив (объектов) для выражения эквивалентной полезности третьей:


Рис. 1. Схема основных этапов простого метода многокритериальной оценки (SMART).


Из u>v>w следует существование такой a, что au+ (1+a) v=w. Обычно эту аксиому называют аксиомой растворимости.

  1. Аксиомы независимости. Эти аксиомы требуют, чтобы предпочтения между альтернативами не зависели от некоторых преобразований этих альтернатив.

А) Слабая условная независимость по полезности: предпочтения для двух альтернатив, отличающихся лишь оценками по шкале одного критерия, не зависят от оценок этих альтернатив по шкалам других критериев.

Б) Совместная независимость: предпочтения между альтернативами, отличающимися оценками по определенному подмножеству критериев, не зависят от одинаковых оценок по критериям оставшегося подмножества.

При справедливости этих аксиом функция полезности многокритериальной альтернативы может быть выражена в виде:


,


где xi - оценка по i - му критерию, fi - функция полезности по i - му критерию.


Методы компенсации


В этих методах делается попытка уравновесить (или скомпенсировать) оценки одной альтернативы, оценками другой, чтобы найти, какие оценки лучше.

Точки и кривые безразличия

Если в многокритериальном пространстве построены поверхности безразличия, то сравнение многокритериальных альтернатив крайне просто, поскольку эти поверхности (или исходные точки) можно упорядочить по полезности.

Построение кривой ki:

  1. Выбирается исходная точка P1 (x1, y1), где x1, y1 - значение критериев X, Y в данной точке;
  2. Выбирается приращение D по критерию X (положительное или отрицательное) и определяется x2 = x1 + D;
  3. Определяется значение y2 по критерию Y такое, что точка P11 (x2, y2) эквивалентна по полезности точке P1 (x1, y1);
  4. По найденным точкам проводится кривая безразличия.

Например, кривые безразличия для двух критериев оценки альтернатив (Рис.2).


Рис. 2. Кривые безразличия для двух критериев оценки альтернатив


Методы сравнения разностей оценок альтернатив

Альтернативы сначала сравниваются покритериально, а уже потом осуществляется общее сопоставление всех достоинств и недостатков каждой из них.

Пусть (x1, x2, …, xN), (y1, y2, …, yN) - оценки альтернатив и по N критериям. Тогда альтернатива предпочтительней, чем альтернатива , если


,


где Ui - функция полезности для i - го критерия, ji - функция, определяющая влияние разностей оценок по i - му критерию на результат сравнения двух альтернатив.

Методы порогов несравнимости

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

На основе выбранного бинарного отношения осуществляется попарное сравнение всех альтернатив, причем альтернативы, оказавшиеся лучшими при всех сравнениях выделяются в новое множество, называемое ядром. Размер ядра характеризуется количеством альтернатив. Если бинарное отношение является отношением доминирования одной альтернативы над другой, при котором одна альтернатива имеет по всем критериям не худшие, а хотя бы по одному из критериев лучшие оценки, то появившееся при этом ядро называется множеством Парето.

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

Бинарные отношения. Каждому из N критериев, имеющих числовые шкалы, ставится в соответствие целое число p, характеризующее важность критерия. Выдвигается гипотеза о превосходстве альтернативы a над альтернативой b. Множество I, состоящее из N критериев, разбивается на три подмножества:+ (a, b) - подмножество критериев, по которым a предпочтительнее b;= (a, b) - подмножество критериев, по которым a равноценно b;- (a, b) - подмножество критериев, по которым b предпочтительнее a.

Далее формируется индекс согласия с гипотезой о превосходстве a над b:


(11)


Также формируется индекс несогласия: для критериев подмножества I- (a, b) определяются dab - разности оценок альтернатив b и a.

Альтернатива a объявляется превосходящей альтернативу b, если cab³c1 и dab£d1 (где c1, d1 - заданные уровни).

Бинарное отношение между альтернативами в общем случае может определяться одним или несколькими индексами. При формировании этих отношений не обязательно использовать веса критериев.

Рекомендуется использовать вложенные бинарные отношения S1ÌS2ÌS3.

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


Человеко-машинные процедуры принятия решений


Эти процедуры применимы, когда модель проблемы известна частично. Человек взаимодействует с ЭВМ, определяя желаемое соотношение между критериями.

Существующие человеко-машинные методы принятия решений отличаются следующими чертами.

В большинстве случаев рассматривается обычная линейная модель задачи многокритериального математического программирования. Дана область допустимых решений DÎRn, определяемая линейной системой:


xi³0, 1£i£n


Задано N критериев качества C1, C2, …, CN, где



Рис. 3. Схема основных этапов метода порогов несравнимости.


Требуется определить в области D вектор x*, обеспечивающий удовлетворительные значения по всем N критериям и наилучший компромисс между ними с точки зрения ЛПР. Иногда область допустимых решений определяется системой нелинейных уравнений.

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


2. Постановка задачи об упаковке


Рассмотрим следующую задачу: имеется множество из М объектов, которое желательно упаковать в К емкостей для последующей перевозки, причем М существенно больше К. Каждый объект характеризуется количественными физическими параметрами (например весом и объемом); каждая емкость характеризуется этими же предельными физическими параметрами (например, общим объемом и грузоподъемностью. Кроме того, каждый из упаковываемых объектов имеет оценки по нескольким критериям (с порядковыми шкалами), которые характеризуют его качество, его привлекательность для лица, ответственного за перевозку. Емкость контейнеров недостаточна для упаковки всех имеющихся объектов. Желательно осуществить упаковку наилучшим образом, т.е. так чтобы:

  1. Среди упакованных объектов было бы наибольшее количество таких, качество которых превосходило бы качество неупакованных - критерий О2.
  2. Число упакованных объектов было бы максимально возможным, так как все они в той или иной степени заслуживают упаковки в емкости (т.е. предварительный отбор, исключающий абсолютно плохие объекты, уже сделан) - критерий О1.

При К = 1 и многих критериях оценки качества упаковываемых предметов мы придем к многокритериальной задаче о многомерном рюкзаке. Задача об упаковке в контейнеры менее известна. Эта задача ставится следующим образом: Имеется конечное множество объектов, причем размер каждого из них задан рациональным числом. Требуется упаковать предметы в минимально возможное количество контейнеров так, чтобы суммарный размер объектов в каждом контейнере не превышал его размер (также рациональное число).

Упаковываемые объекты имеют оценки качества по многим критериям. Требуется упаковать максимальное число объектов, а не получить минимальное число контейнеров. Введем следующие обозначения:


ij - j-й физический параметр i-го объекта;ij - j-й физический параметр l-го контейнера;i - общая ценность i-го объекта.

Обозначим через I=1, 2, …, М множество номеров объектов, а через



множество тех упакованных объектов, для которых не найдется более ценных среди не упакованных.

Формальная постановка задачи имеет следующий вид:


, ,

, j = 1, …, P, l = 1, …, K,


3. Функция полезности


Пусть заданы критерии K1,…,Kn; X = { x | x = (x1,…,xn) } - множество векторых оценок вариантов по этим критериям. Пусть на X задано R - отношение предпочтения. Числовая функция f: X ? R, называется функцией полезности (ценности, предпочтительности), если она обладает следующим свойством: f (x) ? f (y) ? x R y.

Если известна функция полезности, то поиск оптимального варианта сводится к задаче нахождения x* = arg max f (x), x?X - аргумента максимума функции полезности на множестве X.

Как найти функцию полезности? Методы построения функции полезности делятся на эвристические и аксиоматические.

К эвристическим методам можно отнести метод главного критерия и метод обобщенного критерия.

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

Метод обобщенного критерия заключается в свёртке набора критериев в числовую функцию, которая и будет являться функцией полезности.

Виды свёрток:

) аддитивная свёртка: f = ?1K1+…+?nKn;

) мультипликативная свёртка: f = exp (?1ln (K1) +…+?nln (Kn)) = =11. nnKK??;

) приведенная свёртка: f = min (Ki/?i) по всем i=1…n (или f = max (Ki/?i) по всем i=1…n).

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

Обычно, при использовании таких методов функцию полезности строят в аддитивном виде:

= ?1f1+…+?nfn (*)


как сумму функций полезности по каждому критерию с некоторыми весовыми коэффициентами ?1,…,?n.

Пусть KI ? K = {K1,…,Kn} - подмножество множества критериев, т.е. группа критериев с номерами из множества I = {i1,…, im}. ? = {1,…,n}\I. Тогда K? - все остальные критерии, а векторная оценка x представляется в виде (xI,x?).

Говорят, что критерии KI не зависят по предпочтению от критериев K?, если предпочтения для любых двух оценок x = (xI,x?) и x = (xI,x?), содержащих одинаковые компоненты с номерами из ?, не зависят от самих значений этих компонент.

Критерии K1,…,Kn такие, что любой набор KI из них не зависит по предпочтению от остальных критериев K?, называются взаимно независимыми по предпочтению.

Теорема Дебре (критерий существования аддитивной функции полезности): функция полезности может быть задана в аддитивном виде (*) тогда и только тогда, когда критерии K1,…,Kn взаимно независимы по предпочтению (при n?3).

При n=2, кроме взаимной независимости критериев, требуется выполнение условия соответственных замещений (при n?3 оно выполняется автоматически):

?x1,x2,y1,y2,a,b,c,d если (x1,x2) ? (x1-a,x2+b) и (x1,y2) ? (x1-a,y2+c), то (y1,x2) ? (y1-d,x2+b) и (y1,y2) ? (y1-d,y2+c).

Т.е., если увеличение на b и c разных значений x2 и y2 критерия K2 при некотором опорном значении x1 критерия K1 компенсируется одним и тем же уменьшением этого значения x1 критерия K1, то такие же увеличения b и c тех же значений x2 и y2 критерия K2 сохраняются и при любом другом опорном значении y1 критерия K1.



Как осуществляется проверка взаимной независимости критериев по предпочтению?

Непосредственно по определению проверить независимость критериев затруднительно, т.к. даже при небольших n возникает большое число вариантов, которые надо проверить.

Утверждение (Леонтьева-Гормана): если любая пара критериев { Ki, Kj } не зависит по предпочтению от остальных (n-2) критериев, то все критерии K1,…,Kn взаимно независимы по предпочтению.

Таким образом, проверка сводится к установлению независимости только всех пар критериев от всех остальных критериев.

Пусть необходимо проверить на независимость по предпочтению наборы KI и K?. Берём набор x?+ наилучших (явно хороших) значений K? и подбираем (запрашиваем у ЛПР) два разных набора xI и xI таких, что (xI, x?+) ~ (xI, x?+). Затем берём набор x? - самых плохих оценок и спрашиваем у ЛПР, сохранилось ли безразличие (xI, x?-) ~ (xI, x?-)? Если нет, то критерии KI зависят от критериев K?. Если да, повторяем процедуру еще для некоторых других xI и xI. Если всё время безразличие остаётся, задаём вопрос в общем виде (сохранится ли безразличие при любых наборах). Если да, то наборы критериев KI и K? независимы.


Методы построения аддитивной функции полезности


Шаговый метод совместного шкалирования.

Пусть n=2 и условие соответственных замещений выполнено.

(x1,x2) = f1 (x1) + f2 (x2) ? (x1,x2) ?X.

Обозначим диапазоны изменения оценок x1 и x2: x1* ? x1 ? x1*, x2* ? x2 ? x2*.

Полагаем f (x1*,x2*) = f1 (x1*) = f2 (x2*) = 0 (начало отсчета).

Берем любое значение x11 > x1* достаточно близкое к нему. Устанавливаем f1 (x11) = 1 (единица измерения).

От ЛПР требуем указать x21 такое, что (x11, x2*) ~ (x1*, x21), для этого значения также f1 (x21) = 1.

Затем у ЛПР запрашиваем x12 и x22 такие, что:


(x12, x2*) ~ (x11, x21) ~ ~ (x1*, x22). f (x11,x21) = 1+1 = 2 ? f1 (x12) = f2 (x22) = 2.


Далее у ЛПР запрашиваем x13 и x23 такие, что:


(x13, x2*) ~ (x12, x21) ~ ~ (x11, x22) ~ (x1*, x23) ? f1 (x13) = f2 (x23) = 3.


И т.д. Таким образом, получаем наборы значений f1 (x1*), f1 (x11), f1 (x12), f1 (x13) … и f2 (x2*), f2 (x21), f2 (x22), f1 (x23) … по которым с помощью интерполяции строятся функции f1 (x) и f2 (x).

Метод половинного деления.

Метод находит функцию полезности в виде

(x1,x2) = ?1f1 (x1) +?2f2 (x2), где f1 (x1*) = f2 (x2*) = 0, f1 (x1*) = f2 (x2*) = 1, ?1>0, ?2>0, ?1+?2=1.


Построим функцию f1.

ЛПР просим указать среднюю по полезности оценку x10.5 ? [x1*; x1*], т.е. такую, изменение полезности на [x1*; x10.5] равно изменению полезности на [x10.5; x1*]. Устанавливаем f1 (x10.5) = 0.5.

Далее аналогично получаем

10.25 ? [x1*; x10.5] ? f1 (x10.25) = 0.25 и x10.75 ? [x10.5; x1*] ? f1 (x10.75) = 0.75 и т.д.


С помощью интерполяции, восстанавливаем функцию f1 по её значениям в точках x10.5, x10.25, x10.75

Функция f2 строится аналогично.

Для нахождения весового коэффициента ?1 достаточно запросить у ЛПР пару одинаковых по предпочтительности оценок (x1,x2) ? (x1,x2) ? ? f (x1,x2) = f (x1,x2) ? ?1f1 (x1) + (1-?1) f2 (x2) = ?1f1 (x1) + (1-?1) f2 (x2), а из этого равенства уже можно выразить ?1 (а ?2 = 1 - ?1).


4. Слои Парето


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

из исходного множества выделяется недоминируемый элемент

затем выделяются все несравнимые с ним объекты

Выделенные объекты заносятся в новое множество, называемое слоем Парето. Затем исходное множество, из которого теперь удалены "лучшие" объекты, обрабатывается по тому же принципу до тех пор, пока обработке и занесению в свой слой не подвергнется каждый его элемент. Каждый слой Парето является элементом множества подмножеств исходного множества. На рис.4.1 показан граф, иллюстрирующий пример отношения доминирования на множестве. Исходящая стрелка обозначает доминирование объекта, из которого она исходит, над объектом, на который она указывает. Двунаправленная стрелка говорит о том, что объекты несравнимы (4 ó 14, 8 ó 13). Узел 5 является доминирующим на исходном множестве, поэтому на рисунке он не имеет ни одной входящей стрелки, в т. ч. двунаправленной, а только исходящие. Поэтому его можно выделить во множество (слой) Парето, которое будет состоять только из одного элемента. На рисунках 4.2 - 4.8 показан процесс изменения исходного множества по мере выделения из него слоёв Парето.


Рис.4.1 В центре расположен недоминируемый объект (узел графа).


Рис.4.2.


Рис.4.3.


Рис.4.4.


Рис.4.5.


Рис.4.6.


Рис.4.7 Рис.4.8


В результате осуществлённых операций объекты исходного множества распределились по слоям Парето следующим образом:

[5]

[7]

[17]

[16]

[12]

[4] [8] [13] [14]

[10] [15] [20]

[1] [2] [3] [6] [9] [11] [18] [19]

Сравнение упаковки объектов для сортировки по полезности и для распределения по слоям Парето.

В таблице 4.1 представлены объекты, отсортированные по полезности:


Таблица 4.1 Сортировка по полезности.

№ объектаЗначение функции полезности5157148121312161241191112111411151121019102010691091891838118

Упакуем объекты в контейнеры, отсортировав их по полезности (Таб.4.2)


Таблица 4.2 Распределение объектов по контейнерам после сортировки по полезности.

Номера контейнеров12345Номера объектов5, 7, 817, 1613, 9, 124, 1415, 2

Величина суммарной полезности: 144.

А теперь упакуем их после распределения по слоям Парето (Таб.4.3)


Таблица 4.3 Распределение объектов по контейнерам после распределения по слоям Парето.

Номера контейнеров12345Номера объектов5, 7, 817, 1613, 9, 124, 1415, 2

Величина суммарной полезности: 120.

На рис. 4.9 представлен график, отображающий результаты упаковки для обоих случаев распределения объектов. Вывод.


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


Вывод.

Была выполнена упаковка 20 объектов, каждый из которых имеет свои характеристики массы и объёма. Упаковка производилась в 5 контейнеров двумя способами: по полезности и по слоям Парето. В обоих случаях количество упакованных объектов одинаково. Оценка результатов упаковки для варианта по слоям Парето в данной задаче оказалась хуже, чем для упаковки по полезности.


5. Программа


Структура


Программа, решающая эту задачу, написана на языке Java. Java является объектно-ориентированным языком, поэтому в нём доступны классы - структуры данных, описывающие объекты. С математической точки зрения класс можно отождествить с вектором, а поля класса - со скалярами в составе этого вектора. При этом поля класса могут сами являться объектами (экземплярами) других классов (или этого же класса, в случае со связными списками). Помимо этого, класс содержит методы, позволяющие оперировать данными. Другими словами, поля описывают объект класса, а методы - поведение этого объекта. Java также поддерживает спецификаторы доступа к полям и методам, что позволяет обезопасить данные внутри класса от нежелательного доступа и модификации ("повреждения информации"). Также в Java существует наследование классов - объект класса-наследника наследует поля и методы родительского класса, за исключением приватных. Этот механизм используется в случае, когда существующий класс недостаточно подробно описывает какой-либо объект, и требуется расширить его описание и/или переопределить методы родительского класса, доступные классу-наследнику. Класс в Java может наследоваться только от одного родительского класса - создатели языка пришли к выводу, что во всех случаях, когда в программе используется множественное наследование, можно перестроить архитектуру программы так, чтобы обойтись одиночным. Это намного упрощает разработку и исключает проблему т. н. "ромбовидного наследования".

Помимо обычного наследования, в Java есть механизм интерфейсов. Интерфейс можно описать как класс, все поля которого являются константами, а все методы - абстрактными. Интерфейс не содержит реализаций методов, аналогично прототипам функций в С/С++. Интерфейсы, как и классы, могут наследоваться друг от друга, причём для них возможно множественное наследование (поскольку методы в интерфейсах не реализованы, проблем с "ромбовидным наследованием" не возникает). Для задействования механизма интерфейсов в объявлении класса нужно указать, что он реализует интерфейс с таким-то именем. После этого в этом классе необходимо реализовать все методы, объявленные в интерфейсе. Если реализация всех методов невозможна, а "пустые" реализации по тем или иным причинам недопустимы, можно объявить этот класс абстрактным. Но в этом случае объект этого класса, как и объект интерфейса, создать будет нельзя. Класс может реализовать любое количество интерфейсов, и интерфейс может быть реализован любым количеством классов. В дальнейшем, создав интерфейсную ссылку, её можно будет инициализировать объектом любого класса, реализующего этот интерфейс. При этом классы, реализующие интерфейс, могут не состоять друг с другом в каком-либо отношении наследования. (Благодаря этому можно, например, создать массив интерфейсных ссылок на такие классы). Через интерфейсную ссылку недоступны никакие поля объекта, которым инициализирована эта ссылка, кроме констант интерфейса, и недоступны никакие методы, не объявленные в этом интерфейсе либо в родительских интерфейсах. Механизм интерфейсов удобен в тех случаях, когда необходимо определить, что будет делать объект, и неважно, как именно он это будет делать, что очень помогает на стадии проектирования программы.

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

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

2.Следовательно, на момент создания коллекции необязательно знать, сколько элементов должно быть в её составе. Тем более что это и не всегда возможно.

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

В данной программе определены классы, описывающие следующие сущности:

1.Упаковываемый объект. Этот класс содержит параметры упаковываемых объектов - объём, вес и оценки по полезности.

2.Контейнер. Описывает одномерный контейнер.

3.Упаковщик. Осуществляет операции по созданию парных объектов, формированию слоёв Парето, упаковке объектов в контейнеры.

4.ЛПР. Содержит алгоритм вычисления ценности (функция ценности), умеет сравнивать объекты по полезности, отображать парные объекты в один объект.

5.Склад. То место, откуда получают объекты для упаковки и куда возвращаются объекты, не поместившиеся в контейнеры.

6.Бинарное отношение (интерфейс). Содержит один метод - compare ("сравнить"). Реализован вложенным классом в классе, описывающем ЛПР.

Также имеется один класс, содержащий метод main, в котором реализована последовательность действий описываемых сущностей от момента создания всех объектов и до момента упаковки объектов.



Пример решения задачи


Рассмотрим следующую задачу:

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



где wi - вес i-го критерия, назначаемый ЛПР:- оценка альтернативы по i - му критерию.- число номеров критериев.

Назначим веса критериев, в соответствии с условием нормировки:



Так как критерий 1 и 2 имеют большую важность, то им будет соответствовать большой вес.

Вес критериев приведён в таблице 5.3.1.


Таблица 5.3.1 Веса критериев

№ критерия Вес критерия, wi10,4520,4530,0440,0450,02

На рис. 5.3.1 приведены характеристики объектов и контейнеров. На этом этапе есть возможность создавать и разбивать пары объектов, а также менять их характеристики и характеристики контейнеров.


Рис. 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с.

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


Приложения


Приложение 1


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

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

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

/**

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

* @author AtemB

*

*/ class Item {

/** ID. */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;

}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 () {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 () {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) {

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

// В этот список заносятся разности оценок по критериям.<Double> rates = new LinkedList<Double> ();. add ( (double) (i1. rate1 - i2. rate1));. add ( (double) (i1. rate2 - i2. rate2));

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

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

// Одинаковые значения в список не заносятся.<Boolean> flags = new LinkedList<Boolean> ();

for (Double d: rates) {

if (d. doubleValue () > 0) {. add (true);

} else if (d. doubleValue () < 0) {. add (false);

}

}

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

if (flags. isEmpty ()) {

return null;

} else {

boolean resultFlag = false;

for (int i = 1; i < flags. size (); i++) {= 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 () {= new ArrayList<Double> ();

{. add (0.45);. add (0.45);. add (0.04);. add (0.04);. add (0.02);

}

}

/**

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

* @param i Объект.

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

*/

public double getUtility (Item i) {

double ratesSum = i. rate1 * weights. get (0) +. rate2 * weights. get (1) +. rate3 * weights. get (2) +. rate4 * weights. get (3) +. rate5 * weights. get (4);

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

}

/**

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

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

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

*/

public static Item mapPair (Item i) {first = i;second = i. getPair ();resultItem = new Item (first. id + ": " + second. id,. volume + second. volume,. weight + second. weight,. 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 () {= new ArrayList<Container> ();= new ArrayList<Item> ();= new ArrayList<Item> ();= new TreeMap<Container, List<Item>> (new MapKeysComparator ());

}

public void createContainers (int containersNum, ContainerTemplate ct, int maxVolume, int maxCargo) {r = new Random ();

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

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

for (int i = 0; i < containersNum; i++) {. add (new Container (i,. nextInt (volumeDiapasonLength + 1) + ct. getVolume (). getBegin (),. nextInt (cargoDiapasonLength + 1) + ct. getCargo (). getBegin ()));

}

for (Container c: containers) {. 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++) {. add (new Item (i + "", r. nextInt (volumeDiapasonLength + 1) + it. getVolume (). getBegin (),. nextInt (weightDiapasonLength + 1) + it. getWeight (). getBegin (),. nextInt (r1DiapasonLength + 1) + it. getRate1 (). getBegin (),. nextInt (r2DiapasonLength + 1) + it. getRate2 (). getBegin (),. nextInt (r3DiapasonLength + 1) + it. getRate3 (). getBegin (),. nextInt (r4DiapasonLength + 1) + it. getRate4 (). getBegin (),. nextInt (r5DiapasonLength + 1) + it. getRate5 (). getBegin ()));

}

}

/**

* @return the containers

*/

public List<Container> getContainers () {

return containers;

}

/**

* @return the items

*/

public List<Item> getItemsClones () {<SimpleEntry<String, String>> itemPairs = new ArrayList<SimpleEntry<String, String>> ();<Item> newItems = new ArrayList<Item> ();

for (Item i: items) {. add (i. clone ());

if (i. hasPair ()) {. add (new SimpleEntry<String, String> (i. getId (), i. getPair (). getId ()));

}

}

for (Entry<String, String> e: itemPairs) {(e. getKey (), newItems). setPair (getItemFromListByID (e. getValue (), newItems));

}

return newItems;

}

public List<Item> getItemsInstance () {

return items;

}

public void setEmpty () {. clear ();. clear ();

}

/**

* @return the paretoSet

*/

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

return paretoSet;

}

/**

* @return the paretoSet

*/

public List<List<Item>> getParetoSetClone () {<List<Item>> clone = new ArrayList<List<Item>> ();<SimpleEntry<String, String>> itemPairs = new ArrayList<SimpleEntry<String, String>> ();

for (List<Item> paretoLayer: paretoSet) {<Item> newParetoLayer = new ArrayList<Item> ();

for (Item i: paretoLayer) {. add (i. clone ());

if (i. hasPair ()) {. add (new SimpleEntry<String, String> (i. getId (), i. getPair (). getId ()));

}

}. add (newParetoLayer);

}

for (Entry<String, String> e: itemPairs) {(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 () {<Container, List<Item>> clone = new TreeMap<Container, List<Item>> (new MapKeysComparator ());<Entry<Container, List<Item>>> set = map. entrySet ();

for (Entry<Container, List<Item>> e: set) {<Item> items = new ArrayList<Item> ();

for (Item i: e. getValue ()) {. add (i. 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) {. setPair (null);. setPair (null);

}

public void createPair (Item i1, Item i2) {. setPair (i2);. setPair (i1);

}

/**

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

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

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

*/

public List<Item> processPairs (List<Item> items) {<Item> listForRemove = new ArrayList<Item> ();

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

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

if (current. hasPair ()) {

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

// т.к. теперь его параметры будут отражены в результирующем объекте.. add (current. getPair ());resultItem = Boss. mapPair (current);

// Замещаем исходный объект по текущему индексу результирующим.. set (i, resultItem);. getPair (). setPair (null);

}

}

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

for (Item i: listForRemove) {. remove (i);

}

return items;

}

/**

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

* @param boss ЛПР.

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

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

*/

public List<Item> extractParetoLayer (List<Item> items) {<Item> relation = boss. getBinaryRelation ();

if (items. isEmpty ()) {

return null;

} else {

// Сначала извлекаем первый попавшийся недоминируемый объект на исходном множестве.<Item> bestItems = new ArrayList<Item> ();best = items. get (0);

for (Item i: items) {

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

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

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

}

}

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

// Добавляем его в слой Парето.. add (best);

// Теперь нужно найти все несравнимые с ним элементы исходного множества.<Item> equalItems = new ArrayList<Item> ();

for (Item i: items) {

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

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

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

}

}

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

for (Item i: equalItems) {. remove (i);

}

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

for (Item i: equalItems) {. add (i);

}

return bestItems;

}

}

/**

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

* @param boss ЛПР.

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

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

*/

public List<List<Item>> createParetoSet (List<Item> items) {<List<Item>> layers = new ArrayList<List<Item>> ();

while (! (items. isEmpty ())) {<Item> paretoLayer = extractParetoLayer (items);. 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) {+= i. weight;+= i. volume;

}

if (algorythm == ALGORYTHM. FIRST_DECREASE || algorythm == ALGORYTHM. BEST_DECREASE) {(paretoLayer, SORT_TYPE. SIZE);

}

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

if (layerWeight > getFreeCargo (map) ||> getFreeSpace (map)) {(paretoLayer, Packer. SORT_TYPE. UTILITY);

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

for (Item item: paretoLayer) {

if (! tryToPack (map, item, algorythm)) {. getRest (). add (item);. add (item);

}

}

for (Item i: forRemove) {. remove (i);

}

return map;

}

/**

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

* @param map

* @param item Объект.

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

*/

private boolean tryToPack (SortedMap<Container, List<Item>> map, Item item, ALGORYTHM algorythm) {<Container> containers = map. keySet ();

if (algorythm == ALGORYTHM. BEST || algorythm == ALGORYTHM. BEST_DECREASE) {bestContainer = getBest (containers, item, map);

if (bestContainer == null) {

return false;

} else {. get (bestContainer). add (item);

return true;

}

}

for (Container container: containers) {

if (canPack (container, item, 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)) {+= i. volume;

}+= (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)) {+= i. weight;

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

}

return freeCargo;

}

/**

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

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

* @param i Объект.

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

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

*/

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

// Получаем список объектов, упакованных в этот контейнер.<Item> items = map. get (c);

int totalVolume = 0;

double totalWeight = 0.0;

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

for (Item item: items) {+= item. volume;+= item. weight;

}

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

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

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

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

if (c. getVolume () - totalVolume < i. volume ||. getCargo () - totalWeight < i. weight) {

return false;

}

return true;

}

/**

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

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

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

*/

public void createPairs (int pairsNum, List<Item> items) {r = new Random ();

int pairCounter = 0;

while (pairCounter < pairsNum) {(items. get (r. nextInt (items. size ())), items);= countPairs (items);

}

}

/**

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

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

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

*/

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

if (! (i. hasPair ())) {r = new Random ();pair;

do {= items. get (r. nextInt (items. size ()));

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

}

}

/**

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

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

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

*/

public int countPairs (List<Item> items) {

int pairsCounter = 0;

for (Item i: items) {

if (i. hasPair ()) {++;

}

}

return pairsCounter / 2;

}

/**

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

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

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

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

*/

public Item extractHardest (List<Item> items) {hardest = items. get (0);

for (Item i: items) {

if (i. weight > hardest. weight) {= i;

}

}. remove (hardest);

return hardest;

}

/**

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

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

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

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

*/

public Item extractLargest (List<Item> items) {largest = items. get (0);

for (Item i: items) {

if (i. volume > largest. volume) {= i;

}

}. 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++) {_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) {buffer = items. get (j);. set (j, items. get (k));. set (k, buffer);

}

break;

case WEIGHT:

if (items. get (j). weight < items. get (k). weight) {buffer = items. get (j);. set (j, items. get (k));. set (k, buffer);

}

break;

case UTILITY:

if (boss. getUtility (items. get (j)) < boss. getUtility (items. get (k))) {buffer = items. get (j);. set (j, items. get (k));. set (k, buffer);

}

break;

case SIZE:

if (countSize (items. get (j)) > countSize (items. get (k))) {buffer = items. get (j);. set (j, items. get (k));. 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) {<Container> validContainers = new ArrayList<Container> ();

for (Container c: containers) {

if (canPack (c, i, map)) {. 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) {+= rests;

}

}

for (Container c: containers) {

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

if (rests == 0) {

return c;

}

if (rests < 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)) {+= item. volume;+= 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.. java

package core;

/**

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

* @author AtemB

*

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

*/

public interface BinaryRelation<T> {

/**

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

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

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

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

*/

public T compare (T t1, T t2);

}. 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) {

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

// В этот список заносятся разности оценок по критериям.<Double> rates = new LinkedList<Double> ();. add ( (double) (i1. rate1 - i2. rate1));. add ( (double) (i1. rate2 - i2. rate2));

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

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

// Одинаковые значения в список не заносятся.<Boolean> flags = new LinkedList<Boolean> ();

for (Double d: rates) {

if (d. doubleValue () > 0) {. add (true);

} else if (d. doubleValue () < 0) {. add (false);

}

}

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

if (flags. isEmpty ()) {

return null;

} else {

boolean resultFlag = false;

for (int i = 1; i < flags. size (); i++) {= 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 () {= new ArrayList<Double> ();

{. add (0.45);. add (0.45);. add (0.04);. add (0.04);. add (0.02);

}

}

/**

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

* @param i Объект.

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

*/

public double getUtility (Item i) {

double ratesSum = i. rate1 * weights. get (0) +. rate2 * weights. get (1) +. rate3 * weights. get (2) +. rate4 * weights. get (3) +. rate5 * weights. get (4);

return ratesSum / i. weight / i. volume;

}

private double getCriterialUtility (Item i) {

return i. rate1 * weights. get (0) +. rate2 * weights. get (1) +. rate3 * weights. get (2) +. rate4 * weights. get (3) +. rate5 * weights. get (4);

}

/**

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

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

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

*/

public static Item mapPair (Item i) {first = i;second = i. getPair ();resultItem = new Item (first. id + ": " + second. id,. volume + second. volume,. weight + second. weight,. 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)) {+= getCriterialUtility (i);

}

}

return utility;

}

}. 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 () {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;

}

}. java

package core;

/**

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

* @author AtemB

*

*/

public class Item {

/** ID. */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;

}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 () {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;

}

}. 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) {. setPair (null);. setPair (null);

}

public void createPair (Item i1, Item i2) {. setPair (i2);. setPair (i1);

}

/**

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

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

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

*/

public List<Item> processPairs (List<Item> items) {<Item> listForRemove = new ArrayList<Item> ();

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

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

if (current. hasPair ()) {

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

// т.к. теперь его параметры будут отражены в результирующем объекте.. add (current. getPair ());resultItem = Boss. mapPair (current);

// Замещаем исходный объект по текущему индексу результирующим.. set (i, resultItem);. getPair (). setPair (null);

}

}

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

for (Item i: listForRemove) {. remove (i);

}

return items;

}

/**

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

* @param boss ЛПР.

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

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

*/

public List<Item> extractParetoLayer (List<Item> items) {<Item> relation = boss. getBinaryRelation ();

if (items. isEmpty ()) {

return null;

} else {

// Сначала извлекаем первый попавшийся недоминируемый объект на исходном множестве.<Item> bestItems = new ArrayList<Item> ();best = items. get (0);

for (Item i: items) {

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

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

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

}

}

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

// Добавляем его в слой Парето.. add (best);

// Теперь нужно найти все несравнимые с ним элементы исходного множества.<Item> equalItems = new ArrayList<Item> ();

for (Item i: items) {

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

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

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

}

}

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

for (Item i: equalItems) {. remove (i);

}

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

for (Item i: equalItems) {. add (i);

}

return bestItems;

}

}

/**

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

* @param boss ЛПР.

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

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

*/

public List<List<Item>> createParetoSet (List<Item> items) {<List<Item>> layers = new ArrayList<List<Item>> ();

while (! (items. isEmpty ())) {<Item> paretoLayer = extractParetoLayer (items);. 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) {+= i. weight;+= i. volume;

}

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

// sort (paretoLayer, SORT_TYPE. SIZE);

// }

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

if (layerWeight > getFreeCargo (map) ||> getFreeSpace (map)) {(paretoLayer, Packer. SORT_TYPE. UTILITY);

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

for (Item item: paretoLayer) {

if (! tryToPack (map, item, algorythm)) {. getRest (). add (item);. add (item);

}

}

for (Item i: forRemove) {. remove (i);

}

return map;

}

/**

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

* @param map

* @param item Объект.

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

*/

private boolean tryToPack (SortedMap<Container, List<Item>> map, Item item, ALGORYTHM algorythm) {<Container> containers = map. keySet ();

if (algorythm == ALGORYTHM. BEST/* || algorythm == ALGORYTHM. BEST_DECREASE*/) {bestContainer = getBest (containers, item, map);

if (bestContainer == null) {

return false;

} else {. get (bestContainer). add (item);

return true;

}

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

for (Container container: containers) {

if (canPack (container, item, 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)) {+= i. volume;

}+= (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)) {+= i. weight;

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

}

return freeCargo;

}

/**

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

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

* @param i Объект.

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

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

*/

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

// Получаем список объектов, упакованных в этот контейнер.<Item> items = map. get (c);

int totalVolume = 0;

double totalWeight = 0.0;

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

for (Item item: items) {+= item. volume;+= item. weight;

}

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

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

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

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

if (c. getVolume () - totalVolume < i. volume ||. getCargo () - totalWeight < i. weight) {

return false;

}

return true;

}

/**

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

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

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

*/

public void createPairs (int pairsNum, List<Item> items) {r = new Random ();

int pairCounter = 0;

while (pairCounter < pairsNum) {(items. get (r. nextInt (items. size ())), items);= countPairs (items);

}

}

/**

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

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

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

*/

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

if (! (i. hasPair ())) {r = new Random ();pair;

do {= items. get (r. nextInt (items. size ()));

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

}

}

/**

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

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

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

*/

public int countPairs (List<Item> items) {

int pairsCounter = 0;

for (Item i: items) {

if (i. hasPair ()) {++;

}

}

return pairsCounter / 2;

}

/**

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

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

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

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

*/

public Item extractHardest (List<Item> items) {hardest = items. get (0);

for (Item i: items) {

if (i. weight > hardest. weight) {= i;

}

}. remove (hardest);

return hardest;

}

/**

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

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

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

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

*/

public Item extractLargest (List<Item> items) {largest = items. get (0);

for (Item i: items) {

if (i. volume > largest. volume) {= i;

}

}. 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++) {_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) {buffer = items. get (j);. set (j, items. get (k));. set (k, buffer);

}

break;

case WEIGHT:

if (items. get (j). weight < items. get (k). weight) {buffer = items. get (j);. set (j, items. get (k));. set (k, buffer);

}

break;

case UTILITY:

if (boss. getUtility (items. get (j)) > boss. getUtility (items. get (k))) {buffer = items. get (j);. set (j, items. get (k));. set (k, buffer);

}

break;

case SIZE:

if (countSize (items. get (j)) > countSize (items. get (k))) {buffer = items. get (j);. set (j, items. get (k));. 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) {<Container> validContainers = new ArrayList<Container> ();

for (Container c: containers) {

if (canPack (c, i, map)) {. 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) {+= rests;

}

}

for (Container c: containers) {

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

if (rests == 0) {

return c;

}

if (rests < 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)) {+= item. volume;+= 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;

}

}. java

package core;

import java. util. AbstractMap. SimpleEntry;

import java. util. ArrayList;

import java. util.comparator;

import java. util. LinkedList;

import java. util. List;

import java. util. Map. Entry;

import java. util. Random;

import java. util. Set;

import java. util. SortedMap;

import java. util. TreeMap;

import util. ContainerTemplate;

import util. ItemTemplate;

/**

* Склад.

* @author AtemB

*

*/

public class Store {

/**

* Сортировщик по ключам карты упаковки.

* @author AtemB

*

*/

class MapKeysComparator implements Comparator<Container> {

private List<Integer> template;

public MapKeysComparator (int index) {

this. template = templates. get (index);

}

@Override

public int compare (Container c1, Container c2) {

return template. indexOf (c1. getId ()) - template. indexOf (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;

private int [] containersSequence;

private List<List<Integer>> templates;

public Store () {= new ArrayList<Container> ();= new ArrayList<Item> ();= new ArrayList<Item> ();

}

/**

* Создать контейнеры.

* @param containersNum Число контейнеров.

* @param ct Шаблон контейнера.

* @param maxVolume Ограничение по объёму.

* @param maxCargo Ограничение по грузоподъёмности.

*/

public void createContainers (int containersNum, ContainerTemplate ct, int maxVolume, int maxCargo) {r = new Random ();

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

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

for (int i = 0; i < containersNum; i++) {. add (new Container (i + 1,r. nextInt (volumeDiapasonLength + 1) + ct. getVolume (). getBegin (),. nextInt (cargoDiapasonLength + 1) + ct. getCargo (). getBegin ()));

}

this. containersSequence = new int [containersNum];

for (int i = 0; i < containersNum; i++) {[i] = containers. get (i). getId ();

}= new LinkedList<List<Integer>> ();(templates, containersSequence, containersNum);= new TreeMap<Container, List<Item>> (new MapKeysComparator (0));

for (Container c: containers) {. put (c, new LinkedList<Item> ());

}

}

/**

* Создать упаковываемые объекты.

* @param itemsNum Число объектов.

* @param it Шабло объекта.

* @param maxVolume Ограничение по объёму.

* @param maxWeight Ограничение по массе.

*/

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++) {. add (new Item ( (i + 1) + "", r. nextInt (volumeDiapasonLength + 1) + it. getVolume (). getBegin (),. nextInt (weightDiapasonLength + 1) + it. getWeight (). getBegin (),. nextInt (r1DiapasonLength + 1) + it. getRate1 (). getBegin (),. nextInt (r2DiapasonLength + 1) + it. getRate2 (). getBegin (),. nextInt (r3DiapasonLength + 1) + it. getRate3 (). getBegin (),. nextInt (r4DiapasonLength + 1) + it. getRate4 (). getBegin (),. nextInt (r5DiapasonLength + 1) + it. getRate5 (). getBegin ()));

}

}

/**

* @return the containers

*/

public List<Container> getContainers () {

return containers;

}

/**

* @return the items

*/

public List<Item> getItemsClones () {<SimpleEntry<String, String>> itemPairs = new ArrayList<SimpleEntry<String, String>> ();<Item> newItems = new ArrayList<Item> ();

for (Item i: items) {. add (i. clone ());

if (i. hasPair ()) {. add (new SimpleEntry<String, String> (i. getId (), i. getPair (). getId ()));

}

}

for (Entry<String, String> e: itemPairs) {(e. getKey (), newItems). setPair (getItemFromListByID (e. getValue (), newItems));

}

return newItems;

}

public List<Item> getItemsInstance () {

return items;

}

public void setEmpty () {. clear ();. clear ();

}

/**

* @return the paretoSet

*/

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

return paretoSet;

}

/**

* @return the paretoSet

*/

public List<List<Item>> getParetoSetClone () {<List<Item>> clone = new ArrayList<List<Item>> ();<SimpleEntry<String, String>> itemPairs = new ArrayList<SimpleEntry<String, String>> ();

for (List<Item> paretoLayer: paretoSet) {<Item> newParetoLayer = new ArrayList<Item> ();

for (Item i: paretoLayer) {. add (i. clone ());

if (i. hasPair ()) {. add (new SimpleEntry<String, String> (i. getId (), i. getPair (). getId ()));

}

}. add (newParetoLayer);

}

for (Entry<String, String> e: itemPairs) {(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 (int index) {<Container, List<Item>> clone = new TreeMap<Container, List<Item>> (new MapKeysComparator (index));<Entry<Container, List<Item>>> set = map. entrySet ();

for (Entry<Container, List<Item>> e: set) {<Item> items = new ArrayList<Item> ();

for (Item i: e. getValue ()) {. add (i. 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;

}

private void swap (int [] array, int index1, int index2) {

int temp=array [index1];[index1] = array [index2];[index2] = temp;

}

private void addSequence (List<List<Integer>> sequence, int [] array) {<Integer> subSequence = new ArrayList<Integer> ();

for (int i = 0; i < array. length; i++) {. add (new Integer (array [i]));

}. add (subSequence);

}

/**

*

* @param array - массив

* @param n - число переставляемых элементов

*/

private void permutations (List<List<Integer>> sequence, int [] array, int n) {

// Если нечего переставлять

if (n==1) {(sequence, array);

} else {

for (int i=0; i<n; i++) {(array, i,n-1); // меняем последний элемент с каждым,

// в том числе и с самим собой.(sequence, array,n-1); // запускаем функцию, для n-1 элементов(array, i,n-1); // поигрались - и хватит. Надо вернуть массив в прежнее

// состояние для следующего обмена элементов

}

}

}

/**

* @return the templates

*/

public List<List<Integer>> getTemplates () {

return templates;

}

}

Пакет util.. java

package util;

public class ContainerTemplate {

private IntegerDiapason volume;

private IntegerDiapason cargo;

public ContainerTemplate (IntegerDiapason volume, IntegerDiapason cargo) {

super ();

this. volume = volume;

this. cargo = cargo;

}

/**

* @return the volume

*/

public IntegerDiapason getVolume () {

return volume;

}

/**

* @return the cargo

*/

public IntegerDiapason getCargo () {

return cargo;

}

}. java

package util;

public class IntegerDiapason {

private int begin;

private int end;

public IntegerDiapason (int begin, int end) {

super ();

this. begin = begin;

this. end = end;

}

/**

* @return the begin

*/

public int getBegin () {

return begin;

}

/**

* @return the end

*/

public int getEnd () {

return end;

}

}. java

package util;

public class ItemTemplate {

private IntegerDiapason weight;

private IntegerDiapason volume;

private IntegerDiapason rate1;

private IntegerDiapason rate2;

private IntegerDiapason rate3;

private IntegerDiapason rate4;

private IntegerDiapason rate5;

public ItemTemplate (IntegerDiapason weight, IntegerDiapason volume,rate1, IntegerDiapason rate2,IntegerDiapason rate3, IntegerDiapason rate4, IntegerDiapason rate5) {

super ();

this. weight = weight;

this. volume = volume;

this. rate1 = rate1;

this. rate2 = rate2;

this. rate3 = rate3;

this. rate4 = rate4;

this. rate5 = rate5;

}

/**

* @return the weight

*/

public IntegerDiapason getWeight () {

return weight;

}

/**

* @return the volume

*/

public IntegerDiapason getVolume () {

return volume;

}

/**

* @return the rate1

*/

public IntegerDiapason getRate1 () {

return rate1;

}

/**

* @return the rate2

*/

public IntegerDiapason getRate2 () {

return rate2;

}

/**

* @return the rate3

*/

public IntegerDiapason getRate3 () {

return rate3;

}

/**

* @return the rate4

*/

public IntegerDiapason getRate4 () {

return rate4;

}

/**

* @return the rate5

*/

public IntegerDiapason getRate5 () {

return rate5;

}

}

Пакет gui.. java

package gui;

import javax. swing. JFrame;

import javax. swing. JTabbedPane;

import util. ContainerTemplate;

import util. ItemTemplate;

import core. Boss;

import core. Packer;

import core. Store;

/**

* Графический интерфейс.

* @author AtemB

*

*/

public class GUI {

private JFrame mainFrame;

private ObjectCreatorViewer oViewer;

private ParetoLayersViewer pViewer;

private ItemsViewer iViewer;

private ResultViewer rViewer;

private Store store;

public GUI (Store store, Packer packer, Boss boss, ContainerTemplate ct, ItemTemplate it) {

this. store = store;tabbedPane = new JTabbedPane ();= new ObjectCreatorViewer (this, this. store, ct, it, 40,8);= new ItemsViewer (store. getContainers (), store. getItemsInstance (), packer, boss);= new ParetoLayersViewer (this, store, packer);= new ResultViewer (this, store, packer, boss);

this. mainFrame = new JFrame ("Упаковка объектов");. addTab ("Задание исходных данных", oViewer. getViewer ());. addTab ("Объекты и контейнеры", iViewer. getViewer ());. addTab ("Слои Парето", pViewer. getViewer ());. addTab ("Результаты упаковки", rViewer. getViewer ());

this. mainFrame. setSize (1000, 550);

this. mainFrame. add (tabbedPane);

this. mainFrame. setDefaultCloseOperation (JFrame. EXIT_ON_CLOSE);

this. mainFrame. setVisible (true);

}

public void refreshItemsViewer () {. refreshTables (store. getContainers (), store. getItemsInstance ());

}

}. java

package gui;

import java. awt. GridBagConstraints;

import java. awt. GridBagLayout;

import java. awt. Insets;

import java. awt. event. ActionEvent;

import java. awt. event. ActionListener;

import java. awt. event. MouseWheelEvent;

import java. awt. event. MouseWheelListener;

import java. util. HashMap;

import java. util. Map;

import javax. swing. BorderFactory;

import javax. swing. JButton;

import javax. swing. JLabel;

import javax. swing. JPanel;

import javax. swing. JSpinner;

import javax. swing. SpinnerNumberModel;

import util. ContainerTemplate;

import util. ItemTemplate;

import core. Store;

class ObjectCreatorViewer {

private JPanel viewer;

private JPanel containersPanel;

private JSpinner containersNum;

private JSpinner cVolume;

private JSpinner cargo;

private JPanel itemsPanel;

private JSpinner itemsNum;

private JSpinner iVolume;

private JSpinner weight;

private JButton createButton;

private Store store;

private ContainerTemplate ct;

private ItemTemplate it;

private int topItemsNum;

private int topContainersNum;

private GUI gui;

private Map<JSpinner, Integer [] > spinnersTopValues;

public ObjectCreatorViewer (GUI gui, Store store,ct,it,

final int topItemsNum,

final int topContainersNum) {

this. gui = gui;

this. ct = ct;

this. it = it;

this. topItemsNum = topItemsNum;

this. topContainersNum = topContainersNum;

this. store = store;

this. spinnersTopValues = new HashMap<JSpinner, Integer [] > ();containersNumPanel = new JPanel ();= new JSpinner (new SpinnerNumberModel (1, 1, topContainersNum, 1));(containersNum);. put (containersNum, new Integer [] {1, topContainersNum});. add (new JLabel ("Количесвто контейнеров (1 - " + topContainersNum + "): "));. add (containersNum);cVolumePanel = new JPanel ();

int bottomContainerVolume = ct. getVolume (). getBegin ();

int topContainerVolume = ct. getVolume (). getEnd ();= new JSpinner (new SpinnerNumberModel (bottomContainerVolume, bottomContainerVolume, topContainerVolume, 1));(cVolume);. put (cVolume, new Integer [] {bottomContainerVolume, topContainerVolume});. add (new JLabel ("Объём одного контейнера, max (" + bottomContainerVolume + " - " + topContainerVolume +"): "));. add (cVolume);cargoPanel = new JPanel ();

int bottomCargo = ct. getCargo (). getBegin ();

int topCargo = ct. getCargo (). getEnd ();= new JSpinner (new SpinnerNumberModel (bottomCargo, bottomCargo, topCargo, 1));(cargo);. put (cargo, new Integer [] {bottomCargo, topCargo});. add (new JLabel ("Грузоподъёмность одного контейнера, max (" + bottomCargo + " - " + topCargo + "): "));. add (cargo);= new JPanel (new GridBagLayout ());. add (containersNumPanel, new GridBagConstraints (0, 0, 1, 1, 0, 0, GridBagConstraints. NORTHWEST,. BASELINE, new Insets (5, 5, 5,5), 0, 0));. add (cVolumePanel, new GridBagConstraints (0, 1, 1, 1, 0, 0, GridBagConstraints. NORTHWEST,. BASELINE, new Insets (5, 5, 5,5), 0, 0));. add (cargoPanel, new GridBagConstraints (0, 2, 1, 2, 0, 0, GridBagConstraints. NORTHWEST,. BASELINE, new Insets (5, 5, 5,5), 0, 0));. setBorder (BorderFactory. createTitledBorder ("Создание контейнеров"));itemsNumPanel = new JPanel ();= new JSpinner (new SpinnerNumberModel (1, 1, topItemsNum, 1));(itemsNum);. put (itemsNum, new Integer [] {1, topItemsNum});. add (new JLabel ("Количесвто объектов (1 - " + topItemsNum + "): "));. add (itemsNum);iVolumePanel = new JPanel ();

int singleItemBottomVolume = it. getVolume (). getBegin ();

int singleItemTopVolume = it. getVolume (). getEnd ();= new JSpinner (new SpinnerNumberModel (singleItemBottomVolume, singleItemBottomVolume, singleItemTopVolume, 1));(iVolume);. put (iVolume, new Integer [] {singleItemBottomVolume, singleItemTopVolume});. add (new JLabel ("Объём одного объекта, max (" + singleItemBottomVolume + " - " + singleItemTopVolume + "): "));. add (iVolume);weightPanel = new JPanel ();

int singleItemBottomWeight = it. getVolume (). getBegin ();

int singleItemTopWeight = it. getVolume (). getEnd ();= new JSpinner (new SpinnerNumberModel (singleItemBottomWeight, singleItemBottomWeight, singleItemTopWeight, 1));(weight);. put (weight, new Integer [] {singleItemBottomWeight, singleItemTopWeight});. add (new JLabel ("Вес одного объекта, max (" + singleItemBottomWeight + " - " + singleItemTopWeight + "): "));. add (weight);= new JPanel (new GridBagLayout ());. add (itemsNumPanel, new GridBagConstraints (0, 0, 1, 1, 0, 0, GridBagConstraints. NORTHWEST,. NONE, new Insets (5, 5, 5,5), 0, 0));. add (iVolumePanel, new GridBagConstraints (0, 1, 1, 1, 0, 0, GridBagConstraints. NORTHWEST,. NONE, new Insets (5, 5, 5,5), 0, 0));. add (weightPanel, new GridBagConstraints (0, 2, 1, 1, 0, 0, GridBagConstraints. NORTHWEST,. NONE, new Insets (5, 5, 5,5), 0, 0));. setBorder (BorderFactory. createTitledBorder ("Создание объектов"));= new JButton ("Создать");. addActionListener (new ActionListener () {

@Override

public void actionPerformed (ActionEvent arg0) {s = ObjectCreatorViewer. this. store;. setEmpty ();. createContainers (getSpinnerValue (containersNum), ObjectCreatorViewer. this. ct, getSpinnerValue (cVolume), getSpinnerValue (cargo));

// LayouterLauncher. printContainersSumParameters (s. getContainers ());. createItems (getSpinnerValue (itemsNum), ObjectCreatorViewer. this. it, getSpinnerValue (iVolume), getSpinnerValue (weight));

// LayouterLauncher. printItemsSumParameters (s. getItems ());. this. gui. refreshItemsViewer ();

}

});= new JPanel (new GridBagLayout ());. add (containersPanel, new GridBagConstraints (0, 0, 1, 1, 1, 1, GridBagConstraints. NORTHWEST, GridBagConstraints. VERTICAL, new Insets (5, 5, 5,5), 0, 0));. add (itemsPanel, new GridBagConstraints (1, 0, 1, 1, 1, 1, GridBagConstraints. NORTHEAST, GridBagConstraints. VERTICAL, new Insets (5, 5, 5,5), 0, 0));. add (createButton, new GridBagConstraints (1, 1, 1, 1, 0, 0, GridBagConstraints. SOUTHEAST, GridBagConstraints. NONE, new Insets (5, 5, 5,5), 0, 0));

}

/**

* @return the viewer

*/

public JPanel getViewer () {

return viewer;

}

private int getSpinnerValue (JSpinner s) {

return ( (SpinnerNumberModel) s. getModel ()). getNumber (). intValue ();

}

int getContainersNum () {

return getSpinnerValue (containersNum);

}

int getMaxContainerVolume () {

return getSpinnerValue (cVolume);

}

int getMaxCargo () {

return getSpinnerValue (cargo);

}

int getItemsNum () {

return getSpinnerValue (itemsNum);

}

int getMaxItemVolume () {

return getSpinnerValue (iVolume);

}

int getMaxWeight () {

return getSpinnerValue (weight);

}

/**

* @return the topItemsNum

*/

public int getTopItemsNum () {

return topItemsNum;

}

/**

* @return the topContainersNum

*/

public int getTopContainersNum () {

return topContainersNum;

}

private void addStandardWheelListener (final JSpinner spinner) {. addMouseWheelListener (new MouseWheelListener () {

@Override

public void mouseWheelMoved (MouseWheelEvent e) {

int value = getSpinnerValue (spinner) + ( (Integer) e. getWheelRotation () * - 1);[] values = spinnersTopValues. get (spinner);

int bottom = values [0];

int top = values [1];

if (bottom <= value && value <= top) {

( (JSpinner) e. getComponent ()). setValue (value);

}

}

});

}

}. java

package gui;

import java. awt. GridBagConstraints;

import java. awt. GridBagLayout;

import java. awt. Insets;

import java. awt. event. ActionEvent;

import java. awt. event. ActionListener;

import java. awt. event. MouseAdapter;

import java. awt. event. MouseEvent;

import java. util. HashSet;

import java. util. List;

import java. util. Set;

import javax. swing. JButton;

import javax. swing. JLabel;

import javax. swing. JPanel;

import javax. swing. JScrollPane;

import javax. swing. JTable;

import javax. swing. event. TableModelEvent;

import javax. swing. event. TableModelListener;

import javax. swing. table. TableModel;

import javax. swing. table. TableRowSorter;

import core. Boss;

import core. Container;

import core. Item;

import core. Packer;

class ItemsViewer {

class ContainerTableModel implements TableModel {

private List<Container> containers;

private Set<TableModelListener> listeners = new HashSet<TableModelListener> ();

public ContainerTableModel (List<Container> containers) {

this. containers = containers;

}

@Override

public void addTableModelListener (TableModelListener columnIndex) {. add (columnIndex);

}

@Override

public Class<? > getColumnClass (int columnIndex) {

return Integer. class;

}

@Override

public int getColumnCount () {

return 3;

}

@Override

public String getColumnName (int columnIndex) {

switch (columnIndex) {

case 0:

return "ID";

case 1:

return "Объём";

case 2:

return "Грузоподъёмность";

}

return "column index error: \ngetted index = " + columnIndex + ",\nmost admissible index = " + (getColumnCount () - 1);

}

@Override

public int getRowCount () {

return containers. size ();

}

@Override

public Object getValueAt (int rowIndex, int columnIndex) {c = containers. get (rowIndex);

switch (columnIndex) {

case 0:

return c. getId ();

case 1:

return c. getVolume ();

case 2:

return c. getCargo ();

}

return null;

}

@Override

public boolean isCellEditable (int rowIndex, int columnIndex) {

switch (columnIndex) {

case 0:

return false;

case 1:

case 2:

return true;

}

return false;

}

@Override

public void removeTableModelListener (TableModelListener l) {. remove (l);

}

@Override

public void setValueAt (Object arg0, int rowIndex, int columnIndex) {c = containers. get (rowIndex);

switch (columnIndex) {

case 1:. setVolume ( (int) arg0);

break;

case 2:. setCargo ( (int) arg0);

break;

}

}

}

class ItemTableModel implements TableModel {

private List<Item> items;

private Set<TableModelListener> listeners = new HashSet<TableModelListener> ();

public ItemTableModel (List<Item> items) {

this. items = items;

}

@Override

public void addTableModelListener (TableModelListener l) {. add (l);

}

@Override

public Class<? > getColumnClass (int columnIndex) {

switch (columnIndex) {

case 0:

return Integer. class;

case 1:

return Integer. class;

case 2:

return Integer. class;

case 3:

return Integer. class;

case 4:

return Integer. class;

case 5:

return Integer. class;

case 6:

return Integer. class;

case 7:

return Integer. class;

case 8:

return Double. class;

case 9:

return String. class;

}

return null;

}

@Override

public int getColumnCount () {

return 10;

}

@Override

public String getColumnName (int columnIndex) {

switch (columnIndex) {

case 0:

return "ID";

case 1:

return "Объём";

case 2:

return "Вес";

case 3:

return "Кр.1";

case 4:

return "Кр.2";

case 5:

return "Кр.3";

case 6:

return "Кр.4";

case 7:

return "Кр.5";

case 8:

return "Полезность";

case 9:

return "Пара";

}

return "item index error: \ngetted index = " + columnIndex + ",\nmost admissible index = " + (getColumnCount () - 1);

}

@Override

public int getRowCount () {

return items. size ();

}

@Override

public Object getValueAt (int rowIndex, int columnIndex) {

switch (columnIndex) {

case 0:

return Integer. parseInt (items. get (rowIndex). getId ());

case 1:

return items. get (rowIndex). getVolume ();

case 2:

return items. get (rowIndex). getWeight ();

case 3:

return items. get (rowIndex). getRate1 ();

case 4:

return items. get (rowIndex). getRate2 ();

case 5:

return items. get (rowIndex). getRate3 ();

case 6:

return items. get (rowIndex). getRate4 ();

case 7:

return items. get (rowIndex). getRate5 ();

case 8:

return boss. getUtility (items. get (rowIndex));

case 9:

if (items. get (rowIndex). getPair ()! = null) {

return items. get (rowIndex). getPair (). getId ();

} else {

return null;

}

}

return null;

}

@Override

public boolean isCellEditable (int rowIndex, int columnIndex) {

if (columnIndex! = 0 && columnIndex! = 8 && columnIndex! = 9) {

return true;

}

return false;

}

@Override

public void removeTableModelListener (TableModelListener l) {. remove (l);

}

@Override

public void setValueAt (Object aValue, int rowIndex, int columnIndex) {i = items. get (rowIndex);

switch (columnIndex) {

case 1:. setVolume ( (Integer) aValue);

break;

case 2:. setWeight ( (Integer) aValue);

break;

case 3:. setRate1 ( (Integer) aValue);

break;

case 4:. setRate2 ( (Integer) aValue);

break;

case 5:. setRate3 ( (Integer) aValue);

break;

case 6:. setRate4 ( (Integer) aValue);

break;

case 7:. setRate5 ( (Integer) aValue);

break;

}

}

public void recountUtilities () {

for (int i = 0; i < items. size (); i++) {(ItemsViewer. this. boss. getUtility (items. get (i)), i,

);

}

}getElement (int index) {

return items. get (index);

}<Item> getElements () {

return items;

}

}

private JPanel viewer;

private JTable itemTable;

private JTable containersTable;

private JButton createPairButton;

private JButton breakPairButton;

private JLabel pairsNum;

private JLabel pairsCount;

private Packer packer;

private Boss boss;

public ItemsViewer (List<Container> containers, List<Item> items, Packer packer, Boss boss) {

this. boss = boss;

this. packer = packer;= new JPanel (new GridBagLayout ());itm = new ItemTableModel (items);. addTableModelListener (new TableModelListener () {

@Override

public void tableChanged (TableModelEvent e) {

( (ItemTableModel) e. getSource ()). recountUtilities ();

}

});= new JTable (itm);<ItemTableModel> sorter = new TableRowSorter<ItemTableModel> ( (ItemTableModel) itemTable. getModel ());. setSortable (9, false);. setRowSorter (sorter);. addMouseListener (new MouseAdapter () {

@Override

public void mouseReleased (MouseEvent arg0) {

int [] selectedRowIndices = ( (JTable) arg0. getComponent ()). getSelectedRows ();

if (selectedRowIndices. length == 2) {. setEnabled (false);

boolean single = true;

for (int index: selectedRowIndices) {= ( (JTable) arg0. getComponent ()). getModel (). getValueAt (index,

) == null;

if (! single) {. setEnabled (false);

break;

}

}

if (single) {. setEnabled (true);

}

} else if (selectedRowIndices. length == 1) {. setEnabled (false);

if ( ( (ItemTableModel) itemTable. getModel ()). getElement (selectedRowIndices [0]). hasPair ()) {. setEnabled (true);

} else {. setEnabled (false);

}

} else {. setEnabled (false);. setEnabled (false);

}

}

});= new JTable (new ContainerTableModel (containers));. setRowSorter (new TableRowSorter<ContainerTableModel> ( (ContainerTableModel) containersTable. getModel ()));= new JButton ("Создать пару");. addActionListener (new ActionListener () {

@Override

public void actionPerformed (ActionEvent e) {

int [] selectedRowIndices = itemTable. getSelectedRows ();i1 = ( (ItemTableModel) itemTable. getModel ()). getElement (selectedRowIndices [0]);i2 = ( (ItemTableModel) itemTable. getModel ()). getElement (selectedRowIndices [1]);. this. packer. createPair (i1, i2);. setText (ItemsViewer. this. packer. countPairs ( ( (ItemTableModel) itemTable. getModel ()). getElements ()) + "");. repaint ();

( (JButton) e. getSource ()). setEnabled (false);

}

});. setEnabled (false);= new JButton ("Разбить пару");. addMouseListener (new MouseAdapter () {

@Override

public void mousePressed (MouseEvent e) {i1 = ( (ItemTableModel) itemTable. getModel ()). getElement (itemTable. getSelectedRows () [0]);i2 = i1. getPair ();. this. packer. breakPair (i1, i2);. repaint ();

( (JButton) e. getSource ()). setEnabled (false);. setText (ItemsViewer. this. packer. countPairs ( ( (ItemTableModel) itemTable. getModel ()). getElements ()) + "");

}

});. setEnabled (false);= new JLabel ("Количество пар: ");= new JLabel (packer. countPairs ( ( (ItemTableModel) itemTable. getModel ()). getElements ()) + "");buttons = new JPanel ();. add (createPairButton);. add (breakPairButton);labels = new JPanel ();. add (pairsNum);. add (pairsCount);. add (new JScrollPane (itemTable), new GridBagConstraints (0, 0, 1, 1, 1, 1, GridBagConstraints. NORTHWEST, GridBagConstraints. VERTICAL, new Insets (5, 5, 5,5), 0, 0));. add (new JScrollPane (containersTable), new GridBagConstraints (1, 0, 1, 1, 1, 1, GridBagConstraints. NORTHWEST, GridBagConstraints. VERTICAL, new Insets (5, 5, 5,5), 0, 0));. add (buttons, new GridBagConstraints (0, 2, 1, 1, 1, 0, GridBagConstraints. SOUTHWEST, GridBagConstraints. NONE, new Insets (5, 5, 5,5), 0, 0));. add (labels, new GridBagConstraints (1, 2, 1, 1, 1, 0, GridBagConstraints. SOUTHWEST, GridBagConstraints. NONE, new Insets (5, 5, 5,5), 0, 0));

}

public void refreshTables (List<Container> containers, List<Item> items) {. setModel (new ItemTableModel (items));. setModel (new ContainerTableModel (containers));

}

/**

* @return the viewer

*/

public JPanel getViewer () {

return viewer;

}

}. java

package gui;

import java. awt. GridBagConstraints;

import java. awt. GridBagLayout;

import java. awt. Insets;

import java. awt. event. ActionEvent;

import java. awt. event. ActionListener;

import java. util. HashSet;

import java. util. List;

import java. util. Set;

import javax. swing. JButton;

import javax. swing. JCheckBox;

import javax. swing. JPanel;

import javax. swing. JScrollPane;

import javax. swing. JTable;

import javax. swing. event. TableModelListener;

import javax. swing. table. TableColumn;

import javax. swing. table. TableModel;

import core. Item;

import core. Packer;

import core. Store;

class ParetoLayersViewer {

class ParetoLayersTableModel implements TableModel {

private List<List<Item>> paretoLayers;

private Set<TableModelListener> listeners = new HashSet<TableModelListener> ();

public ParetoLayersTableModel (List<List<Item>> paretoLayers) {

super ();

this. paretoLayers = paretoLayers;

}

@Override

public void addTableModelListener (TableModelListener l) {. add (l);

}

@Override

public Class<? > getColumnClass (int columnIndex) {

return String. class;

}

@Override

public int getColumnCount () {

int maxLayerSize = 0;

for (List<Item> l: paretoLayers) {

int currentLayerSize = l. size ();

if (maxLayerSize < currentLayerSize) {= currentLayerSize;

}

}

return maxLayerSize;

}

@Override

public String getColumnName (int columnIndex) {

return (columnIndex + 1) + "";

}

@Override

public int getRowCount () {

return paretoLayers. size ();

}

@Override

public Object getValueAt (int rowIndex, int columnIndex) {<Item> paretoLayer = paretoLayers. get (rowIndex);

if (paretoLayer. size () > columnIndex) {

return paretoLayer. get (columnIndex). getId ();

}

return null;

}

@Override

public boolean isCellEditable (int rowIndex, int columnIndex) {

return false;

}

@Override

public void removeTableModelListener (TableModelListener l) {. remove (l);

}

@Override

public void setValueAt (Object aValue, int rowIndex, int columnIndex) {

}

}

private JPanel viewer;

private JTable paretoLayersTable;

private JCheckBox byUtilityBox;

private JCheckBox byVolumeBox;

private JCheckBox byWeightBox;

private JCheckBox processPairsBox;

private JButton recountButton;

private Store store;

private Packer packer;

public ParetoLayersViewer (GUI gui, Store store, Packer packer) {

this. store = store;

this. packer = packer;

this. viewer = new JPanel (new GridBagLayout ());

this. byUtilityBox = new JCheckBox ("По полезности", false);. addActionListener (new ActionListener () {

@Override

public void actionPerformed (ActionEvent arg0) {();

}

});

this. byVolumeBox = new JCheckBox ("По объёму", false);

this. byWeightBox = new JCheckBox ("По весу", false);

this. recountButton = new JButton ("Пересчитать");. addActionListener (new ActionListener () {

@Override

public void actionPerformed (ActionEvent e) {(ParetoLayersViewer. this. store. getItemsClones ());

}

});= new JCheckBox ("Обрабатывать парные объекты", true);checkBoxesPanel = new JPanel ();. add (byVolumeBox);. add (byWeightBox);. add (byUtilityBox);. add (processPairsBox);. add (recountButton);= new JTable ();. add (new JScrollPane (paretoLayersTable), new GridBagConstraints (0, 0, 1, 1, 1, 1, GridBagConstraints. NORTHWEST, GridBagConstraints. BOTH, new Insets (5, 5, 0, 0), 0, 0));. add (checkBoxesPanel, new GridBagConstraints (0, 1, 1, 1, 1, 1, GridBagConstraints. SOUTHWEST, GridBagConstraints. NONE, new Insets (5, 0, 5, 0), 0, 0));();

}

public void recountLayers (List<Item> sourceSet) {

if (processPairsBox. isSelected ()) {= packer. processPairs (sourceSet);

}<List<Item>> paretoSet = packer. createParetoSet (sourceSet);

if (byUtilityBox. isSelected ()) {

for (List<Item> paretoLayer: paretoSet) {. sort (paretoLayer, Packer. SORT_TYPE. UTILITY);

}

} else {

if (byVolumeBox. isSelected () && byWeightBox. isSelected ()) {

for (List<Item> paretoLayer: paretoSet) {. sort (paretoLayer, Packer. SORT_TYPE. VOLUME, Packer. SORT_TYPE. WEIGHT);

}

} else {

if (byVolumeBox. isSelected ()) {

for (List<Item> paretoLayer: paretoSet) {. sort (paretoLayer, Packer. SORT_TYPE. VOLUME);

}

} else if (byWeightBox. isSelected ()) {

for (List<Item> paretoLayer: paretoSet) {. sort (paretoLayer, Packer. SORT_TYPE. WEIGHT);

}

}

}

}. setParetoSet (paretoSet);. setModel (new ParetoLayersTableModel (paretoSet));

for (int i = 0; i < paretoLayersTable. getColumnCount (); i++) {column = paretoLayersTable. getColumn ( (i + 1) + "");. setMinWidth (35);

}

}

/**

* @return the paretoLayersPanel

*/

public JPanel getViewer () {

return viewer;

}

private void refreshBoxes () {

boolean state =! byUtilityBox. isSelected ();. setEnabled (state);. setEnabled (state);

}

}. java

package gui;

import java. awt.component;

import java. awt. GridBagConstraints;

import java. awt. GridBagLayout;

import java. awt. Insets;

import java. awt. event. ActionEvent;

import java. awt. event. ActionListener;

import java. awt. event. ItemEvent;

import java. awt. event. ItemListener;

import java. text. DecimalFormat;

import java. text. DecimalFormatSymbols;

import java. util. ArrayList;

import java. util. HashSet;

import java. util. Hashtable;

import java. util. List;

import java. util. Set;

import java. util. SortedMap;

import javax. swing.comboBoxModel;

import javax. swing. ImageIcon;

import javax. swing. JButton;

import javax. swing. JComboBox;

import javax. swing. JLabel;

import javax. swing. JPanel;

import javax. swing. JScrollPane;

import javax. swing. JSplitPane;

import javax. swing. JTextPane;

import javax. swing. JTree;

import javax. swing. event. ListDataListener;

import javax. swing. tree. DefaultMutableTreeNode;

import javax. swing. tree. DefaultTreeCellRenderer;

import javax. swing. tree. DefaultTreeModel;

import javax. swing. tree. TreeCellRenderer;

import javax. swing. tree. TreePath;

import core. Boss;

import core. Container;

import core. Item;

import core. Packer;

import core. Store;

import core. Packer. ALGORYTHM;

class ResultViewer {

private class Resume {

private String algNameReport;

private String effectivityReport;

private String restReport;

private String packedReport;

private DecimalFormat format;

public Resume () {f = new DecimalFormatSymbols ();. setDecimalSeparator ('. ');= new DecimalFormat ("#,##0.00", f);

}

/**

* @param algNameReport the algNameReport to set

*/

public void setAlgNameReport (String algNameReport) {

this. algNameReport = "<h2><font color='RED'>Алгоритм: " + algNameReport + "</text></h2><p>";

}

/**

* @param effectivityReport the effectivityReport to set

*/

public void setEffectivityReport (SortedMap<Container, List<Item>> map) {header = "<h3><font color='RED'>Эффективность алгоритма</font></h3>";

double occupiedSpacePercent = 0;

double loadPercent = 0;

double volumeAccumulator = 0;

double weightAccumulator = 0;

double iVolumeAccumulator = 0;

double cargoAccumulator = 0;

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

for (Item i: map. get (c)) {+= i. getVolume ();+= i. getWeight ();

}+= c. getVolume ();+= c. getCargo ();

}= (iVolumeAccumulator / volumeAccumulator) * 100;= (weightAccumulator / cargoAccumulator) * 100;occupiedSpacePercentString = getFormattedPair ("Процент заполнения пространства контейнеров", occupiedSpacePercent);loadPercentString = getFormattedPair ("Процент загрузки контейнеров", loadPercent);loadedItemsMass = getFormattedPair ("Общая масса упакованных объектов", weightAccumulator);loadedItemsVolume = getFormattedPair ("Общий объём упакованных объектов", iVolumeAccumulator);effectivityReport = occupiedSpacePercentString + loadPercentString + loadedItemsVolume + loadedItemsMass;

this. effectivityReport = header + effectivityReport;

}

/**

* @param restReport the restReport to set

*/

public void setRestReport (Store store) {header = "<h3><font color='RED'>Остаток на складе</font></h3>";

double volumeAccumulator = 0;

double weightAccumulator = 0;

for (Item i: store. getRest ()) {+= i. getVolume ();+= i. getWeight ();

}restVolume = getFormattedPair ("Общий объём оставшихся объектов", volumeAccumulator);restWeight = getFormattedPair ("Общий вес оставшихся объектов", weightAccumulator);

this. restReport = header + restVolume + restWeight;

}

/**

* @param packedReport the packedReport to set

*/

public void setPackedReport (SortedMap<Container, List<Item>> map) {packedReport = "<h3><font color='RED'>Упакованные объекты</font></h3>";

for (Container c: map. keySet ()) {containerID = "Контейнер ";itemsID = "Объекты: ";freeSpace = "Свободное место в контейнере: ";freeCargo = "Неиспользованная грузоподъёмность: ";

double iVolumeAccumulator = 0;

double iWeightAccumulator = 0;+= c. getId () + "<br>";

for (Item i: map. get (c)) {+= " " + i. getId ();+= i. getVolume ();+= i. getWeight ();

}+= "<br>";+= (c. getVolume () - iVolumeAccumulator) + "<br>";+= (c. getCargo () - iWeightAccumulator) + "<br>";+= containerID + itemsID + freeSpace + freeCargo + "<br>";

}

this. packedReport = packedReport;

}

/**

* @return the algNameReport

*/

public String getAlgNameReport () {

return algNameReport;

}

/**

* @return the effectivityReport

*/

public String getEffectivityReport () {

return effectivityReport;

}

/**

* @return the restReport

*/

public String getRestReport () {

return restReport;

}

/**

* @return the packedReport

*/

public String getPackedReport () {

return packedReport;

}

private String getFormattedPair (String string, double value) {

return "<font color='BLUE'>" + string + ": " +

"<font color='GREEN'><b>" + format. format (value) + "</b></font></font><br>";

}

}

private class ConsoleLogTextPane extends JTextPane {

/**

*

*/

private static final long serialVersionUID = - 5691372469851601341L;

private String TEMPLATE = "<html><title></title><body></body></html>";

private String buffer;

private int breakIndex;

public ConsoleLogTextPane () {(TEMPLATE);("text/html");= 0;

}

public void addString (String str) {= this. getText ();= buffer. lastIndexOf ("</body>");= buffer. substring (0, breakIndex) + str + buffer. substring (breakIndex);

this. setText (buffer);

}

public void clearConsole () {

this. setText (TEMPLATE);

}

}

class AlgorythmsComboBoxModel implements ComboBoxModel<String> {

private Set<ListDataListener> listeners;

private List<String> elements;

private String selected;

public AlgorythmsComboBoxModel (String. strings) {= new HashSet<ListDataListener> ();= new ArrayList<String> ();= "";

for (String s: strings) {. add (s);

}

}

@Override

public void addListDataListener (ListDataListener l) {. add (l);

}

@Override

public String getElementAt (int index) {

return elements. get (index);

}

@Override

public int getSize () {

return elements. size ();

}

@Override

public void removeListDataListener (ListDataListener l) {. remove (l);

}

@Override

public Object getSelectedItem () {

return selected;

}

@Override

public void setSelectedItem (Object anItem) {= (String) anItem;

}

}

class ResultTreeCellRenderer implements TreeCellRenderer {

private JLabel label = new JLabel ();

@Override

public Component getTreeCellRendererComponent (JTree tree, Object value,

boolean selected, boolean expanded, boolean leaf, int row,

boolean hasFocus) {

if ( (value! = null) && (value instanceof DefaultMutableTreeNode)) {icon = null;node = (DefaultMutableTreeNode) value;userObject = node. getUserObject ();

if (userObject instanceof Container) {= new ImageIcon (ResultViewer. class. getResource ("images/Container. png"));. setText ("Контейнер, ID: " + ( (Container) userObject). getId ());

} else if (userObject instanceof Item) {= new ImageIcon (ResultViewer. class. getResource ("images/Item. png"));. setText ("Объект, ID: " + ( (Item) userObject). getId ());

} else if (userObject instanceof String) {

if (node. getParent () == null ||. getParent () == value) {= new ImageIcon (ResultViewer. class. getResource ("images/Containers. png"));

} else {= new ImageIcon (ResultViewer. class. getResource ("images/Field. png"));

}. setText ( (String) node. getUserObject ());

}. setOpaque (true);

if (selected) {. setBackground (new DefaultTreeCellRenderer (). getBackgroundSelectionColor ());

} else {. setBackground (new DefaultTreeCellRenderer (). getBackgroundNonSelectionColor ());

}. setIcon (icon);

}

return label;

}

}

private JPanel viewer;

private JTree tree;

private JPanel treePanel;

private JPanel cBoxPanel;

private JButton packButton;

private JButton clearConsoleButton;

private ConsoleLogTextPane resumeLoggerPane;

private JSplitPane splitPane;

private JComboBox<String> algorythmsBox;

private Hashtable<String, Packer. ALGORYTHM> table;

private final String NO_ALGORYTHM_CHOSEN = "Выберите алгоритм";

private final String FIRST = "В первый подходящий";

private final String BEST = "В лучший из подходящих";

private Resume resume;

public ResultViewer (final GUI gui, final Store store, final Packer packer, final Boss boss) {= new ConsoleLogTextPane ();. setEditable (false);= new Resume ();top = new DefaultMutableTreeNode (" [пусто] ");= new Hashtable<String, Packer. ALGORYTHM> ();. put (FIRST, ALGORYTHM. FIRST);. put (BEST, ALGORYTHM. BEST);= new JComboBox<String> (new AlgorythmsComboBoxModel (NO_ALGORYTHM_CHOSEN, FIRST, BEST));. setSelectedIndex (0);. addItemListener (new ItemListener () {

@SuppressWarnings ("unchecked")

@Override

public void itemStateChanged (ItemEvent arg0) {. setEnabled ( ( (JComboBox<String>) arg0. getSource ()). getModel (). getSelectedItem ()! = NO_ALGORYTHM_CHOSEN &&. getParetoSetInstance ()! = null &&

! store. getParetoSetInstance (). isEmpty ());

}

});= new JButton ("Упаковать");. setEnabled (false);. addActionListener (new ActionListener () {

@Override

public void actionPerformed (ActionEvent arg0) {

if (store! = null) {. getRest (). clear ();

if (store. getParetoSetInstance ()! = null) {<List<Integer>> templates = store. getTemplates ();

double maxUtilityRate = 0;

int maxUtilityIndex = 0;<Container, List<Item>> map = null;

for (int i = 0; i < templates. size (); i++) {= store. getMapClone (i);

for (List<Item> paretoLayer: store. getParetoSetClone ()) {. pack (map, paretoLayer, table. get (algorythmsBox. getSelectedItem ()));

}

double utilityRate = boss. getPackUtility (map);

if (maxUtilityRate < utilityRate) {= utilityRate;= i;

}. getRest (). clear ();

}= store. getMapClone (maxUtilityIndex);

for (List<Item> paretoLayer: store. getParetoSetClone ()) {. pack (map, paretoLayer, table. get (algorythmsBox. getSelectedItem ()));

}(map); resume. setAlgNameReport ( (String) ResultViewer. this. algorythmsBox. getSelectedItem ());. setEffectivityReport (map);. setRestReport (store);. setPackedReport (map);. addString (resume. getAlgNameReport ());. addString (resume. getEffectivityReport ());. addString (resume. getRestReport ());. addString (resume. getPackedReport ());

}

}

}

});= new JButton ("Очистить");. addActionListener (new ActionListener () {

@Override

public void actionPerformed (ActionEvent arg0) {. this. resumeLoggerPane. clearConsole ();

}

});= new JPanel (new GridBagLayout ());= new JTree (top);. setCellRenderer (new ResultTreeCellRenderer ());= new JPanel (new GridBagLayout ());. add (new JScrollPane (tree), new GridBagConstraints (0, 0, 1, 1, 1, 1, GridBagConstraints. NORTHWEST, GridBagConstraints. BOTH, new Insets (0, 0, 0, 0), 0, 0));= new JPanel (new GridBagLayout ());= new JSplitPane (JSplitPane. HORIZONTAL_SPLIT, treePanel, cBoxPanel);. setOneTouchExpandable (true);. setDividerLocation (350);. add (new JScrollPane (resumeLoggerPane), new GridBagConstraints (0, 0, 2, 1, 1, 1, GridBagConstraints. NORTHEAST, GridBagConstraints. BOTH, new Insets (0, 0, 0, 0), 0, 0));. add (algorythmsBox, new GridBagConstraints (0, 1, 1, 1, 0, 0, GridBagConstraints. NORTHEAST, GridBagConstraints. NONE, new Insets (0, 0, 0, 0), 0, 0));. add (packButton, new GridBagConstraints (1, 1, 1, 1, 0, 0, GridBagConstraints. NORTHWEST, GridBagConstraints. NONE, new Insets (0, 0, 0, 0), 0, 0));. add (clearConsoleButton, new GridBagConstraints (1, 1, 1, 1, 0, 0, GridBagConstraints. NORTHEAST, GridBagConstraints. NONE, new Insets (0, 0, 0, 0), 0, 0));. add (splitPane, new GridBagConstraints (0, 0, 1, 1, 1, 1, GridBagConstraints. NORTHWEST, GridBagConstraints. BOTH, new Insets (5, 5, 5,5), 0, 0));

}

public void refreshTree (SortedMap<Container, List<Item>> map) {root = new DefaultMutableTreeNode ("Упакованные объекты", true);(root, map);

}

private void createTree (DefaultMutableTreeNode root, SortedMap<Container, List<Item>> map) {

( (DefaultMutableTreeNode) ( (DefaultTreeModel) tree. getModel ()). getRoot ()). removeAllChildren ();

( (DefaultTreeModel) tree. getModel ()). setRoot (root);container = null;item = null;containerField = null;itemField = null;<Container> containers = map. keySet ();

for (Container c: containers) {= new DefaultMutableTreeNode (c, true);<Item> items = map. get (c);= new DefaultMutableTreeNode ("ID: " + c. getId (), false);. add (containerField);= new DefaultMutableTreeNode ("Объём: " + c. getVolume (), false);. add (containerField);= new DefaultMutableTreeNode ("Грузоподъёмность: " + c. getCargo (), false);. add (containerField);

for (Item i: items) {= new DefaultMutableTreeNode (i, true);= new DefaultMutableTreeNode ("ID: " + i. getId (), false);. add (itemField);= new DefaultMutableTreeNode ("Объём: " + i. getVolume (), false);. add (itemField);= new DefaultMutableTreeNode ("Вес: " + i. getWeight (), false);. add (itemField);= new DefaultMutableTreeNode ("Кр.1: " + i. getRate1 (), false);. add (itemField);= new DefaultMutableTreeNode ("Кр.2: " + i. getRate2 (), false);. add (itemField);= new DefaultMutableTreeNode ("Кр.3: " + i. getRate3 (), false);. add (itemField);= new DefaultMutableTreeNode ("Кр.4: " + i. getRate4 (), false);. add (itemField);= new DefaultMutableTreeNode ("Кр.5: " + i. getRate5 (), false);. add (itemField);

if (i. hasPair ()) {= new DefaultMutableTreeNode ("ID парного объекта: " + i. getPair (). getId ());. add (itemField);

}. add (item);

}. add (container);

}. expandPath (new TreePath ( ( (DefaultMutableTreeNode) ( (DefaultMutableTreeNode) root. getChildAt (0)). getChildAt (3)). getPath ()));

}

/**

* @return the viewer

*/

public JPanel getViewer () {

return viewer;

}

}

Пакет launcher.. java

package launcher;

import gui. GUI;

import util. ContainerTemplate;

import util. IntegerDiapason;

import util. ItemTemplate;

import core. Boss;

import core. Packer;

import core. Store;

public class LayouterLauncher {

/**

* @param args

*/

public static void main (String [] args) {

// Задаём ограничения на предельные значения параметров объектов и контейнеров.ct = new ContainerTemplate (new IntegerDiapason (25, 40), new IntegerDiapason (25, 40));it = new ItemTemplate (new IntegerDiapason (1, 20),

new IntegerDiapason (1, 20),

new IntegerDiapason (1,5),

new IntegerDiapason (1,5),

new IntegerDiapason (1,5),

new IntegerDiapason (1,5),

new IntegerDiapason (1,5)

);

// Создаём склад.store = new Store ();

// Создаём ЛПРboss = new Boss ();

// Создаём упаковщика.packer = new Packer (store, boss);

new GUI (store, packer, boss, ct, it);

}

}


Оглавление Введение Основные понятия теории принятия решений Формализация задач принятия решений Однокритериальные задачи в условиях определенно

Больше работ по теме:

КОНТАКТНЫЙ EMAIL: [email protected]

Скачать реферат © 2017 | Пользовательское соглашение

Скачать      Реферат

ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ