Методические указания по выполнению курсовых работ по курсу (стр. 2 из 6)
Режим обучения:
Пользователь выбирает следующее добавляемое в остов ребро, если ребро выбрано правильно, то оно выделяется цветом, если не правильно, то пользователь предупреждается об этом. Пометки пересчитываются программой.
2. Задача о ранце
Постановка задачи
Задача о ранце является одной из классических комбинаторных задач оптимизации, в рамках данного курса мы будем рассматривать только одномерную задачу о ранце. Содержательная постановка одномерной задачи: дан набор из n предметов, каждый из которых имеет цену ci и вес wi (i=1,2…n), в ранец, имеющий грузоподъемность Wmax, нужно загрузить предметы таким образом, чтобы суммарная ценность предметов в рюкзаке была максимальной. Математическая формулировка задачи представлена в (1), также эта задача называется задачей о 0-1 ранце или целочисленной задачей о ранце (иногда также задачей о рюкзаке).
 | (1) |
 |
Задача о ранце относится к классу NP-трудных задач, следовательно не имеет алгоритма, находящего оптимальное решение задачи за время, полиномиально зависящее от числа входных параметров, то есть в данном случае от числа предметов в наборе – n.
Методы решения
- Метод ветвей и границ
Основной идеей данного метода является ограничение полного перебора за счет разбиения множества решений на подмножества, получения оценок содержащихся в подмножестве решений и отбрасывании непереспективных подмножеств. Более подробно этот метод можно посмотреть в работах [4, 5, 6].
Применительно к задаче о ранце, дихотомическое разбиение на подмножества осуществляется по принципу присутствия/отсутствия текущего предмета в ранце. Соответственно, все множество решений делится на решения, содержащие текущий предмет и не содержащие его. Оценка решений, содержащихся в подмножестве и приведение вида задачи, производится на основании теоремы Данцига [6].
Теорема (правило) Данцига:
Пусть переменные хj
пронумерованы так, что 
, где 
. Тогда оптимальное решение 
имеет вид: 
 | (2) |
где s определяется из условия:
 | (3) |
Приведение задачи осуществляется согласно правилу Данцига, то есть переменные хj
перенумеровываются так, что 
, где 
.В качестве вершины ветвления выбирается предмет с номером s.
Верхняя оценка подмножества получается при добавлении в решение дробной части предмета с номером s.
 | (4) |
Нижняя оценка – при подсчете цен только целых предметов
 | (5) |
Шаг 1. Приводим задачу согласно правилу Данцига.
Шаг 2. Выбираем вершину ветвления
согласно условию (3).Шаг 3. Получаем верхнюю и нижнюю оценки задачи на текущем шаге по формулам (4) и (5). Исключаем из дальнейшего рассмотрения ветви, для которых полученная верхняя оценка меньше или равна нижней оценке для некоторой другой ветви.
Ветвление также не проводится если верхняя и нижняя оценка в одном направлении совпали – это значит, что по данному направлению достигнут максимум целочисленной задачи.
Шаг 4. Производим процедуру ветвления: для одной ветви устанавливаем
, для другой 
. Для каждого направления повторяем шаги 2-4.Указания по отображению процесса поиска решения:
Режим демонстрации:
Отображать приведенную задачу. Помечать вершины ветвления
соответствующим номером переменной. Для каждой вершины ветвления отображать верхнюю и нижнюю оценки. Помечать ребра ветвления цифрами или цветом (например, если переменная добавляется в решение , то ребро имеет пометку 1, нет – 0). Тупиковые вершины помечать цветом. Отображать оптимальное решение.Режим обучения:
Пользователь выбирает вершину ветвления
(номер переменной), если вершина выбрана правильно, то для идущих из нее ветвей вычисляются верхняя и нижняя оценки, если не правильно, то пользователь предупреждается об этом. Пользователь также производит отбрасывание неперспективных направлений ветвления, если отбрасывание произведено не правильно или пользователь продолжает ветвление в неперспективном направлении, то он предупреждается об этом. Пользователь выбирает ветку с оптимальным решением.- Метод динамического программирования
Метод динамического программирования близок к методу ветвей и границ в том смысле, что также ограничивает перебор решений. Для задачи о ранце процесс поиска решения при помощи динамического программирования является псевдополиномиальным.
Основная идея этого метода состоит в составлении рекуррентных соотношений согласно принципу оптимальности Беллмана: завершающая часть оптимального решения также должна быть оптимальной. Более подробно этот метод можно посмотреть в работах [3, 4, 5, 6].
Рекуррентное соотношение для задачи о ранце выглядит следующим образом:
 ,  | (6) |
При граничных условиях:
 | (7) |
Значение, полученное в результате вычисления соотношения (6), является оптимальным решением исходной задачи.
Часто процедура поиска решения при помощи динамического программирования записывается в табличном виде, однако в данной работе будем использовать для отображения процесса дерево.
Алгоритм состоит в последовательном вычислении соотношений (6).
Указания по отображению процесса поиска решения:
Режим демонстрации:
Отображать задачу. Вершины ветвления (кроме начальной) помечать соответствующим номером добавляемой в решение переменной
. Помечать ребра значениями [ 
, 
] или 0, если достигнуты граничные условия. Ветви с наибольшей ценностью помечать цветом. Отображать оптимальное решение.Режим обучения:
Пользователь помечает вершины ветвления, программа проставляет метки на ребрах. Если вершина выбрана не правильно, то пользователь предупреждается об этом. Пользователь выбирает ветку с оптимальным решением.
3. Задача коммивояжера
Постановка задачи
Еще одной классической комбинаторной задачей оптимизации является задача коммивояжера.
Задача формулируется так: в полном взвешенном графе с n вершинами необходимо найти гамильтонов цикл с минимальным суммарным весом входящих ребер. Вес ребра (i, j), соединяющего вершины с номерами i и j обозначается как
‑ это расстояние между вершинами 
: 
. Математическая формулировка задачи представлена в формулах (8) и (9), причем условие (9) является условием отсутствия повторений в решении, то есть наличием единственного цикла.