Постановка задачи об оптимальном раскрое материалов (о минимизации отходов)
Пусть некоторый полуфабрикат (например, листы фанеры) поступил на предприятие в виде 
различных партий, содержащих соответственно 
единиц полуфабриката одинакового для каждой партии размера. Из поступивших полуфабрикатов требуется изготовить возможно большее число комплектов деталей, в каждый из которых входит 
деталей первого вида, 
деталей второго вида, …, 
деталей 
вида. Пусть каждую единицу полуфабриката можно раскроить на детали различными способами, причем при раскрое единицы 
-й партии 
-м способом получается 
деталей 
-го вида.
Обозначим через 
число единиц из -й партии полуфабрикатов, которые намечено раскроить -м способом, так что из -й партии при -м способе раскроя будет получено 
деталей -го вида. Всего же по плану из всей -й партии деталей -го вида будет получено
а из всех партий их будет получено
как в каждый комплект готовой продукции должно входить 
деталей -го вида, то
деталей позволит их использовать
для составления
комплектов, и, таким образом, число полных комплектов, которое можно будет выпустить по данному плану 
, равно наименьшему из частных
Введением дополнительной переменной 
сведем рассматриваемую задачу к задаче максимизации 
при ограничениях
Не всегда эту задачу решают как целочисленную. Если значения переменных в полученном оптимальном решении задачи линейного программирования достаточно велики, то приближенное целочисленное решение получают из него путем округления до ближайших допустимых целых чисел.
Эта теория взята со страницы лекций по предмету «математическое программирование»:
Предмет математическое программирование
Возможно эти страницы вам будут полезны:
