Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
23 слайда
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
565.57 kB
Просмотров:
74
Скачиваний:
1
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Тема Автоматизация системного](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img0.jpg)
Содержание слайда: Тема 2: Автоматизация системного проектирования
Задачи и методы параметрической оптимизации
Методы и алгоритмы решения задач линейного программирования
Табличный симплекс-метод
Венгерский метод
№2 слайд![Постановка задачи](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img1.jpg)
Содержание слайда: Постановка задачи параметрической оптимизации
Параметрическая оптимизация – процедура определения внутренних параметров проектируемого объекта заданной структуры, при которых достигается наилучшее сочетание его свойств.
Параметрическая оптимизация включает:
переход от исходной неформальной постановки задачи, выраженной на качественном уровне назначения объекта и требований к его свойствам до математической постановки;
решение задачи сформулированной постановки.
№3 слайд![Постановка задачи](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img2.jpg)
Содержание слайда: Постановка задачи параметрической оптимизации
Формализация задачи оптимизации сводится к её формулированию в виде задачи математического программирования:
№4 слайд![Линейное программирование ЛП](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img3.jpg)
Содержание слайда: Линейное программирование (ЛП)
№5 слайд![](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img4.jpg)
№6 слайд![](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img5.jpg)
№7 слайд![](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img6.jpg)
№8 слайд![Симплекс-метод - предложен](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img7.jpg)
Содержание слайда: Симплекс-метод
- предложен Данцигом (1951 г.)
Идея состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение
целевой функции
улучшается пока не будет достигнут оптимум.
№9 слайд![Алгоритм симплекс-метода](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img8.jpg)
Содержание слайда: Алгоритм симплекс-метода
Подготовительный этап
Приводим задачу ЛП к каноническому виду
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
№10 слайд![Шаг . Составляем симплексную](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img9.jpg)
Содержание слайда: Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче
№11 слайд![Шаг . Проверка на](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img10.jpg)
Содержание слайда: Шаг 1. Проверка на допустимость
Проверяем на положительность элементы столбца b, если среди них нет отрицательных то найдено допустимое решение, переходим к шагу 2.
Если в столбце b имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке находим максимальный по модулю отрицательный элемент ak,l - он задает ведущий столбец - l и является ведущим элементом.
Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласно правилам.
Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.
№12 слайд![Шаг . Проверка на](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img11.jpg)
Содержание слайда: Шаг 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 - ведущий (разрешающий).
№13 слайд![Пересчитываем](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img12.jpg)
Содержание слайда: Пересчитываем симплекс-таблицу по формулам.
Пересчитываем симплекс-таблицу по формулам.
Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2
Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена - алгоритм завершает работу.
Если в строке F и в столбце свободных b членов все элементы положительные, то найдено оптимальное решение.
№14 слайд![Правила преобразований](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img13.jpg)
Содержание слайда: Правила преобразований симплексной таблицы
При составлении новой симплекс-таблицы в ней происходят следующие изменения:
вместо базисной переменной 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
№15 слайд![Правила преобразований](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img14.jpg)
Содержание слайда: Правила преобразований симплексной таблицы
Схему преобразования элементов симплекс-таблицы (кроме ведущей строки и ведущего столбца) называют схемой ”прямоугольника”.
№16 слайд![Пример решения задачи](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img15.jpg)
Содержание слайда: Пример решения задачи линейного программирования симплекс методом
Целевая функция:
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
№17 слайд![Формирование исходной](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img16.jpg)
Содержание слайда: Формирование исходной симплекс таблицы
№18 слайд![Пересчитаем симплекс-таблицу](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img17.jpg)
Содержание слайда: Пересчитаем симплекс-таблицу:
№19 слайд![Решение задачи о назначении](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img18.jpg)
Содержание слайда: Решение задачи о назначении
(Венгерский метод)
Постановка задачи
№20 слайд![Блок-схема алгоритма](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img19.jpg)
Содержание слайда: Блок-схема алгоритма венгерского метода
№21 слайд![Составим матрицу задания](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img20.jpg)
Содержание слайда: Составим матрицу задания:
№22 слайд![Первая итерация. Первый этап](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img21.jpg)
Содержание слайда: Первая итерация. Первый этап
№23 слайд![Соответствующее значение](/documents_6/484f6923e9b35fa135a9db91d5b5d9a9/img22.jpg)
Содержание слайда: Соответствующее значение целевой функции:
F = C21 + C32 + C13 + C44 = 2 + 6 + 6 + 10 = 24.