Инструменты пользователя

Инструменты сайта


examination:mo:question4

Вопрос №4. Диагональная форма. Базисные решения. Симплексная таблица.

Диагональная форма

Квадратная матрица <m> D = (d_ij) </m>, где <m> d_ij = 0 </m> для всяких i != j, называется диагональной матрицей. Такая матрица является одновременно и верхнетреугольной и нижнетреугольной:

<m>D = (matrix{4}{4}{{d_11} {0} {…} {0} {0} {d_22} {…} {0} {…} {…} {…} {…} {0} {0} {0} {d_nn}})</m>

  • Диагональная матрица является симметричной
  • Ранг диагональной матрицы равен количеству ненулевых элементов, находящихся на главной диагонали.
  • Определитель диагональной матрицы равен произведению диагональных элементов

Для недоопределенной системы: Пусть есть недоопределенная система: Ax=b, x∈En, b∈Em Аmn, m<n

Тогда матрицу А можно представить в виде двух блоков:

Это равенство можно преобразовать домножив обе части на матрицу обратную В. Получим диагональную форму для недоопределенной системы:

Здесь I - единичная матрица.

Понятие базисного решения СЛУ.

Говорят, что решение X = (x1,…,xn) СЛУ базисное, если оно зависит от такого множества индексов S, что векторы - образуют столбцовый базис матрицы A.

Базисное решение — одно из допустимых решений, находящихся в вершинах области допустимых решений. Оно является решением системы линейных ограничений, которое нельзя представить в виде линейной комбинации никаких других решений.

При решении задачи линейного программирования можно поступить следующим образом: найти любое из таких “вершинных” решений — не обязательно оптимальное — и принять его за исходный пункт расчетов. Такое решение и будет базисным. Если оно окажется оптимальным, расчет на этом закончен, если нет — последовательно проверяют, не будут ли оптимальными соседние вершинные точки: ту из них, в которой план эффективнее, принимают снова за исходную точку; и так, последовательно проверяя на оптимальность аналогичные вершины, приходят к искомому оптимуму. На этом принципе строятся т. н. симплексный метод решения задач линейного программирования, а также ряд других способов, объединенных общим названием “методы последовательного улучшения допустимого решения (МПУ)”: метод обратной матрицы, или модифицированный симплекс-метод, метод потенциалов для транспортной задачи и др. Они отличаются друг от друга вычислительными особенностями перехода от одного базисного решения к другому, улучшенному.

Понятие допустимого базисного решения

Говорят, что решение X = (x1,…,xn) СЛУ является базисным допустимым, если оно базисное для СЛУ и X ≥0, т.е. оно базисное и допустимое для задачи ЛП в канонической форме.

Симплексная таблица

  • БН - базисные переменные
  • НП - небазисные переменные
  • Св.ч - свободные члены
  • F - искомая функция

Коэффициенты функции цели при ее максимизации заносятся в нижнюю строку симплекс-таблицы с противоположными знаками. Свободные члены в симплекс-таблице определяют решение задачи.

Симплексная таблица - матрица, служащая средством перебора допустимых базисных решений задачи линейного программирования при ее решении симплексным методом. Образуется из матрицы коэффициентов системы уравнений линейного программирования; последовательное ее преобразование по т. н. симплексному алгоритму позволяет за ограниченное количество шагов (итераций) получать искомый результат — план, обеспечивающий экстремальное значение целевой функции.

examination/mo/question4.txt · Последние изменения: 2014/01/15 12:19 (внешнее изменение)