Что такое 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
  • Количество просмотров: 192
  • Количество скачиваний: 1
- Предыдущая Конкретный смысл действия деления
Следующая - А. Н. Островского Снегурочка (6 класс)

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

QBasic QBasic 172
Циклический алгоритм с заданным числом повторений в системе программирования КуМир Циклический алгоритм с заданным числом повторений в системе программирования КуМир 197
Сортировка и поиcк данных в электронных таблицах Excel Сортировка и поиcк данных в электронных таблицах Excel 148
Наука информатика Наука информатика 154
Презентация по информатике Поиск информации в Интернете (5-9 класс) Презентация по информатике Поиск информации в Интернете (5-9 класс) 136
Поиск информации в сети Интернет. Информатика 8 класс ФГОС Поиск информации в сети Интернет. Информатика 8 класс ФГОС 162
Презентация по информатике на тему Компьютерная графика Презентация по информатике на тему Компьютерная графика 139
Аппаратное обеспечение ПК Аппаратное обеспечение ПК 174
Я выбираю профессию в IT. Системный администратор Я выбираю профессию в IT. Системный администратор 226
Использование ИКТ в начальной школе презентация к уроку по информатике (1, 2, 3, 4 класс) Использование ИКТ в начальной школе презентация к уроку по информатике (1, 2, 3, 4 класс) 137
ИНТЕРНЕТ ИНТЕРНЕТ 150
Поиск в базах данных с помощью запросов. Условия поиска Поиск в базах данных с помощью запросов. Условия поиска 143
Защита от несанкционированного доступа к информации Защита от несанкционированного доступа к информации 104
Презентация к уроку по информатике на тему Передача информации (8 класс) Презентация к уроку по информатике на тему Передача информации (8 класс) 128
Программа для хранения данных Рassword Keeper Программа для хранения данных Рassword Keeper 96
Знакомьтесь - системная плата Знакомьтесь - системная плата 132
Интерфейс Power Point 2010. Компонент Лента. презентация к уроку по информатике по теме Интерфейс Power Point 2010. Компонент Лента. презентация к уроку по информатике по теме 149
Системы счисления Системы счисления 137
Игровые движки. Различия в движках 2D и 3D Игровые движки. Различия в движках 2D и 3D 150
Field programmable gate arrays Field programmable gate arrays 160
Презентация по информатике на тему Робик. Цепочка выполнения программы (4 класс) Презентация по информатике на тему Робик. Цепочка выполнения программы (4 класс) 246
Тест по теме Компьютерные вирусы Тест по теме Компьютерные вирусы 134
Таксономия. Тесты Таксономия. Тесты 116
Видеонаблюдение в многоквартирных домах Видеонаблюдение в многоквартирных домах 128
Программное обеспечение Программное обеспечение 115
Профессия техник-программист Профессия техник-программист 129
Действия с фрагментами текста Действия с фрагментами текста 123
Решение задач на кодирование графической информации Решение задач на кодирование графической информации 125
Социальные сети: за и против Социальные сети: за и против 167
Слушайте в Екатеринбурге на частоте 89.2 FM и на www.deti.fm 2 Слушайте в Екатеринбурге на частоте 89.2 FM и на www.deti.fm 2 73