Конечность симплекс-метода. Если задача линейного программирования в канонической форме не имеет вырожденных опорных решений, то через конечное число шагов симплекс-метода она будет решена. [c.198]
Вектограмма 52, 95 Внебазисная переменная 419 Вторая вариация 203 Выпуклая оболочка 86, 125 Выпуклое тело, множество 369 Выпуклый конус 46 Вырожденная задача линейного программирования 171 Вычислительная технология 173, 210 [c.484]
ВЫРОЖДЕННАЯ ЗАДАЧА [degenerate problem] — задача линейного программирования, в которой при разложении вектора ограничений В (обозначения см. в ст. "Линейноепрограммирование") по некоторому базису а]х. ... ат по крайней мере один коэффициент оказывается равным нулю. Такая ситуация затрудняет решение задачи симплексным методом, вызывая явление "зацикливания", при котором одно и то же множество базисных решений будет периодически повторяться, а оптимальный план никогда не будет достигнут. [c.59]
СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ (симплекс-метод) [simplex method] — вычислительная процедура, основанная на принципе последовательного улучшения решений — перехода от одной базисной точки (см. Базисное решение) к другой, для которой значение целевой функции больше (эти операции фиксируются в симплексной таблице). Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов (за исключением т.н. вырожденной задачи, при которой возможно явление "зацикливания", т.е. многократного возврата к одному и тому же положению). Название метод получил от термина " -мерный симплекс". Геометрическая интерпретация метода состоит в последовательном движении по верши) шм симплекса. [c.322]
См. также Ассортиментные задачи, Базисное решение, Блочное программирование, Булево линейное программирование, Ведущий столбец, Ведущая строка, Вершина допустимого многогранника, Вырожденная задача, Гомори способ, Граничная точка, Двойственная задача, Двойственность в линейном программировании, Дифференциальные ренты, Дополняющая нежесткостъ, Жесткость и нежесткость ограничений ЛП, Задача диеты, Задача о назначениях, Задача о раскрое, Задачи размещения, Исходные уравнения, Куна— Таккера условия, Множители Лагранжа, Область допустимых решений, Опорная прямая, Оптимальное распределение ресурсов, Распределительные задачи, Седловая точка, Симплексная таблица, Симплексный метод, Транспортная задача. [c.173]