найти целочисленные решения задачи указанным методом
Давайте разберемся с данной задачей, которая решается методом ветвей и границ. Задача — найти целочисленные решения при помощи этого метода.
Модель задачи:
Нам нужно максимизировать целевую функцию: \[ 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. Нахождение точек пересечения границ
Рассчитаем точки пересечения линий, исходя из равенств:
- \(5x_1 + 4x_2 = 17 \)
- \(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. Проверка подобных вариантов
Проведем тест для нескольких значений:
- \(x_1=0,\ x_2=4\)
Проверим неравенства:
\[ 5\cdot 0 + 4\cdot 4 = 16 \geq 17? \quad \text{нет} \Rightarrow не подходит \]
- \(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\).
