• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
ФИО студента
Название работы
Руководитель
Факультет
Программа
Оценка
Год защиты
Малеева Евгения Витальевна
Удаление неравенств в динамическом методе двойного описания
2019
Общеизвестно, что каждый полиэдр в многомерном пространстве может быть представлен любым из двух эквивалентных способов:

как множество решений некоторой системы линейных неравенств (так называемое фасетное описание) и

как сумма выпуклой и конической оболочек некоторых систем векторов (вершинное описание).

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

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

Также заметим, что начальный набор ограничений может быть уточнён, например, новые ограничения могут как удаляться из описания, так и добавляться в него. Проблема добавления ограничений на данный момент изучена более глубоко, чем эквивалентная ей проблема устранения неравенств.

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

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

Задачи исследования:

- изучение метода двойного описания

- изучение инкрементного метода двойного описания

- подготовка к реализации удаления неравенств в методе двойного описания

-реализация, численный эксперимент, сравнение с существующими алгоритмами

Выпускные квалификационные работы (ВКР) в НИУ ВШЭ выполняют все студенты в соответствии с университетским Положением и Правилами, определенными каждой образовательной программой.

Аннотации всех ВКР в обязательном порядке публикуются в свободном доступе на корпоративном портале НИУ ВШЭ.

Полный текст ВКР размещается в свободном доступе на портале НИУ ВШЭ только при наличии согласия студента – автора (правообладателя) работы либо, в случае выполнения работы коллективом студентов, при наличии согласия всех соавторов (правообладателей) работы. ВКР после размещения на портале НИУ ВШЭ приобретает статус электронной публикации.

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

В случае использования ВКР, в том числе путем цитирования, указание имени автора и источника заимствования обязательно.

Расширенный поиск ВКР