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

Постановка задачи параметрической оптимизации

Параметрическая оптимизация – процедура определения внутренних параметров проектируемого

Постановка задачи параметрической оптимизации

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

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

Симплекс-метод - предложен Данцигом (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. Составляем симплексную таблицу, соответствующую исходной задаче

x1, x2, xn - исходные

Шаг 1. Проверка на допустимость

Проверяем на положительность элементы столбца b,

Шаг 2. Проверка на оптимальность

На предыдущем этапе найдено допустимое решение.

Пересчитываем симплекс-таблицу по формулам.
Если в новой таблице после перерасчета в

Правила преобразований симплексной таблицы

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

Правила преобразований симплексной таблицы

Схему преобразования элементов симплекс-таблицы (кроме ведущей строки

Пример решения задачи линейного программирования симплекс методом

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

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

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

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

Ведущей строкой является X2, а ведущий элемент: 0.313. Пересчитаем симплекс-таблицу:

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

Постановка задачи

Вводимые понятия:
- Независимые

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

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

Предварительный этап

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

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

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