Семинар 3- задание

Задание
1. Выбрать один из 1 вариантов (см. ниже) задания, за исключением разобранного примера

2. Выполнить реализацию примера, используя методические указания 

Методические указания 

Цель задания: Освоить применение динамического программирования (ДП) для решения базовых задач исследования операций. Научиться формализовать задачу, выявлять оптимальную подструктуру, строить и заполнять таблицы решений в Excel.

Ключевые принципы ИО, применяемые в ДП:

  1. Оптимальность Беллмана: Оптимальное решение задачи обладает тем свойством, что каково бы ни было первоначальное состояние и первоначальное решение, последующие решения должны составлять оптимальную политику относительно состояния, полученного в результате первого решения.

  2. Многоэтапность принятия решений: Задача разбивается на этапы (шаги). На каждом этапе принимается решение, которое влияет на состояние системы.

  3. Целевая функция: Функция, которую необходимо оптимизировать (максимизировать прибыль, минимизировать затраты или время).

Общий алгоритм выполнения в Excel:

  1. Определите этапы (Stages): Что представляет собой один шаг? (например, распределение ресурса на один проект, планирование одного временного периода).

  2. Определите состояния (States): Что характеризует систему на каждом этапе? (например, количество доступных ресурсов, оставшееся время).

  3. Определите решение (Decision): Какое решение принимается на каждом этапе? (например, сколько ресурсов выделить на проект).

  4. Выведите рекуррентное соотношение: Как целевая функция на текущем этапе зависит от решений и состояния?

  5. Постройте таблицу в Excel:

    • Строки: Возможные состояния на текущем этапе.

    • Столбцы: Возможные решения на текущем этапе.

    • Ячейки: Значение целевой функции для данного состояния и решения + оптимальное значение с предыдущих этапов.

  6. Найдите глобальный оптимум: Ответом является значение в ячейке, соответствующей начальному состоянию на последнем этапе.

Базовая реализация (Пример для варианта №1)

Задача: "Задача о распределении инвестиций" (Упрощенная версия)

Условие: Инвестор имеет 5 млн. долл. (W = 5), которые можно распределить между тремя проектами. Прибыль от каждого проекта в зависимости от вложенной суммы известна. Найти план распределения, максимизирующий суммарную прибыль.

x (вложения)012345
f₁(x)0357810
f₂(x)046789
f₃(x)024689

Реализация в Excel (модуль "Поиск решения" не требуется, используется чистое ДП):

  1. Этапы: Проекты (3, 2, 1).

  2. Состояние (w): Количество миллионов, доступных для распределения на текущем и всех предыдущих проектах.

  3. Решение (x_i): Сколько миллионов выделить на i-й проект.

  4. Рекуррентное соотношение:

    • dp_i(w) = max_{0 ≤ x ≤ w} [ f_i(x) + dp_{i+1}(w - x) ]

    • dp_4(w) = 0 (базовый случай: после всех проектов прибыль равна 0)

Структура листа Excel:

  • Лист "Этап 3" (последний проект): Рассчитывается dp_3(w) = f₃(w) для всех w от 0 до 5.

  • Лист "Этап 2": Таблица с состояниями w (0..5) и решениями x (0..w). Формула в ячейке: =f₂(x) + VLOOKUP(w-x, 'Этап 3'!A:B, 2, FALSE). Затем для каждого w находится MAX по всем x.

  • Лист "Этап 1": Аналогично этапу 2. Ответ находится для w=5.

10 вариантов заданий равной сложности (Исследование операций)

  1. Задача о загрузке (Рюкзак 0-1). Судно имеет грузоподъемность W. Есть n грузов, каждый имеет вес w_i и стоимость c_i. Максимизировать общую стоимость груза без перегрузки. (dp[i][j] = max( dp[i-1][j], c_i + dp[i-1][j - w_i] )).

  2. Задача о планировании производства. Необходимо составить план производства на n месяцев. Известны: затраты на производство, стоимость хранения единицы продукции, спрос. Минимизировать общие затраты (производство + хранение). (dp[month][inventory] = min_{produce} [ prod_cost(produce) + hold_cost(inventory) + dp[month+1][inventory + produce - demand] ]).

  3. Задача замены оборудования. Требуется составить план замены оборудования возраста a на T лет. Известны: стоимость нового оборудования, доход от оборудования в зависимости от возраста, стоимость обслуживания, продажная стоимость. Максимизировать чистый доход за период. (dp[year][age] = max( keep: income(age) - maint_cost(age) + dp[year+1][age+1], replace: income(0) - new_cost + sell_price(age) + dp[year+1][1] )).

  4. Задача управления запасами. Определить объем заказа на каждом из n периодов, чтобы удовлетворить спрос d_t с минимальными затратами (заказ + хранение). Есть ограничение на складскую емкость. (dp[period][start_inv] = min_{order} [ order_cost(order) + hold_cost(end_inv) + dp[period+1][end_inv] ], где end_inv = start_inv + order - d_t).

  5. Задача о назначениях. Имеется n работ и n исполнителей. Каждый исполнитель выполняет каждую работу с разной эффективностью c[i][j]. Назначить исполнителей на работы так, чтобы минимизировать суммарные затраты. (dp[mask] - минимальная стоимость назначения первых k исполнителей на работы, заданные битовой маской mask).

  6. Задача о рекламных кампаниях. Имеется бюджет B. Есть n рекламных площадок. Для каждой известна функция clicks_i(x) — количество кликов в зависимости от вложенной суммы x. Максимизировать общее количество кликов. (Аналогично задаче о распределении инвестиций).

  7. Задача о маршрутизации (кратчайший путь). Найти путь от узла A до узла B в сети с минимальной общей длиной/стоимостью. (dp[node] = min_{prev_node} [ dp[prev_node] + cost(prev_node, node) ]). Решается алгоритмом Беллмана.

  8. Задача календарного планирования (Deadline). Есть n заказов. По каждому известна длительность d_i, дедлайн deadline_i и штраф p_i за просрочку. Найти порядок выполнения, минимизирующий суммарный штраф. (Использовать ДП по битовым маскам: dp[mask][time] - мин. штраф для набора заказов mask, законченных к времени time).

  9. Задача о разбиении множества. Можно ли разбить множество натуральных чисел на два подмножества с равными суммами? (dp[i][s] = true, если сумму s можно получить из первых i элементов. dp[0][0]=true).

  10. Задача о надежности системы. Система состоит из n последовательно соединенных элементов. Для повышения надежности можно добавить параллельно дубликаты для каждого элемента. Задана стоимость добавления k дубликатов к i-му элементу и вероятность его безотказной работы. Максимизировать надежность системы при ограничении на общую стоимость. (dp[i][budget] = max_{spent} [ rel_i(k) * dp[i+1][budget - spent] ]).

Детализация варианта 1 (Задача о рюкзаке) в Excel

Цель: Наглядно продемонстрировать заполнение таблицы ДП.

Шаги реализации:

  1. Входные данные: Создайте таблицу с n строками (предметы) и колонками: Вес (w_i), Стоимость (c_i).

  2. Таблица ДП: Создайте двумерную таблицу. Строки i = 0..n (предметы), столбцы j = 0..W (доступный вес).

  3. Базовый случай: Заполните первую строку (i=0): dp[0][j] = 0 для всех j.

  4. Рекуррентное соотношение: В ячейке B3 (соответствующей i=1, j=0) формула:
    =ЕСЛИ(B$1 >= $A3; МАКС(B2; $D3 + СМЕЩЕНИЕ($A$2; $A3-1; B$1 - $A3)); B2)

    • B$1 - ссылка на доступный вес (заголовок столбца).

    • $A3 - ссылка на вес текущего предмета (предполагается, что в столбце A указаны веса).

    • B2 - значение ячейки прямо сверху (dp[i-1][j]).

    • $D3 - стоимость текущего предмета.

    • СМЕЩЕНИЕ(...) - находит значение dp[i-1][j - w_i].

  5. Автозаполнение: Скопируйте эту формулу на всю таблицу.

  6. Ответ: Находится в ячейке на пересечении i=n и j=W.


Последнее изменение: Воскресенье, 21 сентября 2025, 16:04