Что такое базисные переменные

Что такое базисные переменные

В теме "Теорема Кронекера-Капелли" было указано, что если ранг расширеной матрицы системы $w >

Особый интерес представляет именно случай $
ang A=
angw >

Что означает фраза "ранг матрицы равен $r$"? Она означает, что есть хотя бы один минор $r$-го порядка, который не равен нулю. Напомню, что такой минор называется базисным. Базисных миноров может быть несколько. При этом все миноры, порядок которых выше $r$, равны нулю или не существуют.

Выбрать $r$ базисных переменных в общем случае можно различными способами. В примерах я покажу наиболее часто используемый способ выбора.

Во всех изложенных ниже примерах матрицу системы будем обозначать буквой $A$, а расширенную матрицу системы – буквой $widetilde$.

Решить СЛАУ $ left < egin& 3x_1-6x_2+9x_3+13x_4=9\ & -x_1+2x_2+x_3+x_4=-11;\ & x_1-2x_2+2x_3+3x_4=5. end
ight.$. Если система является неопределённой, указать базисное решение.

Итак, мы имеем СЛАУ, у которой 3 уравнения и 4 переменных: $x_1$, $x_2$, $x_3$, $x_4$. Так как количество переменных больше количества уравнений, то такая система не может иметь единственное решение (чуть позже мы строго докажем это предложение на основе теоремы Кронекера-Капелли). Найдём решения СЛАУ, используя метод Гаусса:

$$ left( egin 3 & -6 & 9 & 13 & 9 \ -1 & 2 & 1 & 1 & -11 \ 1 & -2 & 2 & 3 & 5 end
ight)
ightarrow left|egin & ext<поменяем местами первую и третью>\ & ext<строки, чтобы первым элементом>\ & ext <первой строки стала единица.>end
ight|
ightarrow \
ightarrowleft( egin
1 & -2 & 2 & 3 & 5\ -1 & 2 & 1 & 1 & -11 \ 3 & -6 & 9 & 13 & 9 end
ight) egin
phantom <0>\ II+I\ III-3cdot Iend
ightarrow left( egin
1 & -2 & 2 & 3 & 5\ 0 & 0 & 3 & 4 & -6 \ 0 & 0 & 3 & 4 & -6 end
ight) egin
phantom <0>\ phantom<0>\ III-IIend
ightarrow \
ightarrowleft( egin
1 & -2 & 2 & 3 & 5\ 0 & 0 & 3 & 4 & -6 \ 0 & 0 & 0 & 0 & 0 end
ight) $$

Мы завершили прямой ход метода Гаусса, приведя расширенную матрицу системы к ступенчатому виду. Слева от черты расположены элементы преобразованной матрицы системы, которую мы также привели к ступенчатому виду. Напомню, что если некая матрица приведена к ступенчатому виду, то её ранг равен количеству ненулевых строк.

И матрица системы, и расширенная матрица системы после эквивалентных преобразований приведены к ступенчатому виду; они содержат по две ненулевых строки. Вывод: $
ang A=
angw >

Итак, заданная СЛАУ содержит 4 переменных (обозначим их количество как $n$, т.е. $n=4$). Кроме того, ранги матрицы системы и расширенной матрицы системы равны между собой и равны числу $r=2$. Так как $r

Количество неизвестных $n=5$, ранги обеих матриц $r=3$, поэтому нужно выбрать три базисных переменных и $n-r=2$ свободных переменных. Применяя тот же метод "ступенек", что и в предыдущем примере, выберем в качестве базисных переменных $x_1$, $x_2$, $x_3$, а в качестве свободных переменных – $x_4$ и $x_5$.

Столбцы №4 и №5, которые соответствуют свободным переменным, перенесём за черту. После этого разделим третью строку на 8 и продолжим решение методом Гаусса:

$$ left( egin 1 & -2 & 4 & 0 & 0 & -2\ 0 & -1 & -1 & -2 & 4 & -7\ 0 & 0 & 8 & 5 & -10 & 26 end
ight) egin
phantom <0>\ phantom<0>\ III:8end
ightarrow left( egin
1 & -2 & 4 & 0 & 0 & -2\ 0 & -1 & -1 & -2 & 4 & -7\ 0 & 0 & 1 & 5/8 & -5/4 & 13/4 end
ight) egin
I-4cdot III \ II+III\ phantom<0>end
ightarrow \ left( egin
1 & -2 & 0 & -5/2 & 5 & -15\ 0 & -1 & 0 & -11/8 & 11/4 & -15/4\ 0 & 0 & 1 & 5/8 & -5/4 & 13/4 end
ight) egin
phantom <0>\ IIcdot (-1)\ phantom<0>end
ightarrow left( egin
1 & -2 & 0 & -5/2 & 5 & -15\ 0 & 1 & 0 & 11/8 & -11/4 & 15/4\ 0 & 0 & 1 & 5/8 & -5/4 & 13/4 end
ight) egin
I+2cdot II \ phantom<0>\ phantom<0>end
ightarrow\
ightarrowleft( egin
1 & 0 & 0 & 1/4 & -1/2 & -15/2\ 0 & 1 & 0 & 11/8 & -11/4 & 15/4\ 0 & 0 & 1 & 5/8 & -5/4 & 13/4 end
ight) $$

Читайте также:  Corsair obsidian series 250d

Продолжение этой темы рассмотрим во второй части, где разберём ещё два примера с нахождением общего решения.

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

Для неопределенных систем, имеющих множество решений, неизвестные разделяются па две части: базисные и свободные.

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

Пример 14.1. Пусть система ограничений ЗЛП имеет вид:

Пара неизвестных (xj, Х2) не является базисной, так как соответству-

ющая матрица имеет ранг 1, ее определитель равен нулю. Пара

неизвестных (хз, х4) является базисной, соответствующая матрица

имеет ранг 2. Из данной системы базисные неизвестные (Х3, х4) можно выразить через свободные неизвестные (х4, х2): Х3 = 4 — Х — 2х2, х4 = = 5 — Зх! — 6х2. Все решения системы можно получить, придавая свободным неизвестным произвольные значения. В частности, при Xj = 0, х2 = 0 имеем Хз = 4, х4 = 5. Полученное решение (0, 0, 4, 5) будет неотрицательным. Легко проверить, что базисными являются также все оставшиеся пары неизвестных: (xlt Х3), (ху, х4), (х2, х3), (х2, х4).

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

Опорным (базисным) планом (опорным решением) ЗЛП называется неотрицательное решение системы ограничений ЗЛП, составленное из значений набора базисных неизвестных при пулевых значениях соответствующих свободных неизвестных. В приведенном выше примере решение (0, 0, 4, 5) является опорным планом.

Пролог

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

Читайте также:  Как получить доступ к сетевому диску

Замечание. Пост будет написан достаточно формальным языком, но будет снабжен комментариями, которые должны внести некоторую ясность. Такой формат позволит сохранить научный подход и при этом, возможно, поможет некоторым в изучении данного вопроса.

§1. Постановка задачи линейного программирования

Определение: Линейное программирование – математическая дисциплина, посвященная теории и методам решения экстремальных задач на множествах n- мерного пространства, задаваемых системами линейными уравнений и неравенств.

Общая задача линейного программирования (далее – ЛП) имеет вид:

§2. Каноническая форма задачи ЛП

Каноническая форма задачи ЛП:

Замечание: Любая задача ЛП сводится к канонической.

Алгоритм перехода от произвольной задачи ЛП к канонической форме:

  1. Неравенства с отрицательными $inline$b_i$inline$ умножаем на (-1).
  2. Если неравенство вида (≤), то к левой части добавляем $inline$s_i$inline$ – добавочную переменную, и получаем равенство.
  3. Если неравенство вида (≥), то из левой части вычитаем $inline$s_i$inline$ , и получаем равенство.
  4. Делаем замену переменных:

  • Если $inline$x_i ≤ 0$inline$ , то $inline$x_i’= -x_i ≥ 0$inline$
  • Если $inline$x_i$inline$ — любой, то $inline$x_i= x_i’ — x_i»$inline$ , где $inline$x_i’, x_i»≥ 0$inline$

Замечание: Будем нумеровать $inline$s_i$inline$ по номеру неравенства, в которое мы его добавили.

Замечание: $inline$s_i$inline$ ≥0.

§3. Угловые точки. Базисные/свободные переменные. Базисные решения

Определение: Точка $inline$Х ∈ D$inline$ называется угловой точкой, если представление $inline$ Х= αХ^1+ (1-α) Х^2,где Х^1,Х^2 ∈D;0 возможно только при $inline$Х^1=Х^2 $inline$ .

Иными словами, невозможно найти две точки в области, интервал проходящий через которые содержит $inline$Х$inline$ (т.е. $inline$Х$inline$ – не внутренняя точка).

Графический способ решения задачи ЛП показывает, что нахождение оптимального решения ассоциируется с угловой точкой. Это является основной концепцией при разработке симплекс-метода.

Определение: Пусть есть система m уравнений и n неизвестных (m $inline$(..0100..)^T, (..010..)^T,(..0010..)^T. $inline$ , т.е. только одна координата вектора ненулевая и равна 1.

Замечание: Базисный вектор имеет размерность (m*1), где m – количество уравнений в системе ограничений.

Для удобства вычислений и наглядности обычно пользуются симплекс-таблицами:

  • В первой строке указывают «наименование» всех переменных.
  • В первом столбце указывают номера базисных переменных, а в последней ячейке – букву Z (это строка функционала).
  • В «середине таблицы» указывают коэффициенты матрицы ограничений — aij.
  • Последний столбец – вектор правых частей соответствующих уравнений системы ограничений.
  • Крайняя правая ячейка – значение целевой функции. На первой итерации ее полагают равной 0.

Замечание: Базис – переменные, коэффициенты в матрице ограничений при которых образуют базисные вектора.

Замечание: Если ограничения в исходной задаче представлены неравенствами вида ≤, то при приведении задачи к канонической форме, введенные дополнительные переменные образуют начальное базисное решение.

Замечание: Коэффициенты в строке функционала берутся со знаком “-”.

1. Выбираем переменную, которую будем вводить в базис. Это делается в соответствии с указанным ранее принципом: мы должны выбрать переменную, возрастание которой приведет к росту функционала. Выбор происходит по следующему правилу:

  • Если задача на минимум – выбираем максимальный положительный элемент в последней строке.
  • Если задача на максимум – выбираем минимальный отрицательный.

Такой выбор, действительно, соответствует упомянутому выше принципу: если задача на минимум, то чем большее число вычитаем – тем быстрее убывает функционал; для максимума наоборот – чем большее число добавляем, тем быстрее функционал растет.

Замечание: Хотя мы и берем минимальное отрицательное число в задаче на максимум, этот коэффициент показывает направление роста функционала, т.к. строка функционала в симплекс-таблице взята со знаком “-”. Аналогичная ситуация с минимизацией.

Читайте также:  Getting ready windows 10 зависло что делать

Определение: Столбец симплекс-таблицы, отвечающий выбранному коэффициенту, называется ведущим столбцом.

2. Выбираем переменную, которую будем вводить в базис. Для этого нужно определить, какая из базисных переменных быстрее всего обратится в нуль при росте новой базисной переменной. Алгебраически это делается так:

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

Определение: Такая строка называется ведущей строкой и отвечает переменной, которую нужно вывести из базиса.

Замечание: Фактически, мы выражаем старые базисные переменные из каждого уравнения системы ограничений через остальные переменные и смотрим, в каком уравнении возрастание новой базисной переменной быстрее всего даст 0. Попадание в такую ситуацию означает, что мы «наткнулись» на новую вершину. Именно поэтому нулевые и отрицательные элементы не рассматриваются, т.к. получение такого результата означает, что выбор такой новой базисной переменной будет уводить нас из области, вне которой решений не существует.

3. Ищем элемент, стоящий на пересечении ведущих строки и столбца.

Определение: Такой элемент называется ведущим элементом.

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

5. Далее начинается процесс вычисления нового базисного решения. Он происходит с помощью метода Жордана-Гаусса.

  • Новая Ведущая строка = Старая ведущая строка / Ведущий элемент
  • Новая строка = Новая строка – Коэффициент строки в ведущем столбце * Новая Ведущая строка

Замечание: Преобразование такого вида направлено на введение выбранной переменной в базис, т.е. представление ведущего столбца в виде базисного вектора.

6. После этого проверяем условие оптимальности. Если полученное решение неоптимально – повторяем весь процесс снова.

§5. Интерпретация результата работы симплекс-метода

Условие оптимальности полученного решения:

  • Если задача на максимум – в строке функционала нет отрицательных коэффициентов (т.е. при любом изменении переменных значение итогового функционала расти не будет).
  • Если задача на минимум – в строке функционала нет положительных коэффициентов (т.е. при любом изменении переменных значение итогового функционала уменьшаться не будет).

2. Неограниченность функционала

Однако, стоит отметить, что заданный функционал может не и достигать максимума/минимума в заданной области. Алгебраический признак этого можно сформулировать следующим образом:

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

Фактически, это значит, что какой бы рост мы не задавали новой базисной переменной, мы никогда не найдем новую вершину. А значит, наша функция не ограничена на множестве допустимых решений.

3. Альтернативные решения

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

Алгебраический признак существования альтернативы:

После достижения оптимального решения имеются нулевые коэффициенты при свободных переменных в строке функционала.

Это значит, что при росте соответствующей переменной с нулевым коэффициентом значение функционала не изменится и новое базисное решение будет также давать оптимум функционала.

Эпилог

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

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

Ссылка на основную публикацию
Adblock detector