'

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

Понравилась презентация – покажи это...





Слайд 0

Математические методы исследования операций глава 2. Линейное программирование Курс для студентов экономико-математических специальностей (часть 1)


Слайд 1

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


Слайд 2

Линейное программирование 2 Симплекс-метод, алгоритм Модифицированный симплекс-метод Симплекс-метод, обоснование Проблема вырожденности Альтернативные оптимальные планы Метод минимизации невязок


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

Первая геометрическая интерпретация ЗЛП x2 ? 0 x1 ? 0 Рассмотрим задачу-базовый пример


Слайд 8

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


Слайд 9

Решение достигается в угловой точке Принципиальные ситуации, возможные при решении задачи линейного программирования (a) (b) (c) Целевая функция не ограничена Бесконечное множество решений


Слайд 10

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


Слайд 11

Основные теоремы ЛП 1 ? Теорема ? Доказательство Теорема о представлении многогранного выпуклого множества


Слайд 12

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


Слайд 13

Основные теоремы ЛП 3 - угловые точки


Слайд 14

Основные теоремы ЛП 4 - направляющие вектора конуса (!) рассуждения «от противного»


Слайд 15

Основные теоремы ЛП 5 По свойства многогранного выпуклого конуса: (1) ?


Слайд 16

Основные теоремы ЛП 5 (2) ? (3) ?


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

Базисный план 3 ? базисный план-невырожденный: вырожденный – в противном случае.


Слайд 22

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


Слайд 23

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


Слайд 24

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


Слайд 25

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


Слайд 26

Симплекс-метод, историческая справка Джордж Данциг (1914-2005), 1947 Леонид Витальевич Канторович (1912-1986), 1939


Слайд 27

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


Слайд 28

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


Слайд 29

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


Слайд 30

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


Слайд 31

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


Слайд 32

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


Слайд 33

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


Слайд 34

Симплекс-метод, симплекс-таблица Номера базисных столбцов Столбец ограничений в текущем базисе Матрица задачи в текущем базисе Строка «оценок» Значение цел.функции на текущем плане Значения l, рассч.при определен. выводимого столбца


Слайд 35

Симплекс-метод, пример (0) Исходный допустимый базис


Слайд 36

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


Слайд 37

Симплекс-метод, пример (2) 35:7=5 8:1=8 Разрешающий элемент :7 5:5/7=7 3:9/7=7/3 Разрешающий элемент


Слайд 38

Симплекс-метод, пример (3) План оптимальный !!!


Слайд 39

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


Слайд 40

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


Слайд 41

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


Слайд 42

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


Слайд 43

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


Слайд 44

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


Слайд 45

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


Слайд 46

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


Слайд 47

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


Слайд 48

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


Слайд 49

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


Слайд 50

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


Слайд 51

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


Слайд 52

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


Слайд 53

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


Слайд 54

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


Слайд 55

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


Слайд 56

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


Слайд 57

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


Слайд 58

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


Слайд 59

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


Слайд 60

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


Слайд 61

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


×

HTML:





Ссылка: