Шпаргалка по исследованию операций — страница 6

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

осуществляется до тех пор, пока остаётся хотя бы одна непрозондированная вершина. Эффективность алгоритма существенно зависит от скорости последовательного зондирования вершин. Обычно для выполнения условий 1 и 2 требуется значительное время. Условие 3 нельзя применять до получения нижней границы. Однако нижняя граница определяется только после рассматривания вершины с допустимым решением исходной задачи, то есть вершины

удовлетворяющие условию 1. Поэтому получение перед реализацией алгоритма целочисленного решения исходной задачи может оказаться весьма полезным. Такое решение даёт начальную нижнюю границу, которая используется для получения лучшей нижней границу в процессе ветвления. БИЛЕТ 6 ВОПРОС 1 Алгоритм нумераций событий структурного плана Упорядоченную нумерацию событий проводят по алгоритму: Основанному на использовании метода

вычеркивания работ. Алгоритм предусматривает последнюю нумерацию событий, образующихся после вычеркивания (условного исключения) работ, выходящих из уже пронумерованных событий. Если в процессе нумерации обнаружился контур, то следует проверить правильность изображения на сети работ, ограничивающих непронумерованный участок. Нумеацию событий следует начинать с 0. БИЛЕТ 6 ВОПРОС 2 Метод ветвей и границ. Для определения

истинного значения целочисленных переменных применяется метод отсечений и метод ветвей и границ. Первый базируется на идее деформации ОДР задачи ЛП таким образом, чтобы от нее было отсечено оптимальное нецелочисленное решение, но сохранены все допустимые целочисленные решения. Т.е. была бы построена область, для которой оптимальное решение соответствующей задачи ЛП совпадает с оптимальным решением задачи ЦЛП. Указанная

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