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

Краткая выдержка из текста работы (Аннотация)

ПРАКТИЧЕСКАЯ ЧАСТЬ

Max 60x1 + 60x2 + 40x3 + 10x4 + 20x5 + 10x6 +3x7

при ограничениях

3x1 + 5x2 + 4x3 + 1x4 + 4x5 + 3x6 + 1x7  10,

все xj = 0,1.

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

Во-первых, в аддитивном алгоритме требуется выполнение только операций сложения и вычитания. Выбор на шагах 1 и 4 может основываться на информации, полученной из оптимального решения задачи линейного программирования (3.1), (3.2) и ограничении 0  xj  1.

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

Для реализации вышеизложенных методов целочисленного булевого программирования на практике были написаны две программы на языке Turbo Pascal 7.0. Текст программы, реализующий алгоритм метода ветвей и границ, можно посмотреть в приложении А, а результаты решения задачи приведены в приложении Б. Текст программы, релизующий алгоритм частичного перебора находится в приложении В, а результаты решения задачи приведены в приложении Г.

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

Содержание работы

ВВЕДЕНИЕ 5

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 6

1 Модели целочисленного программирования 6

1.2 Примеры задач целочисленного программирования 7

2 Метод ветвей и границ 8

2.1 Алгоритм метода ветвей и границ 9

3 Метод частичного (неявного) перебора 11

3.1 Алгоритм метода частичного перебора 14

ПРАКТИЧЕСКАЯ ЧАСТЬ 16

ЗАКЛЮЧЕНИЕ 18

СПИСОК ЛИТЕРАТУРЫ 19

ПРИЛОЖЕНИЕ А 20

ПРИЛОЖЕНИЕ Б 26

ПРИЛОЖЕНИЕ В 29

ПРИЛОЖЕНИЕ Г 35

Использованная литература

1. Вагнер Г., Основы исследования операций. Том 2. - М.: Мир, 1973.-486с.
2. Зайченко Ю. П., Исследование операций. - К.: ВШ, 1979. - 387с.
3. Кофман А., Анри-Лабордер А., Методы и модели исследования. - М. Мир, 1977.-428с.

Другие похожие работы

• Контрольная - Лабораторная работа по курсу МС, СМО с ожиданием
• Контрольная - 5 задач по высшей математике
• Курсовая - Квадратичная аппроксимация функции Лагранжа
• Учебник - Современные информационные технологии. Проекционно-сеточные методы решения уравнений математической физики
• Курсовая - определенный интеграл
• Контрольная - Вычислительная математика
• Контрольная - 10 задач по курсу высшая математика
• Курсовая - Модели целочисленного булевого программирования. Алгоритм последовательного анализа вариантов решения
• Контрольная - 5 задач по высшей математике
• Контрольная - Контрольная по численным методам