лекция_8

1. Целочисленные задачи линейного программирования

ЦЕЛОЧИСЛЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ

2.

Остановимся более подробно на рассмотрении метода Гомори
(отсечения) решения задачи целочисленного программирования
заключается в следующем:
1. Решаем задачу без условия целочисленности. Если решение
целочисленное, то получено решение. Если решение содержит нецелые
компоненты, то в задаче необходимо ввести дополнительные ограничения.
2. Выбираем уравнение для которого дробная часть свободного члена
наибольшая. Если таких уравнений несколько, то выбор такого уравнения не
имеет значения (произвольный).
Пусть это уравнение имеет вид: