Бронов С.А. Исследование операций

Подождите немного. Документ загружается.

Бронов, С. А. Исследование операций: конспект лекций

2) выявить информацию, необходимую для получения допустимых ре-

шений на текущем этапе без повторной проверки решений, принятых на

предыдущих этапах.

Выделение этапов не может быть полностью формализовано ввиду раз-

нообразия решаемых данным методом задач и требует творческого подхода.

6.1.2 Задача о загрузке (задача о рюкзаке)

Задача о загрузке формулируется следующим образом: имеется ёмкость

ограниченной вместимости, а также предметы нескольких типов, различных

(но одинаковых внутри типа) по размерам (или массе) и стоимости; требуется

найти наилучшее сочетание этих предметов, обеспечивающее наибольшую

стоимость всей загрузки.

Задача о загрузке возникает, например, при использовании кораблей в

торговом флоте, транспортных самолётов, железнодорожных вагонов и т. п.

Формально вводятся обозначения:

— общий объём (или допустимая суммарная масса);

— число типов грузка;

m — число предметов i-го типа;

r — прибыль, которую приносит один предмет i -го типа;

w — объём (или масса) одного предмета i -го типа.

Требуется максимизировать

max

2211







iinn

mrmrmrmrz 

при условии

Wmwmwmwmw

iinn





1

2211

 ,

где

m ,

m ,…,

m ≥0 — целые числа.

Три указанные выше составляющие метода динамического программи-

рования представляются следующим образом:

1 Этап

ставится в соответствие предмету

-го типа,

=1,2,…,

, т. е.

этапов столько же, сколько типов предметов. На каждом этапе рассматрива-

ется вариант загрузки только предметов одного типа (в дополнение к уже за-

груженным предметам на предыдущих этапах).

2 На каждом i -ом этапе рассматриваются варианты решения, которые

представляются количеством предметов

m , подлежащих загрузке. Соответ-

ствующая прибыль равна

mr . Значение

m — целое и определяется удель-

ными характеристиками (габаритами, весом)

w предметов соответствующе-

Бронов, С. А. Исследование операций: конспект лекций

го

-го типа с учётом ограничений на вместимость

. Поэтому















m0 , где













— целая часть дроби в скобках. Т. е. при этом рас-

сматривают все варианты — от "нулевой загрузки" (т. е. когда предметы дан-

ного типа не загружаются вообще) до полной загрузки только предметами

этого типа, а также все промежуточные.

3 Состояние

x на рассматриваемом i -ом этапе представляет собой сум-

марный вес (объём) предметов всех типов, загруженных ранее и загружае-

мых на данном этапе. Это состояние должно удовлетворять условию

Wmw





1

, где

— число уже загруженных предметов.

В общем виде решение задачи о загрузке ищется в рекуррентной форме,

так как решение на каждом новом этапе зависит от решения на предыдущем

этапе.

Решение начинается с последнего этапа



и движется к первому эта-

пу



. Это — совершенно условное положение, так как под этапом пони-

мают рассмотрение загрузки предмета конкретного типа, а их можно прону-

меровать произвольным образом. Поэтому такое отражение движения приня-

то для удобства математических обозначений.

Обозначим через )(

xf максимальную суммарную прибыль от ранее

рассмотренных этапов







Тогда рекуррентная формула для этого решения через найденное ранее

)(

11  ii

xf :





)(max)(

,,1,0























iiii

xfmrxf







где для начального случая )(

xf , когда формально необходимо знать

)(

11  nn

xf , принято 0)(



 nn

xf .

Эта формула имеет следующее значение. В её правой части указана

функция поиска и выделения максимума среди вариантов решения. Она ра-

ботает на отдельных этапах:

на этапе



загружаются предметы n-го типа;

на этапе





загружаются предметы (n–1)-го типа в дополнение к

ранее загруженным предметам n-го типа;

на этапе





загружаются предметы (n–2)-го типа в дополнение к

ранее загруженным предметам n-го и (n–1)-го типов и т. д.

На каждом последующем этапе (при переходе к загрузке предметов но-

вого типа) осуществляется перебор вариантов их количества:

Бронов, С. А. Исследование операций: конспект лекций















m ,,1,0 

и для этих случаев рассчитываются соответствующие состояния (общий вес)

,,1,0





а также суммарная прибыль

mr , которая суммируется с прибылью на

предыдущем этапе (от уже загруженных предметов) )(

11  ii

xf .

Эта формула применяется для первого этапа, когда 0)(



 nn

xf .

Для последующих этапов формула преобразуется следующим образом.

Загруженный на i-ом этапе вес равен разности получившегося веса

x и

имевшегося ранее веса

1i

x , т. е. загруженный вес

iiii

mwxx





1

откуда

iiii

mwxx





1

Тогда рекуррентная формула перепишется следующим образом:





)(max)(

,,1,0

iiiiii

mwxfmrxf































Следовательно, на каждом i-ом этапе в рассмотрении участвуют данные

этого этапа (справа в формуле). Рекуррентность формул — характерная черта

динамического программирования.

Пример 6.2. Самолёт имеет грузоподъёмность



тонны. Его ис-

пользуют для перевозки крупногабаритных (тяжёлых) предметов трёх типов

(



). Каждый i-ый тип предметов характеризуется весом

w и прибылью

от перевозки одного предмета этого типа

r , где



. Задача: найти

наилучшее сочетание количества перевозимых предметов для получения

максимальной прибыли.

Исходные данные по предметам приведены в таблице:

Предмет

Вес одного предмета

w ,

тонн

Прибыль от перевозки

одного предмета

Так как речь идёт о целых неделимых предметах, то состояния

x могут

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

решалась бы как обычная непрерывная задача линейного программирования.

Бронов, С. А. Исследование операций: конспект лекций

Решение формально начинается с последнего этапа (так выполняется

нумерация типов).

Этап 3. Рассматривается загрузка предметов 3-го типа. Пока никакие

другие предметы не загружены. Поэтому как вариант проверяется возмож-

ность загрузки только предметами 3-го типа. Максимальное число предметов

3-го типа, которые поместятся в самолёт, составляет































m .

Поэтому возможные варианты загрузки:



m , 1



m , 2



m , 3



m , 4



m .

Вариант 0



m означает, что предмет 3-го типа вообще не загружается.

Вариант 4



m означает, что загружаются только предметы 3-го типа.

Остальные варианты предполагают, что наряду с предметами 3-го типа

будут загружаться предметы других двух типов.

Поскольку рассматривается первый этап, то состояние

333

mwx



(на

других этапах будут учитываться другие типы предметов, если таковые по-

явятся).

Следующие уравнения используются для перебора вариантов на данном

этапе:

}56,42,28,14,0{max}14{max}{max)(

4,,1,0

333







mmm

mmrxf ;

4}4,3,2,1,0max{}max{



m .

Все расчёты можно представить в следующей таблице:

iii

mmr 14



Оптимальное

решение



m 2



max{})(





1 2 3 4 5 6 7 8

—

Где



m — возможные оптимальные решения.

Колонка 1 заполняется как последовательность вариантов нагрузки.

Колонки с 2 по 6 заполняются по формуле

m14 , в каждой колонке с 2 по

6 приводятся одни и те же значения, так как рассматривается начальный

Бронов, С. А. Исследование операций: конспект лекций

этап, и до него ещё ничего не было загружено. Прочерки означают, что рас-

положенные выше варианты загрузки отсутствуют.

В колонке 7 записаны максимальные значения из приведённых в соот-

ветствующих строках. В колонке 8 записаны соответствующие им значения

m .

Этап 2. Рассматривается загрузка предметов 2-го типа. Расчёты выпол-

няются по формулам:









)3(47max)(max)(

2232

4,3,2,1,0

1,0

222322

,,1,0

mxfmmwxfmrxf





























1}1,0max{

,0max,,1,0max}max{























































m  .

Дальнейшие расчёты можно представить в следующей таблице:

)3(47

2232

mxfm





Оптималь

ное

решение



m 1



max{})(





1 2 3 4 5 6 7 8

0+0=0

—

0+14=14

—

0+28=28

—

0+42=42

47+0=47

0+56=56

47+14=61

Здесь существует всего два варианта использования предметов 1-го типа

(из-за их веса и ограничений на общий вес) — 0



m или 1



m (т. е. вооб-

ще не загрузить или загрузить 1 предмет). Судя по данным колонки 7,

наибольшие значения получаются при 1



m .

Этап 1. Рассматривается загрузка предметов 1-го типа. На последнем (в

данном случае) этапе используются формулы:









)2(31max)(max)(

1121

4,3,2,1,0

2,1,0

111211

,,1,0

mxfmmwxfmrxf





























2}2,1,0max{

,1,0max,,1,0max}max{























































m  .

Дальнейшие расчёты можно представить в следующей таблице:

Бронов, С. А. Исследование операций: конспект лекций

)2(31

1121

mxfm





Оптимальное

решение



m 1



m 2



max{})(





1 2 3 4 5 6 7 8

0+0=0

—

0+14=14

—

0+28=28

31+0=31

0+4

0+56=56

62+0=62

Оптимальные решения были найдены для каждого этапа.

Далее ищется общее оптимальное решение на основе просмотра частных

решений в обратном порядке.

На этапе 1 было найдено оптимальное решение 2





m (т. е. два предме-

та 1-го типа должны быть загружены, чтобы обеспечить в конечном итоге

наибольшую прибыль).

Для этапа 2 это означает, что 02242

112





mxx , т. е. дозарузка

на этапе 2 не нужна ( 0





m ) и предметы 2-го типа не должны загружаться.

Для этапа 3 это означает, что 00303

223





mxx , т. е. дозарузка

на этапе 3 не нужна ( 0





m ) и предметы 3-го типа не должны загружаться.

Таким образом, общее оптимальное решение: 2





m , 0





m , 0





m .

При динамическом программировании выполняется упорядочение пере-

бора вариантов и уменьшение ветвления процесса перебора, что ускоряет

вычисления.

Бронов, С. А. Исследование операций: конспект лекций

Список литературы

Таха, Хемди А. Введение в исследование операций / Хемди А. Таха. —

7-е изд. — М. ; СПб. ; Киев: Издательский дом "Вильямс", 2005. — 912 с. —

ISBN 5-8459-0740-3.