Методы решения дискретных задач

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

Есть три метода решения задач с булевыми переменными:

■ метод ветвей и границ;

■ метод сплошного перебора;

■ метод фильтрующего ограничения.

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

Совершенно очевидно, что выполнение этих двух требо­ваний обеспечивает получение в решении значений  [0; 1] т. е. равных 0 или 1.

Пример 4. Требуется решить систему методом сплошного перебора:

max L = 3 ₁ - 2 ₂ + 5 ₃

Решение. Так как ₁, ₂, ₃ могут принимать значе­ния 0 или 1 в любом сочетании, рассмотрим все возможные сочетания (табл. 5) в следующей последовательности.

Таблица 5.

№ варианта	1	2	3	(1)	(2)	(3)	(4)	L
1	0	0	0	0	0	0	0	0
2	1	0	0	1	1	1	4	3
3	0	1	0	2	4	1	0	-2
4	0	0	1	-2	1	0	1	5
5	1	0	1	0	2	1	5	8
6	1	1	0	3	5	2	4	1
Требование				<2	<4	<3	<6	max

1. Заполнить все возможные сочетания допустимых зна­чений ₁, ₂, ₃.

2. Определить и записать значения левых частей огра­ничений (1)-(4) и целевой функции.

3. Вычеркнуть те варианты, в которых не удовлетворя­ется хотя бы одно ограничение, как приводящие к недопу­стимым решениям.

4. Из оставшихся вариантов принимается тот, в кото­ром целевая функция максимальна. В примере max L = 8 — в шестом варианте (оптимальном), в котором  =  = 1; .

Из этого примера видно, что в данном случае всего вариантов будет 2³ = 8 и для каждого варианта надо вычислить четыре ограничения и целевую функцию, т. е. выполнить N = 8(4 + 1) = 40 вычислительных операции. Значит, в общем случае  N = 2ⁿ(m + 1), где n — число переменных, m – число ограничений. Следовательно, при увеличении размерности задачи число вычислений резко возрастает (табл. 6).

Таблица 6.

Для сокращения трудоемкости полного перебора при­меняют различные методы.

Метод фильтрующего ограничения предполагает следую­щую последовательность действий.

1. Принимают некоторые значения ₁, ₂, ₃, например: 1, 0, 0.

2. Определяют значение целевой функции при таком на боре переменных L = 3 ₁ - 2 ₂ + 5 ₃ = 3*1 – 2*0 + 5*0 = 3.

3. Далее устанавливают новые значения переменных и целевой функции; причем если полученная целевая функ­ция меньше 3, то этот вариант не рассматривают. Дли исключения возможного рассмотрения такого варианта, вво­дят дополнительное ограничение 3 ₁ - 2 ₂ + 5 ₃ ≥ 3, кото­рое называют фильтром (Ф).

4. Составляют таблицу (табл. 7), в которой для каж­дого варианта проверяют выполнение всех ограничений, включая Ф.

Если вычисление прекращается и величины не опреде­лены, то в клетках таблицы ставится прочерк.

Введение фильтрующего ограничения Ф привело к сокра­щению числа вычисляемых величин (24 вместо 40, т. е. 60%).

№ варианта	1	2	3	F = Ф	(1)	(2)	(3)	(4)
1	0	0	0	-	-	-	-	-
2	1	0	0	3	1	1	1	4
3	0	1	0	-2	-	-	-	-
4	1	1	0	1	-	-	-	-
5	0	0	1	5	-1	1	0	1
6	1	0	1	8	0	2	1	5
7	0	1	1	3	1	5	-	-
8	1	1	1	6	2	6	-	-
Требование				> 3	< 2	< 4	< 3	< 6

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

Например, из таблицы видно, что в пятом варианте Ф = 5. Поэтому для дальнейших вычислений в качестве фильтрую­щего ограничения принимаем 3 ₁ - 2 ₂ + 5 ₃ ≥ 5 (Ф₁). Од­нако для следующего варианта значение целевой функции будет еще больше (Ф = 8) и в качестве фильтрующего огра­ничения принимается 3 ₁ - 2 ₂ + 5 ₃ ≥ 8 (Ф₂). Для седьмо­го и восьмого вариантов значение целевой функции не удов­летворяет требованиям фильтра Ф₂ и значения ограничений не вычисляем. Значит, трехкратный фильтр (Ф, Ф₁, Ф₂) позволил сократить вычисления еще на 4, т. е. надо выпол­нить 20 вычислений вместо 40 (50%). Более значительное сокращение трудоемкости достигается методом Беллмана с фильтром, где наибольший Ф получают сразу.

Заключение

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

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

Список используемой литературы

1. Глухов В. В., Медников М. Д., Коробко С. Б. Математические методы и модели для менеджмента.2-е изд., испр. и доп. – СПб.: Издательство «Лань», 2005. – 5 с. – (Учебники для вузов. Специальная литература).

2. «Исследование операций в экономике»: Учебное пособие для вузов / Кремер Н. Ш., Путко Б. А., Тришин И. М., Фридман М. Н.: под ред. проф. Кремера Н. Ш. – М.: ЮНИТИ, 2004

3. Харчистов Б.Ф. Методы оптимизации: Учебное пособие. - Таганрог: Изд-вo ТРТУ, 2004. - 140с.

4. «Линейное и нелинейное программирование» под общей редакцией профессора Ляшенко И. Н., Киев – 1975

5. «Математические методы и модели в коммерческой деятельности»: Учебник, 2-е изд., перераб. и дополн. / Фомин Г. П. – М: Финансы и статистика, 2005

6. «Математические методы и модели исследования операций»: Учебное пособие / Кутузов А. Л. – издательство СПб ГПУ, 2005

7. «Математические методы: Учебник» / Партика Т. Л., Попов И. И. – М: ФОРУМ: ИНФРА, 2005