Введение к работе
Актуальность. Рациональное расходование материальных и информационных ресурсов является важной научно-технической и практической задачей. Рациональное расходование ресурсов неразрывно связано с эффективным использованием финансовых затрат. В связи с этим классические постановки практических задач пересматриваются и возникают новые, в которых учитывается эта составляющая. Прототипом практических задач расходования материальных и информационных ресурсов, которые рассматриваются в диссертационной работе, являются известные классические задачи. В постановке известной задачи загрузки одного процессора целевая функция определяется как среднее время обслуживания работ. В формулировке задачи одного станка в качестве целевой функции используется время обработки деталей. Поиском приложений задачи Джонсона (задачи о станках) продолжают заниматься в настоящее время . В классической постановке задачи раскроя материалов критерием оптимизации является количество комплектов. В диссертации будет рассматриваться ряд двухкритериальных задач, прототипами которых являются указанные одно критериальные. В качестве критериев решения задачи оптимальной загрузки контейнера определяется суммарная стоимость погрузки и суммарный вес предметов. Оптимальная загрузка станка предполагает максимизацию прибыли от реализации деталей и минимизацию времени изготовления деталей. Первый критерий при оптимальном раскрое материала - площадь остатка листа, а второй - количество разрезов (что приводит к экономии энергии). Оптимальное сохранение файлов предполагает максимизацию суммарного объёма и максимизацию количества сохраняемых файлов. Во всех этих задачах предусматривается рациональное расходование материальных и информационных ресурсов (стройматериала, памяти информационного носителя, грузоподъёмности автотранспортного средства). Эта информация задаётся в виде ограничения в постановках рассмотренных задач. В рассмотренных двухкритериальных задачах первый критерий является главным, а второй второстепенным, но в совокупности они описывают одну оптимизационную задачу и являются неразделимыми. Таким образом, их можно отнести к классу лексикографических многокритериальных задач.
В настоящее время существует два основных подхода к решению этого класса задач:
последовательная оптимизация;
скаляризация векторного критерия.
Первый способ предполагает разбиение многокритериальной задачи на последовательность взаимосвязанных однокритериальных задач и их решение.
Второй способ предполагает нормализацию частных критериев в составе векторного, и далее построение суперкритерия, агрегирующего частные критерии исходной многокритериальной задачи. В рамках подходов существуют методы решения: метод последовательных уступок и метод свёртки в агрегированный критерий. Процедура решения многокритериальной задачи методом последовательных уступок заключается в том, что все частные критерии располагают и нумеруют в порядке их относительной важности; максимизируют первый, наиболее важный критерий; затем назначают величину допустимого снижения значения этого критерия и максимизируют второй по важности частный критерий при условии, что значение первого критерия не должно отличаться от максимального более чем на величину установленного снижения; снова назначают величину уступки, но уже по второму критерию и находят максимум третьего по важности критерия при условии, чтобы значения первых двух критериев не отличались от ранее найденных максимальных значений больше чем на величины соответствующих уступок; далее поочередно используются все остальные частные критерии; оптимальной обычно считают любую стратегию, которая получена при решении задачи отыскания условного максимума последнего по важности критерия. Таким образом, при использовании метода последовательных уступок многокритериальная задача сводится к поочередной максимизации частных критериев и выбору величин уступок. Величины уступок характеризуют отклонение приоритета одних частных критериев перед другими: чем уступки меньше, тем приоритет жестче. Одним из распространенных методов решения многокритериальных задач является метод сведения многокритериальной задачи к однокритериальной путем свертывания векторного критерия в суперкритерий. При этом каждый критерий умножается на соответствующий ему весовой коэффициент (коэффициент важности). При этом возникают трудности с правильным подбором весовых коэффициентов.
Методы применяются к общей постановке лексикографической многокритериальной задачи. Целесообразно выделить из этого класса задачу, которая является моделью рассмотренных практических двухкритериальных задач. Формулирование частной постановки задачи, принадлежащей указанному классу, даёт возможность решать её известными общими методами, но остаётся актуальной разработка нового эффективного метода решения именно этой задачи.
Это направление является актуальным. Существует ряд двухкритериальных лексикографических задач, которые были сформулированы на современном этапе, например:
при разработке методов решения вершинного варианта задачи анализа уязвимости сетевых систем была сформулирована задача анализа уязвимости многопродуктовой сети с учетом выхода из строя полностью одной или нескольких вершин, которая формализована в виде двухкритериальной лексикографической задачи оптимизации;
при оптимизации инвестиционного портфеля страховщика требуется найти такую структуру портфеля, для которой ожидаемая доходность максимальна, а совокупный риск минимален, то есть возникает формальная двухкритериальная постановка.
Недостатком метода последовательных уступок является то, что в итоге поиск решения однокритериальных задач базируется на симплекс-методе, который относится к классу экспоненциальных. Это приводит к существенным временным затратам. Недостатком метода свёртки в функционал является то, что при решении итоговой однокритериальной задачи многократно используется один и тот же метод, что также ведёт к увеличению затрат времени на поиск решения. Для разработки метода решения частной двухкритериальной постановки целесообразно выбрать подход расширения линейного пространства, которое включает область допустимых решений. При этом подходе за счёт отсечений достигается уменьшение количества перебираемых решений. Совершенствованием и разработкой методов решения оптимизационных задач различных классов занимались Брахман Т.Р., Данциг Д., Заславский А.А., Куо Б., Карелин В.П., Констанденко О.С, Лебедев Б.К, Ногин В.Д., Пападимитриу X., Подиновский В.В., Стайглиц К., Табак Д. и др.
Среди актуальных приложений лексикографической многокритериальной задачи можно выделить несколько наиболее перспективных. Применение для нахождения эффективных управлений при исследовании динамики продольного движения пучка заряженных частиц в ускорителе на бегущей волне, принятия решения в управлении экономикой, управления ассортиментной политикой предприятий оптовой торговли, расчёта показателей эффективности технологической системы производства гибридных интегральных схем, оценки эффективности информационных систем с использованием технологии открытых систем (сетевой среды филиала банка), анализа технологичности карт раскроя материалов при производстве мебели.
Таким образом, на практике было выявлено существование ряда задач, которые требуют более эффективных решений, например, задача загрузки контейнера, задача сохранения файлов на внешний носитель
информации, задача раскроя материала и так далее. Формулирование оптимизационной модели этих практических задач, дает возможность разработки эффективного метода для поиска наилучшего оптимального решение.
В диссертационной работе рассматривается булева двухкритериальная задача о рюкзаке. Применительно к практическим задачам, указанным ранее, ее можно классифицировать как информационную модель. Действительно, два входных вектора R=(r,) и L=(1,), /=1,2,...,z, которые на практике несут определенную информацию о моделируемом явлении, преобразуются в выходной вектор у (оптимальное решение двухкритериальной задачи о рюкзаке). Преобразование задается как оптимизационная двухкритериальная задача о рюкзаке (система линейных критериев и ограничение).
Поиск оптимального решения дает возможность эффективно
расходовать ресурс при каждом практическом применении (например,
финансы, стройматериал, память информационного носителя). Таким
образом, разработка информационной модели, булевой
двухкритериальной задачи о рюкзаке, является актуальной.
Целью диссертационной работы является постановка двухкритериальной задачи из класса лексикографических многокритериальных задач (видоизменение задачи о рюкзаке) применительно к расходованию материальных и информационных ресурсов, разработка и исследование эффективного метода ее решения.
Для достижения цели диссертационной работы требуется решение следующих задач:
сформулировать постановку двухкритериальной задачи из класса лексикографических многокритериальных задач (видоизменение задачи о рюкзаке) применительно к расходованию материальных и информационных ресурсов;
разработать алгоритм решения поставленной задачи;
исследовать временную сложность предложенного алгоритма решения данной задачи в сравнении с известными методами решения задач рассматриваемого класса;
оценить эффективность разработанного алгоритма в практическом аспекте.
Методы исследования. В диссертационной работе применялись элементы теории вероятностей, математической статистики, теории графов, линейной алгебры, методы математического программирования.
Научная новизна. Научная новизна диссертационной работы заключается в следующем:
Разработан метод решения булевой двухкритериальной задачи о рюкзаке, основанный на частичном переборе допустимых решений путём расширения линейного пространства допустимых решений. Метод по построению отличается от известных методов класса многокритериальных лексикографических задач, достигает преимущества в эффективности и позволяет снизить временную сложность решения задачи о рюкзаке.
Сформулировано и обосновано положение о независимости решения двухкритериальной задачи о рюкзаке от перестановки числовых коэффициентов, определяемых при её постановке. Положение отличается от аналогов в данном классе задач и на практике позволяет оптимизировать расход материальных и информационных ресурсов.
Для решения двухкритериальной задачи о рюкзаке адаптированы метод свертывания в агрегированный критерий, выведены формулы расчёта числовых коэффициентов. Получено отличное от известных в данном классе задач формальное описание метода решения рассматриваемой задачи, что позволило представить программную реализацию решения.
На основе сравнения временной сложности предложенного метода, метода последовательных уступок, а также свертывания в агрегированный критерий показано, что предложенный метод решает двухкритериальную задачу о рюкзаке вдвое быстрее метода последовательных уступок и в пять раз быстрее свертывания в агрегированный критерий.
Достоверность результатов вытекает из их математического обоснования, подтверждается статистическими оценками, иллюстрируется работой комплекса программ.
Основные положения, выносимые на защиту.
Метод решения двухкритериальной задачи о рюкзаке, основанный на частичном переборе допустимых решений путём расширения линейного пространства допустимых решений.
Положение о независимости решения рассматриваемой двухкритериальной задачи от перестановки числовых коэффициентов, определяемых при её постановке.
Адаптированный метод свертывания в агрегированный критерий для решения двухкритериальной задачи о рюкзаке, формулы расчёта числовых коэффициентов.
Сравнительные оценки временной сложности предложенного метода, метода последовательных уступок и свертывания в агрегированный критерий, согласно которым предложенный метод решает рассматриваемую задачу вдвое быстрее первого и в пять раз быстрее второго.
Практическая ценность.
Программный продукт, разработанный на основе предложенного метода оптимизации, может найти применение на предприятиях, занимающихся грузоперевозками, его использование, примерно, на порядок повышает эффективность по сравнению с загрузкой предметов, отсортированных по весу.
Полученные в работе результаты использованы в ООО «МиР» (Ростов-на-Дону), приняты для загрузки автотранспорта при перевозке стройматериалов; в ЗАО ПКФ «Гефест ВПР» (Таганрог) для изготовления комплектующих при производстве металлоконструкций, что подтверждено соответствующими актами об использовании, приведенными в приложении 8 к диссертационной работе.
Апробация работы. Основные результаты диссертационной работы докладывались на:
Отраслевой научно-технической конференции "Актуальные проблемы развития железнодорожного транспорта и роль молодых ученых в их решении" (г. Ростов-на-Дону, 1998 г.);
Всероссийской научной конференции "Новые информационные технологии. Разработка и аспекты применения" (г. Таганрог, 2000 г.);
Международной научно-технической конференции "Математические методы в экономике" (г. Пенза, 2002 г.);
53 научно-технической конференции профессорско-преподавательского состава, аспирантов и сотрудников Технологического института Южного федерального университета в г. Таганроге (2008 г.). Основные результаты опубликованы в 7 печатных работах, из них 2 работы в изданиях, входящих в перечень ведущих научных журналов и изданий, выпускаемых в Российской Федерации, утверждённый ВАК. Объем и структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 96 наименований, и 8 приложений. Работа изложена на 119 стр., включает 85 стр. приложений, содержит 9 рисунков и 8 таблиц.
