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