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

• Название: 1. Постановка и особенности задач дискретного
• Дата: 15.12.2020
• Размер: 177.02 Kb.
• Имя файла: lect.pdf
• Тип: Задача; #160820
• страница: 2 из 3

3. Задача о ранце
Задача об одномерном ранце. Пусть имеется
n
предметов, каждый из которых имеет ценность
0
>
j
c
и вес
n
j
a
j
,...,
2
,
1
,
0
=
>
. Имеется ранец рюкзак, грузоподъемность которого
R
, при этом
∑
=
>
n
j
j
R
a
1
, те. все предметы в ранец положить невозможно. Необходимо положить в ранец набор предметов с максимальной суммарной ценностью. Введем переменных
0
=
j
x
, если предмет с номером
j
не кладется в ранец,
1
=
j
x
, если предмет с номером
j
кладется в ранец,
n
j
,...,
2
,
1
=
. После введения этих переменных суммарная ценность и грузоподъемность соответственно имеют вид 2
1
,...,
,
,
(
)
∑
=
=
n
j
j
j
n
x
a
x
x
x
g
1 Поэтому задача об одномерном ранце имеет вид, (3.1)
15

R
x
a
n
j
j
j
≤
∑
−
1
, (3.2)
{ }
n
j
x
j
,...,
2
,
1
,
1
;
0
=
∈
. (Естественно предположить, что Множество допустимых решений этой задачи – это множество мерных булевых векторов
(
)
n
x
x
x
x
,...,
,
2 1
=
, удовлетворяющих условию (3.2). Вместе с задачей (3.1)-(3.3) будем рассматривать задачу линейного программирования, в которой вместо условий (3.3) вводятся условия 0
=
≤
≤
. (Существование допустимого решения. В задаче (3.1)-(3.3) допустимое решение всегда существует (например, нулевое. Если решить задачу линейного программирования (3.1)-(3.4) ив полученном оптимальном решении заменить дробные значения
j
x
нулевыми, то получим допустимое решение задачи (3.1)-(3.3). Отсев подмножеств булевых векторов, не содержащих оптимальных решений Рассмотрим вектор
(
)
n
x
x
x
x
,...,
,
2 1
=
, имеющий единиц и нулей. Если вектор
x
является допустимым (те. условие
(3.2.) выполнено, то можно исключить из дальнейшего рассмотрения векторов, получающихся из
x
заменой любого числа единиц нулями, так как для любого такого вектора
x
значение функции
( )
x
f
будет меньше, чем
( )
x
f
. Если вектор
x
не является допустимым (те. условие (3.2) не выполняется, то можно исключить из дальнейшего рассмотрения векторов, которые получаются из
x
заменой любого числа нулей единицами, так как все эти векторы недопустимы.
Оценка точности приближенных булевых решений. Пусть
(
)
0 0
2 0
1 0
,...,
,
n
z
z
z
z
=
- допустимое булево решение задачи (3.1)-(3.3);
(
)
0 0
2 0
1 0
,...,
,
n
x
x
x
x
=
- оптимальное булево решение
(
)
0 0
2 0
1 0
,...,
,
n
y
y
y
y
=
- оптимальное решение задачи (3.1)-(3.4). Тогда имеет место следующее неравенство

( ) ( ) ( )
0 0
0
y
f
x
f
z
f
≤
≤
. (3.5) Величина
( ) ( )
0 0
z
f
y
f
−
=
∆
есть гарантированная оценка отклонения приближенного решения от оптимума Нахождение вектора
0
y
связано с решением задачи линейного программирования. Далее будет показано, что задача (3.1)-(3.4) решается просто.
Алгоритм Данцига для линейной одномерной задачи о ранце.
Рассмотрим задачу линейного программирования (3.1)-(3.4) и опишем алгоритм нахождения оптимального решения
(
)
0 0
2 0
1 Теорема (правило Данцига). Пусть переменные
n
j
x
j
≤
≤
1
,
перенумерованы так, что
n
λ
λ
λ
≥
≥
≥
2 1
, где
j
j
j
a
c /
=
λ
. Тогда оптимальное решение
(
)
0 0
2 0
1 0
,...,
,
n
y
y
y
y
=
имеет вид 0
1 0
2 0
1
=
=
=
=
−
s
y
y
y
,
0 0
0 2
0 1
=
=
=
=
+
+
n
s
s
y
y
y
,
s
s
j
j
s
a
a
R
y
/
1 1
0




−
=
∑
−
=
,
где
s
определяется из условия Смысл этого правила очевиден. Единичные значения следует последовательно назначать переменным, начиная с наибольшей удельной ценности (ценности на единицу веса, при этом
( )
s
s
j
j
s
s
j
j
a
a
R
c
c
y
f
/
1 1
1 Если все компоненты
n
j
y
j
,...,
2
,
1
,
0
=
целые (число дробных компонент не больше одной, то
0 0
x
y
=
; если
1 0
0
<
<
s
y
, то план получится при
0 0
=
s
y
, тогда

( ) ( )
s
s
j
j
s
a
a
R
c
z
f
y
f
/
1 1
0 Алгоритмы последовательного назначения единиц для приближенного решения задачи об одномерном ранце.
Прямые алгоритмы В алгоритмах этого типа в качестве начального рассматривается нулевой вектор, в котором переменным присваиваются единичные значения в соответствии с заданными правилами.
Правило 1. При построении допустимого целочисленного решения следует назначать единичные значения в соответствии с последовательностью
n
j
j
j
λ
λ
λ
≥
≥
≥
2 1
, начиная с наибольшего значения. Если для некоторого такое назначение выполнить невозможно, то полагаем
0 0
=
k
j
z
и переходим к номеру
1
+
k
j
. Процесс завершается после просмотра всех переменных или при нарушении условия. Это правило основано на теореме, приведенной выше.
Рассмотрим примеры.
Пример 3.1.
max
3 7
8 4
5 4
3 2
5 6
10 9
8 7
6 5
4 3
2 1
→
+
+
+
+
+
+
+
+
+
x
x
x
x
x
x
x
x
x
x
,
10 3
3 2
2 2
2 2
2 10 9
8 7
6 5
4 3
2 1
≤
+
+
+
+
+
+
+
+
+
x
x
x
x
x
x
x
x
x
x
,
{ Решение. Вычислим значения
j
λ
:
3 1
=
λ
,
2
/
5 2
=
λ
,
1 3
=
λ
,
3 4
=
λ
,
2 5
=
λ
,
2
/
5 6
=
λ
,
2 7
=
λ
,
3
/
8 8
=
λ
,
3
/
7 9
=
λ
,
3 10
=
λ
. Дальнейшие вычисления сведены в табл. Таблица Значения переменных
0
j
y
( )
0
y
f
( )
0
y
g
3 1
=
λ
1 0
1
=
y
6 2
3 4
=
λ
1 0
4
=
y
6+3=9 2+1=3 3
10
=
λ
1 0
10
=
y
9+3=12 3+1=4 3
/
8 8
=
λ
1 0
8
=
y
12+8=20 4+3=7 18

2
/
5 2
=
λ
1 0
2
=
y
20+5=25 7+2=9 2
/
5 6
=
λ
(
)
5
,
0 2
/
9 10 0
6
=
−
=
y
25+0,5*5=27,5 Из табл. 3.1 получаем, что 0
9 0
7 0
5 Решение линейной задачи имеет вид 0
=
y
,
( )
5
,
27 Допустимое целочисленное решение имеет вид 0
=
z
,
( )
25 Поэтому можно записать
( )
5
,
27 25 Полученное отклонение
5
,
2
=
∆
приближенного решения от оптимума можно улучшить, если обратить внимание на то, что все значения
j
c
целые. Поэтому )
27 25 Отметим, что в данном примере прибыло бы получено точное решение
0
x
. Первое правило последовательного назначения единичных значений в рассмотренном примере дало достаточно хороший результат. Рассмотрим другой пример, в котором полученное поэтому правилу решение
0
z
сильно отличается от оптимального.
Пример 3.2.
max
200 5
2 1
→
+
x
x
,
401 400 5
2 1
≤
+
x
x
,
{ Решение Оптимальное решение
( )
1
,
0 0
=
x
,
( )
200 Воспользуемся правилом Данцига:
1 1
=
λ
,
5
,
0 2
=
λ
,
(
)
99
,
0
;
1 0
=
y
,
( )
203 0
=
y
f
,
( )
0
;
1 0
=
z
,
( )
5 0
=
z
f
,
( )
203 Полученный плохой результат можно, по-видимому, объяснить большим разбросом в значениях элементов каждого из векторов
(
)
2 1
, c
c
c
=
и
(
)
2 1
, a
a
a
=
. В первом примере такого разброса нет. Пример 3.2 указывает
19

второе правило последовательного назначения единичных значений в следующей последовательности
n
j
j
j
c
c
c
≥
≥
≥
2 1
. В примере 3.2 по второму правилу получаем )
1
;
0 0
=
z
,
( )
200 0
=
z
f
,
( )
203 200 Применим второе правило для примера 3.1. Вычисления сведены в табл. Таблица Значения булевых переменных )
0
z
f
( )
0
z
g
8 8
=
c
1 0
8
=
z
8 3
7 9
=
c
1 0
9
=
z
15 6
6 1
=
c
1 0
1
=
z
21 8
5 2
=
c
1 0
2
=
z
26 10 0
0 10 0
7 0
6 0
5 0
4 Получено допустимое целочисленное решение 0
=
z
,
( )
26 0
=
z
f
;
( )
27 26 0
≤
≤
x
f
Сформулируем второе правило последовательного назначения единиц.
Правило 2. Назначения единичных значений выполняются в соответствии с последовательностью
n
j
j
j
c
c
c
≥
≥
≥
2 Можно предложить и другие правила. По-видимому, не представляется возможным указать наилучшее правило из заданного их набора для решения конкретной задачи. Но всегда возможно применение всех правил из набора к этой задаче и выбор лучшего из полученных результатов. Алгоритмы, основанные на описанных здесь правилах, получили название алгоритмов типа «greedy» (жадные, пожирающие алгоритмы. Основная особенность этих алгоритмов состоит в том, что глобальная оптимизация целевой функции заменяется многошаговой локальной оптимизацией на каждом шаге

Рассмотрим модификации правили, которые в ряде случаев позволяют улучшить допустимые целочисленные решения
0
z
. Эти модификации предполагают фиксацию каждой из переменных последовательно назначениях и 1, значения других переменных определяются с помощью правили В примере 3.1 положим
0 0
10
=
z
, остальные значения определим по правилу 1. Вычисления сведены в табл. 3.3.
Таблица Значения булевых переменных )
0
z
f
( )
0
z
g
3 10
=
λ
0 0
10
=
z
0 0
3 1
=
λ
1 0
1
=
z
6 2
3 4
=
λ
1 0
4
=
z
9 3
3
/
8 8
=
λ
1 0
8
=
z
17 6
2
/
5 2
=
λ
1 0
2
=
z
22 8
2
/
5 6
=
λ
1 0
6
=
z
27 10 0
0 9
0 7
0 5
0 Получено допустимое целочисленное решение 0
=
z
,
( )
27 0
=
z
f
,
которое в силу условия
( )
27 27 0
≤
≤
x
f
оптимально, те.
0 Рассмотрим применение правила 2 для этого же примера при
0 0
8
=
z
; здесь Вычисления сведены в табл. 3.4.
Таблица3.4
j
c
Значения булевых переменных )
0
z
f
( )
0
z
g
8 8
=
c
0 0
8
=
z
0
0
7 9
=
c
1 0
9
=
z
7
3
6 1
=
c
1 0
1
=
z
13
5
5 2
=
c
1 0
2
=
z
18
7
5 6
=
c
1 0
6
=
z
23
9
4 5
=
c
0 0
5
=
z
23
9
21

4 7
=
c
0 0
7
=
z
23
9
1 10
=
c
1 0
10
=
z
26
10
0 0
4 Получено булево решение 0
=
z
,
( )
26 совпадающее с полученным в табл. 3.2 по значению целевой функции.
Рассмотренные алгоритмы решения одномерной задачи о ранце получили название эвристических Под эвристическими понимаются алгоритмы, основанные на правдоподобных, ноне обоснованных строго предположениях о свойствах оптимального решения задачи. В первом правиле алгоритм точного решения задачи (3.1)-(3.4) переносится на формирование допустимого целочисленного решения задачи (3.1)-(3.3), в результате такого перенесения получается эвристический алгоритм для задачи (3.1)-(3.3). Полученное целочисленное решение может оказаться сильно отклоняющимся от оптимального. Причина такого поведения эвристического алгоритма состоит, по-видимому, в том, что любая эвристика верна лишь в некоторой, неизвестной, как правило, области изменения параметров задачи.
Двойственные алгоритмы Рассмотренные ранее алгоритмы типа
«greedy» часто называют прямыми. В алгоритмах этого типа формирование допустимого решения
0
z
начинается с нулевого вектора, те. реализуется процедура подъема по допустимым целочисленным решениям. Формирование допустимого решения
0
ω
в двойственных алгоритмах начинается с вектора
x
, все компоненты которого равны 1. Замена единиц нулями начинается с наименьшего значения
j
λ
(или
j
c
) по возрастанию значений, те. реализуется процедура спуска по недопустимым целочисленным векторам

В примере 3.1 положим
0 0
10
=
z
, остальные значения определим по правилу 1. Вычисления сведены в табл. Таблица Значения булевых переменных )
x
f
( )
x
g
10
,...,
2
,
1
,
1
=
=
j
x
j
47 20 1
3
=
λ
0 3
=
x
45 18 2
5
=
λ
0 5
=
x
41 16 2
7
=
λ
0 7
=
x
37 14 3
/
7 9
=
λ
0 9
=
x
30 11 2
/
5 6
=
λ
0 6
=
x
25 Получено двойственное допустимое решение 0
=
ω
,
( ) ( )
25 Из табл. 3.5 видно, что на последнем шаге можно получить
0 2
=
x
, тогда двойственное решение имеет вид 0
=
ω
,
( )
25 0
=
ω
f
,
0 Для иллюстрации работы двойственного алгоритма рассмотрим пример Пример 3.3.
max
4 6
3 2
1
→
+
+
x
x
x
,
3 2
2 3
2 1
≤
+
+
x
x
x
,
{ Решен и е.
Поскольку
1
,
2
,
3 3
2 1
=
=
=
λ
λ
λ
, то прямой алгоритм дает допустимое решение 0
=
z
,
( )
7 0
=
z
f
,
(
)
0
;
5
,
0
;
1 0
=
y
,
( )
8 Вычисления для двойственного алгоритма сведены в табл. Таблица Значения булевых переменных )
x
f
( )
x
g
23

j
λ
3
,
2
,
1
,
1
=
=
j
x
j
11 5
1 3
=
λ
0 3
=
x
10 4
2 2
=
λ
0 2
=
x
6 Получено двойственное решение 0
=
ω
,
( )
6 0
=
ω
f
,
0 0
j
j
z
≤
ω
,
( ) ( )
0 Для изучения отношения
( ) ( )
0 0
/
z
f
f
ω
рассмотрим пример Пример 2
3 2
1
→
+
+
x
x
x
γ
,
2 2
3 2
1
≤
+
+
x
x
x
γ
,
{ }
3
,
2
,
1
,
1 Решение Поскольку
2 1
=
λ
,
2
/
3 2
=
λ
,
1 3
=
λ
, то
(
)
1
;
0
;
1 0
=
z
,
( )
1 Для определения
0
ω
вычисления сведены в табл.3.7.
Таблица Значения булевых переменных )
x
f
( )
x
g
3
,
2
,
1
,
1
=
=
j
x
j
4 2
+
γ
γ
+
3 1
3
=
λ
0 3
=
x
3 2
+
γ
γ
+
2 2
/
3 2
=
λ
0 Получено решение для двойственного алгоритма 0
=
ω
,
( )
γ
ω
2 0
=
f
,
0 0
j
j
z
≤
ω
,
;
3
,
2
,
1
=
j
( ) ( )
0 0
z
f
f
<
ω
,
( )
( )
0 1
2 2
lim lim
0 0
0 Наряду с задачей об одномерном ранце рассматривается задача о многомерном ранце Упражнения для самостоятельного решения

Методом Данцига решить задачи о ранце. max
2 7
15 13 11 9
17 7
6 5
4 3
2 1
→
+
+
+
+
+
+
x
x
x
x
x
x
x
,
15 2
6 5
4 3
7 7
6 5
4 3
2 1
≤
+
+
+
+
+
+
x
x
x
x
x
x
x
,
{ }
7
,...,
2
,
1
,
1
;
0
=
∈
j
x
j
3.6. max
3 10 20 10 40 60 60 7
6 5
4 3
2 1
→
+
+
+
+
+
+
x
x
x
x
x
x
x
,
10 3
4 4
5 3
7 6
5 4
3 2
1
≤
+
+
+
+
+
+
x
x
x
x
x
x
x
,
{ }
7
,...,
2
,
1
,
1
;
0
=
∈
j
x
j

1   2   3