Линейное программирование. Симплекс-метод

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

Перейдя к вектору — g, получим вторую точную грань Р, соответствующую данному набору индексов М. В настоящее время разработано большое число алгоритмов точного решения задачи Л. Все они объединяются общим термином симплекс-метод, однако различают прямые и двойственные варианты симплекс-метода. С этими двумя вариантами связаны две основные качественные идеи, в той или иной мере лежащие в основании большинства алгоритмов как точного, так и приближенного решения задачи линейного программирования. [c.419]
Этим и заканчивается стандартный шаг симплекс-метода. Доказывать теорему о его сходимости мы здесь не будем, однако укажем на основные факторы этого доказательства. [c.422]
Вычисления далее продолжаются с пункта I. [c.424]
Нестандартные задачи линейного программирования. Рассмотрим некоторые задачи, встречающиеся при решении задач с функциями, не имеющими производных, но дифференцируемыми по направлениям. В 46 читатель может познакомиться с тем, каким образом возникают такие задачи. Здесь же будет показано, что они сводятся к стандартной задаче линейного программирования. [c.431]
Очевидно, что Sjf+k 0 (т. е. SB о ) и, так как s n удовлетворяет условиям II задачи А, точка sn отображается в точку Л е. Таким образом, Л А. [c.432]
Рассмотрим следующую пару задач. [c.433]
Требуется найти точку е( Р с наименьшим значением X (т. е. тшж° при = О, я = 0). [c.434]
Теорема 3. Задачи В1 и В — эквивалентны. [c.434]
В этом случае, очевидно, ап = tk -f- т)Л, т. е. [c.434]
Задачи А, В возникают при решении методом Ньютона следующих задач условной минимизации. [c.434]
Теорема 4. Задачи С и С эквивалентны. [c.436]
Доказательство опускается оно аналогично проведенным выше. [c.436]

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