Пример 1. В результате решения задачи симплекс-методом найдем оптимальное решение: x11* = 1; x21* = 7,5; L1 = 29,5; где верхний индекс переменных – номер задачи

Решение

В результате решения задачи симплекс-методом найдем оптимальное решение: x ₁^1* = 1; x ₂^1* = 7,5; L ₁ = 29,5; где верхний индекс переменных – номер задачи.

В полученном решении x ₂ = 7,5 – нецелочисленное. Поэтому для дальнейшего решения составляем две новые задачи с различными граничными условиями.

Задача 2: Задача 3:

Результаты решения симплекс-методом задачи 2: x ₁^2* = 1,2; x ₂^2* = 7; L ₂ = 29,4; задачи 3: x ₁^3* = 0,75; x ₂^3* = 8; L ₃ = 29,25.

В задаче 1 переменная x ₁¹ = 1 – целочисленная, а в последующих задачах при целочисленности x ₂ x ₁ перестала быть целочисленной. Затем следует накладывать ограничения целочисленности на x ₁ и т.д. (рис. 3.2).

Рис. 3.2. Метод ветвей и границ.

Результаты решения непрерывной и целочисленной задач вводятся в табл. 3.1. В качестве оптимального принимается решение задачи 5, которое дает наибольшее из целочисленных решений значение целевой функции.

Таблица 3.1

Результаты решения

N задачи	x1	x2	L
		7,5	29,5

Из примера видно, что метод ветвей и границ достаточно трудоемкий. При этом оптимальное решение может быть получено в результате сравнения всех допустимых целочисленных решений.

Поэтому при решении задач реальной размерности может потребоваться память, не имеющаяся даже у современных компьютеров или потребоваться практически неприемлемое время решения.

Обязательное условие метода – наличие верхних границ на значения переменных D_j. Если D_j не назначена, то ее определяют по зависимости:

где d_j ¹ – минимальные значения всех x_j, для которого определяется верхняя граница D_j.

Задача выбора вариантов

Перейдем теперь к частному случаю задач целочисленного программирования – задаче выбора вариантов.

В этом частном случае искомая переменная x_j в результате решения может принимать не любое целое значение, а только одно из двух: либо 0, либо 1. Чтобы такие переменные отличать от обычных и каждый раз не писать x_j [0;1], будем их вместо x_j обозначать d _j. И это уже будет означать, что в результате решения задачи d _j может быть равным или 0 или 1, то есть всегда d _j [0;1]. Такие переменные обычно называют булевыми (в честь предложившего их английского математика Джорджа Буля, 1815–1864).

С помощью булевых переменных можно решать самые различные по содержанию задачи, в которых надо что-то выбирать из имеющихся различных вариантов (например, еще в первобытно-общинном строе дикарь племени наверняка решал такую задачу, выбирая какого дикаря на какую работу поставить), в том числе: задачи о назначении, выбора вариантов, дискретного программирования.