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

• Автор: Замкова, Любовь Ивановна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Таганрог
• Количество страниц: 205 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.

ГЛАВА 1. ДВУХКРИТЕРИАЛЬНАЯ ЗАДАЧА О РЮКЗАКЕ И МЕТОДЫ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ.

1.1. Описание двухкритериальной задачи о рюкзаке.

1.2. Многокритериальные задачи оптимизации.

1.3. Метод последовательных уступок

1.4. Метод свертывания в актированный критерий.

1.5. Методы решен ия однокритериальных задач.

1.6. Выводы

ГЛАВА 2. РАЗРАБОТКА МЕТОДА РЕШЕНИЯ

ДВУХКРИТЕРИАЛЬНОЙ ЗАДАЧИ О РЮКЗАКЕ.

2.1 .Метод двойной оптимизации.
2.2. Программная реализация метода двойной оптимизации.
2.3. Примеры решения задач методом двойной оптимизации.
2.4. Обоснование метода двойной оптимизации
2.5. Выводы
ГЛАВА 3. СРАВНИТЕЛЬНЫ Й АНАЛИЗ МЕТОДА ДВОЙНОЙ ОПТИМИЗАЦИИ С МЕТОДОМ ПОСЛЕДОВАТЕЛЬНЫХ УСТУПОК И МЕТОДОМ СВРТЫВАНИЯ В АГРЕГИРОВАННЫЙ КРИТЕРИЙ
3.1. Реализация метода последовательных уступок применительно
к двухкритериальной задаче о рюкзаке.
3.2. Адаптация метода свертывания в агрегированный критерий
к двухкритсриалыюй задаче о рюкзаке
3.3. Исследование метода двойной оптимизации.
3.3.1. Этапы эксперимента по анализу времени решения метода двойной оптимизации МДО
3.3.2. Определение зависимости времени решения задач методом МДО от размерности задач г, заданного диапазона.
3.3.3. Ранжирование по времени решения задач методом двойной оптимизации, методом последовательных уступок и методом свертывания в агрегированный
критерий
3.4. Выводы
ГЛАВА 4. ПРИМЕНЕНИЕ ДВУХКРИТЕРИАЛЬНОЙ ЗАДАЧИ
О РЮКЗАКЕ
4.1. Применение двухкритериальной задачи о рюкзаке при оптимальном сохранении файлов на носитель информации.
4.2. Применение двухкритериальной задачи о рюкзаке для оптимального раскроя материала
4.3. Применение двухкритериальной задачи о рюкзаке для оптимальной загрузки контейнера
4.4. Выводы.
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Существует большое количество постановок оптимизационных теоретических задач, которые являются обобщением практических задач в различных областях. На практике существует ряд задач: оптимальное сохранение файлов на носитель информации, оптимальная загрузка контейнера, оптимальная загрузка станка, оптимизация раскроя материала, которые можно описать одной моделью (оптимизационной математической задачей). Приведем постановки указанных практических задач, которые описываются математической моделью, двухкритериальной задачей о рюкзаке (1. Оптимальная загрузка контейнера Имеется множество предметов, которые необходимо загрузить в контейнер. Грузоподъемность контейнера ограничена и равна П. Для каждого предмета известен вес г, и /, — стоимость погрузки. Необходимо выбрать из исходного множества те предметы, которые но суммарному весу можно загрузить в контейнер. При этом максимизировать оплату за погрузку этих предметов. Если существуют наборы предметов, дающие максимальную оплату за погрузку, которые по весу можно поместить в контейнер, то выбрать набор минимальный по весу. При формулировании задачи оптимальной загрузки контейнера использовалась задача загрузки одного процессора [,]. В задаче загрузки процессора критерием является среднее время обслуживания работ, а общий' директивный срок не задан. В задаче загрузки контейнера в качестве ранжированных критериев определяется суммарная стоимость погрузки и суммарный вес предметов. Кроме того накладывается ограничение О на вес загружаемых предметов — аналог общего директивного срока в задаче загрузки процессора. Оптимальная загрузка станка Имеется множество заказов на изготовление деталей* которые необходимо выполнить на станке в течение рабочего дня продолжительностью П. Для каждой детали известна прибыль- от ее реализации // и время, гц. Необходимо выбрать из исходного множества заказов на изготовление деталей те, которые можно в совокупности но времени изготовить за рабочий день. При этом максимизировать прибыль, от их реализации. Если есть, наборы деталей, которые можно изготовить за рабочий-день, дающие максимальную. Формулировка известной постановки задачи одного станка приводится в? В качестве единственного критерия оптимизации в- ней устанавливается минимизация суммарного времени обработки деталей. В настоящее время для предприятий главным критерием является получение наибольшей прибыли при ограниченном ресурсе времени. Имеется множество заказов на раскрой исходного материала в виде прямоугольного листа длиной ? Н, где П»Н (/) много больше 1-Г). Заказы представляют собой прямоугольные листы длиной г, (/=1,2,. Н. Необходимо из множества заказов выбрать те, которые можно исполнить в рамках длины исходного листа, располагая листы-заказы по длине вдоль длины исходного листа. При этом минимизировать остаток исходного листа по длине. Если наборов исполняемых заказов, минимизирующих остаток исходного листа, несколько, то выбрать минимальный по количеству разрезов. Формальная постановка оптимального раскроя прямоугольного листа— двухкритериальная задача о рюкзаке, в которой коэффициенты первого критерия полагаются равными соответствующим коэффициентам ограничения,, а коэффициенты второго критерия равны единицам. Идея раскроя материалов представлена в рабо те []. В качестве критерия-оптимизации определено количество комплектов. В задаче оптимального раскроя материала рассматривается один комплект раскроя прямоугольного листа. Поэтому в отличие от задачи раскроя материалов целесообразно определить в качестве главного критерия площадь оставшегося исходного листа после раскроя. Вторым критерием является минимизация количества разрезов, что позволяет рационально расходовать энергию при раскрое. Рассмотрим пример указанной двухкритериальной- задачи о рюкзаке. Существует множество заказов на раскрой листа. Для каждого заказа множества заказов известна длина гу=0 сантиметров, г2=0 сантиметров, /*3=0 сантиметров, /у=0 сантиметров, /*5=0 сантиметров, г6=0 сантиметров, гт=0 сантиметров. Кроме того существует исходный лист длиной />=0 сантиметров, который необходимо раскроить на заказы.