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

Нажмите для полного просмотра!
Симплекс-метод решения задач линейного программирования, слайд №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

Содержание

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

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


Слайд 1


Симплекс-метод решения задач линейного программирования, слайд №1
Описание слайда:

Слайд 2





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

Слайд 3





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


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

Слайд 4





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

Слайд 5





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

Слайд 6





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

Слайд 7


Симплекс-метод решения задач линейного программирования, слайд №7
Описание слайда:

Слайд 8


Симплекс-метод решения задач линейного программирования, слайд №8
Описание слайда:

Слайд 9


Симплекс-метод решения задач линейного программирования, слайд №9
Описание слайда:

Слайд 10





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

Слайд 11


Симплекс-метод решения задач линейного программирования, слайд №11
Описание слайда:

Слайд 12





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

Слайд 13


Симплекс-метод решения задач линейного программирования, слайд №13
Описание слайда:

Слайд 14





Критерий оптимальности опорного плана
	Теорема 3
	Пусть все симплекс - разности матрицы           неотрицательные. Тогда опорный план          , определяемый матрицей            , является оптимальным.  
	Доказательство.
		По условиям теоремы 
				или
									(8)
	Пусть
				  
				  Произвольный план ЗЛП.
		Умножим левую и правую части (8) на      , тогда в силу неотрицательности       получим
									    (9)
Описание слайда:
Критерий оптимальности опорного плана Теорема 3 Пусть все симплекс - разности матрицы неотрицательные. Тогда опорный план , определяемый матрицей , является оптимальным. Доказательство. По условиям теоремы или (8) Пусть Произвольный план ЗЛП. Умножим левую и правую части (8) на , тогда в силу неотрицательности получим (9)

Слайд 15





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

Слайд 16





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

Слайд 17





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

Слайд 18





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

Слайд 19





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

Слайд 20





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

Слайд 21





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

Слайд 22





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

Слайд 23





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

Слайд 24





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

Слайд 25





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

Слайд 26





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

Слайд 27





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



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