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

Контенус

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

Исходная задача генерации столбца называется основной задачей, а упрощенная задача называется ограниченной задачей.

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

Проблема поиска наилучшей переменной для добавления к ограниченной задаче называется подзадачей, связанной с главной задачей (или оракулом). Его цель — найти переменную (или столбец) минимальной приведенной стоимости (т. е. наиболее перспективную для улучшения решения).

Приведенная стоимость переменных рассчитывается с использованием двойственных переменных, полученных после решения ограниченной задачи. Точка двойственности, используемая таким образом в подзадаче, называется точкой разделения. Часто это оптимальное решение двойственной ограниченной задачи.

Рассмотрим следующую непрерывную линейную программу (ЛП):

Мы предполагаем, что количество переменных T слишком велико для решения задачи (LP) за разумное время, и что мы хотим решить ее путем генерации столбцов. Поэтому мы стремимся решить ограниченную проблему, связанную с главной проблемой, с ограниченным набором переменных, обозначенным R_я. Ограниченная задача должна быть разрешимой. Можно использовать простые столбцы, например случайные столбцы, или даже столбцы, полученные в результате допустимого решения, полученного из эвристический.

Задача (RLP) теперь уменьшена в размере, и ее будет легче решить с помощью решателя. Это разрешение даст нам оптимальные значения двойственных переменных v_я связаны с ограничениями. Эти значения передаются в подзадачу, которая позволяет нам получить столбец или столбцы для добавления в набор R._я.

Расчет приведенной стоимости позволяет нам узнать, уменьшила ли колонка значение цели (и, следовательно, улучшила ли ее).

Так как (LP) является проблемой минимизация, подзадача также стремится минимизировать эту уменьшенную стоимость. Если минимальная приведенная стоимость положительна, то в ограниченную задачу (RLP) нельзя добавлять столбцы для улучшения цели. Таким образом, оптимальное решение ограниченной задачи является оптимальным решением основной задачи (LP). В противном случае мы добавляем один или несколько столбцов среди тех, которые имеют отрицательную приведенную стоимость, обновляя множество R_я и затем мы решаем новую ограниченную задачу (RLP).