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

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

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

Слайд 1
Текст слайда:

Математические методы исследования операций

глава 2.
Линейное программирование

Курс для студентов
экономико-математических специальностей

(часть 1)


Слайд 2
Текст слайда:

Линейное программирование 1

Определение задачи ЛП

КЗЛП и построение канонической формы

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

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

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

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


Слайд 3
Текст слайда:

Линейное программирование 2

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

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

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

Проблема вырожденности

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

Метод минимизации невязок


Слайд 4
Текст слайда:

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















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







Слайд 5
Текст слайда:

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













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



Слайд 6
Текст слайда:

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















Слайд 7
Текст слайда:

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















Слайд 8
Текст слайда:

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

x2 ≥ 0

x1 ≥ 0

Рассмотрим задачу-базовый пример



Слайд 9
Текст слайда:



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






Слайд 10
Текст слайда:

Решение достигается в угловой точке

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




(a)

(b)

(c)

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

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




Слайд 11
Текст слайда:

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


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




Слайд 12
Текст слайда:

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

☝ Теорема

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


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



Слайд 13
Текст слайда:

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


Слайд 14
Текст слайда:

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







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


Слайд 15
Текст слайда:

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








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






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


Слайд 16
Текст слайда:

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








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








(1)



?


Слайд 17
Текст слайда:

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















(2)



?



(3)



?


Слайд 18
Текст слайда:

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


(!) без ограничения общности

Аx = b несовместна



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


Слайд 19
Текст слайда:


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



Слайд 20
Текст слайда:

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


Слайд 21
Текст слайда:

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


Слайд 22
Текст слайда:

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

☞ базисный план-невырожденный:

вырожденный – в противном случае.


Слайд 23
Текст слайда:


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


Слайд 24
Текст слайда:

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

☝ Теорема

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



Слайд 25
Текст слайда:

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


Слайд 26
Текст слайда:

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



Слайд 27
Текст слайда:

Симплекс-метод, историческая справка

Джордж Данциг (1914-2005), 1947

Леонид Витальевич Канторович (1912-1986), 1939



Слайд 28
Текст слайда:


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




Слайд 29
Текст слайда:

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



Слайд 30
Текст слайда:




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











Слайд 31
Текст слайда:

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

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

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




Слайд 32
Текст слайда:

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



Слайд 33
Текст слайда:

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



Слайд 34
Текст слайда:

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



Слайд 35
Текст слайда:

Симплекс-метод, симплекс-таблица

Номера базисных столбцов

Столбец ограничений в текущем базисе

Матрица задачи в текущем базисе

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

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

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



Слайд 36
Текст слайда:

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




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



Слайд 37
Текст слайда:

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









Слайд 38
Текст слайда:




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







35:7=5

8:1=8


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

:7






5:5/7=7

3:9/7=7/3



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




Слайд 39
Текст слайда:

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


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



Слайд 40
Текст слайда:

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



Слайд 41
Текст слайда:

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



Слайд 42
Текст слайда:

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



Слайд 43
Текст слайда:

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

(T2.1)



Слайд 44
Текст слайда:

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


?


?


Слайд 45
Текст слайда:

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



Слайд 46
Текст слайда:

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

(T3.1)



Слайд 47
Текст слайда:

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



Слайд 48
Текст слайда:

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

Рассмотрим пример



Слайд 49
Текст слайда:

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



Слайд 50
Текст слайда:

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



Слайд 51
Текст слайда:

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




Слайд 52
Текст слайда:



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


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

(В.1)



Слайд 53
Текст слайда:

(☝) Теорема Чарнса

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



Слайд 54
Текст слайда:

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

Рассмотрим пример


Слайд 55
Текст слайда:

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






Слайд 56
Текст слайда:

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




Слайд 57
Текст слайда:

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



Слайд 58
Текст слайда:

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


Слайд 59
Текст слайда:


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











Слайд 60
Текст слайда:

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


Слайд 61
Текст слайда:

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


Слайд 62
Текст слайда:

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



r-й столбец:


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


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

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

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

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

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


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

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