Генерация столбцов

Генерация столбцов или отложенная генерация столбцов — это эффективный подход к решению больших задач линейного программирования.

Общая идея метода заключается в том, что многие задачи линейного программирования слишком велики для явного выписывания всех переменных. Поскольку большинство переменных не будут входить в базис, а потому будут иметь нулевое значение в оптимальном решении, только подмножество переменных необходимо для решения задачи. Генерация столбцов поддерживает эту идею путём генерации только тех переменных, которые имеют потенциальную возможность улучшения целевой функции — то есть ищутся только переменные с отрицательной приведённой ценой (предполагаем без потери общности, что решается задача минимизации).

Задача распадается на две — основная задача и подзадача. Основная задача является исходной задачей с предположением, что рассматривается только подмножество переменных. Подзадача же — это новая задача, цель которой — поиск новых переменных. Целевой функцией подзадачи является приведённая цена для текущих двойственных переменных, а ограничения порождаются естественными ограничениями на переменные.

Процесс работает следующим образом. Решаем основную задачу, из решения получаем двойственные переменные для каждого ограничения исходной задачи. Эта информация используется в целевой функции подзадачи. Решаем подзадачу. Если целевая функция подзадачи будет отрицательной, переменная с отрицательной приведённой ценой найдена и эту переменную добавляем в основную задачу и производим очередное решение основной задачи. Новое оптимальное решение основной задачи даст новые двойственные переменные, и процесс повторяется, пока решения подзадачи дают отрицательные значения. Когда решение подзадачи даст положительное значение целевой функции, мы можем заключить, что оптимальное решение основной задачи найдено.

Во многих случаях такой подход позволяет решать большие задачи линейного программирования. Классическим примером применения метода генерации столбцов является задача раскроя. Одна из техник линейного программирования, использующая тот же подход — разложение Данцига — Вулфа. Кроме того, генерация столбцов используется во многих задачах, таких как график работ, составление маршрутов и задача о p-медиане с ограничениями.

Источник: Википедия