Условие
Минимизируйте x₁−x₂ при x₁+x₂≥1, x₁≥x₂ и x₁,x₂≥0. Запишите каноническую форму, все оптимальные точки, базисный оптимум и представление через вершину и конус.
Решение редакции
Из x₁≥x₂ следует z=x₁−x₂≥0. Равенство достигается при x₁=x₂=t, если 2t≥1. Поэтому z*=0, а все оптимальные точки — (t,t), t≥1/2. Это луч с началом A=(1/2,1/2).
Канонические равенства: x₁+x₂−x₃=1, x₁−x₂−x₄=0, все четыре переменные неотрицательны. Цель здесь просто x₄. В оптимуме x₄=0; первый запас равен x₃=2t−1. Полный ответ: (t,t,2t−1,0), t≥1/2, или A′+r·u, где A′=(1/2,1/2,0,0), u=(1,1,2,0), r≥0.
Единственное базисное оптимальное решение — A′. При r>0 положительны x₁,x₂,x₃; их три столбца в системе ранга 2 не могут быть линейно независимыми. Среди базисных допустимых точек есть также (1,0,0,1), но её цель равна 1, поэтому она не оптимальна. Начало луча одновременно является геометрической вершиной.
Проверка
Для A′ оба равенства выполняются, а для u их левые части равны нулю. Значит, A′+ru допустим для всех r≥0. Цель на этом луче равна 0. Нижняя оценка z≥0 доказывает глобальную оптимальность независимо от вычислительного метода.
Что не следует из ответа
Неограниченность допустимого множества или множества оптимумов не означает, что значение задачи бесконечно. Вдоль этого луча целевая функция постоянна. Нельзя искать «наибольшее t»: при минимизации оно не требуется.
Борис Демешев и участники · «Задачки по методам оптимальных решений», задание и исходное решение, строка 1235 · CC0 1.0. Адаптация damirock.com: самостоятельно получены все оптимумы, полный канонический луч и различие между ограниченностью области и значения.