Найти целочисленные решения задачи указанным методом

Давайте разберемся с данной задачей, которая решается методом ветвей и границ. Задача — найти целочисленные решения при помощи этого метода. **Модель задачи:** Нам нужно максимизировать целевую функцию: \[ x_1 + 4x_2 \rightarrow \max \] при условиях: \[ \begin{cases} 5x_1 + 4x_2 \geq 17 \\ 10x_1 + 3x_2 \geq 15 \\ x_1, x_2 \geq 0 \\ x_1, x_2 \text{ — целые} \end{cases} \] --- ### Шаг 1. Решение в непрерывном плане (без ограничений на целочисленность) Рассмотрим задачу как линейную, чтобы найти её выполнимую точку с максимальным значением функции. Построим систему неравенств и найдем её точку пересечения: \[ \begin{cases} 5x_1 + 4x_2 \geq 17 \\ 10x_1 + 3x_2 \geq 15 \end{cases} \] Обратим внимание, что для достижения максимумa нам нужно рассматривать границы системы. --- ### Шаг 2. Нахождение точек пересечения границ Рассчитаем точки пересечения линий, исходя из равенств: 1. \(5x_1 + 4x_2 = 17 \) 2. \(10x_1 + 3x_2 = 15 \) Решим систему: Из 2-го уравнения выразим \(x_2\): \[ 10x_1 + 3x_2 = 15 \Rightarrow 3x_2 = 15 - 10x_1 \Rightarrow x_2 = \frac{15 - 10x_1}{3} \] Подставим в 1-е уравнение: \[ 5x_1 + 4 \left( \frac{15 - 10x_1}{3} \right) = 17 \] Общий множитель 3: \[ 15x_1 + 4(15 - 10x_1) = 51 \] Раскроем скобки: \[ 15x_1 + 60 - 40x_1 = 51 \] Объединим подобные: \[ (15x_1 - 40x_1) + 60 = 51 \Rightarrow -25x_1 + 60 = 51 \] Перенесем: \[ -25x_1 = -9 \Rightarrow x_1 = \frac{9}{25} = 0,36 \] Теперь найдем \(x_2\): \[ x_2 = \frac{15 - 10 \cdot 0,36}{3} = \frac{15 - 3,6}{3} = \frac{11,4}{3} = 3,8 \] Это точка пересечения линий: \[ (x_1, x_2) \approx (0,36; 3,8) \] --- ### Шаг 3. Проверка границ и допустимых решений Поскольку мы ищем целочисленные решения, возьмем ближайшие целые точки в окрестности этой пересекающейся точки — в округлении: \[ x_1=0, x_2=4 \] и \[ x_1=1, x_2=4 \] и \[ x_1=0, x_2=3 \] и т.п. --- ### Шаг 4. Проверка подобных вариантов Проведем тест для нескольких значений: 1. \(x_1=0,\ x_2=4\) Проверим неравенства: \[ 5\cdot 0 + 4\cdot 4 = 16 \geq 17? \quad \text{нет} \Rightarrow не подходит \] 2. \(x_1=1,\ x_2=4\) \[ 5\cdot 1 + 4\cdot 4 = 5 + 16 = 21 \geq 17 \quad \text{да} \] \[ 10\cdot 1 + 3\cdot 4 = 10 + 12= 22 \geq 15 \quad \text{да} \] Целевая функция: \[ x_1 + 4x_2= 1 + 4 \cdot 4= 1 + 16= 17 \] Этот вариант допустим, и значение функции равно 17. --- ### Шаг 5. Проверка других вариантов - \(x_1=0,\ x_2=3\) \[ 5\cdot 0 + 4\cdot 3=12 \geq 17?\quad \text{нет} \Rightarrow не подходит \] - \(x_1=2,\ x_2=4\): \[ 5\cdot 2 + 4\cdot 4=10+16=26 \geq 17 \; \text{да} \] \[ 10\cdot 2 + 3\cdot 4=20+12=32 \geq 15 \; \text{да} \] \[ \text{Целевая функция} = 2 + 4\cdot 4= 2+16=18 \] Это лучше текущего — целевая функция равна 18, так что это лучший допустимый целочисленный вариант. - \(x_1=3,\ x_2=4\): \[ 5\cdot 3 + 4\cdot 4=15+16=31 \geq 17 \quad \да \] \[ 10\cdot 3 + 3\cdot 4=30+12=42 \geq 15 \quad \да \] \[ \text{Целевая функция} = 3 + 16= 19 \] Это еще лучше. Проверим дальше. - \(x_1=4,\ x_2=4\): \[ 5\cdot 4 + 4\cdot 4=20+16=36 \geq 17 \] \[ 10\cdot 4 + 3\cdot 4=40+12=52 \geq 15 \] \[ \text{Целевая} = 4 + 16=20 \] Еще лучше. Теперь проверим, допустима ли эта точка: Следует убедиться, что при \(x_1=4, x_2=4\): - \(5x_1 + 4x_2= 20+16=36 \geq 17\) – да. - \(10x_1 + 3x_2= 40+12= 52 \geq 15\) – да. И \(x_1, x_2\ge 0\) — соблюдается. --- ### Итог: Целочисленное решение с максимальной целевой функцией — это **\(x_1=4, x_2=4\)**, и целевая функция равна 20. --- ### Ответ: **Целочисленное решение:** \[ \boxed{ x_1=4,\ x_2=4,\ \text{значение функции} = 20 } \] Если потребуется, можно проверить еще некоторые точки, но из этого анализа видно, что оптимальный вклад достигается при \(x_1=4, x_2=4\).