Задача 7. Максимальная подпоследовательность. Дана числовая последовательность, требуется найти длину наибольшей возрастающей подпоследовательности.

Задача 8. В условиях двухпроцессорной задачи мастера требуется построить оптимальное расписание обслуживания заявок 1 – 6 со следующими характеристиками: а (1) = 4, τ (1) = 1; а (2) = 7, τ (2) = 2; а (3) = 8, τ (3) = 3; а (4) = 4, τ (4) = 3; а (5) = 10, τ (5) = 5; а (6) = 17, τ (6) = 4.

Задача 9. Записать рекуррентные соотношения динамического программирования для решения трехпроцессорной задачи мастера.

Задача 10. Обобщенная на случай нелинейных функций индивидуального штрафа однопроцессорная задача мастера определяется следующими исходными данными: обслуживанию подлежат заявки 1, 2, 3, 4; продолжительности обслуживания заявок: τ (1) = 4, τ (2) = 1, τ (3) = 3, τ (4) = 1; функции индивидуального штрафа: ϕ ₁(t) = 4 t ², ϕ ₂(t) = 3 t, ϕ ₃(t) = 2 t ² + t, ϕ ₄(t) = t ² + 2 t. Требуется найти оптимальное расписание обслуживания.

Задача 11. Задача однопроцессорного обслуживания множества заявок с минимаксным критерием определяется следующими исходными данными: обслуживанию подлежат заявки 1, 2, 3, 4, 5; продолжительности обслуживания заявок: τ (1) = 3, τ (2) = 2, τ (3) = 4, τ (4) = 1, τ (5) = 2; функции индивидуального штрафа: ϕ ₁(t) = 4 t ², ϕ ₂(t) = 3 t, ϕ ₃ (t) = t ² + t, ϕ ₄(t) = t ² +2 t, ϕ ₅ (t) = t ³ + 1. Требуется найти оптимальное расписание обслуживания.

Задача 12. Задача однопроцессорного обслуживания множества заявок при наличии директивных сроков определяется следующими исходными данными: τ (1) = 4, d (1) = 5; τ (2) = 3, d (2) = 6; τ (3) = = 5; d (3) = 9; τ (4) = 2, d (4) = 9; τ (5) = 3; d (5) = 10; τ (6) = 4; d (6) = 12; τ (7) = 4; d (7) = 13; τ (8) = 4, d (8) = 15. Найти расписание, обеспечивающее выполнение в срок максимально возможного числа заявок.

Задача 13. Записать соотношения динамического программирования для решения задачи двухпроцессорного обслуживания множества заявок при наличии директивных сроков. В этой задаче для каждой заявки i, i = 1,..., n, считаются заданными продолжительность обслуживания τ (i) и директивный срок d (i); требуется построить расписание, минимизирующее число нарушений пред-писанных заявкам директивных сроков.

Задача 14. Каноническая задача однопроцессорного обслуживания потока из шести заявок характеризуется следующими данными: t (1) = 0, τ (1) = 3, а (1) = 4; t (2) = 0, τ (2) = 4, а (2) = 7; t (3) = 1, τ (3) = = 1, а (3) = 8; t (4) = 3, τ (4) = 2, а (4) = 7; t (5) = 5, τ (5) = 3, а (5) = 3; t (6) = 5, τ (6) = 2, а (6) = 7. Методом динамического программирования (обратный счет) требуется определить оптимальное расписание обслуживания.

Задача 15. Каноническая задача однопроцессорного обслуживания потока из шести заявок характеризуется следующими данными: t (1) = 0, τ (1) = 2, а (1) = 3; t (2) = 1, τ (2) = 4, а (2) = 7; t (3) = 1, τ (3) = = 1, а (3) = 8; t (4) = 3, τ (4) = 2, а (4) = 7; t (5) = 5, τ (5) = 3, а (5) = 3; t (6) = 5, τ (6) = 2, а (6) = 7. Методом динамического программирования (прямой счет) требуется определить оптимальное рас-писание обслуживания.

Задача 16. В задаче однопроцессорного обслуживания потока заявок с линейными функциями индивидуальных штрафов и директивными сроками в совокупности расписаний, обеспечивающих соблюдение максимального числа сроков, найти последовательность обслуживания с минимальным значением суммарного штрафа по заявкам. Характеристики заявок следующие: t (1) = 0, τ (1) = 3, ϕ ₁(t) = t, d (1) = 5; t (2) = 2, τ (2) = 3, ϕ ₂(t) = 4 t, d (2) = 5; t (3) = 3, τ (3) = 4, ϕ ₃(t) = 2 t, d (3) =7; t (4) = 4, τ (4) = 3, ϕ ₄(t) = 3 t, d (4) = 9; t (5) = 6, τ (5) = 1, ϕ ₅(t) = 4 t, d(5) = 7.

Задача 17. Записать рекуррентные соотношения динамического программирования для задачи распределения заявок потока R = = {1, 2,..., n } между двумя идентичными параллельными процессорами. Считается, что каждый процессор обслуживает направляемые ему заявки в порядке возрастания их номеров. Каждая заявка i характеризуется тремя целочисленными параметра-ми: t (i) − момент поступления в систему обслуживания (0 = = t (1) ≤ t (2) ≤ … ≤ t (n – 1) ≤ t (n)); τ (i) − требуемая продолжительность обслуживания любым из процессоров (τ (i) > 0); a (i) − штраф за единицу времени пребывания в системе обслуживания. Минимизируемым критерием является суммарный штраф по всем заявкам.