Презентация на тему глава 2. Линейное программирование

Содержание

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

Слайд 1Математические методы исследования операций
глава 2.
Линейное программирование
Курс для студентов
экономико-математических специальностей
(часть 1)

Математические методы исследования операцийглава 2.Линейное программированиеКурс для студентов экономико-математических специальностей(часть 1)

Слайд 2Линейное программирование 1
Определение задачи ЛП
КЗЛП и построение канонической формы
Первая геометрическая интерпретация и

графический метод решения

Основные теоремы ЛП

Вторая геометрическая интерпретация и базисные планы

Теоремы о базисных планах

Линейное программирование	1Определение задачи ЛПКЗЛП и построение канонической формыПервая геометрическая интерпретация и графический

Слайд 3Линейное программирование 2
Симплекс-метод, алгоритм
Модифицированный симплекс-метод
Симплекс-метод, обоснование
Проблема вырожденности
Альтернативные оптимальные планы
Метод минимизации невязок

Линейное программирование	2Симплекс-метод, алгоритмМодифицированный симплекс-методСимплекс-метод, обоснованиеПроблема вырожденностиАльтернативные оптимальные планыМетод минимизации невязок

Слайд 4Общая задача линейного программирования














Общая задача линейного программирования (ОЗЛП)





Общая задача линейного программирования	Общая задача линейного программирования (ОЗЛП)

Слайд 5Каноническая задача линейного программирования 2












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

Каноническая задача линейного программирования	2Каноническая задача линейного программирования (ОЗЛП)

Слайд 6Построение канонической формы 1













Построение канонической формы	1

Слайд 7Построение канонической формы 2













Построение канонической формы	2

Слайд 8Первая геометрическая интерпретация ЗЛП
x2 ≥ 0
x1 ≥ 0
Рассмотрим задачу-базовый пример

Первая геометрическая интерпретация ЗЛПx2 ≥ 0x1 ≥ 0Рассмотрим задачу-базовый пример

Слайд 9

Графический метод решения ЗЛП 1




Графический метод решения ЗЛП	1

Слайд 10Решение достигается в угловой точке
Принципиальные ситуации, возможные при решении задачи линейного

программирования




(a)

(b)

(c)

Целевая функция не ограничена

Бесконечное множество решений



Решение достигается в угловой точкеПринципиальные ситуации, возможные при решении задачи линейного программирования(a)(b)(c)Целевая

Слайд 11Графический метод решения ЗЛП 2

Рассмотрим задачу


Графический метод решения ЗЛП	2Рассмотрим задачу

Слайд 12 Основные теоремы ЛП 1
☝ Теорема
? Доказательство

Теорема о представлении многогранного выпуклого множества

Основные теоремы ЛП	1☝	Теорема?	ДоказательствоТеорема о представлении многогранного выпуклого множества

Слайд 13Основные теоремы ЛП 2

Основные теоремы ЛП 	2

Слайд 14Основные теоремы ЛП 3






- угловые точки

Основные теоремы ЛП 	3- угловые точки

Слайд 15Основные теоремы ЛП 4







- направляющие вектора конуса





(!) рассуждения «от противного»

Основные теоремы ЛП 	4- направляющие вектора конуса (!) рассуждения «от противного»

Слайд 16Основные теоремы ЛП 5







По свойства многогранного выпуклого конуса:







(1)


?

Основные теоремы ЛП 	5По свойства многогранного выпуклого конуса:(1)?

Слайд 17Основные теоремы ЛП 5














(2)


?


(3)


?

Основные теоремы ЛП 	5(2)?(3)?

Слайд 18Вторая геометрическая интерпретация ЗЛП 1

(!) без ограничения общности
Аx = b несовместна


существуют линейно-зависимые ограничения

Вторая геометрическая интерпретация ЗЛП	1(!) без ограничения общностиАx = b несовместнасуществуют линейно-зависимые ограничения

Слайд 19
Вторая геометрическая интерпретация ЗЛП 1

Вторая геометрическая интерпретация ЗЛП	1

Слайд 20Базисный план 1

Базисный план	1

Слайд 21Базисный план 2

Базисный план	2

Слайд 22Базисный план 3
☞ базисный план-невырожденный:
вырожденный – в противном случае.

Базисный план	3☞	базисный план-невырожденный:вырожденный – в противном случае.

Слайд 23
Базисный план 4

Базисный план	4

Слайд 24 Теоремы о свойствах базисных планов 1
☝ Теорема
Каждый допустимый базисный план является

угловой точкой множества допустимых планов


Теоремы о свойствах базисных планов	1☝	Теорема Каждый допустимый базисный план является угловой

Слайд 25 Теоремы о свойствах базисных планов 2

Теоремы о свойствах базисных планов	2

Слайд 26Базисные планы (пример)

Базисные планы (пример)

Слайд 27 Симплекс-метод, историческая справка
Джордж Данциг (1914-2005), 1947
Леонид Витальевич Канторович (1912-1986), 1939

Симплекс-метод, историческая справка	Джордж Данциг (1914-2005), 1947Леонид Витальевич Канторович (1912-1986), 1939

Слайд 28
Симплекс-метод, геометр. интерпретация 1


Симплекс-метод, геометр. интерпретация	1

Слайд 29Симплекс-метод, геометр. интерпретация 2

Симплекс-метод, геометр. интерпретация	2

Слайд 30


Симплекс-метод, геометр. интерпретация 3









Симплекс-метод, геометр. интерпретация	3

Слайд 31Симплекс-метод алгоритм
0-итерация: Определение исходного допустимого базисного плана
Определение выводимого столбца


Симплекс-метод алгоритм0-итерация: Определение исходного допустимого базисного планаОпределение выводимого столбца

Слайд 32Симплекс-метод критерий оптимальности

Симплекс-метод критерий оптимальности

Слайд 33Симплекс-метод определение выводимого столбца

Симплекс-метод определение выводимого столбца

Слайд 34Симплекс-метод, неограниченность

Симплекс-метод, неограниченность

Слайд 35Симплекс-метод, симплекс-таблица
Номера базисных столбцов
Столбец ограничений в текущем базисе
Матрица задачи в текущем

базисе

Строка «оценок»

Значение цел.функции на текущем плане

Значения λ, рассч.при определен. выводимого столбца


Симплекс-метод, симплекс-таблицаНомера базисных столбцовСтолбец ограничений в текущем базисеМатрица задачи в текущем базисеСтрока

Слайд 36Симплекс-метод, пример (0)



Исходный допустимый базис

Симплекс-метод, пример (0)Исходный допустимый базис

Слайд 37Симплекс-метод, пример (1)







Симплекс-метод, пример (1)

Слайд 38


Симплекс-метод, пример (2)






35:7=5
8:1=8

Разрешающий элемент
:7





5:5/7=7
3:9/7=7/3


Разрешающий элемент


Симплекс-метод, пример (2)35:7=58:1=8Разрешающий элемент:75:5/7=73:9/7=7/3Разрешающий элемент

Слайд 39Симплекс-метод, пример (3)

План оптимальный !!!

Симплекс-метод, пример (3)План оптимальный !!!

Слайд 40Симплекс-метод, метод минимизации невязок

Симплекс-метод, метод минимизации невязок

Слайд 41Обоснование симплекс-метода Т1/1

Обоснование симплекс-метода	Т1/1

Слайд 42Обоснование симплекс-метода Т1/2

Обоснование симплекс-метода	Т1/2

Слайд 43Обоснование симплекс-метода Т2/1
(T2.1)

Обоснование симплекс-метода	Т2/1(T2.1)

Слайд 44Обоснование симплекс-метода Т2/2

?

?

Обоснование симплекс-метода	Т2/2??

Слайд 45Обоснование симплекс-метода Т2/3

Обоснование симплекс-метода	Т2/3

Слайд 46Обоснование симплекс-метода Т3/1
(T3.1)

Обоснование симплекс-метода	Т3/1(T3.1)

Слайд 47Обоснование симплекс-метода Т4/1

Обоснование симплекс-метода	Т4/1

Слайд 48Сходимость симплекс-метода и проблема вырожденности 1
Рассмотрим пример

Сходимость симплекс-метода и проблема вырожденности	1Рассмотрим пример

Слайд 49Сходимость симплекс-метода и проблема вырожденности 2

Сходимость симплекс-метода и проблема вырожденности	2

Слайд 50Сходимость симплекс-метода и проблема вырожденности 3

Сходимость симплекс-метода и проблема вырожденности	3

Слайд 51Сходимость симплекс-метода и проблема вырожденности 4


Сходимость симплекс-метода и проблема вырожденности	4

Слайд 52

Сходимость симплекс-метода и проблема вырожденности 5

(☝) Базовая идея: переход к «возмущённой» задаче
(В.1)

Сходимость симплекс-метода и проблема вырожденности	5(☝) Базовая идея: переход к «возмущённой» задаче(В.1)

Слайд 53(☝) Теорема Чарнса
Сходимость симплекс-метода и проблема вырожденности 6

(☝) Теорема ЧарнсаСходимость симплекс-метода и проблема вырожденности	6

Слайд 54 Альтернативные оптимальные планы 1
Рассмотрим пример

Альтернативные оптимальные планы	1Рассмотрим пример

Слайд 55 Альтернативные оптимальные планы 2




Альтернативные оптимальные планы	2

Слайд 56 Альтернативные оптимальные планы 3


Альтернативные оптимальные планы	3

Слайд 57 Модифицированный симплекс-метод 1

Модифицированный симплекс-метод	1

Слайд 58 Модифицированный симплекс-метод 2

Модифицированный симплекс-метод	2

Слайд 59
Модифицированный симплекс-метод, пример 1









Модифицированный симплекс-метод, пример	1

Слайд 60 Модифицированный симплекс-метод, пример 2

Модифицированный симплекс-метод, пример	2

Слайд 61 Модифицированный симплекс-метод, пример 3

Модифицированный симплекс-метод, пример	3

Слайд 62 Модифицированный симплекс-метод, мультипликативная форма 3


r-й столбец:

Мультипликативная форма

Модифицированный симплекс-метод, мультипликативная форма 	3r-й столбец:Мультипликативная  форма

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

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

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

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

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


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

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