Условие
Рассмотрим систему ограничений в канонической форме:
2x1 + 5x2 − x3 = 8,
x1 − 6x2 + x4 = 15,
−x1 + 2x2 + x5 = 11,
x1, x2, x3, x4, x5 ≥ 0.
а) Найдите хотя бы одно базисное допустимое решение системы.
б) Найдите все базисные допустимые решения системы.
Решение источника
а) Решение x = (0, 0, −8, 15, 11) является базисным и не является допустимым. Подойдёт, например, x = (4, 0, 0, 11, 15).
б) В источнике пункт не решён.
Редакционное объяснение
Почему не срабатывает очевидный базис. В первом уравнении x3 стоит с коэффициентом −1: это не остаток, а избыток неравенства 2x1 + 5x2 ≥ 8. Если положить x1 = x2 = 0, то x3 = −8 < 0. Точка (0, 0) на плоскости не удовлетворяет неравенству «больше», поэтому стартовую точку приходится искать отдельно (подбором, как в источнике, или через искусственные переменные). Решение источника (4, 0, 0, 11, 15) проверяется подстановкой: 8 − 0 = 8, 4 + 11 = 15, −4 + 15 = 11; базисные переменные x1, x4, x5.
Пункт «б»: полный перебор. Из пяти переменных выбираем три базисные — 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) | нет |
Ответ на пункт «б»: четыре базисных допустимых решения: (15, 0, 22, 0, 26), (4, 0, 0, 11, 15), (0, 11/2, 39/2, 48, 0), (0, 8/5, 0, 123/5, 39/5).
Геометрия. На плоскости (x1, x2) допустимое множество задаётся неравенствами 2x1 + 5x2 ≥ 8, x1 − 6x2 ≤ 15, −x1 + 2x2 ≤ 11, x1, x2 ≥ 0. Его вершины: (0; 8/5), (4; 0), (15; 0), (0; 11/2) — ровно четыре найденных решения. В отличие от задачи с +x3, множество неограничено: из вершины (15; 0) уходит луч вдоль прямой x1 − 6x2 = 15 (направление (6; 1)), а из вершины (0; 11/2) — луч вдоль прямой −x1 + 2x2 = 11 (направление (2; 1)). В полных переменных эти направления равны u = (6, 1, 17, 0, 4) и v = (2, 1, 9, 4, 0); подстановка в однородную систему даёт нули (12 + 5 − 17 = 0, 6 − 6 + 0 = 0, −6 + 2 + 4 = 0 и аналогично для v). Всё допустимое множество — сумма выпуклой оболочки четырёх вершин и конуса cone(u, v).
Типичные ошибки. По привычке брать в базис переменные, стоящие по одной в уравнении, и не замечать знак коэффициента; считать, что число вершин не зависит от знака одного коэффициента (сравните: с +x3 вершин три, с −x3 — четыре).
Что не следует из ответа
Неограниченность допустимого множества не означает, что любая задача линейного программирования на нём неограничена: цель, убывающая вдоль u и v (например, x1 + x2 → min), достигает оптимума в одной из четырёх вершин. И наоборот, четыре вершины не описывают всё множество: без направлений u и v описание неполно.
Борис Демешев · «Задачки по методам оптимальных решений», задача 3.4 «Базисные допустимые решения с избыточной переменной» · Исходное задание и решение · CC0 1.0. Адаптация: формулы переписаны без LaTeX; пункт «б», не решённый в источнике, решён редакцией; добавлены геометрическая интерпретация и направления неограниченности.