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

Презентация на тему Презентация на тему Симплекс-метод решения задач линейного программирования, предмет презентации: Математика. Этот материал содержит 27 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

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

Слайд 1
Симплекс-метод решения ЗЛП
Текст слайда:

Симплекс-метод решения
ЗЛП


Слайд 2
АЛГОРИТМ СИМПЛЕКС-МЕТОДАСодержаниеОпределение К-матрицы в КЗЛППереход от одной К-матрицы КЗЛП к другой
Текст слайда:

АЛГОРИТМ СИМПЛЕКС-МЕТОДА

Содержание

Определение К-матрицы в КЗЛП
Переход от одной К-матрицы КЗЛП к другой К-матрице
Симплекс-разность К-матрицы КЗЛП
Способ построения опорного плана, более близкого к оптимальному
Критерий оптимальности опорного плана
Критерий отсутствия конечного решения
Алгоритм симплекс-метода
Пример 1
Пример 2


Слайд 3
Симплекс-методПусть требуется решить задачу   						   (1)Или
Текст слайда:

Симплекс-метод

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


Или

(2)











Симплекс-метод решения ЗЛП


Слайд 4
Симплекс-метод 		Так как решением задачи (2) является крайняя точка множества Р
Текст слайда:

Симплекс-метод

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

1) обоснование способа перехода от одного опорного плана (К-матрицы) к другому;

2) указание признака оптимальности, позволяющего проверить, является ли данный опорный план оптимальным;

3) указание способа построения нового опорного плана, более близкого к оптимальному;

4) указание признака отсутствия конечного решения.



Слайд 5
АЛГОРИТМ СИМПЛЕКС-МЕТОДАОпределение К-матрицы в КЗЛП		Рассмотрим каноническую задачу линейного программирования (КЗЛП): 	Будем
Текст слайда:

АЛГОРИТМ СИМПЛЕКС-МЕТОДА

Определение К-матрицы в КЗЛП

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




Будем считать, что ранг матрицы А равен m, причем m Запишем КЗЛП в векторном виде:

(*)

где – j-й столбец матрицы А.
Дадим одно из определений опорного плана. ОП ЗЛП будем называть такой план , что векторы , входящие в разложение со строго положительными , линейно независимы.
К-матрицей КЗЛП будем называть расширенную матрицу системы линейных уравнений, равносильной системе (*), содержащую единичную подматрицу на месте первых n своих столбцов и все элементы (n+1)-го которой неотрицательны. Число К-матриц конечно и не превышает . Каждая К-матрица определяет ОП КЗЛП и наоборот.


Слайд 6
Переход от одной К-матрицы ЗЛП к другой Переход от одной К-матрицы
Текст слайда:

Переход от одной К-матрицы ЗЛП к другой

Переход от одной К-матрицы ЗЛП к другой К-матрице.

Пусть известна К-матрица

(3)




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








Слайд 7
Переход от одной К-матрицы ЗЛП к другой 	Остальные (n - m)
Текст слайда:

Переход от одной К-матрицы ЗЛП к другой

Остальные (n - m) компонент опорного плана, определяемого матрицей , равны нулю. Очевидно, что векторы и полностью задают опорный план, определяемый матрицей Например, пусть:


,




тогда ; и, следовательно, опорный план, определяемый , имеет вид:














Слайд 8
Переход от одной К-матрицы ЗЛП к другой    Итак,
Текст слайда:

Переход от одной К-матрицы ЗЛП к другой

Итак, пусть К-матрица (3) определяет невырожденный опорный план


Выберем в матрице столбец , не принадлежащий единичной подматрице, т. е. , , и такой, что в этом столбце есть хотя бы один элемент больше нуля.

Пусть . Считая направляющим элементом, совершим над матрицей один шаг метода Жордана - Гаусса. В результате получим новую матрицу



,

в которой стал единичным, но которая может и не быть К-матрицей, т.к. среди величин могут быть отрицательные.


Слайд 9
Переход от одной К-матрицы ЗЛП к другой Теорема 1.
Текст слайда:

Переход от одной К-матрицы ЗЛП к другой

Теорема 1.

Пусть в каком-либо столбце К-матрицы - есть хотя бы

один строго положительный элемент ( , ) . Тогда с помощью

одного шага метода Жордана-Гаусса можно построить новую К-матрицу

, выбрав направляющий элемент из условия











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

Симплекс-разность К-матриц ЗЛП

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


Определение.

Величину

,

где - вектор, компонентами которого являются коэффициенты

линейной функции при базисных ( ) переменных

опорного плана, определяемого матрицей , назовем j-й

симплекс - разностью матрицы .









Слайд 11
Симплекс-разность К-матриц ЗЛППусть       и
Текст слайда:

Симплекс-разность К-матриц ЗЛП



Пусть и - опорные планы, определяемые матрицами

и соответственно. Тогда очевидно, что



и

,


где К-номер столбца , вводимого в базис при получении

матрицы из .












Слайд 12
Способ построения опорного плана Способ построения опорного плана
Текст слайда:

Способ построения опорного плана

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



Теорема 2.

Пусть в матрице есть , и в столбце

( , ) есть хотя бы один строго положительный элемент.

Тогда от матрицы можно перейти к матрице , причем


.










Слайд 13
Способ построения опорного плана Доказательство.		Так как в К-ом столбце К-матрицы	есть строго
Текст слайда:

Способ построения опорного плана

Доказательство.

Так как в К-ом столбце К-матрицы есть строго положительный

элемент, то согласно теореме 1 от матрицы можно перейти к новой

К-матрице ЗЛП, выбрав направляющий элемент из условия (7).

По условию , а по построению ,

поэтому из соотношения

следует
(ч.т.д.)

Если все опорные планы ЗЛП невырождены, то и












Слайд 14
Критерий оптимальности опорного планаКритерий оптимальности опорного плана	Теорема 3	Пусть все симплекс -
Текст слайда:

Критерий оптимальности опорного плана

Критерий оптимальности опорного плана

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

Доказательство.
По условиям теоремы
или
(8)
Пусть

Произвольный план ЗЛП.

Умножим левую и правую части (8) на , тогда в силу неотрицательности получим
(9)


Слайд 15
Критерий оптимальности опорного плана	Согласно (9) имеем:		или	Что и доказывает теорему.
Текст слайда:

Критерий оптимальности опорного плана

Согласно (9) имеем:







или



Что и доказывает теорему.


Слайд 16
Критерий отсутствия конечного решенияКритерий отсутствия конечного решения.	Теорема 4	Пусть в матрице
Текст слайда:

Критерий отсутствия конечного решения

Критерий отсутствия конечного решения.

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

Доказательство.
Пусть К-я симплекс-разность матрицы
(10)
и все
(11)
Матрица определяет опорный план


Слайд 17
Критерий отсутствия конечного решения		Рассмотрим вектор				у которого	где    -любое положительное
Текст слайда:

Критерий отсутствия конечного решения

Рассмотрим вектор


у которого






где -любое положительное число.
Остальные n-m+1 компонент вектора положим равными нулю.
В силу условия (11) компоненты вектора неотрицательны. Легко убедиться в том, что компоненты вектора удовлетворяют и функциональным ограничениям ЗЛП, т.е. вектор - план ЗЛП при любом положительном .


Слайд 18
Критерий отсутствия конечного решения		Имеем:		Или окончательно								(12)		Т.к.
Текст слайда:

Критерий отсутствия конечного решения

Имеем:







Или окончательно
(12)

Т.к. , то из (12) следует, что для любого числа М>0 всегда можно найти план ЗЛП, для которого
т.е. линейная форма не ограничена сверху на множестве планов.
Терема доказана.


Слайд 19
ПРИМЕР №1Пример 1Симплекс-методом решить ЗЛП:  			     												(1)								(2)
Текст слайда:

ПРИМЕР №1

Пример 1

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

(1)



(2)


Слайд 20
ПРИМЕР №1Приводим систему линейных неравенств (2) к каноническому виду, вводя в
Текст слайда:

ПРИМЕР №1

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

Получим систему линейных уравнений:


(3)


Слайд 21
ПРИМЕР №1Целевая функция (1) будет иметь вид Расширенная матрица  системы
Текст слайда:

ПРИМЕР №1

Целевая функция (1) будет иметь вид

Расширенная матрица




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


Слайд 22
ПРИМЕР №1  	Введём следующие обозначения:S-номер итерацииi-номера строк таблицы  -номера
Текст слайда:

ПРИМЕР №1

Введём следующие обозначения:
S-номер итерации

i-номера строк таблицы

-номера столбцов, образующих единичную подматрицу

-коэффициенты целевой функции при столбцах, образующих единичную подматрицу

-соответствуют переменным задачи

-сначала содержит правые части системы уравнений , в конце алгоритма - искомые значения переменных

-для вычисления значений


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

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


Слайд 24
ПРИМЕР №1На второй итерации S=2, все
Текст слайда:

ПРИМЕР №1

На второй итерации S=2, все следовательно, опорный план

определяемый К-матрицей , оптимальный,


Оптимальное значение линейной формы равно:


Слайд 25
ПРИМЕР №2Пример 2Симплекс-методом решить ЗЛП:								(4)								(5)Приводим ЗЛП (4-5) к каноническому виду								(6)
Текст слайда:

ПРИМЕР №2

Пример 2

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

(5)


Приводим ЗЛП (4-5) к каноническому виду

(6)


Слайд 26
ПРИМЕР №2		Результаты последовательных итераций запишем в симплекс-таблицу.
Текст слайда:

ПРИМЕР №2

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


Слайд 27
ПРИМЕР №2Из симплекс-таблице при S=2 следует, что согласно шагу 3 	симплекс-алгоритма
Текст слайда:

ПРИМЕР №2

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


Итак,


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика