Программирование
<<  Автоматное программирование Задачи линейного программирования  >>
Линейное программирование
Линейное программирование
Построение канонической формы
Построение канонической формы
Симплекс-метод
Симплекс-метод
Общая задача линейного программирования
Общая задача линейного программирования
Каноническая задача линейного программирования
Каноническая задача линейного программирования
Построение
Построение
Построение канонической формы 2
Построение канонической формы 2
Первая геометрическая интерпретация
Первая геометрическая интерпретация
Графический метод решения
Графический метод решения
Ситуации, возможные при решении задачи линейного программирования
Ситуации, возможные при решении задачи линейного программирования
Рассмотрим задачу
Рассмотрим задачу
Теорема
Теорема
Основные теоремы
Основные теоремы
Теоремы ЛП
Теоремы ЛП
Основные теоремы ЛП
Основные теоремы ЛП
Свойства многогранного выпуклого конуса
Свойства многогранного выпуклого конуса
Теоремы
Теоремы
Геометрическая интерпретация
Геометрическая интерпретация
Вторая геометрическая интерпретация
Вторая геометрическая интерпретация
Базисный план
Базисный план
План
План
Базисный план-невырожденный
Базисный план-невырожденный
Базисный план 4
Базисный план 4
Теоремы о свойствах базисных планов
Теоремы о свойствах базисных планов
Теоремы о свойствах
Теоремы о свойствах
Базисные планы
Базисные планы
Историческая справка
Историческая справка
Метод
Метод
Интерпретация
Интерпретация
Симплекс-метод, геометр
Симплекс-метод, геометр
Определение исходного допустимого базисного плана
Определение исходного допустимого базисного плана
Критерий оптимальности
Критерий оптимальности
Определение выводимого столбца
Определение выводимого столбца
Неограниченность
Неограниченность
Симплекс-таблица
Симплекс-таблица
Исходный допустимый базис
Исходный допустимый базис
Пример
Пример
Разрешающий элемент
Разрешающий элемент
План оптимальный
План оптимальный
Метод минимизации невязок
Метод минимизации невязок
Обоснование симплекс-метода
Обоснование симплекс-метода
Обоснование
Обоснование
Обоснование симплекс-метода Т2/1
Обоснование симплекс-метода Т2/1
Обоснование симплекс-метода Т2/2
Обоснование симплекс-метода Т2/2
Обоснование симплекс-метода Т2/3
Обоснование симплекс-метода Т2/3
Обоснование симплекс-метода Т3/1
Обоснование симплекс-метода Т3/1
Обоснование симплекс-метода Т4/1
Обоснование симплекс-метода Т4/1
Сходимость симплекс-метода
Сходимость симплекс-метода
Проблема вырожденности
Проблема вырожденности
Проблема
Проблема
Сходимость
Сходимость
Базовая идея
Базовая идея
Теорема Чарнса
Теорема Чарнса
Альтернативные оптимальные планы
Альтернативные оптимальные планы
Оптимальные планы
Оптимальные планы
Планы
Планы
Модифицированный симплекс-метод
Модифицированный симплекс-метод
Модифицированный симплекс-метод 2
Модифицированный симплекс-метод 2
Модифицированный симплекс-метод, пример 1
Модифицированный симплекс-метод, пример 1
Модифицированный симплекс-метод, пример 2
Модифицированный симплекс-метод, пример 2
Модифицированный симплекс-метод, пример 3
Модифицированный симплекс-метод, пример 3
Мультипликативная форма
Мультипликативная форма
Презентация «Метод линейного программирования». Размер 935 КБ. Автор: Павел Конюховский.

Загрузка...

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

содержание презентации «Метод линейного программирования.ppt»
СлайдТекст
1 Линейное программирование

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

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

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

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

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

3 Симплекс-метод

Симплекс-метод

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

4 Общая задача линейного программирования

Общая задача линейного программирования

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

5 Каноническая задача линейного программирования

Каноническая задача линейного программирования

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

6 Построение

Построение

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

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

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

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

8 Первая геометрическая интерпретация

Первая геометрическая интерпретация

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

9 Графический метод решения

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

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

10 Ситуации, возможные при решении задачи линейного программирования

Ситуации, возможные при решении задачи линейного программирования

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

11 Рассмотрим задачу

Рассмотрим задачу

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

12 Теорема

Теорема

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

13 Основные теоремы

Основные теоремы

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

14 Теоремы ЛП

Теоремы ЛП

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

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

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

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

16 Свойства многогранного выпуклого конуса

Свойства многогранного выпуклого конуса

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

17 Теоремы

Теоремы

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

18 Геометрическая интерпретация

Геометрическая интерпретация

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

19 Вторая геометрическая интерпретация

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

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

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

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

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

21 План

План

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

22 Базисный план-невырожденный

Базисный план-невырожденный

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

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

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

Базисный план 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 Симплекс-таблица

Симплекс-таблица

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

36 Исходный допустимый базис

Исходный допустимый базис

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

37 Пример

Пример

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

38 Разрешающий элемент

Разрешающий элемент

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

39 План оптимальный

План оптимальный

Симплекс-метод, пример (3). План оптимальный !!! 1. 2. 61/3. 0. 0. 5/9. 1/9. 10/3. 1. 0. 2/9. –5/9. 7/3. 0. 1. –1/9. 7/9.

40 Метод минимизации невязок

Метод минимизации невязок

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

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

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

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

42 Обоснование

Обоснование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обоснование симплекс-метода Т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

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

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

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

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

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

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

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

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

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

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

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

62 Мультипликативная форма

Мультипликативная форма

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

«Метод линейного программирования»
Сайт

5informatika.net

115 тем
5informatika.net > Программирование > Метод линейного программирования.ppt