Условие
Дана таблица, соответствующая равенствам x₁+x₃+5x₄=3, x₂+2x₃+6x₄=4 и цели z=8−3x₃+3x₄→min. Все xᵢ≥0. Найдите допустимые и базисные допустимые решения, их выпуклую оболочку и оптимум.
Решение источника
Источник перечисляет A=(3,4,0,0), B=(0,2/5,0,3/5), C=(0,0,1/2,1/2), D=(1,0,2,0) и называет D оптимумом с z=2. Часть пунктов решения оставлена без пояснения.
Редакционное объяснение
Положим t=x₃, s=x₄. Тогда x=(3−t−5s, 4−2t−6s, t, s), где t,s≥0, t+5s≤3, 2t+6s≤4. На плоскости (t,s) это четырёхугольник с вершинами (0,0), (0,3/5), (1/2,1/2), (2,0). Их образы и есть A,B,C,D.
| Вершина | Значение z |
|---|---|
| A | 8 |
| B | 49/5 |
| C | 8 |
| D | 2 |
Все допустимые векторы имеют вид αA+βB+γC+δD, где коэффициенты неотрицательны и их сумма равна 1. Минимум в D единственный: у остальных вершин цель строго выше. Из второго ограничения t≤2−3s следует z=8−3t+3s≥2+12s≥2. Равенство требует s=0,t=2.
Проверка
Точный перебор базисов системы из двух равенств даёт ровно четыре различных допустимых вектора. Все перечисленные координаты неотрицательны и удовлетворяют равенствам. Значения цели вычислены рационально; в частности, в B получаем 8+9/5=49/5.
Что не следует из ответа
Не каждый допустимый вектор базисный: внутренние выпуклые комбинации обычно имеют больше положительных координат. Константу 8 нельзя потерять при чтении строки цели: минимум переменной части равен −6, но полный минимум z равен 2.
Борис Демешев и участники · «Задачки по методам оптимальных решений», задание и исходное решение, строка 1060 · CC0 1.0. Адаптация damirock.com: восстановлена полная параметризация, рассчитаны все значения цели и доказан единственный минимум.