21. Сходимость СМ. Вырожденность в задачах ЛП.

Важнейшим свойством любого вычислительного алгоритма является сходимость, т.е. возможность получения ходе его применения искомых результатов (с заданной точностью) за конечное число шагов (итераций).

Легко заметить, что проблемы со сходимостью СМ потенциально могут возникнуть на этапе выбора значения r в случае, когда одинаковые минимальные значения отношения

λi=bi(β(q))/ail(β(q)), i=1,m; ail(β(q))>0

будут достигнуты для нескольких строк таблицы одновременно. Тогда на следующей итерации столбец b(β(q+1)) будет содержать нулевые элементы.

Допустимы базисный план канонической задачи ЛП, соответствующий базису β(q), называется вырожденным, если некоторые его базисные компоненты равны 0, т.е вектор b(β(q)) содержит нулевые элементы.

Задача ЛП, имеющая вырожденные планы, называется вырожденной. При «выходе» на вырожденный план мы фактически получаем разложение столбца b по системе меньшего, чем m, количества столбцов aj и, следовательно, лишаемся возможности корректно определить, ввод какого столбца в базис приведет к росту значения целевой функции. Подобные ситуации, в конечном счете, могут привести к зацикливанию вычислительного процесса, т.е. бесконечному перебору одних и тех же базисов.

С точки зрения геометрической интерпретации ЗЛП ситуация вырожденности означает, что через некоторую угловую точку многогранного множества допустимых планов задачи, соответствующую текущему базисному плану, проходит более чем m гиперплоскостей ограничений задачи. Иными словами, одно или несколько ограничений в данной точке являются избыточными. Последнее предоставляет повод для размышлений об экономической стороне проблемы вырожденности как проблемы наличия избыточных ограничений и в некоторых случаях определяет путь ее решения.

С точки зрения второй геометрической интерпретации ЗЛП вырожденность означает «попадание» линии, проходящей через вершину вектора b параллельно оси аппликат, в ребро конуса, натянутого на систему расширенных векторов текущего базиса.

Из данной интерпретации вытекает и идея метода решения вырожденных задач ЛП, получившего названия метода возмущений: при выходе на вырожденный план осуществляется незначительный сдвиг вектора b и вырожденность устраняется.

<< | >>
Источник: Шпаргалка - Математические методы и модели исследования операций. 2016
Вы также можете найти интересующую информацию в научном поисковике Otvety.Online. Воспользуйтесь формой поиска:

Еще по теме 21. Сходимость СМ. Вырожденность в задачах ЛП.:

  1. 45. Вырожденность и ее устранение при решении задач симплекс-методом.
  2. 14. Понятие числового ряда. частичные суммы, определение сходимости ряда. Критерий Коши сходимости ряда. Необходимое условие сходимости ряда. Исследование на сходи­мость ряда
  3. 47. Оценка погрешности и сходимость одношаговых методов решения задачи Коши.
  4. 62. Сходимость сеточного метода решения краевой задачи для уравнения Пуассона.
  5. 54. Сходимость сеточного метода решения краевых задач для обыкновенных диф. уравнений.
  6. Вырожденность
  7. 25. Вырожденные и невырожденные квадратные матрицы.
  8. 19. Абсолютная и условная сходимость. Теорема о связи между сходимостью рядов и Свойства абсолютно сходящихся рядов. Признаки Даламбера и Коши для знакопеременных рядов.
  9. Творческое вырождение.
  10. 73. Решение интегрального уравнения Фредгольма 2-го рода методом вырожденного ядра.
  11. Несобственные интегралы. Сходимость интегралов. Критерии сходимости
  12. 71. Решение интегрального уравнения Фредгольма 2-го рода с вырожденным ядром.
  13. 29. Равномерная сходимость. Критерий Коши равномерной сходимости.
  14. Абсолютная и условная сходимость рядов.
  15. ТЕОРЕМА. (Второй признак сходимости)
  16. Признаки сходимости числовых рядов
  17. 17. Степенные ряды. Радиус и интервал сходимости.
  18. 27. Теорема: Вырожденная квадратная матрица не имеет ни левой обратной, ни правой обратной.
- Аналитическая геометрия - Высшая математика - Высшая математика - Вычислительная математика - Вычислительные методы линейной алгебры - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комбинаторика - Комплексное исчисление - Линейная алгебра - Линейная алгебра и аналитическая геометрия - Линейное программирование - Математическая логика - Математическая статистика - Математическая физика - Математический анализ - Метод конечных элементов - Методы оптимизации - Обработка результатов измерений - Общая алгебра - Операционное исчисление - Основы математики - Планирование эксперимента - Пределы - Ряды - Теория вероятностей - Теория графов - Теория игр - Теория конечных автоматов - Теория массового обслуживания - Теория принятия решений - Теория случайных процессов - Теория чисел - Философия математики - Функциональный анализ - Элементарная математика -