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

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

Электронные таблицы Электронные таблицы 122
Криптография и компьютерная безопасность Криптография и компьютерная безопасность 105
OpenGL и Direct3D OpenGL и Direct3D 134
Модем Модем 346
Действия с информацией Действия с информацией 126
Построение двоичного сумматора в программе Logisim Построение двоичного сумматора в программе Logisim 269
Презентация. Психология розового цвета Презентация. Психология розового цвета 143
Мастер-класс Создание видеороликов в программе Photodex ProShow Producer Мастер-класс Создание видеороликов в программе Photodex ProShow Producer 136
мышь мышь 123
Компьютерные вирусы и антивирусные программы Компьютерные вирусы и антивирусные программы 115
Тест Успешный в информатике 9 класс Тест Успешный в информатике 9 класс 169
Системы электронного голосования Системы электронного голосования 133
Презентация по информатике на тему Решение логических задач Презентация по информатике на тему Решение логических задач 147
Разработка на тему: Информация. Средства массовой информации Разработка на тему: Информация. Средства массовой информации 166
Назначение и устройство компьютера Назначение и устройство компьютера 142
Архитектура ORACLE. Области оперативной памяти (Лекция 5) Архитектура ORACLE. Области оперативной памяти (Лекция 5) 119
Как создать сайт? Как создать сайт? 132
Программирование на Паскале – первый уровень Программирование на Паскале – первый уровень 106
Условный оператор Условный оператор 130
Внеклассное мероприятие в 3 - 4 классах - Путешествие в Компьюрландию методическая разработка по информатике (3 класс) по теме Внеклассное мероприятие в 3 - 4 классах - Путешествие в Компьюрландию методическая разработка по информатике (3 класс) по теме 135
Бесплатные аналоги коммерческих программ для Windows Бесплатные аналоги коммерческих программ для Windows 135
Основы HTML Основы HTML 163
Электронная почта Электронная почта 107
Язык программирования Turbo Pascal 7.0 Язык программирования Turbo Pascal 7.0 146
Урок 2. Введение в информатику Урок 2. Введение в информатику 155
Информационная система автоматизированного управления работой сервиса по ремонту автомобилей Информационная система автоматизированного управления работой сервиса по ремонту автомобилей 137
Программирование циклов Программирование циклов 120
Validation and use of exce spreadsheets in regulated environments. (Part 11) Validation and use of exce spreadsheets in regulated environments. (Part 11) 185
Основные устройства компьютера Основные устройства компьютера 116
Видеокарты Видеокарты 132