Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Методы оптимизации - Харчистов Б.Ф.

.pdf
Скачиваний:
137
Добавлен:
24.05.2014
Размер:
931 Кб
Скачать
☆

101

Таблица 10.6

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

↓

 

 

 

 

 

 

 

 

 

Базис

Своб.

 

x1

 

 

x2

 

 

x3

 

x4

 

u1

 

u2

 

 

 

член

 

 

 

 

 

 

 

 

 

 

 

x1

 

4

4

 

 

1

 

0

 

 

 

0

 

 

1

 

 

 

−

1

 

 

 

0

 

 

 

 

7

 

 

 

 

 

 

7

 

 

 

7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x2

 

3

 

 

0

 

1

 

 

 

0

 

0

 

 

 

1

 

 

 

0

 

 

x3

 

1

4

 

 

0

 

0

 

 

 

1

 

 

1

 

 

 

− 3

1

 

 

0

 

 

 

7

 

 

 

 

 

 

7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7

 

 

 

→

u2

 

 

−

4

 

 

0

 

0

 

 

 

0

 

−

1

 

 

−

6

 

 

 

1

 

7

 

 

 

 

 

 

 

7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7

 

 

 

 

 

 

 

 

 

 

f

 

59

 

 

0

 

0

 

 

 

0

 

1

 

 

 

8

 

 

 

0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

7

 

 

 

9

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3

 

 

 

 

 

 

 

 

 

 

 

 

bu2

< 0

 

→

u2 выводим из базиса,

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

 

 

 

6

 

 

1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

min 1

−

 

 

 

= 7 , 8

 

−

 

= 9

 

 

 

= 7

→

x4 вводим в базис.

 

 

7

 

7

3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Таким образом, Б1 = {x1, x2 , x3 , x4}. В результате приходим

к табл. 10.7.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

БР1 = (х1 = 4, х2 = 3, х3 = 1,

 

 

 

Из

табл. 10.7

 

следует,

что

x4 = 4). БР1 является допустимым и, следовательно, оптималь-

ным решением.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Таким образом, задача L2 имеет решение x(2)

= (4, 3) , при

этом f (х(2) ) = 55 .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Поскольку решение x(2) является целочисленным,

то точ-

ка x(2)

= (4, 3)

 

является решением исходной задачи; поэтому по-

лагаем

х = x(2) = (4, 3) , f = f (x(2) ) = 55

и вычисления завер-

шаются.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

102

Таблица 10.7

Базис

Своб.

x

x

x

x

u

u

2

 

член

1

2

3

4

1

 

x1

4

1

0

0

0

−1

1

 

 

 

 

 

 

 

 

x2

3

0

1

0

0

1

0

 

 

 

 

 

 

 

 

x3

1

0

0

1

0

−4

1

x4

4

0

0

0

1

6

−7

 

 

 

 

 

 

 

 

f

55

0

0

0

0

2

7

 

 

 

 

 

 

 

 

 

Ответ: х = (4, 3) , f = 55 .

Задачи

1. Решить методом отсечений следующую целочисленную задачу ЛП:

f (x) = x1 + 2x2 → max, 4x1 + 2x2 ≤ 13 ,

x1 ≥ 0, x2 ≥ 0 , x1 , x2 − целые.

2. Решить методом отсечений следующую целочисленную задачу ЛП:

f (x) = 2x1 + 3x2 → max, 2x1 + 5x2 ≤ 16 ,

6x1 + 5x2 ≤ 30 , x1 ≥ 0, x2 ≥ 0 ,

x1 , x2 − целые.

103

11. МЕТОД ВЕТВЕЙ И ГРАНИЦ

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

На практическом занятии рассматривается метод ветвей и границ для задачи целочисленного линейного программирования (ЛП) следующего вида:

n

f (x) = ∑ c j x j → max ,

j =1

n

∑ aij x j ≤ bi , i = 1, m ,

j =1

x j ≥ 0 ,

j =

 

 

,

 

1, n

x j − целые,

j =

 

.

1, n

Допустимое множество Х данной задачи предполагается ограниченным.

В данном случае на каждом этапе (шаге) решаются непрерывные задачи ЛП: на предварительном (нулевом) этапе – задача L0; на k-м, k = 1, 2,..., этапе − задачи L2k-1 и L2k. Задача L0 , как и в методе отсечений, представляет собой исходную задачу без учета требования целочисленности; задача Lν , ν = 1,2,..., получается в

результате добавления к задаче L0 дополнительных ограничений. Верхняя граница (оценка) ξν целевой функции f для задачи

104

Lν, ν = 0,1,2,..., определяется следующим образом:

ξν ≡ f (x(ν ) ) ,

где x(ν ) − решение задачи Lν .

Если задача Lν не имеет решения, то полагается ξν ≡ −∞ .

В процессе решения строится дерево задач, в котором ν -я, ν = 0,1,2,..., вершина соответствует задаче Lν . Обозначим

через I множество вершин, из которых возможно ветвление. Для ветвления на k-м, k =1,2,..., этапе выбирается ν-я, ν I, вершина

(задача Lν ), которая имеет максимальную верхнюю оценку ξν .

Пусть в решении x(ν ) некоторая компонента xr(ν ) , 1 ≤ r ≤ n , не является целочисленной. Допустимое, т.е. целочисленное, значение xr должно удовлетворять одному из неравенств, представляющих собой необходимые условия целочисленности xr :

либо xr ≤ [xr(ν ) ] , либо xr ≥ [xr(ν ) ] +1, где [a] − целая часть действительного числа а.

В результате задача Lν разветвляется (разбивается) на две не связанные между собой задачи L2k −1 и L2k . Задача L2k −1 пред-

ставляет

собой

задачу

Lν

с дополнительным

ограничением

x

r

≤ [x(í) ] , а задача L2k − задачу L с дополнительным ограниче-

 

r

 

 

 

 

ν

 

 

 

нием x

≥ [x(ν )

] +1, т.е.

 

 

 

 

 

 

 

r

r

 

 

 

 

 

 

 

 

 

 

L2k −1

 

Lν ,

 

L2k

 

Lν ,

 

 

 

 

 

(ν )

];

 

(ν )

] +1.

 

 

 

 

 

x ≤ [xr

 

 

x ≥ [xr

Для ускорения процесса решения вводится нижняя граница целевой функции f для целочисленного решения, обозначаемая

Θ . После решения задачи Lν значение Θν определяется следующим образом:

 

 

 

105

 

 

 

ν −1

, если задача Lν не имеет решения либо x

(ν )

 

Θ

 

Θν

 

 

не является целочисленным;

 

=

 

 

 

 

 

 

 

max{Θν -1 ,ξν }, если x(ν ) является целочисленным.

При этом Θ0 ≡ −∞ .

Ветвление на k-м, k = 1,2,.., этапе из i-й, i I, вершины следует прекратить, если верхняя граница ξ i целевой функции для задачи Li не больше известной на данном шаге нижней гра-

ницы Θ2k целевой функции для целочисленного решения. Процесс решения завершается, когда отсутствуют вершины, из которых возможно ветвление, т.е. I = . При этом оптимальное зна-

чение f = Θ2k , решение x = x(ν ) , где x(ν ) определятся из условия f (x(ν ) ) = Θ2k .

Итак, алгоритм решения целочисленной задачи ЛП методом ветвей и границ заключается в следующем.

1. Решается задача ЛП L0.

Если задача L0 не имеет решения, то исходная задача не имеет целочисленного решения и вычисления завершаются.

2.Находится решение x(0) , вычисляется верхняя граница

ξ0 = f (x(0) ) .

Если решение x(0) является целочисленным, то полагается x = x(0) , f = ξ 0 и вычисления завершаются.

Если решение x(0) не является целочисленным, то полага-

ется Θ0 = −∞ , k=1 и осуществляется переход к п. 3.

3. Выбирается для ветвления ν-я вершина из I, для которой выполняется условие

ξν = max ξ i .

i I

106

4.Выбирается (произвольно) одна из нецелочисленных компонент xr(ν ) , осуществляется ветвление по переменной xr , составляются задачи L2k −1 и L2k .

5.Решается задача Lj , j = 2k −1, 2k.

Если задача L j не имеет решения, то полагается ξ j = −∞ ,

Θj = Θ j −1 и осуществляется (при j=2k) переход к п. 7.

6.Находится x( j ) , вычисляется ξ j = f (x( j) ) .

Если решение x( j ) является целочисленным, то полагается Θ j = max{Θ j −1,ξ j } и осуществляется (при j = 2k) переход к п. 7.

Если решение x( j ) не является целочисленным, то полагается Θ j = Θ j −1 и осуществляется (при j = 2k) переход к п. 7.

7.Просматриваются вершины из I и прекращается ветвление, если выполняется условие

ξi ≤ Θ2k , i I.

8.Проверяется условие окончания вычислений

I = .

Если оно выполняется, то полагается f = Θ2k , x = x(ν ) ,

где x(ν ) определяется из условия f (x(ν ) ) = Θ2k , и вычисления за-

вершаются.

Если условие не выполняется, то полагается k = k +1 и осуществляется переход к п. 3.

Пример. Решить методом ветвей и границ следующую целочисленную задачу ЛП:

f (x) = 2x1 + 3x2 → max , 5x1 + 7x2 ≤ 35 ,

4x1 + 9x2 ≤ 36 , x1 ≥ 0 , x2 ≥ 0 , x1, x2 − целые.

107

Решение.

Предварительный (нулевой) этап

Записываем задачу L0 (исходная задача без учета требо-

вания целочисленности):

 

 

 

 

 

 

f (x) = 2x1 + 3x2 → max ,

 

 

 

 

 

 

5x1 + 7x2 ≤ 35 ,

(1)

 

 

 

 

 

4x1 + 9x2 ≤ 36 ,

(2)

 

 

 

 

 

x1 ≥ 0, x2 ≥ 0.

 

 

Этой задаче соответствует нулевая вершина дерева задач

(см. ниже рис. 11.6).

 

 

 

 

Решаем графически задачу L0 (рис. 11.1).

x2

 

 

 

 

 

 

 

 

 

 

 

6

 

 

 

 

 

 

5

 

 

 

 

 

 

4

 

 

 

 

 

 

3

 

 

 

x(0)

 

 

2

 

 

 

 

 

 

1

 

 

f (x)

 

 

 

 

 

 

 

x1

 

 

 

1 2 3 4 5 6 7 8 9

(2)

 

 

 

 

(1)

 

 

 

 

 

Рис. 11.1

 

 

Из рис. 11.1

следует, что задача L0 имеет решение x(0) .

Точка x(0) является решением системы уравнений

 

 

 

5 x1 + 7 x2 = 35 ,

 

 

 

 

 

 

4 x1 + 9 x2 = 36 .

 

 

 

 

 

 

 

 

Находим x(0) и ξ 0

:

 

 

 

 

 

 

108

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

− 45x1 + 63x2 = 315 →

 

x = 63

= 312 ;

 

 

 

 

 

 

28x1 + 63x2 = 252

 

 

1

 

17

 

17

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5 63

 

17x1

= 63

 

9

 

 

280

 

 

 

 

 

40

 

6

 

+ 7х = 35

→ 7х

= 35 −18

=

 

→

 

х =

= 2

;

 

 

 

 

 

 

 

 

 

17

2

 

2

 

 

 

17

 

 

 

17

 

 

 

2

17

17

 

 

 

 

 

12

 

6

 

 

 

 

 

 

 

 

 

 

 

x

(0) = (3

, 2

 

);

 

 

 

 

 

 

 

 

 

 

 

 

 

17

17

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ξ 0

= f (x(0) ) = 2 3

12

 

+ 3 2

 

6

 

= 14

 

8

.

 

 

 

 

 

17

 

17

 

17

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Поскольку x(0) не является целочисленным, то полагаем Θ0 = −∞ и выполняем 1-й этап.

Первый этап

Осуществляем ветвление из нулевой вершины.

Выбираем для ветвления нецелочисленную компоненту x2(0) = 2 176 ; осуществляем ветвление по переменной x2 : x2 ≤ 2 , x2 ≥ 3 ; составляем задачи L1 и L2 :

L1

 

L0 ,

 

L2

L0 ,

 

 

2;

 

≥ 3.

 

x2 ≤

 

x2

Записываем задачу L1:

 

 

 

 

 

f (x) = 2x1 + 3x2 → max ,

 

 

 

 

5x1 + 7x2 ≤ 35,

 

(1)

 

 

 

4x1 + 9x2 ≤ 36 ,

 

(2)

 

 

x1 ≥ 0, 0 ≤ x2 ≤ 2.

 

 

Этой задаче соответствует первая вершина дерева задач (см. ни-

же рис. 11.6).

Решаем графически задачу L1 (рис. 11.2).

Из рис. 11.2 следует, что задача L1 имеет решение x(1) .

109

Точка x(1) является решением системы уравнений

 

 

5 x1 + 7 x2 = 35 ,

 

 

 

= 2.

 

 

x2

x2

 

 

6

 

 

 

5

 

 

 

4

 

 

 

3

 

 

x(1)

2

 

 

 

 

 

 

1

 

f (x)

 

 

 

1 2 3 4 5 6 7 8 9

 

 

 

 

x1

 

 

 

 

 

 

(1)

 

 

 

(2)

 

 

Рис. 11.2

 

 

 

 

 

Находим x(1)

и ξ 1 :

 

 

 

 

 

 

 

 

 

5х + 7 2 = 35 → 5х = 21 → х = 4

1

;

 

 

 

1

 

1

 

 

1

 

5

 

 

 

 

 

1

 

 

 

 

 

 

 

 

x(1) = (4

 

, 2);

 

 

 

 

 

 

 

5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ξ1

= f (x(1) ) = 2 4

 

1

+ 3 2 = 14

2

.

 

 

 

5

5

 

 

 

 

 

 

 

 

 

 

 

Поскольку x(1) не является целочисленным, то полагаем

Θ1 = Θ0 = −∞ .

 

 

 

 

 

 

 

 

 

 

Записываем задачу L2 :

 

 

 

 

 

 

 

 

 

 

 

f (x) = 2x1 + 3x2 → max ,

 

 

 

 

 

 

 

5x1 + 7x2 ≤ 35 ,

(1)

 

 

 

 

 

4x1 + 9x2 ≤ 36 ,

(2)

 

 

 

 

 

x1 ≥ 0, x2 ≥ 3.

 

 

 

 

 

110

Этой задаче соответствует вторая вершина дерева задач (см. ниже рис. 11.6).

Решаем графически задачу L2 (рис. 11.3).

x2

 

6

 

 

5

 

 

4

 

x(2)

3

 

 

 

 

2

 

 

1

 

f (x)

 

 

1 2 3 4 5 6 7 8 9

 

 

 

 

x1

 

 

 

 

 

 

(1)

(2)

 

 

Рис. 11.3

 

 

 

 

 

Из рис. 11.3 следует, что задача L имеет решение x(2) .

 

 

 

 

 

 

2

 

 

 

 

 

Точка x(2) является решением системы уравнений

 

 

4 x1 + 9 x2 = 36 ,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

x2 = 3.

 

 

 

 

 

 

Находим x(2)

и ξ 2 :

 

 

 

 

 

 

4х + 9 3 = 36 → 4х = 9 → х = 2

1

;

 

1

 

1

 

1

4

 

 

 

 

 

1

 

 

 

 

 

 

x(2) = (2

 

, 3);

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4

 

 

 

 

 

 

 

ξ 2

= f (x(2) ) = 2 2

1

+ 3 3 = 13

1

.

 

 

 

 

2

 

 

 

 

 

4

 

 

 

 

 

Поскольку x(2) не является целочисленным, то полагаем

Θ2 = Θ1 = −∞ .

Просматриваем вершины из I = {1, 2}.

Соседние файлы в предмете Экономика