Пример. Отбрасывая требование целочисленности, решим заданную задачу как обычную задачу линейного программирования. БП СЧ

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

БП	СЧ				CO
			3		20/3
					40/7
F		-2	-4	-3

БП	СЧ
	20/7	-13/7	-3/7	-23/7
	40/7	9/7	1/7	10/7
F	160/7	22/7	4/7	19/7

В полученном оптимальном решении задачи имеем нецелочисленное значение неизвестной х₂. Дополнительное ограничение формируем по элементам второй строки:

БП	СЧ				CO
	20/7	-13/7	-3/7	-23/7	-
	40/7	9/7	1/7	10/7
	-5/7	-2/7	-1/7	-3/7	5
F	160/7	22/7	4/7	19/7

БП	СЧ



F

Ответ:

Метод ветвей и границ

Сначала в области допустимых решений системы ограничений находится оптимальное решение, в частности симплекс-методом без учета целочисленности. Если в полученном решении некоторые переменные имеют дробные значения, то выбираем любую из дробных переменных и по ней строим два ограничения. В одном ограничении величина этой переменной меньше либо равна наибольшему целому числу, не превышающему значения дробной переменной в оптимальном решении. В другом ограничении переменная больше или равна наименьшему целому значению, но не меньше значения дробной переменной.

Если, например, дополнительные ограничения строить по переменной , то первое ограничение будет а второе этим мы исключаем из ОДР исходной задачи промежуток с дробными значениями неизвестной . Этот промежуток разбивает ОДР на две части

ОДР

ОДЗ1 ОДЗ2

В результате разбиения ОДР получены две новые задачи (подзадачи) линейной оптимизации. Если после их решения полученные значения неизвестных будут не целочисленные, то, сравнив значения функций этих задач, выбираем задачу с большим значением функции и по новой неизвестной с дробным значением строим снова два дополнительных ограничения (третье и четвертое) и разбиваем эту задачу еще на две новые подзадачи. В результате получаем ветви. Ветвление заканчивается нахождением целочисленного решения, если оно существует. Границами в методе выступают значения функций задач каждой ветви. На каждом этапе решения задачи дальнейшему ветвлению (разбиению на новые задачи) подлежит та ветвь (задача), у которой значение функции больше. Поэтому отдельные подзадачи (ветви), у которых, значение функции меньше, могут быть отброшены. Однако иногда, сравнивая значения функций подзадач, приходится возвращаться к ветвям, которые, ранее были отброшены, и продолжать дальнейшее решение от них.

Поскольку множество всех решений задачи ЦЛО конечно, то после конечного числа разбиений исходной задачи на подзадачи оптимальное решение будет найдено.

Проиллюстрируем применение метода ветвей и границ на следующем примере.

Пример. Найти максимум функции

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

Решение. Для наглядности решение осуществим графическим методом. ОДР задачи является многоугольник ОАВС (рис. 1). В точке В находится максимальное значение функции: при и

Рис. 1

Поскольку значения неизвестных дробные, то разобьём по неизвестной ОДР задачи на две части. Одна будет содержать множество точек, у которых , а вторая — у которых . В результате получаем две новые задачи линейной оптимизации: №2 и № 3 (исходная задача имеет № 1).

Задача № 2	Задача № 3

Области допустимых решений задач представлены на рис. 2.

Из рис. 2 видно, что ни одна целочисленная точка исходной ОДР не потеряна. ОДР задачи № 2 является многоугольник OADEC. В точке Е с координатами и функция достигает максимального значения

Рис. 2

Решение задачи № 2 не является целочисленным. Что касается задачи № 3, то ее ОДР пустая. Ограничения этой задачи противоречивы, и она не имеет решения.

Продолжая решение, разобьем ОДР задачи № 2 на два подмножества по неизвестной . В результате получим две новые задачи № 4 и № 5 с соответствующими дополнительными ограничениями: и .

Задача № 4	Задача № 5

ОДР этих задач представлены на рис. 3.

ОДР задачи № 4 является многоугольник OADFK. Максимальное значение функции достигается в точке F с координатами и . . Таким образом, получено целочисленное решение задачи № 4.

ОДР задачи № 5 является треугольник LMC. Максимальное значение функция достигает в точке L с координатами ; ;

Так как значение функции целочисленного решения задачи № 4 меньше , то дальнейшему разбиению на две задачи № 6 и № 7 подлежит задача № 5 по нецелочисленной неизвестной . Не проводя дополнительных построений, отметим, что ОДР задачи № 6 с дополнительным ограничением не существует, а значение функции в оптимальном целочисленном решении задачи № 7 с дополнительным ограничением равно 7, что меньше . Таким образом, целочисленное решение исходной задачи следующее: , , .