Cтраница 2
ШТРАФНЫЕ ФУНКЦИИ [ penalty functions ] - вспомогательные функции, применяемые при численном решении некоторых классов зз. После этого решается задача минимизации суммы Ш.ф. и целевой функции исходной задачи с помощью одного из известных вычислительных алгоритмов. [16]
Целый ряд способов построения расширенных задач основан на добавлении к целевой функции исходной задачи слагаемого, зависящего от искомых переменных таким образом, что на множестве допустимых решений исходной задачи оно обращается в нуль. Ниже рассмотрены расширения Лагранжа и Кротова и расширение, основанное на добавлении функций штрафа. [17]
Понятно, что чем больше ограничений используется, тем больше формируется столбцов на каждом цикле, из которых затем выбирается столбец, вводимый в базис. А это в свою очередь повышает вероятность увеличения скорости убывания значения целевой функции исходной задачи. Но увеличение числа учитываемых ограничений в то же время создает дополнительные вычислительные трудности при реализации используемого при таком подходе модифицированного симплекс-метода. [18]
Процесс ветвления и решения задач ЛП продолжается до получения целочисленного оптимального решения одной из задач ЛП. Значение яь в полученной точке представляет собой текущую нижнюю границу оптимального значения целевой функции исходной задачи ЦЛП. [19]
Обратим также внимание на то, что теорема двойственности позволяет проверить на оптимальность любое допустимое пробное решение исходной задачи. Если существует допустимое решение двойственной задачи, для которого значение целевой функции совпадает со значением целевой функции исходной задачи, то решения обеих задач являются оптимальными. [20]
Докажите, что оптимальные значения ck целевой функции суженной координирующей задачи монотонно возрастают, стремясь в пределе к оптимальному значению с целевой функции исходной задачи. [21]
Одной из основных проблем здесь, становится обоснованная формализация совокупности этих процедур и промежуточных этапов в виде целенаправленных итерационных процессов, а также их реализация и автоматизация с помощью ПВК. При этом не должна забываться первоначальная цель, заключающаяся в получении общего оптимального решения, и потому каждый из этапов и весь процесс декомпозиции необходимо интерпретировать и анализировать с точки зрения удовлетворения всей системы ограничений и достижения глобального ( или по крайней мере локального) минимума целевой функции исходной задачи, а также и возможности изучения поведения решения вблизи своего экстремума. Выделение иерархий подзадач на содержательном уровне и формальная декомпозиция общей задачи часто осуществляются совместно и настолько переплетаются, что их трудно четко разделить. [22]
После нахождения вектора, вводимого в базис, определяем вектор, исключаемый из него. Для этого находим разложения векторов Р ( или Р) и РО ( вектор, определяющий опорный план главной задачи) по векторам данного базиса и определяем минимум отношения компонент вектора РО к соответствующим положительным компонентам вектора РУ в данном базисе. Наименьшее из этих отношений и определяет вектор, исключаемый из базиса. В результате получается новый базис, определяющий последующий опорный план главной задачи. Этот план проверяем на оптимальность, для чего строим соответствующую подзадачу ( подзадачи) и находим решение. Данное решение позволяет сделать вывод, является ли соответствующий опорный план оптимальным или нет. Если он не оптимален, то по описанным выше правилам переходим к новому базису, определяющему некоторый последующий опорный план. При этом заметим, что в ходе итерационного процесса возможен случай, когда среди компонент разложения вектора РУ по векторам данного базиса не имеется положительных. Это означает, что целевая функция главной задачи на множестве ее допустимых решений не ограничена, а следовательно, не ограничена и целевая функция исходной задачи. [23]