Условие
Минимизируйте z=x₁−2x₂+3x₃ при 3x₁+2x₂+x₃≤10, x₁+x₂−x₃≤5, x₁,x₂,x₃≥0. Найдите каноническую форму и решение симплекс-методом.
Решение источника
Источник вводит x₂ и получает вектор (0,5,0,0,0), z=−10.
Редакционное объяснение
Равенства с запасами: 3x₁+2x₂+x₃+x₄=10, x₁+x₂−x₃+x₅=5. При вводе x₂ оба отношения равны 5. Выведем x₅: x₂=5−x₁+x₃−x₅. Тогда x₄=−x₁−3x₃+2x₅, а z=−10+3x₁+x₃+2x₅. При x₁=x₃=x₅=0 получаем x₂=5, x₄=0.
Для любой допустимой точки все добавки к −10 неотрицательны. Равенство возможно только при обнулении трёх небазисных переменных. Оптимум единственный; базис вырожден из-за x₄=0. Если вывести другую строку при ничьей, получится другое описание того же оптимального вектора, а не новый числовой ответ.
Проверка
Вектор даёт 2·5=10 и 5=5 в ограничениях, z=−2·5=−10. Более короткое доказательство: z=−(3x₁+2x₂+x₃)+4x₁+4x₃≥−10. Точный перебор всех базисов согласуется с этим сертификатом.
Что не следует из ответа
Нулевые запасы не означают, что надо исключать точку: они обозначают активные ограничения. При таблицах для min и max критерий знака строки цели зависит от принятой записи; выражение z=−10+… устраняет эту неоднозначность.
Борис Демешев и участники · «Задачки по методам оптимальных решений», задание и исходное решение, строка 1015 · CC0 1.0. Адаптация damirock.com: добавлены алгебраический поворот, две нижние оценки и разбор вырожденного базиса.