Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 30

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 24 25 26 27 28 29 < 30 > 31 32 33 34 35 36 .. 84 >> Следующая


IQ5

вого шага ветвления вершина со значением оценки 13 - отсеяна, так как во всех дальнейших вершинах, с ней связанных, значение целевой функции не может быть больше 13 (все Cj целые).

Рис. 3.3

Если бы в качестве рекорда рассматривалось целочисленное решение Z0 = (I; 1; 0; 0), то эта вершина не была бы отсеяна. В результате выполнения ветвления получаем

13</(®°)<15|.

2

Переходим к ветвлению задачи с оценкой 15 -. Вершина с оцен-6

кой 11 - отсеяна по правилам отсева. В результате выполнения ветвления получаем

13 < f(x°) < 15,5.

Переходим к ветвлению задачи с оценкой 15, 5. Задача со значениями 2/^ = 1/2 = 2/з = 1 не является допустимой. Решив задачу для

2

у і = 0, получаем оценку 13

13 < /(х°) <131,
86

Разд. II. Комбинаторные методы решения задач

и задача решена, X0 = (0; I; 1; 0). Всего решено шесть подзадач, оптимум был известен до начала процесса ветвления, но для доказательства оптимальности начального решения выполнено три ветвления.

Пример 3.2. Найдем точное решение примера 2.1:

f (ж) = бжі H- 5з?2 H- 2жз H- 3x4 H- 4^5 H- 5жб H- 4^7 H- 8^8 H- 7жд -|- Зжю —У шах,

2xi H- 2^2 + 2хз H- ж 4 H- 2ж5 + 2xq H- 2^7 + За?8 + Зжд H- ^io < 10,

Xj Є {0,1}, і = 1,2, ...,10; Ai= 3, A2 = A3 = I, A4 = 3, A5 = 2,

Ає = |, А7 = 2, A8 = |, Ag = |, Ai0 = 3.

Из табл. 2.1 имеем

у° = (1; 1; 0; 1; 0; 0,5; 0; 1; 0; I), f(y°) = 27,5;

z° = (1; 1; 0; 1; 0; 0; 0; 1; 0; I), f(z°) = 25,

поэтому

25 < /(ж0) < 27,5.

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

Z0 = (I; 1; 0; 0; 0; 0; 0; I; 1; 0), f(z°) = 26,

26 < /(ж0) < 27,5.

На рис. 3.4 представлено решение этого примера.

Рис. 3.4
Гл. 3. Метод ветвей и границ

87

Первое ветвление выполняется ПО переменной 2/6 = —, после вычисления оценок имеем

26 < f(x°) < 27,5.

Для ветвления выбирается задача с оценкой 27, 5. После выполнения ветвления получаем

26 < f(x°) < 27 і.

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

О

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

2

Выбирается вершина, у которой у% = -. Решив линейную задачу, у

О

которой г/2 = 2/б = 2/s = 1? получаем целочисленное решение Z0 = (I; 1; 0; 1; 0; 1; 0; 1; 0; 0), f(z°) = 27.

В решении линейной задачи, у которой у® = уg = I, = 0, нет

необходимости. Поскольку

27 < /(ж0) < 27 і,

то задача решена, так как все значения Cj — целые числа. Для решения задачи решено шесть подзадач и выполнено три ветвления.

Пример 3.3. Найдем точное решение примера 2.6 с применением модифицированного алгоритма, описанного в 3.3.2,

f (ж) = бжі H- 5з?2 H- 2жз H- 3x4 H- 4з?5 H- 5жб H- 4^7 -I- Sxg H- 7жд -|- Зжю —^ шах,

01 (ж) = 2хі + 2ж2 + 2х3 + ж4 + 2ж5 + 2ж6 + 2ж7 + Зх$ + Зж9 + жю < 10,

02 (ж) — Жі + 3^2 + Зжз + 2^4 + 2х§ + 2ж6 + Ж7 + 4^8 + 2жд + 2жю ^ 7,

03 (ж) = 4жі +^2+ 2жз + 2^4 + 2х§ + ЗЖб + ЗЖ7 + 3xs + 2жд + ^io < 8,

Xj Є {0,1}, j = 1,2,...,10.

В отличие от примеров 3.1 и 3.2, этот пример не является иллюстративным, и его решение требует существенных затрат времени и вычислительных ресурсов.

В п. 2.2.6 было получено допустимое решение Z0 = (0; 0; 0; 0; 0; 0; I; I; 1; 0), f(z°) = 19. Далее будет показано, что это решение является оптимальным. Была также определена верхняя оценка из неравенства (2.2.8)

19 < f(x°) < min (27, 5; 24; 25).

Перед началом ветвления имеем

19 < f(x°) < 24.

Решение представлено на рис. 3.5 в виде дерева. Для каждой вершины указаны значение оценки и значение дробной переменной, по которой происходит разветвление. Фиксированные значения переменных указаны на дугах дерева. При получении недопустимого целочис-
88

Разд. II. Комбинаторные методы решения задач

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

у0-2 = (1; 0; 0; 0; 1/2; I; 1; 0; 1; 0).

Первое ветвление выполняется ПО переменной у5 = 1/2. Для вычисления оценок необходимо решить три задачи линейного программирования. Для подзадачи у® = 0 получаем оценку

19 < /(ж0) < 24 = min (27,5; 24; 24|) ,

для подзадачи у® = 1 получаем оценку

19 < /(ж0) < 23,5 = min (26,5; 23,5; 241) .

Для ветвления выбираем задачу с большей оценкой 24. Второе ветвление выполняется по переменной г/g = 1/4. Для подзадачи г/g = 0 получена оценка

21, 5 = min (2б|; 23 |; 21, б),

для подзадачи г/g = 1 — оценка

21,5 = min (27,5; 21,5; 24 |) .

После разветвления задачи с оценкой 24 получаем, что 19 < /(ж0) < 23,5,

HO поскольку все Cj целые, то

19 < f(x°) < 23.

Возвращаемся к задаче с оценкой 23, 5 и производим ветвление по переменной уq = 1/2. Получаем для подзадачи у^ = 0 оценку

23 = min (26 |; 23; 24 |),

для подзадачи уq = 1 — оценку
Предыдущая << 1 .. 24 25 26 27 28 29 < 30 > 31 32 33 34 35 36 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100