Эта публикация цитируется в
2 статьях
Нахождение примера задачи линейного раскроя с минимальными размерами, для которого нарушается оптимальность при округлении вверх
А. В. Рипатти,
В. М. Картак Уфимский государственный авиационный технический университет, ул. Карла Маркса, 12, 450008 Уфа, Россия
Аннотация:
Рассматривается известная одномерная задача раскроя с целью найти целочисленные примеры с минимальным размером материала
$L$, для которых не выполняется свойство округления вверх. Разрывом целочисленности называется разница между точным решением примера задачи раскроя и решением её линейной релаксации, и пример задачи раскроя обладает свойством округления вверх, если его разрыв целочисленности меньше
$1$. Предлагается новый метод поиска всех примеров с максимальным разрывом целочисленности для фиксированных значений
$L$, длин заготовок и оптимального целочисленного решения. Данный метод позволяет вычислительно доказать, что все примеры с
$L \le 15$ обладают свойством округления вверх. Также приведены несколько примеров c
$L=16$, не обладающих таким свойством, что даёт улучшение ранее известного результата
$L=18$. Табл. 2, библиогр. 14.
Ключевые слова:
задача раскроя, свойство округления вверх, разрыв целочисленности.
УДК:
519.85 Статья поступила: 27.06.2019
Переработанный вариант: 18.09.2019
Принята к публикации: 27.11.2019
DOI:
10.33048/daio.2020.27.665