Заключение задач целочисленного программирования способами веток и пределов и частичного перебора
Содержание
ВВЕДЕНИЕ 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 60x1 60x2 40x3 10x4 20x5 10x6 3x7
при ограничениях
3x1 5x2 4x3 1x4 4x5 3x6 1x7 < 10,
все xj = 0,1.
Следует направить интерес на 2 главных различия меж способом веток и пределов и способом частичного перебора.
Во-1-х, в аддитивном методе требуется исполнение лишь операций склады и вычитания. Отбор на шагах 1 и 4 может базироваться на инфы, приобретенной из рационального решения задачки линейного программирования(3. 1),(3. 2)и ограничении 0 < xj < 1.
Во-2-х, любое частичное заключение удовлетворяет условиям целочисленности, однако в различие от способа, основанного на решении задач линейного программирования, может не воздавать линейным неравенствам(3. 2). Используя успешные критерии выбора на шагах 1 и 4, с поддержкой аддитивного метода разрешено отыскать возможное сообразно всем ограничениям и недалёкое к хорошему заключение на начальной итерации.
Для реализации вышеизложенных способов целочисленного булевого программирования на практике были написаны две програмки на языке Turbo Pascal 7. 0. Контент програмки, реализующий метод способа веток и пределов, разрешено поглядеть в прибавлении А, а итоги решения задачки приведены в прибавлении Б. Контент програмки, релизующий метод частичного перебора располагаться в прибавлении В, а итоги решения задачки приведены в прибавлении Г.
Для удобства разбора приобретенных итогов при применении метода, основанного на способе веток и пределов, ход итераций представим графически в облике бревна.
Литература
1. Вагнер Г. , Базы изучения операций. Том 2. - М. : Мир, 1973. -486с.
2. Зайченко Ю. П. , Изучение операций. - К. : ВШ, 1979. - 387с.
3. Кофман А. , Анри-Лабордер А. , Способы и модели изучения. - М. Мир, 1977. -428с.