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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Двойственный симплекс-метод, слайд №1Двойственный симплекс-метод, слайд №2Двойственный симплекс-метод, слайд №3Двойственный симплекс-метод, слайд №4Двойственный симплекс-метод, слайд №5Двойственный симплекс-метод, слайд №6Двойственный симплекс-метод, слайд №7Двойственный симплекс-метод, слайд №8Двойственный симплекс-метод, слайд №9Двойственный симплекс-метод, слайд №10Двойственный симплекс-метод, слайд №11Двойственный симплекс-метод, слайд №12Двойственный симплекс-метод, слайд №13Двойственный симплекс-метод, слайд №14Двойственный симплекс-метод, слайд №15Двойственный симплекс-метод, слайд №16Двойственный симплекс-метод, слайд №17Двойственный симплекс-метод, слайд №18Двойственный симплекс-метод, слайд №19Двойственный симплекс-метод, слайд №20Двойственный симплекс-метод, слайд №21Двойственный симплекс-метод, слайд №22Двойственный симплекс-метод, слайд №23
Скачать
Вы можете ознакомиться и скачать презентацию на тему Двойственный симплекс-метод. Доклад-сообщение содержит 23 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


Двойственный симплекс-метод
Описание слайда:
Двойственный симплекс-метод

Слайд 2


Введение Рассмотрим следующую задачу линейного программирования (ЗЛП):
Описание слайда:
Введение Рассмотрим следующую задачу линейного программирования (ЗЛП):

Слайд 3


Приведем рассматриваемую ЗЛП к каноническому виду:
Описание слайда:
Приведем рассматриваемую ЗЛП к каноническому виду:

Слайд 4


Рассмотрим расширенную матрицу системы линейных уравнений: Матрица содержит единичную подматрицу порядка 3 и следовательно, определяет базисное решение системы уравнений, причем
Описание слайда:
Рассмотрим расширенную матрицу системы линейных уравнений: Матрица содержит единичную подматрицу порядка 3 и следовательно, определяет базисное решение системы уравнений, причем

Слайд 5


Так как элементы (n+1=6)-го столбца матрицы системы не являются неотрицательными, то она не является К-матрицей ЗЛП. Вычислим симплекс-разности матрицы : Так как все симплекс-разности матрицы являются неотрицательными, то базисное решение не являющееся допустимым решением ЗЛП, является «лучшим», чем оптимальное решение.
Описание слайда:
Так как элементы (n+1=6)-го столбца матрицы системы не являются неотрицательными, то она не является К-матрицей ЗЛП. Вычислим симплекс-разности матрицы : Так как все симплекс-разности матрицы являются неотрицательными, то базисное решение не являющееся допустимым решением ЗЛП, является «лучшим», чем оптимальное решение.

Слайд 6


В чем отличие двойственного симплекс-метода от обычного?? При решении задачи симплекс-методом текущее базисное решение является допустимым, но неоптимальным. Эти соображения позволяют построить метод решения определенного класса ЗЛП. В этом методе, называемом ДВОЙСТВЕННЫМ СИМПЛЕКС-МЕТОДОМ, на каждой итерации обеспечивается выполнение условия оптимальности текущего базисного решения, не являющегося допустимым. Критерием окончания процесса итераций является получение допустимого решения.
Описание слайда:
В чем отличие двойственного симплекс-метода от обычного?? При решении задачи симплекс-методом текущее базисное решение является допустимым, но неоптимальным. Эти соображения позволяют построить метод решения определенного класса ЗЛП. В этом методе, называемом ДВОЙСТВЕННЫМ СИМПЛЕКС-МЕТОДОМ, на каждой итерации обеспечивается выполнение условия оптимальности текущего базисного решения, не являющегося допустимым. Критерием окончания процесса итераций является получение допустимого решения.

Слайд 7


КЗЛП имеет вид:
Описание слайда:
КЗЛП имеет вид:

Слайд 8


Р-матрица. Определение Р-матрицей КЗЛП (1) –(3) называется расширенная матрица системы линейных уравнений, равносильной системе (2), содержащую единичную подматрицу порядка m на месте n первых столбцов, все симплекс-разности которой неотрицательны. Очевидно, что всякая P-матрица ЗЛП определяет некоторое базисное решение системы уравнений (2). Базисное решение системы линейных уравнений , определяемое Р-матрицей, называется псевдопланом ЗЛП.
Описание слайда:
Р-матрица. Определение Р-матрицей КЗЛП (1) –(3) называется расширенная матрица системы линейных уравнений, равносильной системе (2), содержащую единичную подматрицу порядка m на месте n первых столбцов, все симплекс-разности которой неотрицательны. Очевидно, что всякая P-матрица ЗЛП определяет некоторое базисное решение системы уравнений (2). Базисное решение системы линейных уравнений , определяемое Р-матрицей, называется псевдопланом ЗЛП.

Слайд 9


Условие перехода от одной Р-матрицы ЗЛП к другой Пусть известна Р-матрица , определяющая псевдоплан Условия перехода от матрицы к матрице составляют содержание следующей теоремы:
Описание слайда:
Условие перехода от одной Р-матрицы ЗЛП к другой Пусть известна Р-матрица , определяющая псевдоплан Условия перехода от матрицы к матрице составляют содержание следующей теоремы:

Слайд 10


Теорема 1: Пусть и в строке матрицы есть хотя бы один отрицательный элемент. Тогда с помощью одного шага метода Жордана-Гаусса можно построить новую Р-матрицу , выбрав направляющий элемент из условия: Замечание: Если в матрице не , то определяемый ею псевдоплан является решением ЗЛП.
Описание слайда:
Теорема 1: Пусть и в строке матрицы есть хотя бы один отрицательный элемент. Тогда с помощью одного шага метода Жордана-Гаусса можно построить новую Р-матрицу , выбрав направляющий элемент из условия: Замечание: Если в матрице не , то определяемый ею псевдоплан является решением ЗЛП.

Слайд 11


Теорема 2: Пусть и в строке матрицы нет ни одного отрицательного элемента. Тогда множество планов Р ЗЛП (1) - (3) пусто.
Описание слайда:
Теорема 2: Пусть и в строке матрицы нет ни одного отрицательного элемента. Тогда множество планов Р ЗЛП (1) - (3) пусто.

Слайд 12


Теорема 3: При переходе от матрицы к матрице целевая функция изменяется в соответствии с формулой: откуда следует, что т.к. И . Из последнего неравенства следует, что при переходе от одного псевдоплана к другому значению функции не возрастает.
Описание слайда:
Теорема 3: При переходе от матрицы к матрице целевая функция изменяется в соответствии с формулой: откуда следует, что т.к. И . Из последнего неравенства следует, что при переходе от одного псевдоплана к другому значению функции не возрастает.

Слайд 13


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

Слайд 14


Рассмотрим алгоритм S-ой итерации метода последовательного уточнения оценок. В начале S-ой итерации имеем Р-матрицу задачи линейного программирования, определяющую псевдоплан ШАГ 1. Найдем номер из условия
Описание слайда:
Рассмотрим алгоритм S-ой итерации метода последовательного уточнения оценок. В начале S-ой итерации имеем Р-матрицу задачи линейного программирования, определяющую псевдоплан ШАГ 1. Найдем номер из условия

Слайд 15


ШАГ 2. Если , то псевдоплан является оптимальным опорным планом, а есть оптимальное значение линейной формы , иначе переходим к шагу 3.
Описание слайда:
ШАГ 2. Если , то псевдоплан является оптимальным опорным планом, а есть оптимальное значение линейной формы , иначе переходим к шагу 3.

Слайд 16


ШАГ 3. Если то задача линейного программирования не имеет решения (множество планов Р пусто), иначе переходим к шагу 4. ШАГ 4. Вычисляем для столбцов матрицы симплекс-разности и находим номер К из условия:
Описание слайда:
ШАГ 3. Если то задача линейного программирования не имеет решения (множество планов Р пусто), иначе переходим к шагу 4. ШАГ 4. Вычисляем для столбцов матрицы симплекс-разности и находим номер К из условия:

Слайд 17


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

Слайд 18


Решим задачу, которую мы начали пешать в начале презентации. Результаты решения приведены в симплекс-таблице.
Описание слайда:
Решим задачу, которую мы начали пешать в начале презентации. Результаты решения приведены в симплекс-таблице.

Слайд 19


Двойственный симплекс-метод, слайд №19
Описание слайда:

Слайд 20


Двойственный симплекс-метод, слайд №20
Описание слайда:

Слайд 21


Двойственный симплекс-метод, слайд №21
Описание слайда:

Слайд 22


Решим задачу, которую мы начали решать в начале презентации. Результаты решения приведены в симплекс-таблице.
Описание слайда:
Решим задачу, которую мы начали решать в начале презентации. Результаты решения приведены в симплекс-таблице.

Слайд 23


Двойственный симплекс-метод, слайд №23
Описание слайда:

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию