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

В методах отсечения основу составляют 3 алгоритма Гомори(дискретный, смешанный, циклический). Все они базируются на использовании процедуры линейного программирования для последовательности задач, в которую по мере решения вводятся особые дополнительные ограничения.

В комбинаторных методах процедура линейного программирования почти не используется, а используется сокращения поиска возможных решений с помощью анализа исходного множества решений

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

Человеко-машинные методы требуют значительных вычислений.

Общая задача целочисленного линейного программирования

Рассмотрим задачу о размещении оборудования: есть n предметов, каждый из которых обладает определенный коэффициентов полезности(стоимость, калорийность и т.д.). Общая полезность от размещенных предметов равна сумме полезностей отдельных предметов. Все n предметов не могут быть размешены в заданном объеме (ограничения по объему) и/или грузоподъемность тела меньше суммарного веса предметов(ограничения по массе)

Требуется при ограничениях по массе и объему обеспечить размещения предметов, при котором общая полезность размещенных предметов была бы максимальной

Введем обозначение:

Тогда формально задача ставится следующим образом: