Условие
Рассмотрим систему ограничений в канонической форме:
2x1 + 5x2 + x3 = 8,
x1 − 6x2 + x4 = 15,
−x1 + 2x2 + x5 = 11,
x1, x2, x3, x4, x5 ≥ 0.
а) Найдите хотя бы одно базисное допустимое решение системы.
б) Найдите все базисные допустимые решения системы.
Решение источника
а) x = (0, 0, 8, 15, 11).
б) В источнике пункт не решён.
Редакционное объяснение
Пункт «а». Переменные x3, x4, x5 входят каждая в своё уравнение с коэффициентом 1, а правые части неотрицательны. Поэтому их можно сделать базисными, положив x1 = x2 = 0: получаем решение источника (0, 0, 8, 15, 11). Это стандартная стартовая точка симплекс-метода.
Пункт «б»: перебор базисов. Уравнений три, переменных пять, так что базис состоит из трёх переменных, а две остальные равны нулю. Всего C(5, 3) = 10 кандидатов, и все десять подсистем здесь невырождены:
| базис | базисное решение | допустимое? |
|---|---|---|
| x1, x2, x3 | (−24, −13/2, 177/2, 0, 0) | нет |
| x1, x2, x4 | (−13/3, 10/3, 0, 118/3, 0) | нет |
| x1, x2, x5 | (123/17, −22/17, 0, 0, 354/17) | нет |
| x1, x3, x4 | (−11, 0, 30, 26, 0) | нет |
| x1, x3, x5 | (15, 0, −22, 0, 26) | нет |
| x1, x4, x5 | (4, 0, 0, 11, 15) | да |
| x2, x3, x4 | (0, 11/2, −39/2, 48, 0) | нет |
| x2, x3, x5 | (0, −5/2, 41/2, 0, 16) | нет |
| x2, x4, x5 | (0, 8/5, 0, 123/5, 39/5) | да |
| x3, x4, x5 | (0, 0, 8, 15, 11) | да |
Ответ на пункт «б»: базисных допустимых решений ровно три: (0, 0, 8, 15, 11), (4, 0, 0, 11, 15) и (0, 8/5, 0, 123/5, 39/5).
Как прийти к ответу без полного перебора. Переменные x3, x4, x5 — остатки неравенств 2x1 + 5x2 ≤ 8, x1 − 6x2 ≤ 15, −x1 + 2x2 ≤ 11 на плоскости (x1, x2). Из первого неравенства и неотрицательности следует x1 ≤ 4 и x2 ≤ 8/5. Тогда x1 − 6x2 ≤ 4 < 15 и −x1 + 2x2 ≤ 16/5 < 11, то есть второе и третье ограничения выполняются автоматически и никогда не обращаются в равенство. Допустимое множество — треугольник с вершинами (0; 0), (4; 0), (0; 8/5), и каждая вершина даёт одно базисное допустимое решение; в нём x4 и x5 всегда положительны и потому всегда базисные.
Проверка. Для (0, 8/5, 0, 123/5, 39/5): 5·8/5 = 8; −6·8/5 + 123/5 = 75/5 = 15; 2·8/5 + 39/5 = 55/5 = 11. Для (4, 0, 0, 11, 15): 8 = 8; 4 + 11 = 15; −4 + 15 = 11. Весь перебор десяти базисов выполнен в точной рациональной арифметике.
Типичная ошибка. При переборе забывать проверять знаки всех трёх базисных переменных: например, базис x1, x3, x5 даёт положительные x1 = 15 и x5 = 26, но x3 = −22.
Что не следует из ответа
Из того, что в системе три ограничения, не следует, что все они формируют допустимое множество: здесь два из них избыточны. Число базисов C(5, 3) = 10 — лишь верхняя граница для числа вершин; фактических вершин может быть гораздо меньше. Сравните с соседней задачей, где в первом уравнении стоит −x3: там множество становится неограниченным, а вершин — четыре.
Борис Демешев · «Задачки по методам оптимальных решений», задача 3.3 «Базисные допустимые решения в канонической форме» · Исходное задание и решение · CC0 1.0. Адаптация: формулы переписаны без LaTeX; пункт «б», не решённый в источнике, решён редакцией полным перебором базисов и геометрически.