Условие
Решите max(x₁+x₂) при x₁+x₂≤1, x₁≥x₂, x₁,x₂≥0. Найдите каноническую форму, все базисные допустимые решения и все оптимальные точки.
Решение источника
Источник называет оптимальным отрезок между A=(1/2,1/2) и B=(1,0), со значением 1. В одном из полных векторов для B запас записан как ноль, хотя второе равенство требует единицу.
Редакционное объяснение
Допустимая область — треугольник O=(0,0), A=(1/2,1/2), B=(1,0). Ограничение сразу даёт z≤1. На ребре AB сумма равна 1, значит весь отрезок оптимален: (x₁,x₂)=(t,1−t), 1/2≤t≤1.
С запасом x₃ и избыточной переменной x₄ каноническая система равна x₁+x₂+x₃=1, x₁−x₂−x₄=0. Три различных базисных допустимых вектора: O′=(0,0,1,0), A′=(1/2,1/2,0,0), B′=(1,0,0,1). Все оптимальные векторы — (t,1−t,0,2t−1). Только концы этого отрезка базисные; внутренние точки остаются оптимальными, но имеют три положительные координаты.
Из A можно двигаться по ребру, увеличивая x₄: x₁=(1+x₄)/2, x₂=(1−x₄)/2, 0≤x₄≤1. Цель при этом не меняется. При x₄=1 достигается B. Так нулевая приведённая стоимость объясняет альтернативный оптимум через допустимый симплекс-переход.
Проверка
Для B′ второе равенство даёт 1−0−1=0. Вектор (1,0,0,0) его нарушает. Точный перебор базисов даёт O′, A′, B′; значения цели 0,1,1.
Что не следует из ответа
Один найденный оптимальный базис не исчерпывает ответ «все оптимальные решения». Нулевая приведённая стоимость сама по себе ещё не гарантирует новую точку: нужно проверить допустимое движение. В этой задаче движение существует.
Борис Демешев и участники · «Задачки по методам оптимальных решений», задание и исходное решение, строка 1184 · CC0 1.0. Адаптация damirock.com: добавлены все базисные векторы и параметризация, исправлена избыточная переменная в конечной точке.