«Анализ и проектирование алгоритма симплекс-метода для решения задач линейного программирования.»

Матрица и её ранг. Система mn чисел, расположенных в форме прямоугольной таблицы из m строк и n столбцов, называется матрицей.
Определение. Рангом матрицы [A] называется наибольший порядок, который могут иметь её миноры, не обращающиеся в нуль. Для определения ранга матрицы следует рассмотреть все её миноры порядка р (где р – меньшее из чисел m, n, если m ≠ n или р = m = n); если хотя бы один из них ≠ 0, то ранг [A] равен р; если же все они равны (= 0), то следует рассмотреть все миноры порядка р – 1 и т. д. Практически поступают наоборот: переходят от миноров меньшего порядка к минорам большего порядка, в соответствии со следующим правилом. Если найден минор k-го порядка D_k, отличный от нуля, то остается вычислить только те миноры (k + 1) -го порядка, которые представляют собой «окаймление» D_k, например,
Определение. Минором k-го порядка матрицы [A] (k ≤ m, k ≤ n) называется определитель D, составленный (с сохранением порядка) из k² элементов матрицы, лежащих на пересечении некоторых её k столбцов и k строк См. схему выше минор D из 3-х строк и 3-х столбцов. Обозначается матрица символами:
Матрица А и ее миноры с различным окаймлением
Приведем пример вычисления ранга матрицы.

С выполнением каждого шага связаны процедуры:
1. Получение опорного плана; 2. устанавливается, является ли данный опорный план оптимальным; 3. если нет, то существует ли оптимальный план вообще, или задача является неограниченной; 4. если оптимальный план существует, то, как перейти на следующем шаге, к новому опорному плану с меньшим значением ЦФ.
Алгоритм СМ применяется к ЗЛП после её приведения к канонической форме, т.е. отыскивается минимум целевой функции min Q(X) на множестве векторов Х.

Система ограничений совместна r_A = r_B  и detA ≠ 0 невырожденная, т.е. ранг r =m матрицы A_{[m, n]} и расширенной матрицы системы равен m. Имеется множество решений. Для решения системы произвольным (n - m) переменным могут быть приданы любые, в частности, нулевые значения. Эти переменные называются свободными. Обычно их индексируют x_e, e =(m+1)(1)n. Остальные переменные (их называют базисными), однозначно определяются из решения системы

(здесь x_e, e =(m+1)(1)n). Матрица этой системы неособенная и, следовательно, система имеет единственное решение x_j , j =1(1)m.
Исходный опорный план ЗЛП – вектор, содержащий значения всех переменных задачи как базисных, так и свободных, т.е. этот вектор Х, удовлетворяет ограничениям, но не обеспечивает, как правило, экстремума ЦФ. Общее число опорных планов очевидно равно числу сочетаний из n по m. Оптимальный план можно выявить, перебрав их все. Такой путь громоздок и неприемлем уже при n, m ≈ 10 ÷15.
Алгоритм СМ тоже перебирает опорные планы, но не все, а направленно, т.е. на каждом шаге ЦФ уменьшается. Число шагов имеет тот же порядок, что и число уравнений в ограничениях.
Приведем пояснения некоторым понятиям и терминам, широко используемым в алгоритме решения задач линейного программирования симплексным методом и тесно связанными с ним методами.