Разбор задачи

Решить задачу целочисленного программирования методом ветвей и границ:

Условие:

Решить задачу целочисленного программирования методом ветвей и границ: $

\begin{array}{l}\nf(\mathrm{x})=x_{1}+x_{2} \rightarrow \max ; \\ \left\{ \begin{array}{l} -4 x_{1}+3 x_{2} \leq 6, \\ 2 x_{1}+x_{2} \leq 6, \end{array}

x_{j} \geq 0, x_{j} \in Z, j=1,2 . \end{array} $

Для решения задачи целочисленного программирования методом ветвей и границ, начнем с формулировки задачи:

Максимизируем функцию:

f(x) = x_1 + x_2

при ограничениях: $

\begin{cases} -4x_1 + 3x_2 \leq 6 \\ 2x_1 + x_2 \leq 6 \\ x_j \geq 0, \quad x_j \in \mathbb{Z}, \quad j=1,2 \end{cases}

Сначала решим задачу без целочисленных ограничений, т.е. найдем оптимальное решение для непрерывных переменных (x_1) и (x_2).

Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит

Попробуй решить по шагам

Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение

Какой из следующих шагов является первым при решении задачи целочисленного программирования методом ветвей и границ?

Построение графика ограничений для определения области допустимых решений.

Решение задачи линейного программирования без учета целочисленных ограничений.

Проверка всех возможных целочисленных комбинаций переменных в заданной области.