Задать вопрос юристу

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. 21. Задача о распртепла в неограниченном стержне и ее реш методом разделения переменных. Интеграл Пуассона и его вычисление. Фундаментальное реш. ур-ия теплопроводности. Численное реш. ур-ия теплопроводности. Основные понятия теории р/схем.
  2. 26. Интерполирование функций. Глобальная интерполяция алгебраическими многочленами. Погрешность интерполяционных формул, сходимость интерполяционного процесса. Интерполирование сплайнами. Локальные и нелокальные кубические сплайны.
  3. 2. Спектральные характеристики детерминированных переменных непрерывного типа.
  4. 2. Спектральные характеристики непрерывных детерминированных переменных.
  5. 60. Разностные схемы, оценки их точности и устойчивости для обыкновенных линейных дифференциальных уравнений
  6. § 1. Задача Коши для обыкновенных дифференциальных уравнений:
  7. 12. Некорректность задачи численного диф-я в пр-ве ℂ.
  8. 47. Оценка погрешности и сходимость одношаговых методов решения задачи Коши.
  9. 54. Сходимость сеточного метода решения краевых задач для обыкновенных диф. уравнений.
  10. 62. Сходимость сеточного метода решения краевой задачи для уравнения Пуассона.
  11. Вопросы
  12. 21. Сходимость СМ. Вырожденность в задачах ЛП.
  13. 24.Зацикливание. Задача ЛП в которой может произойти зацикливание.
  14. Численные методы решения начальной задачи (задачи Коши)
  15. Вырожденность
  16. 5. Решение задачи Коши на бесконечной прямой.
  17. 20. Задача Штурма - Лиувилля и ИУ Фредгольма.
  18. Несобственные интегралы. Сходимость интегралов. Критерии сходимости
- Аналитическая геометрия - Высшая математика - Высшая математика - Вычислительная математика - Вычислительные методы линейной алгебры - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комбинаторика - Комплексное исчисление - Линейная алгебра - Линейная алгебра и аналитическая геометрия - Линейное программирование - Математическая логика - Математическая статистика - Математическая физика - Математический анализ - Метод конечных элементов - Методы оптимизации - Обработка результатов измерений - Общая алгебра - Операционное исчисление - Основы математики - Планирование эксперимента - Пределы - Ряды - Теория вероятностей - Теория графов - Теория игр - Теория конечных автоматов - Теория массового обслуживания - Теория принятия решений - Теория случайных процессов - Теория чисел - Философия математики - Функциональный анализ - Элементарная математика -