ВВЕДЕНИЕ
Глава 1 ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДА ГОМОРИ
1.1Методы линейного программирования
1.2Целочисленное программирование
1.2.2Условие целочисленности многогранных множеств
1.3Метод отсекающих плоскостей Гомори
1.4Эффективность отсечения метода Гомори
Глава 2 ПЕРВЫЙ АЛГОРИТМ ГОМОРИ
2.1Описание первого алгоритма Гомори
2.2Численная реализация первого алгоритма Гомори
Глава 3 ВТОРОЙ АЛГОРИТМ ГОМОРИ
3.1Описание второго алгоритма Гомори
3.2Численная реализация второго алгоритма Гомори
3.3Сравнительный анализ первого и второго алгоритмов Гомори
3.3.1Сравнение характеристик первого и второго алгоритмов Гомори
3.3.2Программная реализация первого и второго алгоритмов Гомори
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ А
Целочисленное программирование широко применяется для решения задач в таких областях человеческой деятельности, как производственное планирование, составление расписаний, сети передачи данных и сотовая связь и других, т.е. там, где приходится оперировать штучными физическими или логическими величинами (0 или 1).
Следует отметить, что в отличие от задач линейного программирования, задачи целочисленного программирования очень сложны для решения. Фактически, для их решения не известен эффективный общий алгоритм [18].
Вместе с тем, для некоторых задач известен ряд алгоритмов, позволяющих решить задачу целочисленного программирования с высокой точностью. Одним из таких алгоритмов, анализ и реализация которых представляют научно-практический интерес, является алгоритм Гомори. Этим определяется актуальность бакалаврской работы.
Объект исследования бакалаврской работы - целочисленное линейное программирование.
Предмет исследования бакалаврской работы - алгоритм Гомори.
Цель бакалаврской работы - анализ и реализация алгоритма Гомори.
Для достижения поставленной цели необходимо решить следующие задачи:
-проанализировать теоретические основы метода Гомори;
-осуществить реализацию первого алгоритма метода Гомори;
-осуществить реализацию второго алгоритма метода Гомори
-произвести сравнительный анализ алгоритмов метода Гомори;
-выбрать средство программной реализации алгоритмов Гомори;
Представленная бакалаврская работа состоит из введения, трех глав, заключения, приложения и списка литературы.
Во введение обозначается тема работы и ее актуальность, описывается объект и предмет исследования, цели и задачи, которые необходимо решить в данной работе.
В первой главе представлены теоретические основы.
Вторая глава посвящена первому алгоритму Гомори и его реализации.
В третьей главе рассматривается второй алгоритм Гомори и его реализация и произведено сравнение с первым алгоритмом Гомори .
В заключении представлены результаты выполнения бакалаврской работы.
В приложении приведен кода программной реализации алгоритма Гомори.
Структура бакалаврской работы: страниц 54 с приложением, рисунков 8, таблиц 21, источников 26.
Представленная бакалаврская работа посвящена актуальной проблеме анализа и реализации алгоритма Гомори.
В ходе выполнения бакалаврской работы достигнуты следующие результаты:
1)Проанализированы теоретические основы метода Гомори и описан метод отсечений для решения задач ЦЛП, положенный в основу алгоритмов Гомори.
2)Приведен анализ эффективности отсечения Гомори.
3)Даны описание и анализ первого и второго алгоритмов Гомори.
4)Представлены подходы к численной реализации первого и второго алгоритмов Гомори.
5)Произведено сравнение основных характеристик первого и второго алгоритмов Гомори.
6)На основе технологии Electron и бесплатно распространяемого веб - сервиса решения задач ЛП разработана программа реализации первого и второго алгоритмов Гомори.
7)Выполнено тестовое решение задачи ЛП на разработанной программе.
Результаты бакалаврской работы могут быть рекомендованы для решения задач ЦЛП, связанных с применением алгоритмов Гомори.
