Оптимізація в задачах лінійного розкрою матеріалів

Abstract

В статті розглянута класична задача лінійного розкрою, яка є NP-складною. Для розв’язку даного класу задач пропонується метод точної квадратичної регуляризації (EQR), який є ефективним для розв’язання задач неперервної оптимізації великої розмірності. Проведені обчислювальні експерименти для задач лінійного розкрою засвідчили перевагу методу EQR над методом розгалужень та границь, як по часу так і по точності розв’язку. Приведені приклади це підтверджують.In the paper we considered the classic problem of linear cutting, which is NP-difficult. We solve this class of problems a new method of an Exact Quadratic Regularization (EQR). This method is effective for solving the problems of cutting of large dimension.