Генерация столбцов или отложенная генерация столбцов - эффективный алгоритм для решения больших линейных программ .
Общая идея заключается в том, что многие линейные программы слишком велики, чтобы явно учитывать все переменные. Предпосылка состоит в том, что большинство переменных не являются базовыми и принимают нулевое значение в оптимальном решении. Из-за этого при решении проблемы теоретически необходимо учитывать только подмножество переменных. Генерация столбцов использует эту идею для генерации только тех переменных, которые могут улучшить целевую функцию, то есть для поиска переменных с отрицательной приведенной стоимостью ( без ограничения общности при условии, что проблема заключается в задаче минимизации).
Решаемая проблема разделена на две задачи: основная проблема и подзадача. Основная проблема - это исходная проблема, в которой рассматривается только подмножество переменных. Подзадача - это новая проблема, созданная для идентификации новой переменной. Целевая функция подзадачи - это уменьшенная стоимость новой переменной по сравнению с текущими двойственными переменными, а ограничения требуют, чтобы переменная подчинялась естественным ограничениям.
Процесс работает следующим образом. Основная проблема решена - из этого решения мы можем получить двойные цены для каждого из ограничений в главной задаче. Затем эта информация используется в целевой функции подзадачи. Подзадача решена. Если объективное значение подзадачи отрицательное, была идентифицирована переменная с отрицательной приведенной стоимостью. Затем эта переменная добавляется к главной задаче, и основная проблема решается повторно. Повторное решение основной задачи приведет к созданию нового набора двойных значений, и процесс будет повторяться до тех пор, пока не будут идентифицированы отрицательные переменные приведенной стоимости. Подзадача возвращает решение с неотрицательной приведенной стоимостью, мы можем сделать вывод, что решение основной задачи является оптимальным.
