Алгоритм симплексного метода

Для решения задач линейного программирования имеется практически универсальный алгоритм — симплексный метод, позволяющий за конечное число итераций находить оптимальное решение подавляющего большинства практически важных задач. Тип используемых ограничений (равенства или неравенства) не сказывается на возможности применения указанного алгоритма. Дополнительной проверки на оптимальность для получаемых решений не требуется. Как правило, практические задачи линейного программирования отличаются весьма значительным числом независимых переменных. Поэтому для их решения обычно используют вычислительные машины, необходимая мощность которых определяется размерностью решаемой задачи. [c.33]

Поэтому в некоторых алгоритмах симплексного метода, запрограммированных на вычислительных машинах, в качестве критерия выбора небазисного вектора, вводимого в базис, применяется величина разности Ск — 2. Вектор Ak, для которого разность с — г наибольшая, и вводится в исходный базис. Для этого алгоритма после вычисления обратной матрицы [р/ ] (УП1,135) необходимо еще рассчитать матрицу коэффициентов разложения (УП1,]37) и величины г (УИ1,139). [c.441]

Алгоритм симплексного метода [c.452]

Теперь воспользуемся алгоритмом симплексного метода для отыскания оптимального плана производства. [c.473]

Рассмотрим наглядную иллюстрацию алгоритма симплексного метода на примере задачи отыскания наименьшего значения целевой функции двух независимых переменных с линиями постоянного уровня, изображенными на рис. 1Х-23. [c.516]

Алгоритм симплексного метода заключается в том, что в вершинах симплекса, построенного в области изменения независимых переменных, вычисляются значения оптимизируемой функции и находится вершина с наихудшим значением (наибольшим в случае поиска минимума). [c.388]

Алгоритм симплексного метода. Симплексный метод реализуется в два этапа. На первом этапе определяется начальное базисное допустимое решение, если оно существует. На втором этапе ищется базисное решение, минимизирующее целевую функцию. [c.185]

Алгоритм симплексного метода продемонстрируем на примере решения задачи, рассмотренной в разд. V.2.1 и представленной на рис. У.З, т. е. max Z = Xi l- Зх , с ограничениями [c.188]

Алгоритм симплексного метода позволяет обоснованно выбирать очередное базисное решение и по определенным правилам определяет, как поступить дальше прекратить вычисления или перейти к следующему базисному решению. [c.198]

Ниже при изложении одного из возможных вариантов алгоритма симплексного метода использован прием циркуляции информации в стандартных ячейках, имеющих собственную индексацию. [c.447]

На этом размещение исходной информации заканчивается и начинается выполнение этапов алгоритма симплексного метода. [c.450]

При выводе основных соотношений симплексного метода допускалось, что любые т векторов из общего числа n + m + 1 векторов AJ и В, составляющих матрицу ограничений, линейно независимы. При решении практических задач данное требование, как правило, обычно выполняется. Поэтому рассмотренный выше алгоритм симплексного метода служит основой подавляющего большинства программ, составленных для решения задач линейного программирования на вычислительных машинах. . [c.454]

Попыткой избежать необходимости вычисления производных для определения направления наискорейшего продвижения к оптимуму и в то же время сохранить возможность достаточно быстрого движения к нему является алгоритм симплексного метода [5]. [c.512]

Таким образом, алгоритм симплексного метода допускает автоматическое. изменение величины шага, при использовании которого вдали от оптимума возможно применение симплексов большого размера, что обеспечивает более быстрый спуск. [c.514]

Недостатком симплексного метода является возможность произвольного попадания в одну из возможных зон минимизации, если целевая функция является полиэкстремальной (имеет несколько точек минимума) Поскольку алгоритм симплексного метода поиска экстремума является весьма быстродействующим, то целесообразно выполнить серию расчетов в нескольких исходных точках А для того, чтобы убедиться в сходи.мости решения задачи независимо от позиции А, при этом также выясняется, имеет ли задача единственное решение или у нее имеется несколько решений. [c.107]

Справочник химика 21

Химия и химическая технология