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

насколько можно увеличить её длительность без изменения сроков выполнения других работ, а полный резерв - при сохранении длительности критического пути. Результаты расчетов параметров событий заносятся в специальную форму, которая называется «таблица событий» Индекс события Ранний срок свершения события, Тран Поздний срок свершения события, Тпоз Резерв времени свершения события, Rсоб 1 2 3 4 БИЛЕТ 7 ВОПРОС 2 Особенность линейно

– целочисленных задач и методов их решения Задача ЦЛП – это задача математического программирования, в которой все или некоторые переменные должны принять только целочисленное значение, а целевая функция и функции, входящие в ограничение – линейное. Т.е. это такая нелинейная задача, которая может быть линейной, если бы не требования целочисленности ряда переменных. Задачу ЦЛП можно решать например, как задачу ЛП без учета

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

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

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

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