Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Задачи к главе 1
|
|
1. Имеются сферы капиталовложений S 1, S 2, S 3, S 4; в каждую из них может быть внесен целочисленный вклад, не превосходящий 5. Величина подлежащего распределению капитала равна 12. Функции, определяющие доходы, получаемые при вложении в имеющиеся сферы вклада u, заданы приведенной таблицей. Прямым методом Беллмана требуется найти оптимальное распределение капитала между сферами вложений.
Таблица значений функций дохода ft (u)
| u | f 1(u) | f 2(u) | f 3(u) | f4(u) |
| 0, 1 | 0, 1 | 0, 2 | ||
| 0, 3 | 0, 1 | 0, 2 | ||
| 0, 3 | 0, 4 | 0, 3 | 0, 3 | |
| 0, 4 | 0, 4 | 0, 3 | 0, 4 | |
| 0, 5 | 0, 4 | 0, 3 | 0, 4 |
2. Автомобиль, начиная от базы и заканчивая на базе замкнутый маршрут, должен доставить с базы в точки Т 1, Т 2, …, Тm некоторые грузы. Известно, что вес направляемого в точку Тi груза равен сi, i = 1, …, m. Выполняя тот же маршрут, автомобиль должен собрать в точках R 1, R 2, …, Rn грузы, адресованные базе. Известно, что вес груза, направляемого из точки Rj на базу, равен wj, j=1, …, n. Через каждую из перечисленных точек маршрут должен проходить однократно. Матрица расстояний S размера (m + n + 1)× (m + n + 1) задана. Требуется записать рекуррентные соотношения динамического программирования для определения маршрута, минимального по количеству выполняемых тонно-километров.
— Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
— Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
— SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней. Зарегистрироваться и Начать продвижение
3. Записать рекуррентные соотношения динамического программирования для классической задачи о ранце, дополненной условием: из каждой пары предметов (П 1, Пn), (П 2, Пn -1), …, (Пk, Пn-k +1) в ранец можно.поместить только один предмет, здесь k ≤ n /2.
4. Решить задачу о ранце:
7 х 1 + 4 х 2 + 4 х 3 + 5 х 4 + 2 х 5 + 3 х 6 → max
при условиях
2 х 1 + х 2 + 2 х 3 + 4 х 4 + 3 х 5 + 2 х 6 ≤ 10;
хi Î {0, 1}, i=1, …, 5.
5. Решить следующую модификацию классической задачи о ранце:
5 х 1 + 2 х 2 + 4 х 3 + 7 х 4 + 5 х 5 → max
при условиях
2 х 1 + х 2 + 2 х 3 + 4 х 4 + 3 х 5 ≤ 12;
хi Î {0, 1}, i = 1, 2, 5;
хi Î {0, 1, 2}, i = 3, 4.
6. Имеется множество недробимых камней { К 1, К 2, …, К 8}. Веса камней (в порядке возрастания индексов) следующие: 7, 5, 8, 4, 3, 6, 3, 1. Требуется разбить совокупность { К 1, К 2, …, К 8} на два подмножества так, чтобы суммарный вес камней одного подмножества минимально отличался от суммарного веса камней другого подмножества.
7. Задан взвешенный ориентированный граф с двумя выделенными вершинами, s и t. Веса дуг – это их длины; вес каждой дуги – положительное число. Требуется найти самый длинный простой (т.е. без самопересечений) путь, начинающийся в вершине s и заканчивающийся в вершине t. Записать рекуррентные соотношения динамического программирования для решения задачи.
8. Взвешенный ориентированный граф G задан матрицей
Числовой элемент mij матрицы М равен весу дуги (i, j) графа G; если дуга (i, j) в графе отсутствует, то mij = ∞. Веса дуг трактуются как их длины. Требуется найти расстояния от вершин 1 и 2 до остальных вершин графа.
— Разгрузит мастера, специалиста или компанию;
— Позволит гибко управлять расписанием и загрузкой;
— Разошлет оповещения о новых услугах или акциях;
— Позволит принять оплату на карту/кошелек/счет;
— Позволит записываться на групповые и персональные посещения;
— Поможет получить от клиента отзывы о визите к вам;
— Включает в себя сервис чаевых.
Для новых пользователей первый месяц бесплатно. Зарегистрироваться в сервисе
9. Найти оптимальную схему перемножения матриц М 1, М 2, М 3, М 4 и М 5 размеров 10× 20, 20× 15, 15× 5, 5× 2 и 2× 10 соответственно.
10. Найти устойчивое назначение, максимизирующее суммарную производительность участников при условии, что матрица производительностей А и матрица балльных оценок В определены следующим образом:
Тема 3. Классические задачи, решаемые методом динамического программирования.
План лекции:
Динамическое программирование.
Формальная формулировка задачи динамического программирования.
Принцип оптимальности Беллмана.
История.
Классические задачи динамического программирования.
План решения задачи методом динамического программирования.
Примеры типичных задач, решаемых при помощи динамического программирования.
Числа Фибоначчи.
Черепашка.
Подпалиндром.
|
|