🗊Презентация Автоматизация системного проектирования

Тема 2: Автоматизация системного проектирования Задачи и методы параметрической оптимизации Методы и алгоритмы решения задач линейного программирования Табличный симплекс-метод Венгерский метод

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

Постановка задачи параметрической оптимизации Формализация задачи оптимизации сводится к её формулированию в виде задачи математического программирования:

Линейное программирование (ЛП)

Симплекс-метод - предложен Данцигом (1951 г.) Идея состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается пока не будет достигнут оптимум.

Алгоритм симплекс-метода Подготовительный этап  Приводим задачу ЛП  к каноническому виду F=a0,1x1+a0,2x2+...a0,nxn +b0 → max a1,1x1+a1,2x2+...a1,nxn+xn+1=b1 a2,1x1+a2,2x2+...a2,nxn+xn+2=b2 ....................................... am,1x1+am,2x2+...am,nxn+xn+m=bm

Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче

Шаг 1. Проверка на допустимость Проверяем на положительность элементы столбца b, если среди них нет отрицательных то найдено допустимое решение, переходим к шагу 2.  Если в столбце b имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке находим максимальный по модулю отрицательный элемент ak,l - он задает ведущий столбец - l и является ведущим элементом.  Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно правилам. Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.

Шаг 2. Проверка на оптимальность На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность. Если в строке F (не беря в расчет элемент b0 - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение. Если в строке F есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b0) a0,l=min{a0,i } l – ведущий столбец bk/ak,l =min {bi/ai,l } при ai,l>0, bi>0 k – ведущая cтрока. Элемент ak,l - ведущий (разрешающий).

Пересчитываем симплекс-таблицу по формулам. Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2 Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена - алгоритм завершает работу. Если в строке F и в столбце свободных b членов все элементы положительные, то найдено оптимальное решение.

Правила преобразований симплексной таблицы При составлении новой симплекс-таблицы в ней происходят следующие изменения:  вместо базисной переменной xk записываем xl; вместо небазисной переменной xl записываем xk.   ведущий элемент заменяется на обратную величину ak,l'= 1/ak,l все элементы ведущего столбца (кроме ak,l) умножаются на -1/ak,l все элементы ведущей строки (кроме ak,l) умножаются на 1/ak,l оставшиеся элементы симплекс-таблицы преобразуются по формуле ai,j'= ai,j- ai,lx ak,j/ ak,l

Правила преобразований симплексной таблицы Схему преобразования элементов симплекс-таблицы (кроме ведущей строки и ведущего столбца) называют схемой ”прямоугольника”.

Пример решения задачи линейного программирования симплекс методом Целевая функция: 2x 1+5x2+3x3+8x4 →min Ограничивающие условия: 3x1+6x2-4x3+x4≤12 4x1-13x2+10x3+5x4≥6 3x1+7x2+x3≥1 Приведем систему ограничений к каноническому виду: -2x 1-5x2-3x3-8x4 →max 3x1+6x2-4x3+x4+x5= 12 -4x1+13x2-10x3-5x4+x6= -6 -3x1-7x2-x3+x7= -1

Формирование исходной симплекс таблицы

Пересчитаем симплекс-таблицу:

Решение задачи о назначении (Венгерский метод) Постановка задачи

Блок-схема алгоритма венгерского метода

Составим матрицу задания:

Первая итерация. Первый этап

Соответствующее значение целевой функции:   F = C21 + C32 + C13 + C44 = 2 + 6 + 6 + 10 = 24.