Условие
Исследуйте max(x₁+x₂) при x₁+x₂≤1, x₁+x₂≥2, x₁,x₂≥0. Решите графически и объясните результат первой фазы симплекс-метода.
Решение редакции
Обозначим s=x₁+x₂. Требования s≤1 и s≥2 несовместны. Геометрически одна полуплоскость находится ниже прямой x₁+x₂=1, другая — выше параллельной прямой x₁+x₂=2. Их пересечение пусто. У исходной задачи нет допустимого решения и нет максимума.
Для первой фазы запишем s+x₃=1 и s−x₄+y=2, где x₃,x₄,y≥0, а y — искусственная переменная. Вычтем первое равенство из второго: y=1+x₃+x₄. Поэтому минимально возможное значение искусственной цели равно 1. Оно достигается, например, при s=1, x₃=x₄=0, y=1. Поскольку y нельзя довести до нуля, искусственную переменную невозможно удалить с сохранением всех ограничений.
Это и есть диагностическое назначение первой фазы: проверить совместность ограничений до оптимизации исходной цели. Вторая фаза здесь не начинается. В графическом и алгебраическом решении причина одна — расстояние между двумя несовместными уровнями суммы.
Проверка
Умножим ограничение s≥2 на −1 и сложим с s≤1. Получится 0≤−1 — явный сертификат противоречия. В первой фазе нижняя оценка y≥1 достигается допустимой для вспомогательной системы точкой, значит минимум точно равен 1.
Что не следует из ответа
Пустая область не означает, что цель стремится к +∞. Для неограниченности нужна хотя бы одна допустимая точка и улучшающее направление. Нельзя объявлять ответ 0 по неотрицательности переменных: нулевой вектор нарушает второе ограничение.
Борис Демешев и участники · «Задачки по методам оптимальных решений», задание и исходное решение, строка 1118 · CC0 1.0. Адаптация damirock.com: написано самостоятельное графическое и двухфазное решение, добавлен сертификат несовместности.