Общая постановка задачи оптимизации презентация

Математическая задача оптимизации

Ограниченное применение метода дифференцирования для решения задачи оптимизации

Ограниченное применение метода дифференцирования для решения задачи оптимизации

Этапы постановки и решения оптимизационных задач

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

В интересах покупателей применяется критерий минимума стоимости передачи энергии всех сетевых предприятий, по которому определяются транспортные потоки мощностей

пропорциональность – эффект влияния переменной задачи пропорционален значению этой переменной;
аддитивность – эффект влияния нескольких переменных задачи равен сумме эффектов от каждой переменной;

делимость – все основные переменные задачи могут принимать произвольные вещественные значения в определенном диапазоне (бесконечно делимы).

                                     ,

задача максимизации ЛП

при ограничениях

задача минимизации ЛП

при ограничениях

−заданные параметры

− условие неотрицательности переменной

− целевая функция

− переменные

Вектор доставляющий максимум (минимум) функции z при заданных ограничениях, называется оптимальным решением задачи ЛП.

Наибольшее (наименьшее) значение целевой функции
называется значением задачи ЛП.

Решить задачу ЛП − означает найти оптимальное реше-
ние и значение целевой функции.

Алгоритм графического метода для задач ЛП :

записать каждое ограничение как равенство и нарисовать прямую;
найти для каждого ограничения допустимую область и множество допустимых решений задачи ЛП;
найти градиент целевой функции

нарисовать линию уровня целевой функции

сдвигать линию уровня в направлении градиента, до последней точки пересечения с множеством доп. решений.

Задача ЛП имеет бесконечное множество решений (пример 2.4.3) (альтернативные решения).

Задача ЛП не имеет оптимального решения вследствие:
неограниченности множества допустимых решений
пустоты множества.

Если на переменную не накладывается условие неотрицательности, то ее можно заменить разностью двух неотрицательных переменных:

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

Знак неравенства можно заменить на противоположный, умножив данное неравенство на (-1)!

Утверждение.
Если задача ЛП имеет допустимое решение, то она имеет и допустимое базисное решение.

Утверждение.
Если задача ЛП имеет оптимальное решение, то она имеет и оптимальное базисное решение.

симплексная таблица называется оптимальной, если она одновременно и прямо-допустимая, и двойственно-допустимая. Оптимальная СТ соответствует оптимальному базисному решению.

Если то текущее базисное решение является оптимальным.

Столбец s называется ведущим столбцом СТ.

1. Проверка оптимальности или нахождение ведущего столбца СТ.

ИТЕРАЦИЯ

В противном случае следует выводить из базиса переменную, для которой:

Строка под номером r называется ведущей строкой СТ,

3. Преобразование СТ.

то решение задачи неограниченно.

− ведущим элементом СТ,

Транспортная задача (ТЗ)

Содержательная постановка:

Метод северо-западного угла

в получившейся матрице вычеркнуть все столбцы, содержащие не более одного положительного элемента;

далее процесс вычеркивания строк и столбцов применя-
ется к оставшейся подматрице.

Процесс заканчивается одним из двух исходов:

1. Все строки (столбцы) вычеркнуты. Тогда Х − опорный.

2. Получена подматрица, в каждой строке (столбце) которой не менее 2 положительных элементов. Х − не опорный. Из оставшихся элементов можно построить цикл.