next up previous contents
След: Транспортная задача Нзд: Примеры задач линейного программирования Пред: Примеры задач линейного программирования   Содержание

Задача о раскрое

Как утверждает математический фольклор, основы линейного программирования были заложены в 30-х годах молодым ленинградским математиком В.Л. Канторовичем при работе над социальным заказом -- минимизацией отходов авиационной фанеры. Отдавая должное истории, мы приводим эту задачу в качестве первого примера, тем более, что она и сейчас не потеряла своей актуальности.

Исходная проблема заключается в нахождении оптимального раскроя партии листов (фанеры, бумаги, металла ...) на заготовки заданных размеров: \( l_i,i=1,2,...,I \).

Предположим, что на предприятие материал поступает в виде рулонов стандартной длины \( l \geq \max_{i=1,2,...,I} l_i \), что являетя необходимым условием того, чтобы задача имела решение. Каждый способ (план) раскроя можно описать целочисленным вектором \( a = (a_1, a_2, \ldots, a_I) \), где \( a_i \) - количество заготовок \(i\)-го типа (то есть длины \( l_i \)).

В принципе существует лишь конечное число \(N\) допустимых векторов \(a\). Это число \(N\) представляет собой количество целочисленных точек \(a\), удовлетворяющих неравенству

\begin{displaymath}
\sum_{i=1}^I a_il_i\leq l,\end{displaymath} (2)

хотя, конечно, это число может быть достаточно велико. Перенумеруем эти планы раскроя (векторы): \( a^1, a^2, \ldots, a^N\).

Если \(n_j\) -- это количество листов, раскроенных по плану \(j\), то количество деталей \(i\)-го типа, произведенных по \(j\)-ому плану,равно \(a^i_j n_j \), а их общее количество, произведенное в соответствии с производственной программой \( n_1, n_2, \dots , n_N \), равно

\begin{displaymath}m_i = \sum_{j=1}^N a^i_j n_j.\end{displaymath}

Если результат работы предприятия определяется количеством \(t\) произведенных комплектов (изделий), то это количество должно удовлетворять неравенству

\begin{displaymath}t \leq m_i/d_i, i = 1,2, \dots, I, \end{displaymath}

где \(d_i\) -- норма расхода заготовок \(i\)-го типа на одно изделие.

Максимальное количество готовых изделий, получится тогда при решении задачи

\begin{displaymath}
\begin{array}{c}
\max\ t \\
d_i t \leq m_i,\\
i = 1,2, \dots, I,
\end{array}\end{displaymath} (3)

Подставляя в (3) выражение для \(m_i\), получаем задачу
\begin{displaymath}\begin{array}{c}
\max\ t \\
d_i t \leq \sum_{j=1}^N a^i_j n_j, , i = 1,2, \dots, I.
\end{array}\end{displaymath} (4)

При раскрое \(X\) листов должно выполнятся условие \(\sum_{j=1}^N n_j = X\), и разделив это равенство на \(X\), получим задачу
\begin{displaymath}\begin{array}{c}
\max\ t \\
d_i t \leq \sum_{j=1}^N a^i_j \xi_j, , i = 1,2, \dots, I\\
\sum_{j=1}^N \xi_j = 1.
\end{array}\end{displaymath} (5)

где \(\xi_j = n_j/X\). При больших \(X\) целочисленность \(n_j\) несущуственна и переменные \(\xi_j\) можно считать вещественными.

Разделив неравенства в последней формулировке на \(t> 0\) и введя новые переменные \(x_j = \xi_j /t \) получим итоговую формулировку задачи оптимального раскроя:

\begin{displaymath}
\begin{array}[t]{c}
\max\ t \\
d_i \leq \sum_{j=1}^N a^i_j ...
...m_{j=1}^N a^i_j x_j \geq d_i,\\
i = 1,2, \dots, I,
\end{array}\end{displaymath}

решение которой эквивалентно решению задачи

\begin{displaymath}
\begin{array}[t]{c}
\min \sum_{j=1}^N x_j\\
\sum_{j=1}^N a^i_j x_j \geq d_i,\\
i = 1,2, \dots, I.
\end{array}\end{displaymath}

Интересной особенностью этой задачи является потенциально очень большое количество переменных, имеющее в типичных случаях комбинаторный порядок роста. Хотя рост количества переменных можно сдержать, применяя те или иные правила отбора перспективных вариантов раскроя, тем не менее это может быть весьма значительное число. Следовательно, матрица ограничений этой задачи имеет очень ''вытянутый'' вид и применение алгоритмов, ориентированых на обращение к строкам матрицы становиться затруднительным.

Другой интересной особенностью матрицы ограничений является описание столбцов как элементов множества, удовлетворяющего определенным соотношениям -- в нашем случае условию целочисленности и ограничению (2). Это означает, что при необходимости извлечь тот или иной столбец это может быть сформулировано, как вспомогательная задача с соответствующим критерием отбора. Такие матоды получили название методов ''генерации столбцов''.


Evgeni A. Nurminski 2000-08-19