Условие
Рассмотрите таблицу с равенствами x₁−x₃+3x₄=5, x₂−2x₃+7x₄=6 и строкой −3x₄=12−z для задачи min z. Все xᵢ≥0. Найдите все оптимумы и базисные оптимальные решения.
Решение источника
Источник правильно описывает луч x=(5+t,6+2t,t,0), t≥0, но перед этим пишет z=15. Это не согласуется со строкой таблицы 12−z.
Редакционное объяснение
Из целевой строки получаем z=12+3x₄. Следовательно, z≥12, а в оптимуме x₄=0. Тогда x₁=5+x₃, x₂=6+2x₃. Положив t=x₃≥0, получаем все оптимальные решения: (5+t,6+2t,t,0). Их значение равно 12.
Вектор A=(5,6,0,0) — единственный базисный оптимум. Для t>0 положительны три координаты при двух независимых равенствах, значит решение небазисное. Геометрическое представление: A+cone(u), u=(1,2,1,0). Направление u сохраняет правые части обоих равенств и имеет нулевую стоимость. Именно поэтому допустимо бесконечно удаляться от A, не меняя цель.
Полная допустимая параметризация шире: x₁=5+t−3s, x₂=6+2t−7s, x₃=t, x₄=s, где t,s≥0 и первые две координаты неотрицательны. Цель равна 12+3s, поэтому никакие точки с s>0 не входят в оптимальный луч.
Проверка
Точная подстановка t=0,1/2,2,20 подтверждает оба равенства и z=12. Алгебраическая проверка направления даёт 1−1=0 и 2−2=0. Значение 15 соответствовало бы x₄=1, что повышает цель и не является минимумом.
Что не следует из ответа
Нулевая стоимость x₃ не означает, что вся допустимая область оптимальна: x₄ имеет положительную стоимость. Не следует брать число из текстового ответа, если оно противоречит явно заданной строке цели.
Борис Демешев и участники · «Задачки по методам оптимальных решений», задание и исходное решение, строка 1263 · CC0 1.0. Адаптация damirock.com: исправлено значение 15 на 12, добавлены полная допустимая область и проверка нулевой стоимости луча.