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

 

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

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

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 46 47 48 49 50 51 < 52 > 53 54 55 56 57 58 .. 84 >> Следующая

150

Разд. III. Приближенные методы и алгоритмы

T а б л и ц а 5.2

Новые номера I 2 3 4 5 6 7 8 9 10
Значения Cj 8 7 6 5 5 4 4 3 3 2
Значения dj 21 18 16 14 13 11 10 8 5 2
dj/f(x') 1,10 0,94 0,84 0,73 0,68 0,58 0,52 0,42 0,26 0,11
m/(j є) 6 7 8 10 10 12 14 17 28 70

dj

дены значения . / . и целые части значении

/(* о

т _ т _ m^Cj _ 3 - 47 _ 141 Iе f(x') _ dj dj dj dj

E cJ /(*')

Из двух последних строк следует, что при ? < 0, 68 все переменные могут быть существенными в силу необходимого условия (5.4.10). Из первых трех столбцов видно, что лишь в этих случаях число г-существенных переменных меньше, чем 10. Этот экспериментальный результат подтверждает теоретический вывод о том, что при малых значениях 7 < 0, 5 оценка трудоемкости (5.4.14) не лучше оценки трудоемкости полного перебора. Полученный результат этого примера тем более неудовлетворителен, что начальное решение х' есть оптимальное решение задачи.

Из анализа примеров видно, что очень важным является выделение класса задач о ранце, для которых может быть получена нетривиальная нижняя оценка для п?.
Глава 6

Алгоритмы гарантированного функционирования

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

6.1. Задача об одномерном ранце

Рассмотрим алгоритмы типа «greedy» для этой задачи.

6.1.1. Задача об одномерном целочисленном ранце. Задача имеет вид

п

/ (xi,x2, ...,Xn)= Y1 сзхз тах>

3=і

п

Y aJxJ < ь?

J=I

Cj >0, 0 < dj < Ъ, Xj > 0 целые, j = 1, 2,..., п.

Предполагается, что Ь/а\ > 1.

Определение. Алгоритм А приближенного решения задачи называется е-оптималъным (є > 0), если он вырабатывает целочисленное решение х =(хі, Х2, • • •, хп) такое, что

/ («-/(*) < е (6 11)

X0 = (х\, X2ч • • •, хп) — оптимальное целочисленное решение, f(x°) >

> 0. Решение X = (жі, Х2,..., хп) будем называть е-оптималъным.

Предположим, что Ai > Л2 > • • • > An, Xj = Cj-/?, и рассмотрим аналог алгоритма Данцига. В этом алгоритме в указанной последовательности, начиная с j = 1, назначаем Xj = e(b/dj) и полагаем b равным b — CLjXj] здесь е(«) — целая часть. Если такое назначение вы-
152

Разд. III. Приближенные методы и алгоритмы

полнить невозможно, то полагаем Xj = 0; в обоих случаях переходим к номеру j + 1.

Теорема 6.1. Пусть х° = (xj, х\,..., X0n) — оптимальное целочисленное решение задачи о целочисленном ранце, х = (жі,Х2,...

..., хп) — решение, полученное по описанному алгоритму. Тогда решение х является є-оптимальным при ? = 1/2.

Доказательство. Для оптимального решения х° получаем

п п п

f(x°) = Y cJxJ = EJ aJxJ ^JE aJxJ j=і j=і 3 j=і

Так как в решении х переменная х\ = е(Ь/а\), то f(x) > c\e(b/ai), поэтому

Cie (Ь/dl) < f(x) < / (ж0) < Cib/ai.

Поскольку Ь/аі > 1, то е{Ъ/а\)/{Ъ/а\) = /3 > 1/2. Поэтому f(x°) - f(x) = _ /(ж) _ Cie (b/ai) = _ я 1

/(*°) /(ж0)” cib/oi 2 ’

и теорема доказана.

Предположим, что Ci > С2 > • • • > сп. В этом случае результат, аналогичный предыдущему, может быть получен лишь при дополнительном предположении а\ = ат[п = min aj, I < j < п. Это предположение позволяет рассмотреть только очень узкий класс задач об одномерном целочисленном ранце. Рассмотрим алгоритм формирования приближенного решения, в котором назначение значений переменных происходит в указанной последовательности. Начиная с номера j = = 1 назначаем Xj = e(b/ai) и полагаем b равным b — CLjXj. Если такое назначение выполнить невозможно, то полагаем Xj= 0 и переходим kj-|-1. Для оптимального решения X0 получим

п п

/ (х°) = CjX0j =EJ aJxJ -^~ь= ^b-

Ui tbmm U1

J = I J = I

Так как в решении х переменная х\ = е(Ь/аі), то f(x) > сіе(Ь/аі), и аналогично предыдущему получим

Cie (b/ai) < f(x) < f (х°) < b=—b.

Ctmin CL I

Поэтому получим

/ (д?°) - /О) _ / (х) Cie(b/ai) _ e(b/ai)_ e(b/ai) I

f (х°) f (х°) — cib/amin b/amin b/ai ~ 2’

так как bja\ > I.

Сформулируем полученный результат в виде теоремы.

Теорема 6.2. Если с\ > C2 сп и а\ = ат-ш = minO7-,

I < j < nJ т° описанный алгоритм вырабатывает є-оптимальное решение X = (жі, Ж2, ..., хп) при ? = 1/2.
Гл. 6. Алгоритмы гарантированного функционирования 153

6.1.2. Задача об одномерном булевом ранце. Рассмотрим задачу об одномерном булевом ранце

п

f (x) = Yl С3Х3 ШаХ5

5>Л<ь, (61-2)

Cj > 0, 0 <ctj<bj, Xj Є {0,1}, j = l,2,...,n,

и предположим, что b = b(k) = aifc, к > 1. Тогда 1 < к < ко, где

\ Л Qj- Q-

ко < 3. Пусть, как и ранее, A7- = —, Ai > A2 > ... > An. Условие

а\ aj

г-оптимальности имеет вид (6.1.1). Для нахождения допустимого бу-

левого решения х =(жі, ж2,..., жп) воспользуемся правилом Данцига.

Тогда жі = I, f(x) > Cl. Для оптимального булевого решения имеет

место оценка f(x°) < — b = Cik < Cifco, поэтому с\ < f (х) < f (х°) < а\

< с\ко. Обозначим г0 = 1 — —.

ко

Теорема 6.3. Для задачи об одномерном булевом ранце при 1 < к < ко алгоритм, основанный на правиле Данцига, дает ?о~оптимальное решение х.
Предыдущая << 1 .. 46 47 48 49 50 51 < 52 > 53 54 55 56 57 58 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100