Задачи ЦЛП: Метод отсекающих плоскостей. Оценка количества плоскостей #270243

А можно ли как-то оценить количество плоскостей, которое придется построить для нахожднения оптимального решения?

up-ну; Может математики проснулись:)

во-во, а мне надо задачу рюкзака решить упрощенную

какие такие плоскости зачем их отсекать :(

к сожалению я уже вышку пропил.. не помню, чес слово.. што-то сумбурное в голове вертится... Может более яснее объяснишь задачку - авось какой нибудь нейрон из 3 да и проснется..

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

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

Народ, сегодня же пятница... :(

не.. не думается..

Думаю, иного придется построить :) Как правило, целочисленные задачи - это трудные задачи и количество ресурсов для точного решения весьма велико в худшем случае. Я диплом писал когда-то по похожей на задачу о рюкзаке NP-полной задаче.

ну например к задаче, которую я в прошлой ветке приводил - только 2 отсечения придется строить. А перебор там не прокатит. Задача рюкзака для меня большой геммор - в практике она встречается переодически, но как ее решить так, что бы а) не писать километры кода б) быстро работало в) работало правильно:) пока не придумал... Собственно проще всего конечно простой перебор - 10 минут работы и процедура готова. Но если речь идет о 1000 позиций? 2^1000 - это ж сколько будет обрабатываться?

Если на 1С, то 2^30 это пол-дня..

Долго. Так а книжку, что я в том посте приводил, можно посмотреть. Там уже готовые точные алгоритмы есть, которые зачастую намного быстрее перебора работают. Еще там можно посмотреть работу D. Pisinger'а

Вычислительные машины и труднорешаемые задачи я уже скачал:) А вот Мартелло и Тот - не могу найти даже в бумажном виде:(

Поищи лучше :)

Спасибо большое.

Жаль, что только на английском..

Для рюкзака вполне удовлетворительно работают: - жадный алгоритм; - схема ветвей и границ с оценкой по релаксированной (линейной, непрерывной) задаче.

Увы.. Но это в общем небольшая беда.

прошу прощения за пробелы в образовании, а что такое "оценка по релаксированной (линейной, непрерывной) задаче"?

up

вверх

Рюкзак в чистом виде: A1*X1+A2*X2+...+An*Xn <= B, 0<=Xi<=1, Xi - целые C1*X1+C2*X2+...+Cn*Xn -> MAX В схеме ветвей и границ Вы фиксируете какие-либо переменные и получаете подзадачу. В качестве оценки значения функционала в этой подзадаче берется решение соответствующей задачи линейного программирования (весьма специфической, для нее можно получать решение не симплекс-методом а проще), т.е. условия Xi - целые снимаются. Это и называется релаксацией. Ветвление задачи производят на 2 подзадачи: по Xi=1 и Xi=1. Подробное описание найдете в литературе. Жадный алгоритм еще проще и быстрее: - упорядочиваете переменные по Ci/Ai; - назначаете Xi=1 в этом порядке, пока выполняется ограничение. Если нужна консультация - пишите или звоните 980-2417.

Виноват, описался: вместо по Xi=1 и Xi=1 нужно по Xi=0 и Xi=1.

Спасибо. Т.е. вместо двух ограничений Xi >= 1 и Xi <= 0 мы получаем два равенства. И такие задачи соответсвенно решить можно много проще.. Но ведь жадный алгоритм в чистом виде предполагает определенную погрешность.. Есть ли варианты жадного алгоритма, позволяющие свести погрешность к минимуму?

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

Спасибо за ответы.