Материал: ОиММПР. Лекция 1

Однокритериальные задачи (задачи с одной целевой функцией)

•Задача линейного программирования. Целевая функция — линейная, множество допустимых решений — плоский или выпуклый многогранник.

•Задача квадратичного программирования. Целевая функция — квадратичная

•Задача стохастического программирования. Это подобные линейным задачи с неизвестными числовыми параметрами, о которых имеются статистические данные, либо их получают в процессе решения.

•Задача дискретного программирования. Множество допустимых решений — дискретное множество.

•Задача целочисленного программирования. Множество допустимых решений

— точки целочисленной решетки.

•Задача булева программирования. Множество допустимых решений — матрицы из 0 и 1.

11 из 28

Задача оптимизации решений

Задача принятия решения

Пара (Ω, Ρ),

где Ω – множество вариантов, Р – принцип оптимальности.

Решением задачи является множество ΩРΩ , полученное в соответствии с принципом оптимальности Р.

Основная задача теории оптимальных решений состоит в представлении обоснованных количественных данных и рекомендаций для принятия оптимальных решений. Отсутствие хотя бы одного из элементов (Ω, Ρ) лишает задачу смысла.

Математическим выражением принципа оптимальности Р служит функция выбора Ср, которая со всеми подмножествами Х Ω составляет его часть Ср(х), из которых и находится оптимальное решение исходной задачи Ср,оптим(Ω).

12 из 28

Классы задач принятия решений

По полноте исходных данных

Задачи принятия решения различаются в зависимости от информации о множестве

Ωи принципе оптимальности Р:

1.Общая задача принятия решения: Ω, Р – неизвестны, необходимо получить ΩР в процессе самого решения.

2.Задача с известным, но ограниченным множеством Ω называется задачей выбора решения.

3.Задача, в которой Ω, Ρ – известны называется задачей оптимизации решений.

13 из 28

По времени и срокам

1.Долгосрочное стратегическое планирования:

задачи размещения обьектов производства в телекоммуникациях — узлов доступа разного уровня, развитие региональной телекоммуникационной сети.

2.Среднесрочное планирование:

задачи маршрутизации трафика, задачи планирования инвестиционного строительства (с ограниченными ресурсами), задачи планирования текущего бюджета.

3.Оперативное управление:

задачи текущего ремонта и устранения повреждений на сети, задачи распределения материалов на текущие нужды — установки и ремонт, транспортные задачи.

14 из 28

По типу постановки

Распределительная задача

Имеем

n — число предприятий;

Y — количество единиц некоторого ресурса;

fk(x) — количество продукции, которое будет произведено на k-м предприятии, если в него будет вложено x единиц ресурса (монотонно неубывающая функция).

Требуется: оптимизировать число единиц ресурса xi, выделяемого каждому предприятию, с целью достижения максимума объема выпускаемой ими продукции

15 из 28