Симплексный алгоритм
Cтраница 3
При т 1 применение основного алгоритма связано с использованием симплексного алгоритма для решения оценочных задач, что не всегда удобно. Решим m линейных одномерных задач. В задаче с номером г рассматривается лишь ограничение с этим номером. [31]
При подобной постановке задачи, когда все ограничения линейны, симплексный алгоритм с двусторонними ограничениями на переменные также может быть модифицирован с учетом правила ограниченного ввода в базис, обусловливающего обязательное выполнение свойства весов смежных точек. На любой итерации yk l может быть введено в решение только в том случае, если у входит в базис, причем с максимально допустимым значением, равным X i - Х; Уь может быть исключена из базиса, только если y i не входит в базис и имеет нулевое значение. [32]
В каждом из приведенных ниже вариантов постановки задачи примените модифицированный симплексный алгоритм, описанный в разд. [33]
Именно эту точку и выбирают в качестве исходной для применения симплексного алгоритма. [34]
Эти методы иллюстрируются на примере, решение которого вначале определяется с помощью симплексного алгоритма, что дает базу для последующего их сравнения. Как будет показано в разд. [35]
Таким образом, все, что требуется, - это взять начальную часть симплексного алгоритма и добавить дополнительные ограничения. [36]
Если не считать изменения формулировок, вызванного нелинейным характером задачи, критерии I квадратичного симплексного алгоритма основан на том же подходе, что п критерий I симплексного алгоритма. В обоих случаях улучшение возникает благодаря введению в решение одной небазисной переменной. [37]
Можно построить патологические примеры, показывающие, что при использовании правила ограниченного ввода в базис симплексный алгоритм может даже не давать локального оптимума аппроксимирующей задачи. Такая ситуация возникает, если в текущий базис входят два смежных веса wh и Wh i, причем, вводя в базис wk z и исключая wh, мы можем улучшить значение целевой функции. Все же такие необычайные ситуации встречаются редко. [38]
Мы предполагаем, что: а) выражение (26.9) имеет конечный оптимум и б) симплексный алгоритм достигнет оптимальной для этой задачи матрицы через конечное число итераций. Как будет показано в следующем параграфе, предположение а) можно опустить, принимая во внимание теорему двойственности. Однако если а) справедливо, то б) легко вытекает из теории возмущений, которой мы пользуемся в связи с симплексным методом. Теория возмущений, с другой стороны, гарантирует, что каждая итерация даст z ( е), которое будет строго меньше, чем его предшественники. Так как в выражении (26.9) мы имеем дело с оптимальным базисным решением, а точнее, с соответствующим множеством базисных векторов, то мы можем быть уверены, что единственное наименьшее г ( е) будет достигнуто через конечное число итераций. [39]
Как было показано для уравнения (26.8), этот вид неопределенности можно устранить, если задать для (26.55) специальный симплексный алгоритм. [40]
Если характер целевой функции и ограничений таков, что обеспечивается свойство весов смежных точек, то можно применить обычный симплексный алгоритм, программы которого имеются на всех ЭВМ. Модифицированный алгоритм, обеспечивающий наличие этого свойства в обязательном порядке, имеется на большинстве мощных ЭВМ. [41]
 |
Данные регрессии.| Примеры регрессии. [42] |
Следовательно, теоремы и следствия предыдущего раздела справедливы без оговорок, а модель (26.9), когда она завершается симплексным алгоритмом, можно всегда использовать для характеристики ранга любой матрицы А. [43]
Изложение материала построим так же, как и ранее: покажем, что метод отыскания искомых правил является в конечном итоге методом, основанным на симплексном алгоритме линейного программирования. [44]
Если не считать изменения формулировок, вызванного нелинейным характером задачи, критерии I квадратичного симплексного алгоритма основан на том же подходе, что п критерий I симплексного алгоритма. В обоих случаях улучшение возникает благодаря введению в решение одной небазисной переменной. [45]
Страницы: 1 2 3 4