Программирования.

Таблица I.

	Базис
		-1	-4

Таблица II.

	Базис

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

Теперь запишем правильное отсечение: и, сформировав дополнительную строку, записываем все результаты в таблицу III.

Таблица III.

	Базис
		-		-	-

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

Таблица IV.

	Базис
		-3			-5
							-2
	-	-		-	-

В таблице V представлен новый опорный план, в котором все еще нарушено условие целочисленности.

Таблица V.

	Базис

Так как, для истинных переменных задачи то новое правильное отсечение будем формировать по строке :

Запишем правильное отсечение: и, сформировав дополнительную строку, получим таблицу VI.

Таблица VI.

	Базис
	-	-	-			-

В таблице VII:

Таблица VII.

	Базис
								-2
							-1
								-10

получено искомое целочисленное решение:

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

В литературе, изложенный выше метод, известен также и под названиями метода отсечений или метода Гоморри.

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Найти экстремум целевой функции при заданной системе ограничений. Во всех задачах множество целых чисел.

I.		VI.
II.		VII.
III.		VIII.
IV.		IX.
V.		X.

II.4. МЕТОД ВЕТВЕЙ И ГРАНИЦ В ЗАДАЧАХ ЦЕЛОЧИСЛЕННОГО

ПРОГРАММИРОВАНИЯ.

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

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

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

Задачу

обозначим ЛП I. Она содержит всего лишь две переменные, поэтому ее можно решать, используя графический метод[2].

Из рисунка видно, что оптимальное решение задачи ЛП I достигается в точке , которой соответствует оптимальное решение при этом целевая функция достигает максимального значения

Поскольку принимает дробное значение, найденное решение не может быть оптимальным решением исходной задачи ЦЛП. Найденное значение представляет собой верхнюю границу истинного оптимального значения целевой функции задачи, поскольку при выполнении требований целочисленности значение может разве что уменьшиться[3].

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

Таким образом, из ЛП I получаются две задачи:

ЛП II   при ограничениях:     новое ограничение:

ЛП III   при ограничениях:     новое ограничение:

Допустимые области задач ЛП II и ЛП III обладают следующими свойствами:

1⁰. Оптимальное решение ЛП I недопустимо для обеих ЛП II и ЛП III.

2⁰. Любое целочисленное (допустимое) решение исходной задачи допустимо для обеих задач ЛП II и ЛП III.

Из решений ЛП II и ЛП III следует, что - это нижняя граница максимального значения целевой функции для исходной задачи ЦЛП.

Для ЛП III но план не является целочисленным, так как переменная принимает дробное значение. Поэтому необходимо проверить существование в

допустимой области задачи ЛП III целочисленного решения, дающего значение целевой функции . Для этого рассматриваются задачи ЛП IV и ЛП V, которые получаются в результате добавления к ЛП III дополнительных ограничений и соответственно.

Задача ЛП V допустимых решений не имеет, а допустимая область задачи ЛП IV - это отрезок (см. рисунок II.4.4.). Оптимальное решение ЛП IV даже визуально вполне очевидно: При этом значение целевой функции задачи Следовательно, для любого целочисленного решения в допустимой области ЛП III значение целевой функции не превосходит

Таким образом, перебором установлено, что точка представляет собой оптимальное целочисленное решение исходной задачи.

Дата добавления: 2015-10-29