Условие
Рассмотрим систему уравнений
2x1 + 3x2 + x3 = 8,
x1 − x2 + x4 = 9.
Даны векторы xa = (0, 0, 0, 0), xb = (0, 0, 8, 9), xc = (1, 0, 6, 8), xd = (1, −9, 33, −1), xe = (0, −9, 35, 0).
а) Какие векторы являются решениями системы?
б) Какие векторы являются базисными решениями системы?
в) Какие векторы являются допустимыми решениями при условии, что все xi ≥ 0?
Определения из задачника: решение x системы Ax = b называется допустимым, если все xi ≥ 0, и базисным, если столбцы матрицы A, соответствующие ненулевым xi, линейно независимы.
Решение источника
| вектор | решение | базисное решение | допустимое решение |
|---|---|---|---|
| xa = (0, 0, 0, 0) | нет | нет | нет |
| xb = (0, 0, 8, 9) | да | да | да |
| xc = (1, 0, 6, 8) | да | нет | да |
| xd = (1, −9, 33, −1) | да | нет | нет |
| xe = (0, −9, 35, 0) | да | да | нет |
Редакционное объяснение
Решения. Подставляем векторы в оба уравнения. Для xa левая часть первого уравнения равна 0 ≠ 8 — это не решение. Остальные четыре вектора подходят:
- xb: 0 + 0 + 8 = 8, 0 − 0 + 9 = 9;
- xc: 2 + 0 + 6 = 8, 1 − 0 + 8 = 9;
- xd: 2 − 27 + 33 = 8, 1 + 9 − 1 = 9;
- xe: 0 − 27 + 35 = 8, 0 + 9 + 0 = 9.
Базисность. Столбцы матрицы — векторы на плоскости: (2, 1), (3, −1), (1, 0), (0, 1). Ранг матрицы равен 2, поэтому у базисного решения не больше двух ненулевых компонент: любые три вектора на плоскости линейно зависимы.
- xb: ненулевые x3, x4, столбцы (1, 0) и (0, 1) независимы — базисное.
- xc: три ненулевые компоненты — не базисное.
- xd: четыре ненулевые компоненты — не базисное.
- xe: ненулевые x2, x3, столбцы (3, −1) и (1, 0), определитель 3·0 − 1·(−1) = 1 ≠ 0 — базисное.
Допустимость. Среди решений неотрицательны только xb и xc; у xd и xe есть отрицательные компоненты. Таблица источника полностью подтверждается.
Все базисные решения системы. Базис — это пара переменных с линейно независимыми столбцами; остальные две переменные приравниваются к нулю. Все шесть пар здесь дают невырожденные подсистемы:
| базисные переменные | решение | допустимое? |
|---|---|---|
| x1, x2 | (7, −2, 0, 0) | нет |
| x1, x3 | (9, 0, −10, 0) | нет |
| x1, x4 | (4, 0, 0, 5) | да |
| x2, x3 | (0, −9, 35, 0) = xe | нет |
| x2, x4 | (0, 8/3, 0, 35/3) | да |
| x3, x4 | (0, 0, 8, 9) = xb | да |
Три допустимых базисных решения — это вершины многогранника допустимых решений. Допустимый, но небазисный вектор xc лежит на ребре между двумя вершинами: xc = 0,75·(0, 0, 8, 9) + 0,25·(4, 0, 0, 5) = (1, 0, 6, 8). Это хорошая проверка: допустимое решение ограниченного многогранника всегда выражается выпуклой комбинацией вершин.
Типичные ошибки. Считать базисным любое решение с нулями (важна линейная независимость столбцов при ненулевых компонентах, а не наличие нулей); считать xe небазисным из-за отрицательной компоненты — базисность и допустимость проверяются независимо.
Что не следует из ответа
Из того, что вектор допустим, не следует, что он является вершиной: xc допустим, но лежит внутри ребра. И наоборот, базисное решение не обязано быть допустимым — как xe. В симплекс-методе перебираются только решения, обладающие обоими свойствами одновременно.
Борис Демешев · «Задачки по методам оптимальных решений», задача 3.1 «Решения, базисные и допустимые решения» · Исходное задание и решение · CC0 1.0. Адаптация: формулы переписаны без LaTeX; таблица источника сохранена; добавлены проверка каждого вектора, перечень всех базисных решений и разложение xc по вершинам.