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

Тема 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.