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

АктуальностьРациональное расходование материальных и информационных ресурсов является важной научно-технической и практической задачей. Рациональное расходование ресурсов неразрывно связано с эффективным использованием финансовых затрат. В связи с этим классические постановки практических задач пересматриваются и возникают новые, в которых учитывается эта составляющая. Прототипом практических задач расходования материальных и информационных ресурсов, которые рассматриваются в диссертационной работе, являются известные классические задачи. В постановке известной задачи загрузки одного процессора целевая функция определяется как среднее время обслуживания работ [1]. В формулировке задачи одного станка в качестве целевойфункции используется' время обработки деталей. Поиском приложений задачи Джонсона (задачи о станках) продолжают заниматься в настоящее время [2 — 4]. В классической постановке задачи раскроя материалов критерием оптимизации является количество комплектов' [5, 6]. В диссертации будет рассматриваться ряд двухкритериальных задач, прототипами которых являются указанные однокритериальные. В качестве критериев решения задачи оптимальной загрузки контейнера определяется суммарная стоимость погрузки и суммарный вес предметов. Оптимальная загрузка станка предполагает максимизацию прибыли от реализации деталей и минимизацию времени изготовления деталей. Первый критерий при оптимальном раскрое материала — площадь остатка листа, а второй — количество разрезов (что приводит к экономии энергии). Оптимальное сохранение файлов предполагает максимизацию суммарного объёма и максимизацию количества сохраняемых файлов. Во всех этих задачах предусматривается рациональное расходование материальных и информационных ресурсов (стройматериала, памяти информационного носителя, грузоподъёмности автотранспортного средства). Эта информация задаётся в виде ограничения в постановках рассмотренных задач. В рассмотренных двухкритериальных задачах первый критерий является главным, а второй второстепенным, но в совокупности они описывают одну оптимизационную задачу и являются неразделимыми. Таким образом, их можно отнести к классу лексикографических многокритериальных задач [7 -9]. В настоящее время существует два основных подхода к решению этого класса задач:

— последовательная оптимизация;

— скаляризация векторного критерия.

Первый способ [10] предполагает разбиение многокритериальной задачи на последовательность взаимосвязанных однокритериальных задач и их решение. Второй способ [11, 12] предполагает нормализацию частных критериев в составе векторного, и далее построение суперкритерия, агрегирующего частныекритерии исходной многокритериальной задачи. В рамках подходов существуют методы решения: метод последовательных уступок и метод свёртки в агрегированный критерий. Процедура решения многокритериальной задачи методом последовательных уступок [13] заключается в том, что все частные критерии располагают и нумеруют в порядке их относительной важностимаксимизируют первый, наиболее важный критерийзатем назначают величину допустимого снижения значения этого критерия и максимизируют второй по важности частный критерий при условии, что значение первого критерия не должно отличаться от максимального более чем на величину установленного сниженияснова назначают величину уступки, но уже по второму критерию и находят максимум третьего по важности критерия при условии, чтобы значения первых двух критериев не отличались от ранее найденных максимальных значений больше чем на величины соответствующих уступокдалее поочередно используются все остальные частные критерииоптимальной обычно считают любую стратегию, которая получена при решении задачи отыскания условного максимума последнего по важности критерия. Таким образом, при использовании метода последовательных уступок многокритериальная задача сводится к поочередной максимизации частных критериев и выбору величин уступок. Величины уступок характеризуют отклонение приоритета одних частных критериев перед другими: чем уступки меньше, тем приоритет жестче. Одним из распространенных методов [14] решения многокритериальных задач является метод сведения многокритериальной задачи к однокритериальной путем свертывания векторного критерия в суперкритерий. При этом каждый критерий умножается на соответствующий ему весовой коэффициент (коэффициент важности). При этом возникают трудности с правильным подбором весовых коэффициентов.

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

Это направление является актуальным. Существует ряд двухкритериальных лексикографических задач, которые были сформулированы на современном этапе, например:

— при разработке методов решения вершинного варианта задачи анализа уязвимости сетевых систем была сформулирована задача анализа уязвимости многопродуктовой сети с учетом выхода из строя полностью одной или нескольких вершин, которая формализована в виде двухкритериальной лексикографической задачи оптимизации [15];

— при оптимизации инвестиционного портфеля страховщика требуется найти такую структуру портфеля, для которой ожидаемая доходность максимальна, а совокупный риск минимален, то есть возникает формальная двухкритериальная постановка [16].

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

Ногин В.Д., Пападимитриу X., Подиновский В. В., Стайглиц К., Табак Д. t.

Среди актуальных приложений лексикографической многокритериальной задачи можно выделить несколько наиболее перспективных. Применение для,-нахождения эффективных управлений при исследовании динамики-: продольного движения пучка заряженных частицв ускорителе на бегущей" волне [17], принятия решения в управлении экономикой [18], управления ассортиментной политикой предприятий оптовойторговли [19], расчёта показателей эффективности технологической-системы производства гибридных интегральных схем [20], оценки эффективности информационных систем с использованием технологии открытых систем сетевой среды филиала банка) [21], анализа технологичности карт раскроя материалов при производстве мебели [22].

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

В диссертационной работе рассматривается булева двухкритериальная задача о рюкзаке. Применительно к практическим задачам, указанным ранее, ее можно классифицировать как информационную модель. Действительно, два входных вектора Я=(г,) и /.=(//), /= 1,2,.^, которые на практике несут определенную информацию о моделируемом явлении, преобразуются в выходной вектор у* (оптимальное решение двухкритериальной задачи о рюкзаке). Преобразование задается как оптимизационная двухкритериальная задача о рюкзаке (система линейных критериев и ограничение).

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

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

Для достижения цели диссертационной работы требуется решение следующих задач:

— сформулировать постановку двухкритериальной задачи из класса лексикографических многокритериальных задач (видоизменение задачи о рюкзаке) применительно к расходованию материальных и информационных ресурсов;

— разработать алгоритм решения поставленной задачи;

— исследовать временную сложность предложенного алгоритма решения данной задачи в сравнении с известными методами решения задач рассматриваемого класса;

— оценить эффективность разработанного алгоритма в практическом аспекте. Методы исследования.

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

Научная новизна. Научная новизна диссертационной работы заключается в следующем:

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

2. Сформулировано и обосновано1 положение о независимости решения^ двухкритериальной! задачи* о рюкзаке от перестановки, числовых коэффициентов, определяемых при её постановке. Положение отличается от аналогов в данном классе задач и на практике позволяет оптимизировать расход материальных и информационных ресурсов.

3. Для решения двухкритериальной задачи о рюкзаке адаптированы метод свертывания в агрегированный критерий, выведены формулы расчёта числовых коэффициентов. Получено отличное от известных в данном классе задач формальное описание метода решения* рассматриваемой задачи, что позволило представить программную реализацию решения.

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

Основные положения, выносимые на защиту.

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

2. Положение о независимости решения рассматриваемой двухкритериальной задачи от перестановки числовых коэффициентов, определяемых при её постановке.

3. Адаптированный метод свертывания в агрегированный критерий для. решения двухкритериальной задачи о рюкзаке, формулы расчёта числовых коэффициентов.

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

Практическая ценность.

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

Полученные в работе результаты использованы в ООО «МиР» (Ростов-на-Дону), приняты для загрузки автотранспорта при перевозке стройматериаловв ЗАО ГПСФ «Гефест ВПР» (Таганрог) для изготовления комплектующих при производстве металлоконструкций, что подтверждено соответствующими актами об использовании, приведенными в приложении 8 к диссертационной работе.

Внедрение и использование результатов работы.

Полученные в работе результаты использованы в ООО «МиР» (Ростов-на-Дону), приняты для загрузки автотранспорта при перевозке стройматериаловв ЗАО ПКФ «Гефест ВПР» (Таганрог) для изготовления комплектующих при производстве металлоконструкций, что подтверждено соответствующими актами об использовании, приведенными в приложении 8 к диссертационной работе.

Апробация работы. Основные результаты диссертационной работы докладывались на:

— Отраслевой научно-технической конференции «Актуальные проблемы развития железнодорожного транспорта и роль молодых ученых в их решении» (г. Ростов-на-Дону, 1998 г.);

— Всероссийской научной конференции «Новые информационные технологии. Разработка и аспекты применения» (г. Таганрог, 2000 г.);

— Международной, научно-технической конференции «Математические методы в экономике» (г. Пенза, 2002 г.);

— 53 научно-технической конференции профессорско-преподавательского состава, аспирантов и сотрудников Технологического института Южного федерального университета в г. Таганроге (2008 г.).

Основные результаты опубликованы в 7 печатных работах, из них 2 работы в изданиях, входящих в перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации, утверждённый ВАК. Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 96 наименований, и 8 приложений. Работа изложена на 119 стр., включает 85 стр. приложений, содержит 9 рисунков и 8 таблиц.

4.4. Выводы.

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

В этой главе рассматривается применение двухкритериальной задачи о рюкзаке, в постановке которой коэффициенты первого — критерия полагаются равными соответствующим коэффициентам ограничения, а коэффициенты второго критерия равны единицам. Эта двухкритериальная задача о рюкзаке является моделью оптимального сохранения файлов на носитель информации и оптимального раскроя материала. В первом случае в качестве главного критерия используется общий’объем-сохраняемых файлов, а вторым критерием' является их количество: Во втором случае главным критерием является суммарная длина листов-заказов, которые получаются в результате раскроя исходного листа, а второй критерий определяется количеством разрезов исходного листа. Для оптимального сохранения файлов и оптимального раскроя материала рассчитана сравнительная эффективность по маркетинговому подходу. Оптимальное сохранение файлов в 14 раз, а оптимальный раскрой материала в 10 раз эффективнее способа, используемого на практике.

ЗАКЛЮЧЕНИЕ

.

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

Работа содержит следующие научные результаты:

1. Метод решения двухкритериальной задачи о рюкзаке, основанный на частичном переборе допустимых решений путём расширения линейного пространства допустимых решений. Опубликовано в [83−85, 87, 89].

Метод двойной оптимизации предполагает построение множеств допустимых решений С, — однокритериальных задач о рюкзаке размерности' г-1,2,.^. Решения множества С, — строятся из решений множества С,-./. Каждое решение из С/./ порождает два решения размерности г, которые включаются в С,-, если они* являются' допустимыми и если в С, — нет доминирующих векторов. Условие доминирования реализует оптимизацию по двум критериям, то есть одно-решение доминирует над другим и" включается" во множество допустимых решений, если по значению критерия Ь задачи (1Л) они равны, а по значению критерия Я доминирующее меньше. Именно в этом случае происходит оптимизация по второму критерию. По критерию Ь допустимые решения оптимизируются, когда упорядочиваются во множестве С, — по значению этого критерия.

2. Положение о независимости решения рассматриваемой двухкритериальной задачи от перестановки числовых коэффициентов, определяемых при её постановке. Опубликовано в [96].

В диссертации доказывается, что МДО на одной перестановке коэффициентов задачи (1.1) приводит к оптимальному решению. Но МДО приводит к глобальному оптимуму, если выборка коэффициентов, соответствующая решению, не зависит от перестановки коэффициентов в исходной задаче (1.1). Это положение формулируется в виде гипотезы. Гипотеза обосновывается экспериментально. Рассматривается тысяча перестановок коэффициентов произвольных задач вида (1.1), и оцениваются выборки коэффициентов, соответствующие решениям. Результаты не опровергают гипотезы.

3. Адаптированный метод свертывания в агрегированный критерий для решения двухкритериальной задачи о рюкзаке, формулы расчёта числовых коэффициентов. Опубликовано в [96].

Для решения двухкритериальной задачи о рюкзаке методом свертывания в агрегированный критерий было необходимо решить оптимизационную задачу 3.2. Для решения этой задачи не разработано методов решенияБыло замеченочто оптимальное решение этой задачи можно определить, решив* последовательность задач вида 3.4. Эти задачи^ решались, методом функциональных уравнений динамического программирования.

4. Сравнительные оценки временной сложности предложенного метода, метода последовательных уступок и. свертыванияв- агрегированный критерий, согласно которым предложенный метод решает рассматриваемую задачувдвое быстрее первого и в пятьраз быстрее второго. Предварительные. результаты опубликованы в [86], а окончательные в [96].

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

МДО = °'6 198 секУ"Ды, ашУ = °>°14 193 секунды, &-*мсАК = °>79 317 секунды, то сравнение проводилось по оценкам математического ожидания.

Н* >Ц Н*.

Мщ0 =0,109 980 секунды, Мшу = 0,239 720секунды, ММСАК = 0,500 080 секунды. В итоге сравнения проведено ранжирование МДО, МПУ, МСАК по быстродействию. Самый эффективный МДО, его быстродействие в среднем— 0,109 980 секунды. Менее быстрый МПУ, его быстродействие в среднем—.

0.239 720.секунды. И самый медленный МСАК, его быстродействие в среднем— 0,500 080 секунды. То есть МДО быстрее МПУ в 2 раза и быстрее МСАК в 5 раз.

Научная новизна. Научная новизна диссертационной работы заключается в следующем:

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

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

3. Для решения двухкритериальной задачи о рюкзаке адаптированы метод свертывания в агрегированный критерий, выведены формулы расчёта числовых коэффициентов. Получено отличное от известных в данном классе задач формальное описание метода решения рассматриваемой задачи, что позволило представить программную реализацию решения.

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

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

Полученные в работе результаты использованы в ООО «МиР» (Ростов-на-Дону), приняты для загрузки автотранспорта при перевозке стройматериаловв ЗАО ПКФ «Гефест ВПР» (Таганрог) для изготовления комплектующих при производстве металлоконструкций, что подтверждено соответствующими актами об использовании, приведенными в приложении 8 к диссертационной работе.

Внедрение и использование результатов работы.

Полученные в работе результаты использованы в ООО «МиР» (Ростов-на-Дону), приняты для загрузки автотранспорта при перевозке стройматериаловв ЗАО ПКФ «Гефест ВПР» (Таганрог) для изготовления комплектующих при производстве металлоконструкций, что подтверждено соответствующими актами об использовании, приведенными в приложении 8 к диссертационной работе.