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

 

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

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

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 12 13 14 15 16 17 < 18 > 19 20 21 22 23 24 .. 84 >> Следующая


aJ (I ~ Sj) + CLj + CLjJj < R,

jew0 jeW\W° jei\w

s — 1

aj ~ aiTi <

J = I jew0 jei\w

Поскольку

s — 1

TO

J=I

Получаем

Д - ^ aJ5J + ^ - R'

jew0 jei\w

Y азЪ - Y aiSi - aSy0S'

jew0 jei\w

Вычислим разность:

5-1 5-1

/ (У°) ~f(x) = Y cJ + “ Y cJ + cJ5J - Y сзЪ ^

J = I J = I JGTy0 jGl\VT

^ “( Y а^з - Y aJsJj + Y cJ6J - Y cJ^J=

5 \ei\w jew0 ' jew0 jei\w

— Y^ — cj7j) + Y^ (cjsj ~ ^saj$j) =

jel\w jew0

— Y^ — ^J^ aJ^J ^J ~ ^s) aJSJ —

jel\w jew0

так как при j Є I\W имеем Xs — Xj > 0, а для j Є W0 имеем Xj > A5. Поэтому f(y°) — f(x) > 0, что и требовалось доказать.

2.2.5. Алгоритмы последовательного назначения единиц для приближенного решения задачи об одномерном ранце.

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

Правило 1. При построении допустимого целочисленного решения Z0 следует назначать единичные значения в соответствии с последовательностью Ajl > Aj2 > • • • > Xjn, начиная с наибольшего значения. Если для некоторого Xjk такое назначение выполнить невозможно, то полагаем z®k = 0 и переходим к номеру jk+i- Процесс
Гл. 2. Модели дискретного программирования

49

завершается после просмотра всех переменных или при нарушении условия (2.2.2). Это правило основано на доказанной теореме.

Рассмотрим примеры.

Пример 2.1.

бжі + 5з?2 + 2жз + 3x4 + 4^5 + 5ж6 H- 4^7 H- Sxg + 7жд -|- Зжю —У шах, 2xi H- 2x2 H- 2а?з + Ж4 + 2ж5 + 2xq + 2^7 + 3^8 + Зжд + Жю < 10,

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

Вычислим значения Aj-:

A1 =3, A2 = 5/2, A3 = 1, A4 = 3, A5 = 2, A6 = 5/2,

А7 = 2, Ag = 8/3, Ag = 7/3, Аю = 3. Дальнейшие вычисления сведем в табл. 2.1.

Таблица 2.1

А, Значения переменных у® f(y°) 9(У°)
Ai = 3 V0I=I 6 2
Il CO Il I—1 6 + 3 = 9 2 + 1 = 3
О Il CO 2/10 = 1 9 + 3 = 12 3 + 1=4
A8 = 8/3 «CS ООО Il I—1 12 + 8 = 20 4 + 3 = 7
A2 = 5/2 «с* ыо Il I—1 20 + 5 = 25 7 + 2 = 9
CT Il сл to Ув = (10-9)/2 = 0,5 25 + 0,5-5 = 27,5 9 + 0,5-2 = 10

Из табл. 2.1 получаем, что

У°з = V05 =V07= У°9 = 0.

Решение линейной задачи имеет вид

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

Допустимое целочисленное решение имеет вид

Z0 = (1; 1; 0; 1; 0; 0; 0; 1; 0; I), /(^0) = 25.

Поэтому можно записать 25 < f(x°) < 27, 5.

Полученное отклонение А = 2, 5 приближенного решения от оптимума можно улучшить, если обратить внимание на то, что все значения Cj целые. Поэтому

25 < f(x°) < 27.

Отметим, что в данном примере при R = 9 было бы получено точное решение х°. Первое правило последовательного назначения единичных значений в рассмотренном примере дало достаточно хороший результат. Рассмотрим другой пример, в котором полученное по этому правилу решение Z0 сильно отличается от оптимального.

4 И.Х. Сигал, А.П. Иванова
50 Разд. I. Предмет и модели дискретного программирования

Пример 2.2.

5xi + 200ж2 —>• max, bxi + 400ж2 < 401,

XjG {0,1}, j = 1,2.

Оптимальное решение: ж0 = (0,1), /(ж0) = 200. Воспользуемся правилом Данцига:

A1 = I, A2 =0,5, у0 = (1; 0,99), f(y°) = 203,

z° = (1; 0), /(z°) = 5, 5 < /(ж0) < 203.

Полученный «плохой» результат можно, по-видимому, объяснить большим разбросом в значениях элементов каждого из векторов с = = (Cl, с2) и а = (аі, а2). В первом примере такого разброса нет. Примеры 2.2 и 2.3 указывают второе правило последовательного назначения единичных значений в следующей последовательности: Cj1 > Cj2 > ...

* * * ^ cJn • В примере 2.2 по второму правилу получаем

Z0 = (0; I), f(z°) = 200, 200 < f(x°) < 203.

Рассмотрим пример 2.3, в котором разность /(ж0) — f(z°) может быть сделана сколь угодно большой при применении первого правила, а отношение f(z°)/f(x°) —>• 0.

Пример 2.3*).

Sxi + cIMx2 —>• max,

Xi + Mx2 < М, xj Є {0; 1}, І = 1,2; 2М > З,

M — сколь угодно большое положительное число. Воспользуемся первым правилом:

A1 =3, A2 =2, z° = (l,0), /(z°) = 3.

Оптимальное решение имеет вид

ж0 = (0,1), Дж°) = 2М,

поэтому

Iim ^SZ2 = Iim -^7 = 0, f(x°) — f(z°) = 2M — 3.

M^oo /(ж°) M^oo 2M ’ J J

Отсюда видно, что первое правило может давать сколь угодно «плохое» решение. Второе правило дает целочисленное оптимальное решение

ж0 = (0,1), f(x°) = 2М.

*)Дюбин Г.H., Корбут А.А. Жадные алгоритмы для задачи о ранце: поведение в среднем // Сибирский журнал индустриальной математики. — 1999. — Т. 2, № 2(4). — С. 68-93.
Гл. 2. Модели дискретного программирования

51

Линейное решение имеет вид

1/1 = 1. 2/2° = ^T1. f{y°)=iM + i.

Для первого правила получим 3 < f(x°) < 2M + I; А = 2M — 2; для

второго правила получим: 2M < f(x°) < 2M + I; А = 1.

Применим второе правило для примера 2.1. Вычисления сведем в табл. 2.2.

T а б л и ц а 2.2

cJ Значения булевых переменных f(z0) 9(*°)
C8 = 8 28 = 1 8 3
Cq — 7 *9=1 15 6
Cl = 6 Z01=I 21 8
С2 = 5 Z02 = 1 26 10
Z03 = Z04 = Z05 = Z06 =Z07=Z010= 0
Предыдущая << 1 .. 12 13 14 15 16 17 < 18 > 19 20 21 22 23 24 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100