Исследование алгоритмов решения целочисленных и частично целочисленных задач линейного программирования

Объект исследования – задачи целочисленного и частично целочисленного линейного программирования.

Предмет исследования – методы решения задач целочисленного и частично целочисленного линейного программирования.

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

Введение.......................................................................................................... 4

1 Обзор существующих методов решения задачи линейного программирования....................................................................................... 5

1.1 Общая характеристика задачи целочисленного и частично целочисленного линейного программирования..................................... 5

1.1.1 Математическая модель задачи целочисленного и частично целочисленного линейного программирования............................ 5

1.2 Методы решения задачи целочисленного и частично целочисленного линейного программирования.................................................................................. 6

1.2.1 Метод ветвей и границ................................................................... 7

1.2.2 Метод Гомори............................................................................... 15

2 Реализация алгоритмов для решения целочисленных и частично- целочисленных задач линейного программирования................................. 25

2.1 Структура реализованной программы.................................................. 25

2.2 Реализация метода ветвей и границ...................................................... 26

2.3 Пользовательский графический интерфейс приложения...................... 36

3 Сравнительный анализ реализаций............................................................. 42

3.1 Технические данные для сравнительного анализа................................ 42

3.2 Метод ветвей и границ.......................................................................... 42

3.3 Сравнение графиков однопоточной и параллельной реализации алгоритма ветвей и границ.................................................................... 45

3.4 Метод Гомори....................................................................................... 47

3.5 Сравнение графиков однопоточной и параллельной реализации алгоритма Гомори................................................................................. 50

3.6 Сравнение параллельной реализации алгоритма ветвей и границ и алгоритма Гомори.................................................................................................. 52

4 Моделирование данных............................................................................... 54

4.1 Описание математической модели....................................................... 54

4.2 Применение алгоритма ветвей и границ полученной модели.............. 65

4.3 Применение алгоритма Гомори полученной модели............................ 66

4.4 Сравнительный анализ алгоритмов...................................................... 67

Заключение..................................................................................................... 69

Список используемой литературы и используемых источников................... 70

Приложение А Листинг программы............................................................... 73

Приложение Б Листинг пользовательского интерфейса................................ 96