Сущность оптимального раскроя состоит в разработке таких технологически допустимых раскройных планов, при которых из стандартных единиц раскраиваемых ресурсов получается необходимый комплект заготовок требуемого размера, а критерий оптимальности заключается в сведении к минимуму либо общей величины отходов кроя, либо количества раскраиваемых единиц ресурсов.
Формулировка задачи оптимального раскроя зависит от формы раскраиваемого материала, который может быть длинномерным, листовым, рулонным и т.д. Сформулируем экономико-математическую модель задачи оптимального раскроя по одному измерению длинномерных материалов (прутков, труб, профильного проката и др.). Примем следующие обозначения:
L – длина исходного материала;
i – номер (индекс) вида требуемых заготовок, i = 1, 2 ... т;
li – длина заготовки i-го вида;
Аi – требуемое число заготовок i-го вида (не менее);
j – номер варианта раскроя, j = 1, 2 ... n;
aj – количество заготовок i-го вида при раскрое единицы исходного материала по j-му варианту;
сij – длина отхода по j-му варианту.
Пусть х1 – количество единиц исходного материала, раскраиваемых по i-му варианту. Целевая функция по критерию минимума отходов имеет вид:
По критерию минимума раскраиваемых единиц исходного материала уравнение может быть таким:
Это верно при соблюдении следующих условий:
Получилась задача линейного программирования, которую надо пополнить требованием целочисленности величины хj.
Заметим, что во многих случаях решения задач с обеими указанными целевыми функциями совпадают.
Наиболее трудоемкий этап в процессе построения модели рассматриваемой задачи заключается в определении всех возможных вариантов раскроя. Исходные соотношения для составления вариантов раскроя следующие:
Условие (46) означает, что длина отхода для любого варианта раскроя должна быть меньше, длины самой короткой заготовки (это является признаком полноценности варианта).
Задача о размещении складов. Она является одной из оптимизационных задач исследования операций и решается обычно методами нелинейного программирования. Надо минимизировать общую сумму транспортных и складских расходов при следующих ограничениях:
- с каждого предприятия должна быть отгружена вся продукция;
- не может быть превышена емкость ни единого склада;
- должны быть удовлетворены заявки всех потребителей.
В процессе решения задачи находится оптимальная по минимуму затрат трехчленная комбинация: предприятие – склад – потребитель. При некоторых условиях задача о размещении складов может сводиться к обычной транспортной задаче линейного программирования.
Задача о ранце (или о рюкзаке). Так называется задача о наилучшем выборе предметов из общего их количества, т.е. таким образом, чтобы суммарный вес (или габариты) отобранных предметов не превышал (не превышали) заданную величину, а их суммарная полезность или иная общая оценка (количество калорий, общая стоимость и т.д.) была максимальной. Задача о ранце решается как задача целочисленного линейного программирования, методами динамического программирования и другими. В частности, эта задача применяется при планировании оптимальной загрузки самолетов, кораблей, складов и др.
