Методы оптимальных решений. Симплексный метод - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Методы оптимальных решений. Симплексный метод, слайд №1

Методы оптимальных решений. Симплексный метод, слайд №2

Методы оптимальных решений. Симплексный метод, слайд №3

Методы оптимальных решений. Симплексный метод, слайд №4

Методы оптимальных решений. Симплексный метод, слайд №5

Методы оптимальных решений. Симплексный метод, слайд №6

Методы оптимальных решений. Симплексный метод, слайд №7

Методы оптимальных решений. Симплексный метод, слайд №8

Методы оптимальных решений. Симплексный метод, слайд №9

Методы оптимальных решений. Симплексный метод, слайд №10

Методы оптимальных решений. Симплексный метод, слайд №11

Методы оптимальных решений. Симплексный метод, слайд №12

Методы оптимальных решений. Симплексный метод, слайд №13

Методы оптимальных решений. Симплексный метод, слайд №14

Методы оптимальных решений. Симплексный метод, слайд №15

Методы оптимальных решений. Симплексный метод, слайд №16

Методы оптимальных решений. Симплексный метод, слайд №17

Методы оптимальных решений. Симплексный метод, слайд №18

Методы оптимальных решений. Симплексный метод, слайд №19

Методы оптимальных решений. Симплексный метод, слайд №20

Методы оптимальных решений. Симплексный метод, слайд №21

Методы оптимальных решений. Симплексный метод, слайд №22

Методы оптимальных решений. Симплексный метод, слайд №23

Методы оптимальных решений. Симплексный метод, слайд №24

Методы оптимальных решений. Симплексный метод, слайд №25

Методы оптимальных решений. Симплексный метод, слайд №26

Методы оптимальных решений. Симплексный метод, слайд №27

Методы оптимальных решений. Симплексный метод, слайд №28

Методы оптимальных решений. Симплексный метод, слайд №29

Методы оптимальных решений. Симплексный метод, слайд №30

Методы оптимальных решений. Симплексный метод, слайд №31

Методы оптимальных решений. Симплексный метод, слайд №32

Методы оптимальных решений. Симплексный метод, слайд №33

Методы оптимальных решений. Симплексный метод, слайд №34

Методы оптимальных решений. Симплексный метод, слайд №35

Методы оптимальных решений. Симплексный метод, слайд №36

Методы оптимальных решений. Симплексный метод, слайд №37

Методы оптимальных решений. Симплексный метод, слайд №38

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Методы оптимальных решений. Симплексный метод. Доклад-сообщение содержит 38 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Дисциплина МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ Кафедра математических методов в экономике

Слайд 2

Описание слайда:

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗЛП Введение. Определение К-матрицы в КЗЛП Переход от одной К-матрицы КЗЛП к другой К-матрице Симплекс-разность К-матрицы КЗЛП Способ построения опорного плана, более близкого к оптимальному Критерий оптимальности опорного плана Критерий отсутствия конечного решения Алгоритм симплексного метода Пример 1 Пример 2

Слайд 3

Описание слайда:

Слайд 4

Описание слайда:

Слайд 5

Описание слайда:

Слайд 6

Описание слайда:

Слайд 7

Описание слайда:

Пусть требуется решить задачу (1) Или (2)

Слайд 8

Описание слайда:

Так как решением задачи (2) является крайняя точка множества Р ее допустимых решений, или, что то же самое, неотрицательное базисное решение системы линейных уравнений , то метод решения задачи (1) должен содержать 4 момента: Так как решением задачи (2) является крайняя точка множества Р ее допустимых решений, или, что то же самое, неотрицательное базисное решение системы линейных уравнений , то метод решения задачи (1) должен содержать 4 момента: 1) обоснование способа перехода от одного опорного плана (К-матрицы) к другому; 2) указание признака оптимальности, позволяющего проверить, является ли данный опорный план оптимальным; 3) указание способа построения нового опорного плана, более близкого к оптимальному; 4) указание признака отсутствия конечного решения.

Слайд 9

Описание слайда:

Определение К-матрицы в КЗЛП Рассмотрим каноническую задачу линейного программирования (КЗЛП): Будем считать, что ранг матрицы А равен m, причем m

Слайд 10

Описание слайда:

Переход от одной К-матрицы ЗЛП к другой К-матрице. Пусть известна К-матрица (3) Обозначим через вектор номеров базисных (единичных) столбцов матрицы , - вектор, компоненты которого есть базисные компоненты опорного плана, определяемого матрицей , и могут быть отличны от нуля.

Слайд 11

Описание слайда:

Слайд 12

Описание слайда:

Слайд 13

Описание слайда:

Слайд 14

Описание слайда:

Слайд 15

Описание слайда:

Возьмем в матрице столбец К , не принадлежащий единичной подматрице ( , ) и такой, что в этом столбце есть хотя бы один отличный от нуля элемент. Возьмем в матрице столбец К , не принадлежащий единичной подматрице ( , ) и такой, что в этом столбце есть хотя бы один отличный от нуля элемент. Пусть . Считая направляющим элементом, совершим над матрицей один шаг метода Жордана-Гаусса. В результате получим новую матрицу , элементы которой выражаются через элементы матрицы по следующим формулам:

Слайд 16

Описание слайда:

Слайд 17

Описание слайда:

Слайд 18

Описание слайда:

Слайд 19

Описание слайда:

Слайд 20

Описание слайда:

Симплекс-разность К-матриц ЗЛП. Изменение функции при переходе от одной К-матрицы к другой.

Слайд 21

Описание слайда:

Слайд 22

Описание слайда:

Способ построения опорного плана (матрицы ), более близкого к оптимальному, чем

Слайд 23

Описание слайда:

Критерий оптимальности опорного плана Теорема 3 Пусть все симплекс - разности матрицы неотрицательные. Тогда опорный план , определяемый матрицей , является оптимальным.

Слайд 24

Описание слайда:

Критерий отсутствия конечного решения. Теорема 4 Пусть в матрице есть , и в столбце ( , ) нет ни одного положительного элемента. Тогда ЗЛП (1) не имеет конечного решения.

Слайд 25

Описание слайда:

Алгоритм симплекс-метода Пусть известна исходная К-матрица ЗЛП, определяющая исходный опорный план Последовательно строятся К-матрицы ЗЛП, пока не выполнится критерий оптимальности или критерий, позволяющий убедиться в отсутствии конечного решения. Рассмотрим алгоритм S-ой итерации симплекс-метода. В начале S-ой итерации имеем К-матрицу ЗЛП, определяющую опорный план

Слайд 26

Описание слайда:

Шаг 1. Шаг 1. Вычисляем для столбцов матрицы , симплекс-разности и находим номер К из условия Шаг 2. Если , то опорный план является оптимальным, а есть оптимальное значение линейной формы , иначе переходим к шагу 3 Шаг 3. Если то ЗЛП не имеет конечного решения. Иначе находим номер L из условия ; направляющий элемент на S-ой итерации метода есть элемент

Слайд 27

Описание слайда:

Шаг 4. Шаг 4. Вычисляем компоненты вектора : Шаг 5. Производим один шаг метода Жордана-Гаусса с направляющим элементом . Присваиваем переменной S алгоритма значение S+1 и переходим к шагу 1.

Слайд 28

Описание слайда:

Пример 1 Симплекс-методом решить ЗЛП: (1) (2)

Слайд 29

Описание слайда:

Приводим систему линейных неравенств (2) к каноническому виду, вводя в каждое неравенство дополнительную переменную Приводим систему линейных неравенств (2) к каноническому виду, вводя в каждое неравенство дополнительную переменную , . Получим систему линейных уравнений: (3)

Слайд 30

Описание слайда:

Целевая функция (1) будет иметь вид Целевая функция (1) будет иметь вид Расширенная матрица системы линейных уравнений (3) является исходной К-матрицей ЗЛП, которая определяет исходный опорный план:

Слайд 31

Описание слайда:

Введём следующие обозначения: Введём следующие обозначения: S-номер итерации i-номера строк таблицы -номера столбцов, образующих единичную подматрицу -коэффициенты целевой функции при столбцах, образующих единичную подматрицу -соответствуют переменным задачи -сначала содержит правые части системы уравнений , в конце алгоритма - искомые значения переменных -для вычисления значений

Слайд 32

Описание слайда:

Результаты последовательных итераций симплекс-алгоритма оформим в виде симплекс-таблицы. Результаты последовательных итераций симплекс-алгоритма оформим в виде симплекс-таблицы.

Слайд 33

Описание слайда:

Пересчёт таблицы

Слайд 34

Описание слайда:

На второй итерации S=2, все следовательно, опорный план На второй итерации S=2, все следовательно, опорный план определяемый К-матрицей , оптимальный, Оптимальное значение линейной формы равно:

Слайд 35

Описание слайда:

Пример 2 Симплекс-методом решить ЗЛП: (4) (5) Приводим ЗЛП (4-5) к каноническому виду (6)

Слайд 36

Описание слайда:

Результаты последовательных итераций запишем в симплекс-таблицу. Результаты последовательных итераций запишем в симплекс-таблицу.

Слайд 37

Описание слайда:

Из симплекс-таблицы при S=2 следует, что согласно шагу 3 Из симплекс-таблицы при S=2 следует, что согласно шагу 3 симплекс-алгоритма, данная ЗЛП не имеет конечного решения, т.к. отрицательная симплекс-разность соответствует столбцу , все элементы которого неположительны. Итак,

Слайд 38

Описание слайда:

Список литературы Мастяева И.Н., Горемыкина Г.И., Семенихина О.Н., Методы оптимизации: линейные модели. М.: МЭСИ, 2015. Мастяева И.Н., Горемыкина Г.И., Семенихина О.Н., Исследование операций и методы оптимизации. М.: МЭСИ, 2015. Мастяева И.Н., Горемыкина Г.И., Семенихина О.Н., Методы оптимальных решений. М.: Курс, 2016.