[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4] [5]

Базисные решения

Задача

Решить систему уравнений x1 - x2 - 2x3 + x4 = 0, 2 x1 + x2 + 2 x3 - x4 = 2. Решение. В задаче 2.1 установлено, что основными могут быть переменные x1, x2; x1, x3; x1,x4. Возьмем в качестве основных переменные x1, x2, а переменные x3, x4 будем считать неосновными и перенесем их с соответствующими коэффициентами в правые части уравнений системы. Получим x1 - x2 = 2x3 - x4 2 x1 + x2 = -2x3 + x4 + 2 Решая данную систему любым способом, найдем x1 = 2/3; x2 = 2/3 - 2x3 + x4. Задавая неосновным переменным x3 и x4 произвольные значения, например, x3 = с1, x4 = с2 получим бесконечное множество решений этой системы x1 = 2/3; x2 = 2/3 - 2с1 + с2; x3= с1; x4 = c2)

Определение
Решение Х= (x1, x2, ..., xn) системы (2.1) называется допустимым (Именно такие решения представляют интерес в большинстве задач линейного программирования), если оно содержит лишь неотрицательные компоненты, т.е. xj>= 0 для любых j = 1, 2, ..., n.
В противном случае решение называется недопустимым.

Так, в задаче 2.2 решение системы при с₁ = 2, с₂ = 5, т.е. Х₁ = (2/3; 5/3; 2; 5) является допустимым, а при c₁ = 2, с₂ =1, т.е. X₂ = (2/3; - 7/3; 2; 1) - недопустимым.
Среди бесконечного множества решений системы выделяют так называемые базисные решения.

Определение
Базисным решением системы m линейных уравнений с n переменными называется решение, в котором все n - m неосновных переменных равны нулю.

В задачах линейного программирования особый интерес представляют допустимые базисные решения, или, как их еще называют, опорные планы. Число базисных решений является конечным, так как оно равно числу групп основных переменных, не превосходящему С_n^m.

Определение
Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным.

Задача 2.3.

Найти все базисные решения системы, приведенной в задаче 2.1. Решение. В задаче 2.1 было установлено, что существует три группы основных переменных x1, x2; x1, x3; x1,x4, т.е. число базисных решений равно 3. Найдем первое базисное решение, взяв в качестве основных переменные x1, x2 и неосновных - переменные x3,x4 Приравняв неосновные переменные нулю, т.е. при x3 = x4 = 0, получим систему уравнений в виде x1 - x2 = 0, 2x1 + x2 = 2, откуда x1 = 2/3; x2 = 2/3. Следовательно, первое базисное решение системы Х1 = (2/3; 2/3; 0; 0) - допустимое. Если взять за основные переменные x1, x3 и приравнять нулю соответствующие неосновные переменные x2 = x4 = 0, получим второе базисное решение Х2 = (2/3; 0; 2/3; 0) - также допустимое. Аналогично можно найти и третье базисное решение Xз = (2/3; 0; 0; - 2/3) - недопустимое.

Совместная система (2.1) имеет бесконечно много решений, из них базисных решений - конечное число, не превосходящее С_n^m.

[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4] [5] [В начало страницы]