Cтраница 4
Если х и у вершимы многогранника М такие, что г ( х, r /) diamM, то, взяв линейную функцию сх, экстремум которой достигается в вершине у и, выбрав в качестве стартовой вершины вершину х, получим, что число итераций симплексного алгоритма при решении задачи extr сх: х е М ] не может быть меньше diam M. Разумеется, при условии, что наилучший алгоритм будет построен. [46]
В силу характера задачи допустимое решение содержит ровно п переменных, равных единице, тогда как любое базисное решение включает п п - 1 переменных. Это обстоятельство приводит к выводу, что применение симплексного алгоритма не обеспечивает в полной мере учета особой структуры модели назначений. В данном разделе будут изложены три отличных от симплексного метода решения задачи о назначениях. [47]
Важно отметить, что при однозначном понимании данного предписания предложенный алгоритм действительно приводит к опти-малыюму решению для любой модели линейного программирования за конечное число итераций. Такой способ решения задач линейного программирования часто называют симплексным алгоритмом. [48]
Нахождение вектора у связано с решением задачи линейного программирования. Для решения задачи (2.2.4) ( 2.2.6) необходимо применение симплексного алгоритма, что не всегда удобно. [49]
Если бы у нас было 200 переменных, существовало бы 200 ура нений с 200 неизвестными. Задача стала бы чрезвычайно трудной Однако, компьютерные версии симплексного алгоритма очен эффективны и могут скрупулезно и эффективно решать задачи включающие сотни переменных и ограничений. [50]
Связь между двумя подходами обусловливает также возможность доказательства сходимости метода последовательных приближений в пространстве стратегий к оптимальному решению за конечное число итераций. Требуется лишь незначительно изменить доводы относительно достижения оптимума и конечности симплексного алгоритма. [51]
Завершив первую итерацию, следует вернуться к шагу 2, с тем чтобы определить, является ли полученное решение оптимальным. Если оптимум еще не достигнут, необходимо в соответствии с симплексным алгоритмом приступить к следующей итерации. [52]