Условие
Даны равенства x₁−x₃+3x₄=5, x₂+3x₃+7x₄=6 и строка −3x₄=16+z для max z. Все xᵢ≥0. Найдите все оптимальные решения.
Решение источника
Источник верно называет z*=−16 и концы A=(5,6,0,0), B=(7,0,2,0), но в параметризации пишет x₂=6−x₃. Вторая строка таблицы требует коэффициент 3.
Редакционное объяснение
Цель равна z=−16−3x₄. При x₄≥0 она не превосходит −16. Для оптимума нужно x₄=0. Из двух равенств получаем x₁=5+t, x₂=6−3t, x₃=t. Неотрицательность x₂ ограничивает t сверху: 0≤t≤2.
Все оптимумы: (5+t,6−3t,t,0), 0≤t≤2. В форме выпуклой оболочки это (1−t/2)A+(t/2)B. При t=0 и t=2 получаются два базисных оптимальных решения; при 0<t<2 — внутренние небазисные точки. Конуса ненулевых оптимальных направлений здесь нет: увеличение t останавливается, когда обнуляется x₂.
Вся допустимая область задаётся t,s≥0, x₁=5+t−3s, x₂=6−3t−7s, x₃=t, x₄=s. Из 3t+7s≤6 следует ограниченность обоих параметров. Поэтому этот пример полезен для сравнения с задачами, где нулевая приведённая стоимость порождает целый луч.
Проверка
При t=1 исправленный вектор равен (6,3,1,0): 3+3·1=6. Ошибочная формула даёт (6,5,1,0) и левую часть 8. При t=2 получаем B, а при t=0 — A; обе точки имеют цель −16.
Что не следует из ответа
Коэффициент 3 нельзя восстановить из названия переменной или предполагаемой симметрии. Его задаёт строка ограничения. Наличие двух оптимальных вершин гарантирует оптимальность отрезка между ними, но не допускает продолжить этот отрезок за границы неотрицательности.
Борис Демешев и участники · «Задачки по методам оптимальных решений», задание и исходное решение, строка 1308 · CC0 1.0. Адаптация damirock.com: исправлен x₂=6−t на x₂=6−3t, добавлены все параметры и сравнение отрезка с лучом.