Содержание
ВВЕДЕНИЕ 5
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 6
1 Модели целочисленного программирования 6
1.2 Примеры задач целочисленного программирования 7
2 Метод ветвей и границ 8
2.1 Алгоритм метода ветвей и границ 9
3 Метод частичного (неявного) перебора 11
3.1 Алгоритм метода частичного перебора 14
ПРАКТИЧЕСКАЯ ЧАСТЬ 16
ЗАКЛЮЧЕНИЕ 18
СПИСОК ЛИТЕРАТУРЫ 19
ПРИЛОЖЕНИЕ А 20
ПРИЛОЖЕНИЕ Б 26
ПРИЛОЖЕНИЕ В 29
ПРИЛОЖЕНИЕ Г 35
Выдержка из текста
ПРАКТИЧЕСКАЯ ЧАСТЬ
Max 60×1 + 60×2 + 40×3 + 10×4 + 20×5 + 10×6 +3×7
при ограничениях
3×1 + 5×2 + 4×3 + 1×4 + 4×5 + 3×6 + 1×7 10,
все xj = 0,1.
Следует обратить внимание на два основных различия между методом ветвей и границ и методом частичного перебора.
Во-первых, в аддитивном алгоритме требуется выполнение только операций сложения и вычитания. Выбор на шагах 1 и 4 может основываться на информации, полученной из оптимального решения задачи линейного программирования (3.1), (3.2) и ограничении 0 xj 1.
Во-вторых, каждое частичное решение удовлетворяет условиям целочисленности, но в отличие от метода, основанного на решении задач линейного программирования, может не удовлетворять линейным неравенствам (3.2). Применяя удачные правила выбора на шагах 1 и 4, с помощью аддитивного алгоритма можно найти допустимое по всем ограничениям и близкое к оптимальному решение на начальной итерации.
Для реализации вышеизложенных методов целочисленного булевого программирования на практике были написаны две программы на языке Turbo Pascal 7.0. Текст программы, реализующий алгоритм метода ветвей и границ, можно посмотреть в приложении А, а результаты решения задачи приведены в приложении Б. Текст программы, релизующий алгоритм частичного перебора находится в приложении В, а результаты решения задачи приведены в приложении Г.
Для удобства анализа полученных результатов при использовании алгоритма, основанного на методе ветвей и границ, ход итераций представим графически в виде дерева.
Список использованной литературы
1. Вагнер Г., Основы исследования операций. Том 2. — М.: Мир, 1973.-486с.
2. Зайченко Ю. П., Исследование операций. — К.: ВШ, 1979. — 387с.
3. Кофман А., Анри-Лабордер А., Методы и модели исследования. — М. Мир, 1977.-428с.
С этим материалом также изучают
Содержаниематематика: исследование операций в экономике, АТИСО№1Используя графический метод, найти решение следующей задачи линейного программирования(№ задач 5)№3 (данные к задаче -56)Определить набор товаров потребителя (х1, х2), ...
... геометрии, алгебры и математического анализа. Тенденция использованию при решении геометрических задач только геометрических методов препятствует приложениям алгебры и анализа в самой математике. Целью данной ...
... для различных наборов активных ограничений. Найти решение рассматриваемой задачи нелинейного программирования. Выписать функцию Лагранжа и условия Куна ... точках касания линии уровня целевой функции с границами допустимой области. Найти точки, в которых ...
... методах решения творческих задач: Синектике, Мозговом Штурме, Методе Фокальных Объектов, Морфологическом Анализе. Они основаны на принципе активизации выдвижения и перебора ... изд-во, 1964; 4.Альтшуллеp Г.С. АЛГОРИТМ ИЗОБРЕТЕHИЯ, 1-е изд.: М.: ...
... алгоритм, а для решения задач по геометрии часто нет общих алгоритмов. Поэтому координатный метод является одним из универсальных методов решения задач. Сформировать умения применять данный метод к решению геометрических задач ... и программирование» ...
... 18 22 Выдержка из текста Задание 1 Решить задачу целочисленного программирования методом Гомори: Решение Это задача целочисленного программирования. Ее решение методом отсечений распадается на несколько этапов. Первоначально необходимо ...
... задач к алгоритму дает координатный метод. Поэтому координатный метод является одним из универсальных методов решения задач. Сформировать умения применять данный метод к решению геометрических задач ... Шарыгин // Математика - Приложение к газ. «1 ...
... решения алгебраических задач, как правило, есть готовый алгоритм, а для решения задач по геометрии часто нет общих алгоритмов. Сформировать умения применять данный метод к решению геометрических задач ... полного) общего образования. Приложение к приказу ...
... готовый алгоритм, а для решения задач по геометрии часто нет общих алгоритмов. Поэтому координатный метод является одним из универсальных методов решения задач. Сформировать умения применять данный метод к решению геометрических задач ...
... для решения алгебраических задач, как правило, есть готовый алгоритм, а для решения задач по геометрии часто нет общих алгоритмов. Сформировать умения применять данный метод к решению геометрических задач можно ...
