ПОИСК Статьи Чертежи Таблицы МНОГОКРИТЕРИАЛЬНАЯ ЗАДАЧА ОБ УПАКОВКЕ В КОНТЕЙНЕРЫ Постановка задачи из "Объективные модели и субъективные решения " При /С=1 и многих критериях оценки качества упаковываемых предметов мы имеем многокритериальную задачу о многомерном рюкзаке. Менее известна так называемая задача об упаковке в контейнеры. Эта задача ставится следующим образом [2—4]. Имеется конечное множество объектов, причем размер каждого из них задан рациональным числом. Требуется упаковать предметы в минимально возможное, количество контейнеров так, чтобы суммарный размер объектов Б каждом контейнере не превышал его размер (также рациональное число). Рассматриваемая задача является Л/Р-трудной, т. е., по всей вероятности, нельзя построить точный эффективный алгоритм ее решения. Однако есть ряд простых эвристических алгоритмов, причем с хорошими оценками качества решения [2, 3. Приведем наиболее известные из них. [c.68] Несмотря на явную простоту этих алгоритмов, был получен ряд очень хороших верхних оценок для худшего случая. Приведем оценку для алгоритма ППУ. [c.68] Интересно, что для интуитивно представляюш,ихся лучшими алгоритмов ЛП и ЛПУ не найдено лучших оценок, чем для очень простых алгоритмов ПП и ППУ. [c.69] Введем еще некоторые обозначения. [c.70] Пусть N — количество критериев — количество оценок на шкале -го критерия, эти оценки расположены на порядковой шкале от 1-й к м в порядке убывания качества. [c.70] Пусть Ai—множество оценок на шкале -го критерия, тогда ...Ау — множество векторных оценок у,= (уД. .., — произвольная векторная оценка Уi Y. [c.70] Вернуться к основной статье