Линейное программирование. Итерационный метод

из "Приближенное решение задач оптимального управления "

Имеющийся у автора опыт (впрочем, существенно связанный с итерационным методом 48) заставляет осторожно относиться к этому сведению, отдавая предпочтение тому способу решения (с е= 1, 1,. . ., 1, 0,. . ., 0 ), который был изложен выше. [c.437]
Напомним, что решение такой задачи само по себе определяет только значение X, однако после того как X и соответствующий вектор g найдены, определение прообраза Хе в о сводится к решению системы т линейных алгебраических уравнений (см. 47). [c.438]
Перейдем к описанию алгоритма. [c.438]
Прежде всего докажем простую лемму, обосновывающую выбор параметра а при вычислении нового вектора g. [c.443]
Однако это очень грубая оценка, и мы просто предполагаем, что s выбрано таким, что обеспечивается соотношение ц т . [c.444]
Доказательство очевидно и опускается. [c.445]
Введем теперь нумерацию граней у, отсчитывая их влево от самой низкой точки л, как показано на рис. 79, с). Каждая грань порождена своим вектором Нп, и первой соответствует вектор ffn , второй — Яи2, и т. д. [c.445]
Таким образом, наклон первой же грани, левый конец которой попадает в полуплоскость zl p, обязательно превосходит е. Лемма доказана. [c.446]
Доказательство очевидным образом следует из леммы 4 и из того, что наклон границы у на отрезке 0 z1 [i = x 1 ) e(l — d) больше е. [c.446]
Лемма 6. В итерационном процессе не может быть зацикливания по признаку d ] d. [c.446]
Это есть направление спуска для р- Находим предварительный шаг спуска Д решением задачи min x -J- Дг , т. е. Д = — - — -. [c.450]
Здесь также отмечается факт выхода на границу, и если он имел место, то соответствующая переменная sn исключается (яя=1), вычисляются новые Н1п (для —2), и переходим к пункту 5. [c.450]
Далее переходим к пункту 6. [c.450]

Вернуться к основной статье