Как работает метод генерации столбца?

[damir_777]

Здравствуйте
Не могли бы вы объяснить как работает метод генерации столбца при решении задач линейного программирования?
Я конечно искал в интернете, но как правило чаще всего попадается литература с нагромождением формул, а практических примеров почти нету, да и непонятно как то объяснено.
Вопросы такие:
1.По какому принципу производится замена/добавление столбца?
Мне попадалось пару примеров. Причем в одном из них размер матрицы ограничений не менялся, а просто заменялся необходимы столбце, в другом добавлялся новый столбец при решении вспомогательной задачи. Теперь допустим, получив двойственный оценки после решения задачи линейного программирования, я решаю задачу о рюкзаке, нахожу ее решение. Далее как поступать дальше: как выявить какой столбец должен быть заменен и должен ли быть он заменен или добавлен , т.е матрица ограничений должна быть расширена? И все ли время ее нужно расширять , т.е добавлять новый столбец, или же в определенном случае добавляется новый столбец, в других происходит замена столбца в текущей матрице ограничений?
2. Обязательно ли при решении задачи методом отложенной генерации матрица ограничений должна иметь блочно диагональный вид. Я например столкнулся с примером гда матрица ограничений не имеет блочно диагонального вида. Это задача одномерного раскроя (Бабаев Оптимальный раскрой с помощью ЭВМ) . Метод называется метод Гилмори-Гомори. Я незнаю является ли он методом генерацией столбцов, принцип очень похож. Алгоритм там такой. Вначале после решения исходной системы ограничений (предположим имеется 4 переменный и матрица размером 4 на 4) и решении вспомогательной задачи (рюкзак) добавляется в конец новый столбец (пятый) . А в дальнейшем столбцы заменяются, т.е к примеру если матрица имеет пять переменных (пять столбцов) и допустим, удаляется третий столбец, то четвертый заменяет место третьего, пятый место четвертого, а решение задачи о рюкзаке вставляется в пятый столбец, т.к он освободился сдвигом на четвертый столбец. Я вот не пойму это тоже какой то вариант метода генерации столбцов?
И если есть ссылки на подробные примеры , буду очень благодарен

[deep blue]

damir_777 в сообщении #1118420 писал(а):

Не могли бы вы объяснить как работает метод генерации столбца при решении задач линейного программирования?

Как обычный "модифицированный симплекс-метод". Условие удаления столбца аналогичное. Столбец должен быть заменен в базисной матрице(обратная к базисной матрице при этом легко пересчитывается, а не находится заново), которая имеет всегда один и тот же размер равный числу уравнений. Она не может расширится в принципе. Другое дело если мы не хотим реализовывать симплекс-метод, а хотим воспользоваться готовой реализацией, использующей фиксированную матрицу ограничений на вход. Тогда просто добавляем один столбец к "текущей" матрице ограничений и вызываем функцию решения задачи ЛП. Несмотря на постоянное перерешивание небольшой ЛП задачи такая стратегия может оказаться эффективнее, потому что текущая матрица ограничений предположительно должна содержать основную часть "нужных" столбцов (каждый из них когда либо поучаствовал в увеличении целевой функции) и не придется много раз генерировать/удалять новые столбцы по кругу.
На английском куча ссылок и объяснений, на русском особо не встречал. Можете глянуть Таха там показано решение большой задачи ЛП методом декомпозиции на множество мелких задач если матрица ограничений блочная. Вообще в методе генерации столбца структура матрицы нас не волнует, но конечно может быть использована для решающего ускорения. В общем английский в помощь, если хотите разобраться в идеях и фичах. Например, в подобных задачах вместо симплекс-метода решения прямой задачи могут использовать метод неопределенных множителей Лагранжа и градиентный метод для решения двойственной задачи. Если в прямой мы приближались к минимуму по допустимым решениям сверху вниз, то здесь будем подниматься по не допустимым снизу вверх и на любой итерации можно прекратить решение, получив нужную нижнюю границу. Этот метод гораздо проще в реализации.

[damir_777]

кажется теперь начинаю понимать. В литературе часто упоминается именно модифицированный симплекс-метод. И в примерах показывается замена столбца в базисной матрице, чтобы понять суть замены, а обращенная матрица опускается и не показывается. Я реализовал алгоритм решения задач лин. программирования обычным симплекс-методом, а не модифицированным, и брал только базисную матрицу, а обращенную не учитывал и поэтому у меня может и возникали проблемы, а именно появлялась нулевой столбец на определенной итерации. Я писал здесь на форуме раньше по проблеме раскроя.
Я не понял один момент: если я решаю задачу обычным симплекс-методом ( потом из симплекс-таблицы беру оценки и передаю их в подзадачу (рюкзак)), то в дальнейшем пока целевая функция подзадачи больше единицы, мне на остальных итерациях достаточно добавить один раз новый столбец, а потом уже не добавлять , а только заменять или же после каждого решения подзадачи нужно добавлять новый столбец (решение задачи о рюкзаке)?

[deep blue]

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

[damir_777]

Скажите, а вот , например, при решении задач раскроя (одномерного), когда составляются исходные варианты раскроя, равные количеству заготовок, то в этом случае решать добавлением столбца или заменой?
Я просто описывал ситуацию на другом форуме для задачи раскроя, когда я только заменял столбцы, и у меня получилась нулевая строка .Вот эта ссылка http://www.cyberforum.ru/optimization-m ... 09111.html
Там же я выложил книгу (на английском) по которой реализовал алгоритм. Ее можно скачать прямо с форума.
Не могли бы вы сказать с чем это связано, я просто решал задачу обычным симплекс-методом. Может когда используется второй вариант итерации, то что описали, нужно решать задачу именно модифицированным симплекс-методом? (а я столбцы заменять заменяю, а обращенный базис отстутствует, может если он был бы то в наверняка в нулевой строке появились бы ненулевые элементы из обращенного базиса и задачу можно было продолжать решать)
а в моем случае нужно было только добавлять новые столбцы

[deep blue]

Честно говоря с трудом представляю не модифицированный симплекс-метод применительно к задаче с нелимитированной матрицей ограничений в ширину. Да и чтобы потом решать подзадачу рюкзака, надо же изменить стоимости, которые как раз вычисляются используя обратную матрицу. То есть она в любом случае нужна в явном виде вроде бы. Я уже три года этим не занимался, но что-то еще помню)
Однозначно переделайте на модифицированный с ним потом проще работать. Конечно на каждой итерации вычисляйте обратный базис и ошибка скорее всего произойдет гораздо раньше -- когда матрица станет вырождена, а не когда вы обнаружите в ней нулевую строку. Желательно так же чтобы начальный базис был реальным, а не искусственным, это как минимум упростит отладку. Файл посмотреть не могу так как надолго улетаю, удачи с отладкой!

[damir_777]

Спасибо) будем разбираться