ThePresentation^ru

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

Содержание

1. глава 2. Линейное программирование
2. Линейное программирование 1 Определение задачи ЛП КЗЛП и
3. Линейное программирование 2 Симплекс-метод, алгоритм Модифицированный симплекс-метод Симплекс-метод,
4. Общая задача линейного программирования
5. Каноническая задача линейного программирования 2
6. Построение канонической формы 1
7. Построение канонической формы 2
8. Первая геометрическая интерпретация ЗЛП x2 ≥ 0 x1 ≥ 0 Рассмотрим задачу-базовый пример
9. Графический метод решения ЗЛП 1
10. Решение достигается в угловой точке Принципиальные ситуации,
11. Графический метод решения ЗЛП 2 Рассмотрим задачу
12. Основные теоремы ЛП 1 ☝ Теорема ? Доказательство Теорема о представлении многогранного выпуклого множества
13. Основные теоремы ЛП 2
14. Основные теоремы ЛП 3 - угловые точки
15. Основные теоремы ЛП 4
16. Основные теоремы ЛП 5
17. Основные теоремы ЛП 5
18. Вторая геометрическая интерпретация ЗЛП 1 (!) без
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)
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
53. (☝) Теорема Чарнса Сходимость симплекс-метода и проблема вырожденности 6
54. Альтернативные оптимальные планы 1 Рассмотрим пример
55. Альтернативные оптимальные планы 2
56. Альтернативные оптимальные планы 3
57. Модифицированный симплекс-метод 1
58. Модифицированный симплекс-метод 2
59. Модифицированный симплекс-метод, пример 1
60. Модифицированный симплекс-метод, пример 2
61. Модифицированный симплекс-метод, пример 3
62. Модифицированный симплекс-метод, мультипликативная форма 3 r-й столбец: Мультипликативная форма

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

Главная
Разное
глава 2. Линейное программирование

Слайд 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. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

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