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