Типовые процедуры решения задач дискретной оптимизации

 

Задача решается путем  последовательного, сверху вниз, заполнения строк таблицы стоимостей (таблица 1.4). В каждой клетке (k,p) данной таблицы вслед за полученным значением В*(k, p) в скобках малыми цифрами перечисляются номера предметов, которые согласно оптимальному решению частной задачи Z(k, p) следует положить в ранец. Если задача Z(k, p) имеет несколько оптимальных решений, то указывается только одно из них. Заполнение первой строки таблицы выполняется в соответствии с формулой (3.4); здесь считается, что в нашем распоряжении имеется только предмет П₁, его стоимость равна 7 и вес равен 4. Предмет П₁ можно положить в ранец, если дозволенный вес предметов в ранце не меньше чем 4. Поэтому В*(1, 1)= 0 и В*(1, p) = 7, если p 4. Заполнение второй и каждой из нижеследующих строк выполняется в соответствии с формулой (3.5). Рассмотрим в качестве иллюстрации, причем на содержательном уровне, как заполняется клетка (3, 15). Данная клетка соответствует задаче Z(3, 15). В сравнении с задачей Z(2, 15), которой соответствует клетка (2, 15), в Z(3, 15) появляется новая возможность – в ранец можно положить предмет П₃ . Согласно формуле (3.5), выбирается лучший из двух вариантов. Первый вариант предполагает, что возможностью положить в ранец предмет П₃ мы не воспользовались. Тогда имеет место абсолютно та же ситуация, что в задаче Z(2, 15), и мы можем обеспечить суммарную стоимость предметов в ранце равную В*(2, 15), т.е. числу 17, записанному в клетке, расположенной непосредственно над заполняемой. Итак, первый вариант обеспечивает суммарную стоимость предметов в ранце, равную 17; реализация данного варианта означает, что в ранец кладутся предметы П₁ и П₂. Второй вариант предусматривает, что предмет П₃, его стоимость 15, кладется в ранец. Вес предмета П₃ равен 11. Поэтому от заполняемой клетки в четвертой строке перемещаемся на 11 клеток влево, оказываемся в столбце, соответствующем оставшемуся резерву веса ранца после того, как в него положен предмет П₃; непосредственно над полученной клеткой, а именно в клетке (2, 5) записано число 7, это максимально возможная суммарная стоимость предметов, взятых из совокупности {П₁, П₂}, при условии, что их суммарный вес не превышает пять (в этой ситуации как показывает заполнение клетки (2, 5), из указанной совокупности следует взять первый предмет). Таким образом, второй вариант обеспечивает суммарную стоимость предметов в ранце 7 + 15=22; реализация данного варианта означает, что в ранец кладутся предметы П₁ и П₃. Второй вариант дает лучший результат, заполнение клетки (3, 15) осуществляется по этому варианту.

 

Некоторые действия, выполненные нами при решении примера, являются излишними. Для решения КЗР все клетки таблицы стоимостей заполнять не обязательно. В последней строке нам достаточно заполнить только одну, крайне правую клетку (n, W). Согласно формуле (3.5), для этого достаточно знать содержимое только двух клеток предпоследней строки, а именно клетки (n-1, W) и клетки (n-1, W-v_n). Для заполнения указанных клеток предпоследней строки достаточно знать заполнение максимум четырех клеток строки n-2, и т.д. Процессу счета по соотношениям      динамического      программирования (3.4)-(3.5) целесообразно предварить процесс разметки, когда двигаясь по строкам таблицы снизу вверх, мы отмечаем, заполнение каких клеток таблицы действительно необходимо для решения заданной КЗР.

 

 

4. Решение задачи о ранце методом ветвей и границ

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

В данном разделе будет  рассмотрен такой же пример, как  и в пункте 3. Ниже повторно приведем условие задачи.

В машину грузоподъемностью 35 т. загрузить предметы с наибольшей суммарной ценой (полезностью). Характеристика предметов дана в таблице:

Номер предмета	1	2	3	4	5	6
Вес                                  (т.)	4	7	11	12	16	20
Цена                          (тыс. руб.)	7	10	15	20	27	34

 т.

Подберем какой-нибудь вариант, чтобы его оценку использовать как  первую границу при отсечении  ветвей. В дальнейшем эта оценка может изменяться, если в процессе анализа будет получено лучшее решение. Итак, загружаем самый тяжелый (шестой) груз ( ). Остаток грузоподъемности равен т. Теперь можно загрузить третий груз ( ). Остаток грузоподъемности равен т. Единственная оставшаяся возможность – догрузить первый груз ( ).

Получили вариант загрузки 6–3–1,       т. .

 – значение целевой функции.

Начинаем строить дерево и оценивать ветви. Первый шаг  показан на рис.1.

 

 

 

 

 

 

 

 

Рис.1

 

Дерево строится перевернутым – корни вверху, ветви внизу: так  удобнее их строить. Каждый кружок изображает некоторое состояние. Внутри кружка записываются номер груза, добавляемого на очередном шаге, и его количество. Над кружками через вертикальную черту показываются: слева – достигнутая  загрузка ранца (машины), справа – суммарная  цена (полезность) загруженных предметов. Корень дерева фиксирует начало построения. Загружено 0 предметов (внутри кружка), общая загрузка 0 т (слева над кружком), общая цена 0 (справа над кружком).

Производим первое ветвление, в данном случае дихотомию: берем  или не берем самый тяжелый (шестой) груз. Слева: шестой груз берется (1), при  этом в машину будет загружено 20 т и цена будет равна 34. Справа: шестой груз не берется (0), загрузка и цена равны нулю.

Дальнейшее построение дерева показано на рис.2.

 

Рис.2.

 

Над состоянием (6-1) производим дихотомию, пытаясь загрузить пятый груз. Налево  (5-1), направо (5-0). Но ветвь (5-1) недопустима, т.к. при этом будет загружено 36 т, что превышает грузоподъемность (35 т). Ветвь (5-1) отсекается, на рисунке зачеркивается. Дальнейшее развитие системы показано на рис.3.

Рис.3.

 

Рассматриваем ветвь (6-1)–(5-0). Так как пятый предмет не берется, загрузка машины и общая цена груза не изменяются, над состоянием (5-0) записаны те же числа (20/34), что и над предыдущим состоянием (6-1).

Строим ветви из состояния (5-0), дихотомия (4-1) и (4-0). Вариант (4-1) возможен, но неэффективен. У состояния (4-1) нет дальнейшего развития, т. к. загрузка равна 32 т, оставшаяся грузоподъемность равна т. и ни одного предмета догрузить нельзя. Допустимая цена груза равна , где 56 – полученная нами предварительная оценка целевой функции. Поэтому вариант (4-1) отбрасывается.

Развиваем состояние (4-0). Две ветви (3-1) и (3-0). Анализируем (3-1): загрузка 31, цена 49.  Развиваем (3-1) на две ветви (2-1) и (2-0). Состояние (2-1) имеет загрузку 38 т., превышающую грузоподъемность.  Ветвь (2-1) недопустима и поэтому отбрасывается.

Из (2-1) возвращаемся назад в (3-1) и идем по правой ветви в (2-0), у которой грузоподъемность и оценка равны соответственно 31/49. Из состояния (2-0) есть два пути: (1-1) и (1-0). Оценка  (1-1) равна 35/56, допустима загрузка, а цена не меньше установленной оценки 56. Оставляем ветвь (1-1) для дальнейшего анализа. Т. к. (1-1) не имеет продолжений, возвращаемся обратно в (2-0) и анализируем вариант (1-0). Он допустим, но по цене 49 меньше оценки 56, поэтому вариант (1-0) отбрасывается.

Проанализируем, как мы двигались  по дереву. Начиная от корня (0), пошли  вниз и налево. И так всегда –  при анализе нового состояния  производили дихотомию и двигались  по левой ветви, оставляя правую для  дальнейшего анализа. Как только упирались в тупик, из которого дальнейшее движение вниз невозможно, как, напр., из состояний (5-1),  (4-1), (2-1) и (1-1), то возвращались на шаг назад и начинали анализировать свободную (неразвитую) правую ветвь. Такой принцип (справа налево, а потом направо) не единственный, но нужен какой-то принцип, чтобы не запутаться и не оставить ни одной ветви без анализа.

Из достигнутого состояния (1-0) возвращаемся обратно в (2-0), но нет неанализированных (свободных) ветвей. Последовательно возвращаемся обратно, но свободную ветвь находим только в самом корне (0). Следовательно, все варианты от (0) в направлении (6-1) рассмотрены и лучшим оказался вариант (6-3-1), который был нами выявлен в предварительном анализе. Переходим к анализу состояния (6-0). На рисунок 4 перенесем дерево с рисунка 3, оставив только продуктивные ветви, т.е. такие, которые допустимы и увеличивают загрузку и цену.

Рис.4.

 

Состояние (6-0) анализируется так же, как раньше анализировалось (6-1). Обрывается ветвь от (4-1) на (3-1), т.к. загрузка превышает грузоподъемность ( ). Состояние (2-1) оказывается конечным, т.к. достигнута загрузка 35 т и больше ничего загрузить нельзя. Но в состоянии (2-1) цена равна 57, что больше, чем в найденном ранее варианте (6-3-1). Поэтому ветвь (6-1)-(3-1)-(1-1) отбрасываем (зачеркиваем). Лучшим становится вариант (5-4-2) с загрузкой 35 т и ценой 57. Изменяем теперь оценку границы с 56 на 57. Это значит, что ветви, по которым невозможно превысить цену 57, должны быть отброшены.

Из (2-0) возвратимся в состояние (4-0) и оценим его перспективность. Загрузка (4-0) равна 16, а цена 27. Оставшаяся свободная грузоподъемность равна т. Наибольший прирост цены можно получить, догрузив предметы 3 и 2; при этом цена возрастет на 25 и станет равна , что меньше уже достигнутой цены 57. Следовательно, ветвь на (4–0) бесперспективна и ее нужно оборвать.

Возвращаемся в состояние (5-0) с загрузкой 0 и ценой 0. Оставшиеся предметы  (4, 3, 2, 1) имеют общий вес 34, и их можно погрузить. При этом цена груза составит , что меньше 57. Значит, эта ветвь не перспективна, обрываем ее. Отсечение особенно успешно было проведено в состояниях (5-0) и (4-0), что существенно сократило перебор.

Оптимальным по цене оказался вариант загрузки предметов 5, 4 и 2, общий  вес при котором равен 35 т, а  цена 57. Применение метода ветвей и  границ дает уверенность, что оптимальный  вариант не потерян.

 

Заключение

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

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

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

Очевидным недостатком алгоритма  метода ветвей и границ при решении  задач большой размерности является необходимость перебрать слишком большое количество вариантов перед тем, как будет найден оптимальный план. Однако он отчасти может быть преодолен, если ограничиться поиском не оптимального, а просто «хорошего» (близкого к оптимальному) плана. О степени такой близости и скорости приближения к экстремуму нетрудно судить по изменению значений оценок.

 

 

Список используемой литературы

1. Коган Д. Задачи и методы конечномерной оптимизации. –Н.Н : Издательство Нижегородского Университета, 2004.
2. Таха Х. Введение в исследование операций.–М.: Мир,1985.
3. Кузнецов Ю. Н. Математическое программирование. –М.: Наука,1976.
4. Вентцель Е. С. Исследование операций. –М.: Наука,1976.
5. Вентцель Е. С. Элементы динамического программирования. –М.: Наука,1987.
6. Акоф Р., Сасиени М. Основы исследования операций. –М.: Мир,1971.
7. Вентцель Е. С. Исследование операций: задачи, принципы, методология. –М.: Наука,1988.
8. Карманов В. Т. Математическое программирование. –М.:Наука,1986.
9. Зайченко Ю. П. Исследование операций. –К.: Высшая школа,1985.
10. Аоки М. Введение в методы оптимизации. –М.: Наука,1977.
11. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. –М.: Наука,1965.
12. Муну М. Математическое программирование. Теория алгоритмов. –М.: Наука,1990.