Труды КНЦ (Технические науки) 2/2022(13).

Методы целочисленного линейного программирования Приведем один из вариантов формализации задачи для ее решения методами целочисленного линейного программирования, ка к это предложено в [5]. Для каждого блока i создается набор переменны х X j е {0 ,1 }, где j е { 1 . 7 } . X j = 1 обозначает, что блок i добы т в год j . Для гарантии добычи блока только в один год вводится дополнительное ограничение ^ J - i Xij = 1. Вы года от добычи каждого блока i в определенный год задается явно, образуя множество кон кре тны х значений C j, где j е { 1 . 7 } . Целевая функция с учетом вышенаписанного представляется теперь ка к X Z ( X х C j). О граничения на объемы добычи принимаю т вид: Amin < YXj' < Amax^ где j = t, t е { 1 .7 } (Omint < YXij < Omax^ где j = t, Cj > 0, t е { 1 . 7}). О граничения же на порядок добычи в таком представлении разворачиваются во множество линейны х уравнений вида: 0 < (£Х=1Хрк —Xit ) < 1, для t е { 1 . 7 } , где p — индекс блока, которы й нуж но извлечь перед блоком i . В таком представлении задачи эффективно решаются линейными решателями, но для достаточно малых размерностей. Проблема такого представления заключается в том , что для кодирования ограничений на последовательность извлечения для каждой пары блоков строится 7 линейны х уравнений. Однако для корректно го описания техноло гических ограничений добычи каждом у блоку н уж но задать множество блоков, расположенных относительно рассматриваемого в определенной конф игурации (шаблон добычи). Так, например, для простейшего шаблона из 5 блоков на 5 лет планирования ограничение на порядок добычи породит в среднем 20 линейны х уравнений на каждый блок, что при размерности задачи в 5000 блоков, даст уже 100000 уравнений только для описания одной части задачи. С увеличением размерности задачи, количества лет планирования и сложности шаблона добычи только хранение порожденны х линейны х уравнений в памяти уже представляет некоторую трудность, не говоря уже об и х расчете. Авторами проводились расчеты задачи в таком представлении на тестовой машине с объемом оперативной памяти 32 ГБ с помощ ью свободно распространяемого программного обеспечения (M in iZ in c , Google OR tools). М аш и нны х ресурсов не хватало уже для расчета задачи размерностью 2000 блоков. С примером решения схожей задачи методами целочисленного линейного программирования в усовершенствованном представлении и с помощ ью коммерческого решателя (IBM -C p le x ) можно ознакомиться в [1 ], где на схожей по параметрам тестовой машине для размерности уже порядка 20000 блоков не было получено ни одного решения за 48 часов расчетов. Методы удовлетворения ограничений Общая постановка задачи достаточно ле гко преобразуется в задачу удовлетворения ограничений. Напомним , что для постановки задачи удовлетворения ограничений необходимо определить три множества [6]: множество переменных — это в нашем случае множество блоков B ; множество доменов переменных — доменами каждой переменной из B являются множества { 1 . 7 } и множество ограничений, которое также достаточно подробно описано в общей постановке задачи, но требует формализации средствами программирования в ограничениях. В отличие от предыдущего метода, где процесс решения задачи заключается в решении множества линейны х уравнений, в методе удовлетворения ограничений поиск решения представляет собой сокращение пространства поиска специализированными алгоритмами-распространителями. Данные алгоритмы жестко привязаны к кон кретным ограничениям и на основе анализа доменов участвующ их в соответствующих ограничениях переменных удаляют из этих доменов значения, которые точно не м о гут быть частью решения. Разные ограничения имеют разные по эффективности распространители. Кроме того , одни и те же зависимости часто можно описать разным набором ограничений. Таким образом, от выбора кон кре тны х ограничений для описания задачи существенным образом зависит эффективность ее решения. Труды Кольского научного центра РАН. Серия: Технические науки. 2022. Т. 13, № 2. С. 111-115. Transactions of the Kola Science Centre of RAS. Series: Engineering Sciences. 2022. Vol. 13, No. 2. P. 111-115. © Олейник Ю. А., Зуенко А. А., 2022 113