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

На правах рукописи

Лилаи/-

ЗАМКОВА Любовь Ивановна

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МЕТОДА РЕШЕНИЯ ДВУХКРИТЕРИАЛЬНОЙ ЗАДАЧИ О РЮКЗАКЕ ПРИМЕНИТЕЛЬНО К РАСПРЕДЕЛЕНИЮ ИНФОРМАЦИОННЫХ И МАТЕРИАЛЬНЫХ РЕСУРСОВ

Специальность: 05.13.17 «Теоретические основы информатики»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 в ПРИ

Таганрог -2010

004617455

Работа выполнена в Технологическом институте Федерального государственного образовательного учреждения высшего профессионального образования «Южный федеральный университет»

Научный руководитель: доктор технических наук, профессор

Чефранов Александр Георгиевич

Официальные оппоненты: доктор технических наук, профессор

Ромм Яков Евсеевич.

доктор технических наук, профессор Першин Иван Митрофанович.

Ведущая организация: Федеральное государственное унитарное предприятие «Таганрогский научно-исследовательский институт связи»

Защита состоится в 2010 г. на заседании

специализированного совета Д212.208.21 по защите диссертаций при Технологическом институте Федерального государственного образовательного учреждения высшего профессионального образования «Южного федерального университета» (аудитория Д-406) по адресу:

пер. Некрасовский, 44, ГСП-17А, г. Таганрог, Ростовская область, 347928

С диссертацией можно ознакомится в библиотеке Технологического института Федерального государственного образовательного учреждения высшего профессионального образования «Южный федеральный университет»

Автореферат разослан «

»Ия&ЬрО. 2010 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор ' "V Н.И. Чернов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

В настоящее время существует два основных подхода к решению этого класса задач: ь

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

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

Первый способ предполагает разбиение многокритериальной задачи на последовательность взаимосвязанных однокритериальных задач и их решение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- оценить эффективность разработанного алгоритма в практическом аспекте.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

В первой главе "Двухкритериальная задача о рюкзаке и методы многокритериальной оптимизации" формулируется постановка булевой двухкритериальной задачи о рюкзаке:

z

L - Z I - - )>j -> шах i = 1

z

R= H r-min (max)

« = 1 (1)

1 rryt<D

i = 1

у. e {o,l} / = 1,2.....z

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

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

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

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

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

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

/

Ъ 1П • У о тах < р=1 Р Р

Я(у)=кг -у (2)

г р=1 У Р

/ = 2,3,...,г у е {0,1} р = 1,2,...,/. Множество С/ всегда содержит два вектора (0) и (1).

Для задачи размерности строится множество допустимых решений С,. Элементы С, упорядочиваются по возрастанию целевой функции. Множество С„ 1=2,3,...,г формируется на основе множества С,.;.

Для каждого вектора У¿¡.\ - •У2--у{-\ )> где С,./|,

проверяются последующие условия. Если |С,|=0, то вектор

* ( } ] ] \ У - 1У1 -У 2'У¡-1'^) помещается на первое место в С,. Если в С, нет

векторов, дающих равное или большее значение целевой функции чем

У]М = (х/'^г— ^М )' т0 вект°Р У = (У/'У2'-'У/-1'0) помещается на последнее место в С/.

Если в С, есть вектор уj] ¡, где у7=1,2,...,[С,|, со значением целевой

функции, равным значению целевой функции от вектора уу, то

анализируется условие j ¡~\)< ^¡{у д При истинности этого

* ( / 7 У \ условия вектор у = \У\ •У2' - 'У1-1'®) считается доминирующем над

вектором уд I и помещается в С, на его место, а вектор у^ / отсекается. При ложном значении множество С, не изменяется.

Если в С, есть вектор у ^ ¡, дающий большее значение целевой функции

* ( j j j \ чем yji.\, то у = y^j ,У2 >••• •J'z-i'Oy заносится перед таким вектором.

( \ ** ( j j j \

Если R\yj J + гi <, D , то вектор у ~\У\ ^2 ""'-^/-l / заносится

* #*

в С, на последнее место. Вектора у и у являются потомками размерности / вектора у j ¿.j.

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

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

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

В процессе доказательства того, что на одной перестановке коэффициентов задачи (1) МДО приводит к оптимальному решению у*, формулируется утверждение 1 и утверждение 2.

УТВЕРЖДЕНИЕ 1. Решение, отбрасываемое по превышению £) в процессе вычисления методом двойной оптимизации, не может привести к оптимальному решению задачи (1).

УТВЕРЖДЕНИЕ 2. Отсечение вектора по условию доминирования не приводит к потере оптимального решения задачи (1).

Далее представим идею доказательства утверждения 1. Если

решение является недопустимым (то есть значение функции Л

превышает й), то оно исключается из множества перебираемых решений. По построению множеств С„ /=2,3,(решений-векторов размерности ;)

потомок размерности /+1 недопустимого решения у-{ может иметь

значение функции Я равное или большее, чем вектор его породивший. Таким образом, значение функции Я от потомка тем более превышает Д то есть этот потомок является недопустимым решением. Это справедливо для всех потомков размерности /+1, 1+2, ..., г. Таким образом, все потомки

У1 являются недопустимыми решениями.

Представим идею доказательства утверждения 2. Рассмотрим два

произвольных вектора у'^ и у"^, для которых выполняется условие

доминирования {у\) = Ь^ ) и ) < Щ {у\). Дерево в всех

потомков вектора у£ будем называть идентичным дереву V всех

потомков вектора у. На дереве V, вершины которого участвуют в

переборе, выделяется подграф: вершина уд. и два её потомка (уд.;()) и

(У'к »0 • Рассматриваются ситуации включения или исключения из

перебора векторов и (у 'к >0 • Обосновывается, что

соответствующие потомки (у\;о) и ;1) на О, не будут являться

доминирующими векторами. Эти рассуждения применяем к каждой вершине-вектору размерности к+1, к+2, ..., 2-1 на дереве V. То есть отсечение вектора по условию доминирования не приводит к потере оптимального решения.

Далее в этой главе была сформулирована гипотеза для обоснования оптимальности МДО.

ГИПОТЕЗА. Предполагается, что значение критериев от вектора-решения задачи (1), определяемого методом МДО, не зависит от перестановки коэффициентов в критериях.

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

В третьей главе "Сравнительный анализ метода двойной оптимизации с методом последовательных уступок и методом свертывания в агрегированный критерий" разрабатываются алгоритмические реализации метода последовательных уступок (МПУ) и метода свертывания в агрегированный критерий (МСАК). На основании этих алгоритмов, заложенных в программы, проводится сравнительный анализ по времени решения задач вышеуказанных методов. Для 50 индивидуальных задач вида коэффициенты которых генерировались случайным образом, производились опыты. Опыт - это запуск для одной задачи программ на основании МДО, МПУ, МСАК и снятие показаний времени решения каждым методом. Для серии из 50 опытов рассчитывались оценки математического ожидания и среднеквадратичного отклонения, которые приведены в табл.1.

Табл. 1

МДО МСАК МПУ

М*, секунды 0,109980 0,500080 0,239720

а,секунды 0,006198 0,079317 0,014193

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

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

решаемых на практике. Рассматривались задачи, для которых 0=2000, 2500, 3000 и 2=20,40,60,80. Результаты приведены на графиках рис.1. Согласно графикам рост размерности задач приводит к росту времени их решения методом МДО. Среднее время решения задач на заданном диапазоне является приемлемым, при росте размерности в четыре раза среднее время решения увеличилось в шесть раз.

— ■ 0=2000 -—-[>2500 ■ — -[>3000

Рис.1

В этой главе проведена адаптация МСАК для решения задачи (1). Она заключалась в следующем: для поиска весов линейного функционала необходимо решить задачу (3)

гшп

Задача (3) сводится к решению задач вида (4):

шах

д

> > 1,

О

(4)

2

¿Уф -оптимальное значение целевой функции задачи

тах к{у).

Пусть у —максимальное решение однокритериальной задачи о рюкзаке при ограничении на вес <1,. Задача с ограничением на вес й имеет самую большую разность между максимальным и минимальным значением целевой функции Ь (минимальное значение равно 0). Уменьшая вес рюкзака, и решая полученную задачу, мы находим ближайший максимум к максимуму задачи с предыдущим значением веса. Разность между ближайшим максимумом и минимальным нулевым значением целевой функции будет меньше аналогичной разности для задачи с предыдущим весом. Продолжая подобные рассуждения, мы находим самый ближайший максимум к минимуму. Разность между ними и будет решением задачи (4). Таким образом, задача, описанная формулой (4), сводится к решению однокритериальных задач о рюкзаке вида (5):

тах I (у)

Я (у) £ 1

тах I (у). « (>-) < а1

(5)

й. £ £/. > 1, Ы.

о

2

где г/0 -оптимальное значение целевой функции задачи

тах .

тах

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

Э = ср

1Э ^аналога

где 1э интегральный экономический показатель, который определяется по формуле (7):

1Э =а1 ■ Ц + а2 • Ь2 , (7)

где Ьь Ъ2 — значения первого и второго параметров соответственно; аь а2 — весовые коэффициенты первого и второго параметров соответственно. Значения параметров аналога и разработки представляют в относительных единицах, то есть всем значениям параметров аналога присваивается значение равное единице, а значениям разработки — соответствующее численное улучшение (увеличение) параметра в разах (значение больше единицы) либо соответствующее численное ухудшение (уменьшение) параметра в разах (значение меньше единицы, но больше нуля). Численное значение весовых коэффициентов должно лежать в интервале от 0 до 1, а их сумма — равняться единице. Присвоение численного значения весовым коэффициентам осуществляется с позиции их значимости. В этой главе рассматривается применение двухкритериальной задачи о рюкзаке, в постановке которой коэффициенты первого критерия полагаются равными соответствующим коэффициентам ограничения, а коэффициенты второго критерия равны единицам. Эта двухкритериальная задача о рюкзаке является моделью оптимального сохранения файлов на носитель информации и оптимального раскроя материала. В первом случае в качестве главного критерия используется общий объем сохраняемых файлов, а вторым критерием является их количество. Во втором случае главным критерием является суммарная

(разработки)

длина листов-заказов, которые получаются в результате раскроя исходного листа, а второй критерий определяется количеством разрезов исходного листа. Для оптимального сохранения файлов и оптимального раскроя материала рассчитана сравнительная эффективность по маркетинговому подходу. Оптимальное сохранение файлов в 14 раз, а оптимальный раскрой материала в 10 раз эффективнее способа, используемого на практике. Для решения индивидуальных постановок каждой практической задачи приводится описание кодов программ, которые организуют обработку исходной и результирующей информации этих практических задач. Для практических задач рассчитана средняя сравнительная экономическая эффективность согласно маркетинговому подходу. Решение практических задач оптимально и по среднему значению в 11 раз эффективнее традиционного порядка выбора объектов (деталей, листов, файлов, грузов). Результаты расчётов приведены на рис.2.

Т

Рис.2

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Замкова Л. И. Метод решения задачи максимизации дохода, сведенной к задаче о рюкзаке// Конф. Актуальные проблемы развития железнодорожного транспорта и роль молодых ученых в их решении. -1998.-С. 166-167.

2. Замкова Л.И. Разработка программной системы эффективной оплаты счетов//Известия ТРТУ. --Таганрог,2005.-№6.-С.128-134.

3. Замкова Л.И., ЧгфрановА.Г. Алгоритм принятия решения об оплате счетов на основе решения задачи о ранце// конф. Новые информационные технологии. Разработка и аспекты применения. -Таганрог, 2000. - С. 40-41.

4. Замкова Л.И. Программная система принятия решения об эффективной оплате счетов// Международная научно-техническая конференция Математические методы в экономике. - Пенза, 2002. — ■ С.135-В7.

5. Замкова Л.И. Построение двухкритериальной задачи о рюкзаке, математической модели оплаты счетов, и метод её решения// 53 научно-техническая конференция профессорско-преподавательского состава, аспирантов и сотрудников Технологического института Южного федерального университета в г. Таганроге/ Известия ЮФУ,— Таганрог,-2008.-№1.-С.142.

6. Замкова Л.И. Булева двухкритериальная задача о рюкзаке// Известия ЮФУ. Технические науки - Таганрог, 2009.

- №4. - С.201-204.

7. Замкова Л.И. Сравнительный анализ двухэтапного алгоритма с методом последовательных уступок// Известия ТРТУ. - Таганрог, 2006. - №10. - С.30-32.

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

Соискатель

Л.И. Замкова

Типография Технологического института Федерального государственного образовательного учреждения высшего профессионального образования «Южный федеральный университет», заказ № .тираж экз. 2010 г.

Тип.ТТИ ЮФУ Заказ тир./£><2экз.

ВВЕДЕНИЕ.

ГЛАВА 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]. В формулировке задачи одного станка в качестве целевой- функции используется' время обработки деталей. Поиском приложений задачи Джонсона (задачи о станках) продолжают заниматься в настоящее время [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 опытов решения* двухкритериальных задач, коэффициенты которых генерировались случайным образом. По результатам опытов рассчитывались оценки математического ожидания и среднеквадратичного отклонения. Так как разброс для всех методов незначительный

МДО = °'006198 секУ»Ды, а\шУ = °>°14193 секунды, &*мсАК = °>079317 секунды, то сравнение проводилось по оценкам математического ожидания

Н* >Ц Н*

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

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

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

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

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

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

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

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

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

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

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

1. Илчева И. Многокритериальная модель выбора наиболее эффективной стратегии развития водохозяйственной системы и оценки, воздействия на» окружающую среду// Техническая миссия. 1995. - №2. - С. 49-57.

2. Ъ2.Колесников A.A., Гелъфгат А.Г. Проектирование многокритериальных систем управления промышленными объектами. Москва: Энергоатомиздат, 1993.-304 с.

3. ЗЗ.Гергель В.П., Сысоев A.B. Программная система для исследования методов решения многокритериальных задач// XII международная конференция

4. Сбоева Ю.В. Многокритериальная оптимизация блочно-модульных химико-технологических систем (на примере производства азокрасителей):, канд. Дис. -РХТУ, 1995.-139 с.

5. Ларичев О.И. Наука и искусство принятия решений. -Москва: Наука, 1979.- 200 с.

6. Брахман Т.Р. Многокритериальное^ и выбор альтернативы в технике.- Москва: Радио и-связь, 1984. 288 с.

7. Fletcher R. Practical Methods of Optimization// Vol. 1, Unconstrained Optimization, and Vol. 2, Constrained Optimization, John Wiley and Sons.- 1980.-p. 10-12.

8. Казаков А.Я. Модифицированные модели Джейнса-Каммингса и квантоваяверсия задачи о рюкзаке// ЖЭТФ. 2003. - Т. 124. - С. 1264-1270. 55Заславский A.A. Комбинированный- метод решения задач о рюкзаке//

9. Яковлева Т.В., Кузнецова A.A. Об одном подходе к решению задачи о рюкзаке алгоритмом с построением оценок// Всероссийская конференция Проблемы оптимизации и экономические приложения. Тезисы доклада.- Омск, 2003.-С. 15-16;

10. Юдин Д.Б., Голъштейн Е.Г. Задачи и методы линейного программирования.- Москва: Советское радио, 1964. 763 с.

11. Кузнецов A.B. и др. Руководство к решению задач по математическому программированию. Минск: Высшая школа, 200 Г. - 279 с.

12. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. Москва: Мир, 1985. - С. 446-450.61 .Данциг Дж. Линейное программирование его обобщения и приложения.- Москва: Прогресс, 1966. С. 490-491.

13. Беллман Р. Динамическое программирование. Москва: Издательство иностранной литературы, 1960. -400 с.

14. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления. Москва: Наука, 1969. - 118 с.

15. Васильев Ф.П. Методы оптимизации. Москва: Факториал Пресс, 2002.- С. 462-472.

16. Мухачева Э.А., Рубинштейн-Г.Ш. Математическое программирование.- Новосибирск: Наука, 1987. С. 187-190.вв.Белова Е.С. и др. Оптимальное управление. Москва: МАИ, 1993. -С. 18-29.

17. Зайченко Ю.П. Исследование операций. — Киев: Высшая школа, 1975.- 204 с.

18. Реклейтис и др. Оптимизация в технике: Учебное пособие. Москва: Мир,1986.-Т.1.-320 с. в9.Тилл Ф. и др. Практическая оптимизация. Москва: Мир,1985. - 501 с. 70.Сухарев А.Г. и др. Курс методов оптимизации. - Москва: Наука, 1986.- 328 с.

19. Моисеев H.H. и др. Методы оптимизации. Москва: Наука, 1978. - 351 с. 72.Банди Б. Методы оптимизации. Вводный курс. - Москва: Радио и связь,1988. 127 с.1Ъ.Гольштейн Е.Г., Юдин Д.Б. Линейное программирование.- Москва: Физматгиз, 1966. С.50-51.

20. Галеев Э.М., Тихомиров В.М. Оптимизация: теория, примеры, задачи.- Эдиториал УРСС, 2000. С. 86-95.

21. S3.Замкова Л.И. Метод решения задачи максимизации дохода, сведенной к задаче о рюкзаке// Конф. Актуальные проблемы развития железнодорожного транспорта и роль молодых ученых в их решении. 1998. - С. 166-167.

22. Ы.Замкова Л.И. Разработка программной системы эффективной оплаты счетов// Известия ТРТУ. Таганрог, 2005. - №6. - С. 128-134.

23. Замкова Л.И. Программная система принятия* решения об эффективной оплате счетов// Международная научно-техническая« конференция Математические методы в экономике. Пенза, 2002. - С. 135-137.

24. Архангельский А.Я. Программирование в С++ Builder 5. Москва: БИНОМ, 2000. - 286 с.

25. Теплее М. Borland С++ Builder. Санкт-Петербург: - Питер, 1998. - 503 с.9б.Замкова Л.И. Булева двухкритериальная задача о рюкзаке// Известия ЮФУ. Технические науки. Таганрог, 2009. - №4. - С. 201-204.