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

Определение. Системой линейных уравнений называют систему следующего вида. Ранг матрицы определяется через миноры r = – 5.

Решение системы уравнений. Решаем относительно переменных x и y, полагаем z = 1. Получаем единственное решение х = –2/5, y = 3/5, z =1. Все другие решения получаются из этого линейно-независимого фундаментального решения: х = –2k/5; y = 3k/5; z = k или х = 2k , y = 3k, z = 5k. Подобные системы возникают при описании ограничений ЗЛП. Существенную роль при решении ЗЛП играют определители подобных систем (Δ = 0, Δ ≠ 0). При однородной системе определитель должен быть равен нулю.
Определение. Симплекс – выпуклый многоугольник в n-мерном пространстве с n + 1 вершинами, не лежащими в одной гиперплоскости. Симплексы выделены в отдельный класс потому, что в n-мерном пространстве n точек всегда лежат в одной гиперплоскости. Другими словами, симплекс – это простейший многоугольник, содержащий некоторый объем n-мерного пространства. В обычном (трехмерном) пространстве симплекс – это тетраэдр; трехмерный объем совпадает с объемом тела. На плоскости симплекс – это треугольник, двумерный объем – площадь; на прямой – симплекс – отрезок, объем – длина отрезка.
Определение. Гиперпространство, гиперплоскость. Гиперпространство многомерного (n-мерного) пространства – это его подпространство размерности (n – 1). Главное свойство гиперпространства – то, что оно «самое большое» подпространство. Иначе говоря, если к базису выбранного гиперпространства добавить еще один линейно независимый вектор, то можно получить базис всего пространства.
Например, для трехмерного пространства гиперпространством является плоскость (любая), проходящая через начало координат. Для двумерного пространства – гиперпространство – это прямая линия, проходящая через нуль.
Гиперплоскость в n-мерном пространстве обобщает наши представления о роли прямой на плоскости и плоскости в пространстве. Например, в n-мерном пространстве через любые n точек можно провести единственную гиперплоскость (как в трехмерном через три точки общего положения, т.е. не лежащие на одной прямой).
Гиперплоскость определяется линейной формой: а₁х₁ + а₂х₂ + … + а_nx_n = k, где коэффициенты (а₁, а₂, …, а_n) представляют собой координаты вектора А.
Гиперплоскость делит пространство (соответствующей размерности) на два полупространства. Все точки каждого из них определяются неравенствами. Например, в случае прямой линии на плоскости: а₁х₁ + а₂х₂ ≥_Z, или а₁х₁ + а₂х₂ >Z _, а₁х₁ + а₂х₂ <_Z а₁х₁ + а₂х₂ ≤_Z. Эти два варианта различаются тем, к какой полуплоскости мы относим разделяющую прямую.