X1, х2  0, целые.

Начальный шаг решения этой задачи состоит в нахождении решения задачи ЛП, получаемой при отбрасывании условия целочисленности х₁ и х₂. Обозначим эту задачу через ЛП-1. На рис.5.1.1 представлено графическое решение задачи ЛП-1.

Рис.5.1.1. Решение задачи ЛП-1.

Оптимальное решение задачи ЛП-1 имеет вид: х₁ = 2, х₂ = 1,5, оптимальное значение целевой функции F( ) = 9. Поскольку х₂ принимает дробное значение, найденное решение не может быть оптимальным решением исходной задачи ЦЛП. Но найденное значение F( ) представляет собой верхнюю границу истинного оптимального целочисленного значения, поскольку при выполнении требования целочисленности х₂ значение F( ) может лишь уменьшиться.

Следующий шаг метода ветвей и границ состоит в просмотре целочисленных значений х₂, больших или меньших 1,5. Это делается путем добавления к задаче ЛП-1 либо ограничения x₂  1, либо х₂  2. Таким образом, из задачи ЛП-1 получаются две задачи следующего вида (ЛП-2 и ЛП-3):

ЛП-2 ЛП-3

F( ) = 3x₁ + 2x₂  max F( ) = 3x₁ + 2x₂  max

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

x₁ + x₂  3,5 x₁ + x₂  3,5

x₁  2 x₁  2

x₂  2 x₂  2

x₂  1 х₂  2

x₁, х₂  0, x₁, х₂  0.

На рис.5.1.2 и 5.1.3 изображены допустимые области задач ЛП-2 и ЛП-3 соответственно. (Заметим, что допустимая область задачи ЛП-3 представляет собой просто отрезок АВ).

Рис. 5.1.2. Решение задачи ЛП-2.

Рис. 5.1.3. Решение задачи ЛП-3.

Оптимальное решение задачи ЛП-2 (рис. 2) – точка х₁ = 2, х₂ = 1, где F( ) = 8. Таким образом, получено допустимое (целочисленное) решение исходной задачи ЦЛП. Зафиксируем это целочисленное решение. Пусть Z₀ = 8. Даже если ЛП-2 имеет другие целочисленные решения, значение целевой функции в них не может быть больше 8. Таким образом значение Z₀ = 8 представляет собой текущую нижнюю границу максимального значения F . Поскольку ранее была получена верхняя граница, равная 9, нельзя утверждать, что решение ЛП-2 оптимально для исходной задачи. Следовательно, необходимо также рассмотреть задачу ЛП-3.

Оптимальное значение задачи ЛП-3 (рис.3) – х₁ = 1,5; х₂ = 2; F( ) = 8,5. Для исходной задачи ЦЛП это решение недопустимо, поскольку х₁ принимает дробное значение. Оптимальное значение F( ) = 8,5 задачи ЛП-3 больше ранее полученной нижней границы = 8, поэтому необходимо проверить существование в допустимой области задачи ЛП-3 целочисленного решения, дающего значение целевой функции F  8. Для этого рассматриваются задачи ЛП-4 и ЛП-5, получающиеся при добавлении к ЛП-3 ограничений х₁  1 и х₁  2 соответственно.

ЛП-4 ЛП-5

F( ) = 3x₁ + 2x₂  max F( ) = 3x₁ + 2x₂  max

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

x₁ + x₂  3,5 x₁ + x₂  3,5

x₁  2 x₁  2

x₂  2 x₂  2

х₂  2 х₂  2

x₁  1 х₁  2

x₁, х₂  0, x₁, х₂  0.

Допустимая область задачи ЛП-4 состоит из отрезка ДЕ, показанного на рис. 5.1.4; задача ЛП-5 не имеет допустимых решений.

Рис. 5.1.4. Решение задачи ЛП-4.

Оптимальное решение задачи ЛП-4 имеет вид: х₁ = 1, х₂ = 2; F( ) = 7, следовательно, для любого целочисленного решения в допустимой области ЛП-3 значение целевой функции не превосходит 7. Так как F( ) меньше ранее полученной нижней границы, то = 8 не изменяется. Таким образом, точка х₁ = 2, х₂ = 1 (решение задачи ЛП-2) представляет собой оптимальное целочисленное решение исходной задачи; оптимальное значение целевой функции в этой точке равно = 8.

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

ЛП-1 = (2; 1,5) F( ) = 9

x ₂  1 x ₂ 2

= (2; 1) ЛП-2 ЛП-3 = (1,5; 2)

F ( ) = 8= F( ) = 8,5 

x ₁  1 x ₁ 2

= (1; 2) ЛП-4 ЛП-5 P = 

F( ) = 7 <

Рис. 5.1.5.

Каждая вершина представляет собой либо начальную, либо конечную точку некоторой ветви. Вершина 1 на рис. 5 соответствует задаче ЛП-1, получаемой при отбрасывании требования целочисленности переменных. Ветвление в вершине 1, определяемое целочисленной переменной х₂ с помощью ограничения х₂  1, приводит к вершине 2 (ЛП-2). Поскольку задача ЛП-2 имеет оптимальное целочисленное решение, нет необходимости производить ветвление в вершине 2. В этом случае говорят, что рассматриваемая вершина прозондирована. Ветвление в вершине 1 по ограничению х₂  2 дает ЛП-3 (вершина 3). Поскольку оптимальное решение ЛП-3 является дробным и F( ) > происходит дальнейшее ветвление в вершине 3 по целочисленной переменной х₁. Таким образом, появляются вершины 4 и 5. Эти вершины являются прозондированными, поскольку ЛП-4 обладает целочисленным решением, а задача ЛП-5 не имеет допустимых решений. Наилучшее решение из полученных в прозондированных вершинах представляет собой оптимальное решение исходной задачи.