Главная страница

1. Постановка и особенности задач дискретного


Скачать 177.02 Kb.
Название1. Постановка и особенности задач дискретного
Дата15.12.2020
Размер177.02 Kb.
Формат файлаpdf
Имя файлаlect.pdf
ТипЗадача
#160820
страница3 из 3
1   2   3
4. Метод ветвей и границ
Суть метода ветвей и границ. Метод ветвей и границ относится к группе комбинаторных методов. Комбинаторные методы исходят из конечности числа допустимых планов задачи и заменяют полный перебор всех планов их частичным направленным перебором. Комбинаторные методы в значительно меньшей степени подвержены в процессе вычислений влиянию ошибок округления, поэтому являются более предпочтительными по сравнению с методами отсечения. Метод ветвей и границ – один из наиболее эффективных методов решения задач комбинаторного типа.
Рассмотрим общую задачу дискретного программирования )
x
f
Z
=
max
, (4.1)


x
, (где

- конечное множество допустимых планов.
1.
Находим верхнюю границу (оценку) функции
( )


x
x
f
,
, те. такое число
( )

0
ϕ
, что для любых


x
( )
( Если при этом удается найти такой план
0
x
задачи (4.1)-(4.2), для которого выполняется равенство

( )
( )

=
0 то
0
x
- оптимальный план задачи (4.1)-(4.2).
2. Если оптимальный план не найден, то некоторым способом разбиваем множество

наконечное число непересекающихся подмножеств

1 1
1
r
r
r
=

=

,
=

=

1 и находим для каждого из этих подмножеств верхнюю границу
( )
(
)
1 1
1
,...,
2
,
1
r
r
r
=

ϕ
. Если при этом удастся найти такой план
(
)
1 1
1 1
r
r
x
r
l




, что выполняется соотношение ) ( )
( )(
)
1 то
1
l
x
- оптимальный план задачи (4.1)-(4.2.). Если же такой план не найден, то выбираем подмножество
1
r

с наибольшей верхней границей перспективное подмножество) и разбиваем его на несколько непересекающихся подмножеств
(
)
1 2
,...,
2
,
1
s
s
s
=

. Для каждого нового подмножества находим верхнюю границу
( )
2
s

ϕ
. Если будет найден такой план
2
k
x
, что
( ) ( ) ( )
2 то
2
k
x
- оптимальный план задачи. Если оптимальный план не найден, то дальнейшему ветвлению подвергаем подмножество с наибольшей верхней границей, и т.д. Процесс продолжается дополучения оптимального плана. Способы ветвления и нахождения верхних границ выбираются для каждой конкретной задачи дискретного программирования. Процесс сопровождается построением дерева ветвления (рис

… …
… Рис. Задача целочисленного (частично целочисленного) линейного программирования (2.1)-(2.4). В качестве верхней границы на множестве планов рассматривают значение целевой функции на оптимальном плане соответствующей ЗЛП (2.1)-(2.3). Пусть, далее,
r
x
- целочисленная переменная, значение

r
x
которой в оптимальном решении задачи (2.1)-(2.3) является дробным.
Интервал
[ ]
[ ]
1
+
<
<


r
r
r
x
x
x
не содержит допустимых целочисленных компонент решения. Поэтому допустимое целое значение
r
x
должно удовлетворять одному из неравенств
[ ]


r
r
x
x
или
[ ]
1
+


r
r
x
x
. Введение этих условий в задачу с отброшенным условием целочисленности порождает две несвязанные между собой задачи. Говорят, что исходная задача разветвляется на две подзадачи. Затем каждая подзадача решается как ЗЛП с целевой функцией исходной задачи ]
,
,




r
r
x
x
x
,
[ Если полученное оптимальное решение оказывается допустимым для целочисленной задачи, то его следует зафиксировать как наилучшее. При этом нет необходимости продолжать ветвление подзадачи, поскольку улучшить полученное решение не удастся. В противном случае подзадача должна быть разбита на две подзадачи и т.д. Как только полученное
27 1
1

1 2

1
r

1 1
r

2 1

2
s

2 1
s

допустимое целочисленное решение одной из подзадач оказывается лучше имеющегося, оно фиксируется вместо зафиксированного ранее. Процесс ветвления продолжается до тех пор, пока каждая подзадача не приведет к целочисленному решению или пока не будет установлена невозможность улучшения имеющегося решения. Пример 4.1.
2 1
3 2
max
x
x
Z
+
=
;
,
36 9
4
,
35 7
5 2
1 2
1

+

+
x
x
x
x
,
,
0
,
0 2
1 2
1
целые
х
х
х
х



Р е ш е ни е Решим исходную задачу (задачу 0) как ЗЛП с отброшенным условием целочисленности. Оптимальное решение достигается в точке






=

17 6
2
;
17 12 3
нц
х
Так как обе переменные принимают нецелые значения, то любая из них может быть выбрана в качестве переменной, продолжающей процесс ветвления.
Выбор, например, переменной х порождает две подзадачи, связанные с условием
[ ]


2 2
х
х
или
[ ]
1 2
2
+


х
х
. Так как
[ ]
[
]
2 17
/
40 х, имеем две подзадачи 1.1 и 1.2:
a. 1.2
;
3 2
max
2 1
x
x
Z
+
=
;
3 2
max
2 1
x
x
Z
+
=
,
35 7
5 2
1

+
x
x
,
35 7
5 2
1

+
x
x
,
36 9
4 2
1

+
x
x
,
36 9
4 2
1

+
x
x
,
2 2

x
,
3 2

x
,
0
,
2 1
целые
х
х


0
,
2 1
целые
х
х


Порожденные подзадачи содержат все допустимые целочисленные решения исходной задачи, те. исходное множество допустимых
28
целочисленных решений остается неизменным в процессе ветвления. Их оптимальные решения 2
14
,
2
;
5 1
4
=






=


Z
х
нц
2 1
13
,
3
;
4 1
2
=






=


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






=

2
;
2 1
4
нц
х
. Так как значение
2 1
4 х остается нецелым, задача 1.1 порождает подзадачи 2.1 и
2.2 с дополнительными ограничениями соответственно
[ ]


1 1
х
х
, тех и
[ ]
1 1
1
+


х
х
, тех 2
1

+
х
х
,
35 7
5 2
1

+
х
х
,
36 9
4 2
1

+
х
х
,
36 9
4 2
1

+
х
х
,
2
,
4 2
1


х
х
,
2
,
5 2
1


х
х
,
0
,
2 1
целые
х
х


целые
х
х


0
,
2 Оптимальные решения этих подзадач )
14
,
2
;
4
=
=


Z
х
нц
и
7 2
14
,
7 3
1
;
5
=






=


Z
x
нц
соответственно. Наличие у подзадачи 2.1 целочисленного решения не означает, что найдено оптимальное целочисленное решение исходной задачи 0, потому
29
что еще не решены подзадачи 1.2 и 2.2, которые могут дать лучшее решение, чем 2.1. Целочисленное решение подзадачи 2.1 определяет нижнюю границу
14
=
Z
значений целевой функции. Нет необходимости рассматривать те последующие подзадачи, для которых оптимальные значения
Z
меньше указанной нижней границы.
Обратимся к подзадаче 1.2. Для нее
5
,
13
=

Z
, что не превышает значения
14
=
Z
, поэтому поиск вдоль ветви
3 2

x
следует прекратить.
Исследуем вершину 2.2, которой соответствует
7 2
14
=

Z
. Несмотря на то, что полученное значение превышает нижнюю границу
14
=
Z
, дальнейшее ветвление осуществлять нецелесообразно, поскольку
1 14 7
2 14
<

и все коэффициенты целевой функции целые. Итак, найдено оптимальное решение задачи
( )
( )
14
,
2
;
4
=
=


ц
ц
x
Z
х
. К нему привела цепочка задач
2 2
1 2
2 1
1 Если для исследования выбрать подзадачу 1.2, то получим следующие оптимальные целочисленные решения
( )
13
,
3
;
2
=
=


Z
х
ц
и
( ц. Они явно хуже, чем решение подзадачи Упражнения для самостоятельного решения

Методом ветвей и границ найти оптимальные решения задач. max
3 2
2 1

+
x
x
; 4.3. min
3 2
1

+
x
x
;
1 2
2 2
1

+
x
x
,
29 4
2 1

+

x
x
,
15 4
2 1


x
x
,
15 3
2 1


x
x
,
16 3
2 1

+
x
x
,
38 2
5 целые целые 1
30
Список использованной литературы. Акулич ИЛ. Математическое программирование в примерах и задачах. – М Высш.шк., 1993.
2. Кузнецов А.В., Холод НИ. Математическое программирование. – Минск Высш.шк., 1984.
3. Кузнецов А.В., Холод НИ, Костевич Л.С. Руководство к решению задач по математическому программированию. – Минск Высш.шк.,
2001.
4. Морозов В.В. и др. Исследование операций в задачах и упражнениях.
– М Высш.шк., 1986.
5. Саати Т.Л. Целочисленные методы оптимизации и связанные сними экстремальные проблемы. – М, Мир, 1973.
6. Сергиенко ИВ. Математические модели и методы решения задач дискретной оптимизации. – Киев Наукова думка, 1988.
7. Сигал ИХ, Иванова А.П. Введение в прикладное дискретное программирование. М ФИЗМАТЛИТ, 2002.
8. Схрейвер А. Теория линейного и целочисленного программирования. Т. – М Мир, 1991.
31
Подписано в печать 14.10.2009. Усл. печ. л. 1,75. Тираж 10 экз. Заказ Тверской государственный университет
1   2   3


написать администратору сайта