Введение к работе
Актуальность темы. В связи с резко возросшей сложностью агробиологического моделирования и создания экономико-математической модели землепользования и возникла настоятельная потребность разработки алгоритмов нахождения множеств альтернатив в условиях многокритериальности.
Настоящее исследование обусловлено следующими
обстоятельствами. Известные экономико-математические модели
землепользования отражают лишь структуру посевных площадей.
Причем, они используют в качестве основных исходных данных
усредненные показатели урожайности. Эти данные и представляют
параметры экономической целевой функции (ЦФ). Математические
модели, которые содержали бы одновременно и экономические и
экологические ЦФ в их системной взаимосвязи к настоящему времени, к
сожалению, отсутствует. В настоящей работе восполняется этог пробел.
Предлагаемый подход базируется на идее строить математические
модели землепользования, используя более тонкие, более адекватные (по
сравнению со . средней урожайностью) величины: во первых,
урожайность каждой культуры, дифференцированную по всевозможным
предшественникам, и, во вторых, учитывать изменения (т.е. истощение
или, наоборот, улучшение) биоэкологического состояния почвы после
выращивания на ней конкретной культуры по конкретному
предшественнику. При этом проблема выбора наиболее рациональных
решений неизбежно приводит к необходимости учета многих
противоречивых, требований. В результате адекватные математические
постановки задач оказываются многокритериальными задачами. Наряду
с этим многие возникающие задачи являются многокритериальными
задачами большой размерности на графах Последнее обстоятельство исключает возможность разработки точных методов, которые гарантировали бы нахождение искомого решения за реальное время в производственны.х условиях.
Таким образом, актуальной является проблема создания для указанного класса задач быстрых (малотрудоемких) алгоритмов. которые применительно к выделенным классам дискретных многокритериальных задач оптимизации оказываются эффективными в типичном случае как по точности, гак и по трудоемкости
Следует отметить, что для лица, принимающего решение, существенно больший интерес представляет множество конкурирующих альтернатив (парето-оптимальных) решений по сравнению с одним решением, оптимальным по какому-либо критерию или свертке критериев. Иными словами, возникает проблема нахождения множеств альтернатив. Однако, к настоящему времени эта проблема исследована очень слабо. Приведенными выше обстоятельствами и обусловлен резко возросший теоретический и прикладной интерес к так называемым статистически эффективным методам решения многокритериальных задач на графах. Разработке л обоснованию этих методов и посвяшена диссертационная работа, Вместе с этим в работе оашсствлено обоснование вычислительной сложности рассмотренных задач, а также установлена их неразрешимость с помощью алгоритмов линейной свертки критериев. Разработан также точным полиномиальный алгоритм для одного полиномиально разрешимого класса.
Цель работы. Основной целью настоящей работы является: вывод точных формул вычисления максимальной мощности множества допустимых решений (МДР) задачи о совершенных паросочетаниях на многоцветных графах; определение соотношений между
подмножествами вершин различных цветов, при которых достигается
максимум мощности МДР; доказательство свойства полноты задач о
паросочетаниях на многоцветных графах в случае, когда векторная
целевая функция (ВЦФ) включает весовые критерии вида MJNSUM и
MAXSUM. и. как следствие, получение заключения о
труднорешаемости рассматриваний задачи; выделение полиномиально разрешимых классов векторных задач и построение статистически эффективных азгоритмов для общего случая; исследование проблемы разрешимости с помошью алгоритмов линейной свертки критериев.
Научная новизна: Впервые разработана агробиологическая
математическая модель многокритери&тьной задачи о совершенных
паросочетаниях. Доказано, что рассматриваемая задача обладает
свойством полноты в случае, когда ВЦФ состоит из критериев вида
MTNSUM; выведена точная формула вычисления максимальной
мощности полного множества альтернатив, откуда вытекает,
утверждение о труднорешаемости исследуемой векторной задачи;
построен и обоснован эффективный алгоритм решения 2-критериальной
задачи о совершенных паросочетаниях на многоцветных графах;
выделен класс труднорешаемых 2-критериальных задач о совершенных
паросочетаниях, для которых предложенные автором алгоритмы
являются статистически эффективными; построен алгоритм,
гарантирующий нахождение ПМА 2-критериальной задачи о совершенных паросочетаниях; доказана неразрешимость с помощью АЛС векторной задачи о паросочетаниях на многоцветных графах. '
Методы исследования: В работе использованы методы теории графов, теории вероятностей, комбинаторики и математического программирования.
і І
Практическая ценность: практическая ценность работы состоит в том, что полученные в работе результаты могут быть использованы при разработке системы поддержки принятия решений в процессе агробиологического математического моделирования задачи землепользования в условиях многокритериальности. Идеи доказательства статистической эффективности предложенных в диссертации алгоритмов могут быть применены в дальнейших исследованиях для построения и обоснования новых методов дискретной многокритериальной оптимизации.
Апробация работы. Материалы диссертации докладывались и обсуждались на Общенаучном математическом семинаре, I научно-практической конференции преподавателей и аспирантов КЧТИ (г.Черкесск, 1995), IV научно-методической конференции (г.Черкесск, 1995г.), на международном научном симпозиуме «Экономика и право-стратегия 3000» (г.Кисловодск, 1996г.), V научно-методической конференции «Новые технологии обучения: теория, опыт, проблемы, перспективы» (г.Черкесск, 1996г.), на Всероссийском симпозиуме «Математическое моделирование и компьютерные технологии» (Кисловодск, 1997), На международной конференции (Нальчик, 1996) на Всероссийской молодежной научной конференция «Гагаринские чтения» (Москва, 1997). на конференции «Математическое программирование и приложения» (Екатеринбург, 1997), на международном коллоквиуме КМ-97 (Веймер, 1997), в всероссийской научно-технической конференции с международным участием «Компьютерные технологии в инженерной н управленческой деятельности» (Таганрог, 1998).
В диссертацию вошли результаты, полученные мною как одной из исполнителей проекта X» 792 от . о конкурсе грантов Госкомитета РФ по фундаментальным исследованиям в области
і і
математики по теме «Исследование векторных задач на графах.
Разрешимость, сложность, алгоритмы» 1995- 1997гг.; проекта о
конкурсе грантов Госкомитета РФ по фундаментальным исследованиям в области математики по теме «Исследование векторных задач на графах. Разрешимость, сложность, алгоритмы» 1998-1999гт.
Публикации. Основные результаты диссертации опубликованы в шестнадцати работах.
Структура и объем работы. Диссертационная работа состоит из введения, трех глав, заключения и списка литературы, включающего 58 наименований. Работа изложена на 126 страницах.