Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

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

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

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

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

Презентация на тему Метод линейного программирования

Содержание

Линейное программирование 1Определение задачи ЛПКЗЛП и построение канонической формыПервая геометрическая интерпретация и графический метод решенияОсновные теоремы ЛПВторая геометрическая интерпретация и базисные планыТеоремы о базисных планах
Математические методы исследования операцийглава 2.Линейное программированиеКурс для студентов экономико-математических специальностей(часть 1) Линейное программирование 1Определение задачи ЛПКЗЛП и построение канонической формыПервая геометрическая интерпретация и графический Линейное программирование 2Симплекс-метод, алгоритмМодифицированный симплекс-методСимплекс-метод, обоснованиеПроблема вырожденностиАльтернативные оптимальные планыМетод минимизации невязок Общая задача линейного программирования Общая задача линейного программирования (ОЗЛП) Каноническая задача линейного программирования 2Каноническая задача линейного программирования (ОЗЛП) Построение канонической формы 1 Построение канонической формы 2 Первая геометрическая интерпретация ЗЛПx2 ≥ 0x1 ≥ 0Рассмотрим задачу-базовый пример Графический метод решения ЗЛП 1 Решение достигается в угловой точкеПринципиальные ситуации, возможные при решении задачи линейного программирования(a)(b)(c)Целевая Графический метод решения ЗЛП 2Рассмотрим задачу Основные теоремы ЛП 1☝ Теорема? ДоказательствоТеорема о представлении многогранного выпуклого множества Основные теоремы ЛП 2 Основные теоремы ЛП 3- угловые точки Основные теоремы ЛП 4- направляющие вектора конуса (!) рассуждения «от противного» Основные теоремы ЛП 5По свойства многогранного выпуклого конуса:(1)? Основные теоремы ЛП 5(2)?(3)? Вторая геометрическая интерпретация ЗЛП 1(!) без ограничения общностиАx = b несовместнасуществуют линейно-зависимые ограничения Вторая геометрическая интерпретация ЗЛП 1 Базисный план 1 Базисный план 2 Базисный план 3☞ базисный план-невырожденный:вырожденный – в противном случае. Базисный план 4 Теоремы о свойствах базисных планов 1☝ Теорема Каждый допустимый базисный план является угловой Теоремы о свойствах базисных планов 2 Базисные планы (пример) Симплекс-метод, историческая справка Джордж Данциг (1914-2005), 1947Леонид Витальевич Канторович (1912-1986), 1939 Симплекс-метод, геометр. интерпретация 1 Симплекс-метод, геометр. интерпретация 2 Симплекс-метод, геометр. интерпретация 3 Симплекс-метод алгоритм0-итерация: Определение исходного допустимого базисного планаОпределение выводимого столбца Симплекс-метод критерий оптимальности Симплекс-метод определение выводимого столбца Симплекс-метод, неограниченность Симплекс-метод, симплекс-таблицаНомера базисных столбцовСтолбец ограничений в текущем базисеМатрица задачи в текущем базисеСтрока Симплекс-метод, пример (0)Исходный допустимый базис Симплекс-метод, пример (1) Симплекс-метод, пример (2)35:7=58:1=8Разрешающий элемент:75:5/7=73:9/7=7/3Разрешающий элемент Симплекс-метод, пример (3)План оптимальный !!! Симплекс-метод, метод минимизации невязок Обоснование симплекс-метода Т1/1 Обоснование симплекс-метода Т1/2 Обоснование симплекс-метода Т2/1(T2.1) Обоснование симплекс-метода Т2/2?? Обоснование симплекс-метода Т2/3 Обоснование симплекс-метода Т3/1(T3.1) Обоснование симплекс-метода Т4/1 Сходимость симплекс-метода и проблема вырожденности 1Рассмотрим пример Сходимость симплекс-метода и проблема вырожденности 2 Сходимость симплекс-метода и проблема вырожденности 3 Сходимость симплекс-метода и проблема вырожденности 4 Сходимость симплекс-метода и проблема вырожденности 5(☝) Базовая идея: переход к «возмущённой» задаче(В.1) (☝) Теорема ЧарнсаСходимость симплекс-метода и проблема вырожденности 6 Альтернативные оптимальные планы 1Рассмотрим пример Альтернативные оптимальные планы 2 Альтернативные оптимальные планы 3 Модифицированный симплекс-метод 1 Модифицированный симплекс-метод 2 Модифицированный симплекс-метод, пример 1 Модифицированный симплекс-метод, пример 2 Модифицированный симплекс-метод, пример 3 Модифицированный симплекс-метод, мультипликативная форма 3r-й столбец:Мультипликативная форма
Слайды презентации

Слайд 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)
Целевая функция не ограничена
Бесконечное множество решений


Слайд 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 =

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

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

(☝) Базовая идея: переход

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

к «возмущённой» задаче
(В.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
  • Имя файла: metod-lineynogo-programmirovaniya.pptx
  • Количество просмотров: 171
  • Количество скачиваний: 0
- Предыдущая Конкретный смысл действия деления
Следующая - А. Н. Островского Снегурочка (6 класс)

Похожие презентации

Содержимое системного блока Содержимое системного блока 85
Условная функция со сложными условиями в EXCEL Условная функция со сложными условиями в EXCEL 133
Development of mobile application for equalization of digital audio system Development of mobile application for equalization of digital audio system 85
Краткое введение в Javascript Краткое введение в Javascript 93
Язык разметки гипертекста HTML Язык разметки гипертекста HTML 143
Источники освещения Источники освещения 95
Стандартные приложения Windows Стандартные приложения Windows 112
Технология создания рисунка Лошадь Технология создания рисунка Лошадь 112
Функции дата и время в Microsoft Excel 2007 Функции дата и время в Microsoft Excel 2007 154
Классификация систем искусственного интеллекта Классификация систем искусственного интеллекта 98
Презентация: Изменение формы представления информации Презентация: Изменение формы представления информации 121
Презентация по информатике и ИКТ на тему Информационное моделирование. Графические информационные модели (9 класс) Презентация по информатике и ИКТ на тему Информационное моделирование. Графические информационные модели (9 класс) 117
Система электропитания Система электропитания 30
Процедуры. Как писать программы. (Лекция 8) Процедуры. Как писать программы. (Лекция 8) 101
Исследование методов визуализации семантической сети с использованием графических библиотек Исследование методов визуализации семантической сети с использованием графических библиотек 100
Цикл разработки программного обеспечения Цикл разработки программного обеспечения 105
Социальные сети Социальные сети 95
Создание реляционной БД в среде СУБД ACCESS Создание реляционной БД в среде СУБД ACCESS 81
Power Point 2003 Power Point 2003 137
Системное и прикладное программное обеспечение Системное и прикладное программное обеспечение 120
Microsoft Excel - электронные таблицы Microsoft Excel - электронные таблицы 112
Кодирование текстовой (символьной) информации Кодирование текстовой (символьной) информации 136
Файловые системы. Flash-носители. Конфиденциальность информации Файловые системы. Flash-носители. Конфиденциальность информации 92
Основы синтаксиса. Включение в HTML Основы синтаксиса. Включение в HTML 99
Презентация по информатике на тему PowerPoint (10 класс) Презентация по информатике на тему PowerPoint (10 класс) 106
Защита собственной информации от несанкционированного доступа Защита собственной информации от несанкционированного доступа 104
Мобильный интернет Мобильный интернет 119
Использование компьютера в различных отраслях Использование компьютера в различных отраслях 107
Электронная почта Электронная почта 91
Учебная дисциплина Элементы и узлы ЭВМ. Тема: Триггеры Учебная дисциплина Элементы и узлы ЭВМ. Тема: Триггеры 102