- •1. Характеристика основных подходов к задачам оптимизации
- •1.1. Модельный подход к постановке и решению задачи оптимизации
- •1.1.1 Применение математической модели оптимизации
- •1.2. Применение физической модели объекта оптимизации
- •1.1.3 Совместное применение (комбинирование) физической и математических моделей
- •1.1.4 Инженерный метод решения практических задач оптимизации
- •1.2. Варианты натурно-модельного подхода к задачам оптимизации
- •1 .2.1. Оптимизация на базе натурно-модельных блоков пересчетными моделями
- •1.2.2. Оптимизация на базе натурного объекта и частичной физической модели
- •1.2.3. Оптимизация на базе совместно использования натурной части о. О.(объекта оптимизации), частичной физической модели оо и частичной математической модели оо
- •1.3. Натурный подход к оптимизации
- •2. Известные математические описания. Модели. Задачи оптимизации
- •2.1 Удовлетворенческая (ограничительная) математическая модель (схема) оптимизации
- •2.2. Математическая постановка (модель) задачи скалярной оптимизации
- •2.3. Математическая постановка (модель) задач векторной оптимизации
- •2.3.5 Способ идеальной точки
- •Коэффициенты важности
- •2.3.6. Отыскание оптимума по Парето
- •2.3.7. Математическая схема (модель) задач нечеткой (размытой) оптимизации
- •2.4 Экспертная система
- •2.5. Процедуры оптимизации решений на основе отбора альтернатив.
- •Классификация задач скалярной оптимизации
- •Некоторые типовые задачи скалярного математического программирования
- •Раздел 3. Некоторые алгоритмы решения задач оптимизации
- •3.1 Поисковые (прямые) алгоритмы оптимизации
- •Алгоритм полного перебора (алгоритм сеток)
- •3.1.2 Алгоритм покоординатного поиска
- •3.1.3 Градиентный алгоритм поиска оптимума с использование реверса (возврата назад)
- •3.1.4 Поиск оптимума в многокритериальном пространстве.
- •3.2 Симплекс-алгоритм решения задачи линейного программирования
- •О методе решения задач злп в случае целочисленности искомых переменных
- •3.3. Алгоритм динамического программирования
- •3.4 Метод последовательного конструирования, анализа и отсеивания вариантов (так называемый киевский веник).
- •3.5 Некоторые алгоритмы теории ...
- •Метод ветвей и границ
- •Оптимизация решений с использованием теории статистических решений (тср)
- •Случай 1.
- •Случай 2
- •Некоторые процедуры Парето-оптимизации
О методе решения задач злп в случае целочисленности искомых переменных
Решение данной задачи возможно путем применения выше рассмотренного метода и округления полученного результата. Такой прием допустим, но не всегда дает требуемой точности, поэтому применяются дополнительные хитрости приема. В частности так называемый алгоритм Гомери.
Суть алгоритма Гомери состоит в следующем: организуется итерационная процедура, на каждом шаге которой отыскивается оптимум с помощью симплекс-метода. Затем ... Если найденное решение не целочисленное, то вводится дополнительное ограничение задачи, которое отсекает найденный оптимум далее цикл повторяется, пока не будет найден целочисленный оптимум.
3.3. Алгоритм динамического программирования
Рассмотрим задачу динамического программирования а затем рассмотрим метод.
Задача формулируется след образом:
Для моментов времени i=1,n найти такие упр-я U=(U1,U2,…,Un), которые переведут объект из состояния в состояние при выполнении ограничений:
Метод динамического программирования включается 3 основных этапа:
Определение оптимального управления Un для последнего шага управления. Это решение соответствует частному значению критерия q завиясящей от управления Un и предыдущего состояния
На n-ом шаге для отыскания местного оптимума делается перебор всех допустимых значений Un и соответствующих ему значений Yn-1. Результат q запоминается.
Определяются условно-оптимальные управления Un-1, Un-2,...,Ui,...U1 аналогично этапу один. При этом вычисляются значения критерия Qn-1, Qn-2,...,Qi,...,Q1 с использованием уравнения следующего уравнения белмана:
Qi=qi(Ui,Yi-1)+Qi+1
Определение оптимального начального состояния Y0 принадлежащего S0 (Y0 ϵ S0)
3.4 Метод последовательного конструирования, анализа и отсеивания вариантов (так называемый киевский веник).
Является развитием динамического программирования, позволяет решать задачи от начала к концу.
Рассмотрем киевский веник на основе графика работы бригады
Дано:
а) Интервал времени [0,T]
б) Перечень работ j=1,2,…,N
в) , где
τ – длительность j-ой работы
τj – количество ресурсов для выполнения работы
f – потери при завершении работы в момент t
г) Интервал [0,T] разбит на подинтервалы
Требуется найти такие , чтобы
при удовлетворении ограничений
Алгоритм метода ПКАОВ (последовательного конструирования анализа и отсеивания вариантов) опирается на след правила доминирования последующих работ (фрагментов графика).
Из двух начальных отрезков графика
длиной n, доминирует над ( , если выполняется условие:
Данное правило представим в виде следующего укрупненного алгоритма:
3.5 Некоторые алгоритмы теории ...
В общем случае в расписании устанавливается:
номенклатуру выполняемых работ
моменты начала и окончания каждой работы
место выполнения
Затраты времени
Рассмотрим задачу составления расписаний и N работ
Задача составления расписания для двух станков предполагает, что задано длительность.
Требуется найти расписание, которое минимизирует суммарное время для выполнения всех работ, которые мы обозначим с учетом следующих условий:
Очередность выполнения этапов работ — неизменно
На каждом станке выполняется одновременно одна работа
Работы выполняются без перерыва если они начаты.
Второй этап не может опережать первый этап
....
Данную задачу решил Джонсон, поэтому способ ее решения называется алгоритмом Джонсона. Сформулируем правило Джонсона:
При произвольном выборе N работ порядок их выполнения, соответствующий минимум T должен быть таким, что работа n предшествует работе n+1 если
Из этого правила следует следующий простой практический алгоритм
Запас
-
n
1
2
3
…
…
…
N
…
…
…
Найти minτ
Если min относится к I степени
Если min относится ко II степени
Вычеркнуть столбец
Перейти к шагу 2-5