Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Задачи к главе 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) задана. Требуется записать рекуррентные соотношения динамического программирования для определения маршрута, минимального по количеству выполняемых тонно-километров.

3. Записать рекуррентные соотношения динамического программирования для классической задачи о ранце, дополненной условием: из каждой пары предметов (П 1, Пn), (П 2, Пn -1), …, (Пk, Пn-k +1) в ранец можно.поместить только один предмет, здесь kn /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. Классические задачи, решаемые методом динамического программирования.

План лекции:

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

Формальная формулировка задачи динамического программирования.

Принцип оптимальности Беллмана.

История.

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

План решения задачи методом динамического программирования.

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

Числа Фибоначчи.

Черепашка.

Подпалиндром.


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал