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

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

Содержание ▲

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

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

Слайд 1

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

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

Слайд 2

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

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

Слайд 3

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

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

Слайд 4

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

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

Слайд 5

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

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

Слайд 6

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

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

Слайд 7

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

КЗЛП имеет вид:

Слайд 8

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

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

Слайд 9

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

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

Слайд 10

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

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

Слайд 11

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

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

Слайд 12

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

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

Слайд 13

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

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

Слайд 14

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

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

Слайд 15

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

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

Слайд 16

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

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

Слайд 17

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

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